Efficiently escaping saddle points on manifolds

Abstract

Smooth, non-convex optimization problems on Riemannian manifolds occur in machine learning as a result of orthonormality, rank or positivity constraints. First- and second-order necessary optimality conditions state that the Riemannian gradient must be zero, and the Riemannian Hessian must be positive semidefinite. Generalizing Jin et al.'s recent work on perturbed gradient descent (PGD) for optimization on linear spaces [How to Escape Saddle Points Efficiently (2017), Stochastic Gradient Descent Escapes Saddle Points Efficiently (2019)], we propose a version of perturbed Riemannian gradient descent (PRGD) to show that necessary optimality conditions can be met approximately with high probability, without evaluating the Hessian. Specifically, for an arbitrary Riemannian manifold $\mathcal{M}$ of dimension $d$, a sufficiently smooth (possibly non-convex) objective function $f$, and under weak conditions on the retraction chosen to move on the manifold, with high probability, our version of PRGD produces a point with gradient smaller than $\epsilon$ and Hessian within $\sqrt{\epsilon }$ of being positive semidefinite in $O((\log d{)}^4/{\epsilon }^2)$ gradient queries. This matches the complexity of PGD in the Euclidean case. Crucially, the dependence on dimension is low. This matters for large-scale applications including PCA and low-rank matrix completion, which both admit natural formulations on manifolds. The key technical idea is to generalize PRGD with a distinction between two types of gradient steps: "steps on the manifold" and "perturbed steps in a tangent space of the manifold." Ultimately, this distinction makes it possible to extend Jin et al.'s analysis seamlessly.

arXiv comment18 pages, NeurIPS 2019

References in corpus (11)

• Global rates of convergence for nonconvex optimization on manifolds
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Escaping Saddles with Stochastic Gradients
• On the saddle point problem for non-convex optimization
• The Power of Normalization: Faster Evasion of Saddle Points
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Escaping Saddle Points in Constrained Optimization
• Escaping from saddle points on Riemannian manifolds
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time

Cited by in corpus (12)

• Asynchronous and Parallel Distributed Pose Graph Optimization
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• Convergence Analysis of Riemannian Stochastic Approximation Schemes
• A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization
• Solving Optimization Problems over the Stiefel Manifold by Smooth Exact Penalty Function
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifold
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization