Fundamental Computational Limits in Pursuing Invariant Causal Prediction and Invariance-Guided Regularization
This addresses fundamental computational barriers in causal inference for researchers and practitioners, though the proposed solution requires additional assumptions.
The paper shows that testing for invariant causal prediction across environments is NP-hard even for linear relationships, implying arbitrarily slow estimation error rates for computationally efficient algorithms. It then proposes a distributionally robust estimator that achieves both computational and statistical efficiency under additional conditions, with non-asymptotic results and empirical validation.
Pursuing invariant prediction from heterogeneous environments opens the door to learning causality in a purely data-driven way and has several applications in causal discovery and robust transfer learning. However, existing methods such as ICP [Peters et al., 2016] and EILLS [Fan et al., 2024] that can attain sample-efficient estimation are based on exponential time algorithms. In this paper, we show that such a problem is intrinsically hard in computation: the decision problem, testing whether a non-trivial prediction-invariant solution exists across two environments, is NP-hard even for the linear causal relationship. In the world where P$\neq$NP, our results imply that the estimation error rate can be arbitrarily slow using any computationally efficient algorithm. This suggests that pursuing causality is fundamentally harder than detecting associations when no prior assumption is pre-offered. Given there is almost no hope of computational improvement under the worst case, this paper proposes a method capable of attaining both computationally and statistically efficient estimation under additional conditions. Furthermore, our estimator is a distributionally robust estimator with an ellipse-shaped uncertain set where more uncertainty is placed on spurious directions than invariant directions, resulting in a smooth interpolation between the most predictive solution and the causal solution by varying the invariance hyper-parameter. Non-asymptotic results and empirical applications support the claim.