# Hold-Out Scoring for Efficient Gaussian DAG Learning

arXiv: https://arxiv.org/abs/2610.02785 · HTML: https://mlsanity.com/paper/2610.02785/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 2 Oct 2026.

## Builds on (most cited first, 13 of 13)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Causal Discovery with Continuous Additive Noise Models](https://mlsanity.com/paper/1309.6779/) (2013)
- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [On Causal Discovery with Equal Variance Assumption](https://mlsanity.com/paper/1807.03419/) (2018)
- [Learning linear structural equation models in polynomial time and sample complexity](https://mlsanity.com/paper/1707.04673/) (2017)
- [Scalable Causal Discovery with Score Matching](https://mlsanity.com/paper/2304.03382/) (2023)
- [Causal Discovery with Score Matching on Additive Models with Arbitrary Noise](https://mlsanity.com/paper/2304.03265/) (2023)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [Ordering-Based Causal Discovery for Linear and Nonlinear Relations](https://mlsanity.com/paper/2410.05890/) (2024)
- [Adaptive estimation of High-Dimensional Signal-to-Noise Ratios](https://mlsanity.com/paper/1602.08006/) (2016)
- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)

## Abstract (arXiv)

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.