{"id":"bb8cdcb2-879c-4201-a96d-dd68d1e62279","arxiv_id":"2508.09411","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Two distributed online stochastic mirror descent algorithms achieve dynamic saddle point regret O(max{T^{θ1}, T^{θ2}(1+V_T)}) under Bregman divergence, generalizing earlier Euclidean results to stochastic, non-Euclidean settings.","lead":"This paper designs two distributed algorithms for online saddle-point problems where agents cooperate to minimize a time-varying convex-concave loss, using mirror descent and predictive mappings. It proves dynamic regret bounds that grow sublinearly under certain conditions and shows simulations on a target-tracking problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 hinges on Eq. (15)(b), which invokes the unstated Lemma 2 of [25]; the signed partial regrets bounded in (16)-(22) may not control the absolute dynamic saddle-point regret.","rationale":"The reader's weakest assumption identifies exactly the load-bearing step: Lemma 2 of [25] is used without proof or restatement in Eq. (15)(b). My reading confirms this is the point where the proof would collapse if the lemma is weaker than needed. The paper is otherwise a standard mirror-descent/consensus analysis, and the derivations after (15)(b) are plausible. I would not reject outright: the cited lemma may be correct and may even be standard in the authors' prior work. But a conditional acceptance should require either a statement/proof of the lemma or an independent check that the absolute regret is controlled. A secondary concern is that the abstract's claim 'sublinear provided V_T is sublinear' is too strong: the bound T^{theta2}(1+V_T) is sublinear only if V_T=o(T^{1-theta2}), not for every sublinear V_T. This is also worth fixing, but it is secondary to the decomposition issue.","tokens_in":21546,"tokens_out":25832,"duration_ms":253394,"concrete_test":"Re-derive Lemma 2 of [25] in the notation of this paper and check the exact inequality used in (15)(b). Then test that inequality on the single-agent loss f(x,y)=x^2-(y-x)^2, X=Y=[-1,1], B_t=C_t=I, at a feasible algorithm iterate (x_1,y_1)=(1,0.5), with (x*,y*)=(0,0): compute P-Reg_x, P-Reg_y, the consensus term (zero for n=1), and |f-f*|. If the lemma requires signed P-Reg terms, the inequality fails (0.75 > 0.25); if it requires absolute values, the paper must provide matching absolute partial-regret bounds. This settles whether Theorem 1's proof has a gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Step (b) of Eq. (15) is the hinge of Theorem 1. It invokes Lemma 2 of [25] to replace the absolute expected regret of the agent-j sequence by the two partial regrets P-Reg_x, P-Reg_y plus a consensus penalty. The current paper gives no statement of this lemma, so the reader cannot check whether its conclusion matches the signed quantities actually bounded in Eqs. (16)-(22). The sign of P-Regy is especially delicate: P-Regy^d = sum_i [f_i(x_i,y*) - f_i(x_i,y_i)] is the online-concave-maximization regret and can be negative, while the theorem needs an upper bound on |sum_i f_i(x_i,y_i) - sum_i f_i(x*,y*)|. If Lemma 2 controls only the signed one-sided regrets, Eq. (15)(b) is false in simple single-agent cases; if it controls absolute values, then the partial-regret bounds in (22) and their 'similarly' y-analog do not establish it, because those bounds are one-sided. Either way, the main regret bound rests on an unverified external result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed online convex-concave optimization (OCCO) over time-varying directed graphs, where each agent has access only to stochastic gradients of a local convex-concave loss function. It proposes a distributed online stochastic mirror descent algorithm with Bregman divergences and time-varying predictive mappings (Algorithm 1), and a variant with multiple consensus iterations (Algorithm 2). The performance metric is the expected dynamic saddle-point regret defined in Eq. (2). The main theoretical claim, Corollary 1, is an O(max{T^θ1, T^θ2(1+V_T)}) bound for Algorithm 1, with θ1 and θ2 determined by the step-size exponents, and Corollary 2 gives an analogous bound for Algorithm 2 with an improved consensus coefficient. The paper also reports numerical experiments on a target-tracking problem.","tokens_in":21871,"tokens_out":19634,"duration_ms":193895,"significance":"If the main bounds are correct, the paper makes a useful contribution to distributed OCCO by extending the existing Euclidean/subgradient analysis to non-Euclidean mirror descent with stochastic gradients and predictive mappings. The explicit distinction between the single-consensus and multi-consensus consensus error coefficients, Lemmas 3 and 4, is a genuine and potentially transferable technical contribution. The paper also provides a fairly complete simulation study, including comparisons with several centralized and distributed baselines. However, the central proof hinges on an external lemma from the authors' prior work, and the current manuscript does not state or prove that lemma; this needs to be addressed before the results can be independently verified.","major_comments":[{"comment":"The key inequality (15)(b) is justified solely by 'Lemma 2 of [25]', but that lemma is neither stated nor proved in this manuscript. This is load-bearing: the entire regret bound follows from replacing the absolute expected dynamic saddle-point regret by the sum of the two partial regrets plus a consensus penalty. The definitions of P-Regx and P-Regy in the proof are signed quantities; for individual agents and time steps they need not be nonnegative, so it is not immediate that the upper bounds in (16)-(22) control the absolute value in (15)(a). A self-contained statement and proof of Lemma 2 of [25]—or an equivalent direct argument using the global saddle-point property of f_t=Σ f_i,t—must be included. Without it, the main theorem is not verifiable from the manuscript.","section":"Theorem 1, Eq. (15)(b)"},{"comment":"The bound for E[P-Regy_d(T)] is dismissed by 'similarly'. This is not a purely cosmetic omission: P-Regy compares f_i(x_i,t, y*_t) with f_i(x_i,t, y_i,t), and because y*_t is the global saddle-point coordinate rather than the maximizer of f_i(x_i,t, ·), the sign of this quantity is not controlled a priori. The mirror-ascent argument that gives the claimed upper bound in (22) should be written out explicitly, including the treatment of the noise term, so the reader can verify that the same telescoping and Assumptions 3-4 apply.","section":"Proof of Theorem 1, Eq. (22) y-analog"},{"comment":"Assumption 4 imposes ∥B_t∥≤1 and B_t x∈X, but B_t and C_t are not explicitly stated to be linear or to be defined as operators. The proof of Lemma 3 uses ∥Π_B(t,1)∥≤Π_t∥B_t∥, which only makes sense for linear operators or requires a Lipschitz/nonexpansive definition on X. A short clarification of the standing assumptions on B_t,C_t is needed.","section":"Assumption 4 and Lemma 3 proof"}],"minor_comments":[{"comment":"'no-Euclidean' should read 'non-Euclidean'.","section":"Abstract"},{"comment":"The tuning γ1=γ2=1/2−log_T√(1+V_T) makes γ depend on the unknown horizon-scaled variation and may violate γ∈(0,1) for large V_T; the statement would benefit from an explicit condition under which this choice is admissible.","section":"Remark 1"},{"comment":"The constants Γ and σ in Lemma 1 are used before their formal definition; consider defining them in the lemma statement for readability.","section":"Eq. (4) and Lemma 1 notation"},{"comment":"The exponent in (28) is written as σ1^{∑_p K_p−1}; this is consistent with Lemma 1 applied per block, but the notation σ1^{(t−s+1)K−1} in Eq. (45) is a bit ambiguous and could be made clearer by bracketing.","section":"Section IV, Eq. (28)"},{"comment":"The text around Fig. 8 states that SP-FTL 'cannot converge'; since the normalized regret is plotted, it would be helpful to state whether the plotted value is the raw normalized regret or a log-scale plot with a plateau.","section":"Simulations"}],"recommendation":"major_revision","confidential_remarks":"The main proof relies on Lemma 2 of the authors' own previous paper [25] without restatement. Given that this lemma is the hinge of Theorem 1, I would encourage the editor to require that the authors either reproduce the lemma and its proof or replace it with a self-contained argument. This is a matter of verifiability rather than novelty, but it is essential for a journal publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuine contribution here is the package: distributed online convex-concave optimization under Bregman divergence, stochastic gradients, time-varying predictive mappings, and optional multi-consensus steps, all handled in one dynamic-regret analysis. The mirror-descent machinery is standard, the consensus error bounds via transition matrices look correct, and the multi-consensus variant cleanly quantifies the trade-off between communication frequency and regret. On its own terms the paper is a solid, if incremental, extension of [25] from the Euclidean deterministic setting to the non-Euclidean stochastic one.\n\nThe soft spot is concentrated in one place: step (b) of Eq. (15). The proof invokes Lemma 2 of [25] to go from the absolute dynamic saddle-point regret to the two partial regrets, but that lemma is not stated, so I cannot check whether it applies to the signed quantities actually bounded in (16)-(22). The worry is real: P-Regy can have either sign, and the theorem needs an upper bound on the absolute value of the sum, while the proof only supplies one-sided upper bounds on the individual partial regrets. The stress-test note's counterexample worry is not resolved by anything in the manuscript. This is not a fatal flaw in the overall approach—plausibly Lemma 2 of [25] does establish the needed decomposition—but it is load-bearing and it is not verifiable from the text. That alone forces a conditional verdict.\n\nMinor issues: the simulations lack error bars, and Remark 1 contains a puzzling step-size formula that seems to misstate the resulting bound. These are fixable. The abstract's claim of sublinearity when V_T is sublinear is technically correct, though the bound's dependence on V_T is standard.\n\nThe paper deserves serious peer review: the combination is new, the proof framework is familiar, and the multi-consensus analysis is a reasonable addition. But the authors must state and justify the decomposition step in detail, and ideally prove the analogue of Lemma 2 of [25] for this setting. I would not cite the main theorem until that is settled.","headline":"A useful but incremental extension of [25] to Bregman mirror descent, stochastic gradients, and multi-consensus, whose main theorem leans on an unverified decomposition from the authors' own prior work.","tokens_in":22317,"tokens_out":9498,"would_cite":false,"duration_ms":90696,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C47","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"A distributed mirror-descent algorithm establishes sublinear expected dynamic saddle-point regret for online convex-concave games over networks, under stochastic gradients and general Bregman distances.","keywords":["distributed online convex-concave optimization","dynamic saddle point regret","mirror descent","Bregman divergence","stochastic gradient","multi-consensus iterations","predictive mappings","multiagent networks"],"falsifier":"Run Algorithm 1 on ten agents over a switching three-graph network with bilinear loss $f_t(x,y)=\\langle x,y\\rangle$ on the unit cube, zero gradient noise, and $B_t=C_t=I$. With a static saddle point ($V_T=0$) and $\\gamma_1=\\gamma_2=1/2$, Corollary 1 predicts average dynamic regret at most $C\\sqrt{T}$; with $\\gamma_1=0.8,\\gamma_2=0.2$ the predicted growth exponent is $\\max\\{1-\\gamma_1,1-\\gamma_2,\\gamma_1,\\gamma_2\\}=0.8$. Measured linear growth, or an exponent that ignores this tuning, would indicate the decomposition at step (b) of (15) — the imported lemma — failed.","tokens_in":21490,"feed_emoji":"🎯","tokens_out":24119,"duration_ms":213199,"temperature":0.7,"pith_summary":"Distributed online optimization usually stops at convex losses, but many practical problems—target tracking, robust optimization, transmission-jamming games—have convex-concave (saddle-point) structure. This paper claims that a distributed online stochastic mirror-descent algorithm solves such problems over a time-varying multiagent network with sublinear expected dynamic saddle-point regret, using only noisy gradient estimates and a general Bregman distance instead of the Euclidean norm. The bound is $\\mathcal{O}(\\max\\{T^{\\theta_1}, T^{\\theta_2}(1+V_T)\\})$, with $\\theta_1,\\theta_2\\in(0,1)$ set by the step sizes and $V_T$ the path variation of the moving saddle points; regret is sublinear precisely when $V_T=o(T)$. A multi-consensus variant repeats the averaging step several times per round and provably shrinks the consensus penalty, tightening the bound at the cost of extra communication. A sympathetic reader would care because the paper moves distributed saddle-point learning from Euclidean, exact-gradient settings toward the noisy, non-Euclidean regime that applications actually present.","feed_headline":"Network agents can track a drifting equilibrium with vanishing error","feed_subtitle":"Expected saddle-point regret stays sublinear under noisy gradients, non-Euclidean distances, and sublinear drift.","key_machinery":"The engine is the mirror-descent step in a Bregman divergence $\\Psi_R(u,v)=R(u)-R(v)-\\langle\\nabla R(v),u-v\\rangle$; the strongly convex potential $R$ ranges from the Euclidean norm to the KL divergence on a simplex. Each agent takes the stochastic mirror step $\\nabla R_x(z_{i,t})=\\nabla R_x(x_{i,t})-\\alpha_t\\tilde\\nabla^x_{i,t}$, projects back in Bregman geometry, applies a nonexpansive predictive mapping $B_t$ (resp. $C_t$), and averages neighbors' decisions with a doubly stochastic matrix. The proof splits the absolute dynamic regret into two one-sided partial regrets plus a consensus penalty, telescopes Bregman differences so saddle-point drift becomes the $V_T$ terms, and controls the p","core_discovery":"The central claim is that the proposed DOSMD-CCO algorithm gives every agent expected dynamic saddle-point regret $\\mathcal{O}(\\max\\{(1+\\Gamma/(1-\\sigma))T^{\\theta_1},\\,T^{\\theta_2}(1+V_T)\\})$, where $\\theta_1=\\max\\{1-\\gamma_1,1-\\gamma_2\\}$, $\\theta_2=\\max\\{\\gamma_1,\\gamma_2\\}$, and $V_T$ is the saddle-point path variation relative to predictive mappings $B_t,C_t$. Two consequences are claimed directly: per-round regret vanishes when $V_T=o(T)$, and $\\gamma_1=\\gamma_2=1/2$ yields $\\mathcal{O}(\\sqrt{T}(1+V_T))$, tunable to the optimal centralized rate when $V_T$ is known. The paper further claims that $K_t$ consensus rounds per iteration shrink the consensus coefficient to $\\Gamma_1\\sigma_1^{","pith_inferences":["If the imported decomposition lemma were reproved in full for convex-concave losses, the same mirror-descent scaffolding would likely extend to losses outside the paper's scope, such as nonconvex-concave functions or bandit (value-only) feedback, where the saddle-point structure persists.","The explicit dependence of the consensus term on the mixing constants suggests a tuning rule the paper leaves implicit: choose the number of consensus rounds $K_t$ inversely with the network's mixing speed, since poorly connected networks benefit disproportionately from multi-consensus.","The bound's dependence on $V_T$ points to an adaptive extension: estimate $V_T$ online from observed displacements of the ensemble decision and adjust step sizes accordingly, removing the paper's working assumption that the path variation is known.","A dedicated comparison of KL-divergence versus Euclidean mirror descent on a simplex-constrained tracking problem would test whether the closed-form update delivers the practical speedup the paper's simulations suggest, in the regime where both bounds hold."],"forward_implications":["Per-round expected dynamic regret of every agent vanishes as $T$ grows whenever the saddle points drift sublinearly ($V_T=o(T)$), so the network tracks a moving equilibrium without being told its motion.","Setting $\\gamma_1=\\gamma_2=1/2$ gives the bound $\\mathcal{O}(\\sqrt{T}(1+V_T))$, and with $V_T$ known the step-size tuning can reach the optimal centralized dynamic-regret rate.","Running $K_t$ consensus rounds per iteration shrinks the consensus penalty by the factor $\\sigma_1^{K-1}$ relative to a single round, tightening the bound, with the largest gains on slowly mixing networks.","Because the analysis holds for any Bregman divergence, the guarantees transfer to simplex-constrained problems, where the mirror step is a closed-form multiplicative rule rather than a projection.","Predictive mappings move the path variation into the predicted frame: the better the prediction $B_tx_t^*\\approx x_{t+1}^*$, the smaller $V_T$ and the tighter the regret."],"supporting_citations":[{"why":"Supplies the decomposition lemma used at step (b) of (15) to split absolute dynamic regret into two partial regrets plus a consensus penalty, and the prior Euclidean distributed saddle-point algorithm that this paper generalizes.","marker":"[25]"},{"why":"Provides Lemma 1, the bound on how fast products of doubly stochastic weight matrices converge to the uniform matrix, which controls the consensus disagreement penalty in Lemma 3.","marker":"[31]"},{"why":"Establishes the distributed mirror-descent machinery with Bregman divergence, the KL-divergence closed-form update used in the simulations, and the multiple-consensus assumption framework.","marker":"[8]"},{"why":"Introduces dynamic-regret mirror descent with predictive mappings; its nonexpansive mappings and dynamic regret analysis are the template for Assumptions 3-4 and the path-variation terms.","marker":"[14]"},{"why":"Formulates the stochastic subgradient oracle conditions (unbiasedness, bounded second moments) adopted as Assumption 2 for the noisy gradients.","marker":"[44]"},{"why":"Supplies the optimal centralized dynamic-regret rate that Remark 1 compares against when claiming the tuning is optimal.","marker":"[51]"}],"fun_headline_variants":["Dynamic regret stays sublinear under drift and non-Euclidean metrics","Distributed online algorithm tracks drifting equilibria with vanishing regret","Multiple consensus steps tighten dynamic regret bounds in networked optimization","Saddle-point regret vanishing even with noisy gradients and moving targets","No Euclidean distance needed: sublinear dynamic regret in multiagent optimization"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The load-bearing premise is an imported lemma from the authors' earlier paper (Lemma 2 of [25]), cited without proof here, that the absolute dynamic saddle-point regret of the network splits, up to a Lipschitz-driven consensus penalty, into the sum of two one-sided partial regrets; if that splitting fails for general convex-concave losses, the main regret bound does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Dynamic regret stays sublinear under drift and non-Euclidean metrics","Distributed online algorithm tracks drifting equilibria with vanishing regret","Multiple consensus steps tighten dynamic regret bounds in networked optimization","Saddle-point regret vanishing even with noisy gradients and moving targets","No Euclidean distance needed: sublinear dynamic regret in multiagent optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00021,"raw_usage":{"total_tokens":1286,"prompt_tokens":824,"completion_tokens":462,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":377}},"tokens_in":568,"tokens_out":462,"duration_ms":5815,"temperature":1.0,"reasoning_tokens":377,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T21:04:57.595574+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on ten agents over a switching three-graph network with bilinear loss $f_t(x,y)=\\langle x,y\\rangle$ on the unit cube, zero gradient noise, and $B_t=C_t=I$. With a static saddle point ($V_T=0$) and $\\gamma_1=\\gamma_2=1/2$, Corollary 1 predicts average dynamic regret at most $C\\sqrt{T}$; with $\\gamma_1=0.8,\\gamma_2=0.2$ the predicted growth exponent is $\\max\\{1-\\gamma_1,1-\\gamma_2,\\gamma_1,\\gamma_2\\}=0.8$. Measured linear growth, or an exponent that ignores this tuning, would indicate the decomposition at step (b) of (15) — the imported lemma — failed.","supporting_citations":[],"review_version":1}