Benign Overfitting in Linear Regression

Abstract

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 lies in an infinite dimensional space versus when the data lies in a finite dimensional space whose dimension grows faster than the sample size.

References in corpus (14)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• Breaking the Curse of Dimensionality with Convex Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Spectrally-normalized margin bounds for neural networks
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• To understand deep learning we need to understand kernel learning
• Norm-Based Capacity Control in Neural Networks
• Does data interpolation contradict statistical optimality?
• Diverse Neural Network Learns True Target Functions
• Towards Understanding the Spectral Bias of Deep Learning
• Approximation beats concentration? An approximation view on inference with smooth radial kernels
• Ivanov-Regularised Least-Squares Estimators over Large RKHSs and Their Interpolation Spaces

Cited by in corpus (115)

• Shortcut Learning in Deep Neural Networks
• Is quantum advantage the right goal for quantum machine learning?
• The Modern Mathematics of Deep Learning
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training
• Benign overfitting in ridge regression
• An Investigation of Why Overparameterization Exacerbates Spurious Correlations
• Rethinking Bias-Variance Trade-off for Generalization of Neural Networks
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• Training Data Influence Analysis and Estimation: A Survey
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Generalization despite overfitting in quantum machine learning models
• Optimal Regularization Can Mitigate Double Descent
• Understanding and Mitigating the Tradeoff Between Robustness and Accuracy
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• Exact expressions for double descent and implicit regularization via surrogate random design
• Multiple Descent: Design Your Own Generalization Curve
• Rethinking Parameter Counting in Deep Models: Effective Dimensionality Revisited
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks
• Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization
• Asymptotics of Ridge (less) Regression under General Source Condition
• A Model of Double Descent for High-dimensional Binary Linear Classification
• What causes the test error? Going beyond bias-variance via ANOVA
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent
• Learning curves for the multi-class teacher-student perceptron
• Gaussian Universality of Perceptrons with Random Labels
• On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression
• Failures of model-dependent generalization bounds for least-norm interpolation
• Interpolating Classifiers Make Few Mistakes
• HARFE: Hard-Ridge Random Feature Expansion
• Distributional Generalization: A New Kind of Generalization
• Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
• On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
• On the Generalization Effects of Linear Transformations in Data Augmentation
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression
• Estimation under Model Misspecification with Fake Features
• When Does Preconditioning Help or Hurt Generalization?
• Fitting very flexible models: Linear regression with large numbers of parameters
• The Low-Rank Simplicity Bias in Deep Networks
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• Overparameterized Linear Regression under Adversarial Attacks
• Label-Imbalanced and Group-Sensitive Classification under Overparameterization
• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• Early-stopped neural networks are consistent
• Dimensionality reduction, regularization, and generalization in overparameterized regressions
• Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degree
• Rethinking Cost-sensitive Classification in Deep Learning via Adversarial Data Augmentation
• Tractability from overparametrization: The example of the negative perceptron
• Taxonomizing local versus global structure in neural network loss landscapes
• Linear Regression with Distributed Learning: A Generalization Error Perspective
• Implicit Regularization of Random Feature Models
• Interpolating Predictors in High-Dimensional Factor Regression
• To Each Optimizer a Norm, To Each Norm its Generalization
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Implicit Regularization via Neural Feature Alignment
• On Uniform Convergence and Low-Norm Interpolation Learning
• Benign Overfitting and Noisy Features
• Error Scaling Laws for Kernel Classification under Source and Capacity Conditions
• Implicit Regularization and Convergence for Weight Normalization
• Interpolation and Learning with Scale Dependent Kernels
• On generalization bounds for deep networks based on loss surface implicit regularization
• Increasing Depth Leads to U-Shaped Test Risk in Over-parameterized Convolutional Networks
• Consistent Risk Estimation in Moderately High-Dimensional Linear Regression
• On the proliferation of support vectors in high dimensions
• The Benefits of Implicit Regularization from SGD in Least Squares Problems
• For interpolating kernel machines, minimizing the norm of the ERM solution minimizes stability
• A Deep Conditioning Treatment of Neural Networks
• Empirical Risk Minimization in the Interpolating Regime with Application to Neural Network Learning
• Support vector machines and linear regression coincide with very high-dimensional features
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Removing Spurious Features can Hurt Accuracy and Affect Groups Disproportionately
• Does the Data Induce Capacity Control in Deep Learning?
• Double Descent and Other Interpolation Phenomena in GANs
• The Geometry of Over-parameterized Regression and Adversarial Perturbations
• The Generalization Error of the Minimum-norm Solutions for Over-parameterized Neural Networks
• The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods
• Tight bounds for minimum l1-norm interpolation of noisy data
• The loss landscape of deep linear neural networks: a second-order analysis
• On the Generalization Power of Overfitted Two-Layer Neural Tangent Kernel Models
• The Dynamics of Gradient Descent for Overparametrized Neural Networks
• A finite sample analysis of the benign overfitting phenomenon for ridge function estimation
• The Performance Analysis of Generalized Margin Maximizer (GMM) on Separable Data
• Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolation
• Universal Prediction Band via Semi-Definite Programming
• How Data Augmentation affects Optimization for Linear Regression
• Predictive Model Degrees of Freedom in Linear Regression
• Generalization error of minimum weighted norm and kernel interpolation
• Prediction in latent factor regression: Adaptive PCR and beyond
• Revisiting minimum description length complexity in overparameterized models
• Double Descent Risk and Volume Saturation Effects: A Geometric Perspective
• Foolish Crowds Support Benign Overfitting
• Gaussian Process Boosting
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
• Inference for multiple treatment effects using confounder importance learning
• Dimension Independent Generalization Error by Stochastic Gradient Descent
• Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks
• Relative Flatness and Generalization
• Ghosts in Neural Networks: Existence, Structure and Role of Infinite-Dimensional Null Space
• Good Classifiers are Abundant in the Interpolating Regime
• Is interpolation benign for random forest regression?
• An elementary analysis of ridge regression with random design
• Offline Contextual Bandits with Overparameterized Models
• Bias-variance decomposition of overparameterized regression with random linear features
• Mitigating deep double descent by concatenating inputs
• Precise expressions for random projections: Low-rank approximation and randomized Newton
• Early stopping and polynomial smoothing in regression with reproducing kernels
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regression
• Learning Data-adaptive Nonparametric Kernels