  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.
