# Riemannian Accelerated Zeroth-order Algorithm: Improved Robustness and Lower Query Complexity

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2024.

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

- [The Multi-Query Paradox in Zeroth-Order Optimization](https://mlsanity.com/paper/2509.15552/) (2025)
- [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)
- [Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management](https://mlsanity.com/paper/2502.19210/) (2025)
- [Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds](https://mlsanity.com/paper/2601.08039/) (2026)

## Abstract (arXiv)

Optimization problems with access to only zeroth-order information of the objective function on Riemannian manifolds arise in various applications, spanning from statistical learning to robot learning. While various zeroth-order algorithms have been proposed in Euclidean space, they are not inherently designed to handle the challenging constraints imposed by Riemannian manifolds. The proper adaptation of zeroth-order techniques to Riemannian manifolds remained unknown until the pioneering work of citeli2023stochastic. However, zeroth-order algorithms are widely observed to converge slowly and be unstable in practice. To alleviate these issues, we propose a Riemannian accelerated zeroth-order algorithm with improved robustness. Regarding efficiency, our accelerated algorithm has the function query complexity of O(ε-7/4d) for finding an ε-approximate first-order stationary point. By introducing a small perturbation, it exhibits a function query complexity of tildeO(ε-7/4d) for seeking a second-order stationary point with a high probability, matching state-of-the-art result in Euclidean space. Moreover, we further establish the almost sure convergence in the asymptotic sense through the Stable Manifold Theorem. Regarding robustness, our algorithm requires larger smoothing parameters in the order of tildeO(ε7/8d-1/2), improving the existing result by a factor of tildeO(ε3/4).