AI Insight
This paper introduces HOST, a new algorithm for learning Directed Acyclic Graphs (DAGs) from high-dimensional Gaussian data that achieves both computational efficiency and strong statistical guarantees. The method uses hold-out sample scoring and convex regression to recover causal structures without requiring prior knowledge of the maximum number of parent nodes, achieving exact recovery with sample complexity of order d log p (where d is maximum indegree and p is number of nodes) in polynomial time. HOST addresses a key limitation in the field where existing methods either require exponential computation time or have weaker sample complexity guarantees.
Why it matters
The algorithm could significantly improve the practical feasibility of learning causal relationships from high-dimensional data in fields like genomics, neuroscience, and social sciences, where understanding directional dependencies between many variables is crucial but computationally challenging.
Understand the Science
⚠️ Preprint – Noch nicht peer-reviewed
Dieser Artikel wurde noch nicht von unabhängigen Experten begutachtet. Die Ergebnisse sind vorläufig und sollten mit Vorsicht interpretiert werden.
Abstract: High-dimensional Gaussian DAG learning faces a statistical-computational gap: methods with sharp sample complexity rely on computationally expensive subset search and a supplied indegree bound, whereas polynomial-time alternatives have less favorable sample complexity. We introduce HOST, an efficient DAG learning algorithm that replaces subset search with nodewise hold-out scoring and convex regression, without requiring a supplied indegree bound. Our key insight is that recovering a correct ordering does not require uniformly small estimation errors in ordering scores but only one-sided control of those errors. In the ordering step, HOST exploits the fact that score estimation using hold-out samples inflates ordering scores in expectation, which is the favorable direction for candidates that should not yet be selected. Given the ordering, HOST recovers parents by recursively removing indirect effects from total effects between two nodes. Under suitable conditions, HOST exactly recovers a $p$-node DAG of maximum indegree $d$ with sample complexity of order $dlog p$ in polynomial time. Experiments show that HOST achieves competitive graph recovery while exhibiting favorable runtime scaling.
Source: Hold-Out Scoring for Efficient Gaussian DAG Learning