cs.LGApr 15, 2026

Double descent for least-squares interpolation on contaminated data: A simulation study

Authors: Tino Werner

Organizations: Institute for Mathematics, Carl von Ossietzky University Oldenburg, Carl-von-Ossietzky-Straße 9-11, 26129 Oldenburg, Lower Saxony, Germany

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Overparametrized models can exhibit an excellent generalization performance, although they should be prone to overfitting according to classical statistical theory. The discovery of the "double descent", indicating that the generalization error decreases after a certain model complexity has been reached, opened a new line of research. Robust statistics considers statistical estimation on contaminated data, which, due to assumptions that do not hold on real data, let data points appear as outliers w.r.t. the assumed "ideal" distribution, potentially severely distorting any classical estimator. We address the question whether a double descent phenomenon can be observed in a linear regression setting with contaminated training data. We compare the performance of the highly non-robust least-squares interpolation estimator with several robust alternatives. It turns out that large overparametrization indeed allows for a double descent phenomenon, resulting in a very good generalization performance of the least-squares interpolator, surpassing that of the robust alternatives.

Figures & tables

ppntrainn_{train}ntestn_{test}\SNR\SNRμ\muβ\betaCont.rrcoutc_{out}
Eq. 4.15050{0.1,0.5,2,5}\{0.1,0.5,2,5\}0Normal/uniformNone, XX , YY{0.1,0.25,0.5}\{0.1,0.25,0.5\}100
Table 1: Basic scenario specifications
Figure 1: Test MSE of minimum l2l_{2} -norm interpolation when trained on clean training data.
Figure 2: Test MSE of minimum l2l_{2} -norm interpolation when trained on contaminated training data.
Figure 3: Test MSE of Huber-loss interpolation when trained on clean training data.
Figure 4: Test MSE of Huber-loss interpolation when trained on contaminated training data.
Figure 5: Test MSE of Tukey-loss interpolation when trained on clean training data.
Figure 6: Test MSE of Tukey-loss interpolation when trained on contaminated training data.
Figure 7: Test MSE of SLTS-based interpolation when trained on clean training data.
Figure 8: Test MSE of SLTS when trained on clean training data.
Figure 9: Test MSE of SLTS-based interpolation when trained on contaminated training data.
Figure 10: Test MSE of SLTS when trained on contaminated training data.
Figure 11: Test MSE of RRBoost-based interpolation when trained on clean training data.
Figure 12: Test MSE of RRBoost when trained on clean training data.
Figure 13: Test MSE of RRBoost-based interpolation when trained on contaminated training data.
Figure 14: Test MSE of RRBoost when trained on contaminated training data.
Figure 15: Test MSE of minimum l2l_{2} -norm interpolation when trained on clean training data.
Figure 16: Test MSE of minimum l2l_{2} -norm interpolation when trained on contaminated training data.
Figure 17: Test MSE of Huber-loss interpolation when trained on clean training data.
Figure 18: Test MSE of Huber-loss interpolation when trained on contaminated training data.
Figure 19: Test MSE of Tukey-loss interpolation when trained on clean training data.
Figure 20: Test MSE of Tukey-loss interpolation when trained on contaminated training data.
Figure 21: Test MSE of SLTS-based interpolation when trained on clean training data.
Figure 22: Test MSE of SLTS when trained on clean training data.
Figure 23: Test MSE of SLTS-based interpolation when trained on contaminated training data.
Figure 24: Test MSE of SLTS when trained on contaminated training data.
Figure 25: Test MSE of RRBoost-based interpolation when trained on clean training data.
Figure 26: Test MSE of RRBoost when trained on clean training data.
Figure 27: Test MSE of RRBoost-based interpolation when trained on contaminated training data.
Figure 28: Test MSE of RRBoost when trained on contaminated training data.
Figure 29: Test MSE of minimum l2l_{2} -norm interpolation when trained on clean training data with μ=5\mu=5 .
Figure 30: Test MSE of minimum l2l_{2} -norm interpolation when trained on contaminated training data with μ=5\mu=5 .
Figure 31: Test MSE of Huber-loss interpolation when trained on clean training data.
Figure 32: Test MSE of Huber-loss interpolation when trained on contaminated training data.
Figure 33: Test MSE of SLTS-based interpolation when trained on clean training data.
Figure 34: Test MSE of SLTS when trained on clean training data.
Figure 35: Test MSE of SLTS-based interpolation when trained on contaminated training data.
Figure 36: Test MSE of SLTS when trained on contaminated training data.
Figure 37: Test MSE of minimum l2l_{2} -norm interpolation when trained on YY -contaminated training data.
Figure 38: Test MSE of Huber-loss interpolation when trained on YY -contaminated training data.
Figure 39: Test MSE of minimum l2l_{2} -norm interpolation when trained on YY -contaminated training data.
Figure 40: Test MSE of Huber-loss interpolation when trained on YY -contaminated training data.
Figure 41: Training MSE of minimum l2l_{2} -norm interpolation when trained on clean training data.
Figure 42: Training MSE of minimum l2l_{2} -norm interpolation when trained on contaminated training data.
Figure 43: Training MSE of Huber-loss interpolation when trained on clean training data.
Figure 44: Training MSE of Huber-loss interpolation when trained on contaminated training data.
Figure 45: Training MSE of Tukey-loss interpolation when trained on clean training data.
Figure 46: Training MSE of Tukey-loss interpolation when trained on contaminated training data.
Figure 47: Training MSE of SLTS-based interpolation when trained on clean training data.
Figure 48: Training MSE of SLTS when trained on clean training data.
Figure 49: Training MSE of SLTS-based interpolation when trained on contaminated training data.
Figure 50: Training MSE of SLTS when trained on contaminated training data.
Figure 51: Training MSE of RRBoost-based interpolation when trained on clean training data.
Figure 52: Training MSE of RRBoost when trained on clean training data.
Figure 53: Training MSE of RRBoost-based interpolation when trained on contaminated training data.
Figure 54: Training MSE of RRBoost when trained on contaminated training data.
Figure 55: Training MSE of minimum l2l_{2} -norm interpolation when trained on clean training data.
Figure 56: Training MSE of minimum l2l_{2} -norm interpolation when trained on contaminated training data.
Figure 57: Training MSE of Huber-loss interpolation when trained on clean training data.
Figure 58: Training MSE of Huber-loss interpolation when trained on contaminated training data.
Figure 59: Training MSE of Tukey-loss interpolation when trained on clean training data.
Figure 60: Training MSE of Tukey-loss interpolation when trained on contaminated training data.
Figure 61: Training MSE of SLTS-based interpolation when trained on clean training data.
Figure 62: Training MSE of SLTS when trained on clean training data.
Figure 63: Training MSE of SLTS-based interpolation when trained on contaminated training data.
Figure 64: Training MSE of SLTS when trained on contaminated training data.
Figure 65: Training MSE of RRBoost-based interpolation when trained on clean training data.
Figure 66: Training MSE of RRBoost-based interpolation when trained on clean training data.
Figure 67: Training MSE of RRBoosting when trained on contaminated training data.
Figure 68: Training MSE of RRBoosting when trained on contaminated training data.
Figure 69: Training MSE of minimum l2l_{2} -norm interpolation when trained on clean training data.
Figure 70: Training MSE of minimum l2l_{2} -norm interpolation when trained on contaminated training data.
Figure 71: Training MSE of Huber-loss interpolation when trained on clean training data.
Figure 72: Training MSE of Huber-loss interpolation when trained on contaminated training data.
Figure 73: Training MSE of SLTS-based interpolation when trained on clean training data.
Figure 74: Training MSE of SLTS when trained on clean training data.
Figure 75: Training MSE of SLTS-based interpolation when trained on contaminated training data.
Figure 76: Training MSE of SLTS when trained on contaminated training data.
Figure 77: Training MSE of minimum l2l_{2} -norm interpolation when trained on YY -contaminated training data.
Figure 78: Training MSE of Huber-loss interpolation when trained on YY -contaminated training data.
Figure 79: Training MSE of minimum l2l_{2} -norm interpolation when trained on YY -contaminated training data.
Figure 80: Training MSE of Huber-loss interpolation when trained on YY -contaminated training data.
Figure 81: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of minimum l2l_{2} -norm interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 82: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of minimum l2l_{2} -norm interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 83: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Huber-loss interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 84: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Huber-loss interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 85: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Tukey-loss interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 86: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Tukey-loss interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 87: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS-based interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 88: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS when trained on clean training data and the true coefficient vector β\beta .
Figure 89: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS-based interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 90: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS when trained on contaminated training data and the true coefficient vector β\beta .
Figure 91: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of RRBoosting-based interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 92: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of RRBoosting-based interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 93: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of minimum l2l_{2} -norm interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 94: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of minimum l2l_{2} -norm interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 95: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Huber-norm interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 96: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Huber-norm interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 97: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Tukey-norm interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 98: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Tukey-norm interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 99: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS-based interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 100: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS when trained on clean training data and the true coefficient vector β\beta .
Figure 101: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS-based interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 102: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS when trained on contaminated training data and the true coefficient vector β\beta .
Figure 103: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of RRBoosting-based interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 104: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of RRBoosting-based interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 105: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of minimum l2l_{2} -norm interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 106: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of minimum l2l_{2} -norm interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 107: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Huber-loss interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 108: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Huber-loss interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 109: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS-based interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 110: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS when trained on clean training data and the true coefficient vector β\beta .
Figure 111: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS-based interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 112: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of SLTS when trained on contaminated training data and the true coefficient vector β\beta .
Figure 113: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of RRBoosting-based interpolation when trained on clean training data and the true coefficient vector β\beta .
Figure 114: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of RRBoosting-based interpolation when trained on contaminated training data and the true coefficient vector β\beta .
Figure 115: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of minimum l2l_{2} -norm interpolation when trained on YY -contaminated training data.
Figure 116: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Huber-loss interpolation when trained on YY -contaminated training data.
Figure 117: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of minimum l2l_{2} -norm interpolation when trained on YY -contaminated training data.
Figure 118: Differences ∣∣β^−β∣∣1/n||\hat{\beta}-\beta||_{1}/n for the estimated coefficient vector β^\hat{\beta} of Huber-loss interpolation when trained on YY -contaminated training data.
Figure 119: Mean number of iterations of Huber-loss interpolation when trained on clean training data.
Figure 120: Mean number of iterations of Tukey-loss interpolation when trained on clean training data.
Figure 121: Mean number of iterations of Huber-loss interpolation when trained on contaminated training data.
Figure 122: Mean number of iterations of Tukey-loss interpolation when trained on contaminated training data.
Figure 123: Mean number of iterations of Huber-loss interpolation when trained on clean training data.
Figure 124: Mean number of iterations of Huber-loss interpolation when trained on contaminated training data.
Figure 125: Mean number of iterations of Huber-loss interpolation when trained on clean training data.
Figure 126: Mean number of iterations of Tukey-loss interpolation when trained on clean training data.
Figure 127: Mean number of iterations of Huber-loss interpolation when trained on contaminated training data.
Figure 128: Mean number of iterations of Tukey-loss interpolation when trained on contaminated training data.
Figure 129: Mean number of iterations of Huber-loss interpolation when trained on YY -contaminated training data.
Figure 130: Mean number of iterations of Huber-loss interpolation when trained on YY -contaminated training data.
More in this topic

Double Descent

Double descent describes non-monotonic test error that can peak near interpolation and fall again as model capacity increases.

See all 20 papers

Explore similar work

CardsList
Sep 6, 2021

A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning

The last decade of progress in machine learning (ML), especially the deep learning era, has raised a number of scientific questions that challenge the longstanding dogma of the field. One of the most important riddles was the good empirical generalization of overparameterized models. Overparameterized models are highly complex with respect to the size of the training dataset, which enables them to perfectly fit (i.e., interpolate) even noisy training data. Such interpolation of noisy data is traditionally associated with detrimental overfitting, and yet a wide range of interpolating models -- from simple linear models to deep neural networks -- have been observed to generalize remarkably well on fresh test data. Indeed, the discovery of the double descent phenomenon has revealed that highly overparameterized models can improve over the best underparameterized model in test performance. Understanding learning in this overparameterized regime required new theory and foundational empirical studies, even for the simplest case of the linear model. The underpinnings of this understanding have been laid in foundational analyses of overparameterized linear regression and related statistical learning tasks, mostly published between 2018 and 2022, which resulted in precise analytic characterizations of double descent. This paper provides an overview of the theory of overparameterized ML (henceforth abbreviated as TOPML) by focusing on explaining the most foundational findings through a statistical signal processing perspective. We emphasize the unique aspects that define the TOPML research area as a subfield of modern ML theory and outline interesting open frontiers that remain.

Yehuda Dar, Vidya Muthukumar, Richard G. Baraniuk

Faculty of Computer and Information Science, Ben-Gurion University · Schools of Electrical and Computer Engineering, and Industrial and Systems Engineering, Georgia Institute of Technology · Electrical and Computer Engineering Department, Rice University

Double DescentNeural Network GeneralizationBenign OverfittingStatistical Learning TheoryOverparameterization
AskPDF
Sep 27, 2026

Benign Overfitting for General Norms and Distributions

Understanding why predictors can generalize despite interpolating noisy training data is a central puzzle in machine learning. Most work on such "benign overfitting" studies minimum-2-norm linear regression, reflecting the inductive bias of gradient descent. However, modern optimizers such as Adam and Muon use non-Euclidean update geometries, favoring solutions associated with other norms. Analyzing regression for non-Euclidean norms is substantially more difficult, with known results essentially limited to Gaussians. In this paper, we develop a method to analyze benign overfitting in linear regression for general norms and general (sub-Gaussian) distributions. As a special case, we prove that minimum-p-norm interpolation with p>1 can benignly overfit even for non-Gaussian distributions, under suitable conditions. Perhaps surprisingly, for the 1-norm, benign overfitting does not hold in general for well-behaved (but non-Gaussian) distributions, showing that existing positive 1-norm results rely crucially on Gaussianity. Our proof analyzes the geometry of the dual optimization problem, using concentration and central limit tools to show it is approximately Euclidean in many high-dimensional cases.

Daniel Barzilai, Ohad Shamir

Weizmann Institute of Science · University of Toronto & Vector Institute

Benign OverfittingStatistical Learning TheoryHigh-Dimensional Linear Regression
AskPDF
Jun 4, 2026

How abundant are good interpolators?

Let SS be the set of unit norm linear classifiers θ∈Rdθ\in \mathbb{R}^d which correctly classify every point of a labeled dataset (Xi,yi)i=1n(X_i,y_i)_{i=1}^n, Xi∈RdX_i \in \mathbb{R}^d, yi∈{−1,+1}y_i \in \{-1,+1\}, with a possibly negative margin κκ fixed in advance. Under two natural data-generating distributions of the (X,y)(X,y) pairs -- a Gaussian mixture model and a logistic model with Gaussian features -- and in the proportional regime n/d→αn/d \to α with small enough αα, we establish a large deviation principle on the event that a point θθ chosen uniformly at random from SS achieves a given generalization error, with high probability over the choice of the data. The associated large deviation rate function is deterministic and describes the proportion, at the exponential scale in dd, of interpolating classifiers having a given desired performance. As a consequence, we establish the following concentration phenomenon: all but an exponentially small fraction of interpolating classifiers have approximately the same generalization performance given by the unique maximizer of this rate function. We numerically compare this maximizer to the performance of empirical risk minimization by gradient descent and to the performance of a natural linear program, both finding a point in SS, and deduce that in the overparametrized regime of small αα, these efficient procedures outperform the vast majority of interpolators, pointing to their nontrivial benign overfitting in this setting.

August Y. Chen, Ahmed El Alaoui

Cornell University, Department of Computer Science. Ithaca, NY, USA. · Cornell University, Department of Statistics and Data Science. Ithaca, NY, USA.

Linear ClassificationBenign OverfittingLarge Deviation PrinciplesStatistical Learning Theory
AskPDF