# Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 35 references that are in the map.
- First posted on arXiv 14 Sep 2025.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group](https://mlsanity.com/paper/1901.08428/) (2019)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1605.07147/) (2016)
- [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021)
- [A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization](https://mlsanity.com/paper/1910.10782/) (2019)
- [Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matrices](https://mlsanity.com/paper/1507.02772/) (2015)
- [Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexity](https://mlsanity.com/paper/1806.06373/) (2018)
- [Tracking and regret bounds for online zeroth-order Euclidean and Riemannian optimisation](https://mlsanity.com/paper/2010.00211/) (2020)
- [Retraction-Free Decentralized Non-convex Optimization with Orthogonal Constraints](https://mlsanity.com/paper/2405.11590/) (2024)
- [Policy Optimization over Submanifolds for Linearly Constrained Feedback Synthesis](https://mlsanity.com/paper/2201.11157/) (2022)
- [Decentralized Online Riemannian Optimization with Dynamic Environments](https://mlsanity.com/paper/2410.05128/) (2024)
- [Riemannian Projection-free Online Learning](https://mlsanity.com/paper/2305.19349/) (2023)
- [Implicit Riemannian Optimism with Applications to Min-Max Problems](https://mlsanity.com/paper/2501.18381/) (2025)
- [Horospherically Convex Optimization on Hadamard Manifolds Part I: Analysis and Algorithms](https://mlsanity.com/paper/2505.16970/) (2025)
- [Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds](https://mlsanity.com/paper/2509.07779/) (2025)
- [Convex analysis on Hadamard spaces and scaling problems](https://mlsanity.com/paper/2203.03193/) (2022)
- [Riemannian optimization on unit sphere with p-norm and its applications](https://mlsanity.com/paper/2202.11597/) (2022)
- [Horoballs and the subgradient method](https://mlsanity.com/paper/2403.15749/) (2024)

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

- [Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds](https://mlsanity.com/paper/2510.21468/) (2025)
- [Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions](https://mlsanity.com/paper/2607.20316/) (2026)
- [Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds](https://mlsanity.com/paper/2609.13646/) (2026)

## Abstract (arXiv)

We study online Riemannian optimization on Hadamard manifolds under the framework of horospherical convexity (h-convexity). Prior work mostly relies on the geodesic convexity (g-convexity), leading to regret bounds scaling poorly with the manifold curvature. To address this limitation, we analyze Riemannian online gradient descent for h-convex and strongly h-convex functions and establish O(√T) and O(log(T)) regret guarantees, respectively. These bounds are curvature-independent and match the results in the Euclidean setting. We validate our approach with experiments on the manifold of symmetric positive definite (SPD) matrices equipped with the affine-invariant metric. In particular, we investigate online Tyler's M-estimation and online Fr'echet mean computation, showing the application of h-convexity in practice.