Escaping from saddle points on Riemannian manifolds
This addresses optimization challenges for nonconvex manifold-constrained problems, which are incremental as it extends existing Euclidean results to Riemannian settings.
The paper tackles the problem of minimizing nonconvex smooth functions on Riemannian manifolds, showing that a perturbed Riemannian gradient descent algorithm converges to second-order stationary points with a rate of 1/ε², matching known rates for unconstrained problems and being almost dimension-free.
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/ε^2$ on the accuracy $ε$, 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.