First-order methods almost always avoid strict saddle points

We establish that first-order methods avoid strict saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including (manifold) gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algori...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2019-07, Vol.176 (1-2), p.311-337
Main Authors: Lee, Jason D., Panageas, Ioannis, Piliouras, Georgios, Simchowitz, Max, Jordan, Michael I., Recht, Benjamin
Format: Article
Language:English
Subjects:
Algorithms
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Full Length Paper
Manifolds
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Saddle points
Stability analysis
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We establish that first-order methods avoid strict saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including (manifold) gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algorithms can be studied from a dynamical systems perspective in which appropriate instantiations of the Stable Manifold Theorem allow for a global stability analysis. Thus, neither access to second-order derivative information nor randomness beyond initialization is necessary to provably avoid strict saddle points.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-019-01374-3