mlsanityData to 7 Oct 2026

Lower Bounds for Finding Stationary Points II: First-Order Methods

arXiv 1711.00841 ↗First posted 2 Nov 2017math.OCcited by 55

Not on the map. Why?

Abstract (arXiv)

We establish lower bounds on the complexity of finding ε-stationary points of smooth, non-convex high-dimensional functions using first-order methods. We prove that deterministic first-order methods, even applied to arbitrarily smooth functions, cannot achieve convergence rates in ε better than ε-8/5, which is within ε-1/15logfrac1ε of the best known rate for such methods. Moreover, for functions with Lipschitz first and second derivatives, we prove no deterministic first-order method can achieve convergence rates better than ε-12/7, while ε-2 is a lower bound for functions with only Lipschitz gradient. For convex functions with Lipschitz gradient, accelerated gradient descent achieves the rate ε-1logfrac1ε, showing that finding stationary points is easier given convexity.

Key facts. Cited by 55 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Nov 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 9; 2023: 15; 2024: 6; 2025: 9; 2026: 9.

55 papers.

Sort:

By area:

  1. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  2. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  3. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  4. 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
  5. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  6. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 34
  7. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  8. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  9. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 25
  10. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  11. 2022Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimizationcited by 22
  12. 2021On the Periodic Behavior of Neural Network Training with Batch Normalization and Weight Decaycited by 20
38 more
  1. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  2. 2023A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimizationcited by 16
  3. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  4. 2023Accelerating Inexact HyperGradient Descent for Bilevel Optimizationcited by 15
  5. 2023Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?cited by 14
  6. 2023How to escape sharp minima with random perturbationscited by 13
  7. 2024Tuning-Free Stochastic Optimizationcited by 13
  8. 2022Fisher information lower bounds for samplingcited by 12
  9. 2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
  10. 2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
  11. 2023Accelerating Value Iteration with Anchoringcited by 10
  12. 2022On the Complexity of Finding Small Subgradients in Nonsmooth Optimizationcited by 7
  13. 2024Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methodscited by 7
  14. 2021Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sumscited by 4
  15. 2022Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networkscited by 4
  16. 2024Non-Euclidean High-Order Smooth Convex Optimizationcited by 3
  17. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  18. 2025Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescited by 3
  19. 2022Resource-Efficient Invariant Networks: Exponential Gains by Unrolled Optimizationcited by 2
  20. 2022Gradient Descent for Low-Rank Functionscited by 2
  21. 2024Memory-Efficient 4-bit Preconditioned Stochastic Optimizationcited by 2
  22. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  23. 2026When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Boundscited by 2
  24. 2021On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimizationcited by 1
  25. 2023Beyond first-order methods for non-convex non-concave min-max optimizationcited by 1
  26. 2024Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspectivecited by 1
  27. 2025Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functionscited by 1
  28. 2025Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimizationcited by 1
  29. 2025Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learningcited by 1
  30. 2026Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with k-step Policy Gradientscited by 1
  31. 2023First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methodscited by 0
  32. 2023A Homogenization Approach for Gradient-Dominated Stochastic Optimizationcited by 0
  33. 2024Accelerated Fully First-Order Methods for Bilevel and Minimax Optimizationcited by 0
  34. 2025A Novel Unified Parametric Assumption for Nonconvex Optimizationcited by 0
  35. 2025Observability conditions for neural state-space models with eigenvalues and their roots of unitycited by 0
  36. 2025Complexity Bounds for Smooth Multiobjective Optimizationcited by 0
  37. 2026On Approximate Computation of Critical Pointscited by 0
  38. 2026Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methodscited by 0

50 most cited of 55 All 55 (JSON)