  SPIDER (Stochastic Path Integrated Differential EstimatoR) is an efficient
gradient estimation technique developed for non-convex stochastic optimization.
Although having been shown to attain nearly optimal computational complexity
bounds, the SPIDER-type methods are limited to linear metric spaces. In this
paper, we introduce the Riemannian SPIDER (R-SPIDER) method as a novel
nonlinear-metric extension of SPIDER for efficient non-convex optimization on
Riemannian manifolds. We prove that for finite-sum problems with $n$
components, R-SPIDER converges to an $\epsilon$-accuracy stationary point
within
$\mathcal{O}\big(\min\big(n+\frac{\sqrt{n}}{\epsilon^2},\frac{1}{\epsilon^3}\big)\big)$
stochastic gradient evaluations, which is sharper in magnitude than the prior
Riemannian first-order methods. For online optimization, R-SPIDER is shown to
converge with $\mathcal{O}\big(\frac{1}{\epsilon^3}\big)$ complexity which is,
to the best of our knowledge, the first non-asymptotic result for online
Riemannian optimization. Especially, for gradient dominated functions, we
further develop a variant of R-SPIDER and prove its linear convergence rate.
Numerical results demonstrate the computational efficiency of the proposed
methods.
