Back to Search
Start Over
Lower bounds for finding stationary points II: first-order methods
- Source :
- Mathematical Programming. 185:315-355
- Publication Year :
- 2019
- Publisher :
- Springer Science and Business Media LLC, 2019.
-
Abstract
- We establish lower bounds on the complexity of finding $$\epsilon $$ -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 $$\epsilon $$ better than $$\epsilon ^{-8/5}$$ , which is within $$\epsilon ^{-1/15}\log \frac{1}{\epsilon }$$ of the best known rate for such methods. Moreover, for functions with Lipschitz first and second derivatives, we prove that no deterministic first-order method can achieve convergence rates better than $$\epsilon ^{-12/7}$$ , while $$\epsilon ^{-2}$$ is a lower bound for functions with only Lipschitz gradient. For convex functions with Lipschitz gradient, accelerated gradient descent achieves a better rate, showing that finding stationary points is easier given convexity.
- Subjects :
- 021103 operations research
Information-based complexity
General Mathematics
0211 other engineering and technologies
010103 numerical & computational mathematics
02 engineering and technology
Lipschitz continuity
01 natural sciences
Upper and lower bounds
Stationary point
Convexity
Combinatorics
Optimization and Control (math.OC)
FOS: Mathematics
0101 mathematics
Gradient descent
Convex function
Mathematics - Optimization and Control
Software
Second derivative
Mathematics
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 185
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....02b352866c6c3e0c7fac5c8397e6de1d