mlsanityData to 14 Oct 2026

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD

arXiv 1801.02982 ↗First posted 8 Jan 2018cs.LG cs.DS math.OCcited by 57

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent (SGD) gives an optimal convergence rate when minimizing convex stochastic objectives f(x). However, in terms of making the gradients small, the original SGD does not give an optimal rate, even when f(x) is convex. If f(x) is convex, to find a point with gradient norm varepsilon, we design an algorithm SGD3 with a near-optimal rate tildeO(varepsilon-2), improving the best known rate O(varepsilon-8/3) of [18]. If f(x) is nonconvex, to find its varepsilon-approximate local minimum, we design an algorithm SGD5 with rate tildeO(varepsilon-3.5), where previously SGD variants only achieve tildeO(varepsilon-4) [6, 15, 33]. This is no slower than the best known stochastic version of Newton's method in all parameter regimes [30].

Key facts. Cited by 57 papers in the map (data through 14 Oct 2026). First posted on arXiv 8 Jan 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

57 papers.

Sort:

By area:

  1. 2021Machine Unlearning via Algorithmic Stabilitycited by 130
  2. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 45
  3. 2023Rethinking Semi-Supervised Medical Image Segmentation: A Variance-Reduction Perspectivecited by 43
  4. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  5. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
  6. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  7. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  8. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  9. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 26
  10. 2022Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimizationcited by 23
  11. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  12. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 17
38 more
  1. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 17
  2. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 17
  3. 2025Can SGD Handle Heavy-Tailed Noise?cited by 17
  4. 2021Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimatorcited by 13
  5. 2022Fisher information lower bounds for samplingcited by 12
  6. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 12
  7. 2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
  8. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  9. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  10. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  11. 2021Complementary Composite Minimization, Small Gradients in General Norms, and Applicationscited by 9
  12. 2022Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methodscited by 9
  13. 2024Non-convex Stochastic Composite Optimization with Polyak Momentumcited by 9
  14. 2022On the Complexity of Finding Small Subgradients in Nonsmooth Optimizationcited by 8
  15. 2023Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxycited by 7
  16. 2021Parameter-free Locally Accelerated Conditional Gradientscited by 5
  17. 2024Regression under demographic parity constraints via unlabeled post-processingcited by 5
  18. 2021Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimizationcited by 4
  19. 2021Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sumscited by 4
  20. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  21. 2023Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networkscited by 3
  22. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  23. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  24. 2022Tackling benign nonconvexity with smoothing and stochastic gradientscited by 2
  25. 2023DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regimecited by 2
  26. 2024Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometrycited by 2
  27. 2025Stochastic Optimization with Optimal Importance Samplingcited by 2
  28. 2026How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyondcited by 2
  29. 2024Faster Acceleration for Steepest Descentcited by 1
  30. 2025Are Convex Optimization Curves Convex?cited by 1
  31. 2025Distribution free M-estimationcited by 1
  32. 2025Efficient Public Verification of Private ML via Regularizationcited by 1
  33. 2025Randomized multi-class classification under system constraints: a unified approach via post-processingcited by 1
  34. 2026Finding Stationary Points by Comparisonscited by 1
  35. 2026Sample complexity of variance-reduced policy gradient: weaker assumptions and lower boundscited by 1
  36. 2021Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growthcited by 0
  37. 2023Oblivious Stochastic Composite Optimizationcited by 0
  38. 2023First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methodscited by 0

50 most cited of 57 All 57 (JSON)