Gradient Descent Converges to Minimizers

Abstract

We show that gradient descent converges to a local minimizer, almost surely with random initialization. This is proved by applying the Stable Manifold Theorem from dynamical systems theory.

Submitted to COLT 2016

References in corpus (5)

• The Loss Surfaces of Multilayer Networks
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• On the saddle point problem for non-convex optimization

Cited by in corpus (68)

• Learning to Optimize: Training Deep Neural Networks for Wireless Resource Management
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Matrix Completion has No Spurious Local Minimum
• Asynchronous Stochastic Gradient Descent with Delay Compensation
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• The Mechanics of n-Player Differentiable Games
• Ensemble Kalman Inversion: A Derivative-Free Technique For Machine Learning Tasks
• Global Optimality in Low-rank Matrix Optimization
• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• Escaping Saddles with Stochastic Gradients
• Learning explanations that are hard to vary
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• A near-stationary subspace for ridge approximation
• Competitive Gradient Descent
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• Beyond Convexity -- Contraction and Global Convergence of Gradient Descent
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• On the Loss Landscape of Adversarial Training: Identifying Challenges and How to Overcome Them
• Implicit Geometric Regularization for Learning Shapes
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Local Saddle Point Optimization: A Curvature Exploitation Approach
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• Deep Hamiltonian networks based on symplectic integrators
• Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• A general system of differential equations to model first order adaptive algorithms
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• When Does Non-Orthogonal Tensor Decomposition Have No Spurious Local Minima?
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Stochastic Heavy Ball
• Nonconvex Robust Low-rank Matrix Recovery
• A Survey on Fault-tolerance in Distributed Optimization and Machine Learning
• A Quantitative Analysis of the Effect of Batch Normalization on Gradient Descent
• Deep Online Convex Optimization with Gated Games
• Communication-Efficient Federated Learning with Compensated Overlap-FedAvg
• Implicit Regularization and Convergence for Weight Normalization
• Learning from Sparse Demonstrations
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• Fast Convergence for Langevin Diffusion with Manifold Structure
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
• Block Coordinate Descent Only Converge to Minimizers
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Global Optimality in Distributed Low-rank Matrix Factorization
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Aggressive Local Search for Constrained Optimal Control Problems with Many Local Minima
• An Essay on Optimization Mystery of Deep Learning
• On Alignment in Deep Linear Neural Networks
• Distributed stochastic optimization with large delays
• A Variant of Gradient Descent Algorithm Based on Gradient Averaging
• Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifold
• FourierSAT: A Fourier Expansion-Based Algebraic Framework for Solving Hybrid Boolean Constraints
• One-dimensional System Arising in Stochastic Gradient Descent
• The Landscape of Multi-Layer Linear Neural Network From the Perspective of Algebraic Geometry
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• How regularization affects the critical points in linear networks
• Depth Descent Synchronization in $\mathrm{SO}(D)$
• Generalization Error Bounds for Optimization Algorithms via Stability
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience