# Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 23 references that are in the map.
- First posted on arXiv 13 May 2025.

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

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [SGD Generalizes Better Than GD (And Regularization Doesn't Help)](https://mlsanity.com/paper/2102.01117/) (2021)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs](https://mlsanity.com/paper/2107.05074/) (2021)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [Benign Underfitting of Stochastic Gradient Descent](https://mlsanity.com/paper/2202.13361/) (2022)
- [Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems](https://mlsanity.com/paper/2106.06880/) (2021)
- [Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is False](https://mlsanity.com/paper/2006.01510/) (2020)
- [Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?](https://mlsanity.com/paper/2103.07079/) (2021)
- [The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2401.12058/) (2024)
- [The Sample Complexity of Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2404.04931/) (2024)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)

## Built on by (most cited first, 3 of 3)

- [Flat Minima and Generalization: Insights from Stochastic Convex Optimization](https://mlsanity.com/paper/2511.03548/) (2025)
- [Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity](https://mlsanity.com/paper/2606.11431/) (2026)
- [The Fourth Quadrant: A Stylized View of Benign Misfitting](https://mlsanity.com/paper/2608.01032/) (2026)

## Abstract (arXiv)

We study the out-of-sample performance of multi-pass stochastic gradient descent (SGD) in the fundamental stochastic convex optimization (SCO) model. While one-pass SGD is known to achieve an optimal Theta(1/√n) excess population loss given a sample of size n, much less is understood about the multi-pass version of the algorithm which is widely used in practice. Somewhat surprisingly, we show that in the general non-smooth case of SCO, just a few epochs of SGD can already hurt its out-of-sample performance significantly and lead to overfitting. In particular, using a step size η = Theta(1/√n), which gives the optimal rate after one pass, can lead to population loss as large as Omega(1) after just one additional pass. More generally, we show that the population loss from the second pass onward is of the order Theta(1/(η T) + η √T), where T is the total number of steps. These results reveal a certain phase-transition in the out-of-sample behavior of SGD after the first epoch, as well as a sharp separation between the rates of overfitting in the smooth and non-smooth cases of SCO. Additionally, we extend our results to with-replacement SGD, proving that the same asymptotic bounds hold after O(n log n) steps. Finally, we also prove a lower bound of Omega(η √n) on the generalization gap of one-pass SGD in dimension d = smashwidetilde O(n), improving on recent results of Koren et al.(2022) and Schliserman et al.(2024).