acceptodds
Under review as a conference paper at ICLR 2027

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 -node DAG of maximum indegree with sample complexity of order in polynomial time. Experiments show that HOST achieves competitive graph recovery while exhibiting favorable runtime scaling.

Primary area:
causal reasoning
Keywords:
causal discovery, Gaussian DAG models, statistical–computational tradeoffs, hold-out scoring

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_tKUNOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces a new method for recovering high-dimensional Gaussian DAGs. The new method avoids expensive subset search and thus achieves polynomial-time complexity. It uses hold-out samples to control score underestimation, so the performance of the new method can still be guaranteed without requiring uniformly small estimation errors. The method then uses structural thresholding for parent recovery and achieves near-optimal sample complexity. Theoretical recovery guarantees are established under appropriate assumptions, and experiments are conducted to validate the results. For equal-error-variance models that satisfy Assumption 1, the method achieves good performance.

Critical strengths

The paper proposes a new method to recover high-dimensional Gaussian DAGs. The new method has polynomial-time complexity and can achieve good performance.

The new method uses Hold-Out Ordering to avoid expensive subset search and the requirement for uniformly small score estimation errors.

The method uses Lasso-based regression and hold-out scoring to control score underestimation without dependence on the regression dimension.

The paper provides theoretical guarantees for recovery performance under certain assumptions.

The new method has good numerical performance compared with existing methods.

Critical weaknesses

The theoretical guarantee is based on exact Lasso minimizers, but the time complexity is calculated based on cyclic coordinate descent for Lasso. It is unclear how users should set the iteration counts or tolerances of Lasso to make sure the solutions are good enough. And if the Lasso solutions are not accurate enough, how would this affect the performance of the method?

The algorithm avoids some requirements of existing methods, but it still requires giving λord\lambda_{\mathrm{ord}} and τj\tau_j. It is unclear how to choose these parameters. In the experiments, they use cpar=3c_{\mathrm{par}}=3 for Figure 2 and cpar=2c_{\mathrm{par}}=2 for Figure 3 without explaining why.

Lemma 3.2 is used to show the guarantee of hold-out scoring, but this lemma assumes that XX, θ\theta, and θ~\widetilde{\theta} are F\mathcal{F}-measurable and that ξ∣F∼N(0,vIn)\xi\mid\mathcal{F}\sim N(0,vI_n). Since the selected set S^r\widehat{S}_r is updated based on previous hold-out scores, θ~\widetilde{\theta} may depend on ξ\xi through S^r\widehat{S}_r. If θ~\widetilde{\theta} and ξ\xi are dependent, the conditional Gaussian assumption may not hold. This is confusing.

In the experiments, they mainly focus on equal-error-variance models, and some methods in Table 1 are not included in the comparisons. For most of the points, the standard errors are barely visible. Does this mean the standard errors are 0?

It is hard to understand Figures 2 and 3 together. For example, the recovery rate in Figure 2 corresponding to n=512n = 512, p=200p = 200, and d=3d = 3 is almost 0 with barely visible standard errors. But Figure 3 shows that when n=512n = 512, p=200p = 200, and d=3d = 3, the F1 score is 0.984 and the standard error is almost 0. How do the false positives and false negatives vary across trials? Are they the same across all the experiments? It is hard to understand what really happened in each trial and whether these two metrics reflect the performance of the method.

Questions for authors

See weaknesses

6 comments

Thank you for your careful reading and constructive comments. We address each of your concerns below.

W1. Lasso solver accuracy

Thank you for your helpful comment. The main focus of our paper is hold-out scoring and the graph recovery guarantees it enables. As in other theoretical analyses of Lasso-based methods (Wainwright, 2009; Daskalakis et al., 2025), our ordering guarantee is stated for exact Lasso minimizers. In practice, we solve the Lasso problems to a numerical tolerance by cyclic coordinate descent (Friedman et al., 2010). For these fits, the complexity analysis in Proposition 4.4 uses the per-sweep cost detailed in Appendix B.5.

To check whether the tolerance is sufficient for a given dataset, we recommend tightening it with the data, folds, and regularization parameters fixed and checking whether the returned graph changes. Users can also monitor the primal–dual gap, as the scikit-learn Lasso solver does, to see how close the objective value is to its minimum. If the solver reaches the sweep cap before its stopping criterion is met, the cap should be increased.

We carried out this check on 30 datasets for each of (p,n,d)=(50,200,3)(p,n,d)=(50,200,3), (200,200,3)(200,200,3), and (200,500,3)(200,500,3), generated as in Figure 3 of the original manuscript and fitted with the fixed tuning parameters used there. The table below reports the maximum number of sweeps per Lasso fit, the mean primal–dual gap over all candidate nodes, folds, and datasets, and, in the last column, the number of datasets on which the returned graph agrees with the reference solution computed with tolerance 10−1110^{-11}. The gap is computed for the objective ∥y−Xβ∥22/(2m)+λ∥β∥1\|y-X\beta\|_2^2/(2m)+\lambda\|\beta\|_1, where mm is the fitting-fold size.

ToleranceMax. sweeps (50,200,3)(50,200,3)Max. sweeps (200,200,3)(200,200,3)Max. sweeps (200,500,3)(200,500,3)Mean primal–dual gapGraph agreement
10−310^{-3}2327231.652×10−41.652\times10^{-4}79/90
10−510^{-5}4058461.706×10−61.706\times10^{-6}90/90
10−710^{-7}6291691.707×10−81.707\times10^{-8}90/90
10−910^{-9}84126951.706×10−101.706\times10^{-10}90/90
10−1110^{-11}1081621191.709×10−121.709\times10^{-12}Reference

At all tested tolerances of 10−510^{-5} or smaller, the returned graph matched the reference on all 90 datasets. At 10−310^{-3}, some of the returned graphs differed from the reference, and tightening the tolerance removed these differences. Our default coefficient-change tolerance of 10−710^{-7} with a cap of 1,000 sweeps was sufficient in all of these experiments, requiring at most 91 sweeps per fit.

W2. Parameter selection

Thank you for asking how to choose the tuning parameters. We agree that a practical tuning rule is important. For this purpose, we recommend HOST-CV/EBIC, described in Appendices C.1 and C.2 of the original manuscript. It selects a common ordering penalty by pooled two-fold cross-validation and a parent threshold for each node by the extended Bayesian information criterion (EBIC), using only the observed data.

In the original manuscript, the fixed multipliers for Figures 2 and 3 were chosen heuristically for each experiment. In response to your comment, both figures in the revised manuscript now use HOST-CV/EBIC, which gives the main experiments a common practical tuning rule. The plots in Figure 2 have been replaced with the results of HOST-CV/EBIC. The fixed-tuning HOST recovery results from Figure 3(a)–(b) are retained in Figure 4 in Appendix D.3, which reports the exact recovery rate, the directed F1 score (F1), and the structural Hamming distance (SHD) for the same experiments. We have also revised the numerical comparisons and the discussion of Figures 2 and 3 accordingly.

The revised Figure 2 shows the same recovery trends: the exact recovery rate improves as nn increases, and larger pp and dd generally require more observations. The table below reports the exact recovery rate, F1, the numbers of true positives (TP), false positives (FP), and false negatives (FN), and SHD at d=3d=3 for p=50p=50 and 200200, as mean (standard error, SE) over 200 repetitions. The results for all settings are given in Table 4 in Appendix F.1 of the revised manuscript.

ppnnExact recovery rateF1TPFPFNSHD
501280.000 (0.000)0.808 (0.004)52.94 (0.52)6.64 (0.22)18.28 (0.36)24.92 (0.53)
502560.060 (0.017)0.944 (0.003)68.13 (0.56)4.16 (0.22)3.90 (0.19)8.06 (0.39)
505120.555 (0.035)0.985 (0.002)70.50 (0.51)1.44 (0.16)0.74 (0.08)2.18 (0.23)
5010240.910 (0.020)0.998 (<0.001<0.001)72.21 (0.57)0.27 (0.08)0.07 (0.02)0.34 (0.10)
5020480.975 (0.011)1.000 (<0.001<0.001)71.08 (0.49)0.03 (0.01)0.00 (0.00)0.03 (0.01)
2001280.000 (0.000)0.753 (0.002)193.54 (1.21)22.40 (0.41)104.08 (0.86)126.48 (1.11)
2002560.000 (0.000)0.940 (0.001)274.82 (1.12)16.34 (0.46)19.06 (0.42)35.40 (0.85)
2005120.120 (0.023)0.985 (<0.001<0.001)292.43 (1.05)5.87 (0.35)3.32 (0.20)9.19 (0.53)
20010240.770 (0.030)0.998 (<0.001<0.001)294.70 (1.10)0.94 (0.15)0.33 (0.05)1.27 (0.20)
20020480.965 (0.013)1.000 (<0.001<0.001)298.58 (1.15)0.04 (0.01)0.00 (0.00)0.04 (0.01)

W3. Adaptive selection and dependence

Thank you for drawing attention to the dependence induced by adaptive selection. As you noted, the conditional Gaussian argument needs to account for this dependence. Handling it is one of the nontrivial theoretical contributions of our paper, and Lemmas B.8 and B.9 in Appendix B.2 establish the conditional bound used in the proof of Theorem 4.1.

Lemma B.9 introduces an auxiliary procedure that selects only from nodes outside a remaining source and its descendants, and its selections agree with those of HOST until HOST first selects a node outside this set. For the hold-out scores computed with these selected nodes as predictors, Lemma B.8 verifies the conditions of Lemma 3.2, including the conditional Gaussian assumption. This yields a bound on score underestimation for remaining nonsources, which Lemma B.9 then uses to control the probability of an ordering error. To make this argument visible in the main text, we have expanded the explanation after Theorem 4.1 along these lines.

W4. Baseline coverage and unequal variances

Thank you for asking about the baseline coverage and the focus on equal error variances. We first explain why some methods listed in Table 1 are not included in the comparisons. Daskalakis Alg. 1 (Daskalakis et al., 2025) was evaluated only at p=50p=50 in the Figure 3 recovery comparison because of its high memory requirements at larger dimensions, as noted in Appendix D.3. For Daskalakis Alg. 3, our implementation stalled before completing the DAG on all 20 datasets at p=200p=200, n=100n=100, and d=3d=3, and so did an additional diagnostic that uses the true parent sets and a residual-variance threshold computed from the generating parameters. For LISTEN (Ghoshal and Honorio, 2018), we tested the code released by its authors on the same 20 datasets with λ=clog⁡p/n\lambda=c\sqrt{\log p/n} for c∈{0.005,0.01,0.015,0.05,0.1,0.5,1}c\in\{0.005,0.01,0.015,0.05,0.1,0.5,1\}. It failed to produce a valid DAG in all runs, because of CLIME infeasibility or zero precision diagonals after thresholding.

As for unequal error variances, Theorem 4.3 provides a recovery guarantee under Assumption 1, which permits them. We repeated the experiment of Figure 2 with the same settings, except that the error variance of each node was drawn independently from Uniform⁡[0.7,0.8]\operatorname{Uniform}[0.7,0.8]. The results show the same recovery trends as Figure 2: the exact recovery rate improves as nn increases, and larger pp and dd generally require more observations. Figure 9 in the new Appendix D.8 shows all settings in the same panel layout as Figure 2, and the table below gives the numbers of exactly recovered graphs out of 200 repetitions for p=50p=50.

ddn=128n=128n=256n=256n=512n=512n=1024n=1024n=2048n=2048
20/20019/20089/200163/200186/200
30/2006/20065/200153/200191/200
40/2003/20053/200143/200180/200
50/2002/20047/200139/200189/200
Reviewer_bPmjOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the problem of exact Gaussian DAG recovery. Given nn i.i.d. observations x(1),…,x(n)∈Rp\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(n)}\in\mathbb{R}^p generated from a Gaussian linear structural equation model,

\qquad \varepsilon_j\sim\mathcal N(0,\sigma_j^2),$$ where the noise variables are mutually independent, the goal is to recover the underlying DAG. The authors propose an algorithm called HOST. The approach works as follows. First, the observations are partitioned into two equal-sized subsets. The node with the smallest empirical variance is selected as the first node, and $S$ is initialized as the set of selected nodes. The algorithm then iteratively performs the following steps: 1. For each remaining node, fit two Lasso regressions using the variables in $S$ as predictors, one on each subset of observations. 2. Evaluate the regressions using a two-fold cross-validation-like procedure and select the node with the smallest held-out prediction error. 3. Estimate the total effects from previously selected nodes to the newly selected node, subtract indirect effects to obtain estimates of direct effects, and apply thresholding to determine the incoming edges. 4. Fit an OLS regression using the identified parents, store the residuals, and add the newly selected node to $S$. The process continues until all nodes have been selected and the DAG has been constructed. The theoretical results show that, under suitable identifiability and regularity conditions, HOST can recover the exact DAG with probability at least $1-1/p$ using $n\gtrsim d\log p$ samples, where $d$ is the maximum indegree, while achieving computational complexity $O(np^3+p^4)$. These rates suppress model-dependent factors. This provides near-optimal sample complexity with polynomial-time computation, without requiring a supplied indegree bound or combinatorial subset search.
Critical strengths
  • The proposed method improves upon previous results by achieving near-optimal sample complexity in polynomial time without requiring a supplied indegree bound.
Critical weaknesses
  • The theoretical guarantees rely on restrictive identifiability assumptions, which may limit the method's applicability to real-world data.
Questions for authors

see weaknesses

3 comments

Thank you for your review and feedback. We respond to your comment below.

W1. Identifiability and applicability

Thank you for pointing this out. For Gaussian DAG models, exact identification from observational data is impossible in general without additional identifiability assumptions such as Assumption 1, because distinct Markov-equivalent DAGs can generate the same Gaussian distribution (Peters and Bühlmann, 2014).

Identifiability under equal error variances was established by Peters and Bühlmann (2014), and Loh and Bühlmann (2014) studied identification when the error variances are known up to scale. Broader conditions involving error variances and edge effects were later developed by Ghoshal and Honorio (2018), Park and Kim (2020), and Park (2020). Assumption 1 likewise permits unequal error variances, provided that the required separation of ordering scores holds. Such assumptions can be meaningful in applications where domain knowledge supports comparable error variances, for example, when related variables are measured in the same physical units with similar instruments.

The real-data results in Table 3 in Appendix E, reproduced below, show that HOST-CV/EBIC (labeled HOST in that table) performs competitively against methods developed under similar modeling assumptions. It achieves the highest directed F1 score (F1) and the lowest structural Hamming distance (SHD) on both the Sachs and Light Tunnel datasets, including ties. These results support the applicability of HOST-CV/EBIC to real-world data.

MethodSachs F1Sachs SHDLight Tunnel F1Light Tunnel SHD
HOST-CV/EBIC0.385160.51841
HLSM0.276210.47757
TD-BSS0.303230.34480
TD-BIC0.385160.50641
TD-Lasso0.200160.51743
Daskalakis Alg. 10.357180.41166
Daskalakis Alg. 20.370170.47247

References

  • Ghoshal, A., and Honorio, J. (2018). Learning Linear Structural Equation Models in Polynomial Time and Sample Complexity. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research 84, 1466–1475.

  • Loh, P.-L., and Bühlmann, P. (2014). High-Dimensional Learning of Linear Causal Networks via Inverse Covariance Estimation. Journal of Machine Learning Research 15(88), 3065–3105.

  • Park, G. (2020). Identifiability of Additive Noise Models Using Conditional Variances. Journal of Machine Learning Research 21(75), 1–34.

  • Park, G., and Kim, Y. (2020). Identifiability of Gaussian Linear Structural Equation Models with Homogeneous and Heterogeneous Error Variances. Journal of the Korean Statistical Society 49(1), 276–292.

  • Peters, J., and Bühlmann, P. (2014). Identifiability of Gaussian Structural Equation Models with Equal Error Variances. Biometrika 101(1), 219–228.

Thank you for the response and the clarification. I will keep my original positive score.

Thank you for your careful review and for taking the time to consider our response. We are glad that the clarification was helpful.

Reviewer_JLpeOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper addresses a statistical computation gap in high-dimensional Gaussian DAG learning. It finds the order of the nodes and then the connections by forming the parents recursively. The performance was supported by some simulations.

Critical strengths
  • The studied problem of recovering a high dimensional Gaussian DAG is important.
Critical weaknesses
  • I was not able to understand the paper due to the way it was presented. The paper seems to be targeting specific experts who know both linear models and advanced statistics. The paper is very heavy on notations and without illustrations. It may therefore not be a good fit for ICLR, and better match a statistics venue. Without elaborating the concepts and notations, a general reader won't be able to follow. Minimal effort has been put to walk the reader through the preliminaries and results. Even some concepts and terms were not defined in the first place; For example, in the Introduction, what is "moralized"? What is the "score [of a node]"? What is "d-dependent"?
  • No clear conclusion was made from the experiments.
Questions for authors

No question. I believe the main weakness of the paper is the presentation.

4 comments

Thank you for reading our paper carefully and sharing your feedback. We respond to each of your comments below.

W1. Presentation and terminology

Thank you for your helpful comments. The key idea of HOST lies in how candidate nodes are scored in the ordering step. The ordering score of a candidate node is its prediction error when it is regressed on the nodes already selected. To recover a compatible ordering, it is enough to control two kinds of errors: overestimation of the scores of nodes whose parents have all been selected, and underestimation of the scores of nodes with unselected parents.

Figure 1 in Section 3 illustrates why hold-out scoring helps with the second kind of error. In panel (a), indirect effects make the regression of a node with only two parents involve all 64 selected variables. Panels (b) and (c) show that when the same observations are used for both fitting and scoring, this node can be placed too early, while hold-out scoring orders the two nodes correctly more often. Section 3.2 explains the mechanism: fitting error adds a nonnegative term to the conditional mean of the hold-out score, which is the intuition behind the bound on score underestimation in Lemma 3.2.

This one-sided control allows HOST to recover an ordering without subset search or a supplied indegree bound and, under the stated conditions, to recover the DAG exactly with sample complexity of order dlog⁡pd\log p in polynomial time. This focus on learning linear DAGs from observational data is shared by several recent ICLR studies (Saboksayr et al., 2024; Zhang et al., 2025; Wienöbst et al., 2026; Ormaniec et al., 2025; Duong et al., 2025).

Within the page limit, we kept the background discussion brief. We have now clarified the three terms you pointed out. In the Introduction, the paragraph on forward methods now defines the maximum indegree dd as the largest number of parents of any node, and the first contribution bullet states explicitly that the sample complexity depends on dd, which is what “dd-dependent” referred to. The paragraph on backward methods now explains that moralization connects parents that share a child and removes edge directions, and Section 2.1 gives the formal definition of the moralized graph and the maximum moralized degree dmd_{\mathrm m}. For the score of a node, the paragraph explaining why forward methods need subset search now refers to the ordering scores of each node and notes that, under Gaussian DAG models, the population ordering score of a node equals its conditional variance given the nodes already selected. The original manuscript gives the formal definition in Section 2.2. We will add a short appendix section introducing basic graphical model concepts.

W2. Experimental conclusions

Thank you for your helpful comment. We designed the experiments in Section 5 to illustrate the recovery behavior studied in Section 4 and assess the tradeoff between recovery accuracy and runtime that motivates HOST. The original discussion of Figure 2 explains that the exact recovery rate improves as nn increases and is generally higher for smaller dd at a fixed nn, and that larger pp typically requires more observations to reach a comparable rate. The original discussion of Figure 3 compares recovery accuracy and runtime and highlights the favorable statistical–computational tradeoff of HOST.

To make these conclusions clearer, we have revised Section 5. Figure 2 now uses HOST-CV/EBIC and preserves the qualitative trends, which we discuss in connection with Theorem 4.3. The paragraph after Figure 3 now builds on the numerical comparison with TD-BSS and identifies the settings in which HOST-CV/EBIC achieves a higher directed F1 score than other baselines, with larger differences at p=200p=200. It also compares how the runtimes of HOST-CV/EBIC, TD-BSS, TD-BIC, and TD-Lasso grow with dd and pp in panels (c) and (d).

References

  • Duong, B., Gupta, S., and Nguyen, T. (2025). Causal Discovery via Bayesian Optimization. International Conference on Learning Representations, 54318–54351.

  • Ormaniec, W., Sussex, S., Lorch, L., Schölkopf, B., and Krause, A. (2025). Standardizing Structural Causal Models. International Conference on Learning Representations, 68912–68954.

  • Saboksayr, S. S., Mateos, G., and Tepper, M. (2024). CoLiDE: Concomitant Linear DAG Estimation. International Conference on Learning Representations, 41687–41715.

  • Wienöbst, M., Henckel, L., and Weichwald, S. (2026). Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning. International Conference on Learning Representations, 54630–54652.

  • Zhang, Z., Ng, I., Gong, D., Liu, Y., Gong, M., Huang, B., Zhang, K., van den Hengel, A., and Shi, J. Q. (2025). Analytic DAG Constraints for Differentiable DAG Learning. International Conference on Learning Representations, 15862–15887.

Thanks. This helps but still the paper is difficult to follow, especially at the Results Section. I however, increase my score from 1 to 2.

One further point could strengthen the discussion of the scope of the results. A Gaussian SCM with hidden confounders can have the same observational distribution as an unconfounded SCM. Consequently, although HOST excludes hidden confounders, its recovery guarantees may also apply to an unconfounded DAG representation of data generated by a confounded system, provided that representation satisfies HOST’s assumptions. This connection highlights the broader distributional relevance of the results, while distinguishing recovery of an observationally equivalent DAG from recovery of the underlying causal structure. A brief discussion of this distinction would be useful. For related work on structure learning and identification with hidden variables, see, for example, Frot et al. (2019), Salehkaleybar et al. (2020), and Sanjaroonpouri and Ramazi (2025).

Thank you for considering our responses and revising your assessment.

If the observed distribution of a confounded Gaussian SCM admits an unconfounded Gaussian DAG representation satisfying HOST's assumptions, our recovery guarantees apply to that representation under the theorem's stated conditions. This follows because the observed samples have the same distribution in either case. The guarantee concerns recovery of that DAG representation of the observational distribution. Its edges need not reflect the causal relationships in the original confounded system.

We will add a brief discussion of this distinction and include the suggested references. We will also revise the explanations in the Results section to make the main findings and their implications easier to follow.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.