Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
Abstract
This work addresses decentralized online Riemannian optimization on Hadamard manifolds. Prior work under geodesic convexity (g-convexity) may require curvature information in the optimization analysis, typically through a finite lower bound on the sectional curvature. Curvature may also enter the step size or contraction factor of tangent-space Riemannian consensus schemes. In this work, we relax the curvature dependence for a narrower class of horospherical convex (h-convex) functions. We study Distributed Riemannian Online Gradient Descent (D-ROGD), which combines local Riemannian h-subgradient updates with an implicit Fréchet-mean consensus. For h-convex and strongly h-convex local objectives, we establish O(√T) and O(log T) static regret, respectively, matching the corresponding Euclidean rates with respect to T, with network dependence governed solely by the spectral gap. To our knowledge, these are the first curvature-independent regret guarantees for decentralized online optimization on Hadamard manifolds. Experiments on hyperbolic embeddings corroborate the predicted rates, with no observable degradation due to curvature.
Related
- Isoperimetric and total curvature inequalities in Cartan-Hadamard manifolds with nullity
- Technical Report: Partially Asynchronous Distributed Optimization on Riemannian Manifolds
- Almgren frequency and Agmon convexity on rotationally symmetric Cartan-Hadamard manifolds
- The Cartan-Hadamard isoperimetric inequality under controlled variation of curvature
- A proof of the Cartan-Hadamard conjecture for small volumes under a Ricci curvature lower bound
BibTeX
@misc{cai2026curvatureindependent,
title = {{Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds}},
author = {Zhanyuan Cai and Emre Sahinoglu and Shahin Shahrampour},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13646},
eprint = {2609.13646},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13646},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
AU - Zhanyuan Cai
AU - Emre Sahinoglu
AU - Shahin Shahrampour
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.13646
UR - https://arxiv.org/abs/2609.13646
AB - This work addresses decentralized online Riemannian optimization on Hadamard manifolds. Prior work under geodesic convexity (g-convexity) may require curvature information in the optimization analysis, typically through a finite lower bound on the sectional curvature. Curvature may also enter the step size or contraction factor of tangent-space Riemannian consensus schemes. In this work, we relax the curvature dependence for a narrower class of horospherical convex (h-convex) functions. We study Distributed Riemannian Online Gradient Descent (D-ROGD), which combines local Riemannian h-subgradient updates with an implicit Fréchet-mean consensus. For h-convex and strongly h-convex local objectives, we establish O(√T) and O(log T) static regret, respectively, matching the corresponding Euclidean rates with respect to T, with network dependence governed solely by the spectral gap. To our knowledge, these are the first curvature-independent regret guarantees for decentralized online optimization on Hadamard manifolds. Experiments on hyperbolic embeddings corroborate the predicted rates, with no observable degradation due to curvature.
ER -