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 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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Causal-Invariant Cross-Domain Out-of-Distribution Recommendation
RaMen: Multi-Strategy Multi-Modal Learning for Bundle Construction
Best Practices for Large-Scale, Pixel-Wise Crop Mapping and Transfer Learning Workflows
Robust-Multi-Task Gradient Boosting
PSAT: Pediatric Segmentation Approaches via Adult Augmentations and Transfer Learning
A Survey on Prompt Tuning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.