Learning Causal Structures Using Regression Invariance
This work addresses causal structure learning for researchers in statistics and machine learning, offering incremental improvements in computational efficiency.
The paper tackles causal inference in multi-environment settings by leveraging invariance of functional relations across environments, proposing a baseline algorithm with proven completeness and an improved alternate algorithm that outperforms existing methods in experiments.
We study causal inference in a multi-environment setting, in which the functional relations for producing the variables from their direct causes remain the same across environments, while the distribution of exogenous noises may vary. We introduce the idea of using the invariance of the functional relations of the variables to their causes across a set of environments. We define a notion of completeness for a causal inference algorithm in this setting and prove the existence of such algorithm by proposing the baseline algorithm. Additionally, we present an alternate algorithm that has significantly improved computational and sample complexity compared to the baseline algorithm. The experiment results show that the proposed algorithm outperforms the other existing algorithms.