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

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 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 the rate ${\epsilon }^{-1}\log \frac{1}{\epsilon }$, showing that finding stationary points is easier given convexity.