Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives
Emre Sahinoglu, Shahin Shahrampour · 2025
Read Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives by Emre Sahinoglu, Shahin Shahrampour (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11236.txt.
Introduction
Emre Sahinoglu and Shahin Shahrampour prove learning guarantees on curved spaces in this 2025 paper. Online optimization makes a decision, sees the cost, and adjusts, round after round. On curved spaces called Hadamard manifolds, earlier guarantees for a natural convexity notion worsened as the space curved more, which punished exactly the settings where the geometry helps.
Working instead with horospherical convexity, the authors analyze online gradient descent and prove regret bounds that do not depend on curvature at all. For the plain and strong versions of the notion, the bounds match the best flat-space rates. Experiments on the space of positive definite matrices, covering robust estimation and averaging problems, show the theory at work.
Catalog record
| CREATOR | Emre Sahinoglu, Shahin Shahrampour |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-11236
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives Emre Sahinoglu, Shahin Shahrampour Abstract 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 ) O(\sqrt{T}) and O ( log ( T ) ) 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 M -estimation and online Fréchet mean computation, showing the application of h-convexity in practice. I Introduction Riemannian optimization has emerged as a powerful framework for solving constrained optimization problems where the feasible set naturally possesses a geometric structure. Unlike Euclidean methods that rely on projections to maintain feasibility, Riemannian approaches exploit the intrinsic geometry of the manifold to design algorithms that are both efficient and theoretically principled [ 1 ] . In control theory, Riemannian optimization has been applied to the Linear–Quadratic Regulator (LQR) problem [ 27 ] , system identification [ 25 ] , consensus and synchronization on nonlinear state spaces [ 21 ] , and covariance estimation on the manifold of positive-definite matrices [ 18 ] . In machine learning, manifold-constrained optimization problems arise in low-rank matrix completion [ 28 ] , principal component analysis [ 10 ] , dictionary learning [ 8 ] , and representation learning in hyperbolic spaces [ 19 ] . By aligning the optimization algorithms with the underlying geometry, Riemannian optimization not only ensures feasibility but also uncovers algorithmic principles that are central to modern large-scale learning and control applications. While Riemannian optimization has been extensively studied in offline settings, many modern applications require algorithms that adapt to sequential data. This motivates the study of online Riemannian optimization , where at each round a learner selects a point on a subset of the manifold and subsequently observes a loss function defined on that point [ 30 , 31 ] . A common performance metric for this setting is regret , which compares the cumulative loss of the online sequence with that of the best decision in hindsight. Online Riemannian optimization extends the classical theory of online convex optimization [ 12 ] to non-Euclidean spaces, introducing new challenges stemming from curvature, nonlinearity, and the lack of global linear structure. These challenges are particularly relevant in adaptive control, distributed learning, and streaming machine learning tasks, where the decision variable belongs to various manifolds, such as Lie groups, spheres, or the set of positive-definite matrices [ 8 ] , [ 16 , 23 ] . One central challenge in extending the optimization theory to manifolds is the proper generalization of convexity. The natural analogue of Euclidean convexity along line segments is the geodesic convexity (g-convexity), quantifying convexity along geodesics [ 34 ] . While this notion provides a useful foundation for convergence analysis, it also introduces nontrivial geometric complexities since classical inequalities, such as the law of cosines, take curvature-dependent forms that affect the attainable convergence rates. On Hadamard manifolds, simply connected spaces with non-positive curvature, curvature-adjusted cosine or comparison inequalities replace Euclidean quadratic expansions, rendering convergence guarantees more delicate [ 34 ] . These curvature-induced corrections highlight the fundamental differences between Euclidean and Riemannian settings, where regret bounds and convergence rates deteriorate due to curvature-dependent constants, involving both sectional curvature and the diameter of the feasible set. This motivates the exploration of alternative convexity notions, such as horospherical convexity (h-convexity), that more effectively capture the asymptotic geometric behavior in non-positively curved spaces [ 9 , 11 , 13 , 15 ] . In this letter, we study Riemannian online optimization for h-convex and strongly h-convex objectives, characterized by Busemann functions as a natural extension of affine functions in Euclidean spaces. While recent work on g-convex objectives establishes regret bounds that scale poorly with respect to the lower bound of the sectional curvature, we aim for curvature-independent guarantees by focusing on h-convex objectives instead. In what follows, • Section II reviews the background on online optimization and convexity notions on manifolds. We discuss both inner and outer characterizations of convexity on Hadamard manifolds and introduce h-convex objectives, defined via Busemann functions. In addition, we present a geometric lemma that establishes an inequality for geodesic triangles, which plays a key role in deriving the regret bound for strongly h-convex objectives. • Section III presents the technical assumptions as well as the Riemannian Online Gradient Descent (ROGD) algorithm. We analyze the regret rates, establishing O(\sqrt{T}) regret for h-convex objectives and O(\log(T)) regret for strongly h-convex objectives. Notably, these bounds match the corresponding Euclidean regret rates and do not involve curvature-dependent terms. • Section IV illustrates the performance of ROGD via numerical experiments. We consider the manifold of symmetric positive-definite (SPD) matrices, endowed with the affine-invariant metric. Our testbeds are the Tyler’s M -estimator problem for h-convex objectives and the Fréchet mean estimation for strongly h-convex objectives. Consistent with our theoretical claims, the numerical results demonstrate that ROGD achieves sublinear regret in both cases. I-A Literature Review Riemannian Optimization. Over the past two decades, there has been a growing interest in Riemannian optimization, motivated by the prevalence of problems with non-Euclidean constraints in machine learning, signal processing, and control [ 1 , 10 , 22 ] . Many classical Euclidean algorithms have been successfully extended to the Riemannian setting. Foundational work formalized retractions, vector transports, and convergence guarantees for first-order and second-order methods [ 5 ] , while stochastic extensions such as Riemannian SGD [ 4 ] , variance-reduced methods [ 24 , 33 ] , and decentralized techniques [ 7 , 26 ] provided practical tools for optimization on curved spaces. To capture convexity in the Riemannian setting, the notion of g-convexity was introduced, enabling the complexity analysis of first-order methods, mirroring Euclidean convergence results with the addition of curvature-dependent terms [ 34 , 29 ] . More recently, an alternative notion of convexity, i.e., h-convexity, has been explored, motivated by outer characterizations of convexity via Busemann functions and horospheres, leading to a new framework for optimization in non-positively curved Hadamard manifolds [ 9 , 11 , 15 ] . Online Riemannian Optimization. The extension of Euclidean online convex optimization (OCO) to manifolds has gained significant attention recently, fueled by applications where decisions evolve on curved spaces. Building on OCO several works have analyzed g-convex functions on Hadamard manifolds, showing regret bounds for first-order and zeroth-order (bandit) ROGD, which depend on both the sectional curvature and the time horizon [ 31 , 20 ] . Beyond basic ROGD, optimistic and projection-free variants also attain static or dynamic regret guarantees under g-convexity [ 14 , 32 ] , while bandit and tracking settings quantify how curvature perturbs rates in time-varying problems [ 17 ] . Extensions also study positively curved spaces via adapted projection arguments, yielding analogous regret bounds under curvature constraints [ 31 ] , and decentralized settings on