First-order Methods Almost Always Avoid Saddle Points
We establish that first-order methods avoid saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including 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 saddle points.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Inertial Newton Algorithms Avoiding Strict Saddle Points
We study the asymptotic behavior of second-order algorithms mixing Newton's method and inertial gradient descent in non-convex landscapes. We show that, despite the Newtonian behavior of these methods, they almost always…
Accelerated Multiplicative Weights Update Avoids Saddle Points almost always
We consider non-convex optimization problems with constraint that is a product of simplices. A commonly used algorithm in solving this type of problem is the Multiplicative Weights Update (MWU), an algorithm that is wide…
System III: Learning with Domain Knowledge for Safety Constraints
Reinforcement learning agents naturally learn from extensive exploration. Exploration is costly and can be unsafe in $\textit{safety-critical}$ domains. This paper proposes a novel framework for incorporating domain know…
Safe ExplorationTransformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscape
Large language models based on the Transformer architecture have demonstrated impressive capabilities to learn in context. However, existing theoretical studies on how this phenomenon arises are limited to the dynamics o…
In-Context LearningHeavy-ball Algorithms Always Escape Saddle Points
Nonconvex optimization algorithms with random initialization have attracted increasing attention recently. It has been showed that many first-order methods always avoid saddle points with random starting points. In this …