🔢 mathematics

Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

This paper proposes a decentralized online Riemannian optimization framework that overcomes the limitations of Hadamard manifolds by introducing a curvature-aware consensus step, achieving an $O(\sqrt{T})$ regret bound for both full-information and two-point bandit feedback settings on manifolds with possibly positive curvature.

Original authors: Emre Sahinoglu, Shahin Shahrampour

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: 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 hikers trying to find the lowest point in a vast, foggy valley. In a flat, straight world (like a standard computer screen), they could easily walk toward the center, share their locations, and agree on a single spot to meet. This is how most current "decentralized" AI algorithms work: everyone shares data, averages their positions, and moves toward a common goal.

But what if the world isn't flat? What if the ground is curved, like the surface of a sphere or a saddle? This is the world of Riemannian manifolds. In this paper, the authors tackle a very difficult problem: How do you get a group of agents (like hikers or computers) to agree on a solution and optimize their path when the ground they are walking on is curved, potentially bulging outward (positive curvature), and they can only talk to their immediate neighbors?

Here is a breakdown of their work using simple analogies:

1. The Problem: The "Curved Ground" Challenge

Most previous research assumed the ground was either perfectly flat or curved inward (like a bowl). This made it easy for the hikers to agree on a meeting spot. However, the authors wanted to solve the problem on positively curved surfaces (like the surface of a ball).

On a ball, the rules of geometry change. If two hikers walk in straight lines (geodesics) that start parallel, they might eventually crash into each other. This makes it hard to "average" their positions. If you try to use the old, flat-world math to tell them where to meet, they might end up in the wrong place or get stuck.

2. The Solution: A New Way to "Meet Up" (Consensus)

The core of the paper is a new method for the "consensus step"—the moment the hikers decide where to gather.

The Old Way: In flat spaces, you just take the average of everyone's coordinates.
The New Way: On a curved ball, you can't just average coordinates. The authors designed a "curvature-aware" step. Imagine the hikers are holding elastic bands connecting them to their neighbors. Instead of pulling in a straight line, they pull along the curve of the ground.
The Breakthrough: They proved that even on this tricky, bulging ground, if the hikers pull with the right amount of force (a specific "step size"), they will still converge to a single point quickly. They managed to balance the "stretchiness" of the ground so that the group doesn't scatter.

3. The Goal: Learning While Moving (Online Optimization)

The hikers aren't just trying to meet; they are trying to find the best spot to meet while the terrain changes every second (this is "online" optimization).

Full Information: In the first scenario, every hiker can see the slope of the ground right under their feet (they have the "gradient"). The authors showed that even with this curved ground and limited communication, the group can find the best spot almost as fast as if they were in a flat world. They proved the "regret" (the difference between their performance and the perfect performance) grows very slowly, at a rate of the square root of time ( $\sqrt{T}$ ).
The "Blind" Scenario (Bandit Feedback): In the second, harder scenario, the hikers are blindfolded. They can't see the slope. They can only poke the ground at two nearby points to feel if it's higher or lower. This is like trying to find the bottom of a valley by tapping your cane twice.
- The authors invented a clever "smoothing" trick. Instead of trying to guess the slope from one poke, they simulate a "smoothed" version of the terrain.
- Even with this blindness and the curved ground, they proved the group can still find the optimal spot with the same slow-growing regret rate ( $\sqrt{T}$ ).

4. The Proof: Geometry Tools

To make this work, the authors had to invent new mathematical "rulers" and "compasses" (geometric tools) that work on any curved surface, whether it curves up or down. They showed that even though the ground is weird, you can still measure distances and angles accurately enough to guarantee the hikers will eventually succeed.

Summary

Think of this paper as a new rulebook for a group game played on a giant, bouncy trampoline instead of a flat floor.

The Challenge: The trampoline makes it hard to agree on a center point or find the lowest spot.
The Innovation: The authors created a new way for the players to communicate and move that respects the bounciness of the trampoline.
The Result: They proved that whether the players can see the whole trampoline or are just poking it blindly, they can still find the best spot efficiently, without getting lost in the curves.

This work is significant because it moves beyond the "easy" flat or bowl-shaped worlds and shows that decentralized learning can work effectively even on the most complex, curved geometries.

Technical Summary: Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

Problem Formulation
This paper addresses the problem of decentralized online Riemannian optimization over manifolds that may possess positive curvature, extending beyond the restrictive setting of Hadamard manifolds (which have non-positive curvature). The goal is for a network of $n$ agents to collaboratively minimize a global objective function $f_t(\cdot) = \frac{1}{n}\sum_{i=1}^n f_{i,t}(\cdot)$ at each time step $t$ , where each agent $i$ only observes its local loss function $f_{i,t}$ . The agents operate under two feedback regimes:

Full Gradient Feedback: Agents have access to the exact Riemannian gradient of their local functions.
Two-Point Bandit Feedback: Agents only receive function evaluations at two nearby points, requiring the construction of gradient estimators.

The decision variables and the comparator point $x^*$ are constrained to a geodesically convex subset $\mathcal{X}$ of a Riemannian manifold $\mathcal{M}$ . The primary technical challenges stem from the lack of global convexity in positively curved spaces and the non-linearity of the manifold, which complicates the standard consensus steps used in Euclidean decentralized optimization.

Methodology
The authors propose a unified framework that relies on three core methodological components:

Curvature-Aware Consensus Step:
The paper utilizes a specific consensus update rule defined in the tangent space:
$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 $y_{i,t+1}$ is the result of the local gradient update and projection, $W$ is a doubly stochastic communication matrix, and $s$ is a consensus step-size. Unlike previous works that rely on the linearity of an ambient space or the global convexity of Hadamard manifolds, this work analyzes the linear variance reduction of this step on general manifolds with bounded sectional curvature $K \in [K_{\min}, K_{\max}]$ . The analysis optimizes the step-size $s$ to balance the trade-off between the convexity and smoothness properties distorted by curvature.
Full Information Algorithm (Algorithm 1):
In the full gradient setting, agents perform a Riemannian gradient descent step followed by a projection onto the feasible set $\mathcal{X}$ , and then execute the consensus step described above. The regret analysis decomposes the total error into a network error (discrepancy between local variables and the global Fréchet mean) and a local optimization error. The network error is bounded using the linear variance reduction property established in the consensus analysis.
Bandit Feedback Algorithm (Algorithm 2) and Smoothing:
For the two-point bandit setting, the authors employ a randomized smoothing technique. Agents sample directions uniformly from the tangent space sphere and evaluate the function at two points separated by a smoothing parameter $\delta$ . This generates a gradient estimator $g^\delta_{i,t}$ .
- Subconvexity Analysis: Since smoothing destroys strict geodesic convexity, the authors establish that the smoothed objective is $\delta$ -geodesically subconvex. They prove that the deviation from perfect convexity is linearly controlled by $\delta$ .
- Domain Shrinkage: To ensure feasibility when evaluating points near the boundary, the algorithm operates on a shrinking subset $(1-\tau)\mathcal{X}$ of the original domain.

Key Contributions
The paper makes the following specific technical contributions:

Linear Variance Reduction on General Manifolds: The authors establish the linear convergence of the consensus step for manifolds with both positive and negative curvature (Theorem III.2). This is achieved by optimizing the consensus step-size to manage the trade-off between convexity and smoothness, a challenge not present in the Hadamard setting where negative curvature naturally reinforces convexity.
$O(\sqrt{T})$ Regret for Full Information: For general manifolds (potentially positively curved), the paper proves a static regret bound of $O(\sqrt{T})$ for the decentralized gradient descent algorithm (Theorem IV.2). This matches the optimal rate known in Euclidean settings, demonstrating that decentralization and positive curvature do not asymptotically degrade the regret rate.
First $O(\sqrt{T})$ Regret for Bandit Feedback: The paper provides the first static regret bound of $O(\sqrt{T})$ for decentralized online Riemannian optimization under two-point bandit feedback (Theorem V.2). This is achieved using a computationally efficient gradient estimator and a rigorous analysis of the subconvexity of smoothed objectives.
Generalized Geometric Tools: The authors develop and extend geometric comparison inequalities (Lemmas VII.3–VII.4) valid for manifolds with arbitrary signs of curvature bounds, providing constants explicitly defined in terms of $K_{\min}$ and $K_{\max}$ .

Results

Theoretical Bounds: The derived static regret bounds are $O(\sqrt{T})$ for both full gradient and two-point bandit feedback settings. The constants in these bounds depend on the manifold's curvature, the network connectivity (via the second largest singular value of $W$ ), and the diameter of the domain, but the asymptotic rate with respect to the time horizon $T$ remains optimal.
Numerical Experiments: Experiments were conducted on a 16-dimensional unit sphere (a positively curved manifold) with 50 agents. The results confirm that the algorithms converge, with cumulative regret increasing as expected. The experiments show that larger consensus step-sizes generally lead to lower regret due to faster consensus rates, and that the bandit setting exhibits slower convergence than the full-information setting due to gradient estimation variance.

Significance
The paper claims significance in bridging a critical gap in the theoretical understanding of decentralized optimization on curved spaces.

Beyond Hadamard: Prior theoretical guarantees for decentralized Riemannian optimization were largely restricted to Hadamard manifolds. This work extends these guarantees to manifolds with positive curvature, where geodesic distances do not induce globally convex structures.
Bandit Setting: It addresses the previously unexplored area of decentralized Riemannian optimization under bandit feedback, providing the first sublinear regret bounds for this setting.
Optimality: The results demonstrate that the fundamental $O(\sqrt{T})$ regret rate achievable in Euclidean decentralized online optimization is preserved even in the presence of positive curvature and limited feedback, provided that curvature-aware consensus and smoothing techniques are employed.

The authors note that while the bounds are optimal in terms of $T$ , future work could investigate the specific dependence of these bounds on network connectivity and curvature parameters, and design algorithms provably optimal with respect to those specific parameters.