mlsanityData to 14 Oct 2026

Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition

arXiv 1308.6370 ↗First posted 29 Aug 2013math.OCcited by 54

Not on the map. Why?

Abstract (arXiv)

We consider optimizing a function smooth convex function f that is the average of a set of differentiable functions fi, under the assumption considered by Solodov [1998] and Tseng [1998] that the norm of each gradient fi' is bounded by a linear function of the norm of the average gradient f'. We show that under these assumptions the basic stochastic gradient method with a sufficiently-small constant step-size has an O(1/k) convergence rate, and has a linear convergence rate if g is strongly-convex.

Key facts. Cited by 54 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 Aug 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 12; 2022: 4; 2023: 12; 2024: 8; 2025: 8; 2026: 10.

54 papers.

Sort:

By area:

  1. 2022Adam Can Converge Without Any Modification On Update Rulescited by 114
  2. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  3. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 42
  4. 2022Provable Adaptivity of Adam under Non-uniform Smoothnesscited by 30
  5. 2021Implicit Gradient Alignment in Distributed and Federated Learningcited by 29
  6. 2023Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index modelscited by 26
  7. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
  8. 2021Does Momentum Change the Implicit Regularization on Separable Data?cited by 22
  9. 2021Communication-efficient SGD: From Local SGD to One-Shot Averagingcited by 19
  10. 2021Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descentcited by 16
  11. 2023Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Modelscited by 15
  12. 2021SVRG Meets AdaGrad: Painless Variance Reductioncited by 13
38 more
  1. 2024Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performancecited by 13
  2. 2023Convergence and concentration properties of constant step-size SGD through Markov chainscited by 11
  3. 2021An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learningcited by 10
  4. 2021A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functionscited by 10
  5. 2022Nesterov Accelerated Shuffling Gradient Method for Convex Optimizationcited by 10
  6. 2023Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?cited by 10
  7. 2024Stochastic Gradient Succeeds for Banditscited by 10
  8. 2025ODE approximation for the Adam algorithm: General and overparametrized settingcited by 10
  9. 2021Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functionscited by 9
  10. 2023Maestro: Uncovering Low-Rank Structures via Trainable Decompositioncited by 8
  11. 2023Adaptive Federated Learning with Auto-Tuned Clientscited by 7
  12. 2024Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPscited by 7
  13. 2023Practical and Matching Gradient Variance Bounds for Black-Box Variational Bayesian Inferencecited by 6
  14. 2021Off-Policy Actor-Critic with Emphatic Weightingscited by 5
  15. 2024Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computationscited by 5
  16. 2023Target-based Surrogates for Stochastic Optimizationcited by 4
  17. 2025On the Interaction of Batch Noise, Adaptivity, and Compression, under (L0,L1)-Smoothness: An SDE Approachcited by 4
  18. 2023Fast Convergence in Learning Two-Layer Neural Networks with Separable Datacited by 3
  19. 2025Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Fastercited by 3
  20. 2025Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participationcited by 3
  21. 2022On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithmscited by 2
  22. 2024Demystifying SGD with Doubly Stochastic Gradientscited by 2
  23. 2024Convergence Conditions for Stochastic Line Search Based Optimization of Over-parametrized Modelscited by 2
  24. 2025Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysiscited by 2
  25. 2023Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Conditioncited by 1
  26. 2024Incremental Gauss-Newton Descent for Machine Learningcited by 1
  27. 2025Nearly Dimension-Independent Convergence of Mean-Field Black-Box Variational Inferencecited by 1
  28. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 1
  29. 2026mathsfVISTA: Decentralized Machine Learning in Adversary Dominated Environmentscited by 1
  30. 2021Adaptive Learning Rate and Momentum for Training Deep Neural Networkscited by 0
  31. 2023Unified analysis of SGD-type methodscited by 0
  32. 2024Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolationcited by 0
  33. 2025Convergence Analysis of SGD under Expected Smoothnesscited by 0
  34. 2025Adaptive SGD with Line-Search and Polyak Stepsizes: Nonconvex Convergence and Accelerated Ratescited by 0
  35. 2026Sample-wise Constrained Learning via a Sequential Penalty Approach with Applications in Image Processingcited by 0
  36. 2026Stochastic Gradient Variational Inference with Price's Gradient Estimator from Bures-Wasserstein to Parameter Spacecited by 0
  37. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0
  38. 2026Stochastic Trust-Region Methods for Over-parameterized Modelscited by 0

50 most cited of 54 All 54 (JSON)