Identifying and attacking the saddle point problem in high-dimensional 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 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.

The theoretical review and analysis in this article draw heavily from arXiv:1405.4604 [cs.LG]

References in corpus (2)

• Theano: new features and speed improvements
• On the saddle point problem for non-convex optimization

Cited by in corpus (78)

• FitNets: Hints for Thin Deep Nets
• The Loss Surfaces of Multilayer Networks
• Spectral Norm Regularization for Improving the Generalizability of Deep Learning
• Qualitatively characterizing neural network optimization problems
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• The Modern Mathematics of Deep Learning
• Ab-initio quantum chemistry with neural-network wavefunctions
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• Softmax Deep Double Deterministic Policy Gradients
• Recent Advances in Adversarial Training for Adversarial Robustness
• Explorations on high dimensional landscapes
• The worst of both worlds: A comparative analysis of errors in learning from data in psychology and machine learning
• The Break-Even Point on Optimization Trajectories of Deep Neural Networks
• Fundamental bounds on learning performance in neural circuits
• Classification regions of deep neural networks
• Coulomb GANs: Provably Optimal Nash Equilibria via Potential Fields
• Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks
• A community-powered search of machine learning strategy space to find NMR property prediction models
• Convexified Convolutional Neural Networks
• Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape
• Hessian-based toolbox for reliable and interpretable machine learning in physics
• Task Agnostic Continual Learning Using Online Variational Bayes with Fixed-Point Updates
• Towards Understanding Theoretical Advantages of Complex-Reaction Networks
• Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances
• Towards Understanding Generalization in Gradient-Based Meta-Learning
• Convergence to minima for the continuous version of Backtracking Gradient Descent
• Block-diagonal Hessian-free Optimization for Training Neural Networks
• Absence of barren plateaus and scaling of gradients in the energy optimization of isometric tensor network states
• Taxonomizing local versus global structure in neural network loss landscapes
• Escaping Saddle Points Faster with Stochastic Momentum
• AdaDNNs: Adaptive Ensemble of Deep Neural Networks for Scene Text Recognition
• A Stochastic Trust Region Method for Non-convex Minimization
• Optimizing Mode Connectivity via Neuron Alignment
• Efficiency of neural quantum states in light of the quantum geometric tensor
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Red-QAOA: Efficient Variational Optimization through Circuit Reduction
• On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size
• Convergence rates of Gibbs measures with degenerate minimum
• Synaptic balancing: a biologically plausible local learning rule that provably increases neural network noise robustness without sacrificing task performance
• Low-rank Bilinear Pooling for Fine-Grained Classification
• An adaptive Hessian approximated stochastic gradient MCMC method
• Unconstrained optimisation on Riemannian manifolds
• Improved Deep Learning of Object Category using Pose Information
• Expanded Alternating Optimization of Nonconvex Functions with Applications to Matrix Factorization and Penalized Regression
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• A Generative Model for Sampling High-Performance and Diverse Weights for Neural Networks
• A Continuous Optimisation Benchmark Suite from Neural Network Regression
• Expectigrad: Fast Stochastic Optimization with Robust Convergence Properties
• Kähler Geometry of Quiver Varieties and Machine Learning
• ADINE: An Adaptive Momentum Method for Stochastic Gradient Descent
• NCVX: A User-Friendly and Scalable Package for Nonconvex Optimization in Machine Learning
• New Q-Newton's method meets Backtracking line search: good convergence guarantee, saddle points avoidance, quadratic rate of convergence, and easy implementation
• Critical Point Finding with Newton-MR by Analogy to Computing Square Roots
• Are Saddles Good Enough for Deep Learning?
• Combining learning rate decay and weight decay with complexity gradient descent - Part I
• Distributed Stochastic Nested Optimization via Cubic Regularization
• Appearance of Random Matrix Theory in Deep Learning
• A Langevinized Ensemble Kalman Filter for Large-Scale Static and Dynamic Learning
• On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes
• ResNEsts and DenseNEsts: Block-based DNN Models with Improved Representation Guarantees
• Towards glass-box CNNs
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• Deep Neural Networks Are Congestion Games: From Loss Landscape to Wardrop Equilibrium and Beyond
• How regularization affects the critical points in linear networks
• Not all parameters are born equal: Attention is mostly what you need
• Solving hybrid machine learning tasks by traversing weight space geodesics
• Inertial Newton Algorithms Avoiding Strict Saddle Points
• A Neural Tangent Kernel Perspective of Infinite Tree Ensembles
• On Simplicity and Complexity in the Brave New World of Large-Scale Neuroscience
• Generalisations and improvements of New Q-Newton's method Backtracking
• Improving Adversarial Robustness for Free with Snapshot Ensemble
• Expressive Power and Loss Surfaces of Deep Learning Models
• Optimal Auction Design for the Gradual Procurement of Strategic Service Provider Agents
• Exploiting Spline Models for the Training of Fully Connected Layers in Neural Network
• Exact Stochastic Second Order Deep Learning
• Training Deep Neural Networks via Branch-and-Bound
• Binary Search and First Order Gradient Based Method for Stochastic Optimization