Timezone: »

 
Spotlight
Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the $O(\epsilon^{-7/4})$ Complexity
Huan Li · Zhouchen Lin

Tue Jul 19 01:25 PM -- 01:30 PM (PDT) @ Room 309
in OPT: Non-Convex »
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 $\epsilon$-approximate first-order stationary point in $O(\epsilon^{-7/4})$ gradient computations with simple proofs. Our complexity does not hide any polylogarithmic factors, and thus it improves over the state-of-the-art one by the $O(\log\frac{1}{\epsilon})$ factor. Our simple algorithm only consists of Nesterov's classical AGD and a restart mechanism, and it does not need the negative curvature exploitation or the optimization of regularized surrogate functions. Technically, our simple proof does not invoke the analysis for the strongly convex AGD, which is crucial to remove the $O(\log\frac{1}{\epsilon})$ factor.
Keywords: OPT: First-order · OPT: Non-Convex

Author Information

Huan Li (Nankai University)
Zhouchen Lin (Peking University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors