mlsanityData to 14 Oct 2026

Lower Bounds for Non-Convex Stochastic Optimization

arXiv 1912.02365 ↗First posted 5 Dec 2019math.OC cs.IT cs.LGcited by 307

Not on the map. Why?

Abstract (arXiv)

We lower bound the complexity of finding ε-stationary points (with gradient norm at most ε) using stochastic first-order methods. In a well-studied model where algorithms access smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance, we prove that (in the worst case) any algorithm requires at least ε-4 queries to find an ε stationary point. The lower bound is tight, and establishes that stochastic gradient descent is minimax optimal in this model. In a more restrictive model where the noisy gradient estimates satisfy a mean-squared smoothness property, we prove a lower bound of ε-3 queries, establishing the optimality of recently proposed variance reduction techniques.

Key facts. Cited by 307 papers in the map (data through 14 Oct 2026). First posted on arXiv 5 Dec 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 33; 2022: 36; 2023: 49; 2024: 66; 2025: 53; 2026: 70.

307 papers.

Sort:

By area:

  1. 2025Training Deep Learning Models with Norm-Constrained LMOscited by 192
  2. 2022Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Modelscited by 174
  3. 2023Convergence of Adam Under Relaxed Assumptionscited by 99
  4. 2025Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimizationcited by 92
  5. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  6. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
  7. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 78
  8. 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
  9. 2021Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Datacited by 69
  10. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 63
  11. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 63
  12. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
38 more
  1. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
  2. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
  3. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 45
  4. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  5. 2022A Unified Analysis of Federated Learning with Arbitrary Client Participationcited by 45
  6. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  7. 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
  8. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  9. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  10. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  11. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 41
  12. 2021SUPER-ADAM: Faster and Universal Framework of Adaptive Gradientscited by 40
  13. 2021Non-convex Distributionally Robust Optimization: Non-asymptotic Analysiscited by 39
  14. 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
  15. 2023Momentum Benefits Non-IID Federated Learning Simply and Provablycited by 38
  16. 2023Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexitycited by 38
  17. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  18. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 36
  19. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 36
  20. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
  21. 2022Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimizationcited by 36
  22. 2021Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimizationcited by 33
  23. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  24. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  25. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  26. 2023Momentum Provably Improves Error Feedback!cited by 31
  27. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  28. 2025On the Convergence of Muon and Beyondcited by 31
  29. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  30. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  31. 2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
  32. 2025Beyond the Ideal: Analyzing the Inexact Muon Updatecited by 27
  33. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  34. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 26
  35. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 24
  36. 2022Convergence of gradient descent for deep neural networkscited by 24
  37. 2022Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimizationcited by 23
  38. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23

50 most cited of 307 All 307 (JSON)