mlsanityData to 7 Oct 2026

Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization

arXiv 2303.10758 ↗First posted 19 Mar 2023cs.LG math.OC stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

This work studies the generalization error of gradient methods. More specifically, we focus on how training steps T and step-size η might affect generalization in smooth stochastic convex optimization (SCO) problems. We first provide tight excess risk lower bounds for Gradient Descent (GD) and Stochastic Gradient Descent (SGD) under the general non-realizable smooth SCO setting, suggesting that existing stability analyses are tight in step-size and iteration dependence, and that overfitting provably happens. Next, we study the case when the loss is realizable, i.e. an optimal solution minimizes all the data points. Recent works show better rates can be attained but the improvement is reduced when training time is long. Our paper examines this observation by providing excess risk lower bounds for GD and SGD in two realizable settings: 1) η T = bigOn, and (2) η T = bigOmegan, where n is the size of dataset. In the first case η T = bigOmegan, our lower bounds tightly match and certify the respective upper bounds. However, for the case η T = bigOmegan, our analysis indicates a gap between the lower and upper bounds. A conjecture is proposed that the gap can be closed by improving upper bounds, supported by analyses in two special scenarios.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 35 of its 52 references that are in the map. First posted on arXiv 19 Mar 2023.

Builds on

35 of 52 references.

References · 35

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2016Densely Connected Convolutional Networkscited by 6,691
  4. 2021Convex optimizationcited by 2,479
  5. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  6. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  7. 2019Benign Overfitting in Linear Regressioncited by 544
  8. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  9. 2017Train longer, generalize better: closing the generalization gap in large batch training of neural networkscited by 278
  10. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  11. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  12. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
23 more
  1. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  2. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  3. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  4. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  5. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  6. 2020Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimizationcited by 51
  7. 2019How does Early Stopping Help Generalization against Label Noise?cited by 41
  8. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  9. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
  10. 2020Improving Generalization by Controlling Label-Noise Information in Neural Network Weightscited by 35
  11. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  12. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  13. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  14. 2021SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochscited by 22
  15. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  16. 2019Fast-rate PAC-Bayes Generalization Bounds via Shifted Rademacher Processescited by 20
  17. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  18. 2021Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regressioncited by 17
  19. 2017Exponential convergence of testing error for stochastic gradient methodscited by 13
  20. 2022Dimension Independent Generalization of DP-SGD for Overparameterized Smooth Convex Optimizationcited by 9
  21. 2022Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergencecited by 6
  22. 2021Towards Understanding Generalization via Decomposing Excess Risk Dynamicscited by 5
  23. 2016On the Exponentially Weighted Aggregate with the Laplace Priorcited by 3

Built on by

Cited by year (2026 to 7 Oct)

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

6 papers.

  1. 2023Fantastic Generalization Measures are Nowhere to be Foundcited by 19
  2. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 10
  3. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  4. 2023Towards Understanding Generalization and Stability Gaps between Centralized and Decentralized Federated Learningcited by 3
  5. 2024Which Algorithms Have Tight Generalization Bounds?cited by 1
  6. 2026All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimensioncited by 0