mlsanityData to 7 Oct 2026

The Complexity of Finding Stationary Points with Stochastic Gradient Descent

arXiv 1910.01845 ↗First posted 4 Oct 2019cs.LG math.OC stat.MLcited by 34

Not on the map. Why?

Abstract (arXiv)

We study the iteration complexity of stochastic gradient descent (SGD) for minimizing the gradient norm of smooth, possibly nonconvex functions. We provide several results, implying that the O(ε-4) upper bound of Ghadimi and Lan~citeghadimi2013stochastic (for making the average gradient norm less than ε) cannot be improved upon, unless a combination of additional assumptions is made. Notably, this holds even if we limit ourselves to convex quadratic functions. We also show that for nonconvex functions, the feasibility of minimizing gradients with SGD is surprisingly sensitive to the choice of optimality criteria.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 3; 2023: 11; 2024: 6; 2025: 3; 2026: 4.

34 papers.

Sort:

By area:

  1. 2021STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learningcited by 43
  2. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  3. 2023Optimal Linear Decay Learning Rate Schedules and Further Refinementscited by 41
  4. 2021Proximal and Federated Random Reshufflingcited by 33
  5. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  6. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  7. 2024Robust Multi-Task Learning with Excess Riskscited by 23
  8. 2021On the Convergence of Step Decay Step-Size for Stochastic Optimizationcited by 21
  9. 2021Random Reshuffling with Variance Reduction: New Analysis and Better Ratescited by 19
  10. 2024ADOPT: Modified Adam Can Converge with Any β2 with the Optimal Ratecited by 18
  11. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  12. 2023Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approachcited by 14
22 more
  1. 2023How to escape sharp minima with random perturbationscited by 13
  2. 2023Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimizationcited by 11
  3. 2023Accelerating Value Iteration with Anchoringcited by 10
  4. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
  5. 2023Quasi-optimal Reinforcement Learning with Continuous Actionscited by 7
  6. 2021Frequency-aware SGD for Efficient Embedding Learning with Provable Benefitscited by 6
  7. 2024Generalizing Reward Modeling for Out-of-Distribution Preference Learningcited by 6
  8. 2025Efficient Utility-Preserving Machine Unlearning with Implicit Gradient Surgerycited by 5
  9. 2022A simplified convergence theory for Byzantine resilient stochastic gradient descentcited by 3
  10. 2024Quantized and Asynchronous Federated Learningcited by 3
  11. 2021Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimizationcited by 2
  12. 2021Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimizationcited by 2
  13. 2025Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shufflingcited by 2
  14. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 2
  15. 2026When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Boundscited by 2
  16. 2022Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysiscited by 1
  17. 2023Over-the-Air Federated Averaging with Limited Power and Privacy Budgetscited by 1
  18. 2024Momentum-Based Federated Reinforcement Learning with Interaction and Communication Efficiencycited by 1
  19. 2023Locally Optimal Descent for Dynamic Stepsize Schedulingcited by 0
  20. 2024OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterationscited by 0
  21. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 0
  22. 2026The Row Normalization Puzzle in Muoncited by 0