Malign Overfitting: Interpolation Can Provably Preclude Invariance

Yoav Wald, Gal Yona, Uri Shalit, Yair Carmon

Introduction

In modern deep learning, over-parameterized models often achieve zero training error—a phenomenon known as interpolation. While this is frequently "benign," allowing models to generalize well to similar test data despite fitting noise, this paper demonstrates that interpolation is "malign" for robustness and invariance. When a model perfectly fits high-dimensional training data, it is mathematically compelled to rely on spurious correlations, undermining its performance in out-of-distribution (OOD) settings.

The Impossibility of Invariant Interpolation

The core contribution of this work is a theoretical proof showing that in high-dimensional settings, any learning rule that interpolates training data with a non-zero margin must incorporate spurious features. Using a high-dimensional Gaussian mixture model, the authors show that as the dimensionality $d$ increases, the "simplest" way for a model to achieve zero training error is to exploit noise rather than the stable, invariant "core" signal.

This is formalized in Theorem 1, which proves that for any interpolating classifier in their model, the robust error (error in a new environment) is at least 0.5—no better than a random guess—even when a perfectly invariant classifier exists. This explains why popular invariance-inducing regularizers, such as Invariant Risk Minimization (IRM) and Variance Risk Extrapolation (VREx), fail when models are large enough to interpolate. As dimensionality grows, these methods lose their regularizing power and converge toward standard Empirical Risk Minimization (ERM) behavior.

Algorithm 1: A Two-Phase Approach to Invariance

To circumvent the malign effects of interpolation, the authors propose a two-stage learning framework:

  1. Feature Extraction: Train separate interpolating classifiers on different environments to extract high-dimensional features.
  2. Invariant Classification: Learn a final, low-dimensional classifier on these features while enforcing an invariance constraint (e.g., Equal Opportunity).

By separating the high-dimensional interpolation task from the invariance-enforcement task, the second stage can identify the core signal without being forced to fit high-dimensional noise.

Empirical Validation

The authors validate their findings using both simulated Gaussian data and the Waterbirds dataset. The results highlight a stark contrast between standard test accuracy and robust accuracy as the model complexity increases.

Figure 3: Performance metrics across varying dimensionality $d$. As models reach the interpolation threshold (Training Accuracy $\approx 1.0$), robust accuracy for standard methods (ERM, IRM, etc.) collapses, while Algorithm 1 maintains high robust performance.

As shown in the figure above, while in-domain test accuracy remains high for all methods (benign overfitting), robust accuracy for baseline methods plummets as $d$ increases. Only the proposed two-stage approach (Algorithm 1) successfully maintains robustness in the over-parameterized regime. On the Waterbirds dataset, this algorithm maintained a low False Negative Rate (FNR) gap across groups even as the model became highly over-parameterized, whereas the fairness properties of standard baselines evaporated.

Conclusion

This research provides a critical theoretical foundation for understanding why over-parameterization can be detrimental to algorithmic fairness and OOD generalization. While fitting every data point might seem ideal for standard performance, it creates a mathematical trap that precludes invariance. The proposed two-phase learning strategy offers a path forward for building robust models in the era of massive neural networks.

Summary updated

Abstract

Learned classifiers should often possess certain invariance properties meant to encourage fairness, robustness, or out-of-distribution generalization. However, multiple recent works empirically demonstrate that common invariance-inducing regularizers are ineffective in the over-parameterized regime, in which classifiers perfectly fit (i.e. interpolate) the training data. This suggests that the phenomenon of "benign overfitting", in which models generalize well despite interpolating, might not favorably extend to settings in which robustness or fairness are desirable. In this work we provide a theoretical justification for these observations. We prove that -- even in the simplest of settings -- any interpolating learning rule (with arbitrarily small margin) will not satisfy these invariance properties. We then propose and analyze an algorithm that -- in the same setting -- successfully learns a non-interpolating classifier that is provably invariant. We validate our theoretical observations on simulated data and the Waterbirds dataset.
BibTeX
@misc{wald2022malign,
  author = {Yoav Wald and Gal Yona and Uri Shalit and Yair Carmon},
  title = {{Malign Overfitting: Interpolation Can Provably Preclude Invariance}},
  year = {2022},
  eprint = {2211.15724},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.15724},
}
Figure