Harmless interpolation of noisy data in regression

By Vidya Muthukumar, Kailas Vodrahalli, Anant Sahai. 2019

213 citations recorded by the source corpus.

A continuing mystery in understanding the empirical success of deep neural networks has been in their ability to achieve zero training error and yet generalize well, even when the training data is noisy and there are more parameters than data points. We investigate this "overparametrization" phenomena in the classical underdetermined linear regression problem, where all solutions that minimize training error interpolate the data, including noise. We give a bound on how well such interpolative solutions can generalize to fresh test data, and show that this bound generically decays to zero with the number of extra features, thus characterizing an explicit benefit of overparameterization. For appropriately sparse linear models, we provide a hybrid interpolating scheme (combining classical sparse recovery schemes with harmless noise-fitting) to achieve generalization error close to the bound on interpolative solutions.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

In Signal Processing

Citations in the corpus

Deep double descent: where bigger models and more data hurt (2019, neutral): “2019) characterize the fundamental limit of of any interpolating solu-tion in the presence of noise and provide some interesting Fourier-theoretic interpretations.”
What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation (2020, background): “Another line of research focuses on the generalization error of algorithms that fit the data perfectly (referred to as interpolating) [29, 10, 8, 20, 9, 25, 5, 7, 14, 21].”
Benign overfitting in linear regression (2019, methodology): “[31] Vidya Muthukumar, Kailas Vodrahalli, and Anant Sahai.”
Classification vs regression in overparameterized regimes: Does the loss function matter? (2020, methodology): “Subsequent work [4, 8, 22, 26, 29, 27] has identified theoretical conditions under which overparameterization and interpolation can be helpful, or at the very least, harmless in linear regression with different feature families.”
Implicit Regularization via Neural Feature Alignment (2020, unknown): “Recently, new analysis of minimum norm interpolators and max margin solutions for overparametrized linear models emphasize the key role of feature geometry, and speciﬁcally feature anisotropy, in the generalization performance (Bartlett et al., 2019; Muthukumar et al., 2019, 2020; Xie et al., 2020).”
The Optimal Ridge Penalty for Real-world High-dimensional Data Can Be Zero or Negative due to the Implicit Ridge Regularization (2020, background): “…al., 2019; Belkin et al., 2018a,b, 2019a,b,c; Nakkiran, 2019; Nakkiran et al., 2020a,b; Liang and Rakhlin, 2020; Hastie et al., 2019; Bartlett et al., 2020; Chinot and Lerasle, 2020; Muthukumar et al., 2020; Mei and Montanari, 2019; Bibas et al., 2019; Dereziński et al., 2019; Negrea et al., 2019).”
Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution (2022, unknown): “By analyzing different linear overparameterized settings Belkin et al. (2019); Hastie et al. (2019); Bartlett et al. (2019); Muthukumar et al. (2020); Mei & Montanari (2019); Bibas et al. (2019) study various statistical properties such as the “double descent curve” in addition to benign…”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “This phenomenon can be rigorously proved for certain simple models (Hastie et al., 2019; Belkin et al., 2019; Muthukumar et al., 2019).”