Distributed Online Stochastic Convex-Concave Optimization: Dynamic Regret Analyses under Single and Multiple Consensus Steps

Baoyong Zhang; Deming Yuan; Shengyuan Xu; Vincent K. N. Lau; Wentao Zhang

REVIEW 3 major objections 5 minor 53 references

Distributed Online Stochastic Convex-Concave Optimization: Dynamic Regret Analyses under Single and Multiple Consensus Steps

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2508.09411 v1 pith:T3XPFEVK submitted 2025-08-13 math.OC

Wentao Zhang , Baoyong Zhang , Deming Yuan , Shengyuan Xu , Vincent K. N. Lau This is my paper · ORCID

classification math.OC MSC 90C2590C4768W27

keywords distributedonlineconvex-concaveoptimizationdynamicsaddlepointregretmirrordescentBregmandivergencestochasticgradientmulti-consensusiterationspredictivemappingsmultiagentnetworks

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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^{

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

Minor 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.

The 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[Theorem 1, Eq. (15)(b)] 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.
[Proof of Theorem 1, Eq. (22) y-analog] 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.
[Assumption 4 and Lemma 3 proof] 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.

minor comments (5)

[Abstract] 'no-Euclidean' should read 'non-Euclidean'.
[Remark 1] 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.
[Eq. (4) and Lemma 1 notation] The constants Γ and σ in Lemma 1 are used before their formal definition; consider defining them in the lemma statement for readability.
[Section IV, Eq. (28)] 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.
[Simulations] 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.

Circularity Check

1 steps flagged · score 4.0 of 10

The main theorem relies on an unstated decomposition lemma from the authors' prior paper; otherwise the derivation is self-contained.

self citation load bearing [Section III-B, proof of Theorem 1, Eq. (15), step (b)]
"where Ωx PR(T ) and Ωy PR(T ) represents two non-negative upper bounds that satisfy E[P-Regx d(T )] ≤ Ωx PR(T ) and E[P-Regy d(T )] ≤ Ωy PR(T ), respectively, (a) follows triangle inequality and the fact that |E[s1]| ≤ E[|s1|], s1 ∈ R, and (b) follows Lemma 2 of [25]."

The proof of Theorem 1 replaces the absolute expected dynamic saddle-point regret in Eq. (15) by a consensus penalty plus two partial-regret upper bounds, citing 'Lemma 2 of [25]'. This lemma is not stated, proved, or restated in the present paper, and [25] is the authors' own prior distributed online saddle point work with overlapping authors. The decomposition is load-bearing: without Eq. (15)(b), the subsequent partial-regret bounds in (16)-(22) do not connect to the ESP-Regret definition. Thus the central regret bound inherits a key structural inequality from an unverified self-citation rather than deriving it independently.

full rationale

No fitted constant is renamed as a prediction, and no parameter is calibrated to the data: the regret bounds depend on the problem-dependent path variation V_T and on step-size sequences, and the consensus lemmas are proved in the appendix. The simulation comparison to [25] is empirical and does not enter the proof. The main circularity burden is the single citation to Lemma 2 of [25] at Eq. (15)(b), which is a load-bearing decomposition for the absolute dynamic saddle-point regret and is not independently established in this manuscript. Because the rest of the derivation—stochastic mirror descent with Bregman divergences, predictive mappings, and consensus error bounds—is new and does not reduce to the cited lemma, the central claim retains independent content. This warrants a score of 4 rather than a higher score; there is no construction by definition or fitted prediction.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The central proof depends on standard graph/connectivity, stochastic-gradient, and Bregman assumptions, plus one cited lemma from the authors' own prior work. The tunable step sizes and predictive mappings are algorithmic choices rather than fitted constants, but the simulation selects them favorably.

free parameters (4)

γ1, γ2 = γ1=0.35, γ2=0.4 in simulation
Tuning exponents in step sizes α_t = (1/ε1) t^{-γ1}, η_t = (1/ε2) t^{-γ2}; these control the regret trade-off between T^{θ1} and T^{θ2}(1+V_T).
ε1, ε2 = 1/ε1=3, 1/ε2=15 in simulation
Step size scale constants; chosen by hand to balance constants in practice.
B_t, C_t = B_t = P_t, C_t = I in simulation
Predictive mappings, user-chosen; the path variation V_T depends on them.
K_t = K_t ∈ {1, 3, 6+⌈4/t^{0.2}⌉} in simulation
Number of consensus iterations per round in Algorithm 2; the constant-factor improvement depends on K = min_t K_t.

assumptions (6)

domain assumption Assumption 1: uniform strong connectivity over intervals Q (graph union strongly connected)
Standard condition for consensus convergence in time-varying networks; used in Lemma 1 and Lemma 3.
domain assumption Assumption 2: unbiased, bounded-variance stochastic gradients
Needed for the martingale argument and the Lipschitz bound on f_i,t; typical in stochastic online learning.
domain assumption Assumption 3: Bregman divergence satisfies Lipschitz and convex-mixture inequalities
These properties are not true for all Bregman divergences and are assumed; they are used in (19)-(20) and the partial regret analysis.
domain assumption Assumption 4: predictive mappings B_t, C_t are non-expansive, invariant on X,Y, and satisfy ∥B_t∥≤1, ∥C_t∥≤1
Ensures prediction errors do not accumulate; used in Lemma 3's product bound ∥ΠB[C]∥≤1 and in (20).
domain assumption Assumption 5: each time-step graph is strongly connected (for Algorithm 2)
Stronger than Assumption 1, needed for the one-step contraction in the multiple-consensus analysis.
domain assumption Lemma 2 of [25]: a decomposition bounding the dynamic saddle point regret by the sum of partial regrets plus a consensus penalty
Cited from the authors' prior work without proof; it is the step marked (b) in (15) and is load-bearing for Theorem 1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Distributed Online Stochastic Convex-Concave Optimization: Dynamic Regret Analyses under Single and Multiple Consensus Steps." pith.science (2026). https://pith.science/paper/T3XPFEVK

@misc{pith2026250809411,
  author       = {Pith},
  title        = {Pith review of: Distributed Online Stochastic Convex-Concave Optimization: Dynamic Regret Analyses under Single and Multiple Consensus Steps},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T3XPFEVK}},
  note         = {Machine review of arXiv:2508.09411}
}

abstract

This paper considers the distributed online convex-concave optimization with constraint sets over a multiagent network, in which each agent autonomously generates a series of decision pairs through a designable mechanism to cooperatively minimize the global loss function. To this end, under no-Euclidean distance metrics, we propose a distributed online stochastic mirror descent convex-concave optimization algorithm with time-varying predictive mappings. Taking dynamic saddle point regret as a performance metric, it is proved that the proposed algorithm achieves the regret upper-bound in $\mathcal{O}(\max \{T^{\theta_1}, T^{\theta_2} (1+V_T ) \})$ for the general convex-concave loss function, where $\theta_1, \theta_2 \in(0,1)$ are the tuning parameters, $T$ is the total iteration time, and $V_T$ is the path-variation. Surely, this algorithm guarantees the sublinear convergence, provided that $V_T$ is sublinear. Moreover, aiming to achieve better convergence, we further investigate a variant of this algorithm by employing the multiple consensus technique. The obtained results show that the appropriate setting can effectively tighten the regret bound to a certain extent. Finally, the efficacy of the proposed algorithms is validated and compared through the simulation example of a target tracking problem.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 23 canonical work pages

[25]

Dynamic re gret of distributed online saddle point problem,

W. Zhang, Y . Shi, B. Zhang, D. Y uan, and S. Xu, “Dynamic re gret of distributed online saddle point problem,” IEEE Trans. Autom. Control , vol. 69, no. 4, pp. 2522–2529, 2024

2024
[1]

Online learning and online convex optimiza- tion,

S. Shalev-Shwartz et al. , “Online learning and online convex optimiza- tion,” F ound. Trends Mach. Learn., vol. 4, no. 2, pp. 107–194, 2011

2011
[2]

Introduction to online convex optimization,

E. Hazan et al. , “Introduction to online convex optimization,” F ound. Trends Optim., vol. 2, no. 3-4, pp. 157–325, 2016

2016
[3]

Multi-agent online optimization,

D. Y uan, A. Proutiere, G. Shi et al. , “Multi-agent online optimization,” F ound. Trends Optim., vol. 7, no. 2-3, pp. 81–263, 2024

2024
[4]

A survey on distributed online op timization and online games,

X. Li, L. Xie, and N. Li, “A survey on distributed online op timization and online games,” Annu. Rev. Control , vol. 56, p. 100904, 2023

2023
[5]

Online convex programming and generaliz ed inﬁnitesi- mal gradient ascent,

M. Zinkevich, “Online convex programming and generaliz ed inﬁnitesi- mal gradient ascent,” in Proc. 20th Int. Conf. Mach. Learn. , 2003, pp. 928–936

2003
[6]

Online convex optimization with tim e-varying constraints and bandit feedback,

X. Cao and K. R. Liu, “Online convex optimization with tim e-varying constraints and bandit feedback,” IEEE Trans. Autom. Control , vol. 64, no. 7, pp. 2665–2680, 2019

2019
[7]

Proximal online gradient is optimum for dynamic regret: A general lower boun d,

Y . Zhao, S. Qiu, K. Li, L. Luo, J. Yin, and J. Liu, “Proximal online gradient is optimum for dynamic regret: A general lower boun d,” IEEE Trans. Neural Netw. Learn. Syst. , vol. 33, no. 12, pp. 7755–7764, 2022

2022

Show all 53 references

[8]

Distributed mirror d escent for online composite optimization,

D. Y uan, Y . Hong, D. W. Ho, and S. Xu, “Distributed mirror d escent for online composite optimization,” IEEE Trans. Autom. Control , vol. 66, no. 2, pp. 714–729, 2020

2020
[9]

Distributed bandit online convex optimization with time-varying coupl ed inequality constraints,

X. Yi, X. Li, T. Y ang, L. Xie, T. Chai, and K. H. Johansson, “ Distributed bandit online convex optimization with time-varying coupl ed inequality constraints,” IEEE Trans. Autom. Control , vol. 66, no. 10, pp. 4620– 4635, 2021

2021
[10]

Distributed online op timization in time-varying unbalanced networks without explicit subgra dients,

Y . Xiong, X. Li, K. Y ou, and L. Wu, “Distributed online op timization in time-varying unbalanced networks without explicit subgra dients,” IEEE Trans. Signal Proc. , vol. 70, pp. 4047–4060, 2022

2022
[11]

Distributed constrained online c onvex optimiza- tion over multiple access fading channels,

X. Cao and T. Bas ¸ar, “Distributed constrained online c onvex optimiza- tion over multiple access fading channels,” IEEE Trans. Signal Proc. , vol. 70, pp. 3468–3483, 2022

2022
[12]

Dadam: A consensus- based distributed adaptive gradient method for online opti mization,

P . Nazari, D. A. Tarzanagh, and G. Michailidis, “Dadam: A consensus- based distributed adaptive gradient method for online opti mization,” IEEE Trans. Signal Proc. , vol. 70, pp. 6065–6079, 2022

2022
[13]

Online learning ov er dynamic graphs via distributed proximal gradient algorithm,

R. Dixit, A. S. Bedi, and K. Rajawat, “Online learning ov er dynamic graphs via distributed proximal gradient algorithm,” IEEE Trans. Autom. Control, vol. 66, no. 11, pp. 5065–5079, 2021

2021
[14]

Distributed online o ptimization in dynamic environments using mirror descent,

S. Shahrampour and A. Jadbabaie, “Distributed online o ptimization in dynamic environments using mirror descent,” IEEE Trans. Autom. Control, vol. 63, no. 3, pp. 714–725, 2017

2017
[15]

Distribu ted saddle-point problems: Lower bounds, near-optimal and robust algorithm s,

A. Beznosikov, V . Samokhin, and A. Gasnikov, “Distribu ted saddle-point problems: Lower bounds, near-optimal and robust algorithm s,” Optim. Methods Softw., 2025, DOI: 10.1080/10556788.2025.2463986

2025
[16]

Accelerat ed primal-dual gradient method for smooth and convex-concave saddle-poin t problems with bilinear coupling,

D. Kovalev, A. Gasnikov, and P . Richt´ arik, “Accelerat ed primal-dual gradient method for smooth and convex-concave saddle-poin t problems with bilinear coupling,” in Proc. Adv. Neural Inf. Process. Syst. , 2022, pp. 21725–21737

2022
[17]

Saddle point opti mization with approximate minimization oracle and its application to rob ust berthing control,

Y . Akimoto, Y . Miyauchi, and A. Maki, “Saddle point opti mization with approximate minimization oracle and its application to rob ust berthing control,” ACM Trans. Evol. Learn. Optim. , vol. 2, no. 1, pp. 1–32, 2022

2022
[18]

Convergence analysis of saddle point prob- lems in time varying wireless systems–Control theoretical approach,

J. Chen and V . K. N. Lau, “Convergence analysis of saddle point prob- lems in time varying wireless systems–Control theoretical approach,” vol. 60, no. 1, pp. 443–452, 2012

2012
[19]

Adaptive exact penalty de sign for constrained distributed optimization,

H. Zhou, X. Zeng, and Y . Hong, “Adaptive exact penalty de sign for constrained distributed optimization,” IEEE Trans. Autom. Control , vol. 64, no. 11, pp. 4661–4667, 2019

2019
[20]

Exploiting probl em structure in optimization under uncertainty via online convex optimiza tion,

N. Ho-Nguyen and F. Kılınc ¸-Karzan, “Exploiting probl em structure in optimization under uncertainty via online convex optimiza tion,” Math. Program., vol. 177, no. 1, pp. 113–147, 2019

2019
[21]

The online saddle point pr oblem and online convex optimization with knapsacks,

A. Rivera, H. Wang, and H. Xu, “The online saddle point pr oblem and online convex optimization with knapsacks,” Math. Oper . Res., vol. 50, no. 1, pp. 1–39, 2025

2025
[22]

Online saddle point track ing with decision-dependent data,

K. R. Wood and E. Dall’Anese, “Online saddle point track ing with decision-dependent data,” in Proc. 5th Conf. Learn. Dyn. Control, , 2023, pp. 1416–1428

2023
[23]

Competi ng against Nash equilibria in adversarially changing zero-sum games,

A. R. Cardoso, J. Abernethy, H. Wang, and H. Xu, “Competi ng against Nash equilibria in adversarially changing zero-sum games, ” in Proc. 36th Int. Conf. Mach. Learn. , 2019, pp. 921–930

2019
[24]

Online and bandit algorithms for nonstationary stochastic saddle-po int optimiza- tion,

A. Roy, Y . Chen, K. Balasubramanian, and P . Mohapatra, “ Online and bandit algorithms for nonstationary stochastic saddle-po int optimiza- tion,” arXiv preprint arXiv:1912.01698 , 2019

1912 arXiv
[26]

Non-stationary stocha stic optimiza- tion,

O. Besbes, Y . Gur, and A. Zeevi, “Non-stationary stocha stic optimiza- tion,” Math. Program., vol. 63, no. 5, pp. 1227–1244, 2015

2015
[27]

A d istributed online convex optimization algorithm with improved dynami c regret,

Y . Zhang, R. J. Ravier, M. M. Zavlanos, and V . Tarokh, “A d istributed online convex optimization algorithm with improved dynami c regret,” in Proc. IEEE Conf. Decis. Control , 2019, pp. 2449–2454

2019
[28]

An online saddle point optimization algorithm with regularization,

Y . Xu, Y . Jiang, X. Xie, and D. Li, “An online saddle point optimization algorithm with regularization,” in Proc. IOP Conf. Series:Mater . Sci. Eng., 2019, p. 052035

2019
[29]

A survey of distributed optimiz ation,

T. Y ang, X. Yi, J. Wu, Y . Y uan, D. Wu, Z. Meng, Y . Hong, H. Wa ng, Z. Lin, and K. H. Johansson, “A survey of distributed optimiz ation,” Annu. Rev. Control , vol. 47, pp. 278–305, 2019

2019
[30]

Distributed optimization for con trol,

A. Nedi´ c and J. Liu, “Distributed optimization for con trol,” Annu. Rev. Control Robot. Auton. Syst. , vol. 1, pp. 77–103, 2018

2018
[31]

Distributed subgradient methods and quantization effects,

A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsikli s, “Distributed subgradient methods and quantization effects,” in Proc. IEEE Conf. Decis. Control, 2008, pp. 4177–4184

2008
[32]

Distributed empiri cal risk minimization with differential privacy,

C. Liu, K. H. Johansson, and Y . Shi, “Distributed empiri cal risk minimization with differential privacy,” Automatica, vol. 162, 2024, art. no. 111514

2024
[33]

A dual inexact nonsmooth ne wton method for distributed optimization,

D. Niu, Y . Hong, and E. Song, “A dual inexact nonsmooth ne wton method for distributed optimization,” IEEE Trans. Signal Proc. , vol. 73, pp. 188–203, 2025

2025
[34]

Differentially private dis tributed op- timization over time-varying unbalanced networks with lin ear conver- gence rates,

Z. Y ang, W. He, and S. Y ang, “Differentially private dis tributed op- timization over time-varying unbalanced networks with lin ear conver- gence rates,” IEEE Trans. Signal Proc. , vol. 73, pp. 1138–1152, 2025

2025
[35]

Distributed algo rithms for composite optimization: Uniﬁed framework and convergence analysis,

J. Xu, Y . Tian, Y . Sun, and G. Scutari, “Distributed algo rithms for composite optimization: Uniﬁed framework and convergence analysis,” IEEE Trans. Signal Proc. , vol. 69, pp. 3555–3570, 2021. IEEE TRANSACTIONS TEMPLA TE, VOL. XX, JUNE 2025 12

2021
[36]

Distributed dual gradient tracking for resource allocation in unbalanced networks,

J. Zhang, K. Y ou, and K. Cai, “Distributed dual gradient tracking for resource allocation in unbalanced networks,” IEEE Trans. Signal Proc. , vol. 68, pp. 2186–2198, 2020

2020
[37]

Distributed saddle- point subgradient algorithms with Laplacian averaging,

D. Mateos-N´ unez and J. Cort´ es, “Distributed saddle- point subgradient algorithms with Laplacian averaging,” IEEE Trans. Autom. Control , vol. 62, no. 6, pp. 2720–2735, 2016

2016
[38]

Decentralized distributed optimization for saddle point problems,

A. Rogozin, A. Beznosikov, D. Dvinskikh, D. Kovalev, P . Dvurechensky, and A. Gasnikov, “Decentralized distributed optimization for saddle point problems,” arXiv preprint arXiv:2102.07758 , 2021

2021 arXiv
[39]

Distributed saddle-point problems under data similarity,

A. Beznosikov, G. Scutari, A. Rogozin, and A. Gasnikov, “Distributed saddle-point problems under data similarity,” in Proc. Adv. Neural Inf. Process. Syst., 2021, pp. 8172–8184

2021
[40]

A distributed stochastic ﬁ rst-order method for strongly concave-convex saddle point problems,

M. I. Qureshi and U. A. Khan, “A distributed stochastic ﬁ rst-order method for strongly concave-convex saddle point problems, ” in Proc. IEEE Conf. Decis. Control , 2023, pp. 4170–4175

2023
[41]

B. T. Polyak, Introduction to optimization . New Y ork, NY , USA: Optimization Software, Inc, 1987

1987
[42]

Distributed online optimiza tion over a heterogeneous network with any-batch mirror descent,

N. Eshraghi and B. Liang, “Distributed online optimiza tion over a heterogeneous network with any-batch mirror descent,” in Proc. 37th Int. Conf. Mach. Learn. , 2020, pp. 2933–2942

2020
[43]

Fast distrib uted gradient methods,

D. Jakoveti´ c, J. Xavier, and J. M. Moura, “Fast distrib uted gradient methods,” IEEE Trans. Autom. Control , vol. 59, no. 5, pp. 1131–1146, 2014

2014
[44]

On stochastic subgradient mirror- descent algo- rithm with weighted averaging,

A. Nedic and S. Lee, “On stochastic subgradient mirror- descent algo- rithm with weighted averaging,” SIAM J. Optim. , vol. 24, no. 1, pp. 84–107, 2014

2014
[45]

Event- triggered distributed stochastic mirror descent for convex optimiza tion,

M. Xiong, B. Zhang, D. W. C. Ho, D. Y uan, and S. Xu, “Event- triggered distributed stochastic mirror descent for convex optimiza tion,” IEEE Trans. Neural Netw. Learn. Syst. , vol. 34, no. 9, pp. 6480–6491, 2023

2023
[46]

Clustering with bregman divergences

A. Banerjee, S. Merugu, I. S. Dhillon, J. Ghosh, and J. La fferty, “Clustering with bregman divergences.” J. Mach. Learn Res. , vol. 6, no. 10, 2005

2005
[47]

Joint and separate con vexity of the bregman distance,

H. H. Bauschke and J. M. Borwein, “Joint and separate con vexity of the bregman distance,” Stud. Comput. Math. , vol. 8, pp. 23–36, 2001

2001
[48]

Matrix nearness problems with bregman divergences,

I. S. Dhillon and J. A. Tropp, “Matrix nearness problems with bregman divergences,” SIAM J. Matrix Anal. Appl. , vol. 29, no. 4, pp. 1120–1146, 2008

2008
[49]

Distributed on line convex optimization with time-varying coupled inequality constr aints,

X. Yi, X. Li, L. Xie, and K. H. Johansson, “Distributed on line convex optimization with time-varying coupled inequality constr aints,” IEEE Trans. Signal Proc. , vol. 68, pp. 731–746, 2020

2020
[50]

Distributed online bandit learning in dynamic environments over unbalanced digraphs ,

J. Li, C. Li, W. Y u, X. Zhu, and X. Y u, “Distributed online bandit learning in dynamic environments over unbalanced digraphs ,” IEEE Trans. Netw. Sci. Eng. , vol. 8, no. 4, pp. 3034–3047, 2021

2021
[51]

Adaptive online learni ng in dynamic environments,

L. Zhang, S. Lu, and Z.-H. Zhou, “Adaptive online learni ng in dynamic environments,” in Proc. Adv. Neural Inf. Process. Syst. , 2018, pp. 1330– 1340

2018
[52]

Ben-Tal, L

A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust optimization . Princeton, NJ, USA: Princeton Univ. Press, 2009

2009
[53]

Comm unication- efﬁcient gradient descent-accent methods for distributed variational inequalities: Uniﬁed analysis and local updates,

S. Zhang, S. Choudhury, S. U. Stich, and N. Loizou, “Comm unication- efﬁcient gradient descent-accent methods for distributed variational inequalities: Uniﬁed analysis and local updates,” arXiv preprint arXiv:2306.05100, 2023

2023 arXiv

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [25]

Dynamic re gret of distributed online saddle point problem,

W. Zhang, Y . Shi, B. Zhang, D. Y uan, and S. Xu, “Dynamic re gret of distributed online saddle point problem,” IEEE Trans. Autom. Control , vol. 69, no. 4, pp. 2522–2529, 2024

2024

[2] [1]

Online learning and online convex optimiza- tion,

S. Shalev-Shwartz et al. , “Online learning and online convex optimiza- tion,” F ound. Trends Mach. Learn., vol. 4, no. 2, pp. 107–194, 2011

2011

[3] [2]

Introduction to online convex optimization,

E. Hazan et al. , “Introduction to online convex optimization,” F ound. Trends Optim., vol. 2, no. 3-4, pp. 157–325, 2016

2016

[4] [3]

Multi-agent online optimization,

D. Y uan, A. Proutiere, G. Shi et al. , “Multi-agent online optimization,” F ound. Trends Optim., vol. 7, no. 2-3, pp. 81–263, 2024

2024

[5] [4]

A survey on distributed online op timization and online games,

X. Li, L. Xie, and N. Li, “A survey on distributed online op timization and online games,” Annu. Rev. Control , vol. 56, p. 100904, 2023

2023

[6] [5]

Online convex programming and generaliz ed inﬁnitesi- mal gradient ascent,

M. Zinkevich, “Online convex programming and generaliz ed inﬁnitesi- mal gradient ascent,” in Proc. 20th Int. Conf. Mach. Learn. , 2003, pp. 928–936

2003

[7] [6]

Online convex optimization with tim e-varying constraints and bandit feedback,

X. Cao and K. R. Liu, “Online convex optimization with tim e-varying constraints and bandit feedback,” IEEE Trans. Autom. Control , vol. 64, no. 7, pp. 2665–2680, 2019

2019

[8] [7]

Proximal online gradient is optimum for dynamic regret: A general lower boun d,

Y . Zhao, S. Qiu, K. Li, L. Luo, J. Yin, and J. Liu, “Proximal online gradient is optimum for dynamic regret: A general lower boun d,” IEEE Trans. Neural Netw. Learn. Syst. , vol. 33, no. 12, pp. 7755–7764, 2022

2022