Escape saddle points by a simple gradient-descent based algorithm

Escaping saddle points is a central research topic in nonconvex optimization. In this paper, we propose a simple gradient-based algorithm such that for a smooth function fcolonℝn→ℝ, it outputs an ε-approximate second-order stationary point in tildeO(log n/ε1.75) iterations. Compared to the previous state-of-the-art algorithms by Jin et al. with tildeO((log n)4/ε2) or tildeO((log n)6/ε1.75) iterations, our algorithm is polynomially better in terms of log n and matches their complexities in terms of 1/ε. For the stochastic setting, our algorithm outputs an ε-approximate second-order stationary point in tildeO((log n)2/ε4) iterations. Technically, our main contribution is an idea of implementing a robust Hessian power method using only gradients, which can find negative curvature near saddle points and achieve the polynomial speedup in log n compared to the perturbed gradient descent methods. Finally, we also perform numerical experiments that support our results.