  This paper studies accelerated gradient methods for nonconvex optimization
with Lipschitz continuous gradient and Hessian. We propose two simple
accelerated gradient methods, restarted accelerated gradient descent (AGD) and
restarted heavy ball (HB) method, and establish that our methods achieve an
$\epsilon$-approximate first-order stationary point within $O(\epsilon^{-7/4})$
number of gradient evaluations by elementary proofs. Theoretically, our
complexity does not hide any polylogarithmic factors, and thus it improves over
the best known one by the $O(\log\frac{1}{\epsilon})$ factor. Our algorithms
are simple in the sense that they only consist of Nesterov's classical AGD or
Polyak's HB iterations, as well as a restart mechanism. They do not invoke
negative curvature exploitation or minimization of regularized surrogate
functions as the subroutines. In contrast with existing analysis, our
elementary proofs use less advanced techniques and do not invoke the analysis
of strongly convex AGD or HB.
  Code is avaliable at https://github.com/lihuanML/RestartAGD.
