Escaping from saddle points on Riemannian manifolds

Abstract

We consider minimizing a nonconvex, smooth function $f$ on a Riemannian manifold $\mathcal{M}$. We show that a perturbed version of Riemannian gradient descent algorithm converges to a second-order stationary point (and hence is able to escape saddle points on the manifold). The rate of convergence depends as $1/{\epsilon }^2$ on the accuracy $\epsilon$, which matches a rate known only for unconstrained smooth minimization. The convergence rate depends polylogarithmically on the manifold dimension $d$, hence is almost dimension-free. The rate also has a polynomial dependence on the parameters describing the curvature of the manifold and the smoothness of the function. While the unconstrained problem (Euclidean setting) is well-studied, our result is the first to prove such a rate for nonconvex, manifold-constrained problems.

arXiv commentsubmitted to NeurIPS 2019

References in corpus (11)

• Global rates of convergence for nonconvex optimization on manifolds
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• First-order Methods Almost Always Avoid Saddle Points
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• First-order Methods for Geodesically Convex Optimization
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• Stochastic Primal-Dual Method on Riemannian Manifolds with Bounded Sectional Curvature

Cited by in corpus (13)

• Efficiently escaping saddle points on manifolds
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Convergence Analysis of Riemannian Stochastic Approximation Schemes
• A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
• Solving Optimization Problems over the Stiefel Manifold by Smooth Exact Penalty Function
• Momentum Accelerates Evolutionary Dynamics
• 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