Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions

Source

• Source name: arXiv
• Source kind: paper
• Authors / organization: Zhanyuan Cai, Emre Sahinoglu, Shahin Shahrampour
• Venue: arXiv: math.OC
• Published: 2026-07-22
• Collected: 2026-07-23
• URL: http://arxiv.org/abs/2607.20316v1
• PDF: https://arxiv.org/pdf/2607.20316v1
• DOI: UNKNOWN

Plain-Language Brief

The authors study decentralized online optimization for specific types of functions (strongly geodesically convex) on Riemannian manifolds with certain curvature properties. They propose a new network-error analysis to address time-varying schedules and establish a logarithmic regret bound for decentralized online Riemannian gradient descent, matching the optimal rate for strongly-convex Euclidean optimization.

What the Document Says

• The study is on 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(sqrt(T)) to O(log T), where T is the time horizon.
• However, in the decentralized Riemannian setting, existing methods only address g-convex losses, leaving the strongly g-convex regime unexplored.
• A 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.
• The authors provide a general network-error analysis for time-varying schedules.
• They then use this analysis to establish an O(log T) static regret bound for decentralized online Riemannian gradient descent.
• Finally, they prove the same 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.

Key Concepts Mentioned

• Decentralized online optimization
• Strongly geodesically convex functions
• Riemannian manifolds
• Bounded sectional curvature
• Positively curved manifolds
• Time-varying schedules
• Network-error analysis
• Static regret bound
• Two-point bandit feedback

Claims Made by the Document

• Establishing O(log T) static regret bound for decentralized online Riemannian gradient descent.
• Proving the same O(log T) regret bound for two-point bandit feedback using novel strong subconvexity arguments.

Evidence Used

• The study details a new network-error analysis for time-varying schedules and the derived regret bounds.

Methods / Approach

• General network-error analysis for time-varying schedules
• Decentralized online Riemannian gradient descent
• Novel strong subconvexity arguments for smoothed versions of the loss functions

Limitations Stated by the Authors

The authors admit that the required decaying step size in the centralized regime is a challenge to incorporate with existing network-error analyses.

Limitations Noted by the Agent

Agent interpretation — not from the source.

The study focuses on strongly geodesically convex functions, leaving other types of functions unexplored.

Open Questions

• Can these results be extended to other types of functions or settings?
• What are the implications for non-positively curved manifolds?

Notes for Future Q&A

May include interpretation. Labeled where it does.

The authors focus on strongly geodesically convex functions, a specific type of function on Riemannian manifolds. The study does not explore other types of functions or non-positively curved manifolds.

Raw Abstract / Excerpt

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(\sqrt{T})$ to $O(\log T)$, where $T$ 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(\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(\log T)$ regret bound for the two-point bandit feedback setting using novel strong subconvexity arguments for the smoothed versions of the loss functions.