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 (5)

• Theano: new features and speed improvements
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
• Krylov Subspace Descent for Deep Learning
• On the saddle point problem for non-convex optimization

Cited by in corpus (216)

• A Critical Review of Recurrent Neural Networks for Sequence Learning
• FitNets: Hints for Thin Deep Nets
• SGDR: Stochastic Gradient Descent with Warm Restarts
• Training Very Deep Networks
• A Deep Learning Framework for Unsupervised Affine and Deformable Image Registration
• The Loss Surfaces of Multilayer Networks
• Embedding Watermarks into Deep Neural Networks
• f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Sensitivity and Generalization in Neural Networks: an Empirical Study
• An overview and comparative analysis of Recurrent Neural Networks for Short Term Load Forecasting
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Spectral Norm Regularization for Improving the Generalizability of Deep Learning
• Qualitatively characterizing neural network optimization problems
• Identifying Implementation Bugs in Machine Learning based Image Classifiers using Metamorphic Testing
• Deep learning of dynamics and signal-noise decomposition with time-stepping constraints
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Essentially No Barriers in Neural Network Energy Landscape
• Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?
• Online Batch Selection for Faster Training of Neural Networks
• Scaling description of generalization with number of parameters in deep learning
• Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networks
• Equilibrated adaptive learning rates for non-convex optimization
• Training Neural Networks Without Gradients: A Scalable ADMM Approach
• Entropy and mutual information in models of deep neural networks
• The Mechanics of n-Player Differentiable Games
• Sharp Minima Can Generalize For Deep Nets
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• The Modern Mathematics of Deep Learning
• Ab-initio quantum chemistry with neural-network wavefunctions
• Gradient Descent Converges to Minimizers
• When Are Nonconvex Problems Not Scary?
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Memcomputing: Leveraging memory and physics to compute efficiently
• Universal discriminative quantum neural networks
• The Non-convex Geometry of Low-rank Matrix Optimization
• Nonlinear Approximation via Compositions
• Escaping Saddles with Stochastic Gradients
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• On the Expressive Power of Deep Neural Networks
• Depth Creates No Bad Local Minima
• Task Agnostic Continual Learning Using Online Variational Bayes
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets
• Hidden Unit Specialization in Layered Neural Networks: ReLU vs. Sigmoidal Activation
• On the loss landscape of a class of deep neural networks with no bad local valleys
• On Graduated Optimization for Stochastic Non-Convex Problems
• Strong error analysis for stochastic gradient descent optimization algorithms
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Softmax Deep Double Deterministic Policy Gradients
• Understanding the Loss Surface of Neural Networks for Binary Classification
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Understanding the impact of entropy on policy optimization
• Effect of Depth and Width on Local Minima in Deep Learning
• Recent Advances in Adversarial Training for Adversarial Robustness
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• Explorations on high dimensional landscapes
• The worst of both worlds: A comparative analysis of errors in learning from data in psychology and machine learning
• Replica Symmetry Breaking in Bipartite Spin Glasses and Neural Networks
• Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets
• An empirical analysis of the optimization of deep network loss surfaces
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• 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
• A Closer Look at the Optimization Landscapes of Generative Adversarial Networks
• The Difficulty of Training Sparse Neural Networks
• Coulomb GANs: Provably Optimal Nash Equilibria via Potential Fields
• The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size
• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior
• On the diffusion approximation of nonconvex stochastic gradient descent
• Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks
• Local Saddle Point Optimization: A Curvature Exploitation Approach
• Training Recurrent Neural Networks by Diffusion
• A community-powered search of machine learning strategy space to find NMR property prediction models
• The local convexity of solving systems of quadratic equations
• Learning with hidden variables
• Transport Analysis of Infinitely Deep Neural Network
• Deep Learning without Poor Local Minima
• High Dimensional Spaces, Deep Learning and Adversarial Examples
• Indefinite Kernel Logistic Regression with Concave-inexact-convex Procedure
• Fenchel Lifted Networks: A Lagrange Relaxation of Neural Network Training
• Convexified Convolutional Neural Networks
• An Introduction to Deep Learning for the Physical Layer
• Hessian-based toolbox for reliable and interpretable machine learning in physics
• Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape
• Task Agnostic Continual Learning Using Online Variational Bayes with Fixed-Point Updates
• Understanding cytoskeletal avalanches using mechanical stability analysis
• Towards Understanding Theoretical Advantages of Complex-Reaction Networks
• The Landscape of Deep Learning Algorithms
• Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances
• Generalization in Machine Learning via Analytical Learning Theory
• On the energy landscape of deep networks
• Inexact Newton Methods for Stochastic Nonconvex Optimization with Applications to Neural Network Training
• Finding Local Minima via Stochastic Nested Variance Reduction
• Towards Understanding Generalization in Gradient-Based Meta-Learning
• Shared Representational Geometry Across Neural Networks
• Convergence to minima for the continuous version of Backtracking Gradient Descent
• Hubless keypoint-based 3D deformable groupwise registration
• Block-diagonal Hessian-free Optimization for Training Neural Networks
• Full deep neural network training on a pruned weight budget
• SGD momentum optimizer with step estimation by online parabola model
• Perturbed Proximal Descent to Escape Saddle Points for Non-convex and Non-smooth Objective Functions
• Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Training
• Taxonomizing local versus global structure in neural network loss landscapes
• Solving Continual Combinatorial Selection via Deep Reinforcement Learning
• Proximal Backpropagation
• Biological credit assignment through dynamic inversion of feedforward networks
• Bayesian Sparse learning with preconditioned stochastic gradient MCMC and its applications
• Orthogonal Deep Neural Networks
• Absence of barren plateaus and scaling of gradients in the energy optimization of isometric tensor network states
• Symmetry & critical points for a model shallow neural network
• Escaping Saddle Points Faster with Stochastic Momentum
• Optimizing Mode Connectivity via Neuron Alignment
• Orthogonal Convolutional Neural Networks
• A Stochastic Trust Region Method for Non-convex Minimization
• AdaDNNs: Adaptive Ensemble of Deep Neural Networks for Scene Text Recognition
• Distributed Bayesian Learning with Stochastic Natural-gradient Expectation Propagation and the Posterior Server
• Reducing the Training Time of Neural Networks by Partitioning
• Accelerating Natural Gradient with Higher-Order Invariance
• DANTE: Deep AlterNations for Training nEural networks
• Maximum likelihood estimation of determinantal point processes
• Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Optimization methods for achieving high diffraction efficiency with perfect electric conducting gratings
• Non-attracting Regions of Local Minima in Deep and Wide Neural Networks
• Efficiency of neural quantum states in light of the quantum geometric tensor
• Red-QAOA: Efficient Variational Optimization through Circuit Reduction
• Automated Polysomnography Analysis for Detection of Non-Apneic and Non-Hypopneic Arousals using Feature Engineering and a Bidirectional LSTM Network
• Demystifying ResNet
• Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
• RandomOut: Using a convolutional gradient norm to rescue convolutional filters
• On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size
• Convergence rates of Gibbs measures with degenerate minimum
• Deep Neural Networks for Choice Analysis: Extracting Complete Economic Information for Interpretation
• Neural Taylor Approximations: Convergence and Exploration in Rectifier Networks
• Low-rank Bilinear Pooling for Fine-Grained Classification
• Adaptive Normalized Risk-Averting Training For Deep Neural Networks
• Unconstrained optimisation on Riemannian manifolds
• CaMKII activation supports reward-based neural network optimization through Hamiltonian sampling
• Reinforced stochastic gradient descent for deep neural network learning
• An adaptive Hessian approximated stochastic gradient MCMC method
• Convergence Analyses of Online ADAM Algorithm in Convex Setting and Two-Layer ReLU Neural Network
• Synaptic balancing: a biologically plausible local learning rule that provably increases neural network noise robustness without sacrificing task performance
• Fast Approximation of the Gauss-Newton Hessian Matrix for the Multilayer Perceptron
• To Relieve Your Headache of Training an MRF, Take AdVIL
• Discovery of Latent Factors in High-dimensional Data Using Tensor Methods
• A Continuous Optimisation Benchmark Suite from Neural Network Regression
• RecurJac: An Efficient Recursive Algorithm for Bounding Jacobian Matrix of Neural Networks and Its Applications
• Integrated Inference and Learning of Neural Factors in Structural Support Vector Machines
• Collective evolution of weights in wide neural networks
• Abstraction Mechanisms Predict Generalization in Deep Neural Networks
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• Deep Curvature Suite
• A Generative Model for Sampling High-Performance and Diverse Weights for Neural Networks
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Expanded Alternating Optimization of Nonconvex Functions with Applications to Matrix Factorization and Penalized Regression
• The global optimum of shallow neural network is attained by ridgelet transform
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• Expectigrad: Fast Stochastic Optimization with Robust Convergence Properties
• Improved Deep Learning of Object Category using Pose Information
• The Saddle Point Problem of Polynomials
• Distributed Gradient Methods for Nonconvex Optimization: Local and Global Convergence Guarantees
• Kähler Geometry of Quiver Varieties and Machine Learning
• Semi-Supervised Translation with MMD Networks
• A fast and simple modification of Newton's method helping to avoid saddle points
• ADINE: An Adaptive Momentum Method for Stochastic Gradient Descent
• New Q-Newton's method meets Backtracking line search: good convergence guarantee, saddle points avoidance, quadratic rate of convergence, and easy implementation
• NCVX: A User-Friendly and Scalable Package for Nonconvex Optimization in Machine Learning
• Understanding and Controlling Memory in Recurrent Neural Networks
• Low Rank Saddle Free Newton: A Scalable Method for Stochastic Nonconvex Optimization
• ResNEsts and DenseNEsts: Block-based DNN Models with Improved Representation Guarantees
• Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models: Extension
• Traversing the noise of dynamic mini-batch sub-sampled loss functions: A visual guide
• Generalisation in fully-connected neural networks for time series forecasting
• Improving SGD convergence by online linear regression of gradients in multiple statistically relevant directions
• Evaluation of Neural Networks for Image Recognition Applications: Designing a 0-1 MILP Model of a CNN to create adversarials
• On the Analysis of Trajectories of Gradient Descent in the Optimization of Deep Neural Networks
• Trust-Region Algorithms for Training Responses: Machine Learning Methods Using Indefinite Hessian Approximations
• Mean Field Theory of Activation Functions in Deep Neural Networks
• Distributed Stochastic Nested Optimization via Cubic Regularization
• On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes
• Critical Percolation as a Framework to Analyze the Training of Deep Networks
• Appearance of Random Matrix Theory in Deep Learning
• A Langevinized Ensemble Kalman Filter for Large-Scale Static and Dynamic Learning
• Adaptive Hamiltonian Variational Integrators and Symplectic Accelerated Optimization
• Global Convergence of the (1+1) Evolution Strategy
• Combining learning rate decay and weight decay with complexity gradient descent - Part I
• Critical Point Finding with Newton-MR by Analogy to Computing Square Roots
• Are Saddles Good Enough for Deep Learning?
• Solving hybrid machine learning tasks by traversing weight space geodesics
• Exploiting Spline Models for the Training of Fully Connected Layers in Neural Network
• Exact Stochastic Second Order Deep Learning
• Binary Search and First Order Gradient Based Method for Stochastic Optimization
• Inertial Newton Algorithms Avoiding Strict Saddle Points
• Simulation-based inference methods for partially observed Markov model via the R package is2
• The many faces of deep learning
• A Neural Tangent Kernel Perspective of Infinite Tree Ensembles
• Expressive Power and Loss Surfaces of Deep Learning Models
• Training Deep Neural Networks via Branch-and-Bound
• A Deterministic Gradient-Based Approach to Avoid Saddle Points
• A Globally Convergent Penalty-Based Gauss-Newton Algorithm with Applications
• Towards glass-box CNNs
• How regularization affects the critical points in linear networks
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• Deep Neural Networks Are Congestion Games: From Loss Landscape to Wardrop Equilibrium and Beyond
• Not all parameters are born equal: Attention is mostly what you need
• Backtracking gradient descent method for general $C^1$ functions, with applications to Deep Learning
• On Simplicity and Complexity in the Brave New World of Large-Scale Neuroscience
• Depth Descent Synchronization in $\mathrm{SO}(D)$
• Barcodes as Summary of Loss Function Topology
• Optimal Auction Design for the Gradual Procurement of Strategic Service Provider Agents
• Improving Adversarial Robustness for Free with Snapshot Ensemble
• Generalisations and improvements of New Q-Newton's method Backtracking