# Tracking and regret bounds for online zeroth-order Euclidean and Riemannian optimisation

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

## Key facts

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

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

- [Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms](https://mlsanity.com/paper/2309.14506/) (2023)
- [Minimizing Dynamic Regret on Geodesic Metric Spaces](https://mlsanity.com/paper/2302.08652/) (2023)
- [Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds](https://mlsanity.com/paper/2509.07779/) (2025)
- [Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives](https://mlsanity.com/paper/2509.11236/) (2025)
- [Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds](https://mlsanity.com/paper/2510.21468/) (2025)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Locally Differentially Private Distributed Online Learning with Guaranteed Optimality](https://mlsanity.com/paper/2306.14094/) (2023)
- [Federated Learning on Riemannian Manifolds: A Gradient-Free Projection-Based Approach](https://mlsanity.com/paper/2507.22855/) (2025)
- [Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions](https://mlsanity.com/paper/2607.20316/) (2026)
- [Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications](https://mlsanity.com/paper/2306.05655/) (2023)
- [Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds](https://mlsanity.com/paper/2601.08039/) (2026)
- [Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds](https://mlsanity.com/paper/2609.13646/) (2026)

## Abstract (arXiv)

We study numerical optimisation algorithms that use zeroth-order information to minimise time-varying geodesically-convex cost functions on Riemannian manifolds. In the Euclidean setting, zeroth-order algorithms have received a lot of attention in both the time-varying and time-invariant cases. However, the extension to Riemannian manifolds is much less developed. We focus on Hadamard manifolds, which are a special class of Riemannian manifolds with global nonpositive curvature that offer convenient grounds for the generalisation of convexity notions. Specifically, we derive bounds on the expected instantaneous tracking error, and we provide algorithm parameter values that minimise the algorithm's performance. Our results illustrate how the manifold geometry in terms of the sectional curvature affects these bounds. Additionally, we provide dynamic regret bounds for this online optimisation setting. To the best of our knowledge, these are the first regret bounds even for the Euclidean version of the problem. Lastly, via numerical simulations, we demonstrate the applicability of our algorithm on an online Karcher mean problem.