Faster Perturbed Stochastic Gradient Methods for Finding Local Minima

Abstract

Escaping from saddle points and finding local minimum is a central problem in nonconvex optimization. Perturbed gradient methods are perhaps the simplest approach for this problem. However, to find $(\epsilon ,\sqrt{\epsilon })$-approximate local minima, the existing best stochastic gradient complexity for this type of algorithms is $\tilde{O}({\epsilon }^{-3.5})$, which is not optimal. In this paper, we propose LENA (Last stEp shriNkAge), a faster perturbed stochastic gradient framework for finding local minima. We show that LENA with stochastic gradient estimators such as SARAH/SPIDER and STORM can find $(\epsilon ,{\epsilon }_H)$-approximate local minima within $\tilde{O}({\epsilon }^{-3}+{\epsilon }_H^{-6})$ stochastic gradient evaluations (or $\tilde{O}({\epsilon }^{-3})$ when ${\epsilon }_H=\sqrt{\epsilon }$). The core idea of our framework is a step-size shrinkage scheme to control the average movement of the iterates, which leads to faster convergence to the local minima.

arXiv comment29 pages, 1 figure, 1 table. In ALT 2022

References in corpus (9)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Escaping Saddles with Stochastic Gradients
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Neon2: Finding Local Minima via First-Order Oracles
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization