Benign overfitting in linear regression
By Peter L. Bartlett, Philip M. Long, Gábor Lugosi, Alexander Tsigler. 2019
961 citations recorded by the source corpus.
The phenomenon of benign overfitting is one of the key mysteries uncovered by deep learning methodology: deep neural networks seem to predict well, even with a perfect fit to noisy training data. Motivated by this phenomenon, we consider when a perfect fit to training data in linear regression is compatible with accurate prediction. We give a characterization of linear regression problems for which the minimum norm interpolating prediction rule has near-optimal prediction accuracy. The characterization is in terms of two notions of the effective rank of the data covariance. It shows that overparameterization is essential for benign overfitting in this setting: the number of directions in parameter space that are unimportant for prediction must significantly exceed the sample size. By studying examples of data covariance properties that this characterization shows are required for benign overfitting, we find an important role for finite-dimensional data: the accuracy of the minimum norm interpolating prediction rule approaches the best possible accuracy for a much narrower range of properties of the data distribution when the data lie in an infinite-dimensional space vs. when the data lie in a finite-dimensional space with dimension that grows faster than the sample size.
Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Scaling & Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Percy Liang
- Yoshua Bengio
- Mohit Bansal
- Quoc V. Le
- Ruslan Salakhutdinov
- Sergey Levine
- Jianfeng Gao
- Luke S. Zettlemoyer
In Computational Mechanics
- Robert Tibshirani
- Percy Liang
- Trevor J. Hastie
- Francis R. Bach
- Vitaly Feldman
- Tengyuan Liang
- Christopher R'e
- Martin Jaggi
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Ming-Hsuan Yang
- Jitendra Malik
- Bernt Schiele
- Xiaogang Wang
- Andrew Zisserman
In Scaling & Learning Theory
- Vitaly Feldman
- Percy Liang
- Tengyuan Liang
- Aditi Raghunathan
- Chiyuan Zhang
- Andrea Montanari
- Taiji Suzuki
- Benoit Sanchez
Citations in the corpus
- Shortcut learning in deep neural networks (2020, background): “The complex interactions between training method and architecture are poorly understood so far; strong claims can only be made for simple cases [118].”
- One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares (2022, neutral): “often highly overparameterized models [4], [5], it will take many iterations for OGD to perfectly fit the datapoint.”
- 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].”
- Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution (2022, neutral): “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…”
- Rethinking Parameter Counting in Deep Models: Effective Dimensionality Revisited (2020, background): “(2019), Bartlett et al. (2019), Mei & Montanari (2019), and Belkin et al.”
- The coefficient of determination R-squared is more informative than SMAPE, MAE, MAPE, MSE and RMSE in regression analysis evaluation (2021, neutral): “However, the reference landscape is far wider: the aforementioned considerations stimulated a steady flow of studies investigating more philosophically oriented arguments (Allen, 2004; Berk, 2004), or deeper analysis of implications related to learning (Bartlett 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): “The fact that such interpolating estimators can have low risk has been called benign overfitting (Bartlett et al., 2020; Chinot and Lerasle, 2020) and harmless interpolation (Muthukumar et al., 2020).”
- Large Language Models (2023, background): “” [10, 15] Another argument was that the objective functions for these models are highly nonconvex and optimization would get stuck at poor quality local minima.”
- On the Risk of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels (2019, background): “…risk of estimators that interpolate data, including work on nonparametric local rules (Belkin et al., 2018b,d), high-dimensional linear regression (Bartlett et al., 2019; Hastie et al., 2019), random features model (Ghorbani et al., 2019), and kernel (ridgeless) regression (Belkin et al., 2018c;…”
- Classification vs regression in overparameterized regimes: Does the loss function matter? (2020, methodology): “Note that the isotropic ensemble constitutes the “maximal” level of effective overparameterization (as defined in the second effective rank in [4]) for a given choice of (n, d).”
- Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “This phenomenon is known as double descent, and can be precisely quantified for certain linear models (Hastie et al., 2019; Mei and Montanari, 2019; Belkin et al., 2019; Bartlett et al., 2019).”
- Understanding and Mitigating the Tradeoff Between Robustness and Accuracy (2020, methodology): “Interpolating estimators for linear regression have been studied in many recent works such as (Ma et al., 2018; Belkin et al., 2018; Hastie et al., 2019; Liang & Rakhlin, 2018; Bartlett et al., 2019).”
- An Investigation of Why Overparameterization Exacerbates Spurious Correlations (2020, methodology): “, 2019) and shown analytically in highdimensional regression (Hastie et al., 2019; Bartlett et al., 2019; Mei & Montanari, 2019).”
- Surprises in High-Dimensional Ridgeless Least Squares Interpolation (2019, background): “The term “benign overfitting” was proposed in [6] for such phenomena.”