Efficient approaches for escaping higher order saddle points in non-convex optimization

By Anima Anandkumar, Rong Ge. 2016

142 citations recorded by the source corpus.

Local search heuristics for non-convex optimizations are popular in applied machine learning. However, in general it is hard to guarantee that such algorithms even converge to a local minimum, due to the existence of complicated saddle point structures in high dimensions. Many functions have degenerate saddle points such that the first and second order derivatives cannot distinguish them with local optima. In this paper we use higher order derivatives to escape these saddle points: we design the first efficient algorithm guaranteed to converge to a third order local optimum (while existing techniques are at most second order). We also show that it is NP-hard to extend this further to finding fourth order local optima.

Subfields: Artificial Intelligence, Computational Mechanics

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

Citations in the corpus

Entropy-SGD: biasing gradient descent into wide valleys (2016, background): “…good generalization error, however, is challenging: complex architectures are sensitive to initial conditions and learning rates (Sutskever et al., 2013) and even linear networks (Kawaguchi, 2016) may have degenerate and hard to escape saddle points (Ge et al., 2015; Anandkumar & Ge, 2016).”
Stochastic Gradient Descent Performs Variational Inference, Converges to Limit Cycles for Deep Networks (2017, background): “SGD and noise: Noise is often added in SGD to improve its behavior around saddle points for non-convex losses, see Lee et al. (2016); Anandkumar and Ge (2016); Ge et al. (2015).”
Accelerated Methods for Non-Convex Optimization (2016, background): “Anandkumar and Ge [4] extend these ideas, showing how to find a point that approximately satisfies the thirdorder necessary conditions for local optimality in polynomial time.”
Gradient Descent Only Converges to Minimizers (2016, background): “In concurrent work, Anandkumar and Ge (2016) have proposed an algorithm to avoid third-order saddles.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Such and higher-order saddle points are harder to escape; we refer interested readers to [142] for more discussions.”
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (2017, background): “Although this fact introduces challenges to the analysis, we show that its non-asymptotic efﬁciency can be characterized by a positive quantity called the restricted Cheeger constant .”
Deep convolutional neural networks for brain image analysis on magnetic resonance imaging: a review (2017, background): “Recent works have also been proposed to escape saddle points during the optimisation process [91, 92].”
Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learning (2020, result): “For extremely ICLBs (μ→ 0 or μ = 0), the above analysis does not hold which accords with the previous results that first-order gradient algorithms cannot escape from them provably [50].”
On Interpretability of Artificial Neural Networks: A Survey (2020, methodology): “…and describe key methods with our insights; 2) we systematically illustrate interpretability methods as educational aids, as shown in Figures 3, 5, 6, 7, 9, 10, 16, 17; and 3) we shed light on future directions of interpretability research in terms of the convergence of neural networks and…”
Non-convex Optimization for Machine Learning (2017, background): “For such cases, even finding locally optimal solutions is an NP-hard problem [Anandkumar and Ge, 2016].”
Skip Connections Eliminate Singularities (2017, background): “The Hessian of the loss function becomes singular at these singularities (Supplementary Note 1), hence they are sometimes also called degenerate or higher-order saddles (Anandkumar & Ge, 2016).”