A Note on Nesterov's Accelerated Method in Nonconvex Optimization: a Weak Estimate Sequence Approach

We present a variant of accelerated gradient descent algorithms, adapted from Nesterov's optimal first-order methods, for weakly-quasi-convex and weakly-quasi-strongly-convex functions. We show that by tweaking the so-called estimate sequence method, the derived algorithm achieves optimal convergence rate for weakly-quasi-convex and weakly-quasi-strongly-convex in terms of oracle complexity. In particular, for a weakly-quasi-convex function with Lipschitz continuous gradient, we require O(frac1√varepsilon) iterations to acquire an varepsilon-solution; for weakly-quasi-strongly-convex functions, the iteration complexity is Oleft( lnleft(frac1varepsilonright) right). Furthermore, we discuss the implications of these algorithms for linear quadratic optimal control problem.