Distributed algorithms optimize functions without curvature limits
Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
Machine Learning
Summary
This paper looks at how to solve optimization problems across a network when the space has certain curved shapes, called Hadamard manifolds. Previous methods needed to know details about the space’s curvature to guarantee good performance. The authors find a way to guarantee good learning performance without needing curvature information for a narrower type of function called horospherical convex. Their method achieves performance similar to that on flat spaces, and experiments with hyperbolic data support their findings.
What this means in practice
- •For machine learning engineers: Optimize models distributed across multiple devices operating on curved geometric data without requiring curvature estimates.
- •For network algorithm designers: Design consensus algorithms for decentralized systems that maintain performance independently of manifold curvature.
Authors
Zhanyuan Cai, Emre Sahinoglu, Shahin Shahrampour
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(\sqrt{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.