- 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 and . It is unclear how to choose these parameters. In the experiments, they use for Figure 2 and for Figure 3 without explaining why.
Lemma 3.2 is used to show the guarantee of hold-out scoring, but this lemma assumes that , , and are -measurable and that . Since the selected set is updated based on previous hold-out scores, may depend on through . If and 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 , , and is almost 0 with barely visible standard errors. But Figure 3 shows that when , , and , 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
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 increases, and larger and 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 for and , 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.
| Exact recovery rate | F1 | TP | FP | FN | SHD | ||
|---|---|---|---|---|---|---|---|
| 50 | 128 | 0.000 (0.000) | 0.808 (0.004) | 52.94 (0.52) | 6.64 (0.22) | 18.28 (0.36) | 24.92 (0.53) |
| 50 | 256 | 0.060 (0.017) | 0.944 (0.003) | 68.13 (0.56) | 4.16 (0.22) | 3.90 (0.19) | 8.06 (0.39) |
| 50 | 512 | 0.555 (0.035) | 0.985 (0.002) | 70.50 (0.51) | 1.44 (0.16) | 0.74 (0.08) | 2.18 (0.23) |
| 50 | 1024 | 0.910 (0.020) | 0.998 () | 72.21 (0.57) | 0.27 (0.08) | 0.07 (0.02) | 0.34 (0.10) |
| 50 | 2048 | 0.975 (0.011) | 1.000 () | 71.08 (0.49) | 0.03 (0.01) | 0.00 (0.00) | 0.03 (0.01) |
| 200 | 128 | 0.000 (0.000) | 0.753 (0.002) | 193.54 (1.21) | 22.40 (0.41) | 104.08 (0.86) | 126.48 (1.11) |
| 200 | 256 | 0.000 (0.000) | 0.940 (0.001) | 274.82 (1.12) | 16.34 (0.46) | 19.06 (0.42) | 35.40 (0.85) |
| 200 | 512 | 0.120 (0.023) | 0.985 () | 292.43 (1.05) | 5.87 (0.35) | 3.32 (0.20) | 9.19 (0.53) |
| 200 | 1024 | 0.770 (0.030) | 0.998 () | 294.70 (1.10) | 0.94 (0.15) | 0.33 (0.05) | 1.27 (0.20) |
| 200 | 2048 | 0.965 (0.013) | 1.000 () | 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 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 , , and , 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 for . 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 . The results show the same recovery trends as Figure 2: the exact recovery rate improves as increases, and larger and 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 .
| 2 | 0/200 | 19/200 | 89/200 | 163/200 | 186/200 |
| 3 | 0/200 | 6/200 | 65/200 | 153/200 | 191/200 |
| 4 | 0/200 | 3/200 | 53/200 | 143/200 | 180/200 |
| 5 | 0/200 | 2/200 | 47/200 | 139/200 | 189/200 |
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), (200,200,3), and (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−11. The gap is computed for the objective ∥y−Xβ∥22/(2m)+λ∥β∥1, where m is the fitting-fold size.
At all tested tolerances of 10−5 or smaller, the returned graph matched the reference on all 90 datasets. At 10−3, some of the returned graphs differed from the reference, and tightening the tolerance removed these differences. Our default coefficient-change tolerance of 10−7 with a cap of 1,000 sweeps was sufficient in all of these experiments, requiring at most 91 sweeps per fit.