# Is Spurious Correlation Removal Always Learnable?

arXiv: https://arxiv.org/abs/2606.12930 · HTML: https://mlsanity.com/paper/2606.12930/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 30 references that are in the map.
- First posted on arXiv 11 Jun 2026.

## Builds on (most cited first, 7 of 7)

- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [In Search of Lost Domain Generalization](https://mlsanity.com/paper/2007.01434/) (2020)
- [Out-of-Distribution Generalization via Risk Extrapolation (REx)](https://mlsanity.com/paper/2003.00688/) (2020)
- [The Risks of Invariant Risk Minimization](https://mlsanity.com/paper/2010.05761/) (2020)
- [Rethinking Reconstruction Autoencoder-Based Out-of-Distribution Detection](https://mlsanity.com/paper/2203.02194/) (2022)
- [Pedestrian Attribute Recognition as Label-balanced Multi-label Learning](https://mlsanity.com/paper/2405.04858/) (2024)

## Abstract (arXiv)

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 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 mathbbE[dist(hatV,Vinv)2]=Theta(k(d-k)/(n|E|)), and under label-induced shifts a phase transition occurs at n^*propto k(d-k)/(|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.