mlsanityData to 7 Oct 2026

Unified Optimal Analysis of the (Stochastic) Gradient Method

arXiv 1907.04232 ↗First posted 9 Jul 2019cs.LG cs.NA math.NAcited by 81

Not on the map. Why?

Abstract (arXiv)

In this note we give a simple proof for the convergence of stochastic gradient (SGD) methods on μ-convex functions under a (milder than standard) L-smoothness assumption. We show that for carefully chosen stepsizes SGD converges after T iterations as Oleft( LR2 exp bigl[-fracμ4LTbigr] + fracσ2μ T right) where σ2 measures the variance in the stochastic noise. For deterministic gradient descent (GD) and SGD in the interpolation setting we have σ2 =0 and we recover the exponential convergence rate. The bound matches with the best known iteration complexity of GD and SGD, up to constants.

Key facts. Cited by 81 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Jul 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 21; 2022: 14; 2023: 14; 2024: 14; 2025: 9; 2026: 9.

81 papers.

Sort:

By area:

  1. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  2. 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 68
  3. 2021Distributed Deep Learning in Open Collaborationscited by 58
  4. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  5. 2021Consensus Control for Decentralized Deep Learningcited by 49
  6. 2021RelaySum for Decentralized Deep Learning on Heterogeneous Datacited by 39
  7. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 38
  8. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  9. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
  10. 2021Proximal and Federated Random Reshufflingcited by 33
  11. 2021Local Adaptivity in Federated Learning: Convergence and Consistencycited by 31
  12. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
38 more
  1. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  2. 2023Provable convergence guarantees for black-box variational inferencecited by 29
  3. 2021Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGDcited by 28
  4. 2021A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularizationcited by 27
  5. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  6. 2023Improving Convergence and Generalization Using Parameter Symmetriescited by 23
  7. 2022Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problemscited by 21
  8. 2021Robust Training in High Dimensions via Block Coordinate Geometric Median Descentcited by 20
  9. 2021Stochastic Polyak Stepsize with a Moving Targetcited by 19
  10. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19
  11. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  12. 2021Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descentcited by 16
  13. 2022FedSkip: Combatting Statistical Heterogeneity with Federated Skip Aggregationcited by 16
  14. 2021Masked Training of Neural Networks with Partial Gradientscited by 15
  15. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  16. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  17. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  18. 2024Federated Learning with Bilateral Curation for Partially Class-Disjoint Datacited by 13
  19. 2023DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updatescited by 12
  20. 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
  21. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  22. 2021An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learningcited by 10
  23. 2021Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizescited by 9
  24. 2022Mixed Federated Learning: Joint Decentralized and Centralized Learningcited by 8
  25. 2022On the effectiveness of partial variance reduction in federated learning with heterogeneous datacited by 8
  26. 2021Random-reshuffled SARAH does not need a full gradient computationscited by 7
  27. 2023A2CiD2: Accelerating Asynchronous Communication in Decentralized Deep Learningcited by 7
  28. 2023Locally Adaptive Federated Learningcited by 7
  29. 2021The Minimax Complexity of Distributed Optimizationcited by 6
  30. 2023Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Featurescited by 6
  31. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  32. 2024Towards Exact Gradient-based Training on Analog In-memory Computingcited by 6
  33. 2024Towards Efficient Risk-Sensitive Policy Gradient: An Iteration Complexity Analysiscited by 5
  34. 2023On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approachcited by 4
  35. 2024Provably Scalable Black-Box Variational Inference with Structured Variational Familiescited by 4
  36. 2024Communication-Efficient Adaptive Batch Size Strategies for Distributed Local Gradient Methodscited by 4
  37. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  38. 2023Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networkscited by 3

50 most cited of 81 All 81 (JSON)