Metraipolis › archive › dc_86bd1c046dbd

Hold-Out Scoring for Efficient Gaussian DAG Learning — arXiv:2610.02785

Source
arXiv
Original
https://arxiv.org/abs/2610.02785
License (as archived)
CC0-1.0
Archived
2026-10-05T23:10:42.113Z
SHA-256 of the archived text
5fc6b86dbde1d6fced4f379a4c7980728b4e3421a37e7865d5507b8f3d82f4f7
Stable URL of this page
https://metraipolis.com/documento/dc_86bd1c046dbd

How to cite

Hold-Out Scoring for Efficient Gaussian DAG Learning — arXiv:2610.02785 — arXiv, https://arxiv.org/abs/2610.02785 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_86bd1c046dbd (Metraipolis archive dc_86bd1c046dbd, sha256 5fc6b86dbde1d6fced4f379a4c7980728b4e3421a37e7865d5507b8f3d82f4f7)
BibTeX
@misc{dc86bd1c046dbd,
  title = {Hold-Out Scoring for Efficient Gaussian DAG Learning — arXiv:2610.02785},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.02785},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_86bd1c046dbd; sha256 5fc6b86dbde1d6fced4f379a4c7980728b4e3421a37e7865d5507b8f3d82f4f7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.02785. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.02785 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-05T23:01:38.752Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).