🔢 mathematics

Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions

This paper establishes the first $O(\log T)$ static regret bounds for decentralized online Riemannian optimization of strongly geodesically convex functions by developing a novel network-error analysis compatible with decaying step sizes and extending the result to bandit feedback settings.

Original authors: Zhanyuan Cai, Emre Sahinoglu, Shahin Shahrampour

Published 2026-07-23

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhanyuan Cai, Emre Sahinoglu, Shahin Shahrampour

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to solve a massive puzzle, but they are scattered across a giant, bumpy trampoline instead of sitting at a flat table. In the world of computer science and math, this is called "distributed optimization." Usually, when people try to solve problems together, they assume the ground they stand on is perfectly flat, like a sheet of paper. This makes sharing information easy: you just average your numbers with your neighbors. But in the real world, many problems—like tracking a robot's movement or analyzing complex data shapes—happen on curved surfaces, like the surface of a sphere or a saddle. These are called "Riemannian manifolds."

When these friends try to solve a puzzle on a curved surface, things get tricky. If the surface curves the wrong way, simply averaging their positions might send them off the edge of the puzzle entirely. Furthermore, the puzzle pieces they are trying to fit together change every second; this is "online optimization," where the goal is to make good decisions in real-time without knowing what comes next. The big question researchers have been asking is: If the puzzle pieces are "strongly convex" (meaning they have a clear, steep valley leading to the perfect solution), can a group of friends on a bumpy trampoline find that solution efficiently, or will they get stuck wandering around forever?

This paper, titled "Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions," answers that question with a resounding "yes." The authors, Zhanyuan Cai, Emre Sahinoglu, and Shahin Shahrampour, show that even on these tricky, curved surfaces, a decentralized group can find the best solution with remarkable efficiency. Specifically, they prove that if the problem has that special "strongly convex" shape, the group's mistakes (called "regret") grow extremely slowly over time—mathematically described as growing like the logarithm of time, $O(\log T)$ , rather than the much slower square root, $O(\sqrt{T})$ . While the errors do accumulate, they do so at a rate that is significantly faster and more stable than previous methods allowed.

To understand how they did this, imagine the friends are trying to meet at a specific spot on the trampoline. In the past, researchers had a method where everyone took a fixed-size step toward their neighbors. This worked okay for general problems, but it was too clumsy for the "strongly convex" puzzles where you need to zoom in quickly. The authors realized that to zoom in, you need to take smaller and smaller steps as you get closer to the answer. However, taking smaller steps on a bumpy trampoline creates a new problem: the friends start to drift apart because their steps don't match up perfectly with the curvature.

The team's breakthrough was figuring out how to manage this "drift." They developed a new way to analyze the group's movement that accounts for the changing step sizes and the bumpy ground. They showed that even though the friends are constantly nudging each other and the ground is curving, the group stays tight enough to find the solution. They proved this works for two scenarios: one where everyone can see the exact direction to the goal (full information), and a harder one where they can only peek at the puzzle from two nearby spots and have to guess the direction (bandit feedback).

The paper doesn't just stop at theory; they tested their ideas with simulations. In one experiment, they used a 7-dimensional sphere (a hyper-sphere), which is like a trampoline that curves inward everywhere. In another, they used real-world weather data mapped onto a special shape called a "symmetric positive-definite matrix manifold." In both cases, their new method, which uses those shrinking steps, found the solution much faster and with fewer mistakes than the old methods that took fixed steps. They found that their approach reduced the total error significantly, proving that the "strongly convex" advantage isn't lost just because the friends are on a curved surface and can't talk to a central boss.

The authors are careful to note that while they solved the problem for finding the best static solution, there are still open questions. For instance, their method relies on a standard way of sharing information, and they suspect that using faster "accelerated" sharing techniques could make things even better. They also point out that if the puzzle pieces change too wildly over time (dynamic regret), the math gets even more complicated. But for the steady, strong puzzles they studied, they have successfully shown that a decentralized team on a curved world can be just as efficient as a team on a flat one, provided they know how to take the right steps.

Technical Summary: Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions

1. Problem Statement

The paper addresses the problem of decentralized online optimization on Riemannian manifolds. In this setting, a network of $n$ agents collaboratively minimizes a time-varying global loss function $f_t = \frac{1}{n}\sum_{i=1}^n f_{i,t}$ , where each agent $i$ only observes its local loss $f_{i,t}$ sequentially. The agents communicate only with their neighbors via a fixed communication graph.

The specific focus is on strongly geodesically convex (strongly g-convex) loss functions defined on manifolds with bounded sectional curvature, including those with positive curvature (e.g., spheres). The performance metric is static regret, defined as the difference between the collective cumulative loss of the agents and the cumulative loss of the best fixed decision in hindsight.

The Gap: While centralized online Riemannian optimization and decentralized Euclidean online optimization both achieve an optimal $O(\log T)$ regret rate for strongly convex/strongly g-convex losses (a significant improvement over the $O(\sqrt{T})$ rate for general convex losses), existing decentralized Riemannian methods have only achieved $O(\sqrt{T})$ for g-convex losses. The strongly g-convex regime in the decentralized Riemannian setting remained unexplored due to the incompatibility of decaying step sizes (required for logarithmic rates) with existing network error analyses that assume fixed step sizes.

2. Methodology

The authors propose a two-step algorithm for each agent at every time step $t$ :

Gradient Descent Step: Agent $i$ performs a projected Riemannian gradient descent update:
$y_{i,t+1} = P_X \left( \text{Exp}_{x_{i,t}}(-\eta_t \nabla f_{i,t}(x_{i,t})) \right)$
where $\eta_t$ is a decaying step size and $P_X$ is the projection onto the feasible set $X$ .
Consensus Step: Agent $i$ performs a curvature-aware consensus update using the exponential map and logarithmic map to approximate the weighted Fréchet mean of neighbors' iterates:
$x_{i,t+1} = \text{Exp}_{y_{i,t+1}} \left( s \sum_{j=1}^n w_{ij} \text{Log}_{y_{i,t+1}}(y_{j,t+1}) \right)$
where $s$ is a fixed consensus step size and $W$ is the doubly stochastic communication matrix.

The analysis covers two feedback settings:

Full Information: Agents observe the exact Riemannian gradient.
Two-Point Bandit: Agents observe only function values at two perturbed points and construct a zeroth-order gradient estimator.

Key Technical Challenges and Solutions

Decaying Step Sizes vs. Network Error: Existing analyses for decentralized Riemannian optimization assume fixed step sizes, leading to stationary network error terms. The authors develop a new curvature-aware network error analysis for time-varying (decaying) schedules. They show that the network error accumulates as a time-weighted sum of past step sizes (a geometric convolution) rather than a single static term, and prove this sum remains $O(\log T)$ .
Positive Curvature: On manifolds with positive curvature, the metric projection $P_X$ is not necessarily non-expansive, introducing an extra error term. To control this, the authors employ a shifted decaying step size of the form $\eta_t = O(1/(t+c_0))$ rather than the standard $O(1/t)$ .
Bandit Feedback & Smoothing: In the bandit setting, smoothing the loss function destroys the strong g-convexity property. The authors introduce a novel strong sub-g-convexity argument. They prove that the smoothed surrogate function satisfies a strong convexity-type inequality up to a controllable additive slack. This allows them to maintain the $O(\log T)$ rate by carefully tuning the smoothing parameter $\delta$ (specifically $\delta = O(T^{-2})$ ) jointly with the decaying step size.

3. Key Contributions

First $O(\log T)$ Regret in Decentralized Riemannian Optimization: The paper establishes the first static regret bound of $O(\log T)$ for strongly g-convex losses in the decentralized online Riemannian setting. This bound matches the minimax-optimal rate for strongly convex losses in both Euclidean and centralized Riemannian settings, up to curvature-dependent constants and the spectral gap of the communication matrix.
Novel Network Error Analysis: The authors provide a general analysis for network consensus errors under decaying step sizes. They demonstrate that the error behaves as a geometric convolution of past step sizes and remains logarithmic, resolving the incompatibility between decaying schedules and existing fixed-step-size analyses.
Extension to Bandit Feedback: The work extends the logarithmic regret guarantee to the two-point bandit feedback setting. By developing a strong sub-g-convexity lemma for smoothed surrogates and jointly tuning the smoothing radius with the step size, they preserve the $O(\log T)$ rate despite the degradation of convexity and the introduction of projection/shrinkage errors.

4. Results

Theoretical Bounds:
- Full Information: Theorem 3.2 proves a static regret bound of $R_1 \log(1 + \frac{T\mu D}{L}) + R_2$ .
- Bandit Feedback: Theorem 4.5 proves an expected static regret bound of $R'_1 \log(1 + \frac{T\mu D}{dL}) + R'_2$ .
- Both bounds depend on the spectral gap $(1-\sigma_2(W))^{-1}$ , reflecting the cost of decentralization.
Numerical Experiments:
- Hyper-sphere ( $S^7$ ): Experiments on a positively curved manifold confirm that the proposed strongly g-convex schedule achieves logarithmic growth in regret, significantly outperforming the $O(\sqrt{T})$ baseline. Larger consensus step sizes were observed to reduce regret.
- SPD Manifold (FLUXNET2015): Using a real-world dataset on the manifold of Symmetric Positive Definite matrices (a Hadamard manifold), the proposed method achieved a final regret of ~46.8 compared to ~76.9 for the convex baseline in the full-information setting. The bandit variant also showed sublinear growth, though with higher regret due to zeroth-order estimation variance.

5. Significance and Claims

The paper claims to resolve the fundamental question of whether the logarithmic regret improvement from strong convexity can be attained in decentralized online Riemannian optimization. The authors affirmatively answer this by:

Bridging the gap between centralized and decentralized Riemannian optimization rates for strongly convex objectives.
Providing the first theoretical framework that handles decaying step sizes in decentralized Riemannian consensus, a necessary condition for logarithmic regret.
Demonstrating that strong g-convexity can be exploited even in bandit settings on manifolds with positive curvature, provided specific geometric constraints (bounded diameter, injectivity radius) are met.

The work is presented as a foundational step, noting that while it achieves the optimal rate for static regret, future work could explore accelerated gossip schemes to improve the dependence on the spectral gap and extend these results to dynamic regret settings.