Benign overfitting in ridge regression

Abstract

In many modern applications of deep learning the neural network has many more parameters than the data points used for its training. Motivated by those practices, a large body of recent theoretical research has been devoted to studying overparameterized models. One of the central phenomena in this regime is the ability of the model to interpolate noisy data, but still have test error lower than the amount of noise in that data. arXiv:1906.11300 characterized for which covariance structure of the data such a phenomenon can happen in linear regression if one considers the interpolating solution with minimum ${\ell }_2$-norm and the data has independent components: they gave a sharp bound on the variance term and showed that it can be small if and only if the data covariance has high effective rank in a subspace of small co-dimension. We strengthen and complete their results by eliminating the independence assumption and providing sharp bounds for the bias term. Thus, our results apply in a much more general setting than those of arXiv:1906.11300, e.g., kernel regression, and not only characterize how the noise is damped but also which part of the true signal is learned. Moreover, we extend the result to the setting of ridge regression, which allows us to explain another interesting phenomenon: we give general sufficient conditions under which the optimal regularization is negative.

76 pages; completely rewrote the old version. Enhanced introduction, comparisons to other papers, and results on negative regularization

References in corpus (2)

• Understanding overfitting peaks in generalization error: Analytical risk curves for $l_2$ and $l_1$ penalized interpolation
• Exact expressions for double descent and implicit regularization via surrogate random design

Cited by in corpus (26)

• Multiple Descent: Design Your Own Generalization Curve
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression
• Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression
• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Conditioning of Random Feature Matrices: Double Descent and Generalization Error
• The Benefits of Implicit Regularization from SGD in Least Squares Problems
• A Theoretical Analysis of Fine-tuning with Linear Teachers
• On generalization bounds for deep networks based on loss surface implicit regularization
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Tight bounds for minimum l1-norm interpolation of noisy data
• Foolish Crowds Support Benign Overfitting
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
• Asymptotic Risk of Overparameterized Likelihood Models: Double Descent Theory for Deep Neural Networks
• Revisiting minimum description length complexity in overparameterized models
• Harmless interpolation in regression and classification with structured features
• Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regression
• Is interpolation benign for random forest regression?
• Benign overfitting without concentration
• On the Minimal Error of Empirical Risk Minimization
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks