mlsanityData to 14 Oct 2026

Lower Bounds for Finding Stationary Points I

arXiv 1710.11606 ↗First posted 31 Oct 2017math.OCcited by 126

Not on the map. Why?

Abstract (arXiv)

We prove lower bounds on the complexity of finding ε-stationary points (points x such that |nabla f(x)| ≤ ε) of smooth, high-dimensional, and potentially non-convex functions f. We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives of f at a query point x. We show that for any (potentially randomized) algorithm mathsfA, there exists a function f with Lipschitz pth order derivatives such that mathsfA requires at least ε-(p+1)/p queries to find an ε-stationary point. Our lower bounds are sharp to within constants, and they show that gradient descent, cubic-regularized Newton's method, and generalized pth order regularization are worst-case optimal within their natural function classes.

Key facts. Cited by 126 papers in the map (data through 14 Oct 2026). First posted on arXiv 31 Oct 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 21; 2022: 13; 2023: 25; 2024: 19; 2025: 17; 2026: 31.

126 papers.

Sort:

By area:

  1. 2025Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimizationcited by 92
  2. 2022A Closer Look at Smoothness in Domain Adversarial Trainingcited by 85
  3. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 78
  4. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 63
  5. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
  6. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
  7. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  8. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 45
  9. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  10. 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
  11. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  12. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
38 more
  1. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 36
  2. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  3. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  4. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  5. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  6. 2025Beyond the Ideal: Analyzing the Inexact Muon Updatecited by 27
  7. 2021A Stochastic Optimization Framework for Fair Risk Minimizationcited by 26
  8. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 26
  9. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 24
  10. 2022Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimizationcited by 23
  11. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  12. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 23
  13. 2025AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updatescited by 23
  14. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 19
  15. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  16. 2025Low-rank Orthogonalization for Large-scale Matrix Optimization with Applications to Foundation Model Trainingcited by 18
  17. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  18. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  19. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 17
  20. 2023A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimizationcited by 16
  21. 2021Neural Network Weights Do Not Converge to Stationary Points: An Invariant Measure Perspectivecited by 15
  22. 2023Accelerating Inexact HyperGradient Descent for Bilevel Optimizationcited by 15
  23. 2021Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimizationcited by 14
  24. 2021Variance Reduced Training with Stratified Sampling for Forecasting Modelscited by 14
  25. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
  26. 2023Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifoldcited by 14
  27. 2023Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?cited by 14
  28. 2023Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approachcited by 14
  29. 2026Adam Improves Muon: Adaptive Moment Estimation with Orthogonalized Momentumcited by 14
  30. 2023How to escape sharp minima with random perturbationscited by 13
  31. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  32. 2022Fisher information lower bounds for samplingcited by 12
  33. 2023Gradient-free optimization of highly smooth functions: improved analysis and a new algorithmcited by 12
  34. 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
  35. 2025SGD with Adaptive Preconditioning: Unified Analysis and Momentum Accelerationcited by 12
  36. 2021FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learningcited by 11
  37. 2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
  38. 2023Accelerating Value Iteration with Anchoringcited by 11

50 most cited of 126 All 126 (JSON)