First-order methods almost always avoid saddle points: the case of vanishing step-sizes

Abstract

In a series of papers \cite{LSJR16, PP17, LPP}, it was established that some of the most commonly used first order methods almost surely (under random initializations) and with step-size being small enough, avoid strict saddle points, as long as the objective function $f$ is $C^2$ and has Lipschitz gradient. The key observation was that first order methods can be studied from a dynamical systems perspective, in which instantiations of Center-Stable manifold theorem allow for a global analysis. The results of the aforementioned papers were limited to the case where the step-size $\alpha$ is constant, i.e., does not depend on time (and bounded from the inverse of the Lipschitz constant of the gradient of $f$). It remains an open question whether or not the results still hold when the step-size is time dependent and vanishes with time. In this paper, we resolve this question on the affirmative for gradient descent, mirror descent, manifold descent and proximal point. The main technical challenge is that the induced (from each first order method) dynamical system is time non-homogeneous and the stable manifold theorem is not applicable in its classic form. By exploiting the dynamical systems structure of the aforementioned first order methods, we are able to prove a stable manifold theorem that is applicable to time non-homogeneous dynamical systems and generalize the results in \cite{LPP} for vanishing step-sizes.

We add an extra assumption that the Hessian matrix of the objective function is invertible

References in corpus (8)

• The Loss Surfaces of Multilayer Networks
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• First-order Methods Almost Always Avoid Saddle Points
• On the saddle point problem for non-convex optimization
• Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos

Cited by in corpus (1)

• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications