Efficiently Escaping Saddle Points on Manifolds

Abstract

We generalize Jin et al.'s perturbed gradient descent algorithm, PGD, to Riemannian manifolds (for Jin et al's work, see [How to Escape Saddle Points Efficiently (2017), Stochastic Gradient Descent Escapes Saddle Points Efficiently (2019)]). For an arbitrary Riemannian manifold $\calM$ of dimension $d$, a sufficiently smooth nonconvex objective function $f$ and weak conditions on the chosen retraction, our algorithm perturbed Riemannian gradient descent, PRGD, achieves an $\epsilon$-second-order critical point in $O((\log{d})^4 / \epsilon^{2})$ gradient queries, matching the complexity achieved by perturbed gradient descent in the Euclidean case. Like PGD, PRGD does not require Hessian information and only has polylogarithmic dependence on dimension $d$. This is important for applications involving optimization on manifolds in large dimension, including PCA, low-rank matrix completion, etc. Our key idea is to distinguish between two types of gradient steps: ``steps on the manifold'' and ``steps in a tangent space'' of the manifold. This idea allows us to seamlessly extend Jin et al.'s analysis.