On the saddle point problem for non-convex optimization

Abstract

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.

11 pages, 8 figures

References in corpus (3)

• Theano: new features and speed improvements
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• The statistics of critical points of Gaussian fields on large-dimensional spaces

Cited by in corpus (32)

• Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• The Unreasonable Effectiveness of Deep Learning in Artificial Intelligence
• Gradient Descent Converges to Minimizers
• Gradient Descent Happens in a Tiny Subspace
• Overfitting Mechanism and Avoidance in Deep Neural Networks
• When Are Nonconvex Problems Not Scary?
• A Critical Review of Physics-Informed Machine Learning Applications in Subsurface Energy Systems
• On the Origin of Deep Learning
• First-order Methods Almost Always Avoid Saddle Points
• Random Walk Initialization for Training Very Deep Feedforward Networks
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• Efficiently escaping saddle points on manifolds
• A Kronecker-factored approximate Fisher matrix for convolution layers
• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior
• Training Recurrent Neural Networks by Diffusion
• Quantitative Propagation of Chaos for SGD in Wide Neural Networks
• A trust-region method for stochastic variational inference with applications to streaming data
• Towards Understanding Generalization in Gradient-Based Meta-Learning
• Interpreting Deep Learning: The Machine Learning Rorschach Test?
• Reducing the Training Time of Neural Networks by Partitioning
• The asymptotic spectrum of the Hessian of DNN throughout training
• Numerically Recovering the Critical Points of a Deep Linear Autoencoder
• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• Integrated Inference and Learning of Neural Factors in Structural Support Vector Machines
• Improved Deep Learning of Object Category using Pose Information
• Kähler Geometry of Quiver Varieties and Machine Learning
• A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points
• Smooth Bilevel Programming for Sparse Regularization
• Are Saddles Good Enough for Deep Learning?
• Not all parameters are born equal: Attention is mostly what you need
• Run-and-Inspect Method for Nonconvex Optimization and Global Optimality Bounds for R-Local Minimizers