Hold-Out Scoring for Efficient Gaussian DAG Learning
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.
Related
- Efficient estimation methods for non-Gaussian regression models in continuous time
- Efficient Mass Matrix Estimation with Gaussian Cooling
- Efficient Deep Gaussian Process Surrogates via Mini-Batch Latent MAP Estimation
- Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
- Learning Probabilistic Filters with Strictly Proper Scoring Rules
BibTeX
@misc{shin2026holdout,
title = {{Hold-Out Scoring for Efficient Gaussian DAG Learning}},
author = {Donguk Shin and Byeongguk Kang and Inseol Lee and Gunwoong Park},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02785},
eprint = {2610.02785},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02785},
}
RIS
TY - UNPB
TI - Hold-Out Scoring for Efficient Gaussian DAG Learning
AU - Donguk Shin
AU - Byeongguk Kang
AU - Inseol Lee
AU - Gunwoong Park
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02785
UR - https://arxiv.org/abs/2610.02785
AB - 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.
ER -