First-order methods almost always avoid strict saddle points
成果类型：
Article; Proceedings Paper
署名作者：
Lee, Jason D.; Panageas, Ioannis; Piliouras, Georgios; Simchowitz, Max; Jordan, Michael I.; Recht, Benjamin
署名单位：
University of Southern California; Singapore University of Technology & Design; University of California System; University of California Berkeley
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-019-01374-3
发表日期：
2019
页码：
311-337
关键词：
摘要：
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.