# The Statistical Cost of Causal Discovery with Feedback

arXiv: https://arxiv.org/abs/2609.34050 · HTML: https://mlsanity.com/paper/2609.34050/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Builds on (most cited first, 13 of 13)

- [Foundations of Structural Causal Models with Cycles and Latent Variables](https://mlsanity.com/paper/1611.06221/) (2016)
- [Learning linear structural equation models in polynomial time and sample complexity](https://mlsanity.com/paper/1707.04673/) (2017)
- [Characteristic and Universal Tensor Product Kernels](https://mlsanity.com/paper/1708.08157/) (2017)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [Fast Computing for Distance Covariance](https://mlsanity.com/paper/1410.1503/) (2014)
- [Inference for Individual Mediation Effects and Interventional Effects in Sparse High-Dimensional Causal Graphical Models](https://mlsanity.com/paper/1809.10652/) (2018)
- [Local Causal Discovery with Linear non-Gaussian Cyclic Models](https://mlsanity.com/paper/2403.14843/) (2024)
- [Learning linear non-Gaussian directed acyclic graph with diverging number of nodes](https://mlsanity.com/paper/2111.00740/) (2021)
- [Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models](https://mlsanity.com/paper/2509.21423/) (2025)
- [Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models: Characterization and Learning](https://mlsanity.com/paper/2603.04780/) (2026)
- [Causal Discovery for Linear Non-Gaussian Models with Disjoint Cycles](https://mlsanity.com/paper/2507.10767/) (2025)
- [ACE Bounds; SEMs with Equilibrium Conditions](https://mlsanity.com/paper/1410.0470/) (2014)
- [Coarsening Linear Non-Gaussian Causal Models with Cycles](https://mlsanity.com/paper/2605.10163/) (2026)

## Abstract (arXiv)

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 p variables, maximum SCC size smax, and maximum external-parent count dB, any estimator requires order smaxlog(ep/smax)+dBlog(ep/dB) 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 smax or dB 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.