Escape saddle points by a simple gradient-descent based algorithm

2021/11/28 by Zhang, Chenyi, Li, Tongyang
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2111.14069

Abstract

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ℝⁿ→ℝ, it outputs an ε-approximate second-order stationary point in O(log n/ε^1.75) iterations. Compared to the previous state-of-the-art algorithms by Jin et al. with O((log n)⁴/ε²) or O((log n)⁶/ε^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 O((log n)²/ε⁴) 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.

Related

• Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• How to Escape Saddle Points Efficiently
• A Newton-Based Method for Nonconvex Optimization with Fast Evasion of\n Saddle Points
• Escaping Saddle Points for Zeroth-order Nonconvex Optimization using Estimated Gradient Descent