On the saddle point problem for non-convex optimization

By Razvan Pascanu, Yann Dauphin, Surya Ganguli, Yoshua Bengio. 2014

117 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 the ability of 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, and neural network theory, 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 algorithm, 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 neural network training, and provide preliminary numerical evidence for its superior 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

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).”
Neural Tangent Kernel: Convergence and Generalization in Neural Networks (2018, background): “A number of results [3, 14, 15] suggest that for wide enough networks, there are very few “bad” local minima, i.”
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization (2014, background): “In this work, which is an extension of the previous report Pascanu et al. (2014), we ﬁrst want to raise awareness of this issue, and second, propose an alternative approach to second-order optimization that aims to rapidly escape from saddle points.”
A Kronecker-factored approximate Fisher matrix for convolution layers (2016, methodology): “The original and most well-known example is Newton’s method, where C is chosen to be the Hessian matrix; this isn’t appropriate in the non-convex setting because of the well-known problem that it searches for critical points rather than local optima (e.g. Pascanu et al., 2014).”
Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning (2017, background): “Note that although deep neural networks often do not struggle with lo-cal optima in supervised learning (Pascanu et al., 2014), local optima remain an issue in RL because the reward signal may deceptively encourage the agent to perform actions that prevent it from discovering the globally optimal…”
Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes (2018, background): “…networks (NNs) demonstrate remarkable performance (He et al., 2016; Oord et al., 2016; Silver et al., 2017; Vaswani et al., 2017), but are still only poorly understood from a theoretical perspective (Goodfellow et al., 2015; Choromanska et al., 2015; Pascanu et al., 2014; Zhang et al., 2017).”
Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning (2018, background): “(More recently, this fact seems to have been rediscovered [108, 37, 56, 135].”
Gradient Descent Converges to Minimizers (2016, background): “We remark that the strict saddle assumption is necessary in the worst case, due to hardness results regarding testing the local optimality of functions whose Hessians are highly degenerate at criticalpoints (e.g, quartic polynomials) [19].”
Optimization Methods for Supervised Machine Learning: From Linear Models to Deep Learning (2017, background): “On the other hand, it tends to slow down around stationary points, which can hinder its progress in training DNNs [58, 63, 21].”
Gradient Descent Only Converges to Minimizers (2016, methodology): “Specialized to deep learning applications, Dauphin et al. (2014); Pascanu et al. (2014) have introduced a saddle-free Newton method.”
Random Walk Initialization for Training Very Deep Feedforward Networks (2014, background): “Further, the topic of why deep networks are difﬁcult to train is also an area of active research (Glorot & Bengio, 2010), (Pascanu et al., 2012), (Saxe et al., 2013), (Pascanu et al., 2014).”
The unreasonable effectiveness of deep learning in artificial intelligence (2020, background): “special mathematical properties that we are just beginning to understand. Local minima during learning are rare because in the high-dimensional parameter space, most critical points are saddle points (12). Another reason why good solutions can be found so easily by stochastic gradient descent is tha”
On the Origin of Deep Learning (2017, result): “Recently, the studying of cost surfaces of neural networks have indicated the existence of saddle points (Choromanska et al., 2015; Dauphin et al., 2014; Pascanu et al., 2014), which may explain the findings of Brady et al back in the late 80s.”