Paper deep dive
Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions
Zhanyuan Cai, Emre Sahinoglu, Shahin Shahrampour
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 7/23/2026, 2:01:32 AM
Summary
This paper addresses decentralized online optimization for strongly geodesically convex (strongly g-convex) losses on Riemannian manifolds with bounded sectional curvature. It establishes the first O(log T) static regret bound for decentralized online Riemannian gradient descent, overcoming challenges related to decaying step sizes and network error analysis. The work also extends these results to the two-point bandit feedback setting using novel strong subconvexity arguments.
Entities (10)
Relation Signals (8)
Decentralized Online Riemannian Optimization → achieves → O(log T) Regret Bound
confidence 95% · establish the first O(log T) static regret bound for decentralized online Riemannian gradient descent
Decentralized Online Riemannian Optimization → appliesto → Strongly Geodesically Convex Functions
confidence 95% · We study decentralized online optimization for strongly geodesically convex (strongly g-convex) losses
Z. Cai → affiliatedwith → Northeastern University
confidence 90% · Z. Cai, E. Sahinoglu and S. Shahrampour are with the Department of Mechanical & Industrial Engineering at Northeastern University
This work → fundedby → NSF Award ECCS-2240788
confidence 90% · This work is supported in part by NSF Award ECCS-2240788
Decentralized Online Riemannian Optimization → handles → Two-Point Bandit Feedback
confidence 90% · prove the same O(log T) regret bound for the two-point bandit feedback setting
Decentralized Online Riemannian Optimization → requires → Network Error Analysis
confidence 85% · First, we provide a general network-error analysis for time-varying schedules.
Decentralized Online Riemannian Optimization → uses → Decaying Step Size
confidence 85% · required decaying step size in the centralized regime is incompatible with existing network-error analyses
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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(\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.
Tags
Links
- Source: https://arxiv.org/abs/2607.20316v1
- Canonical: https://arxiv.org/abs/2607.20316v1
Trouble viewing inline? Open PDF directly →
Full Text
84,731 characters extracted from source content.
Expand or collapse full text
Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions Zhanyuan Cai Emre Sahinoglu and Shahin Shahrampour This work is supported in part by NSF Award ECCS-2240788 as well as NSF CAREER Award ECCS-2442321.Z. Cai, E. Sahinoglu and S. Shahrampour are with the Department of Mechanical & Industrial Engineering at Northeastern University, Boston, MA 02115, USA. emails:cai.zha,sahinoglu.m, s.shahrampour@northeastern.edu. 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 (T)O( T) to (logT)O( 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 (logT)O( 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 (logT)O( T) regret bound for the two-point bandit feedback setting using novel strong subconvexity arguments for the smoothed versions of the loss functions. 1 Introduction Distributed online optimization has been studied extensively in the control literature with applications in multi-robot target tracking, distributed resource allocation and distributed economic dispatch. In this setting, a network of n agents collaboratively minimizes a time-varying global loss ft=1n∑i=1nfi,tf_t= 1n _i=1^nf_i,t while each agent i observes only its local loss fi,tf_i,t sequentially and can exchange information with neighboring agents. The performance of distributed online algorithms is measured by regret, the difference between the collective cumulative loss of agents and that of the best single decision in hindsight. In Euclidean spaces, consensus-based gradient methods effectively solve this problem and achieve sublinear regret bounds [18, 33, 4, 42]. These guarantees, however, rest on the vector-space structure of Euclidean space and do not extend readily to curved manifolds on which many modern engineering problems are naturally posed. Such manifold optimization problems are prevalent: collaborative geometric estimation for SLAM [35], distributed PCA on orthogonality-constrained manifolds [16], and consensus-based multi-robot active mapping over probability-simplex and SE(3)SE(3) variables [6]. In these manifold optimization problems, the Euclidean consensus update is inapplicable, since weighted averaging requires a vector-space structure; intrinsic methods replace it with a tangent-space approximation of the weighted Fréchet mean [31, 36, 26, 41], whereas extrinsic methods exploit an ambient Euclidean embedding and so apply only to a narrow class of manifolds, such as the Stiefel and other compact submanifolds [12, 13, 14]. Both lines of work, however, target offline problems with non-convex or g-convex objectives. In both Euclidean online optimization and centralized online Riemannian optimization, strong convexity sharpens the attainable regret from (T)O( T) to (logT)O( T) [17, 39], a rate that is minimax-optimal for strongly convex losses [1]. In the decentralized online Riemannian setting, however, this improvement remains out of reach: the only existing algorithms [10, 28] attain (T)O( T) regret for g-convex losses and do not exploit strong g-convexity. This raises a basic question: Can the logarithmic regret improvement from strong convexity be attained in decentralized online Riemannian optimization on manifolds? We answer the above question affirmatively by resolving three main challenges. First, network error: the ingredient delivering the logarithmic rate, a decaying step size, is incompatible with the existing analyses. All prior consensus analyses in decentralized Riemannian optimization assume a fixed step size [10, 28], under which the per-step error reduces to a stationary term. With a decaying step size, the iterates are re-perturbed by a different amount at every round, so the network error becomes a time-weighted accumulation of past step sizes, and the static argument no longer applies. Second, positive curvature: the metric projection onto the feasible set may not be non-expansive, which introduces an extra term in the optimization error; controlling it requires a shifted step size ηt=O(1/(t+c0)) _t=O\! (1/(t+c_0) ) rather than the standard O(1/t)O(1/t) [39]. Third, the bandit feedback setting when the gradients are unavailable only compounds both effects: smoothing replaces each loss by a surrogate and degrades strong g-convexity, and keeping the queried points feasible shrinks the domain, so the smoothing and projection errors incorporate into the optimization and network terms simultaneously. Preserving the logarithmic rate therefore demands that a smoothing parameter be tuned jointly with the decaying schedule, so that each of these errors contributes only a constant. Contributions: We study decentralized online Riemannian optimization for μ-strongly g-convex losses on manifolds with bounded sectional curvature, including positively curved manifolds, and establish (logT)O( T) static regret under both full-information and two-point bandit feedback settings. Our work focuses on the curvature-aware consensus step and the two-point gradient estimator of [28]; the main contribution is the analysis of the strongly g-convex regime with a decaying step size to establish a novel logarithmic regret. Concretely: • First (logT)O( T) regret in decentralized online Riemannian optimization. We establish the first (logT)O( T) static regret bound for strongly g-convex losses in the decentralized online Riemannian setting, on manifolds of bounded curvature including positively curved ones (Theorem 3.2). The bound matches, up to curvature-dependent constants, the optimal logarithmic rate for strongly convex losses in both Euclidean optimization and centralized Riemannian optimization, and its (1−σ2(W))−1(1- _2(W))^-1 dependence on the spectral gap of the mixing matrix W is the expected price of decentralization. • Consensus and optimization error analysis under a decaying step size. Achieving this rate requires a decaying step size, which the existing fixed-step-size analyses [10, 28] do not cover. We develop a curvature-aware network error analysis valid for decaying schedules, in which the error accumulates as a time-weighted sum of past step sizes rather than a single stationary term, and we show that this sum remains (logT)O( T). On positively curved manifolds, where the metric projection may not be non-expansive, the same shifted decaying schedule also keeps the optimization error term controlled. • Computationally efficient two-point bandit feedback. We extend the analysis to the two-point bandit feedback, where each agent observes only two function values per round, using the estimator of [28, 30]. Since smoothing does not preserve strong g-convexity, we develop a novel strong sub-g-convexity argument that recovers a strong-convexity-type inequality for the smoothed surrogate up to a controllable slack (Lemma 4.3), which yields the logarithmic rate (Theorem 4.5). The tighter (logT)O( T) target also forces a smaller smoothing radius than the g-convex case, δ=O(T−2)δ=O(T^-2) in place of O(T−1)O(T^-1), chosen jointly with the decaying schedule so that the smoothing, shrinkage, and projection errors remain constant and the (logT)O( T) rate is preserved. Table 1: Static regret bounds for online geodesically convex optimization on Riemannian manifolds. †: separation oracle; ‡: linear optimization oracle; †: static case; cent: centralized; dec: decentralized; g-cvx: g-convex; sg-cvx: strongly g-convex Reference Objective Manifold Setting Feedback Regret Bound Wang et al. [39] g-cvx Riemannian cent Gradient / 2-BAN (T)O( T) Wang et al. [39] sg-cvx Riemannian cent Gradient / 2-BAN (logT)O( T) Hu et al. [19] g-cvx Hadamard cent Gradient / 2-BAN† (T)O( T) Hu et al. [19] sg-cvx Hadamard cent Gradient‡ (T2/3logT)O(T^2/3 T) Chen & Sun [10] g-cvx Hadamard dec Gradient (T)†O( T) Sahinoglu & Shahrampour [28] g-cvx Riemannian dec Gradient / 2-BAN (T)O( T) Our work sg-cvx Riemannian dec Gradient / 2-BAN (logT)O( T) 1.1 Related Work (i) Online optimization in Euclidean spaces. Online convex optimization (OCO) is well understood in the Euclidean space. The convex case admits (T)O( T) regret [45], and strong convexity improves this rate to (logT)O( T) [17]. These guarantees, together with their dynamic-regret refinements [20, 25, 9], form the standard backdrop for OCO. Moving from the single-agent to multi-agent scenario, consensus-based online gradient and mirror descent methods recover sublinear regret while incurring a cost for consensus in terms of the spectral gap of the communication matrix [18, 33, 4, 42]. Recent analyses further attain nearly optimal rates for both convex and strongly convex losses [37]. The picture is essentially complete in the Euclidean setting, encompassing both the convex and strongly convex regimes as well as the centralized and decentralized settings. (i) Riemannian optimization. Centralized optimization on manifolds has been well developed over the past two decades [2, 32]: global complexity guarantees for g-convex objectives, including the strongly g-convex case, are now available [44], together with accelerated [21, 24] and stochastic [7] variants. The decentralized setting, however, has not kept pace and is broadly divided according to how consensus is enforced. Intrinsic methods average through the tangent-space Fréchet-mean approximation and so apply on general manifolds with bounded curvature [10, 41, 26], whereas extrinsic methods rely on an ambient Euclidean embedding and are therefore confined to specific embedded manifolds, such as the Stiefel manifold [12, 13] and compact submanifolds [14, 11]. Nevertheless, prior analysis focuses on non-convex or g-convex objectives; strong g-convexity, the property that leads to the logarithmic regret in online optimization, has not been exploited in any decentralized Riemannian method. (i) Online Riemannian optimization. For the centralized case, (T)O( T) and (logT)O( T) regret rates are available for g-convex and strongly g-convex losses, respectively, with a matching lower bound in the g-convex case and an analysis that reaches beyond Hadamard manifolds to positively curved domains [39]. A growing set of refinements has also followed, including zeroth-order [22], optimistic [40], projection-free [19], and curvature-independent [29] methods, while the two-point bandit feedback we adopt traces to the multi-point and gradient-free estimators of Euclidean online optimization [3, 15]. For the decentralized online setting, however, only two prior works exist [10, 28], both restricted to g-convex losses and fixed step sizes. Strong g-convexity requires a decaying schedule, not addressed by any of these analyses. We close this gap by developing the first regret analysis for strongly g-convex losses in the decentralized regime. 2 Preliminary 2.1 Background on Riemannian Optimization We consider a decentralized online optimization problem, defined over a d-dimensional complete Riemannian manifold ℳM, equipped with a Riemannian metric g. For any point x∈ℳx , the tangent space is denoted by TxℳT_xM. ℬTxℳ(r)B_T_xM(r) (respectively, Txℳ(r)S_T_xM(r)) denotes the ball (respectively, sphere) in tangent space TxℳT_xM centered at the origin with radius r≥0r≥ 0. A curve on ℳM is called a geodesic if it locally minimizes length, playing the role of a straight line in Euclidean space. The Riemannian metric g induces a smoothly varying inner product111The subscript x is omitted when clear from the context. ⟨⋅,⋅⟩x ·,· _x and a geodesic distance function d(x,y)≔infγ∫01‖γ′(t)‖td(x,y) _γ _0^1\|γ (t)\|dt, where the infimum is over piecewise smooth curves γ with γ(0)=xγ(0)=x and γ(1)=yγ(1)=y. For a point x∈ℳx with tangent space TxℳT_xM, the exponential map Expx:Txℳ→ℳExp_x:T_xM is defined as γ(t)=Expx(tu)γ(t)=Exp_x(tu) for a vector u∈Txℳu∈ T_xM, such that γ(0)=xγ(0)=x and γ′(0)=uγ (0)=u. The sectional curvature at a point x of ℳM measures how the manifold bends within a two-dimensional plane of directions through x. We say ℳM has bounded sectional curvature if this is uniformly bounded across all such planes and all points of ℳM. Manifolds with everywhere non-positive sectional curvature are called Hadamard manifolds; in this paper, we place no restriction on the sign of the curvature and allow it to be positive. A key consequence of positive curvature is that ExpxExp_x need not be a global diffeomorphism: it is invertible only within the injectivity radius rinj>0r_inj>0, the largest radius on which ExpxExp_x remains a diffeomorphism. A subset ⊆ℳX is geodesically convex (g-convex) if, any x,y∈x,y are joined by a geodesic γ⊂γ , and uniquely g-convex if this geodesic is unique. Since ExpxExp_x is locally a diffeomorphism within rinjr_inj, it admits an inverse Logx:ℳ→TxℳLog_x:M→ T_xM on a uniquely g-convex set. For a differentiable function f:ℳ→ℝf:M , the Riemannian gradient gradf(x)∈Txℳgradf(x)∈ T_xM is the unique tangent vector satisfying ⟨gradf(x),v⟩x=Df(x)[v],∀v∈Txℳ, (x),v _x=Df(x)[v], ∀ v∈ T_xM, where Df(x)[v]Df(x)[v] denotes the directional derivative of f at x along v [8]. A function f:ℳ→ℝf:M is said to be μ-strongly g-convex (μ≥0μ≥ 0) if it is μ-strongly convex along every geodesic; the case μ=0μ=0 recovers g-convexity. For differentiable functions, this is equivalent to f(y)≥f(x)+⟨gradf(x),Logx(y)⟩x+μ2d2(x,y),f(y)≥ f(x)+ \,f(x),Log_x(y) _x+ μ2\,d^2(x,y), ∀x,y∈ℳ∀ x,y . This generalizes Euclidean strong convexity by requiring a uniform quadratic lower bound along geodesics. 2.2 Network Model, Consensus Update, and Regret We consider a network of n agents collaboratively minimizing a sequence of global objectives over a uniquely g-convex compact subset ⊆ℳX . Communication among the agents is modeled by a doubly stochastic weight matrix W=[wij]W=[w_ij], where wij≥0w_ij≥ 0, and the entries in each row and each column sum to 1. In particular, wij>0w_ij>0 if agent i can receive information from agent j. Otherwise, wij=0w_ij=0. The Euclidean consensus update xi=∑j=1nwijyjx_i= _j=1^nw_ijy_j is inapplicable on a manifold since this weighted average may be infeasible due to nonlinearity of the manifold. Its intrinsic analogue is the weighted Fréchet mean xi=argminy∈∑j=1nwijd2(y,yj)x_i= _y \ _j=1^nw_ijd^2(y,y_j)\, which requires an auxiliary optimization at every step, so instead, we use the first-order approximation xi=Expyi(s∑j=1nwijLogyi(yj)),x_i=Exp_y_i (s _j=1^nw_ij\,Log_y_i(y_j) ), where the consensus step size s>0s>0 is chosen according to the curvature of ℳM [10, 28]. This moves yiy_i along a tangent direction that depends on its neighbors. At each round t∈1,…,Tt∈\1,…,T\: (i) every agent i selects xi,t∈x_i,t using information from rounds 1,…,t−11,…,t-1; (i) the environment reveals a μ-strongly g-convex loss fi,t:→ℝf_i,t:X ; (i) agent i incurs a loss and receives some feedback. The feedback consists of the gradient gradfi,t(xi,t)grad\,f_i,t(x_i,t) in the full information setting (Section 3) and two function evaluations in the bandit setting (Section 4). Note that agent i has no knowledge of fi,tf_i,t when choosing xi,tx_i,t. The collective goal is to minimize the static regret relative to a fixed comparator x∗∈x^* . Under full information feedback, regret is defined as Regfull(T)≔1n∑i=1n∑t=1Tft(xi,t)−∑t=1Tft(x∗),Reg^full(T) 1n _i=1^n _t=1^Tf_t(x_i,t)- _t=1^Tf_t(x^*), (1) where ft(x)=1n∑i=1nfi,t(x)f_t(x)= 1n _i=1^nf_i,t(x) is the global objective function at round t. This standard definition is commonly adopted in decentralized online optimization [10, 33, 28]. The bandit regret definition differs from (1) only in the evaluation point. When the gradient is unavailable or costly to compute, we instead consider the two-point bandit setting, in which each agent i observes the function values at the two queried points, xi,t,1x_i,t,1 and xi,t,2x_i,t,2, rather than xi,tx_i,t, and the regret is defined as Regbandit(T)≔12n∑i=1n∑t=1Tft(xi,t,1)+ft(xi,t,2)−∑t=1Tft(x∗). aligned Reg^bandit(T) & 12n _i=1^n _t=1^Tf_t(x_i,t,1)+f_t(x_i,t,2)- _t=1^Tf_t(x^*). aligned (2) The two evaluations are used to build a two-point gradient estimator at xi,tx_i,t, as we will describe in Section 4. This regret definition aligns with prior work on Riemannian online optimization [39] and its decentralized extension [28]. 2.3 Assumptions The theoretical analysis relies on the following standard assumptions on the network topology, the manifold geometry, and the properties of the loss functions. Assumption 2.1 The network is connected and the communication matrix W∈ℝn×nW ^n× n is symmetric and doubly stochastic. σ2(W) _2(W) denotes the second largest singular value of the matrix W, for which we have that σ2(W)∈[0,1) _2(W)∈[0,1). This assumption is standard in the literature on decentralized online optimization [10, 28, 33]. Generally, a smaller σ2(W) _2(W) corresponds to a better-connected network, facilitating faster information propagation among the agents. Assumption 2.2 The sectional curvature K on ℳM is bounded, such that Kmin≤K≤KmaxK_ ≤ K≤ K_ . The diameter of set X is bounded by D. If Kmax>0K_ >0, we further assume that D<rcxD<r_cx, where rcx:=12minrinj,πKmaxr_cx:= 12 \r_inj, π K_ \, and rinjr_inj denotes the injectivity radius. This assumption (1) implies that X is uniquely g-convex, so the Riemannian logarithm is well defined on X, and (2) it rules out antipodal pairs, allowing meaningful strongly g-convex objectives on positively curved manifolds [43]. These geometric conditions are used in recent work on online Riemannian optimization beyond Hadamard manifolds [39, 28]. Assumption 2.3 For all i∈1,…,ni∈\1,…,n\, the local losses fi,tt=1T\f_i,t\_t=1^T are differentiable, μ-strongly g-convex, and L-Lipschitz on the compact domain X. Since X is compact and the losses are continuous, the sum ∑t=1Tft _t=1^Tf_t attains its minimum on X. We fix the minimizer x∗=argminx∈∑t=1Tft(x)x^*= _x _t=1^Tf_t(x) as the comparator against which the static regrets (1) and (2) are measured. The loss regularity in Assumption 2.3 is likewise standard in geodesically convex optimization [44, 39, 28]. However, the strong g-convexity is what we specifically analyze in this paper. 3 Decentralized Online Riemannian Optimization: Full Information Feedback In this section, we establish the first (logT)O( T) static regret bound for decentralized online Riemannian optimization in the full information setting (Theorem 3.2). We analyze the same two-step algorithm as in [28], but under a decaying step size, as required to achieve the strongly g-convex regret rate. This change necessitates the new consensus analysis developed in Lemma 3.1. At each time step t, every agent i performs the following two updates: yi,t+1 y_i,t+1 =(Expxi,t(−ηtgradi,t)), =P_X\! (Exp_x_i,t\! (- _tgrad_i,t ) ), (I) xi,t+1 x_i,t+1 =Expyi,t+1(s∑j=1nwijLogyi,t+1(yj,t+1)), =Exp_y_i,t+1\! (s _j=1^nw_ijLog_y_i,t+1(y_j,t+1) ), (I) where we write gradi,t:=gradfi,t(xi,t)grad_i,t:=gradf_i,t(x_i,t) for brevity, :ℳ→P_X:M denotes the projection onto X, defined by (x)≔argminy∈d(x,y)P_X(x) _y d(x,y), and s>0s>0 is the consensus step size. In our analysis, the regret decomposes into two components (errors) corresponding to the two steps of the update. Step (I) is a projected Riemannian gradient descent update: agent i moves along the negative gradient via the exponential map and projects back onto X, contributing to the online optimization error. Step (I) is a curvature-aware consensus step: agent i takes a step of size s toward the weighted Fréchet mean of its neighbors’ post-gradient iterates yj,t+1\y_j,t+1\ for any j in the neighborhood of i, contributing to the network error, i.e., the discrepancy among agents’ iterates due to imperfect communication. Let us now discuss the challenges in the analysis of each component. (a) Online optimization error: The principal difficulty in this term is the metric projection P_X, whose non-expansiveness is not guaranteed on positively curved manifolds. On Hadamard manifolds, P_X is non-expansive and the analysis proceeds as in the Euclidean case. On manifolds with positive sectional curvature, non-expansiveness may fail to hold, and the projection introduces an additional error term. To keep this term summable while preserving the (logT)O( T) rate, we adopt the shifted decreasing step size ηt=O(1/(t+c0)) _t=O(1/(t+c_0)) of [39], where c0>0c_0>0 certifies ηtL≤D _tL≤ D for all t≥1t≥ 1. (b) Network error: The network error quantifies the deviation of each agent’s iterate from the network Fréchet mean, and insufficient consensus degrades the regret. Our analysis also reveals an extra interference term that does not contribute to regret, provided s is chosen appropriately with respect to the curvature (see (13) in Section 7.2). Consequently, only the network error itself, namely the failure to reach exact consensus, contributes to the final regret bound. Unlike the online-optimization term, this is where decentralization and the decaying step size interact, and where the fixed-step-size analyses of [10, 28] do not apply. We first bound the network error. The consensus step (I) contracts the Fréchet variance of the agents’ iterates at a linear rate. Let us denote by y¯t y_t the Fréchet mean of yi,ti=1n\y_i,t\_i=1^n and by x¯t x_t the Fréchet mean of xi,ti=1n\x_i,t\_i=1^n. [28, Theorem I.2] proves that ∑i=1nd2(xi,t,x¯t)≤ρ∑i=1nd2(yi,t,y¯t) _i=1^nd^2(x_i,t, x_t)≤ρ _i=1^nd^2(y_i,t, y_t), where the factor ρ∈(0,1)ρ∈(0,1) depends on the consensus step size s, the spectral gap 1−σ2(W)1- _2(W), and the curvature. This contraction is a property of the consensus step alone and is unaffected by the choice of gradient step size ηt _t. What the decaying ηt _t does change is the disturbance the contraction must absorb: Step (I) re-perturbs the iterates by an ηt _t-dependent amount, so the network error behaves like a geometric convolution ∑kρ(t−k)/2ηk _kρ^(t-k)/2 _k of past step sizes. Prior analyses [10, 28] evaluate this sum only for a constant η, for which it collapses to a single static term. The decaying schedule requires summing the convolution against a time-varying sequence. The following lemma carries out this analysis and shows the resulting sum remains (logT)O( T). Lemma 3.1 (Network error) Let Assumptions 2.1, 2.2, and 2.3 hold, and suppose all agents share a common initialization xi,1=x1∈x_i,1=x_1 . If we set s=(2C1)−1C2s=(2C_1)^-1C_2, then for any step size sequence ηt\ _t\ with ηt≤DL _t≤ DL and for all t≥2t≥ 2, running Steps (I) and (I) gives 1n∑i=1nd(xi,t,x¯t)≤L⋅∑k=1t−1(ρt−k2ηk), 1n _i=1^nd(x_i,t, x_t)≤ L· _k=1^t-1 (ρ t-k2 _k ), (3) where ρ:=1−C22(1−σ2(W))2C1(1+C3D2)2ρ:=1- C_2^2(1- _2(W))2C_1(1+C_3D^2)^2, and C1,C2,C3C_1,C_2,C_3 are curvature-dependent constants defined in Appendix 7.5. In particular, under ηt=(μt+L/D)−1 _t=(μ t+L/D)^-1, for all T≥1T≥ 1, it holds that 1n∑t=1T∑i=1nd(xi,t,x¯t)≤2Lμ(1−ρ)log(1+TμDL). 1n _t=1^T _i=1^nd(x_i,t, x_t)≤ 2\,Lμ(1-ρ) (1+ Tμ DL ). Combining the network-error bound of Lemma 3.1 with the online optimization error analysis, we obtain the following static regret bound. Theorem 3.2 Let Assumptions 2.1, 2.2, and 2.3 hold, and suppose all agents share a common initialization xi,1=x1∈x_i,1=x_1 . Running the two Steps (I) and (I) for T iterations with step size ηt=(μt+L/D)−1 _t=(μ t+L/D)^-1 and s=(2C1)−1C2s=(2C_1)^-1C_2, we have the following static regret bound: Regfull(T) ^full(T) ≤R1log(1+TμDL)+R2, ≤ R_1 (1+ Tμ DL )+R_2, where R1R_1 and R2R_2 are constants independent of T. See Appendix 7.5 for their values. Remark 3.3 In the Euclidean decentralized online optimization setting, the static regret bound for strongly convex functions under the standard communication scheme is of order logT/(1−σ2(W)) T/(1- _2(W)) [42]. Our bound matches this order in both T and σ2(W) _2(W) but has extra geometry-dependent constants reflecting the cost of optimization on a non-flat manifold. Remark 3.4 In the centralized online Riemannian optimization setting, an (logT)O( T) regret bound is established for strongly g-convex functions [39]. Our result recovers the same rate in the decentralized setting, with the additional cost of (1−σ2(W))−1(1- _2(W))^-1 for consensus in multi-agent networks. 4 Decentralized Online Riemannian Optimization: Two-Point Bandit Feedback Under two-point bandit feedback, agents observe only function values and must rely on zeroth-order information. Each agent queries its loss at two nearby points and forms a two-point gradient estimator in place of the Riemannian gradient. Establishing an (logT)O( T) bound here raises three difficulties beyond the full-information case. First, the estimator is associated with a smoothed surrogate of the loss, and smoothing does not preserve strong g-convexity. We should quantify the residual as a strong-sub-g-convexity property (Lemma 4.3). Second, constraint handling introduces shrinkage and projection errors. Third, these terms must be controlled tightly enough to keep the logarithmic rate. With an appropriate smoothing parameter each contributes only a constant, so the (logT)O( T) bound carries over. Let xi,tx_i,t denote the decision of agent i at time t. Following [28], we sample a direction ui,tu_i,t uniformly from the unit sphere Txi,tℳ(1)S_T_x_i,tM(1) and form two perturbed points xi,t,1≔Expxi,t(δui,t)x_i,t,1 _x_i,t(δ u_i,t) and xi,t,2≔Expxi,t(−δui,t)x_i,t,2 _x_i,t(-δ u_i,t), at most 2δ2δ apart along a common geodesic through xi,tx_i,t. From their central difference we define the estimator i,tδ=d2δ(fi,t(xi,t,1)−fi,t(xi,t,2))ui,t,g^δ_i,t= d2δ (f_i,t(x_i,t,1)-f_i,t(x_i,t,2) )u_i,t, (4) where δ>0δ>0 is the smoothing parameter and d is the dimension of ℳM. First, we address the feasibility of the queries. Because the two-point estimator evaluates the loss at perturbed points xi,t,1x_i,t,1 and xi,t,2x_i,t,2, these points must remain in the feasible set X. So, we constrain the decision variables xi,tx_i,t to a shrinking subset of X, which requires the following geometric assumption. Assumption 4.1 There exists an interior reference point p∈p and radii 0<r≤R0<r≤ R such that ℬp(r)⊆ℬp(R)B_p(r) _p(R), where ℬp(ρ)B_p(ρ) denotes the geodesic ball of radius ρ centered at p. Following [28], restricting the iterates to the shrinking set (1−τ)≔Expp((1−τ)Logp(x))∣x∈(1-τ)X \Exp_p((1-τ)Log_p(x)) x \ with shrinkage factor τ≔δθrτ δθr guarantees that the perturbed points xi,t,1x_i,t,1 and xi,t,2x_i,t,2 remain in X. The geometric constant θ>0θ>0, which depends on the sectional-curvature bounds of ℳM and the radii R and r, is defined in [28]. Next, to analyze the estimator, we introduce the smoothed surrogate of each local loss as follows, f^i,tδ(x)≔∫ℬTxℳ(1)fi,t(Expx(δu))p(u), f^δ_i,t(x) _B_T_xM(1)f_i,t (Exp_x(δ u) )\ dp(u), where p denotes the uniform measure on ℬTxℳ(1)B_T_xM(1). Since the update is driven by i,tδg^δ_i,t, the algorithm effectively optimizes these surrogates rather than the losses themselves, so we analyze the regret against f^i,tδ f^δ_i,t and control the gap to fi,tf_i,t via Lipschitzness. The crux is that f^i,tδ f^δ_i,t satisfies a strong-sub-g-convexity inequality with respect to i,tδg^δ_i,t up to a controllable slack (Lemma 4.3), replacing the exact strong g-convexity of the full-information case. We begin by formalizing the relaxed strong-convexity notion used in the analysis. Definition 4.2 A function f:⊆ℳ→ℝf:X , together with a vector field G on X, is said to be μ-strong λ-sub-g-convex for constants μ, λ≥0λ≥ 0 if, for all x,y∈x,y , f(y)−f(x)−⟨G(x),Logx(y)⟩−μ2d2(x,y)≥−λ.f(y)-f(x)- G(x),Log_x(y) - μ2d^2(x,y)≥-λ. When G=gradfG=gradf, this recovers μ-strong g-convexity up to the additive slack λ. The above definition allows G to be a surrogate for the gradient, such as the estimator δg^δ. The next lemma shows that the expectation of the estimator i,tδg^δ_i,t satisfies this inequality for the smoothed surrogate f^i,tδ f^δ_i,t, with a slack proportional to δ. Lemma 4.3 Suppose Assumption 2.2 holds, and let f:⊆ℳ→ℝf:X be μ-strongly g-convex and L-Lipschitz on the uniquely g-convex domain X. Fix a smoothing radius 0<δ≤D0<δ≤ D, let f^δ(x)=∫ℬTxℳ(1)f(Expx(δu))p(u) f^δ(x)= _B_T_xM(1)f(Exp_x(δ u))dp(u) be the smoothed surrogate, and define the gradient estimator δ(x)=d2δ(f(Expx(δu))−f(Expx(−δu)))u,g^δ(x)= d2δ(f(Exp_x(δ u))-f(Exp_x(-δ u)))u, (5) where u is uniformly distributed on Txℳ(1)S_T_xM(1). Then, the pair (f^δ,G)( f^δ,G) with certifying field G(x)≔u[δ(x)]∈TxℳG(x) _u[g^δ(x)]∈ T_xM is μ-strong δ(LC4+2μD)δ(LC_4+2μ D)-sub-g-convex in the sense of Definition 4.2 for all x,y∈(1−τ)x,y∈(1-τ)X, i.e., f^δ(y)−f^δ(x)−⟨u[δ(x)],Logx(y)⟩−μ2d2(x,y) f^δ(y)- f^δ(x)- _u[g^δ(x)],Log_x(y) - μ2d^2(x,y) (6) ≥−δ(LC4+2μD), ≥-δ(LC_4+2μ D), where C4>0C_4>0 depends on KminK_ , KmaxK_ , and D (see Appendix 7.5). Remark 4.4 The g-convex counterpart in [28] establishes that f^i,tδ f_i,t^δ is δLC4δ LC_4-sub-g-convex. Exploiting strong g-convexity, our lemma adds the quadratic term μ2d2(x,y) μ2d^2(x,y) at the price of the extra 2μD2μ D slack. The same trade-off, a stronger convexity inequality for a larger additive constant, appears in centralized online Riemannian optimization [39]. And, when μ=0μ=0, we recover the result of [28] as expected. The update for each agent i at time t is then yi,t+1= y_i,t+1= (1−τ)((Expxi,t(−ηti,tδ))), \ P_(1-τ)X (P_X (Exp_x_i,t (- _tg^δ_i,t ) ) ), (I’) followed by the same consensus step (I) as in the full-information setting. The bandit update thus differs from (I)-(I) only in two respects: the Riemannian gradient is replaced by the two-point estimator i,tδg^δ_i,t defined in (4), and the gradient iterate is additionally projected onto the shrinking set (1−τ)(1-τ)X. We are now ready to establish the main theoretical guarantee regarding the regret bound in the two-point bandit setting. Theorem 4.5 Suppose that Assumptions 2.1,2.2,2.3 as well as 4.1 hold. Let the gradient estimator i,tδg^δ_i,t be generated as in (4). With step size ηt=(μt+dLD)−1 _t= (μ t+ dLD )^-1, the smoothing parameter δ=T−2δ=T^-2, and the shrinkage factor τ=δθ/rτ=δθ/r, running the update steps (I’) and (I) for T rounds yields the following expected static regret bound: [Regbandit(T)]≤ [Reg^bandit(T)]≤ R1′log(1+TμDdL)+R2′, R_1 \! (1+ Tμ DdL )+R_2 , where R1′R_1 and R2′R_2 are explicitly defined constants that are independent of the time horizon T (see Appendix 7.5). Thus, although smoothing degrades strong g-convexity and introduces a gap between fi,tf_i,t and f^i,tδ f^δ_i,t, and the sampling constraint shrinks the feasible set, the (logT)O( T) rate is preserved for μ-strongly g-convex losses on manifolds. In the centralized case (n=1n=1), the theorem recovers the rate of [39], and the extra 1−σ2(W)1- _2(W) dependence reflects the cost of decentralization. 5 Numerical Experiments In this section, we conduct experiments to evaluate the performance of our algorithms. The first experiment is on a positively curved manifold, 7⊂ℝ8S^7 ^8, which poses greater geometric challenges than Hadamard manifolds due to possible projection errors. The second experiment is with a real-world dataset on the symmetric positive-definite (SPD) matrix manifold, which lets us analyze the decaying step size for strongly g-convex objectives on a Hadamard manifold 222The code is available at: https://github.com/ZhanyCai-opt/decentralized-online-riemannian-strongly-g-convex.. 5.1 Hyper-sphere experiment Adapting the online Fréchet-mean setup of [28], each agent i observes the loss fi,t(x)=d2(x,zi,t)f_i,t(x)=d^2(x,z_i,t), with global objective ft(x)=1n∑i=1nfi,t(x)f_t(x)= 1n _i=1^nf_i,t(x). The feasible set X is a geodesic ball of radius 7π/327π/32, so its diameter satisfies D=7π/16<π/(2Kmax)=π/2D=7π/16<π/(2 K_ )=π/2 and Assumption 2.2 holds. By Hessian comparison [27], d2(⋅,z)d^2(·,z) is μ-strongly g-convex on X. We use n=10n=10 agents on a ring graph, where each agent communicates with its k=2k=2 nearest neighbors on each side, giving σ2(W)≈0.65 _2(W)≈ 0.65. The base points zii=1n\z_i\_i=1^n are sampled from an inner ball, and each zi,tz_i,t is drawn uniformly from a small ball around ziz_i. We run both feedback models for T=1000T=1000 rounds, using smoothing δ=T−2δ=T^-2 under bandit feedback, and average the bandit results over 55 Monte-Carlo simulation runs. Fig. 1 reports the static regret for consensus step-sizes s∈0.3,0.5,0.8s∈\0.3,0.5,0.8\ under full-information and two-point bandit feedback settings. Fig. 2 compares the strongly g-convex schedule against the g-convex baseline [10, 28] (with ηt=O(1/t) _t=O(1/ t) and δ=O(1/T)δ=O(1/T)), together with O(logT)O( T) and O(T)O( T) reference curves. Fig. 1 shows that a larger consensus step size s consistently reduces regret, and that bandit feedback incurs larger regret than full-information feedback, reflecting the estimator’s variance and dimension dependence. Fig. 2 confirms the predicted separation: the strongly g-convex schedule grows logarithmically and quickly stabilizes, while the g-convex baseline keeps growing at the O(T)O( T) rate under both feedback models. Figure 1: Static regret for strongly g-convex losses with consensus step size s∈0.3,0.5,0.8s∈\0.3,0.5,0.8\. Figure 2: Strongly g-convex schedule, O(logT)O( T), versus g-convex baseline, O(T)O( T), with s=0.8s=0.8. 5.2 FLUXNET2015 experiment on SPD manifold We evaluate the proposed method on a real dataset, namely FLUXNET2015. We treat each flux-tower site as an agent and, for each week from 2010 to 2013, form an SPD matrix from the weekly correlation matrix of five meteorological variables. These matrices lie on the manifold SPD(5)SPD(5) equipped with the affine-invariant metric. Each agent’s local loss is fi,t(X)=12dSPD2(X,Zi,t)f_i,t(X)= 12\,d^2_SPD(X,Z_i,t), where Zi,tZ_i,t is the weekly SPD matrix at site i, and the iterates are constrained to a geodesic ball centered at the identity. We use n=20n=20 agents on a ring graph with three neighbors on each side and run the algorithms for T=208T=208 weeks. Since SPD(5)SPD(5) is Hadamard, the projection is non-expansive and the shift c0=0c_0=0 is sufficient. We compare the strongly g-convex schedule against a convex-stepsize baseline, a local-only baseline, the centralized method, and the two-point bandit variant. Fig. 3 depicts the cumulative static regret, and the network consensus error with final regret values are tabulated in Table 2. Among the decentralized full-information methods, the strongly g-convex schedule achieves the lowest regret, 46.8346.83 versus 76.9776.97 for the convex baseline, confirming the advantage of the decaying stepsize on a Hadamard manifold. The local-only baseline is the worst, highlighting the necessity of communication, while the two-point bandit method incurs larger regret, as expected from zeroth-order estimation, but still grows sublinearly. The strongly g-convex method also attains a smaller consensus error than the convex baseline, indicating more agreement among agents. Table 2: Final FLUXNET2015 results. Algorithm Final regret Consensus error Strongly g-convex full 46.82849746.828497 1.486785×10−11.486785× 10^-1 G-convex full 76.97145176.971451 7.190531×10−17.190531× 10^-1 Local-only full 106.078126106.078126 8.304925×10−18.304925× 10^-1 Centralized full 2.5222292.522229 0.0000000.000000 Strongly g-convex bandit 97.29761697.297616 1.602836×10−11.602836× 10^-1 G-convex bandit 169.713605169.713605 1.6825391.682539 Local-only bandit 156.744117156.744117 8.835844×10−18.835844× 10^-1 Centralized bandit 59.22603259.226032 0.0000000.000000 Figure 3: FLUXNET2015 results. Strongly g-convex regret, O(logT)O( T), versus g-convex baseline, O(T)O( T). 6 Conclusion, Limitations, and Future Work We studied decentralized online Riemannian optimization for strongly g-convex losses on manifolds with bounded sectional curvature. Our analysis gives a network-consensus-error bound that holds for general time-varying step-size schedules under a mild condition (Lemma 3.1), and uses it to establish an (logT)O( T) regret bound under both full-information and two-point bandit feedback settings. This bound matches the lower bound for strongly convex losses in Euclidean online optimization, and is corroborated by our numerical experiments. Two directions remain open. First, our bound carries the unaccelerated (1−σ2(W))−1(1- _2(W))^-1 spectral-gap dependence of standard gossip; extending Euclidean accelerated-gossip schemes [37, 38] to manifolds would potentially improve it. Second, dynamic regret under strong g-convexity is largely unexplored, and the nontrivial interaction of time-varying comparators with curvature makes this an interesting future direction. 7 Appendix 7.1 Proof of Lemma 3.1 By [28, Theorem I.2], one application of the consensus step (I) contracts the Fréchet variance of the iterates as ∑i=1nd2(xi,t+1,x¯t+1)≤ρ∑i=1nd2(yi,t+1,y¯t+1), _i=1^nd^2(x_i,t+1, x_t+1)≤ρ _i=1^nd^2(y_i,t+1, y_t+1), where the factor ρ∈(0,1)ρ∈(0,1). Setting at:=(∑i=1nd2(xi,t,x¯t))1/2a_t:= ( _i=1^nd^2(x_i,t, x_t) )^1/2, we then have at+1 a_t+1 ≤ρ∑i=1nd2(yi,t+1,y¯t+1) ≤ ρ _i=1^nd^2(y_i,t+1, y_t+1) ≤ρ∑i=1nd2(yi,t+1,x¯t) ≤ ρ _i=1^nd^2(y_i,t+1, x_t) ≤ρ∑i=1nd2(xi,t,x¯t)+ρ∑i=1nd2(xi,t,yi,t+1) ≤ ρ _i=1^nd^2(x_i,t, x_t)+ ρ _i=1^nd^2(x_i,t,y_i,t+1) ≤ρ∑i=1nd2(xi,t,x¯t)+ρnηtL. ≤ ρ _i=1^nd^2(x_i,t, x_t)+ ρ n _tL. where the second inequality uses the fact that the Fréchet mean y¯t+1 y_t+1 is the minimizer of the function g(y)=∑id2(y,yi,t+1)g(y)= _id^2(y,y_i,t+1) over X. The third follows from Minkowski’s inequality applied to d(yi,t+1,x¯t)≤d(xi,t,x¯t)+d(xi,t,yi,t+1)d(y_i,t+1, x_t)≤ d(x_i,t, x_t)+d(x_i,t,y_i,t+1), and the last uses the bound d(xi,t,yi,t+1)≤ηtLd(x_i,t,y_i,t+1)≤ _tL due to Step (I). Under the common initialization xi,1=x1x_i,1=x_1 we have a1=0a_1=0. Unrolling the recursion at+1≤ρat+ρnηtLa_t+1≤ ρ\,a_t+ ρ n\, _tL then gives, for all t≥2t≥ 2, at≤nL∑k=1t−1ρt−k2ηka_t≤ n\,L _k=1^t-1ρ t-k2 _k and at2n≤L2(∑k=1t−1ρt−k2ηk)2. a_t^2n\;≤\;L^2 ( _k=1^t-1ρ t-k2 _k )^2. By the Cauchy–Schwarz inequality, we have 1n∑id(xi,t,x¯t)≤1n∑id2(xi,t,x¯t) 1n _id(x_i,t, x_t)≤ 1 n _id^2(x_i,t, x_t); hence, 1n∑i=1nd(xi,t,x¯t)≤L∑k=1t−1ρt−k2ηk. 1n _i=1^nd(x_i,t, x_t)\;≤\;L _k=1^t-1ρ t-k2 _k. Summing over t and exchanging the order of summation, 1n∑t=1T∑i=1nd(xi,t,x¯t) 1n _t=1^T _i=1^nd(x_i,t, x_t) ≤L⋅∑t=2T∑k=1t−1(ρt−k2ηk) ≤ L· _t=2^T _k=1^t-1 (ρ t-k2 _k ) ≤L⋅∑k=1T−1ηk∑t=k+1Tρt−k2 ≤ L· _k=1^T-1 _k _t=k+1^Tρ t-k2 ≤L⋅ρ1−ρ∑k=1T−1ηk, ≤ L· ρ1- ρ _k=1^T-1 _k, where the last step bounds the inner geometric series by ∑t=k+1Tρ(t−k)/2≤ρ/(1−ρ) _t=k+1^Tρ^(t-k)/2≤ ρ/(1- ρ). Using ρ/(1−ρ)≤2/(1−ρ) ρ/(1- ρ)≤ 2/(1-ρ) for ρ∈(0,1)ρ∈(0,1) and ηk=(μk+L/D)−1 _k= (μ k+L/D )^-1, which implies ∑k=1T−1ηk≤1μlog(1+TμDL) _k=1^T-1 _k≤ 1μ \! (1+ Tμ DL ), we obtain 1n∑t=1T∑i=1nd(xi,t,x¯t)≤2Lμ(1−ρ)log(1+TμDL), 1n _t=1^T _i=1^nd(x_i,t, x_t)\;≤\; 2Lμ(1-ρ) \! (1+ Tμ DL ), which provides the second bound of Lemma 3.1. □ 7.2 Proof of Theorem 3.2 We use two geometric lemmas. The first is a Riemannian law of cosines that two-sidedly compares squared distances. It helps with converting the gradient step into a telescoping sum and supplies the constants C1,C2C_1,C_2. The result is due to [5, Corollary 2.1] and [44, Lemma 5]. Lemma 7.1 (Trigonometric distance comparison) Let a,b,c∈ℳa,b,c with d(a,b)≤Dd(a,b)≤ D and d(b,c)≤Dd(b,c)≤ D, so that log maps are well-defined. Given Assumption 2.2, we have d2(a,c)≤ d^2(a,c)≤ g1(Kmin,d(a,b))d2(b,c)+d2(a,b) \,g_1(K_ ,d(a,b))d^2(b,c)+d^2(a,b) (7) −2⟨Logb(a),Logb(c)⟩, -2 _b(a),Log_b(c) , d2(a,c)≥ d^2(a,c)≥ g2(Kmax,q)d2(b,c)+d2(a,b) \,g_2(K_ ,q)d^2(b,c)+d^2(a,b) −2⟨Logb(a),Logb(c)⟩, -2 _b(a),Log_b(c) , for some q>0q>0, where g1(⋅,⋅)g_1(·,·) and g2(⋅,⋅)g_2(·,·) are defined in the Appendix 7.5. The second result controls where positive curvature obstructs the Euclidean argument: the projection P_X need not be non-expansive, so projecting the gradient update may increase the distance to x∗x . The lemma bounds this excess by a gradient-norm term with constant C7C_7 [39, Lemma 21]. Lemma 7.2 (Projection-error bound) Suppose ⊆MX M with diameter D<π2KmaxD< π2 K_ . Let us define the iterates zi,t=Expxi,t(−ηtgt)z_i,t=Exp_x_i,t(- _tg_t) and yi,t+1=P(zi,t)y_i,t+1=P_X(z_i,t) with ‖ηtgt‖≤D\| _tg_t\|≤ D. Then, it holds that ∑t=1T12ηt(d2(yi,t+1,x∗)−d2(zi,t,x∗))≤C7∑t=1T12ηt‖gt‖2, _t=1^T 12 _t (d^2(y_i,t+1,x )-d^2(z_i,t,x ) )≤ C_7 _t=1^T 12 _t\|g_t\|^2, where C7C_7 is defined in Appendix 7.5. Decomposition of Regret Terms We now split the regret as Regfull(T)= ^full(T)= 1n∑i=1n∑t=1Tft(xi,t)−∑t=1Tft(x∗) 1n _i=1^n _t=1^Tf_t(x_i,t)- _t=1^Tf_t(x^*) = = 1n∑i=1n∑t=1Tft(xi,t)−1n∑i=1n∑t=1Tfi,t(xi,t) 1n _i=1^n _t=1^Tf_t(x_i,t)- 1n _i=1^n _t=1^Tf_i,t(x_i,t) (8) +1n∑i=1n∑t=1Tfi,t(xi,t)−∑t=1Tft(x∗). + 1n _i=1^n _t=1^Tf_i,t(x_i,t)- _t=1^Tf_t(x^*). (9) where (8) is the network error and (9) is the online optimization error. Analysis of Term (8) Since ft=1n∑i=1nfi,tf_t= 1n _i=1^nf_i,t, we have 1n∑i=1nfi,t(x¯t)=ft(x¯t) 1n _i=1^nf_i,t( x_t)=f_t( x_t), so adding and subtracting ft(x¯t)f_t( x_t) leave the average unchanged as 1n∑i=1n(ft(xi,t)−fi,t(xi,t)) 1n _i=1^n (f_t(x_i,t)-f_i,t(x_i,t) ) =1n∑i=1n(ft(xi,t)−ft(x¯t)) = 1n _i=1^n (f_t(x_i,t)-f_t( x_t) ) +1n∑i=1n(fi,t(x¯t)−fi,t(xi,t)). + 1n _i=1^n (f_i,t( x_t)-f_i,t(x_i,t) ). By the L-Lipschitz property of ftf_t and each fi,tf_i,t, both summands are at most L·d(xi,t,x¯t)L·d(x_i,t, x_t), and hence 1n∑i=1n(ft(xi,t)−fi,t(xi,t))≤2Ln∑i=1nd(xi,t,x¯t). 1n _i=1^n (f_t(x_i,t)-f_i,t(x_i,t) )≤ 2Ln _i=1^nd(x_i,t, x_t). Summing over t and applying Lemma 3.1, we get (8)≤2Ln∑t=1T∑i=1nd(xi,t,x¯t)≤4L2μ(1−ρ)log(1+TμDL). eq:term7≤ 2Ln _t=1^T _i=1^nd(x_i,t, x_t)≤ 4\,L^2μ(1-ρ) \! (1+ Tμ DL ). Analysis of Term (9) Let zi,t≔Expxi,t(−ηtgradi,t)z_i,t _x_i,t(- _tgrad_i,t) for the gradient iterate before projection. By the μ-strong g-convexity of fi,tf_i,t (Assumption 2.3), we have fi,t(xi,t)−fi,t(x∗)≤⟨−gradi,t,Logxi,t(x∗)⟩−μ2d2(xi,t,x∗).f_i,t(x_i,t)-f_i,t(x^*)≤ -grad_i,t,Log_x_i,t(x^*) - μ2d^2(x_i,t,x^*). Since −gradi,t=1ηtLogxi,t(zi,t)-grad_i,t= 1 _tLog_x_i,t(z_i,t), the inner product equals 1ηt⟨Logxi,t(zi,t),Logxi,t(x∗)⟩ 1 _t _x_i,t(z_i,t),Log_x_i,t(x^*) . Applying Lemma 7.1 (a=x∗a=x , b=xi,tb=x_i,t, c=zi,tc=z_i,t) and using the monotonicity of g1(Kmin,⋅)g_1(K_ ,·), fi,t(xi,t)−fi,t(x∗) f_i,t(x_i,t)-f_i,t(x ) ≤12ηt(d2(xi,t,x∗)−d2(zi,t,x∗)) ≤ 12 _t (d^2(x_i,t,x )-d^2(z_i,t,x ) ) +C12ηtd2(xi,t,zi,t)−μ2d2(xi,t,x∗). + C_12 _td^2(x_i,t,z_i,t)- μ2d^2(x_i,t,x ). Inserting distances based on yi,t+1=(zi,t)y_i,t+1=P_X(z_i,t) and xi,t+1x_i,t+1 splits the first line into a telescoping term, a consensus-interference term, and a projection-error term as follows fi,t(xi,t)−fi,t(x∗) f_i,t(x_i,t)-f_i,t(x ) ≤12ηt(d2(xi,t,x∗)−d2(xi,t+1,x∗)) ≤ 12 _t (d^2(x_i,t,x )-d^2(x_i,t+1,x ) ) +12ηt(d2(xi,t+1,x∗)−d2(yi,t+1,x∗)) + 12 _t (d^2(x_i,t+1,x )-d^2(y_i,t+1,x ) ) +12ηt(d2(yi,t+1,x∗)−d2(zi,t,x∗)) + 12 _t (d^2(y_i,t+1,x )-d^2(z_i,t,x ) ) +C12ηtd2(xi,t,zi,t)−μ2d2(xi,t,x∗). + C_12 _td^2(x_i,t,z_i,t)- μ2d^2(x_i,t,x ). (10) The step size ηt _t satisfies ‖ηtgradi,t‖≤η1L≤D\| _tgrad_i,t\|≤ _1L≤ D for every t, so Lemma 7.2 applies with gt=gradi,tg_t=grad_i,t. Summing (10) over t=1,…,Tt=1,…,T, the first term above telescopes as ∑t=1T12ηt _t=1^T 12 _t (d2(xi,t,x∗)−d2(xi,t+1,x∗)) (d^2(x_i,t,x )-d^2(x_i,t+1,x ) ) = = ∑t=2T(12ηt−12ηt−1)d2(xi,t,x∗) _t=2^T ( 12 _t- 12 _t-1 )d^2(x_i,t,x ) +12η1d2(xi,1,x∗)−12ηTd2(xi,T+1,x∗). + 12 _1d^2(x_i,1,x )- 12 _Td^2(x_i,T+1,x ). With this schedule, 12ηt−12ηt−1=μ2 12 _t- 12 _t-1= μ2 for all t, and the first line above is canceled by the −μ2d2(xi,t,x∗)- μ2d^2(x_i,t,x ) term in (10). Using 12η1−μ2=L2D 12 _1- μ2= L2D and d2(xi,1,x∗)≤D2d^2(x_i,1,x )≤ D^2, we obtain ∑t=1T(fi,t(xi,t) _t=1^T (f_i,t(x_i,t) −fi,t(x∗))≤DL2−12ηTd2(xi,T+1,x∗) -f_i,t(x ) )≤ DL2- 12 _Td^2(x_i,T+1,x ) +∑t=1T12ηt(d2(xi,t+1,x∗)−d2(yi,t+1,x∗)) + _t=1^T 12 _t (d^2(x_i,t+1,x )-d^2(y_i,t+1,x ) ) +∑t=1T(C1+C7)ηt2‖gradi,t‖2, + _t=1^T(C_1+C_7) _t2\|grad_i,t\|^2, (11) where the projection-error term has been bounded via Lemma 7.2 and merged with the gradient-norm term. Since ‖gradi,t‖≤L\|grad_i,t\|≤ L and ∑tηt≤1μlog(1+TμDL) _t _t≤ 1μ (1+ Tμ DL), by discarding the non-positive term −12ηTd2(xi,T+1,x∗)- 12 _Td^2(x_i,T+1,x ), we have ∑t=1T(fi,t(xi,t)−fi,t(x∗))≤(C1+C7)L22μlog(1+TμDL) _t=1^T (f_i,t(x_i,t)-f_i,t(x ) )≤ (C_1+C_7)L^22μ \! (1+ Tμ DL ) +DL2+∑t=1T12ηt(d2(xi,t+1,x∗)−d2(yi,t+1,x∗)). + DL2+ _t=1^T 12 _t (d^2(x_i,t+1,x )-d^2(y_i,t+1,x ) ). (12) The interference term It remains to handle the sum term in (12). Since we further sum over agents in the final regret bound, we need to evaluate the following term ∑i=1n∑t=1T12ηt(d2(xi,t+1,x∗)−d2(yi,t+1,x∗)). _i=1^n _t=1^T 12 _t (d^2(x_i,t+1,x )-d^2(y_i,t+1,x ) ). For each fixed t this term depends only on Step (I) and not on the gradient step size ηt _t, i.e., the factor 1/ηt1/ _t is simply independent of i. Following the argument of [28, proof of Thm. IV.2], with s=(2C1)−1C2s=(2C_1)^-1C_2 the doubly stochastic, symmetric weights make the per-t sum non-positive, i.e., ∑i=1n12ηt(d2(xi,t+1,x∗)−d2(yi,t+1,x∗))≤0. _i=1^n 12 _t (d^2(x_i,t+1,x )-d^2(y_i,t+1,x ) )≤ 0. (13) Conclusion Combining the bounds on (8) and (9), and using (13) to discard the interference sum in (12), we derive Regfull(T)≤R1log(1+TμDL)+R2, ^full(T)≤ R_1 \! (1+ Tμ DL )+R_2, with R1:=4L2μ(1−ρ)+(C1+C7)L22μR_1:= 4L^2μ(1-ρ)+ (C_1+C_7)L^22μ and R2:=DL2R_2:= DL2, both independent of T. This completes the proof of Theorem 3.2. □ 7.3 Proof of Lemma 4.3 Let us set xu≔Expx(u)x_u _x(u) and yu≔Expy(Γxy(u))y_u _y( ^y_x(u)), where Γxy ^y_x denotes parallel transport along the minimizing geodesic from x to y. Step 1 - Surrogate gap from strong convexity Since Γxy ^y_x is a linear isometry, the change of variables u→Γxy(u)u→ ^y_x(u) is measure preserving, so both surrogate integrals can be written over the common ball ℬTxℳ(δ)B_T_xM(δ) as follows f^δ(y)−f^δ(x)=∫ℬTxℳ(δ)(f(yu)−f(xu))p(u), f^δ(y)- f^δ(x)= _B_T_xM(δ)(f(y_u)-f(x_u))dp(u), where p denotes the uniform measure on ℬTxℳ(δ)B_T_xM(δ). Applying μ-strong g-convexity of f to the pair (xu,yu)(x_u,y_u) gives f^δ(y)−f^δ(x)≥ f^δ(y)- f^δ(x)≥ ∫ℬTxℳ(δ)⟨gradf(xu),Logxu(yu)⟩p(u) _B_T_xM(δ) (x_u),Log_x_u(y_u) \ dp(u) + + ∫ℬTxℳ(δ)μ2d2(xu,yu)p(u). _B_T_xM(δ) μ2d^2(x_u,y_u)\ dp(u). (14) Step 2 - The certifying field By the Stokes’ identity for the spherical two-point estimator [3, 15], the expectation of δg^δ over u equals the δ-ball average of the gradient of hx(u)≔f(Expx(u))h_x(u) f(Exp_x(u)). For any v∈Txℳv∈ T_xM, we have ⟨u[δ(x)],v⟩= _u[g^δ(x)],v = ∫ℬTxℳ(δ)⟨gradf(xu),dExpx(u)[v]⟩p(u), _B_T_xM(δ) f(x_u),dExp_x(u)[v] dp(u), (15) where dExpx(u):Txℳ→TxuℳdExp_x(u):T_xM→ T_x_uM is the differential of the exponential map. Step 3 - Subtract Taking v=Logx(y)v=Log_x(y) in Equation (7.3) and subtracting (7.3) and μ2d2(x,y) μ2d^2(x,y) from (7.3), we get f^δ(y)−f^δ(x)−⟨u[δ(x)],Logx(y)⟩−μ2d2(x,y) f^δ(y)- f^δ(x)- _u[g^δ(x)],Log_x(y) - μ2d^2(x,y) ≥ ≥ ∫ℬTxℳ(δ)⟨gradf(xu),Logxu(yu)−dExpx(u)[v]⟩p(u) _B_T_xM(δ) (x_u),Log_x_u(y_u)-dExp_x(u)[v] \ dp(u) +μ2∫ℬTxℳ(δ)(d2(xu,yu)−d2(x,y))p(u). + μ2 _B_T_xM(δ)(d^2(x_u,y_u)-d^2(x,y))dp(u). Step 4 - Bound the two integrals Applying the Cauchy-Schwarz inequality, we bound the absolute value of the integrand of the first integral as ‖Logxu(yu)−dExpx(u)[Logx(y)]‖⋅‖gradf(xu)‖.\|Log_x_u(y_u)-dExp_x(u)[Log_x(y)]\|·\|gradf(x_u)\|. Using ‖gradf‖≤L\|gradf\|≤ L and the bound ‖Logxu(yu)−dExpx(u)[Logx(y)]‖≤δC4\|Log_x_u(y_u)-dExp_x(u)[Log_x(y)]\|≤δ C_4 from [28], this is at most δC4Lδ C_4L. Hence, the first integral is bounded below by −δLC4-δ LC_4. For the second integral, since d(x,xu)≤δd(x,x_u)≤δ and d(y,yu)≤δd(y,y_u)≤δ, the triangle inequality gives |d(xu,yu)−d(x,y)|≤2δ|d(x_u,y_u)-d(x,y)|≤ 2δ. Since |d(xu,yu)+d(x,y)|≤2D|d(x_u,y_u)+d(x,y)|≤ 2D, we get |(d2(xu,yu)−d2(x,y))|≤4δD|(d^2(x_u,y_u)-d^2(x,y))|≤ 4δ D, so the integral is bounded below by −2μDδ-2μ Dδ. We obtain f^δ(y)−f^δ(x)−⟨u[δ(x)],Logx(y)⟩−μ2d2(x,y) f^δ(y)- f^δ(x)- _u[g^δ(x)],Log_x(y) - μ2d^2(x,y) ≥ ≥ −δ(LC4+2μD). -δ(LC_4+2μ D). 7.4 Proof of Theorem 4.5 Throughout, f^i,tδ f^δ_i,t and f^tδ=1n∑i=1nf^i,tδ f^δ_t= 1n _i=1^n f^δ_i,t denote the smoothed local and global losses, i,tδg^δ_i,t the two-point estimator of (4), and xτ∗:=argminx∈(1−τ)∑t=1Tft(x).x^*_τ\;:=\; _x∈(1-τ)X\ _t=1^Tf_t(x). Recall the bandit step size ηt=(μ(t+dLμD))−1 _t= (μ(t+ dLμ D) )^-1 and the shrinkage factor τ=δθ/rτ=δθ/r. Step 1: Regret Decomposition Adding and subtracting ft(xi,t)f_t(x_i,t), f^tδ(xi,t) f^δ_t(x_i,t), f^tδ(xτ∗) f^δ_t(x^*_τ), and ft(xτ∗)f_t(x^*_τ) inside the bandit regret (2) gives [Regbandit(T)]E\! [Reg^bandit(T) ] equals to [1n∑i=1n∑t=1T(12(ft(xi,t,1)+ft(xi,t,2))−ft(xi,t))] \, [ 1n\! _i=1^n _t=1^T\! ( 12 (f_t(x_i,t,1)+f_t(x_i,t,2) )-f_t(x_i,t) ) ] (15a) +[1n∑i=1n∑t=1T(ft(xi,t)−f^tδ(xi,t))] +E\, [ 1n\! _i=1^n _t=1^T\! (f_t(x_i,t)- f^δ_t(x_i,t) ) ]\; (15b) +[1n∑i=1n∑t=1T(f^tδ(xi,t)−f^tδ(xτ∗))] +E\, [ 1n\! _i=1^n _t=1^T\! ( f^δ_t(x_i,t)- f^δ_t(x^*_τ) ) ] (16) +[1n∑i=1n∑t=1T(f^tδ(xτ∗)−ft(xτ∗))] +E\, [ 1n\! _i=1^n _t=1^T\! ( f^δ_t(x^*_τ)-f_t(x^*_τ) ) ] (15c) +[1n∑i=1n∑t=1T(ft(xτ∗)−ft(x∗))]. +E\, [ 1n\! _i=1^n _t=1^T\! (f_t(x^*_τ)-f_t(x^*) ) ]. (15d) Step 2: Upper bounds on (15a), (15b), (15c) and (15d) We show that, these terms are O(1)O(1) in T. Each query point satisfies d(xi,t,k,xi,t)≤δd(x_i,t,k,x_i,t)≤δ for k∈1,2k∈\1,2\, so by L-Lipschitzness of ftf_t we get (15a)≤δTL 15a≤δ TL. Likewise, ft(x)−f^tδ(x)=∫BTxM(1)(ft(x)−ft(Expx(δu)))p(u)≤δLf_t(x)- f^δ_t(x)= _B_T_xM(1)\! (f_t(x)-f_t(Exp_x(δ u)) )dp(u)≤δ L, hence (15b)≤δTL 15b≤δ TL and (15c)≤δTL 15c≤δ TL. For (15d), g-convexity of ftf_t gives ft(xτ∗)−ft(x∗)≤τ(ft(p)−ft(x∗))≤τDLf_t(x^*_τ)-f_t(x^*)≤τ (f_t(p)-f_t(x^*) )≤τ DL, where p is the interior reference point defined in Assumption 4.1 and satisfies Expp((1−τ)Logp(x∗))∈(1−τ)Exp_p ((1-τ)Log_p(x^*) )∈(1-τ)X. Therefore, (15a)+(15b)+(15c)+(15d)≤(3δ+τD)LT. 15a+ 15b+ 15c+ 15d\;≤\;(3δ+τ D)\,L\,T. (15) Step 3: The main term (16) Insert the local smoothed losses to split (16) into a network term, an optimization term, and a vanishing term: (16) =[1n∑i=1n∑t=1T(f^tδ(xi,t)−f^i,tδ(xi,t))] =E\, [ 1n\! _i=1^n _t=1^T\! ( f^δ_t(x_i,t)- f^δ_i,t(x_i,t) ) ] (17) +[1n∑i=1n∑t=1T(f^i,tδ(xi,t)−f^i,tδ(xτ∗))] +E\, [ 1n\! _i=1^n _t=1^T\! ( f^δ_i,t(x_i,t)- f^δ_i,t(x^*_τ) ) ] (18) +[1n∑i=1n∑t=1T(f^i,tδ(xτ∗)−f^tδ(xτ∗))]. +E\, [ 1n\! _i=1^n _t=1^T\! ( f^δ_i,t(x^*_τ)- f^δ_t(x^*_τ) ) ]. (19) Term (19) vanishes: 1n∑if^i,tδ=f^tδ 1n _i f^δ_i,t= f^δ_t pointwise, so 1n∑i(f^i,tδ(xτ∗)−f^tδ(xτ∗))=0 1n _i ( f^δ_i,t(x^*_τ)- f^δ_t(x^*_τ) )=0. Term (17) – network error (reuse of Lemma 3.1). Firstly, we estimate the Lipschitz constant of f^i,tδ f^δ_i,t. In [23, Lemma 1] it is given that for any w∈Txℳw∈ T_xM satisfying ‖w‖≤π2Kmax\|w\|≤ π2 K_ , we have d(Expx(w),Expy(Γxy(w)))≤cosh(Kmin‖w‖)d(x,y).d (Exp_x(w),Exp_y( ^y_x(w)) )≤ ( K_ \|w\|)d(x,y). Therefore, with xu:=Expx(δu)x_u:=Exp_x(δ u) and yu:=Expy(Γxy(δu))y_u:=Exp_y( ^y_x(δ u)), as defined in the proof of Lemma 4.3, it follows that f^i,tδ(x)−f^i,tδ(y)= f^δ_i,t(x)- f^δ_i,t(y)= ∫ℬTxℳ(1)[fi,t(xu)−fi,t(yu)]p(u) \, _B_T_xM(1) [f_i,t (x_u )-f_i,t (y_u ) ]dp(u) ≤ ≤ L⋅∫ℬTxℳ(1)d(xu,yu)p(u) \,L· _B_T_xM(1)d (x_u,y_u )dp(u) ≤ ≤ Ld(x,y) \,Ld(x,y) ∫ℬTxℳ(1)cosh(Kminδ‖u‖)p(u) _B_T_xM(1) ( K_ δ\|u\| )\,dp(u) ≤ ≤ C8Ld(x,y), \,C_8Ld(x,y), where C8C_8 is defined in Appendix 7.5. The last inequality follows from the monotonicity of cosh(⋅) (·) on [0,∞)[0,∞) and the fact that δ‖u‖≤1δ\|u\|≤ 1 for every u∈ℬTxℳ(1)u _T_xM(1). Function f^tδ f^δ_t inherits the C8LC_8L-Lipschitz property from f^i,tδ f^δ_i,t. Similar to the term (8) in the proof of Theorem 3.2, we have (17)≤1n∑i=1n∑t=1T2C8Ld(xi,t,x¯t). 18\;≤\; 1n _i=1^n _t=1^T2C_8L\,d(x_i,t, x_t). Lemma 3.1 carries over almost verbatim to the bandit update (I’): the consensus step (I) is unchanged, and the only modification is the per-step displacement that feeds the recursion. Writing the pre-consensus chain zi,t=Expxi,t(−ηti,tδ)→wi,t+1=P(zi,t)→yi,t+1=P(1−τ)(wi,t+1)z_i,t=Exp_x_i,t(- _tg^δ_i,t)→ w_i,t+1=P_X(z_i,t)→ y_i,t+1=P_(1-τ)X(w_i,t+1), the nearest-point property of the two projections, with xi,t∈(1−τ)⊆x_i,t∈(1-τ)X feasible for both, gives d(zi,t,wi,t+1)≤d(zi,t,xi,t)≤ηtdLd(z_i,t,w_i,t+1)≤ d(z_i,t,x_i,t)≤ _tdL and d(wi,t+1,yi,t+1)≤d(wi,t+1,xi,t)≤2ηtdLd(w_i,t+1,y_i,t+1)≤ d(w_i,t+1,x_i,t)≤ 2 _tdL so d(xi,t,yi,t+1)≤4ηtdLd(x_i,t,y_i,t+1)≤ 4 _tdL: the gradient-case displacement ηtL _tL is replaced by 4ηtdL4 _tdL (no non-expansiveness is used; on a positively curved manifold the projection onto a g-convex set may be expansive). The displacement enters the recursion linearly, enlarging only the absolute constant, not the order, so Lemma 3.1 yields (17)≤16C8dL2(1−ρ)(∑t=1Tηt)≤16C8dL2μ(1−ρ)log(1+TμDdL). 18\;≤\; 16C_8dL^2(1-ρ)\, ( _t=1^T _t )≤ 16C_8dL^2μ(1-ρ) (1+ Tμ DdL ). Term (18) – optimization error. Let zi,tz_i,t, wi,t+1w_i,t+1 and yi,t+1y_i,t+1 be defined as before. By Lemma 4.3, for any fixed t≥1t≥ 1, we have: f^i,tδ(xi,t)−f^i,tδ(xτ∗) f^δ_i,t(x_i,t)- f^δ_i,t(x^*_τ) ≤ ≤ ⟨−u[i,tδ],Logxi,t(xτ∗)⟩−μ2d2(xi,t,xτ∗)+δ(LC4+2μD) -E_u[g_i,t^δ],Log_x_i,t(x_τ^*) - μ2d^2(x_i,t,x_τ^*)+δ\,(LC_4+2μ D) ≤ ≤ 12ηtu[d2(xi,t,xτ∗)−d2(zi,t,xτ∗)] 12 _tE_u [d^2(x_i,t,x_τ^*)-d^2(z_i,t,x^*_τ) ] +C12ηt⋅u[d2(xi,t,zi,t)]−μ2d2(xi,t,xτ∗) + C_12 _t·E_u[d^2(x_i,t,z_i,t)]- μ2d^2(x_i,t,x^*_τ) +δ(LC4+2μD) +δ\,(LC_4+2μ D) = = 12ηtu[d2(xi,t,xτ∗)−d2(xi,t+1,xτ∗)] 12 _tE_u [d^2(x_i,t,x^*_τ)-d^2(x_i,t+1,x^*_τ) ] +12ηtu[d2(xi,t+1,xτ∗)−d2(yi,t+1,xτ∗)] + 12 _tE_u [d^2(x_i,t+1,x^*_τ)-d^2(y_i,t+1,x^*_τ) ] +12ηtu[d2(yi,t+1,xτ∗)−d2(wi,t+1,xτ∗)] + 12 _tE_u [d^2(y_i,t+1,x^*_τ)-d^2(w_i,t+1,x^*_τ) ] +12ηtu[d2(wi,t+1,xτ∗)−d2(zi,t,xτ∗)] + 12 _tE_u [d^2(w_i,t+1,x^*_τ)-d^2(z_i,t,x^*_τ) ] +C12ηt⋅u[d2(xi,t,zi,t)]−μ2d2(xi,t,xτ∗) + C_12 _t·E_u[d^2(x_i,t,z_i,t)]- μ2d^2(x_i,t,x^*_τ) +δ(LC4+2μD). +δ\,(LC_4+2μ D). To apply Lemma 7.2, we take i,tδg_i,t^δ as the sequence gtg_t there, and set ηt=(μt+dLD)−1 _t= (μ t+ dLD )^-1 such that for each t, ‖ηti,tδ‖≤|η1|⋅dL≤D\| _tg_i,t^δ\|≤| _1|· dL≤ D. Then, by inequality (13) of the proof of Theorem 3.2 with xτ∗x^*_τ in place of x∗x^*, and by Lemma 7.2, we have, respectively, ∑i=1n∑t=1T12ηt(d2(xi,t+1,xτ∗)−d2(yi,t+1,xτ∗))≤0, _i=1^n _t=1^T 12 _t (d^2(x_i,t+1,x^*_τ)-d^2(y_i,t+1,x^*_τ) )≤ 0, ∑t=1T12ηt(d2(wi,t+1,xτ∗)−d2(zi,t,xτ∗))≤C7∑t=1T12ηt‖i,tδ‖2, _t=1^T 12 _t (d^2(w_i,t+1,x^*_τ)-d^2(z_i,t,x^*_τ) )\\ ≤ C_7 _t=1^T 12 _t\|g_i,t^δ\|^2, and d2(xi,t,zi,t)=ηt2‖i,tδ‖2d^2(x_i,t,z_i,t)= _t^2\|g_i,t^δ\|^2. Since d(yi,t+1,wi,t+1)≤τDd(y_i,t+1,w_i,t+1)≤τ D, we also have ∑t=1T12ηt(d2(yi,t+1,xτ∗)−d2(wi,t+1,xτ∗))≤τD2∑t=1T1ηt. _t=1^T 12 _t (d^2(y_i,t+1,x^*_τ)-d^2(w_i,t+1,x^*_τ) )\\ ≤τ D^2 _t=1^T 1 _t. Because of the term ∑t=1T1ηt _t=1^T 1 _t, both τ and δ must be O(1/T2)O(1/T^2). Set δ=1T2δ= 1T^2 and keep ηt=(μt+dLD)−1 _t= (μ t+ dLD )^-1. Following the same telescope summation argument as in the case of full information feedback, we have (18)≤R3′log(1+TμDdL)+R4′, 19≤ R_3 \! (1+ Tμ DdL )+R_4 , where R3′≔(C1+C7)(dL)22μR_3 (C_1+C_7)(dL)^22μ and R4′≔DdL2+LC4+2μD+θD2r(μ+dLμD)R_4 DdL2+LC_4+2μ D+ θ D^2r(μ+ dLμ D). Combining upper bounds on (15), (17) and (18) we obtain E[Regbandit(T)]≤R1′log(1+TμDdL)+R2′, E [Reg^bandit(T) ]\;≤\;R _1\, \! (1+T μ DdL )\;+\;R _2, where R1′≔R3′+16C8dL2μ(1−ρ)R_1 R_3 + 16C_8dL^2μ(1-ρ) and R2′≔R4′+(3+θDr)LR_2 R_4 +(3+ θ Dr)L. □ 7.5 Constant Terms In this subsection, we define the constant terms used in our paper. The first set of constants are defined as functions: g1(K,r):=−Krtanh(−Kr) if K<01 if K≥0 g_1(K,r):= cases -Kr ( -Kr)& if K<0\\ 1& if K≥ 0 cases g2(K,r):=1 if K≤0Krcot(Kr) if K>0 g_2(K,r):= cases1& if K≤ 0\\ Kr ( Kr)& if K>0 cases g3(K,r):=16 if K≤01Kr2(rKsin(rK)−1) if K>0 g_3(K,r):= cases 16& if K≤ 0\\ 1Kr^2( r K (r K)-1)& if K>0 cases g4(K,r):=1−Kr2(sinh(r−K)r−K−1) if K<016 if K≥0 g_4(K,r):= cases 1-Kr^2( (r -K)r -K-1)& if K<0\\ 16& if K≥ 0 cases Defining κ:=max|Kmin|,|Kmax|κ:= \|K_ |,|K_ |\, the second set of constants are the absolute constants: C1:=g1(Kmin,D) 12C_1:=g_1(K_ ,D) 12 C2 C_2 :=g2(Kmax,D) :=g_2(K_ ,D) C3:=κg3(Kmax,D) 12C_3:=κ g_3(K_ ,D) 12 C4 C_4 :=(2C3+C6+3C5)D2 :=(2C_3+C_6+3C_5)\,D^2 C6:=κg4(Kmin,δ) 12C_6:=κ g_4(K_ ,δ) 12 C7 C_7 :=max(0,−g2(Kmax,2D)) := (0,-g_2(K_ ,2D)) C8:=cosh(Kmin) 12C_8:= ( K_ ) For C5C_5 find the definition in Lemma 6 of [34]. Finally, for completeness, we present the constants in the regret bound here as well: R1 R_1 ≔4L2μ(1−ρ)+(C1+C7)L22μ 4L^2μ(1-ρ)+ (C_1+C_7)L^22μ R2 R_2 ≔DL2 DL2 R1′ R_1 ≔R3′+16C8dL2μ(1−ρ) R_3 + 16C_8dL^2μ(1-ρ) R2′ R_2 ≔R4′+(3+θDr)L R_4 + (3+ θ Dr )L R3′ R_3 ≔(C1+C7)(dL)22μ (C_1+C_7)(dL)^22μ R4′ R_4 ≔DdL2+LC4+2μD+θD2r(μ+dLμD) DdL2+LC_4+2μ D+ θ D^2r (μ+ dLμ D ) References [1] J. Abernethy, P. L. Bartlett, A. Rakhlin, and A. Tewari (2008) Optimal strategies and minimax lower bounds for online convex games. Proceedings of the 21st Annual Conference on Learning Theory (COLT), p. 415–424. Cited by: §1. [2] P.-A. Absil, R. Mahony, and R. Sepulchre (2009) Optimization algorithms on matrix manifolds. Princeton University Press. Cited by: §1.1. [3] A. Agarwal, O. Dekel, and L. Xiao (2010) Optimal algorithms for online convex optimization with multi-point bandit feedback. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), p. 28–40. Cited by: §1.1, §7.3. [4] M. Akbari, B. Gharesifard, and T. Linder (2017) Distributed online convex optimization on time-varying directed graphs. IEEE Transactions on Control of Network Systems 4 (3), p. 417–428. Cited by: §1.1, §1. [5] F. Alimisis, A. Orvieto, G. Bécigneul, and A. Lucchi (2020) A continuous-time perspective for modeling acceleration in riemannian optimization. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, S. Chiappa and R. Calandra (Eds.), Proceedings of Machine Learning Research, Vol. 108, p. 1297–1307. Cited by: §7.2. [6] A. Asgharivaskasi, F. Girke, and N. Atanasov (2025) Riemannian optimization for active mapping with robot teams. IEEE Transactions on Robotics 41 (), p. 1077–1097. External Links: Document Cited by: §1. [7] S. Bonnabel (2013) Stochastic gradient descent on Riemannian manifolds. IEEE Transactions on Automatic Control 58 (9), p. 2217–2229. Cited by: §1.1. [8] N. Boumal (2023) An introduction to optimization on smooth manifolds. Cambridge University Press. Cited by: §2.1. [9] T. Chang and S. Shahrampour (2021) On online optimization: dynamic regret analysis of strongly convex and smooth problems. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, Vol. 35, p. 6966–6973. Cited by: §1.1. [10] H. Chen and Q. Sun (2024) Decentralized online Riemannian optimization with dynamic environments. Note: arXiv preprint arXiv:2410.05128 Cited by: 2nd item, §1.1, §1.1, Table 1, §1, §1, §2.2, §2.2, §2.3, §3, §3, §5.1. [11] J. Chen, L. Liu, T. Zhu, Y. Liu, G. Dai, Y. Jiang, and I. W. Tsang (2025) Decentralized optimization on compact submanifolds by quantized riemannian gradient tracking. IEEE Transactions on Signal Processing. Cited by: §1.1. [12] S. Chen, A. Garcia, M. Hong, and S. Shahrampour (2021) Decentralized Riemannian gradient descent on the Stiefel manifold. In Proceedings of the 38th International Conference on Machine Learning (ICML), p. 1594–1605. Cited by: §1.1, §1. [13] S. Chen, A. Garcia, M. Hong, and S. Shahrampour (2023) On the local linear rate of consensus on the Stiefel manifold. IEEE Transactions on Automatic Control 69 (4), p. 2324–2339. Cited by: §1.1, §1. [14] K. Deng and J. Hu (2025) Decentralized projected Riemannian gradient method for smooth optimization on compact submanifolds. Numerische Mathematik. Cited by: §1.1, §1. [15] A. D. Flaxman, A. T. Kalai, and H. B. McMahan (2005) Online convex optimization in the bandit setting: gradient descent without a gradient. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 385–394. Cited by: §1.1, §7.3. [16] A. Gang and W. U. Bajwa (2022) A linearly convergent algorithm for distributed principal component analysis. Signal Processing 193, p. 108408. External Links: ISSN 0165-1684, Document, Link Cited by: §1. [17] E. Hazan, A. Agarwal, and S. Kale (2007) Logarithmic regret algorithms for online convex optimization. Machine Learning 69 (2–3), p. 169–192. Cited by: §1.1, §1. [18] S. Hosseini, A. Chapman, and M. Mesbahi (2016) Online distributed convex optimization on dynamic networks. IEEE Transactions on Automatic Control 61 (11), p. 3545–3550. Cited by: §1.1, §1. [19] Z. Hu, G. Wang, and J. D. Abernethy (2023) Riemannian projection-free online learning. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1.1, Table 1, Table 1. [20] A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan (2015) Online optimization: competing with dynamic comparators. In Artificial Intelligence and Statistics, p. 398–406. Cited by: §1.1. [21] J. Kim and I. Yang (2022) Accelerated gradient methods for geodesically convex optimization: tractable algorithms and convergence analysis. In Proceedings of the 39th International Conference on Machine Learning (ICML), Cited by: §1.1. [22] A. I. Maass, C. Manzie, D. Nešić, J. H. Manton, and I. Shames (2022) Tracking and regret bounds for online zeroth-order Euclidean and Riemannian optimization. SIAM Journal on Optimization 32 (2), p. 445–469. Cited by: §1.1. [23] O. Mangoubi and A. Smith (2018) Rapid mixing of geodesic walks on manifolds with positive curvature. The Annals of Applied Probability 28 (4), p. 2501–2543. Cited by: §7.4. [24] D. Martínez-Rubio (2022) Global Riemannian acceleration in hyperbolic and spherical spaces. In Proceedings of the 33rd International Conference on Algorithmic Learning Theory (ALT), p. 768–826. Cited by: §1.1. [25] A. Mokhtari, S. Shahrampour, A. Jadbabaie, and A. Ribeiro (2016) Online optimization in dynamic environments: improved regret rates for strongly convex problems. In Proceedings of the 55th IEEE Conference on Decision and Control (CDC), p. 7195–7201. Cited by: §1.1. [26] D. T. Nguyen and C. A. Uribe (2026) Intrinsic decentralized stochastic riemannian optimization on manifolds with bounded sectional curvature. arXiv preprint arXiv:2603.17096. Cited by: §1.1, §1. [27] P. Petersen (2006) Riemannian geometry. 2 edition, Graduate Texts in Mathematics, Vol. 171, Springer. Cited by: §5.1. [28] E. Sahinoglu and S. Shahrampour (2025) Decentralized online Riemannian optimization beyond Hadamard manifolds. Note: arXiv preprint arXiv:2509.07779 Cited by: 2nd item, 3rd item, §1.1, Table 1, §1, §1, §1, §2.2, §2.2, §2.2, §2.3, §2.3, §2.3, §3, §3, §3, Remark 4.4, §4, §4, §5.1, §5.1, §7.1, §7.2, §7.3. [29] E. Sahinoglu and S. Shahrampour (2025) Online optimization on Hadamard manifolds: curvature independent regret bounds on horospherically convex objectives. Note: arXiv preprint arXiv:2509.11236 Cited by: §1.1. [30] E. Sahinoglu, Y. Sun, and S. Shahrampour (2025) Finite-time analysis of stochastic nonconvex nonsmooth optimization on the Riemannian manifolds. In Advances in Neural Information Processing Systems, Vol. 38. Cited by: 3rd item. [31] A. Sarlette and R. Sepulchre (2009) Consensus optimization on manifolds. SIAM Journal on Control and Optimization 48 (1), p. 56–76. Cited by: §1. [32] H. Sato (2021) Riemannian optimization and its applications. Vol. 670, Springer. Cited by: §1.1. [33] S. Shahrampour and A. Jadbabaie (2018) Distributed online optimization in dynamic environments using mirror descent. IEEE Transactions on Automatic Control 63 (3), p. 714–725. Cited by: §1.1, §1, §2.2, §2.3. [34] Y. Sun, N. Flammarion, and M. Fazel (2019) Escaping from saddle points on Riemannian manifolds. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 32. Cited by: §7.5. [35] Y. Tian, A. S. Bedi, A. Koppel, M. Calvo-Fullana, D. M. Rosen, and J. P. How (2022) Distributed riemannian optimization with lazy communication for collaborative geometric estimation. In 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vol. , p. 4391–4398. External Links: Document Cited by: §1. [36] R. Tron, B. Afsari, and R. Vidal (2013) Riemannian consensus for manifolds with bounded curvature. IEEE Transactions on Automatic Control 58 (4), p. 921–934. Cited by: §1. [37] Y. Wan, T. Wei, M. Song, and L. Zhang (2024) Nearly optimal regret for decentralized online convex optimization. In The Thirty Seventh Annual Conference on Learning Theory, p. 4862–4888. Cited by: §1.1, §6. [38] Y. Wan (2025) Black-box reductions for decentralized online convex optimization in changing environments. In Proceedings of the 38th Annual Conference on Learning Theory (COLT), p. 5605–5631. Cited by: §6. [39] X. Wang, Z. Tu, Y. Hong, Y. Wu, and G. Shi (2023) Online optimization over Riemannian manifolds. Journal of Machine Learning Research 24 (84), p. 1–67. Cited by: §1.1, Table 1, Table 1, §1, §1, §2.2, §2.3, §2.3, Remark 3.4, §3, Remark 4.4, §4, §7.2. [40] X. Wang, D. Yuan, Y. Hong, Z. Hu, L. Wang, and G. Shi (2025) Riemannian online optimistic algorithms with dynamic regret. IEEE Transactions on Automatic Control 70 (10), p. 6481–6496. External Links: Document Cited by: §1.1. [41] X. Wang, R. Borsoi, C. Richard, and A. H. Sayed (2025) Distributed riemannian optimization in geodesically non-convex environments. arXiv preprint arXiv:2512.04915. Cited by: §1.1, §1. [42] F. Yan, S. Sundaram, S. V. N. Vishwanathan, and Y. Qi (2013) Distributed autonomous online learning: regrets and intrinsic privacy-preserving properties. IEEE Transactions on Knowledge and Data Engineering 25 (11), p. 2483–2493. Cited by: §1.1, §1, Remark 3.3. [43] S. Yau (1974) Non-existence of continuous convex functions on certain Riemannian manifolds. Mathematische Annalen 207 (4), p. 269–270. Cited by: §2.3. [44] H. Zhang and S. Sra (2016) First-order methods for geodesically convex optimization. In Proceedings of the 29th Annual Conference on Learning Theory (COLT), p. 1617–1638. Cited by: §1.1, §2.3, §7.2. [45] M. Zinkevich (2003) Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), p. 928–935. Cited by: §1.1. IEEEbiography []Zhanyuan Cai is currently a Ph.D. student in the Department of Mechanical and Industrial Engineering at Northeastern University. He received his B.S. degree in Mathematics and Applied Mathematics from Ocean University of China in 2022, and his M.S. degree in Mathematics from Tianjin University in 2025. His research interests include online optimization, decentralized optimization, and Riemannian optimization, with emphasis on decentralized online optimization and Riemannian geometry. IEEEbiography [] Emre Sahinoglu is currently a Ph.D. candidate in the Department of Mechanical and Industrial Engineering at Northeastern University. He received the B.S. degree in Electrical and Electronics Engineering from Bilkent University, Turkey. His research interests lie at the intersection of machine learning, optimization, and multi-agent systems. In particular, his work focuses on distributed optimization, online optimization, and Riemannian optimization, with applications to learning and decision-making over networks. IEEEbiography [] Shahin Shahrampour received the Ph.D. degree in Electrical and Systems Engineering, the M.A. degree in Statistics (The Wharton School), and the M.S.E. degree in Electrical Engineering, all from the University of Pennsylvania, in 2015, 2014, and 2012, respectively. He is currently an Associate Professor in the Department of Mechanical and Industrial Engineering at Northeastern University. His research interests include machine learning, optimization, sequential decision-making, and distributed learning, with a focus on developing computationally efficient methods for data analytics. He is a Senior Member of the IEEE.