mlsanityData to 7 Oct 2026

Convex SGD: Generalization Without Early Stopping

arXiv 2401.04067 ↗First posted 8 Jan 2024cs.LG math.ST stat.THcited by 1

Not on the map. Why?

Abstract (arXiv)

We consider the generalization error associated with stochastic gradient descent on a smooth convex function over a compact set. We show the first bound on the generalization error that vanishes when the number of iterations T and the dataset size n go to zero at arbitrary rates; our bound scales as tildeO(1/√T + 1/√n) with step-size αt = 1/√t. In particular, strong convexity is not needed for stochastic gradient descent to generalize well.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 24 of its 39 references that are in the map. First posted on arXiv 8 Jan 2024.

Builds on

24 of 39 references.

References · 24

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  2. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  3. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  4. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  5. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  6. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
  7. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  8. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  9. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  10. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
  11. 2023Generalization Bounds: Perspectives from Information Theory and PAC-Bayescited by 60
  12. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
12 more
  1. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 41
  2. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  3. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  4. 2017A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descentcited by 29
  5. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  6. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  7. 2022Generalization Bounds via Convex Analysiscited by 27
  8. 2016Generalization Properties and Implicit Regularization for Multiple Passes SGMcited by 16
  9. 2022Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Coverscited by 11
  10. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  11. 2023The Sample Complexity Of ERMs In Stochastic Convex Optimizationcited by 8
  12. 2022Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithmscited by 3

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Generalization Error Matters in Decentralized Learning Under Byzantine Attackscited by 4