# The Sample Complexity of Gradient Descent in Stochastic Convex Optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 26 references that are in the map.
- First posted on arXiv 7 Apr 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [SGD Generalizes Better Than GD (And Regularization Doesn't Help)](https://mlsanity.com/paper/2102.01117/) (2021)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs](https://mlsanity.com/paper/2107.05074/) (2021)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Never Go Full Batch (in Stochastic Convex Optimization)](https://mlsanity.com/paper/2107.00469/) (2021)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [The Sample Complexity Of ERMs In Stochastic Convex Optimization](https://mlsanity.com/paper/2311.05398/) (2023)
- [Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization](https://mlsanity.com/paper/2202.13328/) (2022)
- [The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2401.12058/) (2024)

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

- [Flat Minima and Generalization: Insights from Stochastic Convex Optimization](https://mlsanity.com/paper/2511.03548/) (2025)
- [Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2505.08306/) (2025)
- [Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization](https://mlsanity.com/paper/2412.04274/) (2024)
- [All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension](https://mlsanity.com/paper/2602.08350/) (2026)
- [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 analyze the sample complexity of full-batch Gradient Descent (GD) in the setup of non-smooth Stochastic Convex Optimization. We show that the generalization error of GD, with common choice of hyper-parameters, can be tilde Theta(d/m + 1/√m), where d is the dimension and m is the sample size. This matches the sample complexity of worst-case empirical risk minimizers. That means that, in contrast with other algorithms, GD has no advantage over naive ERMs. Our bound follows from a new generalization bound that depends on both the dimension as well as the learning rate and number of iterations. Our bound also shows that, for general hyper-parameters, when the dimension is strictly larger than number of samples, T=Omega(1/ε4) iterations are necessary to avoid overfitting. This resolves an open problem by Schlisserman et al.23 and Amir er Al.21, and improves over previous lower bounds that demonstrated that the sample size must be at least square root of the dimension.