Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions

Abstract

Given a non-convex twice differentiable cost function f, we prove that the set of initial conditions so that gradient descent converges to saddle points where \nabla^2 f has at least one strictly negative eigenvalue has (Lebesgue) measure zero, even for cost functions f with non-isolated critical points, answering an open question in [Lee, Simchowitz, Jordan, Recht, COLT2016]. Moreover, this result extends to forward-invariant convex subspaces, allowing for weak (non-globally Lipschitz) smoothness assumptions. Finally, we produce an upper bound on the allowable step-size.

arXiv comment2 figures

References in corpus (6)

• 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 II: Recovery by Riemannian Trust-region Method
• Gradient Descent Converges to Minimizers
• Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing
• Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics

Cited by in corpus (17)

• A Geometric Analysis of Phase Retrieval
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• Convergence guarantees for a class of non-convex and non-smooth optimization problems
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• 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
• A Geometric Approach of Gradient Descent Algorithms in Linear Neural Networks
• Statistical Inference with Local Optima
• Robust Blind Deconvolution via Mirror Descent
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Multichannel Sparse Blind Deconvolution on the Sphere
• A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points
• BPGrad: Towards Global Optimality in Deep Learning via Branch and Pruning
• Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points