- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper investigates the sample complexity of exact condensation recovery – identifying the strongly connected components (SCCs) and the directed acyclic condensation edges between them – in cyclic linear non-Gaussian (LiNG) structural equation models from observational data. First, the authors derive an information-theoretic minimax lower bound showing that over regular model classes with variables, maximum SCC size , and maximum external parent count , exact condensation recovery requires samples. Second, under principal invertibility of (and without correlation faithfulness), they establish a population "block-exogeneity" and "sparse-adjustment" characterization. This yields the BlockExo algorithm, which achieves high-probability exact recovery in samples.
Critical strengths
- Clean Population Characterization via Block Exogeneity and Sparse Adjustment (Section 4): The combination of Theorem 4.1 and Proposition 4.3 is the strongest contribution of the paper. Showing that (i) upstream sufficiency of a sparse adjustment set can be verified purely via second-order covariance checks while (ii) root-SCC ancestry in reduces to scalar pairwise independence tests without correlation faithfulness is both mathematically clean and conceptually insightful.
- Dimension-Reduction in Conditioning Sets: By regressing only on candidate external parent sets of size rather than the entire previously recovered ancestral set (which can grow to ), the method avoids high-dimensional regression variance inflation when the condensation graph is sparse ().
- Clear Separation of Structural Costs: Decomposing the combinatorial search complexity into SCC membership discovery and external parent selection provides a natural extension of DAG LiNGAM sample complexity bounds (Oh et al., 2025) to cyclic condensations.
Critical weaknesses
- Hidden Coupling Between Structural Parameters () and Separation Margins (): The paper claims that
BlockExo"attains a structurally matching sample bound" relative to the lower bound in Theorem 3.1. However, Theorem 3.1 is proved using weak edges scaling as and (Figure 1), whereas the upper bound in Theorem 5.2 / Corollary 5.3 multiplies the structural term by . In the lower-bound constructions of Figure 1, the separation margins and themselves shrink with and (or with edge weights), so plugging the lower-bound instances into Theorem 5.2 would incur additional polynomial factors in and through and . Indeed, Corollary 5.3 only claims minimax optimality when are held fixed. - Exponential Computational Complexity :
BlockExorelies on exhaustive subset enumeration over all candidate blocks () and parent sets () in increasing order of . While tractable for , its runtime scales as , which contrasts sharply with polynomial-time ICA-based condensation methods such as Coarsening (Madaleno et al., 2026) when SCCs or indegrees are moderate in size. - Crucial Algorithmic Details Omitted from the Main Text: The finite-sample algorithm requires threshold multipliers (and a choice of dependence functional ), which in Theorem 5.2 are existential constants depending on unknown model parameters. The main text never specifies which dependence functional or threshold tuning rule is actually used in
BlockExoin Section 6, nor how sensitive the algorithm is to these thresholds in finite samples (in contrast toCoarsening, whose sensitivity to thresholds 0.1 vs. 0.2 is explicitly shown). - Superficial Empirical Section and Unexplained Baseline Failures: Section 6 is overly brief and leaves key definitions to the appendix. I appreciate that space is tight, but I expected to see a few more details, e.g. (1) In Figure 3, the x-axis normalization factor is never defined, and the alignment across in Figure 3(a) remains fairly loose. (2) All experiments use only 20 replicates and test only in Figure 4, where
BlockExois given tight search bounds . (3) Two recent baselines –DisjointCycles(Drton et al., 2025) andStableSpIn(Misiakos & Püschel, 2026) – achieve 0% exact recovery across all four panels of Figure 4 (even on disjoint 2-cycles, whichDisjointCyclesis specifically designed for!), with no explanation in the main text for why they fail.
Questions for authors
- Dependence of and on in the Lower-Bound Ensemble: In the lower-bound constructions of Figure 1 (where edge weights scale as and to satisfy Assumption 2.2), how do the population margins and scale with and ? Doesn't Theorem 5.2 yield a sample complexity of on those instances rather than because scales with (and with )? This point weighed most heavily in my final assessment. I would consider revising my score upward if it can be adequately addressed.
- Practical Selection of and : How are the thresholds and chosen in the simulations in Section 6? Are and fixed across all experiments, or tuned on synthetic validation data? How sensitive is
BlockExoto varying (analogous to showingCoarsening (0.1)vs.Coarsening (0.2)in Figure 4)? - Why Do
DisjointCyclesandStableSpInAchieve 0% Recovery in Figure 4? Panels (a) and (c) of Figure 4 specifically test disjoint 2-cycles (), which is the exact setting of Drton et al. (2025). Why doesDisjointCyclesachieve 0/20 recovery up to ? This result seems unexpected. - Scalability Beyond : Since
BlockExosearches over pairs, what is the largest for whichBlockExoremains computationally feasible at ? Can theUPcovariance screening step be used to prune candidate parent sets via sparse regression (e.g., Lasso/OMP of on ) before running the expensive non-parametricOUTindependence tests?
4 comments
Weakness 3 & Question 2
Thank you for your careful comments on the presentation of these practical choices. We will bring the dependence functional and threshold-selection details currently provided in the appendix into Section 6, together with a brief discussion of threshold sensitivity.
- Threshold-selection details
As described in Appendix F.1, we use normalized squared distance covariance as the dependence functional in all experiments. The thresholds are with . As specified in Appendix F.1 for the experiments in Section 6 and the noise-distribution comparisons in Appendix~F.5, the multipliers are selected on separate simulated datasets for each noise law and then held fixed across structures and sample sizes within that noise law. We use throughout, with , , and for the asymmetric Gaussian mixture, symmetric Gaussian mixture, and uniform noise, respectively.
- Sensitivity analysis
Our additional sensitivity experiments show that high recovery does not require a single finely tuned multiplier pair when the sample size is adequate. Under asymmetric Gaussian-mixture noise at , , and , all nine combinations obtained by multiplying each of and by achieve 19--20/20 exact recoveries. Near the recovery transition, tuning matters more: at with the same structure and UP fixed at its reference value, the three OUT choices yield 18/20, 18/20, and 7/20. The same sensitivity experiments under symmetric Gaussian-mixture and uniform noise likewise show high recovery across a range of multiplier choices in multiple additional settings. Appendix G.2 reports the complete results.
- Data-driven selection of
We also propose and empirically evaluate a fully data-driven procedure for selecting both multipliers (Algorithm 2, Appendix G.1). On one third of the observations, we try a prespecified sequence of multiplier pairs in BlockExo until a fit assigns all variables to blocks. A blockwise residual bootstrap based on this provisional condensation selects the final multipliers. We then use these multipliers to run BlockExo anew on the remaining two thirds. We use the same selection procedure across all three noise laws, and it requires no prior knowledge of the graph structure or the noise law.
For the Figure 4 construction with and , this procedure achieves 20/20 and 19/20 exact recoveries under asymmetric and symmetric Gaussian-mixture noise at total , respectively, and 20/20 under uniform noise at (Table 4). The procedure also shows empirical robustness to initialization, retaining 18--20/20 exact recoveries across four alternative choices of the initial multipliers in each of these three settings (Table 5). An exact provisional SCC partition is not required for success in these experiments: under uniform noise, all 20 provisional fits return singleton blocks, yet final recovery succeeds in 20/20 cases (Table 4).
Weakness 4 (1)
Thank you for highlighting the need for a more self-contained presentation of Figure 3. As defined in Appendix F.2, the normalization combines the UP and OUT separation margins, scaled by their threshold multipliers, with the structural complexity term in Theorem 5.2. We will bring this definition into the main text. The normalization reflects the sufficient sample-complexity bound, rather than predicting identical recovery curves across structures. Accordingly, Figure 3 examines the extent to which this normalization aligns the empirical transitions, without requiring identical recovery curves across structures. Nevertheless, it brings the empirical recovery transitions into closer alignment than plotting against the raw sample size, providing empirical support for the sample-complexity scaling captured by Theorem 5.2.
Weakness 4 (2)
Thank you for your helpful comment. We will increase the number of independent replicates in the camera-ready version. We also tested larger SCCs than those in Figure 4. In a star construction with at and , BlockExo recovered the condensation exactly. We report the other larger-structure experiments and their computational costs in our response to Question 4. Separately, Theorem 5.2 allows any valid search bounds under our recovery conditions. With the true structure fixed at , the enlarged bounds each yield 20/20 exact recoveries at .
Weakness 4 (3) & Question 3
Our evaluation requires exact recovery of both the SCC partition and all condensation edges. Even one incorrect component or condensation edge makes a run unsuccessful, so 0% exact recovery does not imply that no structure was recovered. This criterion is more stringent than achieving a small average structural error on the recovery target.
For DisjointCycles, disjoint cycles are not the only relevant condition: its moment-based tests use second- and third-order moments [4]. The symmetric mixture and uniform distributions have vanishing third moments, removing the skewness information used by these tests. Keeping the same disjoint-cycle construction and asymmetric-mixture noise, we increased the sample size to and obtained 20/20 exact recoveries for each . Successful recovery was thus obtained with substantially more data, at a scale comparable to the -- used in [4]. In addition to accommodating overlapping cycles and noise with vanishing third moments, BlockExo achieved exact recovery with fewer samples than DisjointCycles even in the disjoint-cycle, asymmetric-mixture setting tested here.
StableSpIn uses a Laplace-based objective, and its original experiments emphasize sparse exogenous inputs [5], unlike our Gaussian-mixture and uniform noise. In separate models with dense or sparse Laplace noise, it achieved 20/20 exact recoveries in each setting at both and . On the same datasets, BlockExo, using data-driven multiplier selection from Appendix G.1 (Algorithm 2), achieved 20/20 exact recoveries in both dense-Laplace settings and 20/20 and 19/20 under sparse Laplace noise at and , respectively. The contrast with its failures under our Gaussian-mixture and uniform settings suggests sensitivity of StableSpIn's recovery performance to the noise distribution, rather than a general failure of the method. Meanwhile, BlockExo's high recovery rates in these additional settings extend its empirical performance beyond the sub-Gaussian assumptions of our finite-sample theory.
Weakness 2
We agree that exhaustive search carries a substantial computational cost as grows. Our central contribution concerns the fundamental statistical cost of condensation recovery. The lower bound and BlockExo play complementary roles: the former characterizes the intrinsic statistical difficulty of the problem, while the latter provides a constructive achievability result rather than a claim of computational efficiency. Although Coarsening offers an important computational advantage, our recovery guarantee improves the explicit dimension dependence of its published sufficient bound. As summarized in Appendix A.1, Table 1, for fixed structural bounds and with the respective signal and regularity parameters treated as constants, our bound grows logarithmically in , whereas Coarsening's bound grows linearly in .
Question 4 (Scalability Beyond )
To examine the practical cost beyond , we conducted additional experiments at with larger structural sizes. All completed runs recover the condensation exactly. Using a single CPU thread, median runtimes ranged from approximately 1.5 to 6 hours across the tested settings. For , the settings took approximately 16.5, 10, and 23 CPU hours, respectively.
These costs can be reduced through computational improvements that preserve the search and testing rules. Beyond the UP-based early rejection and reuse of computed statistics already implemented, we evaluated GPU batching of OUT tests. This reduced the runtimes to approximately 0.4--1.6 hours, with median paired speedups of about . For , GPU runtimes were approximately 3.5, 4, and 8 hours, respectively, with speedups ranging from to . Even this straightforward GPU implementation substantially reduces runtime, suggesting considerable scope for further acceleration through more extensive parallel evaluation and more effective caching and reuse of computed statistics. We will incorporate these results and measurement details into the manuscript.
References
[4] Drton, Garrote-López, Nikov, Robeva, and Wang. “Causal Discovery for Linear Non-Gaussian Models with Disjoint Cycles.” UAI, PMLR 286:1064–1083, 2025.
[5] Misiakos and Püschel. “Learning Stable Digraphs from Sparse-Input Linear Structural Causal Models.” UAI, PMLR 337:4561–4594, 2026.
Question 4 (Sparse regression screening e.g. Lasso/OMP)
Thank you for suggesting sparse regression screening as a practical way to reduce the computational cost of BlockExo. Motivated by your suggestion, we examined its theoretical requirements and evaluated Lasso- and OMP-based variants through simulations.
Block exogeneity provides a direct basis for sparse-regression screening. Specifically, if screening retains all true external parents throughout recovery with probability tending to one and the restricted search preserves the original ordering among retained candidates, our consistency results can be applied. Lasso or OMP can provide this screening property under suitable design and minimum-signal conditions [6,7], beyond the assumptions required by our exact search.
Screening reduces parent-set enumeration at the cost of an additional statistical requirement for reliable screening. Retaining variables from reduces the number of parent sets considered per candidate block from to , with additional screening cost. The sample requirement for reliable screening depends on the dimension, sparsity, and additional design and minimum-signal conditions, so the structurally matching sample bound does not automatically carry over.
In our experiments, OMP screening reduced runtime at the cost of fewer exact recoveries, whereas the broader Lasso screen took longer than exhaustive search. To reduce total runtime, screening must save enough search time to offset its own cost, but an overly restrictive screen can exclude true external parents from the restricted search. Across the same 320 Figure 4 inputs, BlockExo with exhaustive search achieved 141 exact recoveries with a total fitting time of approximately 0.98 hours, while the four-step OMP variant achieved 122 in 0.14 hours. The broader Lasso screen achieved 131 in 1.16 hours. We will incorporate this discussion and the additional comparisons into the manuscript.
References
[6] Bühlmann and Mandozzi. “High-dimensional variable screening and bias in subsequent inference, with an empirical comparison.” Computational Statistics, 29:407–430, 2014.
[7] Zhang. “Sparse Recovery With Orthogonal Matching Pursuit Under RIP.” IEEE Transactions on Information Theory, 57(9):6215–6221, 2011.
Weakness 1& Question 1
We appreciate the opportunity to clarify a central contribution of our work. For the ensembles illustrated in Figure 1, omitting one parent gives Δpar≤1/(2d) in the parent-star construction. For the reciprocal-star ensemble, using Appendix B's noise law and normalized squared distance covariance gives ΔD≤1/[2π(s−1)]. However, the additional factors obtained by substituting these margins into Theorem 5.2 are not thereby established as information-theoretically necessary. Nor does this calculation establish that the particular margin decay in these ensembles is required for the structural lower-bound order. The lower bound establishes estimator-independent structural costs over the broad model class of Theorem 3.1, while our recovery guarantee applies to a regular and separated subclass.
To our knowledge, our work provides the first information-theoretic sample-complexity lower bounds for exact condensation recovery in observational cyclic linear non-Gaussian models. The cost of identifying SCC membership persists even when there are no edges between components, revealing a statistical cost of feedback beyond parent selection in DAG recovery. When smax and dB are held fixed and p grows, Corollary 5.3 and Proposition E.3 establish, to our knowledge, the first minimax characterization for this recovery problem, with sample complexity Θ(logp) on a common separated subclass. These results provide a foundation for further statistical and computational advances in condensation recovery.
In addition to this minimax result, structural matching characterizes how the explicit sample cost varies with SCC size and the number of external parents. Our structural-matching claim concerns the explicit structural term H=slog(ep/s)+dlog(ep/d) shared by the upper and lower bounds, with separation margins and regularity parameters treated separately as constants. The separation dependence remains explicit in Theorem 5.2. Our block-exogeneity characterization and sparse-adjustment principle yield a recovery guarantee that handles unknown SCC membership and external-parent selection jointly with the same explicit structural dependence identified by the lower bound. Structural matching thus connects these unavoidable costs to an achievable procedure, establishing a benchmark for structural sample complexity. Matching bounds jointly in growing structural sizes and separation is a stronger result that we have not established.
Appendix H.1 provides alternative hard families with growing smax=dB=s and p=8s2 that retain the same Ω(H) lower bound but exhibit different margin behavior, as illustrated in Figures 14--15. These constructions show that the specific UP and OUT decay rates of the Figure 1 ensembles are not required for this structural lower-bound order. Structural sizes can influence the separation margins, but do not determine them alone: the graph's connectivity, coefficients, and noise distributions also matter.
Studying structural dependence with signal and regularity parameters treated separately is an important line of research in causal learning. Ghoshal and Honorio [1] establish matching dependence on the number of variables for Gaussian DAG recovery. OptLiNGAM [2] establishes matching dimension and indegree dependence for acyclic non-Gaussian models, with separation and covariance parameters treated as constants. Hütter and Rigollet’s LLC analysis for cyclic Gaussian models under interventions [3] provides a particularly close precedent: its estimation bound matches the lower bound’s explicit structural dependence with conditioning factors treated as constants, while the authors distinguish this result from a uniform minimax guarantee [3, Theorem 4 and Remark 5]. Their analysis connects population identification to finite-sample estimation and quantifies the statistical cost of estimation with feedback. We will explain in the revised manuscript how our results contribute to this line of research by identifying the structural costs of exact condensation recovery and showing how they can be attained at fixed separation.
References
[1] Oh, Han, and Park. “Optimal Estimation of Linear Non-Gaussian Structure Equation Models.” AISTATS, PMLR 258:748–756, 2025.
[2] Ghoshal and Honorio. “Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity.” NeurIPS, 2017.
[3] Hütter and Rigollet. “Estimation Rates for Sparse Linear Cyclic Causal Models.” UAI, PMLR 124:1169–1178, 2020.