mlsanityData to 7 Oct 2026

SGD Generalizes Better Than GD (And Regularization Doesn't Help)

arXiv 2102.01117 ↗First posted 1 Feb 2021cs.LG stat.MLcited by 38

Not on the map. Why?

Abstract (arXiv)

We give a new separation result between the generalization performance of stochastic gradient descent (SGD) and of full-batch gradient descent (GD) in the fundamental stochastic convex optimization model. While for SGD it is well-known that O(1/ε2) iterations suffice for obtaining a solution with ε excess expected risk, we show that with the same number of steps GD may overfit and emit a solution with Omega(1) generalization error. Moreover, we show that in fact Omega(1/ε4) iterations are necessary for GD to match the generalization performance of SGD, which is also tight due to recent work by Bassily et al. (2020). We further discuss how regularizing the empirical risk minimized by GD essentially does not change the above result, and revisit the concepts of stability, implicit bias and the role of the learning algorithm in generalization.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). Builds on 13 of its 23 references that are in the map. First posted on arXiv 1 Feb 2021.

Builds on

13 of 23 references.

References · 13

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2019Introduction to Online Convex Optimizationcited by 793
  3. 2014Convex Optimization: Algorithms and Complexitycited by 569
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  5. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  6. 2017Implicit Regularization in Matrix Factorizationcited by 318
  7. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  8. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  9. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  10. 2018Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatecited by 99
  11. 2018Does data interpolation contradict statistical optimality?cited by 95
  12. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
1 more
  1. 2020Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Studycited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 10; 2023: 12; 2024: 5; 2025: 5; 2026: 2.

38 papers.

Sort:

  1. 2024LoRA-GA: Low-Rank Adaptation with Gradient Approximationcited by 134
  2. 2021Stochastic Training is Not Necessary for Generalizationcited by 63
  3. 2023The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learningcited by 63
  4. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  5. 2021SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochscited by 22
  6. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  7. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  8. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  9. 2022Differentially Private Generalized Linear Models Revisitedcited by 17
  10. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  11. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
  12. 2022On the Overlooked Structure of Stochastic Gradientscited by 13
26 more
  1. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  2. 2022Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Coverscited by 11
  3. 2024The Implicit Bias of Gradient Descent on Separable Multiclass Datacited by 11
  4. 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
  5. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  6. 2023Domain Generalization with Adversarial Intensity Attack for Medical Image Segmentationcited by 8
  7. 2023The Sample Complexity Of ERMs In Stochastic Convex Optimizationcited by 8
  8. 2022Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimizationcited by 7
  9. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  10. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  11. 2024The Sample Complexity of Gradient Descent in Stochastic Convex Optimizationcited by 5
  12. 2023Generalization Bounds for Label Noise Stochastic Gradient Descentcited by 3
  13. 2025Flat Minima and Generalization: Insights from Stochastic Convex Optimizationcited by 3
  14. 2025Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimizationcited by 2
  15. 2022Black-Box Generalization: Stability of Zeroth-Order Learningcited by 1
  16. 2024Convex SGD: Generalization Without Early Stoppingcited by 1
  17. 2025Beyond Propagation of Chaos: A Stochastic Algorithm for Mean Field Optimizationcited by 1
  18. 2025Multi-Agent Reinforcement Learning for Inverse Design in Photonic Integrated Circuitscited by 1
  19. 2022Making Progress Based on False Discoveriescited by 0
  20. 2022Learning Non-Vacuous Generalization Bounds from Optimizationcited by 0
  21. 2023MagicEye: An Intelligent Wearable Towards Independent Living of Visually Impairedcited by 0
  22. 2023Comparison between layer-to-layer network training and conventional network training using Deep Convolutional Neural Networkscited by 0
  23. 2023Semantic Segmentation of Porosity in 4D Spatio-Temporal X-ray μ CT of Titanium Coated Ni wires using Deep Learningcited by 0
  24. 2025The Double Descent Behavior in Two Layer Neural Network for Binary Classificationcited by 0
  25. 2026All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimensioncited by 0
  26. 2026Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivitycited by 0