Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

By Yann Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, Yoshua Bengio. 2014

1,536 citations recorded by the source corpus.

A central challenge to many fields of science and engineering involves minimizing non-convex error functions over continuous, high dimensional spaces. Gradient descent or quasi-Newton methods are almost ubiquitously used to perform such minimizations, and it is often thought that a main source of difficulty for these local methods to find the global minimum is the proliferation of local minima with much higher error than the global minimum. Here we argue, based on results from statistical physics, random matrix theory, neural network theory, and empirical evidence, that a deeper and more profound difficulty originates from the proliferation of saddle points, not local minima, especially in high dimensional problems of practical interest. Such saddle points are surrounded by high error plateaus that can dramatically slow down learning, and give the illusory impression of the existence of a local minimum. Motivated by these arguments, we propose a new approach to second-order optimization, the saddle-free Newton method, that can rapidly escape high dimensional saddle points, unlike gradient descent and quasi-Newton methods. We apply this algorithm to deep or recurrent neural network training, and provide numerical evidence for its superior optimization performance.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

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 Optimization & Training

Citations in the corpus

Training Very Deep Networks (2015, background): “This enables the study of extremely deep and efficient architectures.”
FitNets: Hints for Thin Deep Nets (2014, background): “On the one hand, the proliferation of local minima and especially saddle points in highly non-linear functions such as very deep networks highlights the difﬁculty of ﬁnding a good starting point in the parameter space at random (Dauphin et al., 2014).”
Scaling description of generalization with number of parameters in deep learning (2019, background): “Numerical and theoretical studies [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17] show that in the overparametrized regime, the loss landscape of DNNs is not rough with isolated minima as initially thought [18, 19], but instead has connected level sets and presents many flat directions, even near its g”
Gradient Descent Happens in a Tiny Subspace (2018, methodology): “A second criticism of Newton’s method is that it does not strictly descend, but rather moves towards critical points, whether they are minima, maxima, or saddles (Pascanu et al., 2014; Dauphin et al., 2014).”
A Closer Look at the Optimization Landscapes of Generative Adversarial Networks (2019, methodology): “Another way to gain insight into the landscape of deep neural networks is by looking at the Hessian of the loss; this was done in the context of single objective minimization by (Dauphin et al., 2014; Sagun et al., 2016, 2017; Alain et al., 2019).”
Coulomb GANs: Provably Optimal Nash Equilibria via Potential Fields (2017, background): “Even though these are strong assumptions, recent research indicates that the effect of local minima in deep learning vanishes with increasing depth [9, 7, 25], while capacity increases with network size.”
f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization (2016, background): “Note that although there could be many saddle points that arise from the structure of deep networks [6], they do not qualify as the solution of our variational framework under these assumptions.”
Measuring the Intrinsic Dimension of Objective Landscapes (2018, background): “Dauphin et al. (2014) showed that, in contrast to conventional thinking about getting stuck in local optima (as one might be stuck in a valley in our familiar D = 2 ), local critical points in high dimension are almost never valleys but are instead saddlepoints: structures which are “valleys” along…”
The Loss Surfaces of Multilayer Networks (2014, background): “…much higher than the global minimum are exponentially likely to be saddle points with many negative and approximate plateau directions whereas all local minima are likely to have an error very close to that of the global minimum (these results are conveniently reviewed in [Dauphin et al., 2014]).”
Sharp Minima Can Generalize For Deep Nets (2017, background): “See Amari (1998); Pascanu & Bengio (2014) for more details.”
Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “Recent work indicates that in practice, the loss surfaces of sufficiently over-parameterized NNs are surprisingly wellbehaved and in particular less prone to bad local minima than previously thought [11, 17, 9].”
Visualizing the Loss Landscape of Neural Nets (2017, background): “Numerous theoretical studies have been done on our ability to optimize neural loss function [5, 4].”
Model compression via distillation and quantization (2018, background): “…hypothesis for why overcomplete representations are necessary is that they make learning possible by transforming local minima into saddle points (Dauphin et al., 2014) or to discover robust solutions, which do not rely on precise weight values (Hochreiter & Schmidhuber, 1997; Keskar et al.,…”
Learning Fair Classifiers (2015, background): “As a consequence, the ratio in the p % rule is a function with many saddle points, which would complicate the optimization procedure even further (Dauphin et al., 2014).”