AI Insight
This study establishes fundamental theoretical limits on how much data is needed to learn causal relationships in systems with feedback loops (cyclic structures). The researchers prove that for cyclic linear non-Gaussian models, the minimum sample size required depends on the size of the largest feedback loop and the number of external influences, scaling logarithmically with the total number of variables. They also develop a new algorithm called BlockExo that achieves near-optimal sample efficiency by identifying feedback components through residual independence testing without needing to know the system's complexity in advance.
Why it matters
Understanding sample complexity bounds for cyclic causal discovery has practical implications for fields where feedback is common, such as economics, neuroscience, and climate science, where data collection is often expensive or limited. This work provides both theoretical guarantees about what is fundamentally possible and a practical algorithm that can work efficiently with smaller datasets when learning systems with feedback.
Understand the Science
⚠️ Preprint – Noch nicht peer-reviewed
Dieser Artikel wurde noch nicht von unabhängigen Experten begutachtet. Die Ergebnisse sind vorläufig und sollten mit Vorsicht interpretiert werden.
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 $s_{max}$, and maximum external-parent count $d_B$, any estimator requires order $s_{max}log(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.
Source: The Statistical Cost of Causal Discovery with Feedback