mlsanityData to 7 Oct 2026

Unified analysis of SGD-type methods

arXiv 2303.16502 ↗First posted 29 Mar 2023math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

This note focuses on a simple approach to the unified analysis of SGD-type methods from (Gorbunov et al., 2020) for strongly convex smooth optimization problems. The similarities in the analyses of different stochastic first-order methods are discussed along with the existing extensions of the framework. The limitations of the analysis and several alternative approaches are mentioned as well.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 53 of its 77 references that are in the map. First posted on arXiv 29 Mar 2023.

Builds on

53 of 77 references.

References · 53

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  4. 2018Sparsified SGD with Memorycited by 373
  5. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  6. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  7. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  8. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  9. 2019SGD: General Analysis and Improved Ratescited by 206
  10. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  11. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  12. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
38 more
  1. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  2. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  3. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  4. 2020On Biased Compression for Distributed Learningcited by 140
  5. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  6. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  7. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  8. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  9. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  10. 2020On the Convergence of SGD with Biased Gradientscited by 79
  11. 2020Variance-Reduced Methods for Machine Learningcited by 79
  12. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  13. 2020Linearly Converging Error Compensated SGDcited by 61
  14. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  15. 2018Distributed learning with compressed gradientscited by 53
  16. 2020A Better Alternative to Error Feedback for Communication-Efficient Distributed Learningcited by 42
  17. 2021Rethinking gradient sparsification as total error minimizationcited by 41
  18. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
  19. 2021Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothnesscited by 37
  20. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  21. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  22. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  23. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  24. 2020Recent Theoretical Advances in Non-Convex Optimizationcited by 30
  25. 2020A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimizationcited by 27
  26. 20223PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregationcited by 27
  27. 2016A Simple Practical Accelerated Method for Finite Sumscited by 18
  28. 2022EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimizationcited by 17
  29. 2019L-SVRG and L-Katyusha with Arbitrary Samplingcited by 14
  30. 2021MURANA: A Generic Framework for Stochastic Variance-Reduced Optimizationcited by 13
  31. 2019Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functionscited by 12
  32. 2022Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topologycited by 10
  33. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  34. 2019Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noisecited by 9
  35. 2019One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methodscited by 8
  36. 2022Shifted Compression Framework: Generalizations and Improvementscited by 6
  37. 2020Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithmscited by 5
  38. 2019A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functionscited by 4

50 most cited of 53 All 53 (JSON)

Built on by

Not cited yet.