A Generic Approach for Escaping Saddle points

By Sashank J. Reddi, Manzil Zaheer, Suvrit Sra, Barnab'as P'oczos, Francis R. Bach, Ruslan Salakhutdinov, Alex Smola. 2017

87 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

The Hidden Vulnerability of Distributed Learning in Byzantium (2018, methodology): “, 2015b), especially when we stick to such a cheap, first– order method as SGD, and avoid expensive, Hessian–like, computations as pointed out by (Reddi et al., 2017).”
Adaptive Methods for Nonconvex Optimization (2018, background): “Recently, several first-order and second-order methods have been proposed that are guaranteed to converge to local minima under certain conditions [1, 4, 14, 28].”
On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization (2018, methodology): “But, there is a subtle difference between classical momentum methods and their implementation in practice – classical momentum methods work in the exact ﬁrst order oracle model (Nesterov, 2004), i.e., they employ exact gradients (computed on the full training dataset), while in practice (Sutskever e”
ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning (2020, methodology): “For example, theoretically it has been shown that some ﬁrst order methods can only converge to an approximate second order critical point [19, 23, 26, 40].”
Learning to Predict Gradients for Semi-Supervised Continual Learning (2022, background): “In a similar manner, several first-and second-order methods are devised to guarantee convergence to local minima under certain conditions [48]–[50].”
Escaping Saddles with Stochastic Gradients (2018, methodology): “This is applied e.g. using matrix-free Lanczos iterations (Curtis & Robinson, 2017; Reddi et al., 2017) or online variants such as Oja’s algorithm (Allen-Zhu, 2017).”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, background): “In comparison, to the best of our knowledge the best-known results only achieve a gradient cost of O( −3.5) under similar assumptions (Reddi et al., 2018; Tripuraneni et al., 2018; Allen-Zhu, 2018; Allen-Zhu & Li, 2018; Zhou et al., 2018a).”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, methodology): “[20] developed a stochastic algorithm for solving a finite-sum problem by using SVRG and a second-order stochastic algorithm for computing the NC.”
Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization (2018, methodology): “, 2000), cubic regularized Newton’s method (Nesterov & Polyak, 2006), and a hybrid of first-order and second-order methods (Reddi et al., 2017).”
Escaping Saddle Points with Adaptive Gradient Methods (2019, methodology): “Thus Reddi et al. [2018b] break Adam by making estimation of E[g2] harder.”
Neon2: Finding Local Minima via First-Order Oracles (2017, background): “[25], but we do not need Hessian-vector product computations.”