# Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 25 Sep 2023.

## Builds on (most cited first, 11 of 11)

- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1605.07147/) (2016)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates](https://mlsanity.com/paper/2008.10526/) (2020)
- [A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimization](https://mlsanity.com/paper/2001.10669/) (2020)
- [Tracking and regret bounds for online zeroth-order Euclidean and Riemannian optimisation](https://mlsanity.com/paper/2010.00211/) (2020)
- [Riemannian conjugate gradient methods: General framework and specific algorithms with convergence analyses](https://mlsanity.com/paper/2112.02572/) (2021)
- [Riemannian stochastic recursive momentum method for non-convex optimization](https://mlsanity.com/paper/2008.04555/) (2020)
- [From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds](https://mlsanity.com/paper/2108.07406/) (2021)
- [On Sharp Stochastic Zeroth Order Hessian Estimators over Riemannian Manifolds](https://mlsanity.com/paper/2201.10780/) (2022)
- [Stochastic Search for a Parametric Cost Function Approximation: Energy storage with rolling forecasts](https://mlsanity.com/paper/2204.07317/) (2022)

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

- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds](https://mlsanity.com/paper/2509.07779/) (2025)
- [Batched Stochastic Bandit for Nondegenerate Functions](https://mlsanity.com/paper/2405.05733/) (2024)
- [Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds](https://mlsanity.com/paper/2510.21468/) (2025)
- [Federated Learning on Riemannian Manifolds: A Gradient-Free Projection-Based Approach](https://mlsanity.com/paper/2507.22855/) (2025)
- [Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds](https://mlsanity.com/paper/2601.08039/) (2026)
- [Riemannian Dueling Optimization](https://mlsanity.com/paper/2603.00023/) (2026)

## Abstract (arXiv)

We present Zeroth-order Riemannian Averaging Stochastic Approximation (textttZo-RASA) algorithms for stochastic optimization on Riemannian manifolds. We show that textttZo-RASA achieves optimal sample complexities for generating ε-approximation first-order stationary solutions using only one-sample or constant-order batches in each iteration. Our approach employs Riemannian moving-average stochastic gradient estimators, and a novel Riemannian-Lyapunov analysis technique for convergence analysis. We improve the algorithm's practicality by using retractions and vector transport, instead of exponential mappings and parallel transports, thereby reducing per-iteration complexity. Additionally, we introduce a novel geometric condition, satisfied by manifolds with bounded second fundamental form, which enables new error bounds for approximating parallel transport with vector transport.