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 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.
Related
- Causal Discovery beyond Conditional Independence: Identifiability, Algorithms, and Statistical Inference for Directed Acyclic and Cyclic Graphs
- Statistical Inference for Bivariate Functional Causal Discovery
- Statistical Inference for Causal Discovery under Selection and Latent Variables via Single-Target Interventions
- Forecast-Necessary Causal Discovery for Nonlinear Political Panel Data: Feedback, Functional Form, and the Dynamics of Democratization
- Compressibility is not Feedback: A Random-access Gap in Causal Semantic Repair
BibTeX
@misc{oh2026statistical,
title = {{The Statistical Cost of Causal Discovery with Feedback}},
author = {Sunmin Oh and Seungsu Han and Gunwoong Park},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34050},
eprint = {2609.34050},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34050},
}
RIS
TY - UNPB
TI - The Statistical Cost of Causal Discovery with Feedback
AU - Sunmin Oh
AU - Seungsu Han
AU - Gunwoong Park
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34050
UR - https://arxiv.org/abs/2609.34050
AB - 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 s_max, and maximum external-parent count d_B, any estimator requires order s_maxlog(ep/s_max)+d_Blog(ep/d_B) 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 s_max or d_B 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.
ER -