  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.
