First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time

Abstract

Two classes of methods have been proposed for escaping from saddle points with one using the second-order information carried by the Hessian and the other adding the noise into the first-order information. The existing analysis for algorithms using noise in the first-order information is quite involved and hides the essence of added noise, which hinder further improvements of these algorithms. In this paper, we present a novel perspective of noise-adding technique, i.e., adding the noise into the first-order information can help extract the negative curvature from the Hessian matrix, and provide a formal reasoning of this perspective by analyzing a simple first-order procedure. More importantly, the proposed procedure enables one to design purely first-order stochastic algorithms for escaping from non-degenerate saddle points with a much better time complexity (almost linear time in terms of the problem's dimensionality). In particular, we develop a {\bf first-order stochastic algorithm} based on our new technique and an existing algorithm that only converges to a first-order stationary point to enjoy a time complexity of {$\tilde{O}(d/{\epsilon }^{3.5})$ for finding a nearly second-order stationary point $\mathbf{x}$ such that $\Vert \nabla F(bfx)\Vert \le \epsilon$ and ${\nabla }^{2}F(bfx)\ge -\sqrt{\epsilon }I$ (in high probability), where $F(\cdot )$ denotes the objective function and $d$ is the dimensionality of the problem. To the best of our knowledge, this is the best theoretical result of first-order algorithms for stochastic non-convex optimization, which is even competitive with if not better than existing stochastic algorithms hinging on the second-order information.

40 pages; updated some proofs, included some new results

References in corpus (7)

• How to Escape Saddle Points Efficiently
• The Power of Normalization: Faster Evasion of Saddle Points
• Accelerated Methods for Non-Convex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• A Generic Approach for Escaping Saddle points
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
• Stochastic Non-convex Optimization with Strong High Probability Second-order Convergence

Cited by in corpus (11)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Escaping Saddles with Stochastic Gradients
• Finding Local Minima via Stochastic Nested Variance Reduction
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
• Memory Augmented Optimizers for Deep Learning
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience