{"id":"6e94d33f-e443-4b75-911f-6fc7bf1ae49d","arxiv_id":"2509.07779","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Decentralized online Riemannian optimization is shown to achieve O(sqrt T) regret on manifolds with bounded positive curvature under gradient and bandit feedback.","lead":"This paper derives O(sqrt T) static regret bounds for decentralized online optimization on curved spaces that can have positive curvature, covering both full gradient and two-point bandit feedback. It also proves a curvature-aware consensus step converges linearly, extending prior Hadamard-manifold results.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Consensus step-size used in the regret proofs differs from the step-size stated in the theorems, so the stated algorithms are not the ones analyzed.","rationale":"I read the paper as aiming to show O(√T) regret for decentralized online Riemannian OGD beyond Hadamard manifolds, using the consensus-step contraction of Theorem III.2 as the key engine. The proof skeleton is coherent and the reader's CONDITIONAL is justified. The most load-bearing issue I find is not the diameter bound itself but the mismatch between the consensus step-size for which the contraction is proved and the step-size stated in the subsequent theorems: Lemma IV.1/Theorem IV.2 state s = α(4C1)^{-1}(1−σ2), while Theorem IV.2's proof uses s = C2/(2C1). Since Theorem III.2's contraction coefficient ρ is derived for the latter, applying it to the stated former step-size is unjustified as written. The same mismatch propagates into the bandit section, since it relies on the full-information network-error lemma. This is a genuine correctness-repair issue, not fraud or an unsupported novelty claim. I do not think it changes the verdict: the manuscript is already CONDITIONAL, and the concern is plausibly fixable by consistent parameterization. The reader's rationale listed the step-size mismatch among other inconsistencies, but their weakest_assumption focused on the diameter/convexity-radius condition; I partially agree with that too, but the step-size mismatch is the more direct obstruction to the stated theorems.","tokens_in":21634,"tokens_out":39930,"duration_ms":445370,"concrete_test":"Carry out the network-error recursion with the stated step-size s = α(4C1)^{-1}(1−σ2(W)): compute ρ(s) = 1 − 2(sC2 − C1 s^2)(1−σ2)/(1+C4D^2)^2 and check whether the recursion (14) can be made to yield the stated bound (8) with denominator (1−σ2)^2 α^2. Independently, rerun the proof of Theorem IV.2 replacing the line \"s = C2/(2C1)\" by the stated s and verify that Σ_i(d^2(x_{i,t+1},x*) − d^2(y_{i,t+1},x*)) ≤ 0 still holds. If either check fails, the theorem statements as written are unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem III.2 proves linear variance reduction only for s = C2/(2C1). Lemma IV.1 and Theorem IV.2 state that Algorithm 1 uses s = α(4C1)^{-1}(1−σ2(W)). In the proof of Theorem IV.2, immediately after Eq. (17), the authors write \"Since we have s = C2/(2C1) ≤ C2/C1\" and use this value to show Σ_i T_{i,5} ≤ 0. The proof of Lemma IV.1 also invokes Theorem III.2's contraction coefficient ρ, which is computed for the optimal step-size, not for the smaller stated step-size. Hence, if a reader implements the step-size stated in the theorems, the network-error bound (8) and the regret bound (9) do not follow from the manuscript's proof; if the proof's step-size is used instead, the theorem statements and Algorithm 1 are mis-specified. This is the load-bearing soft spot because every regret bound in Sections IV and V inherits the consensus contraction coefficient. The O(√T) dependence is plausibly recoverable by choosing one step-size consistently, but as written the central theorems are not proven for the stated algorithms.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies decentralized online Riemannian optimization on manifolds with bounded sectional curvature, allowing positive curvature. The authors prove a linear variance-reduction property for the Riemannian consensus step (Theorem III.2), and then use it to establish O(sqrt T) static regret for full-information decentralized online Riemannian gradient descent (Theorem IV.2) and for the two-point bandit feedback setting (Theorem V.2). The analysis is based on curvature comparison inequalities and assumes the domain has diameter D < pi/(2 sqrt(Kmax)) when Kmax > 0. The central claims are that neither positive curvature nor decentralization changes the optimal-in-T regret rate.","tokens_in":21861,"tokens_out":11662,"duration_ms":111128,"significance":"If the main theorems are correct, this is a significant contribution to online Riemannian optimization: it removes the Hadamard-manifold restriction in decentralized settings and gives the first O(sqrt T) two-point bandit bound in this setup. The consensus step-size optimization and the subconvexity analysis of smoothed objectives are interesting, and the proofs are provided in detail with no fitted parameters or circular derivations. However, the stated theorems and the proofs use different consensus step-sizes, so the results are not yet established as written. The issue appears local and fixable, which supports a major revision rather than rejection.","major_comments":[{"comment":"The stated algorithm and the analyzed algorithm use different consensus step-sizes. Lemma IV.1 and Theorem IV.2 state s = alpha(4C1)^{-1}(1 - sigma2(W)), whereas Theorem III.2 proves linear variance reduction only for s = C2/(2C1). In the proof of Lemma IV.1, the contraction coefficient rho is used as computed in Theorem III.2 without re-derivation for the stated s; in the proof of Theorem IV.2, immediately after Eq. (17), the text says 'Since we have s = C2/(2C1) <= C2/C1' to conclude sum_i T_{i,5} <= 0. Consequently, the network-error bound (8), the full-information regret bound (9), and, by inheritance, the bandit regret bound (11) are not proven for the step-size stated in the theorems. The O(sqrt T) conclusion is plausibly recoverable by consistently setting s = C2/(2C1) or by re-doing the contraction analysis for the smaller stated s, but as written the central theorems do not appl","section":"Section IV (Lemma IV.1, Theorem IV.2) and Section VII-D"},{"comment":"The contraction coefficient is mis-specified. Theorem III.2 states rho = 1 - C3^2(1 - sigma2(W)) / (4 C1 (1 + C4 D^2)^2), but the proof in Appendix VII-B derives rho = 1 - C2^2(1 - sigma2(W)) / (4 C1 (1 + C4 D^2)^2) by maximizing q(s) = s C2 - s^2 C1. The constant C3 is never defined; Appendix VII-H simply refers to Lemma 4 of [43]. Since rho enters the network-error bound and the constant C5, this is a load-bearing inconsistency. In addition, the equality in Lemma IV.1, 2 sqrt(n) eta L / (1 - rho) = 8 C1 sqrt(n) eta L / ((1 - sigma2(W))^2 alpha^2), does not follow from the definitions of alpha and rho given in the paper.","section":"Section III (Theorem III.2) and Appendix VII-H"}],"minor_comments":[{"comment":"Several constants are left as pointers to external references ('For C3 and C4, find the definition in Lemma 4 of [43]; for C8, find the definition in Lemma 3 of [43]'). For a self-contained proof these constants should either be stated explicitly or the cited statements reproduced with their hypotheses.","section":"Appendix VII-H"},{"comment":"The numerical experiments use consensus step-sizes s in {0.6, 0.8, 1}, which do not correspond to the theoretically analyzed step-size s = C2/(2C1) nor to the value stated in Lemma IV.1. A short remark explaining the relation, or clarifying that the experiments are illustrative, would improve the paper.","section":"Section VI"},{"comment":"The theorem statement says delta = O(1/sqrt T) and tau = O(delta), while the proof chooses delta = 1/T and tau = delta/(r theta). The statement and proof should be aligned. Also, the bound O(eta^{-1} + eta T + sqrt T) is redundant once eta = O(1/sqrt T); the proof actually yields O(eta^{-1} + eta T + 1).","section":"Theorem V.2 and its proof"},{"comment":"Minor typographical issues include 'proprty' in the conclusion, inconsistent accents on Frechet, and the cross-reference 'Section Proof VII-D'. These do not affect the mathematics.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The step-size mismatch is the main concern; it is a theorem/proof inconsistency rather than a fundamental flaw. If the authors can make the step-size choices consistent and correct the definition of rho, the paper's contribution would be substantial. I recommend major revision, not rejection. The paper would also benefit from a careful pass to define all constants in the appendix and to align the experimental step-sizes with the theory."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something real. It takes Chen and Sun's decentralized online Riemannian framework, which required Hadamard manifolds, and gets O(√T) regret for full-information and two-point bandit feedback under bounded sectional curvature with a small-diameter assumption. The consensus variance-reduction step with a curvature-tuned step-size is the genuinely new piece, and the subconvexity analysis of smoothed objectives is new as far as I know. If the results stand, they close a previously open problem.\n\nThe load-bearing problem is an internal inconsistency in the step-size. Theorem III.2 proves linear variance reduction for s = C2/(2C1). Lemma IV.1 and Theorem IV.2 state that Algorithm 1 uses s = α(4C1)^{-1}(1−σ2(W)), which is a different, smaller value. The proof of Theorem IV.2 then uses s = C2/(2C1) to show the consensus error term is nonpositive. The network-error bound (8) and the regret bound (9) inherit this mismatch, so as written the theorems are not proven for the stated algorithm. This is a mechanical statement-versus-proof error rather than a sign of a fundamentally wrong approach; the O(√T) rate is plausibly recoverable by picking one step-size consistently and adjusting the contraction coefficient ρ accordingly. The bandit proof has a milder version: Theorem V.2 states δ = O(1/√T), but the proof sets δ = 1/T and τ = δ/(rθ), which changes the final expression. Again repairable.\n\nOther soft spots: Assumption II.2(ii) restricts the domain to diameter less than π/(2√Kmax), so the positive-curvature result is really for mildly curved, small patches. The authors are honest about this, but it tempers the \"beyond Hadamard\" claim. The experiments are thin—one sphere, one network topology, no error bars, no code—so they add little. The citation pattern is fine: self-citations are to their own previous work in related settings, external geometric lemmas are properly attributed, and there are no fitted parameters or circular derivations.\n\nOverall, this is a serious paper with a correctable flaw. It deserves a serious referee, not a desk rejection. I would send it to review with the expectation of major revision. I would not cite it in its current form, but I would bring it to a reading group to work through the proof details.\n\nRecommendation: send to peer review, with instructions to the authors to reconcile the stated algorithms with the analyzed step-sizes.","headline":"Solid extension of decentralized Riemannian OCO beyond Hadamard manifolds, but the stated and analyzed consensus step-sizes disagree; the central O(√T) claims look recoverable with a careful revision.","tokens_in":22364,"tokens_out":1819,"would_cite":false,"duration_ms":20331,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"On manifolds with bounded positive curvature, a curvature-tuned Riemannian consensus step contracts disagreement at a linear rate, and this paper shows the same O(sqrt T) regret for decentralized online gradient descent and two-point bandit","keywords":["decentralized optimization","online Riemannian optimization","positive curvature","regret bounds","two-point bandit","geodesic convexity","randomized smoothing","consensus"],"falsifier":"On a unit sphere (Kmax = 1), place three points at vertices of a small equilateral spherical triangle inside a ball of radius pi/8 (diameter < pi/2), apply the consensus update with s = C2/(2C1), and measure Var after one step; Theorem III.2 predicts a contraction ratio rho < 1. A configuration inside the stated diameter bound with ratio >= 1 would refute it. Likewise, running Algorithm 1 on the sphere with eta = 1/sqrt T and tracking cumulative regret should grow like sqrt T; a visibly superlinear trajectory would refute Theorem IV.2.","tokens_in":21487,"feed_emoji":"📐","tokens_out":7236,"duration_ms":78483,"temperature":0.7,"pith_summary":"This paper sets out to show that decentralized online optimization on curved spaces does not have to settle for worse regret rates once positive curvature is allowed. The authors prove that a specific Riemannian consensus step—each agent moves a tuned fraction of the way toward its neighbors along geodesics—contracts disagreement linearly even on manifolds with bounded positive sectional curvature, not just Hadamard manifolds. Building on that contraction, they show decentralized online Riemannian gradient descent achieves O(sqrt T) static regret under full gradient feedback, and the same O(sqrt T) rate under two-point bandit feedback using smoothed gradient estimators. The upshot: neither decentralization nor positive curvature needs to change the optimal dependence on the time horizon.","feed_headline":"O(sqrt T) regret survives positive curvature","feed_subtitle":"A curvature-tuned consensus step keeps the Euclidean O(sqrt T) rate on curved manifolds.","key_machinery":"The consensus step (1) is the load-bearing object: a curvature-aware averaging rule that replaces Euclidean weighted averages by exponential-map combinations. Its step size s is chosen to balance two opposing curvature effects—positive curvature weakens the convexity needed for contraction while negative curvature weakens smoothness—and the analysis uses geodesic law-of-cosines inequalities (Lemma II.4) together with a bound on how much exponential maps distort tangent-space distances (Lemma II.5) to obtain a uniform contraction rate rho < 1.","core_discovery":"The central claim is that the consensus update x_i(s) = Exp_{y_i}(s sum_j w_ij Log_{y_i} y_j), with step size s = C2/(2C1), has variance contraction Var({x_i(s)}) <= rho Var({y_i}) with rho in (0,1) whenever the domain is a geodesically convex set of diameter below pi/(2 sqrt(Kmax)). This is Theorem III.2. The contraction coefficient depends on the network spectral gap, curvature bounds, and domain diameter through curvature-dependent constants. Armed with it, the paper proves Theorem IV.2: with gradient step size eta = O(1/sqrt T) and consensus step size s = alpha(1 - sigma_2(W))/(4 C1), decentralized online Riemannian gradient descent has regret at most D C5 sqrt T. Theorem V.2 then extend","pith_inferences":["A test this paper does not run: if the consensus contraction is as general as claimed, offline decentralized Riemannian optimization with strongly geodesically convex objectives should inherit linear convergence on positively curved manifolds, since the hard part is exactly the variance-reduction lemma.","The diameter restriction D < pi/(2 sqrt(Kmax)) means the theory covers geodesic balls smaller than a quarter circumference; on spheres that is natural, but a natural next question is whether the rate survives domains crossing the convexity radius with additional projection care.","The bandit estimator has a dimensional factor d entering through the bound ||g^delta|| <= dL, so in high-dimensional manifolds the constant grows; tightening this dimensional dependence or proving a lower bound is a separate question.","The same consensus step might extend to time-varying networks if sigma_2(W) is replaced by a worst-case connectivity factor, but that extension is not analyzed here."],"forward_implications":["Decentralized online Riemannian gradient descent achieves O(sqrt T) static regret on manifolds with bounded sectional curvature, including positive curvature, matching the Euclidean optimal rate in T.","Two-point bandit feedback carries the same O(sqrt T) rate, so zeroth-order queries do not asymptotically hurt beyond the full-gradient setting.","The consensus step is isolated as a stand-alone linear variance-reduction result, so other decentralized Riemannian algorithms that can control network error can reuse the contraction bound.","The regret matches centralized Riemannian and decentralized Euclidean rates, so curvature and decentralization do not introduce an extra asymptotic penalty under the stated assumptions.","When Kmax = 0, the results reduce to the Hadamard-manifold setting, giving a unified treatment of both negatively and positively curved spaces."],"supporting_citations":[{"why":"Supplies the consensus update (1) and the Hadamard-manifold analysis that this paper extends to bounded sectional curvature.","marker":"[11]"},{"why":"Establishes centralized Riemannian online regret baselines and provides projection and comparator inequalities reused in the full-information proof.","marker":"[6]"},{"why":"Provides the computationally efficient randomized smoothing gradient estimation technique used in Algorithm 2.","marker":"[15]"},{"why":"Extends the randomized smoothing estimator framework that the bandit analysis builds on.","marker":"[16]"},{"why":"Supplies the geodesic law-of-cosines inequalities (Lemma II.4) that carry the curvature accounting for the consensus and regret proofs.","marker":"[42]"},{"why":"Supplies tangent-space distortion bounds (Lemma II.5 and related constants) used in the consensus variance and subconvexity analyses.","marker":"[43]"},{"why":"Gives the Riemannian projection characterization used to control the network error after each gradient step.","marker":"[46]"}],"fun_headline_variants":["Curvature-tuned consensus locks in O(sqrt T)","Positive curvature? Not for this consensus step","Riemannian online descent keeps optimal regret","Decentralized curved-space optimization hits O(sqrt T)","Consensus step tames positive curvature for regret"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"All iterates and the comparator must stay within a geodesically convex ball whose diameter is strictly less than pi/(2 sqrt(Kmax)); if the domain is larger or the positive curvature is too strong, the lower-bound constants that make consensus contract can lose their sign.","fun_headline_variants_meta":{"raw":{"variants":["Curvature-tuned consensus locks in O(sqrt T)","Positive curvature? Not for this consensus step","Riemannian online descent keeps optimal regret","Decentralized curved-space optimization hits O(sqrt T)","Consensus step tames positive curvature for regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000148,"raw_usage":{"total_tokens":1010,"prompt_tokens":710,"completion_tokens":300,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":226}},"tokens_in":454,"tokens_out":300,"duration_ms":3585,"temperature":1.0,"reasoning_tokens":226,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T21:42:33.853885+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a unit sphere (Kmax = 1), place three points at vertices of a small equilateral spherical triangle inside a ball of radius pi/8 (diameter < pi/2), apply the consensus update with s = C2/(2C1), and measure Var after one step; Theorem III.2 predicts a contraction ratio rho < 1. A configuration inside the stated diameter bound with ratio >= 1 would refute it. Likewise, running Algorithm 1 on the sphere with eta = 1/sqrt T and tracking cumulative regret should grow like sqrt T; a visibly superlinear trajectory would refute Theorem IV.2.","supporting_citations":[{"cited_title":"Decentralized Online Riemannian Optimization with Dynamic Environments","cited_arxiv_id":"2410.05128","evidence_quote":"Supplies the consensus update (1) and the Hadamard-manifold analysis that this paper extends to bounded sectional curvature."},{"cited_title":"Online optimization over riemannian manifolds,","cited_arxiv_id":null,"evidence_quote":"Establishes centralized Riemannian online regret baselines and provides projection and comparator inequalities reused in the full-information proof."},{"cited_title":"Stochastic zeroth-order rieman- nian derivative estimation and optimization,","cited_arxiv_id":null,"evidence_quote":"Provides the computationally efficient randomized smoothing gradient estimation technique used in Algorithm 2."},{"cited_title":"Zeroth-order riemannian averaging stochastic approximation al- gorithms,","cited_arxiv_id":null,"evidence_quote":"Extends the randomized smoothing estimator framework that the bandit analysis builds on."},{"cited_title":"A continuous- time perspective for modeling acceleration in riemannian optimization,","cited_arxiv_id":null,"evidence_quote":"Supplies the geodesic law-of-cosines inequalities (Lemma II.4) that carry the curvature accounting for the consensus and regret proofs."},{"cited_title":"Escaping from saddle points on riemannian manifolds,","cited_arxiv_id":null,"evidence_quote":"Supplies tangent-space distortion bounds (Lemma II.5 and related constants) used in the consensus variance and subconvexity analyses."},{"cited_title":"On the metric projection onto convex sets in riemannian spaces,","cited_arxiv_id":null,"evidence_quote":"Gives the Riemannian projection characterization used to control the network error after each gradient step."}],"review_version":1}