# Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifolds

arXiv: https://arxiv.org/abs/1811.08109 · HTML: https://mlsanity.com/paper/1811.08109/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2018.

## Built on by (most cited first, 12 of 12)

- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2303.16510/) (2023)
- [Riemannian Hamiltonian methods for min-max optimization on manifolds](https://mlsanity.com/paper/2204.11418/) (2022)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [Nonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Data](https://mlsanity.com/paper/2406.08465/) (2024)
- [Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties](https://mlsanity.com/paper/2211.14645/) (2022)
- [Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties](https://mlsanity.com/paper/2305.16186/) (2023)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Rieoptax: Riemannian Optimization in JAX](https://mlsanity.com/paper/2210.04840/) (2022)
- [Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds](https://mlsanity.com/paper/2406.02296/) (2024)
- [Fr'echet Regression on the Bures-Wasserstein Manifold](https://mlsanity.com/paper/2604.03566/) (2026)

## Abstract (arXiv)

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 ε-accuracy stationary point within Obig(minbig(n+frac√nε2,frac1ε3big)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 Obig(frac1ε3big) 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.