mlsanityData to 14 Oct 2026

The Sample Complexity of Gradient Descent in Stochastic Convex Optimization

arXiv 2404.04931 ↗First posted 7 Apr 2024cs.LG math.OCcited by 6

Not on the map. Why?

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.

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

16 of 26 references.

References · 16

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2014Convex Optimization: Algorithms and Complexitycited by 575
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  4. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 342
  5. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  6. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  7. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 37
  8. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
  9. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 22
  10. 2021SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochscited by 22
  11. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 17
  12. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
4 more
  1. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 14
  2. 2023The Sample Complexity Of ERMs In Stochastic Convex Optimizationcited by 8
  3. 2022Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimizationcited by 7
  4. 2024The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimizationcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 3.

6 papers.

  1. 2025Flat Minima and Generalization: Insights from Stochastic Convex Optimizationcited by 4
  2. 2025Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimizationcited by 3
  3. 2024Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimizationcited by 1
  4. 2026All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimensioncited by 0
  5. 2026Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivitycited by 0
  6. 2026The Fourth Quadrant: A Stylized View of Benign Misfittingcited by 0