A Simple AGD for General Non-problems under the Lipschitz and Hessian Lipschitz Assumptions

Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the $O(ε^{-7/4})$ Complexity

This paper studies the accelerated gradient descent for general nonconvex problems under the gradient lipschitz and hessian lipschitz assumptions.

We establish that a simple restarted accelerated gradient descent (agd) finds an first-order stationary point in gradient computations with simple proofs.

Our simple algorithm only consists of a classical agd and a restart mechanism, and it does not need the negative curvature exploitation or the optimization of regularized surrogatefunctions.

Our complexity does not hide any polylogarithmic factors, and thus it improves over the state-of-the-art one by the factor.