mlsanityData to 7 Oct 2026

Improved Learning Rates for Stochastic Optimization

arXiv 2107.08686 ↗First posted 19 Jul 2021cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

Stochastic optimization is a cornerstone of modern machine learning. This paper studies the generalization performance of two classical stochastic optimization algorithms: stochastic gradient descent (SGD) and Nesterov's accelerated gradient (NAG). We establish new learning rates for both algorithms, with improved guarantees in some settings or comparable rates under weaker assumptions in others. We also provide numerical experiments to support the theory.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 34 of its 64 references that are in the map. First posted on arXiv 19 Jul 2021.

Builds on

34 of 64 references.

References · 34

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  5. 2015Coordinate Descent Algorithmscited by 218
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  7. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  8. 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
  9. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  10. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  11. 2019Sharper bounds for uniformly stable algorithmscited by 91
  12. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
22 more
  1. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  2. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  3. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  4. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  5. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  6. 2018Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regressioncited by 42
  7. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  8. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 41
  9. 2017Algorithmic stability and hypothesis complexitycited by 39
  10. 2019SGD Converges to Global Minimum in Deep Learning via Star-convex Pathcited by 39
  11. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  12. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  13. 2013On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functionscited by 23
  14. 2019Hypothesis Set Stability and Generalizationcited by 23
  15. 2021Distribution-Free Robust Linear Regressioncited by 19
  16. 2018Graphical Convergence of Subgradients in Nonconvex Optimization and Learningcited by 17
  17. 2021Algorithmic Instabilities of Accelerated Gradient Descentcited by 16
  18. 2017Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Boundscited by 15
  19. 2019Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Ratecited by 14
  20. 2015Unregularized Online Learning Algorithms with General Loss Functionscited by 11
  21. 2020Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictorscited by 9
  22. 2016Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimizationcited by 6

Built on by

Not cited yet.