Fundamental Computational Limits in Pursuing Invariant Causal Prediction and Invariance-Guided Regularization
不变因果预测与不变性引导正则化的基本计算极限
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…