Hold-Out Scoring for Efficient Gaussian DAG Learning

Donguk Shin; Byeongguk Kang; Inseol Lee; Gunwoong Park

stat.MLOct 2, 2026

Hold-Out Scoring for Efficient Gaussian DAG Learning

Authors: Donguk Shin, Byeongguk Kang, Inseol Lee, Gunwoong Park

Organizations: Department of Statistics, Seoul National University. · Interdisciplinary Program in Artificial Intelligence, Seoul National University. · Institute for Data Innovation in Science, Seoul National University.

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.

Figures & tables

Reference	Sample complexity	Computational complexity	Irrep.	Input $q$
Ghoshal and Honorio (2018)	$n\gtrsim d_{\mathrm{m}}^{4}\log p$	$\widetilde{O}(p^{3}+pd_{\mathrm{m}}^{4})$	$\times$	$\times$
Chen et al. (2019)	$n\gtrsim d^{2}\log p$	$p^{O(q)}$	$\times$	$\checkmark$
Park et al. (2021)	$n\gtrsim d_{\mathrm{m}}^{2}\log p$	$O\{n(p^{3}+p^{2}d_{\mathrm{m}}^{2})\}$	$\checkmark$	$\times$
Gao et al. (2022)	$n\gtrsim d\log(p/d)$	$p^{O(q)}$	$\times$	$\checkmark$
Daskalakis et al. (2025) , Alg. 1	$n\gtrsim d\log(p/d)$	$p^{O(q)}$	$\times$	$\checkmark$
Daskalakis et al. (2025) , Alg. 2/3	$n\gtrsim d^{4}\log p$	$\operatorname{poly}(n,p)$	$\times$	$\checkmark$

Table 1: Comparison of Gaussian DAG learning algorithms. The results for Chen et al. (2019) concern ordering recovery only. In this table,

\gtrsim

suppresses constants, including model-dependent factors.

\widetilde{O}

suppresses logarithms. Irrep. denotes irrepresentability. Input

q

indicates whether a supplied indegree bound

q\geq d

is required.

Panel of Figure 1 — Figure 1: Panel (a) shows a 127-node layered DAG with the ancestral set $S$ shaded, the designated remaining source $X_{\rm src}$ in blue, and the designated remaining nonsource $X_{\rm ns}$ in red. Panel (b) shows mean Lasso ordering scores for in-sample (In) and hold-out (HO) scoring using $X_{S}$ on a log scale. Error bars indicate one standard deviation across repetitions, computed on the original score scale. Horizontal lines mark population scores of 0.75 for $X_{\rm src}$ and 1.93 for $X_{\rm ns}$ . Panel (c) shows the fraction of repetitions with $X_{\rm src}$ scoring below $X_{\rm ns}$ , with 95% Wilson intervals. Appendix D.1 gives the settings.

Panel of Figure 2 — Figure 2: Graph recovery rate of HOST with $\pm 1$ standard error over 200 repetitions. Panels (a)–(d) overlay curves for different $d$ at fixed $p$ , and (e)–(h) for different $p$ at fixed $d$ .

Panel of Figure 3 — Figure 3: Recovery accuracy and runtime scaling. Recovery uses $d$ = 3 and shows means $\pm 1$ standard error over 50 paired repetitions. Runtime uses $n$ = 100 and reports mean full-fit time in seconds (log scale), including tuning, over 20 paired repetitions.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: Graph recovery for $d$ = 3. Panels (a)–(c) use $p$ = 50, and (d)–(f) use $p$ = 200. Columns show exact recovery, F1, and SHD. Points and error bars show means $\pm 1$ standard error over 50 paired repetitions.

Panel of Figure 5 — Figure 5: Mean full-fit time (seconds, log scale) at $n$ = 100, including tuning, over 20 paired repetitions. Panels (a)–(e) vary $d$ at fixed $p$ , and (f)–(j) vary $p$ at fixed $d$ .

Figure 6: Graph recovery for ER, hub, and bipartite DAGs in the first, second, and third rows, respectively, with

p

= 30. Columns show exact recovery, F1, and SHD. Points and error bars show means

\pm 1

standard error across 50 paired repetitions.

Figure 7: Ordering recovery and computational cost at

p

= 50. Rows show Kendall distance and runtime, and columns show

d

= 2, 3, 4. Points and error bars show means

\pm 1

standard error across 50 paired repetitions.

Figure 8: Parent recovery with the true ordering and oracle tuning at

p

= 50. Rows correspond to

d

= 2, 3, 4, and columns show SHD, precision, and recall. Each method selects

c\in\{0.5,1,2,3,4,5\}

by minimizing SHD separately in each repetition. Points and error bars show means

\pm 1

standard error across 50 paired repetitions.

Method	Parameters and selection procedure
HOST	Select $c_{\mathrm{ord}}\in\mathcal{C}$ by pooled two-fold CV, then $c_{j}\in\mathcal{C}$ for each node by EBIC.
HLSM	For each $c\in\mathcal{C}$ , fit with Lasso penalty $\lambda=c\sqrt{\log p/n}$ .
TD-BSS	For every $(q,c)\in Q\times\mathcal{C}$ , fit with supplied indegree bound $q$ and parent-selection threshold $\eta=c\log p/n$ .
TD-BIC	For each $q\in Q$ , select each parent set by minimizing nodewise BIC over subsets of at most $q$ earlier nodes.
TD-Lasso	For each $q\in Q$ , recover the ordering and select nodewise Lasso penalties by ten-fold cross-validation using the one-standard-error rule.
Daskalakis Alg. 1	For every $(q,c_{b})\in Q\times\mathcal{C}$ , fit with supplied indegree bound $q$ and $b_{\min}=c_{b}\sqrt{\log p/n}$ .

Appendix

Table 2: Real-data tuning parameters and candidate construction.

Method	F1	SHD	F1	SHD
	Sachs		Light Tunnel
HOST	0.385	16	0.518	41
HLSM	0.276	21	0.477	57
TD-BSS	0.303	23	0.344	80
TD-BIC	0.385	16	0.506	41
TD-Lasso	0.200	16	0.517	43

Appendix

Table 3: Directed F1 and SHD on the full Sachs and Light Tunnel datasets. Bold entries indicate the highest F1 or lowest SHD in each column.

Graph Structure Learning

Graph structure learning infers or adapts network connections from data for statistical discovery and downstream prediction.

See all 139 papers

Oct 6, 2026

Directional Evidence Guided Search-Space Reduction for Exact DAG Learning

Learning a directed acyclic graph (DAG) from observational data is a challenging combinatorial problem due to the exponential growth in the number of candidate parent-set configurations. Existing exact score-based methods often require computationally intensive combinatorial search, whereas constraint-based methods can become unreliable or computationally demanding as graph size and conditioning-set complexity increase. We develop a non-parametric hybrid framework, referred to as DECO (Directional Evidence-guided Configuration Optimization), that extracts dependency and directional evidence from observation data to construct admissible parent sets prior to exact optimization. It reduces the optimization search space by eliminating empirically unsupported parent configurations while preserving flexibility for all plausible edge orientations. Theoretical analysis establishes an exponential reduction in the admissible parent-set configuration space and quantifies how bounded edge-level omission affects the probability of retaining the true parent structure. Experiments on benchmark Bayesian networks and synthetic discrete and continuous DAGs demonstrate substantial search-space reduction while achieving competitive structure-recovery performance, with favorable structural Hamming distance across many evaluated settings. These results show that directional evidence can provide an effective preprocessing mechanism for reducing the computational burden of exact DAG learning without requiring a fixed parametric structural~model.

Upala Junaida Islam, Abdelmonem Elrefaey, Rong Pan

School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA.

Score-Based Causal Discovery Bayesian Network Structure Learning Causal Discovery Causal Structure Learning Bayesian Networks

Ask PDF

Jun 19, 2026

A Framework for Directed Acyclic Hypergraph Learning

Continuous optimization methods for learning Directed Acyclic Graphs (DAGs) operate on weighted adjacency matrices and are therefore limited to pairwise causal relationships. We propose a framework for learning Directed Acyclic Hypergraphs (DAHGs) from observational data, capturing joint parental influences that pairwise models cannot represent. Our approach rests on three components: (i) a generalized linear structural equation model (SEM) with multiplicative interaction terms whose non-zero weights correspond one-to-one with directed hyperedges; (ii) a weighted adjacency tensor representation whose acyclicity is characterized via nilpotency under the tensor t-product; and (iii) a differentiable acyclicity constraint derived through the Fourier decomposition of the t-product, which reduces tensor nilpotency to slice-wise matrix nilpotency and enables least-squares learning via the augmented Lagrangian method.

Zhiyuan Dong, Carlos Mundo-Levano, Wei Qian +2

Institute for Financial Services Analytics, University of Delaware, Newark, DE 19716, USA · Department of Electrical and Computer Engineering, University of Delaware, Newark, DE 19716, USA · Department of Applied Economics AND Statistics, University of Delaware, Newark, DE 19716, USA +1

Structural Causal Models Causal Structure Learning Hypergraph Learning

Ask PDF

May 19, 2026

Exploiting Non-Negativity in DAG Structure Learning

This work addresses the problem of learning directed acyclic graphs (DAGs) from nodal observations adhering to a linear structural equation model. DAG structure learning is a central task in signal processing, machine learning, and causal inference, but it remains challenging because acyclicity is a global combinatorial property and the search space grows superexponentially in the number of nodes. Continuous acyclicity characterizations have led to important algorithmic advances by replacing the discrete DAG restriction with smooth equality constraints on the candidate adjacency matrix. However, existing formulations still involve difficult non-convex optimization landscapes and may suffer from degenerate first-order optimality conditions. Here, we restrict attention to DAGs with non-negative edge weights and exploit this additional structure to obtain a simpler acyclicity characterization devoid of Hadamard products. We propose a new non-negative constrained DAG estimator and develop a tractable, locally convergent algorithm based on the method of multipliers. We further analyze the benign optimization landscape induced by the non-negativity constraints. In the large-sample regime, we show that the true DAG is the unique global minimizer of the population augmented Lagrangian. Moreover, the landscape contains no spurious interior stationary points, and the true DAG is the only acyclic Karush--Kuhn--Tucker (KKT) point. Critically, this allows us to guarantee local convergence to the true DAG given infinite samples. Comprehensive numerical experiments show that the proposed structure identification method improves over state-of-the-art continuous DAG-learning baselines.

Samuel Rey, Madeline navarro, Santiago Segarra +1

Dept. of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627, USA

Graph Structure Learning Structural Causal Models Causal Structure Learning Nonconvex Optimization Augmented Lagrangian Method Constrained Optimization

Ask PDF

Abstract

Graph Structure Learning

Explore similar work

Directional Evidence Guided Search-Space Reduction for Exact DAG Learning

A Framework for Directed Acyclic Hypergraph Learning

Exploiting Non-Negativity in DAG Structure Learning