Sample costs uncovered for learning feedback loops in causal models
The Statistical Cost of Causal Discovery with Feedback
Machine Learning
Summary
Understanding how variables affect each other in loops, like a feedback system, is tricky because you need enough data to learn the connections accurately. The authors study how many data points it takes to identify groups of variables that strongly influence each other and how they connect to others outside these groups. They provide theoretical limits on this data requirement and introduce a method called BlockExo that efficiently finds these groups and connections without needing to know some key details upfront. Their experiments show that their method needs fewer samples compared to others doing similar tasks.
What this means in practice
- •For data scientists: Design causal discovery analyses for complex systems with feedback using fewer data points.
- •For systems engineers: Develop algorithms that efficiently identify feedback loops in model variables without full prior knowledge of system structure.
Authors
Sunmin Oh, Seungsu Han, Gunwoong Park
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_B\log(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.