Benign Overfitting of Constant-Stepsize SGD for Linear Regression

Abstract

There is an increasing realization that algorithmic inductive biases are central in preventing overfitting; empirically, we often see a benign overfitting phenomenon in overparameterized settings for natural learning algorithms, such as stochastic gradient descent (SGD), where little to no explicit regularization has been employed. This work considers this issue in arguably the most basic setting: constant-stepsize SGD (with iterate averaging or tail averaging) for linear regression in the overparameterized regime. Our main result provides a sharp excess risk bound, stated in terms of the full eigenspectrum of the data covariance matrix, that reveals a bias-variance decomposition characterizing when generalization is possible: (i) the variance bound is characterized in terms of an effective dimension (specific for SGD) and (ii) the bias bound provides a sharp geometric characterization in terms of the location of the initial iterate (and how it aligns with the data covariance matrix). More specifically, for SGD with iterate averaging, we demonstrate the sharpness of the established excess risk bound by proving a matching lower bound (up to constant factors). For SGD with tail averaging, we show its advantage over SGD with iterate averaging by proving a better excess risk bound together with a nearly matching lower bound. Moreover, we reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares (minimum-norm interpolation) and ridge regression. Experimental results on synthetic data corroborate our theoretical findings.

arXiv comment56 pages, 2 figures. A short version is accepted at the 34th Annual Conference on Learning Theory (COLT 2021)

References in corpus (10)

• Understanding deep learning requires rethinking generalization
• Benign Overfitting in Linear Regression
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
• Benign overfitting in ridge regression
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• Optimal Regularization Can Mitigate Double Descent
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model
• A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)

Cited by in corpus (5)

• A Theoretical Analysis of Fine-tuning with Linear Teachers
• The Benefits of Implicit Regularization from SGD in Least Squares Problems
• On the Double Descent of Random Features Models Trained with SGD
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics