Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions

Source: arXiv:2607.20316 · Published 2026-07-22 · By Zhanyuan Cai, Emre Sahinoglu, Shahin Shahrampour

TL;DR

This paper addresses the problem of decentralized online optimization for strongly geodesically convex (strongly g-convex) loss functions defined on Riemannian manifolds with bounded sectional curvature, including positively curved cases where classical Euclidean notions fail. Prior decentralized Riemannian methods only guaranteed O(√T) regret for g-convex losses using fixed step sizes. The authors develop a novel analysis framework for decaying step sizes that harmonizes the time-varying nature of gradient steps with network consensus errors across manifold-valued iterates. This allows them to prove the first O(log T) static regret bounds matching centralized and Euclidean strongly convex rates, even in the presence of positive curvature which complicates projection and consensus steps. They further extend these guarantees to a two-point bandit feedback setting via a novel strong sub-g-convexity concept for smoothed surrogate losses, preserving the logarithmic regret rate despite gradient estimation challenges. Empirical results on an S7 sphere and SPD matrix manifold using FLUXNET2015 data validate improved regret and consensus errors compared to baselines, illustrating practical benefits of their theoretical advances.

Key findings

• Established first O(log T) static regret for decentralized online Riemannian gradient descent on µ-strongly g-convex losses with decaying step size η_t = 1/(µ t + L/D) (Theorem 3.2).
• Proved general network error bound for consensus step with time-varying step sizes showing the error accumulation behaves as a geometric convolution sum and remains O(log T) under suitable consensus step size (Lemma 3.1).
• Extended logarithmic regret guarantees to two-point bandit feedback setting with gradient estimator variance controlled by smoothing radius δ = T^(-2) (Theorem 4.5), improving prior g-convex O(√T) results.
• Showed projection step on positively curved manifolds requires shifted decaying step size regime η_t = O(1/(t + c0)) to control additional projection errors introduced by curvature.
• Numerical experiments on S7 sphere with n=10 agents confirm strongly g-convex schedule stabilizes regret growth to O(log T) versus O(√T) baseline; bandit feedback incurs higher but still sublinear regret.
• On FLUXNET2015 SPD manifold data with n=20 agents, strongly g-convex full information method achieved final regret 46.83, outperforming convex baseline at 76.97 and local-only baseline at 106.08 (Table II).
• Strongly g-convex decentralized optimization attains smaller consensus error than convex-step baseline, indicating tighter agreement among nodes.
• The spectral gap dependence enters regret bounds as (1 - σ_2(W))^(-1), quantifying the communication cost of decentralization.

Threat model

The adversary is an adaptive environment selecting sequences of strongly geodesically convex loss functions per agent at each round. The agents lack future loss knowledge and only receive local gradient or bandit feedback. The adversary cannot manipulate the communication network topology or inject false messages. Agents trust neighbors for information exchange. Attacks or Byzantine behavior are not modeled. The focus is on performance degradation due to decentralized partial information and geometric complexities, not adversarial manipulation.

Methodology — deep read

1. Threat model & assumptions: The problem considers a network of n agents optimizing a time-varying global objective given by the average of local strongly g-convex loss functions {f_{i,t}} on a compact, uniquely g-convex subset of a d-dimensional Riemannian manifold M with bounded sectional curvature K_min ≤ K ≤ K_max. The topology is modeled by a symmetric, doubly stochastic matrix W with second largest singular value σ_2(W)<1, ensuring connectivity. Agents only have local access to losses and communicate with neighbors. The adversary chooses adaptive losses but feedback is restricted to full-gradient or two-point bandit (zeroth-order) observations. Strong geodesic convexity with parameter µ>0 is assumed, guaranteeing quadratic growth along geodesics.

2. Data and preprocessing: No classical data; problem is online with T iterations. Losses are generated or sampled satisfying µ-strong g-convexity and Lipschitz continuity over domain X. The domain diameter D and curvature bounds enforce injectivity radius constraints ensuring well-defined exponential and logarithm maps and projections.

3. Algorithm and architecture: The algorithm alternates between two steps each round t: (I) a projected Riemannian gradient descent step per agent i using exponential map and projection onto X with decaying step size η_t, and (II) a curvature-aware consensus step moving each iterate toward the weighted Fréchet mean approximation of neighbors' updated points, using a consensus step size s tuned to curvature constants. For the bandit setting, the Riemannian gradient is replaced by a two-point estimator computed from function evaluations at points offset by ±δ along a sampled unit tangent vector. Due to smoothing, iterates are constrained to a shrinking feasible set (1-τ)X to keep queried points feasible.

4. Training regime: Runs for T rounds with decaying step size η_t = 1/(µ t + L/D) for full information and η_t = 1/(µ t + d L / D) combined with smoothing δ = T^-2 and shrinkage τ = δ θ / r for bandit setting. Consensus step size s is set based on curvature constants to guarantee contraction. Agents initialize from a common point xi,1 = x1.

5. Evaluation protocol: Performance is measured by static regret, comparing cumulative network average loss against best fixed point x* in hindsight. Regret bounds for both full-information and bandit feedback are derived theoretically. Empirical evaluation uses synthetic data on S7 sphere manifold and real data (FLUXNET2015) on SPD(5) manifold. Metrics reported include static regret growth curves, final cumulative regret values, and network consensus errors (average pairwise squared distances). Comparisons are made versus g-convex baselines (fixed or slower step decay), local-only optimization without communication, and centralized optimization.

6. Reproducibility: Code released at reported GitHub repo. The experiments are reproducible following scripts with provided hyperparameters. Theoretical constants and proof details are in appendices. Dataset (FLUXNET2015) is public.

Concrete example (full info case): On S7 sphere, 10 agents run the two-step updates with η_t = 1/(µ t + L/D) and s tuned to curvature constants. Each agent’s local loss is squared geodesic distance to a moving reference point. The consensus step aligns via weighted average of logarithms of neighbors’ positions. Network error accumulates as a time-weighted sum of past step sizes but bounded by O(log T) due to geometric contraction factor ρ < 1. The resulting combined regret, involving the online optimization error and consensus error, is rigorously upper bounded by O(log T), verified by slowly growing empirical regret plots stabilizing after a few hundred rounds.

Technical innovations

• Developed a curvature-aware network error analysis for decentralized Riemannian optimization with time-varying decaying step sizes, overcoming incompatibility with fixed-step-size assumptions in prior work.
• Proved the first O(log T) static regret bounds for decentralized online optimization of µ-strongly geodesically convex losses on manifolds including positively curved settings.
• Introduced a notion of strong sub-g-convexity for smoothed surrogates to extend logarithmic regret guarantees to two-point bandit feedback scenarios within decentralized Riemannian online optimization.
• Identified and handled projection non-expansiveness failures on positively curved manifolds by adopting a shifted decaying step size η_t = O(1/(t + c_0)) to control additional curvature-induced errors.

Datasets

• Synthetic S7 sphere data — 10 agents, 1000 rounds — synthetic in paper
• FLUXNET2015 — 20 agents, 208 weeks — public meteorological dataset

Baselines vs proposed

• G-convex decentralized online Riemannian gradient (Hu et al. [19]): static regret = O(√T) vs proposed strongly g-convex: O(log T)
• Local-only baseline (no consensus): final regret = 106.08 vs strongly g-convex decentralized: 46.83 on FLUXNET2015 full-information
• Convex-step-size decentralized (baseline): final regret = 76.97 vs strongly g-convex: 46.83 on FLUXNET2015 full-information
• Centralized full information: regret = 2.52 vs decentralized strongly g-convex: 46.83 (expected consensus cost)
• G-convex bandit baseline: regret 169.71 vs proposed strongly g-convex bandit: 97.3 on FLUXNET2015
• Centralized bandit: 59.23 regret vs decentralized strongly g-convex bandit: 97.3

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.20316.

Fig 1: STATIC REGRET FOR STRONGLY G-CONVEX LOSSES WITH

Fig 2: STRONGLY G-CONVEX SCHEDULE, O(log T ), VERSUS G-

Fig 3: FLUXNET2015 RESULTS. STRONGLY G-CONVEX REGRET,

Fig 4 (page 12).

Fig 5 (page 12).

Fig 6 (page 12).

Limitations

• Regret bounds include unaccelerated spectral-gap dependence (1 - σ2(W))^(-1), possibly improvable by adapting accelerated gossip techniques to manifolds.
• The analysis is restricted to static regret; dynamic regret with time-varying comparators remains unexplored and challenging due to curvature and decentralization.
• The strong sub-g-convexity in the bandit setting introduces additive slack terms scaling with smoothing radius, complicating parameter tuning and possibly limiting practical smoothing choices.
• Feasibility of two-point bandit queries relies on shrinking the feasible set, which may limit practical domains or require domain-specific geometric parameters that are hard to estimate.
• The theoretical constants hidden in the bounds depend on manifold curvature and geometry, which can be large or unknown in real-world problems, affecting convergence speed in practice.
• Empirical validation is limited to two manifolds with moderate-scale agent networks; generalization to larger networks or other manifold classes is not demonstrated.

Open questions / follow-ons

• Can Euclidean accelerated gossip methods for faster consensus rates be extended to Riemannian manifolds to reduce the spectral-gap dependence in regret?
• What are achievable dynamic regret bounds for decentralized strongly g-convex online optimization on manifolds, especially under time-varying comparators?
• How can the smoothing parameter and shrinking feasible sets in the bandit setting be adaptively tuned or relaxed for better practical performance without sacrificing regret guarantees?
• Can the analysis be generalized to broader classes of nonconvex or weakly convex losses on manifolds to handle more realistic decentralized scenarios?

Why it matters for bot defense

This work deepens the theoretical understanding of decentralized online optimization on curved spaces, which is relevant when CAPTCHA and bot-defense features rely on distributed sensor or agent networks operating over manifold-valued data (e.g., rotations, probability simplices). The established logarithmic regret guarantees demonstrate that strongly geodesically convex cost functions allow fast convergence even with partial bandit feedback and communication constraints. This inspires bot-defense practitioners to consider incorporating geometric optimization techniques when aggregating decentralized signals or learning online in complex nonlinear domains. The curvature-aware consensus and decaying step size strategy highlight critical algorithmic components needed to achieve stable, provably efficient distributed learning in such settings.

However, the technical depth and geometric assumptions suggest careful tuning and validation are necessary before deployment in real-world CAPTCHA pipelines. Also, the work does not address adversarial manipulation or Byzantine robustness explicitly, which remain open challenges in bot defense. Nonetheless, the paper's framework offers valuable tools and theoretical baselines for practitioners designing distributed online learning mechanisms on manifold-structured data streams common in advanced bot detection scenarios.

Cite

@article{arxiv2607_20316,
  title={ Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions },
  author={ Zhanyuan Cai and Emre Sahinoglu and Shahin Shahrampour },
  journal={arXiv preprint arXiv:2607.20316},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.20316}
}

Read the full paper

• arXiv:2607.20316 (abstract)
• arXiv:2607.20316 (PDF)