A Generic Approach for Escaping Saddle points

Abstract

A central challenge to using first-order methods for optimizing nonconvex problems is the presence of saddle points. First-order methods often get stuck at saddle points, greatly deteriorating their performance. Typically, to escape from saddles one has to use second-order methods. However, most works on second-order methods rely extensively on expensive Hessian-based computations, making them impractical in large-scale settings. To tackle this challenge, we introduce a generic framework that minimizes Hessian based computations while at the same time provably converging to second-order critical points. Our framework carefully alternates between a first-order and a second-order subroutine, using the latter only close to saddle points, and yields convergence results competitive to the state-of-the-art. Empirical results suggest that our strategy also enjoys a good practical performance.

Cited by in corpus (19)

• The Hidden Vulnerability of Distributed Learning in Byzantium
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Adaptive Federated Optimization
• Escaping Saddles with Stochastic Gradients
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Hybrid Precoding For Millimeter Wave MIMO Systems: A Matrix Factorization Approach
• SGD Converges to Global Minimum in Deep Learning via Star-convex Path
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Finding Local Minima via Stochastic Nested Variance Reduction
• Inexact Newton Methods for Stochastic Nonconvex Optimization with Applications to Neural Network Training
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• Multi-Segment Reconstruction Using Invariant Features
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum