Is Spurious Correlation Removal Always Learnable?
For researchers in invariant learning and domain generalization, this work identifies fundamental computational barriers and provides practical diversity diagnostics.
This paper shows that invariant learning can be computationally hard even when statistically identifiable, proving that under a plausible cryptographic primitive, there exist samplable multi-environment instances where polynomial-time algorithms fail to recover the invariant subspace. The authors also derive minimax rates for invariant subspace estimation under sufficient diversity and characterize a phase transition in label-induced shifts.
Invariant learning can fail even when the invariant structure is statistically identifiable. We show a conditional computational barrier: under a black-box samplable supervised sparse recovery primitive motivated by average-case sparse-recovery reductions, there exist \emph{samplable} multi-environment instances with a one-dimensional predictive invariant subspace ($k=1$) that are learnable with polynomial samples by exhaustive search, while any polynomial-time constant-accuracy recovery algorithm would contradict the primitive. We further quantify environment diversity by a separation parameter $γ$, which controls identifiability and the curvature of invariance objectives. Under sufficient diversity and local Gaussian regularity, the minimax risk is $\mathbb{E}[\dist(\hat{V},V_{\mathrm{inv}})^2]=Θ(k(d-k)/(n|\mathcal{E}|))$, and under label-induced shifts a phase transition occurs at $n^*\propto k(d-k)/(|\mathcal{E}|γ^2)$ with refined estimation error scaling proportional to $1/γ^2$. Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.