arXiv：cs.LG· Donguk Shin, Byeongguk Kang, Inseol Lee, Gunwoong Park·· 3 小时前AI 评分38
HOST：面向高效高斯 DAG 学习的留出评分算法
Hold-Out Scoring for Efficient Gaussian DAG Learning
AI 导读
研究者提出 HOST，一种用逐节点留出评分与凸回归替代子集搜索的高斯 DAG 学习算法，无需预先给定入度上界。在合适条件下，HOST 可在多项式时间内精确恢复最大入度为 d 的 p 节点 DAG，样本复杂度为 d log p 量级。实验显示其图恢复效果具竞争力，且运行时间扩展性良好。
正文
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 $d\log p$ in polynomial time. Experiments show that HOST achieves competitive graph recovery while exhibiting favorable runtime scaling.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.02785 [stat.ML] |
| (or arXiv:2610.02785v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.02785 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Donguk Shin [view email]
[v1]
Fri, 2 Oct 2026 04:20:12 UTC (277 KB)
来源：arXiv：cs.LG · arxiv.org