Is Spurious Correlation Removal Always Learnable?

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 $\gamma$, 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]=\Theta(k(d-k)/(n|\mathcal{E}|))$, and under label-induced shifts a phase transition occurs at $n^*\propto k(d-k)/(|\mathcal{E}|\gamma^2)$ with refined estimation error scaling proportional to $1/\gamma^2$. Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.

Machine learning systems often learn shortcuts that work in the training data but fail in the real world. For example, an image classifier may learn to associate birds with particular backgrounds instead of learning the shape of the bird itself. Researchers try to avoid this by training models on data from multiple environments, hoping to find patterns that stay reliable across settings. This paper asks whether such reliable patterns are always easy to learn when they exist. We show that, in some carefully constructed cases, the answer may be no: the correct stable feature can be identifiable with enough data, but finding it efficiently can still be computationally difficult. We also study when multiple environments are actually useful. Our results suggest that what matters is not just the number of environments, but how differently they expose misleading correlations. These findings help explain why methods for removing spurious correlations sometimes work well and sometimes fail. They also suggest a practical lesson: before blaming an algorithm, practitioners should check whether their environments are diverse enough to reveal the right stable features.