# Benign Overfitting of Constant-Stepsize SGD for Linear Regression

arXiv: https://arxiv.org/abs/2103.12692 · HTML: https://mlsanity.com/paper/2103.12692/

## Key facts

- Cited by 71 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 25 references that are in the map.
- First posted on arXiv 23 Mar 2021.

## Builds on (most cited first, 15 of 15)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Optimal Regularization Can Mitigate Double Descent](https://mlsanity.com/paper/2003.01897/) (2020)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model](https://mlsanity.com/paper/2006.08212/) (2020)
- [A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)](https://mlsanity.com/paper/1710.09430/) (2017)
- [Accelerating Stochastic Gradient Descent For Least Squares Regression](https://mlsanity.com/paper/1704.08227/) (2017)
- [Dimension Independent Generalization Error by Stochastic Gradient Descent](https://mlsanity.com/paper/2003.11196/) (2020)

## Built on by (most cited first, 30 of 71)

- [How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?](https://mlsanity.com/paper/2310.08391/) (2023)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [How Does Critical Batch Size Scale in Pre-training?](https://mlsanity.com/paper/2410.21676/) (2024)
- [Scaling Laws in Linear Regression: Compute, Parameters, and Data](https://mlsanity.com/paper/2406.08466/) (2024)
- [From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks](https://mlsanity.com/paper/2302.05882/) (2023)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [Benign Overfitting for Two-layer ReLU Convolutional Neural Networks](https://mlsanity.com/paper/2303.04145/) (2023)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [Understanding Forgetting in Continual Learning with Linear Regression](https://mlsanity.com/paper/2405.17583/) (2024)
- [Analysis of Catastrophic Forgetting for Random Orthogonal Transformation Tasks in the Overparameterized Regime](https://mlsanity.com/paper/2207.06475/) (2022)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shift](https://mlsanity.com/paper/2208.01857/) (2022)
- [The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective](https://mlsanity.com/paper/2210.05021/) (2022)
- [SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs](https://mlsanity.com/paper/2107.05074/) (2021)
- [Selective Underfitting in Diffusion Models](https://mlsanity.com/paper/2510.01378/) (2025)
- [A Theoretical Analysis of Fine-tuning with Linear Teachers](https://mlsanity.com/paper/2107.01641/) (2021)
- [A Defense of the Quadratic Model](https://mlsanity.com/paper/2607.21716/) (2026)
- [From Continual Learning to SGD and Back: Better Rates for Continual Linear Models](https://mlsanity.com/paper/2504.04579/) (2025)
- [Benign Overfitting in Adversarially Robust Linear Classification](https://mlsanity.com/paper/2112.15250/) (2021)
- [A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momenta](https://mlsanity.com/paper/2206.11124/) (2022)
- [On Regularization via Early Stopping for Least Squares Regression](https://mlsanity.com/paper/2406.04425/) (2024)
- [Improved Scaling Laws in Linear Regression via Data Reuse](https://mlsanity.com/paper/2506.08415/) (2025)
- [Benign Overfitting in Deep Neural Networks under Lazy Training](https://mlsanity.com/paper/2305.19377/) (2023)
- [Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Data](https://mlsanity.com/paper/2310.01975/) (2023)
- [Anytime Pretraining: Horizon-Free Learning-Rate Schedules with Weight Averaging](https://mlsanity.com/paper/2602.03702/) (2026)
- [Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions](https://mlsanity.com/paper/2202.00992/) (2022)
- [Accelerated SGD for Non-Strongly-Convex Least Squares](https://mlsanity.com/paper/2203.01744/) (2022)
- [Provable Generalization of Overparameterized Meta-learning Trained with SGD](https://mlsanity.com/paper/2206.09136/) (2022)
- [Learning Ability of Interpolating Deep Convolutional Neural Networks](https://mlsanity.com/paper/2210.14184/) (2022)
- [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025)

## Abstract (arXiv)

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.