Escape saddle points by a simple gradient-descent based algorithm
This addresses a central challenge in nonconvex optimization for machine learning and AI, offering improved efficiency in training deep networks, though it is incremental with specific algorithmic enhancements.
The paper tackles the problem of escaping saddle points in nonconvex optimization by proposing a simple gradient-based algorithm that outputs an ε-approximate second-order stationary point in Õ(log n/ε^1.75) iterations, achieving polynomial speedup in log n compared to prior state-of-the-art methods.
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 $f\colon\mathbb{R}^n\to\mathbb{R}$, it outputs an $ε$-approximate second-order stationary point in $\tilde{O}(\log n/ε^{1.75})$ iterations. Compared to the previous state-of-the-art algorithms by Jin et al. with $\tilde{O}((\log n)^{4}/ε^{2})$ or $\tilde{O}((\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 $\tilde{O}((\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.