Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives
This work addresses a limitation in online optimization on Hadamard manifolds for researchers in optimization and machine learning, though it is incremental as it builds on prior convexity frameworks.
The paper tackled the problem of poor regret bounds scaling with manifold curvature in online Riemannian optimization by analyzing Riemannian online gradient descent for horospherically convex functions, achieving curvature-independent O(√T) and O(log(T)) regret guarantees that match Euclidean results.
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(\sqrt{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échet mean computation, showing the application of h-convexity in practice.