math.OCJul 22, 2026

Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions

Authors: Zhanyuan CaiEmre SahinogluShahin Shahrampour

Organizations: Department of Mechanical & Industrial Engineering at Northeastern University, Boston, MA 02115, USA

Abstract

We study decentralized online optimization for strongly geodesically convex (strongly g-convex) losses on Riemannian manifolds with bounded sectional curvature, including positively curved manifolds. In centralized Riemannian optimization, strong g-convexity tightens the optimal regret from O(T)O(\sqrt{T}) to O(logT)O(\log T), where TT is the time horizon; in the decentralized Riemannian setting, however, existing methods address only g-convex losses, leaving the strongly g-convex regime unexplored. One challenge is that the required decaying step size in the centralized regime is incompatible with existing network-error analyses, which typically assume a fixed step size. First, we provide a general network-error analysis for time-varying schedules. Next, we build on this analysis to establish the first O(logT)O(\log T) static regret bound for decentralized online Riemannian gradient descent, matching the minimax-optimal rate for strongly-convex Euclidean online optimization. Finally, we prove the same O(logT)O(\log T) regret bound for the two-point bandit feedback setting using novel strong subconvexity arguments for the smoothed versions of the loss functions.

Explore similar work

CardsList
  1. Small Gradient Norm Regret for Online Convex Optimization

    Jan 20, 2026Wenzhi Gao, Chang He, Madeleine Udell