acceptodds
Under review as a conference paper at ICLR 2027

The Statistical Cost of Causal Discovery with Feedback

Abstract

What determines the unavoidable sample cost of learning cyclic causal structure? For cyclic linear non-Gaussian models, we study exact condensation recovery from observational data: identifying the strongly connected component (SCC) partition and all edges between components. We establish the first information-theoretic lower bounds on sample complexity for this target. For variables, maximum SCC size , and maximum external-parent count , any estimator requires order samples in the worst case over a regular model class. These bounds distinguish the costs of SCC membership and external-parent selection. Under principal invertibility and without correlation faithfulness, we establish a population block-exogeneity principle that identifies unknown root SCCs through residual independence and inclusion minimality. A sparse-adjustment characterization shows that small adjustment sets suffice to identify SCCs and their direct external parents, without regressing on all previously recovered variables. These characterizations yield BlockExo, which attains a structurally matching sample bound without knowing or under suitable conditions. Simulations support the structural dependence of our sample bound and demonstrate BlockExo's sample-efficient recovery in comparisons with other methods for cyclic causal discovery.

Primary area:
causal reasoning
Keywords:
Causal discovery, Linear non-Gaussian models, Cyclic graphs, Information-theoretic lower bounds, Sample complexity, Block exogeneity, Strongly connected components

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_aow1OpenReview ↗
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 pp variables, maximum SCC size ss, and maximum external parent count dd, exact condensation recovery requires Ω(slog⁡(ep/s)+dlog⁡(ep/d))\Omega(s\log(ep/s) + d\log(ep/d)) samples. Second, under principal invertibility of I−BI - B (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 O((smax⁡log⁡(ep/smax⁡)+dBlog⁡(ep/dB))max⁡{Δpar−2,ΔD−2})O((s_{\max}\log(ep/s_{\max}) + d_B\log(ep/d_B))\max\{\Delta_{\text{par}}^{-2}, \Delta_{\mathcal{D}}^{-2}\}) 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 G[R]G[R] 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 ≤d\le d rather than the entire previously recovered ancestral set FF (which can grow to O(p)O(p)), the method avoids high-dimensional regression variance inflation when the condensation graph is sparse (dB≪pd_B \ll p).
  • 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 (s,ds, d) and Separation Margins (Δpar,ΔD\Delta_{\text{par}}, \Delta_{\mathcal{D}}): The paper claims that BlockExo "attains a structurally matching sample bound" relative to the lower bound Ω(slog⁡(ep/s)+dlog⁡(ep/d))\Omega(s\log(ep/s) + d\log(ep/d)) in Theorem 3.1. However, Theorem 3.1 is proved using weak edges scaling as (s−1)−1/2(s-1)^{-1/2} and d−1/2d^{-1/2} (Figure 1), whereas the upper bound in Theorem 5.2 / Corollary 5.3 multiplies the structural term LL by max⁡{Δpar−2,ΔD−2}\max\{\Delta_{\text{par}}^{-2}, \Delta_{\mathcal{D}}^{-2}\}. In the lower-bound constructions of Figure 1, the separation margins Δpar\Delta_{\text{par}} and ΔD\Delta_{\mathcal{D}} themselves shrink with ss and dd (or with edge weights), so plugging the lower-bound instances into Theorem 5.2 would incur additional polynomial factors in ss and dd through Δpar−2\Delta_{\text{par}}^{-2} and ΔD−2\Delta_{\mathcal{D}}^{-2}. Indeed, Corollary 5.3 only claims minimax optimality Θ(log⁡p)\Theta(\log p) when s,d,γpar,γDs, d, \gamma_{\text{par}}, \gamma_{\mathcal{D}} are held fixed.
  • Exponential Computational Complexity pO(s+d)p^{\mathcal{O}(s+d)}: BlockExo relies on exhaustive subset enumeration over all candidate blocks C⊆RC \subseteq R (∣C∣≤s|C| \le s) and parent sets P⊆FP \subseteq F (∣P∣≤d|P| \le d) in increasing order of ∣C∣+∣P∣|C| + |P|. While tractable for s+d≤5s+d \le 5, its runtime scales as pO(s+d)p^{\mathcal{O}(s+d)}, 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 PASS^(C,P)\widehat{\text{PASS}}(C,P) requires threshold multipliers κup,κout\kappa_{\text{up}}, \kappa_{\text{out}} (and a choice of dependence functional D\mathcal{D}), which in Theorem 5.2 are existential constants depending on unknown model parameters. The main text never specifies which dependence functional D\mathcal{D} or threshold tuning rule is actually used in BlockExo in Section 6, nor how sensitive the algorithm is to these thresholds in finite samples (in contrast to Coarsening, 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 Δ^hyb2/L\widehat{\Delta}_{\text{hyb}}^2 / L is never defined, and the alignment across smax⁡∈{1,2,3,4}s_{\max} \in \{1, 2, 3, 4\} in Figure 3(a) remains fairly loose. (2) All experiments use only 20 replicates and test only smax⁡∈{2,3}s_{\max} \in \{2, 3\} in Figure 4, where BlockExo is given tight search bounds (s,d)=(3,2)(s,d) = (3,2). (3) Two recent baselines – DisjointCycles (Drton et al., 2025) and StableSpIn (Misiakos & Püschel, 2026) – achieve 0% exact recovery across all four panels of Figure 4 (even on disjoint 2-cycles, which DisjointCycles is specifically designed for!), with no explanation in the main text for why they fail.
Questions for authors
  1. Dependence of Δpar\Delta_{\text{par}} and ΔD\Delta_{\mathcal{D}} on (s,d)(s, d) in the Lower-Bound Ensemble: In the lower-bound constructions of Figure 1 (where edge weights scale as (s−1)−1/2(s-1)^{-1/2} and d−1/2d^{-1/2} to satisfy Assumption 2.2), how do the population margins Δpar\Delta_{\text{par}} and ΔD\Delta_{\mathcal{D}} scale with ss and dd? Doesn't Theorem 5.2 yield a sample complexity of O((s2 or s)⋅slog⁡(ep/s))\mathcal{O}((s^2\text{ or }s) \cdot s\log(ep/s)) on those instances rather than O(slog⁡(ep/s))\mathcal{O}(s\log(ep/s)) because ΔD−2\Delta_{\mathcal{D}}^{-2} scales with ss (and Δpar−2\Delta_{\text{par}}^{-2} with dd)? This point weighed most heavily in my final assessment. I would consider revising my score upward if it can be adequately addressed.
  2. Practical Selection of κup\kappa_{\text{up}} and κout\kappa_{\text{out}}: How are the thresholds τup(t)\tau_{\text{up}}(t) and τout(t)\tau_{\text{out}}(t) chosen in the simulations in Section 6? Are κup\kappa_{\text{up}} and κout\kappa_{\text{out}} fixed across all experiments, or tuned on synthetic validation data? How sensitive is BlockExo to varying κup,κout\kappa_{\text{up}}, \kappa_{\text{out}} (analogous to showing Coarsening (0.1) vs. Coarsening (0.2) in Figure 4)?
  3. Why Do DisjointCycles and StableSpIn Achieve 0% Recovery in Figure 4? Panels (a) and (c) of Figure 4 specifically test disjoint 2-cycles (smax⁡=2s_{\max}=2), which is the exact setting of Drton et al. (2025). Why does DisjointCycles achieve 0/20 recovery up to n=1024n=1024? This result seems unexpected.
  4. Scalability Beyond s+d≤5s+d \le 5: Since BlockExo searches over (∣R∣≤s)(∣F∣≤d)\binom{|R|}{\le s}\binom{|F|}{\le d} pairs, what is the largest s+ds+d for which BlockExo remains computationally feasible at p=50p=50? Can the UP covariance screening step be used to prune candidate parent sets P⊆FP \subseteq F via sparse regression (e.g., Lasso/OMP of XCX_C on XFX_F) before running the expensive non-parametric OUT independence tests?
4 comments

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)\Delta_{\rm par}\le 1/(2\sqrt d) 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)]\Delta_{\mathcal D}\le 1/[2\pi(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⁡s_{\max} and dBd_B are held fixed and pp grows, Corollary 5.3 and Proposition E.3 establish, to our knowledge, the first minimax characterization for this recovery problem, with sample complexity Θ(log⁡p)\Theta(\log p) 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)H=s\log(ep/s)+d\log(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=ss_{\max}=d_B=s and p=8s2p=8s^2 that retain the same Ω(H)\Omega(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.

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 D\mathcal D in all experiments. The thresholds are τj(t)=κjℓ(t)/n,j∈{up,out},t=∣C∣+∣P∣,\tau_j(t)=\kappa_j\sqrt{\ell(t)/n},\qquad j\in\{\mathrm{up},\mathrm{out}\},\quad t=|C|+|P|, with δ=0.05\delta=0.05. 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 κup=1.68\kappa_{\rm up}=1.68 throughout, with κout=0.22\kappa_{\rm out}=0.22, 0.040.04, and 0.010.01 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 p=50p=50, (smax⁡,dB)=(3,2)(s_{\max},d_B)=(3,2), and n=768n=768, all nine combinations obtained by multiplying each of κup\kappa_{\rm up} and κout\kappa_{\rm out} by {0.8,1,1.25}\{0.8,1,1.25\} achieve 19--20/20 exact recoveries. Near the recovery transition, tuning matters more: at n=512n=512 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 3×33\times3 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 κ\kappa

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 p=50p=50 and (smax⁡,dB)=(3,2)(s_{\max},d_B)=(3,2), this procedure achieves 20/20 and 19/20 exact recoveries under asymmetric and symmetric Gaussian-mixture noise at total n=4096n=4096, respectively, and 20/20 under uniform noise at n=8192n=8192 (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 LL 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 (smax⁡,dB)=(6,2)(s_{\max},d_B)=(6,2) at p=50p=50 and n=2048n=2048, 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 (smax⁡,dB)=(3,2)(s_{\max},d_B)=(3,2), the enlarged bounds (4,2),(3,3),(4,3)(4,2),(3,3),(4,3) each yield 20/20 exact recoveries at p=50,n=1024p=50,n=1024.

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 p=50p=50 disjoint-cycle construction and asymmetric-mixture noise, we increased the sample size to n=20,000n=20{,}000 and obtained 20/20 exact recoveries for each dB∈{1,2}d_B\in\{1,2\}. Successful recovery was thus obtained with substantially more data, at a scale comparable to the n=10,000n=10{,}000--100,000100{,}000 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 p=8p=8 models with dense or sparse Laplace noise, it achieved 20/20 exact recoveries in each setting at both n=2048n=2048 and n=8192n=8192. 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 n=2048n=2048 and 81928192, 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 s+ds+d 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 pp, whereas Coarsening's bound grows linearly in pp.

Question 4 (Scalability Beyond s+d≤5s+d\leq 5)

To examine the practical cost beyond s+d≤5s+d\le5, we conducted additional experiments at p=50,n=2048p=50,n=2048 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 s+d=7s+d=7 settings. For s+d=8s+d=8, the settings (s,d)=(6,2),(5,3),(4,4)(s,d)=(6,2),(5,3),(4,4) 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 s+d=7s+d=7 runtimes to approximately 0.4--1.6 hours, with median paired speedups of about 3.7×3.7\times. For (s,d)=(6,2),(5,3),(4,4)(s,d)=(6,2),(5,3),(4,4), GPU runtimes were approximately 3.5, 4, and 8 hours, respectively, with speedups ranging from 2.5×2.5\times to 4.7×4.7\times. 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 mm variables from FF reduces the number of parent sets considered per candidate block from (∣F∣≤d)\binom{|F|}{\le d} to (m≤d)\binom{m}{\le d}, 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.

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

The paper studies the sample complexity of recovering the condensation graph of a cyclic linear non-Gaussian structural equation model, including its strongly connected components (SCCs) and the directed edges between them. The authors derive information-theoretic lower bounds separating the costs of identifying SCC membership and external parents, giving a necessary sample complexity. In particular, over a class of models with SCC size at most ss and at most dd external parents per SCC, any estimator requires order slog⁡(ep/s)+dlog⁡(ep/d)s\log(ep/s)+d\log(ep/d) samples in the worst case.

The paper also establishes a block-exogeneity characterization for identifying unknown root SCCs through residual independence without correlation faithfulness. A sparse-adjustment characterization then identifies external parents using small conditioning sets. Based on these results, the authors propose BlockExo and derive a finite-sample recovery guarantee with matching structural dependence under quantitative separation assumptions. Simulations on synthetic cyclic graphs demonstrate favorable recovery performance relative to several existing approaches.

Critical strengths
  1. The paper establishes separate information-theoretic lower bounds for recovering SCC membership and external parents. The reciprocal-star and parent-star packing constructions in Appendix B provide a convincing basis for the respective smax⁡log⁡(ep/smax⁡)s_{\max}\log(ep/s_{\max}) and dBlog⁡(ep/dB)d_B\log(ep/d_B) terms. This extends sample-complexity analysis from acyclic LiNG models to the condensation recovery problem in cyclic systems.

  2. The block-exogeneity result (Theorem 4.1) characterizes ancestral blocks using scalar residual independence under principal invertibility, without requiring correlation faithfulness. The proof uses the Darmois–Skitovitch theorem and a rank argument to rule out incoming edges. Proposition 4.3 further shows that sparse adjustment suffices to identify external parents. These results lead to BlockExo, whose recovery guarantee has the same structural dependence as the lower bound under appropriate separation conditions.

Critical weaknesses
  1. Assumption 2.2 requires the eigenvalues of the full covariance matrix to be bounded independently of pp. In the one-SCC construction (Appendix F.1), increasing pp adds children of the same root. For dB=1d_B=1, each child satisfies Xj=0.8X1+εjX_j=0.8X_1+\varepsilon_j, so λmax⁡(Σ)≥1+0.64kVar⁡(X1)\lambda_{\max}(\Sigma)\ge1+0.64k\operatorname{Var}(X_1) with kk children, which grows with pp. However, Section 5.2 notes that the analysis needs eigenvalue bounds only for principal submatrices of size at most smax⁡+dB+1s_{\max}+d_B+1.

  2. Theorem 5.2 requires n≳Lmax⁡{1,Δpar−2,ΔD−2}n\gtrsim L\max\{1,\Delta_{\mathrm{par}}^{-2},\Delta_D^{-2}\}, whereas the lower bound does not capture the separation margins. Matching optimality is shown only for fixed s,ds,d on a separated class (Corollary 5.3, Proposition E.3). The gap appears on the lower-bound models themselves. In the parent-star packing (Lemma B.4), each edge has weight 1/(2d)1/(2\sqrt d). Omitting one parent qq from the adjustment set gives Cov⁡(e1(Q∖{q}),Xq)=1/(2d)\operatorname{Cov}(e_1(Q\setminus\{q\}),X_q)=1/(2\sqrt d), so Δpar≤1/(2d)\Delta_{\mathrm{par}}\le1/(2\sqrt d). Theorem 5.2 then requires nn of order d2log⁡(ep/d)d^2\log(ep/d), a factor dd above the lower bound. "Structurally matching" therefore holds only when the margins do not shrink with ss and dd.

Questions for authors
  1. Can Assumption 2.2 be restated in the local form (principal submatrices of size at most smax⁡+dB+1s_{\max}+d_B+1) that the proofs and simulations actually use?

  2. Can matching bounds be established for growing smax⁡s_{\max} and dBd_B, including the dependence on Δpar\Delta_{\mathrm{par}} and ΔD\Delta_D? Given that Δpar≤1/(2d)\Delta_{\mathrm{par}}\le1/(2\sqrt d) on the parent-star packing, how should "structurally matching" be interpreted?

  3. How should the search bounds (s,d)(s,d) and the multiplier κout\kappa_{\mathrm{out}} be chosen when the structural sizes and the noise law are unknown?

4 comments

Weakness 2 & Question 2

Thank you for highlighting this distinction. As you correctly pointed out, the parent-star calculation introduces an additional factor of at least dd through the UP margin in the sufficient bound of Theorem 5.2 for that ensemble. However, this does not establish a universal additional dd factor or show that such a factor is information-theoretically necessary. Appendix H.1 provides alternative hard families with the same structural lower-bound order but different individual margin behavior, showing that the specific decay rates in Appendix B are not required for that order.

Structural matching refers to the agreement between the explicit structural terms in our lower and upper bounds, H=slog⁡(ep/s)+dlog⁡(ep/d)H=s\log(ep/s)+d\log(ep/d), with separation margins and regularity parameters treated separately as constants. These bounds play complementary roles. The lower bound identifies estimator-independent costs of unknown SCC membership and external-parent selection over the broad model class of Theorem 3.1. Our block-exogeneity characterization and sparse-adjustment principle yield a recovery guarantee over a narrower regular and separated subclass, handling these two uncertainties jointly with the same explicit structural dependence. Theorem 5.2 retains the separation dependence explicitly. We have not established matching bounds jointly in growing structural sizes and separation. For fixed structural bounds, Corollary 5.3 and Proposition E.3 establish, to our knowledge, the first minimax sample-complexity characterization for exact condensation recovery in observational cyclic linear non-Gaussian models: Θ(log⁡p)\Theta(\log p) on a common separated subclass.

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.

To our knowledge, our work establishes 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. These lower bounds provide a benchmark for evaluating the structural sample complexity of future condensation-recovery algorithms. BlockExo matches the explicit structural dependence of these lower bounds when the separation margins and regularity parameters are treated as constants. In addition, when smax⁡s_{\max} and dBd_B are held fixed, BlockExo attains the minimax sample complexity Θ(log⁡p)\Theta(\log p) on a common separated subclass as pp grows.

References

[1] Ghoshal and Honorio. “Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity.” NeurIPS, 2017.

[2] Oh, Han, and Park. “Optimal Estimation of Linear Non-Gaussian Structure Equation Models.” AISTATS, PMLR 258:748–756, 2025.

[3] Hütter and Rigollet. “Estimation Rates for Sparse Linear Cyclic Causal Models.” UAI, PMLR 124:1169–1178, 2020.

[4] Freedman, D. A. “Bootstrapping regression models.” The Annals of Statistics, 9(6):1218–1228, 1981.

[5] Eck, D. J. “Bootstrapping for multivariate linear regression models.” Statistics & Probability Letters, 134:141–149, 2018.

[6] Liu, H., Roeder, K., and Wasserman, L. “Stability approach to regularization selection (StARS) for high dimensional graphical models.” NeurIPS, 23:1432–1440, 2010.

[7] Biza, K., Tsamardinos, I., and Triantafillou, S. “Tuning causal discovery algorithms.” Proceedings of the International Conference on Probabilistic Graphical Models, PMLR 138:17–28, 2020.

Weakness 1 & Question 1

Thank you for your suggestion. Both our lower and upper bounds remain valid under the local covariance condition. We have therefore restated Assumption 2.2 as λ−1≤λmin⁡(ΣH,H)≤λmax⁡(ΣH,H)≤λ,∣H∣≤min⁡p,smax⁡+dB+1,\lambda^{-1}\le\lambda_{\min}(\Sigma_{H,H})\le\lambda_{\max}(\Sigma_{H,H})\le\lambda,\qquad |H|\le\min\\{p,s_{\max}+d_B+1\\}, while retaining the sub-Gaussian tail assumption. We have also made the candidate-size range explicit in Assumption 5.1 and clarified how the proof in Appendix D uses the local covariance condition over this range.

The lower-bound constructions satisfy the stronger global condition and hence belong to the revised model class. For the upper bound, with valid search bounds and correct testing decisions, each round stops at a pair of total size at most smax⁡+dBs_{\max}+d_B. As noted in Section 5.2, each required regression therefore involves at most smax⁡+dBs_{\max}+d_B predictors and one response. Thus the local condition supplies the eigenvalue bounds needed for the regression and concentration arguments.

Your example helpfully illustrates the benefit of the local formulation. Write h=smax⁡+dB+1h=s_{\max}+d_B+1. Although adding children increases the largest eigenvalue of the full covariance matrix, any required submatrix involves at most hh children, whose loading matrix has norm at most 0.8h0.8\sqrt h. Consequently, the required local covariance matrices have eigenvalues bounded above and away from zero, with bounds depending on smax⁡s_{\max} and dBd_B, but not on the total number of variables pp. The local formulation therefore accommodates the growing-pp experimental construction while retaining the covariance control needed for recovery.

Question 3

  • Search bounds

Exact structural sizes are unnecessary for recovery. Any valid upper bounds suffice under our recovery conditions (Theorem 5.2). Our additional paired experiment directly confirms recovery with conservative bounds: with the true structure fixed at (smax⁡,dB)=(3,2)(s_{\max},d_B)=(3,2), enlarging the search bounds to (4,2),(3,3)(4,2),(3,3), or (4,3)(4,3) still gives 20/20 exact recoveries for each choice at p=50,n=1024p=50, n=1024. For underspecified bounds, Proposition C.4 provides a diagnostic for deciding when to increase them. At the population level, the algorithm returns failure if and only if s<smax⁡s<s_{\max} or d<dBd<d_B. When no candidate passes, this gives a principled reason to increase the bounds, with the finite-sample diagnostic interpreted in light of the accuracy of the tests. In practice, we recommend conservative upper bounds guided by domain knowledge, balancing coverage of plausible structural sizes against the additional sample and computational costs of a wider search. We will expand the practical guidance in Section 4.3 and include this additional comparison in Appendix F.6.

  • κ\kappa selection

For κ\kappa selection, we propose a simple data-driven method that achieves high recovery rates with sufficient data, without requiring any prior knowledge of the noise distribution. On one third of the observations, we run BlockExo with a common, prespecified sequence of threshold multipliers and retain the first completed fit. We resample residual vectors independently across fitted blocks [4,5], generate bootstrap observations, and recompute UP and OUT along the provisional recovery path. This estimates sampling variation for tests that should pass under the fitted model. The empirical 95th percentiles of the normalized UP and OUT maxima select the two multipliers. Recovery is then performed anew on the remaining observations. Algorithm 2 in Appendix G.1 specifies the complete procedure.

With p=50p=50 and (smax⁡,dB)=(3,2)(s_{\max},d_B)=(3,2) in the Figure 4 construction, the method achieves 19/20 exact recoveries under asymmetric Gaussian-mixture noise at total n=2048n=2048. At n=4096n=4096, the asymmetric and symmetric mixtures give 20/20 and 19/20, respectively; uniform noise gives 20/20 at n=8192n=8192 (Table 4). The procedure shows empirical robustness to initialization. At the larger sample sizes, it achieves 18--20 exact recoveries out of 20 under each of four changes to the multiplier sequence used for the provisional fit (Table 5). Exact recovery was also possible with an incorrect provisional SCC partition. Under uniform noise, all 20 provisional fits returned only singleton blocks, yet the procedure recovered the condensation exactly in all 20 cases (Table 4).

This simple procedure can be further developed through improved provisional estimation and resampling, or adaptations of stability-based selection [6] and Out-of-sample Causal Tuning [7].

Thank you for the detailed response. The local covariance condition resolves my first concern.

On matching, a gap may remain when the margins are not constant, since the families in Appendix H.1 keep only one margin bounded at a time. If the intended meaning of “structural matching” is matching with margins treated as constants, this should be stated clearly in the abstract and contributions, which currently present the result more strongly. Please also clarify that minimax optimality is shown only for fixed structural bounds, and mention the possible gap as future work.

Assuming these revisions, I raise my score to 3.

Thank you for the careful follow-up and for raising your score. As you correctly note, our intended meaning of “structural matching” is that the bounds match in their structural dependence when the margins are treated as constants. We will make this explicit in the abstract and contributions. We will also clarify that we establish minimax optimality only for fixed structural bounds and identify the possible gap when the margins vary as a question for future work.

Reviewer_TDtWOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the problem of learning SCC partition and all edges between the components of a cyclic linear non-Gaussian models. In their first result, the provide a worst case lower bound on the sample complexity for SCC learning problem defined earlier in terms of max SCC size and maximum indegree of the SCC. Under some additional assumptions, they provide sample efficient recovery algorithm as well.

Critical strengths
  1. The paper is very well written. I cruised through the initial pages in no time.
  2. The lower bound is quite interesting.
  3. The matching upper bound even under additional assumptions is quite interesting, making the results complete.
Critical weaknesses

Weakness/questions

  1. Add more related work on cyclic Gaussian linear models. In particular, all sample complexity results that were known.
  2. When s=1, this is just a DAG recovery as you said in the paper. I believe that sample complexity results for this would be known. Can you please cite these papers at appropriate places and state the sample complexity known in this regime explicitly. I see that this might have been mentioned at the end of Section 5, this should be mentioned in the introduction, far up in the paper.
  3. Also, can authors talk about the time complexity of the proposed approaches. Either add time complexity information in the introduction, related work or immediately after you state the theorems.
Questions for authors

See weaknesses

1 comment

Question 1

Thank you for suggesting this broader comparison. We have added a discussion of statistical guarantees for cyclic Gaussian linear models in Appendix A.2, including the bounds of H"utter and Rigollet [1], Causal Dantzig [2], FRP [3], and related Lyapunov models [4]. Table 2 summarizes their observation regimes, assumptions, recovery targets, and sample-complexity or estimation rates, clarifying their relation to our observational condensation-recovery problem.

Question 2

Thank you for suggesting that we highlight the connection to DAG recovery earlier in the paper. We have expanded the Introduction's related-work paragraph to state the known DAG rate and explain how our result specializes to it. When smax⁡=1s_{\max}=1, every SCC is a singleton, exact condensation recovery becomes exact DAG recovery, and dB=dind_B=d_{\rm in}. For din≥1d_{\rm in}\ge1, our structural term reduces to log⁡(ep)+dinlog⁡(ep/din)≍dinlog⁡(ep/din),\log(ep)+d_{\rm in}\log(ep/d_{\rm in})\asymp d_{\rm in}\log(ep/d_{\rm in}), matching the dimension and sparsity dependence established for acyclic LiNGAMs by OptLiNGAM [5]. Allowing cycles introduces the additional task of discovering which variables belong to each SCC. To our knowledge, our work provides the first information-theoretic sample-complexity lower bounds for exact condensation recovery in cyclic linear non-Gaussian models from observational data. Our membership lower bound shows that this cost remains even without edges between SCCs, and identifies it through the smax⁡log⁡(ep/smax⁡)s_{\max}\log(ep/s_{\max}) term. Our recovery guarantee matches the combined membership and external-parent structural costs at fixed separation.

Question 3

We have expanded the existing ``Search bounds'' paragraph following Algorithm~1 and the population-recovery theorem to make the connection between candidate counts and computational complexity explicit.

In each round, BlockExo examines candidate pairs (C,P)(C,P) in order of increasing total size ∣C∣+∣P∣|C|+|P|. With valid search bounds and correct testing decisions, it finds a passing pair of total size at most smax⁡+dBs_{\max}+d_B and stops the search for that round. Using the O(nlog⁡n)O(n\log n) scalar dCov estimator of [6], the resulting time complexity is bounded by nlog⁡n,pO(smax⁡+dB)n\log n\\,p^{O(s_{\max}+d_B)}. For arbitrary testing decisions, the supplied search bounds (s,d)(s,d) give a worst-case bound of nlog⁡n,pO(s+d)n\log n\\,p^{O(s+d)}. Thus, for fixed (s,d)(s,d), the time complexity is polynomial in pp, with the exponent bounded by O(s+d)O(s+d). Appendix~A compares the computational complexity of BlockExo with that of related methods.

References

[1] Hütter and Rigollet. “Estimation Rates for Sparse Linear Cyclic Causal Models.” UAI, PMLR 124:1169–1178, 2020.

[2] Rothenhäusler, Bühlmann, and Meinshausen. “Causal Dantzig: Fast Inference in Linear Structural Equation Models with Hidden Variables under Additive Interventions.” The Annals of Statistics, 47(3):1688–1722, 2019.

[3] Yi and Lee. “Filter, Rank, and Prune: Learning Linear Cyclic Gaussian Graphical Models.” AISTATS, PMLR 238:1135–1143, 2024.

[4] Dettling, Drton, and Kolar. “On the Lasso for Graphical Continuous Lyapunov Models.” CLeaR, PMLR 236:514–550, 2024.

[5] Oh, Han, and Park. “Optimal Estimation of Linear Non-Gaussian Structure Equation Models.” AISTATS, PMLR 258:748–756, 2025.

[6] Huo and Székely. “Fast Computing for Distance Covariance.” Technometrics, 58(4):435–447, 2016.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Follow-up on our responses

Thank you again for your time and thoughtful feedback. As the discussion period is nearing its end, we would appreciate it if you could take a look at our responses. We would be happy to clarify any remaining questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.