Finding Local Minima via Stochastic Nested Variance Reduction

Abstract

We propose two algorithms that can find local minima faster than the state-of-the-art algorithms in both finite-sum and general stochastic nonconvex optimization. At the core of the proposed algorithms is ${\text{One-epoch-SNVRG}}^{+}$ using stochastic nested variance reduction (Zhou et al., 2018a), which outperforms the state-of-the-art variance reduction algorithms such as SCSG (Lei et al., 2017). In particular, for finite-sum optimization problems, the proposed ${\text{SNVRG}}^{+}+{\text{Neon2}}^{\text{finite}}$ algorithm achieves $\tilde{O}(n^{1/2}{\epsilon }^{-2}+n{\epsilon }_H^{-3}+n^{3/4}{\epsilon }_H^{-7/2})$ gradient complexity to converge to an $(\epsilon ,{\epsilon }_H)$-second-order stationary point, which outperforms $\text{SVRG}+{\text{Neon2}}^{\text{finite}}$ (Allen-Zhu and Li, 2017) , the best existing algorithm, in a wide regime. For general stochastic optimization problems, the proposed ${\text{SNVRG}}^{+}+{\text{Neon2}}^{\text{online}}$ achieves $\tilde{O}({\epsilon }^{-3}+{\epsilon }_H^{-5}+{\epsilon }^{-2}{\epsilon }_H^{-3})$ gradient complexity, which is better than both $\text{SVRG}+{\text{Neon2}}^{\text{online}}$ (Allen-Zhu and Li, 2017) and Natasha2 (Allen-Zhu, 2017) in certain regimes. Furthermore, we explore the acceleration brought by third-order smoothness of the objective function.

37 pages, 4 figures, 1 table

References in corpus (14)

• The Loss Surfaces of Multilayer Networks
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• How to Escape Saddle Points Efficiently
• Escaping Saddles with Stochastic Gradients
• The Power of Normalization: Faster Evasion of Saddle Points
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• Neon2: Finding Local Minima via First-Order Oracles
• Accelerated Methods for Non-Convex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• A Generic Approach for Escaping Saddle points
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima

Cited by in corpus (9)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient
• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• Escaping Saddle Points with Compressed SGD
• SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points