A Near-Optimal Algorithm for Decentralized Convex-Concave Finite-Sum Minimax Optimization
Authors: Hongxu Chen
Ke Wei
Haishan Ye
Luo Luo
Venue: NeurIPS 2025 spotlight ()
Keywords: Minimax optimization
decentralized optimization
stochastic algorithm
variance reduction
Primary area: optimization

Abstract: In this paper, we study the distributed convex-concave finite-sum minimax optimization over the network, and a decentralized variance-reduced optimistic gradient method with stochastic mini-batch sizes (DIVERSE) is proposed. For the strongly-convex-strongly-concave objective, it is shown that DIVERSE can achieve a linear convergence rate that depends on the global smoothness parameters, yielding sharper computation and communication complexity bounds than existing results. Furthermore, we also establish the lower complexity bounds, which show that our upper bounds are optimal up to a logarithmic factor in terms of the local incremental first-order oracle calls, the computation rounds, and the communication rounds. Numerical experiments demonstrate that our algorithm outperforms existing methods in practice.

A Near-Optimal Algorithm for Decentralized Convex-Concave Finite-Sum Minimax Optimization
Hongxu Chen'
Ke Wei!
Haishan Ye
Luo Luo
'School of Data Science, Fudan University School of Management, Xi'an Jiaotong University SSII AI Lab, State Grid Corporation of China
SShnghaii Key Laboratory for Contemporary Applied Mathematics (hxchen20, kewei] @uddn edu. cn yehaishan@xjtu. edu. cn
luoluo0fudan edu. cn
Abstract
In this paper, we study the distributed convex-concave finite-sum minimax opti- mization over the network, and a decentralized variance-reduced optimistic gradient method with stochastic mini-batch sizes (DIVERSE) is proposed. For the strongly- convex-strongly-com -tons--ooooocccccaeeeeeeeee objective, is shown that DIVERSE can achieve a linear convergence rate that depends the global smoothness parameters, yielding sharper computation and communication complexity bounds than existing results. Furthermore, we also establish the lower complexity bounds, which show that our upper bounds are optimal up to a logarithmic factor terms of the local incremental first-order oracle calls, the computation rounds, and the communica- tion rounds. Numerical experiments demonstrate that our algorithm outperforms existing methods in practice.
Introduction
In this paper, we consider the following distributed minimax optimization problem
min
yx.,))
f(x,y),
(1)
xER4a yeRdv
where the global objective f: RRd x Rdd + R is
We assume
the local function fa R.d Rdd, IR on the i-th node has the finite-sum structure of the form
f(x,)) = 1 Σ (x,
(2)
where each St, is smooth. This formulation appears in many fields, including game theory 9 21
robust optimization 10 29)] and control theory [45]. In particular, it has received increasing attention recently from the machine learning community, with the rise of adversarial generative networks
[5] adversarial training 49 68 71 77). and reinforcement learning [8] 75).
The first-order minimax optimization has been studied extensively over the past decades. Gradient descent ascent (GDA) a natural extension of gradient descent in minimization problem, which is comnestone for many minimax optimization algorithms [1 51). In the extragradient (EG)
method, [24] 34 [3] an intermediate prediction step is introduced to improve the convergence of
GDA, which exhibits the optimal convergence rate under the convex-concave assumption [59 89
Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Additionally, the optimistic gradient descent ascent (OGDA) method [61 optimal convergence rate, by incorporating the momentum-like term. In the more general variational inequality framework, Kotsalis et al. 355 proposed an optimal operator extrapolation method.
64 can also achieve the
For large-scale optimization arising from machine learning, it is desirable to design efficient stochastic algorithms by exploiting the finite-sum structure in the objective since computing the full gradient is usually expensive. The variance reduction ideas used achieve the optimal incremental first-order
oracle (IFO) complexity bounds in the minimization problem ( 4 20 extended to minimax optimization, though the details are quite involved. Palaniappan and Bach [60] incorporated variance reduction into GDA iteration and provided an catalyst acceleration framework. Chavdarova et al. [16] and Alacaoglu al. [3] studied the EG method with variance reduction for a specific minimax problem. Alacaoglu and Malitsky (2) introduced a retracted term into the iteration of EG and OGDA, achieving the optimal IFO complexity for the finite-sum minimax problem under the convex-concan setting [26].
32
37
78 90 have been
The decentralized optimization have been widely studied in recent years. Compared with the centralized scenario, it can avoid the communication and computation bottlenecks for problems over networks [57 82 87], while the algorithm design and analysis are more challenging since each node
in a network can only directly share the information with its neighbors. For the minimax optimization,
Mukherjee and Chakraborty [55), Beznosikov et [13], and Luo and Ye [46] developed EG methods for the decentralized setting and provided the linear convergence rates. Rogozin et al. [65] extended
the results the -uc-luciidnnn mirror prox framework. Kovalev et al. 33 combined variance reduction and the optimistic gradient method [6]] within the ADOM framework
[38] achieving the
best-known upper complexity bound on the computation rounds and the communication rounds.
It is worth noting that exiting decentralized minimax optimization methods require identical mini- batch size for all the nodes when constructing the local gradient estimator, which is sample inefficient. Moreover, both the computation complexity and communication complexity of previous works depend on the local smoothness parameters. It remains an open question on how to develop the decentralized minimax optimization algorithm that depends on the global smoothness parameters.
In this paper, propose decentralized auriance-reduced optimistic gradient method with stochastic mini-hatch sizes (DIVERSE) for the minimax problem ( which can find an e-suboptimal solution with ((mm + min (mn //nT.)////////m /b) log (1/c)) local incremental first-order oracle (LIFO) calls, ((n++//u+ L/M min (,L, / /nt/mL//////// / /1) (1/e)/)) computation rounds, and pl/x//)llg()//e com- pa
munication rounds. Here, L the smoothness parameter of the objective f. L the mean-squared smoothness parameter of the function set (fyl"" and is the characteristic number of the mixing matrix associated with the network. The corresponding lower bounds have also been established which demonstrate that all the above results are (nearly) optimal. We would like to emphasize that all of our complexity bounds have the global smoothness dependency, which are tighter than existing Moreover, the linear convergence guarantee in this paper only requires the global objective function f to be strongly-conver sertll-oooooteteooy-eeoee- -tonong and the local component function fi, (also the local function fi) can even be nonconvex-nonconeen This relaxes the assumption for the state-of-the the-art linear convergent decentralized algorithm in Kovalev et al. [39] that requires each fo to be monnglyyyoonee-sttoogyyoooooo concave..
results that only rely on the local smoothness (39 46 55
2 Preliminaries
In this section, we introduce the problem setup, followed by review of the related work.
2.1 Problem Setup
We use the bold lowercase letters to represent vectors, c.g., X E Rdd and y E Rdd, use x; E 1xd, and y, E glxd, to denote the local variables on the i-th node. The bold uppercase letters are used to denote the matrices aggregating the corresponding vectors, such as X = [xii...; xm]] E mx,, and = y :y E Rmdd, The bold lowercase letter with bar presents the average of local variables, e.g.
2==1 x; and y // E yi. The notations 1 and 0 are vectors (or matrices) whose entries are all one and zero, respectively. We let I be the identity matrix. The notation || represents the Euclidean norm of vector or the Frobenius norm of matrix.
2

---

For the minimax optimization problem (1) we stack the variables E Rd and E R as x R where d₃ d₂ + dy. We further define the gradient operators as
m Σ (i( ER.
g.(z) = E and g(z) (z) = Vy (x,
We make the following assumptions for the decentralized minimax optimization problem U Assumption 2.1. The global function y) is westrongly-convex-pee p-strrogggoogyyyycccevee i.e., the function y() is p-strongly convex for all given x E Rd and the function f(x,-) is j-sttrongly concave for all given y E B
Assumption 2.2 (global smoothness). The global functtin is L-smooth, i.e., for all z, E Rd, there exists constant L > 0 such that
lg(z) g(z')l1 L2
z2112. 1/112-1'11-
Assumption 2.3 (mean- smoothness). The function set (fr.) bijz m.n is L-mean-squared smooth, i.e. for all z, E Rdd there exists a constant T. > 0 such that
g (z) (z)(21) 5 F/2 2'12
Assumption 2.1 is equivalent to the strong monotonicity of the gradient operator g, i.e., for all z, E RR, it holds (g(z) g(z'), (izz),, z²) 2 ul|z z²|1² Note that we have
llg(z) - g(2')||
mm ΣΣ (2) - gz)(z')1 < L?|1z - 2'11
for all z, z' E RRd.. Therefore, it holds that L < for the tight parameters and satisfying Assumptions 2.2 and 2.3 In fact, L can be arbitrarily larger than L there are no convexity/concavity assumption for the local functions 48
Our complexity analysis considers the upper and lower bounds with respect to the global smoothness parameter L and the mquan-s smoothness parameter In contrast, existing works for decentral- ized minimax optimization only consider the local smoothness assumptions. For example, Mukherjee and Chakraborty (55) and Luo and Ye [66] assume there exists a constant Lumax > 0 such that
|gg (z) gi, (z')ll 11 < 2
z'12²
for all z, z' E Rd, i e [m], and [n]] Kovalev et al. and L > 0 such that
39 assume there exist constants
(z) g: (z()l1 < T-712 - 2/12
and
72 Σ
(B) B., < T. - z/112
for all 12 E Rdd and i [m]. Noting that the constants L, and L are determined by the "worst" local (component) function that can verify that L L, T-max and T. S I4 S Temax for the tight smoothness parameters that satisfy the above assumptions [48]. The examples Appendix A demonstrate that the magnitude of these smoothness parameters differ significantly under data heterogeneity.
In decentralized optimization, each node can only directly communicate with its neighbors. The communication step is usually expressed based on a mixing matrix W Rmxxm which satisfies the following standard assumption [28 66 87].
Assumption 2.4. Let W E Rmxm be mixing matrix associated with network. We assume
(a) W is symmetric with wij 2 0 for all i, j. and wi,j + 0 if and only if nodes i and connected or j;
(b) 0 < W < I, w W W1 and mull(I W) sspnn1).

---

Table 1: We summarize the complexity for finding the e-suboptimal solution of problem ① We use the notation (-)) to hide the logarithmic terms with respect to m, n, ja, and the smoothness parameters. Note that the computation rounds may not be proportional to the LIFO calls, since distributed algorithms include the scheme of partial participated computation.
Algorithms
Calls
Computation Rounds
Communication Rounds
GT-EG SS
m0
log
log
log
MC-SVRE 16
mm
/
log
(2))
of
Vi
log
log
OADSVI 8
o
log
vinl
Log
WxTl 1
Log
Je
14
DIVERSE Thereem 3.7
mina macc,, y vmmLi
log
( o( a+
min(md. v /
log
log
Je
14
1
Lower Hounds Theorem
finmm y /mml)
log
a((= + ("
minfrlt Lt vmrpaa)
log
log
(!)
Assumption 2.4 indicates that 1 - X2 (W) > O, where 22 (W) is the second largest eigenvalue of W E R x Thus, we can define the characteristic number X == 1/(1 - (W)).
In this paper we consider the e-suboptimal solution of problem i.e., the point yx such that
||x x2 + Iyy y0
where (x",y" ) is the solution of problem ① that satisfies f(x",'') S f(x", y(x for all x' E Rd and y' E RR4, Noting that the solution (x",y") is unique under the strongly-convex- strongly-coneat assumption.
)
2.2 Related Work
Significant advancement has been made for decentralized optimization over the last decade. For the minimization problem, the convergence of decentralized gradient descent (DGD) with decaying step sizes has been established by Duchi et al. Tsianos and Rabbat [74), and Jakovetić et al. [31]. The gradient tracking technique was introduced in Nedic et al. [56). Qu and Li (63) and Song et al. [6), so that constant step size can be utilized and linear convergence was achieved for strongly-convex objective. Pu and Nedié [22), Koloskova et al. (33. Ye and Chang 851 further investigated the convergence of gradient tracking under stochastic setting. Scaman et al. [66]. Kovalev et al. (38) and Ye al. (87 introduced the multi-consensus steps by Chebyshev acceleration 5 43
further
improve the communication complexity. For the objective with the finite-sum structure, Xin et al.
[8]] Ye al. [86). Hendrikx et al. (28). and Li al. [41] integrated the variance reduction techniques to improve the computational efficiency of the algorithms. In recent works [44, 48 [2], different
types of smoothness parameters have been considered and sharper complexity bounds have been established for the decentralized finite-sum minimization problems.
55 proposed the GT-EG method by combining gradient tracking with EG, proving its linear convergence under the strongly- convex-strongly--oneea
For decentralized minimax optimization, Mukherjee and Chakraborty
assumption. Later, Luo and Ye [46) improved the decentralized EG method by incorporating variance reduction 22 and multi-consensus steps (5 43). achieving better complexity bound on the LIFO calls. It worth noting that the convergence for both of these methods require the assumption that each component function Js, is -mooth. In a seminal work, Kovalev et al. (39 considered the relaxed conditions that only assume each local function fa is Li-smooth and each local function set by is (--mean-squree smooth. The authors introduced an extra momentum term into the variance-reduced OGDA method 22] that they could take the advantage of mini-batch sampling to construct an accurate stochastic gradient estimator, leading to improved computation complexity and communication complexity. The lower bounds were also established therein to justify the optimality of their algorithm with respect to the local smoothness parameters L, and L, However, has considered the potentially tighter complexity bounds with respect to the global smoothness in Assumptions 2.2 and and which will be well-addressed in this paper. We compare our theoretical results with related work in [
none of the previous works on decentralized minimax optimization [3 46 55

---

Algorithm 1 FastMixx(") W, Rt)
1- (
1: Initialize: U-1 U0, 1/0 1+ 1- 1+V1-2311
2: for 0.,,..., do
3: U--1= (1 11-1- U--1
4: end for
5: Output: U
Algorithm 2 DIVERSE
1: Input: initial point zº, step size 1), mini-batch size b, probability p E [0. 1], parameters a, 8 E
[0, 1]. mixing matrix W, iteration numbers K, communication rounds R
2: V-1 v Z Z 1z".S-1 A-1 0
3: for = 0,1,2 K do
4: for = 1....... in parallel
5: Sij Lid Bernoulli(q) with = b/(mn)
6: 8% = (v,
[z,(Zz)) (v, 1 ((8)((²)) (1,(2,-11)
j=1
7: end for
8: s FastMix(S* 1- + A k k-1 W R)
9: Z FastMix (1 3)z* vvv S/ R)
FastMix (Z W) with probability - p
with probability p,
10: y++1
Vv
11: end for
12: Output: z!th = z
3
Algorithm and Complexity Analysis
The proposed decentralized yariance-reduced optimistic gradient method with stochastic mini-batch sizes (DIVERSE) is described in Algorithm 2 which is based on novel sampling strategy and the subroutine of multi-consensus steps (Algorithm [p. The details of the algorithm and complexity
analysis presented in Sections 3.1 and 3.2 respectively.
3.1
Algorithm Design
Recall that the standard OGDA update
19 54
is given by
k+1
z²
7
Lg(g
g(( g(z
optimistic gradient
where is the step size. To improve the computational efficiency by using the finite-sum structure the local function, DIVERSE constructs the variance-reduced optimistic gradient estimator at node i as follows
5.¹ g. + Σ th g (Bi)(a)) Bi,(v a (B:)(2))) (1,
where ck Lid Bernoulli(g) with g b/ b/(mn) and v k-1 is the snapshot point, and > is the momentum parameter. The distribution of et, means we only need to compute the gradient operator gij in equation 3 when st, 1. Note that the snapshot point k+1 is updated with probability in
5

---

each iteration (see Line 10 of Algorithm 2). which implies the term [v(v in equation (3 can be reused with probability 1-pp p. Therefore, the expected LIFO calls the algorithm each iteration O(mmp- + (1 p)b), which is much more efficient than the cost of accessing the full gradient if we take p < and b < mn.
The main difference between DIVERSE and exiting decentralized minimax optimization methods 39
55 is that the mini-batch size for the local gradient estimator 8 in equation (3) is not 46
required be fixed since the variables { 1n..
random. Therefore, the behaviors of all m nodes are similar to the large mini-batch sampling on a single machine. Besides, the steps of gradient tracking and multi-consensus in Lines 8 and of Algorithm 2
ensures that the local variables sufficiently close to each other, resulting in the sharper complexity bounds with respect to the global smoothness.
3.2 Complexity Analysis
For the convergence analysis of DIVERSE (Algorithm based on the mean vectors as follows
2)
define the following Lyapunov function
1 17
3/
+ B - 1112 -v
1
Φ
112
2
112 -1
--=-11²
2
11
811
3 + TH
+ 2(g((z=)) g(z") x" - =²) +
| z²11?
pd
It is not hard verify that the Lyapunov function &h is always non-negative for all v S 1/(4L) (see Appendix B.T).
We first consider the case of T. S /mnl, in which the Lyapunov function satisfies the following relation.
Lemma 3.1. Under Assumptions
2.2
2.3 and 2.4 with < 1s
I. I.
/ /mnI, we run
Algorithm 2 with
1
L
Vmn a max 1 pm
pnp
17 16L
3=p-
7L
max
L
4
+ 17
L
mmn }]. and R = (VXlog(mm
b min
Then holds that
E [ S alE (+) Ci ( [1 - -12*113 + 1Z 12 +
||| 1 10 104-1111)
where Ci = (1 + a²) (12 /bb + SnT.2/1²)
To characterize the convergence of the multi-consensus steps (Algorithm define
p p=
We have P < 1 if R is sufficient large. See more properties of Algorithm iin Appendix B.2 We then bound the consensus error follows.
Lemma 3.2. Under the settings of Lemma 3.1 we have
E z 1+1 12 S 3p²(1
E [|
B
V
1
3p2 2 [||S 1|
and
E [[ - 1
pp k
12"1|3]
p)E [| 1 +
Noting that the upper bound Lemma for S can be bounded as follows.
3.2 depends on the term || 18 112 the consensus error

---

Lemma 3.3. Under the settings of Lemma 3.1 we have
E [[SS - 1|] v C2p² RR [1 - 18 [|]] E 1Z 1 1| + E [IVV - 15
+ E [1 - 15 111] + C3 [IISt 1s |1]] Cap² [ + IE [ + E [ 1])
where C2 n C3 180m² 2200m2n22 n22 C₁ 616 + m) and o
Remark 3.4. Lemma 3.3 shows that the upper bound E [|| - 1s 1| does not only depend on the consensus error the k--th iteration, but also on that of the (A: 1- iteration. In contrast, the
consensus error in the decentralized minimization problem only depends on the term related to the previous iteration [40] [4 [8 [87] The difference poses a challenge in the analysis, which requires
us to develop a novel inductive proof technique.
Applying Lemmas 3.133.1 3.3 we obtain the linear convergence for the Lyapunov function and consensus errors.
Lemma 3.5. Under the settings of Lemma 3.1 we have
1 1-a ā á
E [000] S 00,0
E [
-12
1=
4C1
1-
ā a
1-a ā a x+ 411²Ci
E I1IV 1
x0
and
E
||IS
1s
4C1
where ā = max {1 - un/8 1///8.11 pn (2(3 + nu))}.
According to the parameter settings in Lemma 3.1 the linear convergence rate à achieved by Lemma 3.5 has the order of @ - - 14/L), which depends on the global smoothness. The expected
overall LIFO complexity to achieve the c-suboptimal solution is O( + /mnL/j) log (1/c)).
matching the complexity of variance-reduced EG/OGDA on single machine [2].
We then consider the case of L, S L/ /mmi Note that under the setting of Lemma 3.1 one has b 2 mn
in this case. which motivates us to use the exact local gradients. That is, we set = 0 and = mn in Algorithm when L < L/ /mn, which leads to & q 1 and
, g (2t) + a (g) gi (z)-1)).
Hence, the snapshot vi is unnecessary, so we set and define the simplified I Lyapunov function
/ = (1 3p
1z
1|2 2(g(("=11 - g((z)) -zz))
2
4n
Similar to the analysis of Lemma 3.5 the linear convergence can also be achieved with respect to the global smoothness.
Lemma 3.6. Under Assumptions
2.7
2.2
2.3 and 2.4 with 0 < 1 < L < L/ymn, we run wad and R O (oggoo/(m)).)))
Algorithm 2 with 1 = 1/(16)), 3 Then it holds that
0,
mn, a
V <
(1
am &
TO
Iz 12 v 48n 122
12211 (1 (2))
1+1
T
2
112
Mn k+1
and ||S - 15
<
40
48
2
According to Lemma 3.6 we achieve the LIFO complexity of (( (1))). It is worth noting that the expected overall LIFO complexity of O( + /mnL/H) log(1 (1/e) achieved by variance reduction (under the parameter settings in Lemma 3.1 I is worse than the LIFO complexity achieved by iterations with exact local gradients in the also observed by Luo et al. [48) in nonconvex minimization. Our result implies that the trade-off between variuece-reduced gradient estimator and the exact gradient is also necessary in minimax optimization.
of L < L/ Lmm. Similar phenomenon
Combining the results of Lemmas 3.5 and 3.6 yields the following upper complexity bounds.
7

---

Theorem 3.7. Under Assumptions 2.1 2.2 2.3 and 2.4 with 0 < μ. H running DIVERSE (Algorithm 2) with appropriate parameter settings can find an e-suboptimal solution at each node, with the expected LIFO complexity of ((mm + min min(mnL,, /mnl.) /n) log(1/s)), the expected computation rounds of Ö((n + L/u + min(nL, vn/mL)/// log(1/e)), and the communication rounds of O(vxL/uloo(LL/))
As demonstrated in Table 1 all of our upper bounds in Theorem 3.7 are sharper than state-of-the-arr results since we have L S L1 S. Lmax and L S Li S Lmax for the tight smoothness parameters. Additionally, our LIFO complexity depends on vm in the case of L S /nnnL which is better than existing results that always depends on m. These improvements essentially rely on the sampling strategy that does not fix the mini-batch size on different nodes, thereby allowing partial participation to reduce computational costs.
Remark 3.8. The computation rounds in Algorithm 2 depend E[max [m] Ej=1 st,] which may not be proportional to the LIFO calls. We upper bound this quantity by using the locally uub-Gaussian property, which simplifies the analysis in Liu et al. [44] and Luo et al. [48), see Lemma C.1 for details.
4 The Lower Complexity Bounds
In this section, we establish the lower complexity bounds of the first-order methods for the decen- tralized finite- sum minimax optimization. Specifically, we consider the local incremental first-order oracle algorithms as follows,
Definition 4.1. A local incremental first-order oracle (LIFO) algorithm network of m nodes satisfies the following constraints:
Local memory: Each node stores vectors in local memories M and My at time f > 0. The local memories updated through local computation local communication, i.e., for all E [m]. it holds MN, S .M U UMM and My S MM U UM
Local computation: At time i, each node i can query the local first-order oracles Vxli, (x, and (y y) for any E -M and y M Additionally, the local computational memories M and Mg comp.y satisfy M compp. = Span ((x, Vxhis(x,)) : E M%
and M = Span ((x, (x,t)(xx)) y E MY,
Local communication: At time each node i can communicate with its neighbours (i).. For all i E [m]. the communication memories are defined as M = Span(U)eNaa M
and i,t M Span(U)eN My My where is a delay parameter satisfying 7 < t.
Output value: Each node specifies local outputs from its memory time i, that is, for all i [m]. we have x E M, and y! E EM,--
The definition of the above algorithm class follows the standard settings in the studies of decentralized optimization 8 28 44 48 (66. Compared with the algorithm classes defined by Kovalev al.
33.. we remove the requirement that all nodes must access their stochastic local gradients with the identical mini-batch size per iteration, so our algorithm class also contains the partial participated computation schemes.
The lower complexity bounds on the LIFO calls, the computation rounds, and the communication rounds are presented in the following three theorems.
Theorem 4.2. For the parameters L 2 L, L/p > 2, and < 0.003, there exists hard instances satisfying Assumptions 2.4 In order find e-suboptimal solution, the LIFO calls of any LIFO algorithm is lower bounded by 2(mm + min mnin(ma (mnL., /mml.. log(1 /e)).
Theorem 4.3. For the parameters T. 2 T,, T./p > 2, and < 0.003, there exists hard instances satisfying Assumptions 2.4 In order to find an e-suboptimal solution, the computation rounds of any LIFO algorithm lower bounded by 2(n + (L/H min(nL, /n/mLI/ /p) log(1/c)).
Theorem 4.4, For the parameters L, > L, > 2p > 0, and 2 2, n E N, there exists hard instance satisfying Assumptions 2.4 with A2 (W) E [0, cos(st///// /os)=
order to find an e-suboptimal solution, the communication rounds of any LIFO algorithm is lower bounded by 21
(2LLL he.L///lg(L/) (1/e)).
8

---

GIEG
NCSVRE OADSVI
MCSYRE
OADSVI
36D5VI
DIVERSE
DIVERSE
194
10-4
1--
(a) a9a
(b) w8a
(c) ijcnn1
(d) cod-rna
Figure I: Performance comparison with respect to LIFO calls across different datasets.
5911
BMENSE
99%
(a) a9a
(b) uSa
(c) ijcnn1
(d) cod-rna
Figure 2: Performance comparison with respect to computation rounds actoss different datasets.
194.
20-
1x-
Connir unon lundl
Conniiccooo mund
XLX
<
(a) a9a
(b) uSa
(c)
ijcnn1
(d) cod-rna
Figure 3: Performance comparison with respect to communication rounds across different datasets.
The above theorems indicate that the upper complexity bounds provided in Theorem 3.7 are optimal (up to logarithmic factor). Our lower bounds hold for the decentralized finite-sum minimax optimization under the general smoothness settings. Specifically, the results in Theorems 4.2 4.4 hold for all L and L. such that L L. contrast, the existing lower bounds (39 consider the local smoothness parameters L1 and L (see Section 2.1). and their analysis requires the additional condition VnLy Lt.
Numerical Experiments
In this section, numerical experiments are conducted to evaluate the performance of Algorithm 2 We consider the problem of robust regularized linear regression [22
27
39 50), which is formulated as
N
(x (a; + b.)² + 2 |x|
T2 |yl| 2
min max YER"
2N
where the weight the model, y is the adversarial noise, ((a,. b,) = the training dataset, and F1, are regularization parameters. We consider the undirected ring network with m 50 nodes and each node has n training samples. Therefore, the total number of samples N = mm. The mixing matrix with Metropolis-Hastings weights [80) is used for communication steps. The regularization parameters are set to be 71 = = 0.2. The numerical experiments are conducted on datasets a9a, w8a, ijcnni, and cod-rna, from the LIBSVM repository [14). We compare the proposed DIVERSE (Algorithm with the baseline methods including GT-EG [53]. MC-SVRE [46], and OADSVI [3 Algorithm The parameters of these algorithms are set according to the theoretical analysis the recommended settings by the authors 39 46 55
Specifically, the parameter b in the DIVERSE is set to be 128 and the fixed batch size for each node in OADSVI is set to be 3. The best performance step sizes from {0.1, 0.05, 0.01} are used, up to the algorithms and the datasets.
The experimental results are shown in Figures outperforms all the tested methods in terms LIFO calls, the computation rounds, and the communi- cation rounds, which validates our theoretical results. The deterministie method GT-EG (55 and the
It can be observed that the proposed DIVERSE

---

stochastic method MC-SVRE [ require much more communication rounds than other methods. This is because GT-EG does not include Chebyshev acceleration its communication protocol and MC-SVRE cannot benefit from the communication efficiency by the mini-batch sampling. Addition- ally, the LIFO complexity of DIVERSE significantly superior to all the baselines, since it the only one that uses stochastic mini-batch sizes, benefiting from partially participated computations.
6 Conclusion
This paper proposes variance-reduced optimistic gradient method with stochastic mini-batch sizes for decentralized convex-concave finite-sum minimax problem. We establish the linear convergence rate with global smoothness parameters dependency for the sonngly-covvex--ttonggyooooo which is shaper than existing results that only consider the local smoothness. Lower complexity bounds are constructed to show the near optimality of our method. The efficiency of the proposed method is also validated through numerical experiments. For future direction, we would like to extend the ideas to solve the decentralized minimax problem with different constants of strong convexity We can also study the global smoothness
objective,
and strong concavity [26 36 42
76 84
dependency in decentralized nonconvex minimax optimization 17 23
93
Acknowledgments and Disclosure of Funding
Luo is supported by the Major Key Project of Pengcheng Laboratory (No. PCL.2024006), National Natural Science Foundation of China (No. 12571557), National Natural Science Foundation of China (No. 62206058), and Shanghai Basic Research Program (23JC1401000) Chen and Wei were partially supported by the National Key R&D Program of China (No. 2023YTA1009300).
References
[1] Alekh Agarwal and Leon Bottou. A lower bound for the optimization of finite sums. In International conference on machine learning, pages 78-86, 2015.
[2] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In Conference on Learning Theory, pages 778-816, 2022.
[3] Ahmet Alacaoglu, Yura Malitsky, and Volkan Cevher. Forwaadd-reflectee-bakkwe method with variance reduction. Computational Optimization and Applications, 80(2):321-366, 2021.
[4] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):151,, 2018.
[5] Mario Arioli and Jennifer Scott. Chebyshev acceleration of iterative refinement. Numerical Algorithms, 66(3):591-66) 2014.
[6] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. International Conference on Machine Learning, pages 214-223, 2017.
[7] Tao Bai, Jinqi Luo, Jun Zhao, Bihan Wen, and Qian Wang. Recent advances in adversarial training for adversarial robustness. In International Joint Conference on Artificial Intelligence, pages 4312 2021.
[8] Yunyan Bai, Yuxing Liu, and Luo Luo. On the complexity of finite-sum smooth optimization under the Polyak-Lojasiewicc condition. In International Conference on Machine Learning, pages 2392-2417, 2024.
[9] Tamer Başar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
[10] Aharon Ben-Tal, Arkadi Nemirovski, and Laurent El Ghaoui. Robust optimization. Princeton university press, 2009.
[11] Michel Benarm and Morris W. Hirsch. Mixed equilibria and dynamical systems arising from fictitious play in perturbed games. Games and Economic Behavior, 291-2)336-7 1999.
10

---

[12] Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Dis- tributed saddle-point problems under data similarity. In Advances in Neural Information Processing Systems, pages 8172-8184, 2021.
[13] Aleksandr Beznosikov, Pavel Dvurechenski,, Anastasiia Koloskova, Valentin Samokhin, Se- bastian U. Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. In Advances Neural Information Processing Systems, pages 38116- 38133, 2022.
[14] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions Intelligent Systems and Technology. 2(3):1-27, 2011.
[15] Patrick Chareka, Ottilia Chareka, and Sarah Kennendy. Locally sub-Gaussian random variable and the strong law of large numbers. Atlantic Electronic Journal of Mathematics, 1(1):75-81, 2006.
[16] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien, Reducing noise in GAN training with variance reduced extragradient. In Advances in Neural Information Processing Systems, pages 391-401, 2019.
[17] Lesi Chen, Haishan Ye, and Luo Luo. An efficient stochastic algorithm for decentralized minimax optimization. In International Conference Artificial Intelligence and Statistics, pages 1990-1998, 2024.
manconvee-strongly--oomm
[18] Christoph Dann, Gerhard Neumann, and Jan Peters. Policy evaluation with temporal differences: survey and comparison. Journal of Machine Learning Research, 15(1):809-85) 883, 2014.
[19] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference on Learning Representations, 2018.
[20] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pages 1646-1654, 2014.
[21] Ding-Zhu Du and Panos M. Pardalos. Minimax and applications, volume 4. Springer Science & Business Media, 1995.
[22] John C. Duchi, Alekh Agarwal, and Martin J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3):592-606, 2011.
[23] Hongchang Gao. Decentralized stochastic gradient descent ascent for finite-sum minimax problems. arXiv preprint arXiv:2212.02722 2022.
[24] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien.
A variational inequality perspective on generative adversarial networks. In International Conference on Learning Representations, 2019.
[25] Ian Goodfellow, Jean Pouget-Abadie Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances Neural Information Processing Systems, pages 2672-2680, 2014.
[26] Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. Journal of Machine Learning Research, 2562):1-86, 2024.
[27] Hadrien Hendrikx, Lin Xiao, Sebastien Bubeck, Francis Bach, and I Laurent Massoulie. Statisti- cally preconditioned accelerated gradient method for distributed optimization. International conference on machine learning, pages 4203 2207-4227,2 2020.
(28] Hadrien Hendrikx, Francis Bach, and Laurent Massoulie. An optimal algorithm for decentralized finite-sune optimization. SIAM Journal on Optimization, 31(4):2753 -2153,,-78,.-- 2021.
11

---

[29] Zhe Hong, Kwan Deok Bae, and Do Sang Kim. Minimax programming as tool for studying robust multi-objective optimization problems. Aunals of Operations Research, 31992):5589 1606, 2022.
[30] Feihu Huang and Songcan Chen. Near-optimal decentralized momentum method for nonconvex- PL minimax problems. arXiv preprini arXiv:2304. 10902, 2023.
[31] Dušan Jakovetić, Joao Xavier, and José M.F. Moura. Fast distributed gradient methods. IEEE Transactions on Automatic Control, 59(5): 2014.
[32] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315-323, 2013.
[33] Anastasia Koloskova, Tao Lin, and Sebastian U. Stich. An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, pages 1 11435, 2021.
[34] Galina M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[35] Georgios Kotsalis, Guanghui Lan, and Tianjiao Li. Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation. SIAM Journal on Optimization, 32(3):2041- 2073, 2022.
[36] Dmitry Kovalev and Alexander Gasnikov. The first optimal algorithm for smooth and strongly- convex-strongly-connayy minimax optimization. In Advances in Neural Information Processing Systems, pages 14691-14703, 2022.
[37] Dmitry Kovalev, Samuel Horváth, and Peter Richtárik, Don't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Algorithmic Learning Theory, pages 451 1677 2020.
[38] Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. In Advances in Neural Information Processing Systems, pages 18342-188 18352, 2020.
[39] Dmitry Kovalev, Aleksandr Beznosikov, Abdurakhmon Sadiev, Michael Persiianov, Peter Richtárik, and Alexander Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. In Advances in Neural Information Processing Systems, pages 31073-31088, 2022.
[40] Boyue Li, Zhize Li, and Yuejie Chi. DESTRESS: Computation-optimal and communication- efficient decentralized nonconvex finite-sum optimization. SIAM Journal on Mathematics of Data Science, 403):1031-1055 2022.
[41] Huan Li, Zhouchen Lin, and Yongchun Fang. Variance reduced EXTRA and DIGing and their optimal acceleration for strongly convex decentralized optimization. Journal of Machine Learning Research, 23(222):1-41, 2022.
[42] Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pages 2738 2779, 2020.
[43] Liu and A. Stephen Morse. Accelerated linear iterations for distributed averaging. Annual Reviews in Control, 35(2):160-163 2011.
[44] Yuxing Liu, Lesi Chen, and Luo Luo. Decentralized convex finite-sum optimization with better dependence on condition numbers. In International Conference on Machine Learning, pages 30807-30841, 2024.
[45] Johan Löfberg. Minimax approaches to robust model predictive control, volume 812. Linköping University Electronic Press, 2003.
[46] Luo Luo and Haishan Ye. Decentralized stochastic variance reduced extragradient method. arXiv preprint arXiv:2202.00509, 2022.
12

---

[47] Luo Luo, Guangzeng Xie, Tong Zhang, and Zhihua Zhang. Near optimal stochastic al- gorithms for finite-sum unbalanced convex convex-concayy concave minimax optimization. arXiv preprint arXiv:2106.0176/ 2021.
[48] Luo Luo, Yunyan Bai, Lesi Chen, Yuxing Liu, and Haishan Ye. On the complexity of decentral- ized finite-sum nonconvex optimization. arXiv preprint WxXiv:2210.39931 2022.
[49] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
[50] Ulysse Marteau-Ferey Francis Bach, and Alessandro Rudi. Globally convergent newton meth- ods for ill-conditioned generalized self-concordant losses. In Advances in Neural Information Processing Systems, pages 7634-7644, 2019.
[51] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles adversarial regularized learning. In Smposium on Discrete Algorithms, pages 2703-2717, 2018.
[52] Dmitry Metelev, Savelii Chezhegov, Alexander Rogozin, Aleksandr Beznosikov, Alexander Sholokhov, Alexander Gasnikov, and Dmitry Kovalev. Decentralized finite-sum optimization over time-varying networks. arXiv preprint arXiv:2402.02444 2024.
[53] Dmitry Metelev, Alexander Rogozin, Alexander Gasnikov, and Dmitry Kovalev. Decentral- ized saddle-poin problems with different constants of strong convexity and strong concavity. Computational Management Science, 21(5):1-41, 2024.
[54) Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra estra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference Artificial Intelligence and Statistics, pages 1497-1507, 2020.
[55] Soham Mukherjee and Mrityunjoy Chakraborty. A decentralized algorithm for large scale min-max problems. In IEEE Conference on Decision and Control, pages 2967-2972, 2020.
[56] Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2633, 2017.
[57] Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoff's in decentralized optimization. Proceedings of the IEEE, 106(5):953-976. 2018.
[58] Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
[59] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 185(1):1-35, 2021.
[60] Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle- point problems. In Advances in Neural Information Processing Systems, pages 1408-1416, 2016.
[61] Leonid Denisovich Popov. A modification of the arrow-hurwitz method of search for saddle points. Mat. Zamerki, 28(5):777-784, 1980.
[62] Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. Mathematical Programming, 187:409-457, 2021.
[63] Guannan Qu and Na Li. Harnessing smoothness to accelerate distributed optimization. IEEE Trunsactions on Control of Network Systems, 5(3): 2017.
[64] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, pages 3066-3074, 2013.
[65] Alexander Rogozin, Aleksandr Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized saddle point problems via non-Fuelidean mirror prox. Optimization Methods and Software, pages 1-26, 2024.
13

---

[66] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization networks. In international conference on machine learning, pages 3027-3036, 2017.
[67] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112. 2017
[68] Ali Shafahi, Mahyar Najibi, Zheng Xu, John Dickerson, Larry S. Davis, and Tom Goldstein. Universal adversarial training. In AAAI Conference on Artificial Intelligence, pages 5636-5643, 2020.
[69] Zhuoqing Song, Lei Shi, Shi Pu, and Ming Yan. Optimal gradient tracking for decentralized optimization. Mathematical Programming, 207(1):1-53, 2024.
[70] Vladislav Tominin, Yaroslav Tominin, Ekaterina Borodich, Dmitry Kovalev, Alexander Gas- nikov, and Pavel Dvurechensky. On accelerated methods for saddle-point problems with composite structure, arXiv preprint 0rXiv:2103.09344 2021.
[71] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint 1xxx:/705.00204 2017.
[72] Ioannis Tsaknakis, Mingyi Hong, and Sijia Liu. Decentralized min-max optimization: Formula- tions, algorithms and applications network poisoning attack. In International Conference on Acoustics, Speech and Signal Processing, pages 5755-5759 2020.
[73] Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):237-255 1995.
[74] Konstantinos I. Tsianos and Michael G. Rabbat. Distributed strongly convex optimization. In Allerton Conference on Communicution, Control, and Computing, pages 593-600, 2012.
[75] John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffferee learning with function approximation. In Advances in neural information processing systems, pages 1075-1081, 1996.
[76] Yuanhao Wang and Jian Li. Improved algorithms for convex-concave minimax optimization. In Advances in Neural Information Processing Systems, pages 4800 1100048110 4810, 2020.
[77] Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2020.
[78] Blake E. Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems, pages 3639-3647, 2016.
[79] Wenhan Xian, Feihu Huang, Yanfu Zhang, and Heng Huang. A faster decentralized algorithm for nonconvex minimax problems. In Advances in Neural Information Processing Systems, pages 25865-25877, 2021.
[80] Lin Xiao, Stephen Boyd, and Sanjay Lall. A scheme for robust distributed sensor fusion based on average consensus. In International Symposium on Information Processing in Sensor Networks, pages 63-70, 2005.
[81] Ran Xin, Usman A. Khan, and Soummya Kar. Variance-reduced decentralized stochastic optimization with accelerated convergence. IEEE Transactions on Signal Processing, 68: 2255-6271, 2020.
[82] Ran Xin, Shi Pu, Angelia Nedić, and Usman A. Khan. A general framework for decentralized optimization with first-order methods. Proceedings of the IEEE, (0:(11):1869-1) 1889, 2020.
[83] Yangyang Xu. Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems. SIAM Journal on Optimization, 34(1):1006-1044 2024.
[84] Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A catalyst framework for minimax optimization. In Advances in Neural Information Processing Systems, pages 5667-5678, 2020.
14

---

[85] Haishan Ye and Xiangyu Chang. Snap-shot decentralized stochastic gradient tracking methods. arXiv preprint arXiv:2212.05273, 2022.
[86] Haishan Ye, Wei Xiong, and Tong Zhang. PMGT-VR: A decentralized moximall-gradien algorithmic framework with variance reduction. arXiv preprint arXiv:2012. 2020.
[87] Haishan Ye, Luo Luo, Ziang Zhou, and Tong Zhang. Multi-consensus decentralized accelerated gradient descent. Journal of Machine Learning Research, 24(306):1-50, 2023.
(88] Kun Yuan, Xinmeng Huang, Yiming Chen, Xiaohan Zhang, Yingya Zhang. and Pan Pan. Revis- iting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. In Advances in Neural Information Processing Systems, pages 36382-36395, 2022.
[89] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1):901-933 2022.
[90] Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number independent access of full gradients. In Advances in Neural Information Processing Systems, pages 980-988, 2013.
[91] Xin Zhang, Zhuqing Liu, Jia Liu, Zhengyuan Zhu, and Songtao Lu. Taming communication and sample complexities in decentralized policy evaluation for cooperative multi-agent reinforce- ment learning. In Advances in Neural Information Processing Systems, pages 18825-18838, 2021.
[92] Xuan Zhang, Gabriel Mancino-BE Ball, Necdet Serhat Aybat, and Yangyang Xu. Jointly improving the sample and communication complexities in decentralized stochastic minimax optimization. In AAAI Conference on Artificial Intelligence, pages 10865-20873 2024.
[93] Yihan Zhang, Wenhao Jiang, Feng Zheng, Chiu C. Tan, Xinghua Shi, and Hongchang Gao. Can decentralized stochastic minimax optimization algorithms converge linearly for finite-sum nonconvex-nonconeee problems? arXiv preprint arXiv:2304. 1778, 2023.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main contributions of this paper summarized in the final paragraph of the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification: All assumptions are stated in Section 2 and complete proofs of the theorems are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The algorithm is elaborated in Section 3 and the details required for reproduc- ing the experiments, including parameter settings, are provided in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
17

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is included in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ mripss.cc/ubllic/gui.ee CoodeSumeeieeeeee ssi iessonPolll molyicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental details are elaborated in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The effect of the settings such as random seed is minor since the datasets and initialization are fixed, and only the random gradients are affected, with little impact on the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
18

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: requires few computational resources to run the numerical experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper focuses on optimization theory, so the work does not have direct societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
19

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The datasets used in the numerical experiments are properly cited in Section 5
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
20

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
21

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy buttps://neure wwwparripp..ccoooeeeeeeeeeea /t/CCooffeeencss//2222 for what should or should be described.
22

---

Appendix
In Appendix A we construct examples that smoothness parameters are significantly different. In Appendix B we present some basic results, including the non-negativity of the Lyapunov functions and several useful lemmas. The proofs of the lemmas and Theorem
3.7 in Section are provided in
Appendix C
and Appendix D contains the proofs of Theorems 4.2 4.3
and 4.4 in Section
A Examples of Differences among Smoothness Parameters
In this section, we provide two specific examples show that the smoothness parameters can differ significantly. We first construct instance where the local smoothness parameters Lt. Lt, and Lmax are a factor of O vm) larger than the global parameters L and L.
Example A. For simplicity, assume dz = dy and n 1. Define the function
y) vT.2 )²)xx² T y + クリー |x| lyll
(4)
and denote its gradient operator by BA (z). It can be verified that for any z, E Rdd,
|gn (z) - (z()))
|Vxh(x, Vx (xh(x', IV - Vyh(x','')) y'1l
-II -12) - y) p(x x')| ILV x') ply y')l²
L? (||x - x'12 + lly - y'
= 12112-22 =2'11,
indicating that h(x,y) y) is L-smooth, and the constant tight. We now define the local objective functions as
if 1, (1 + m)),(x,)),
fx = (1 /x),, if 2, otherwise.
h(x,y),
Then the global objective f(x, y) m Em [i y) h(x. remains L-smooth. The global
mean-squared smoothness parameter L can be computed as
(z) g00-gg((()) 22 ((1 + vm)² + (1 - vm)² + - 2) [1g (z) (x)22))
=3L 2'11..
Meanwhile, the local smoothness parameters Lt, Lt, and Lmax are all determined by f1, since for any E [m). gg(()) - g;(2')11 < ||g - gz
= (1 + lm) (z) (x(2))12
(1 + Vm)) 2 L2 2-2'''
Thus, we conclude that L = V3L and L1 L, Lmax (1 + /m)L.
Based on Example A.I and Table (ignoring all log term), DIVERSE achieves the LIFO calls complexity of O(m + mL/p). computation rounds complexity of Ö(L/μ), and communication complexity of Ó L/))) In contrast, the existing state-of-the-art method OADSVI requires the LIFO calls complexity of Ö(m + 3/22 L/ computation rounds complexity ((vmL/p), and communication complexity of ŌlvmxL//p)
If the heterogeneity among nodes further increases, the local smoothness parameters may exceed @(ym) relative to J., as demonstrated by the following example. (In fact, the local smoothness parameters can be arbitrarily large relative to L.)
23

---

Example A.2. Using the same definition of h(x. y) as in equation ④ define the local functions as
(1 + 11+m))h(x,,, if 1,
yxx,y))
(1 (1-m (xx,))),
if 2, otherwise.
y(
Then the global objective remains f(x, y) = hxx y). which L-smooth. Following the calculation as in Example A.1 it is straightforward to verify that L = vI L and L = L = Lmax =
+ -
For Example A.2 DIVERSE achieves the LIFO calls complexity of Õ(m + mL/p), p), computa-
tion rounds complexity of ((L//),, and communication complexity of ((EL//)) while existing methods require the LIFO calls complexity of ( + m2 L/),, computation rounds complexity of L/p), and communication complexity of Om2 VxT./u)
B
Some Basic Results
In this section, we establish the non-negenn non-negatyy of the Lyapunov functions, and then present some useful lemmas.
B.1
The Non-Negativity of Lyapunov Functions
In this section, we prove that the defined Lyapunov functions + and are non-negative when n S 1/(4.). Recalling the definition of Φh we have
1 + 17
3/
- -
1
||z 1²12
12 +
1 2* 1
r
811
3 + np | - zz" z²11
+ 2g((z 1) g(z") ) z² x²) +
pn
1
1z
1| 2 (g(z b )) g(z ) z σ²)
1 2t -112
2n
811
z 112
(g(z))
g(z 8-1 112 8n 211 td - z 1|
+
112
2m
8n
87)
1
x ||
/ 211 3n112112* 1²11²
1
z 113
2n
81
817
8.2
||
1
27
2 0,
where the third inequality holds by Assumption 2.2 and the last inequality is based on 17 1/LL.).
Similarly, for & we have
3p
11 - =z'12 + 4x)
112 111 + 2(g(z* - g((z), 2d -z")
2
1
b z" 1 + 2g(2==- - -g((z)) z² -z') + 1
1z 2112
2m
8n7
IV
0.
B.2 Useful Lemmas
In this section, present basic lemmas that will be used in the subsequent proofs. Firstly, based on Assumption [..] we can derive the following lemma.
Lemma B.1. Under Assumption
2.3
we have
Bi. (z) Bi, (z')22 < mn - 2/112,
(5)
24

---

and
S mmf2l1z [g.(()) - =
- z'11²
for all z' IR i e [m]) and j E [n].
Proof. For equation G holds because
B 2) Bi, (z')l1
gi,( gi.(zz)] S mnL 2'1²,
where the last inequality is based on Assumption
2.3 Equation 66 is due the fact that
(g) {z(2)11
|
Σ (i. (z) Bi, (z')) ||
gig (2) Bi.s
71
j=1
1 m
ΣΣ
gi. (z) gi, (z))l
71 j=1
< mm..
z. 1
This completes the proof.
The following proposition 88
characterizes the convergence of Algorithm [
Proposition B.2 (Ye et al. 87 Proposition 1]). Under Assumption 2.4 Algorithm hoolds that
1 1 n
m
and
|UR 17 S 01 (1 - 02v )2 (W) R 1
1 lū
d2
where ú = -1 .1 V44, and C9 1 1/v2.
The following lemma shows crucial property of gradient tracking. Lemma B.3. For Algorithm ? it holds that
8
Proof. From Proposition
B.2 combined with the update of S in Algorithm 2 (Line 8), we have
S
m 1 FastMix(sk- A -Ak k-1 W.
8
Note that = 50_ By induction, is straightforward to verify that 5 holds for & 2 0.
C The Proofs for Section 3
In this section, we prove the lemmas and Theorem 3.7 Section Specifically, it is organized as
follows:
Appendix C.T we prove Lemma which provides an upper bound for the Lyapunov function 4
25

---

In Appendix 2
we provide the proof of Lemma 3.2 which bounds the consensus errors of
Z and V.
Appendix
Lemma
3.3 is established, bounding the consensus error S.
Appendix
we prove Lemma 3.5 by applying Lemmas and induction.
In Appendix
Lemma 3.6 is established using a similar approach to Lemma 3.5
Theorem 3.7 is proved in Appendix C.6
C.1 The Proof of Lemma 3.1
3.1
follows from Line 9 of Algorithm 2 and equation 7 that
*k+1_
1 =
171
FastMix ((1 3) + BV - n W.
(1 B)z + B8 -n/*
(1 B)z + Bip -n0t
which implies
z k+| zº¹ = 3 (v* - -z²) - -70*.
2
We have
|| ++1 2² + z - 2²1
z"
1 z" 2 2(2 2" 2 z" + | - 1/1122
2 z" 1 2(z 2² 2 1+1 z
|z*+| 1012
2 z 1 + 23 2 ++1 z
2 5t g(2"),
2 )
1 4 11112
1 2 + z", 2 k+1
2²) (z
22 2. z²)
2n g(z"), 2 x
++1 zz 1/2
-112 z" 112 0 (1z || 2112 8 | z² 1|
1 b+1 z (1)
+ 3 (I 2² - 1|z z" 1
k+] - z 11²)
|| 2 (5 g(z") 2 k+1 z²)
(1 - 1) 12 B||z v4122 + 81| 1|2 -(1 (1-1))|1bb++ 2//112
(5 g(2²),22 - =²)).
(8)
Then we bound the term E [8 g(z"), 2 z²) Note that
E 5* g(z"), z k+1 2²)] E ((5 Ree (5*1, /² z + E 1(5t E [Eg [8+] g(("), z z²)]
Eet [ g. 2t)]
(9)
where Egx denotes the expectation taken over random variables (et, m.n 1ij==1
For the first term of equation
we have
E
6
Eet
6*1 *.
z
z²)]
=E
Eg (65t - (= zz"]] 0.
(10)
For the second term of equation an upper bound for E (8+ Ega 1²11 zt z 2b+1)] By Young's inequality, we have
(9) we aim obtain its lower bound, which is equivalent to finding
1 || - 1112 (11)
E (5th 10
j zh - zbt1g| < n/ |1 Eg [6*112] +
4n
26

---

Recalling the definition that
8 1
Sti
(B Bi)(v+ a(gi)(E)) 8i.(2, (1))
gi
m72
mi
we have
m
ck
Ege
[115
Egt
[5*]
(Bi)(())
Bio (v
mn
g
(12)
+ gx
Si.j -1
(Bi)(zf) (2
q
By Yong's inequality, the first term of equation
can be bounded by
1
Siuj
(Bt) (v(-1))
-
mm
q
Si.j
-2Ex
-1 (gi)(z,)) (zn)
q
1
(Bi)(v - Bi. (ib(((11)))
m
q
m
ck
-1
(Bis(Et) Bit(((-11)
mn
q
ck Si.j
6Egt
q -1
(g.) B(t(
mn
ck Si.j
+ 6E.z
1
(B:.)(V - (()((b-1))
(13)
mn
q
+ 6EE.*
Sig
(2")
Bi. Bis (p
mn
For the first term of equation (33. we have
ck
Egs
-1
(Bis(2)) Bin
q
i=1 j=1
m
n
ạ
(Big(2
Big (2*)))1
m m 2
j=1
m
(g., (z B1, ||
m m2n²q
1= ==1
I
1 21
miy
1=1 1=1
nī²
| 1z
b
27

---

where the second inequality holds by equation ( Similarly, it holds that
Eee
-1)
(Bi)(v)-1)
((-())
nL?
b | -16-1112
q
For the third term of equation
13
170
13
ck
Exh
Siy
-1 1 (Bi)(Et) Bin (vb
mm
q
j=1
q [[B,) Bi, (x ||
m²n²
q
i=1
m2n2q
i=1 j=1
L
|
mng
T,2
11
b
where the second inequality holds by Assumption 2.3
Thus, an upper bound for equation
13 is given by
5ig -1)
2k
mn
1=1
6n
6nI²
|z
1z
* |1
1
+
1|
11-
b
b
b
Similarly, the second term equation
12)
can be bounded by
m
n
ck Si.j
27
Ext
(gr,
(z
1))
mn
q
j=1
6nl2
6nI²
2a²
IZ
11
1z=-1 1z
-112 +
1|z
- 1/1 112
b
b
anL
2nL
6L2a²
|z
1
+
||
1
1112
b
Consequently, an upper bound for equation
11 is
E 15th Ege 10*1,2" z z 2
< 1/ [|15 - Exx (0'111
+ dr7
[||
x+ 11
b + GmmLaaa
G
E
[[|1 |
1z |2
+ b E [[[ 11]-
T.2
E [|1Z
k-
1z
x
1|2
E || 34-11121
T,2
E
z
z
12]
+
E
[||
- 2
(14)
4n
28

---

For the third term of equation 9 we have
E
(Eex 10-1
g(z")
=h+1__
zz)
}
1
1
E
(z +
gi
gi 2 111
-g(")) ) kk+1 zz¹
m i=1
m
E
1
Bi (z + a
m Σ g: (2
1
m Σ
m
gi x 1111 1)
g((²) a (B(2*) - -(( zt-1 2²
+
[g
a (g(Z))
g(z
1) - g(z )
22 {*
m
1 m
1 m
E
g: (2f)
Σ 8
Σ
gc (2(-11
- -8(2") - a (g(x*) g(z²-1) 1))
M E ||
||]] + + (g((z))
a (g(z")
g(z () g((")) zk+1 z1)
4
m
3 BB
m
E
g: (z+) 8(24))
Bi(2t) -((**)
m
1
//
3
E
Σ
m
(i(2) 1 g(((~1) 1
1 E || 1121
/
E (g((*) a (g(z*) g(z² 1) g(z"), x }
(15)
where the inequalities hold by Young's 's inequality.
Note that
2
1 m = m
1 m
- -
- (zz)))
m
Bi, - Bi , )21))
mn
j=1
m n
mnI. || 2/11²
mn
j=1
= nI
|
1z & 2
where the first inequality is based on the fact follows similarly; the third inequality is based on equation
1 Σm a.
-
< Σ m
1i=1
||a;||: the second inequality
and
(g(Z*) + a (g(z") - g(z² 1) 8(z"), z++1 2²)
(B(2") (( 2, - 2²) - a (g(2 - g((z") z - xt)
a (B(2* g(z"),²" 2t =z) + (g(2)+)) -((z")) ") z² 2²)
2 (B(2*) g(z ) z z²) 2 Analll((z* g(zt-1) + 1
1z zz 2²)
Anja
- (B(2 g(8)), x²) + #1|z/t1
k+1 z 101
2 (g(Z*) - -g(z+11) , z²) - 2naa 2 L 1'|l"* -112
1z
x+1
zz 1²1
8n
- (g(2 g(z²), - z²) + ul| - z 112
where the first inequality holds due to Young's inequality and Assumption strong monotonicity), while the second inequality follows from Assumption 2.2
2. (equivalently, the
The lower bound of
29

---

equation 15 can be further expressed as
(I 18-1 - g(z") ) k =n)
3nd2
1 (1 + a² DIE [lz - 1 anLaa²
E [[|Za=1 - 12 113]
+ +B (g((e) g(z"+1) ) 1, -z")| -2naa² i L |||E - [13]
1
E
| - =11
8n
3 EE [| x z 2=
-a [[g(z
g 20t) zz - =2"}]
(16)
Combining the results of equations 8 E
14). and (16). we obtain the upper bound of
||| x =1];
E |1 1
(1 B) [||Z* - [ SEE [| |-] + SE [| zz [|]
(1 - B [||z/t] - 11] - 2n [65t - g(z"), zk+1 x²)}
S (1 B)T [|| - -=] - ST [||2
- --1133 + HE [[|v - 2 112]
(1 - B [| + 2
E
-||zht- - [3]
12 + a²)
121/2nL²
E [||Z*
12$1
E [|
1 15 [13]
b
12n2nLaaa
12t7 I2
E [|/ ||| 1z 113] +
EE [||z 11
12n 2 L
E ||| - 1 || + GnnI²
(1 + a IE [|| - 1s |1]
b
6nnl'a²
a²
|||- 1s x ||3] - 21ylE (g(2*)
g(z 2, - -2") 2n>1
10
+ 2nalE
(((( - -g(zz)) 2² 2 + 4n a² 2 || * 11
1B [|ztt] z² [7] 3 un [||2/t2 zz 11
Rearranging the above equations yields
_ +
3
E [|
113] + EE [||E - [²] +
1
B
E
[| || - -1]
1
2
4n
"
21E
(g((2)) g(z 2 21>}
1
E |||a* - x² =01] + -E [||v - 2 11 +
12n
E
[||a* - [12 ||2]
1
b
12 1,2
(17)
+ +4aa I,2 E [||=~ -
[| + 2 [(8( 1 g(zz), ) z² 2²
b
12qnI?
+ 6nI?
||| 1z * ||3] + 12mnL² E [| 1 1 [|3]
(1 + 1
1
12mmL2a²
6nI'a?
E
[||Z
1|2
b
P
According to the update rule (Line 10) in Algorithm 2 we have
B + 7T11 E [[|a+t]
3 + mp
E
[|
z² [1 (1 1 p))
+ nu
E [l|v 2t (18)
pn
r
pd
30

---

By adding equation 18 to both sides of equation 17
and rearranging the terms, we obtain
- 1j
3
e "1
+
2"
E
[| 1 z" 1| + E
||z
+
4nj
E
|| 1 - 1011
21E [(8(2*) - g(z*+1)) 11 20} +
+
+HEE
[[] - x 211
pr
1 + 14
12
E [||t - 2²1 +
[||z* 11
17
b
12n 1222
+ 4nja212 L² E [112 11
(19)
b
- B(2²) ), - > + (1
3 + 1111
2xB
(g((a-1)
E. [[| =='1]]]
B + mp
po
12qmI?
6nI?
12 I.2
(1 + y² || -12" 12 +
IE || 1100--118-111 163
11
12
6nI²ar
E
12
113
b
Based on the choice of parameters, it follows that
1 3
12nL²
a9
24
7
7
1)
1
8 z
12.
and
+ Ana
212
407
8n¹
81
Thus, equation (19) implies that
(
3
8
1
E ||z k+ z²
12|
+
_ [|| |+
[1]
+
E [|| =
81]
B + np
+ 21E (g(z") g((++1), zk+ 1,
z²>} +
E [||
=1"113]
pm
<11-11) - 4 () + 3
13 E [|
17 2
|||E* - 11 + a E
+
E
|||
z² 1
17
8m
+ 2a (gg (z--1) g(z*) ), z² -z")] + 1
mdd
8 + m7
E [||
z [1]]
+ m7
pd
12mmL2 + 11
6nl2
(1 a²) (B I 1
E |
18 112
E
V
Recalling
a = max
piju
C1 =
12mm + 1
6nI.²
(1 (1+a2),
4
B B+ +np mp
we thereby complete the proof of Lemma 3.1
C.2 The proof of Lemma 3.2
Based on the update rule for ++1 in Algorithm 2 we obtain
1 +1 12
= E |astMix ((1 (1= + BV - - W)
11 FastMix ((1 B)z²* + VV n W. [1a]
m
31

---

S [|(L
3)z* vV* S/S ((1- 3)z* B ns5*) |
5 33p 3 11z* - 1s 12 + 3p² || - 1 || + 3 I|Is
1=
(20)
where the first inequality follows from Proposition B.2 and the second inequality is due to Young's inequality.
For the consensus enror of Vk+1 we have
E
[|| 11
= pF PastMix (Z W, R)
1
11 FastMix (Z', W, R)
|"] + +11 p)l V
12]
m
- P [|1* 12 + (1 E) || - 1
where the inequality holds by Proposition B.2
C.3
The proof of Lemma 3.3
According to the update rule for Sk+1 in Algorithm
we have
|s
1|2
FastMix (St + A+1
& W)
1
11 FastMix (S* + Ah+1 - A W RR)
1
s 0² Sh + 1Akt k+1
11
(S*
A
k+1 $
m
1
2p² - 18 11
2p²1
8+1
- 11 A K-
m
S 22p 1 + 2p² 1 || 1+1
A
(21)
where the second incquality holds due to Young's ss inequality, and the last inequality follows from the fact that ||A
11 All S ||||| for any A E Rmxds
Next, we bound the term E A 4-1 & 13. follows that
[||
k+1
12]
m
E
|
8.¹ |
m7
E
gi
(v..)
gi (v(
+ Σ
1 12
((., - + + (2, (2--1) gig (z)(2)))
n j=l
q
n ck1 1
(g:
Bi, (v. + a (B - (2
< 5 Σ
E
gi (v.)
g. (v. >|| + 5 >
(B, ) [v,(
(22)
1m1
172
ck Si
5
E
Biy
[z
k+
71
q
i=1
j=1
k-1
+ ΣB
E
(i,)(,,)) - -z
1=1
1=1
k-
+ Σ E
Σ
(B))(2)) - -B:)) (1,
n
q
i=1
i=l
32

---

For the first term of equation 22 it holds that
E [[lg:( (v [v ][
mLL' v - v
(23)
- 3 [llv - *-]]]] + 3 [[lv* -1-
+ 3mL [[lv;- -
where the first inequality holds by equation (6) and the second inequality is due Young's inequality. For the other terms in equation
22 Note that
Si.j
Egt
(gi, ( Bis(v!)))
q
27
Si.l
(B
Bin (v.))
11
9
/=1
1
||s,, (z)
Bi (v
nq
1=1
mnL²
||z
k+1 -v
n2
-z= 1222 3mZn²L2
3m²n²L² b
||
1 2k12
l| - 101
where the first inequality is based on the fact that || Ei= a
< Ei= ||a/|? the second
inequality is based on equation (5): the last inequality holds by Young's inequality. Further, we obtain
E
(2, ( BL)(()))
3m n L
E
||
3mm²" L
E h+1 s41]]]
3m 3mm=n" n LL"
E
[|v +-1]]] (24)
Similarly, for the third term in equation
we have
E
(2)
k-1)
-g:)(z)))
3m3 n
L²
E
||
|
pP
3m 3m2nn La
|| |
zt
2?
|| x²11?
b
(25)
For the fourth term, it follows that
ト Sin
(2)) (v (1)--1)))
3m 2n?
||et 2 {(]²]]
n.2 |1e2
E
1p]
3m2
18
1 1p] (26)
b
b
For the fifth term, it holds that
E
(2,)( (2)
J=1
3mn 2 n² I a
3m 2 n² i² az
3m 3m 2nn
|| - 20|]]]
|| - zh 11]
||
(27)
33

---

Substituting the results of equations 23 obtain an upper bound for E
24
(25
226
and
27
into equation 22
we finally
||
1++1
as
E [|| k+1 A [12]
15mL'E |1IV*
+ 15m2 m L [lle 11] + 15m 2 [|| || - 11
E [[1Z 15,
15m=
12 []3]
E
[ - v ||a]
b
b
15m I??
15m2 o.2a²
E [| - 17
E
1
b
b
15m 2IILaa²
15m² n² a²Laa
E |||
1+| +
E [| 12 [|]]
b
1
15m n² I
E
||| 1/
E 1112 - 112
b
15m2"n2 b
E [| 10 11?] 15m²n2L'a
E || 12
b
15m= 2 (2202
[||c 113] + 15m22n2
E
EE [[|Z
1 113]
b
< 30m n [|V 1- + 15m 3 L'E E [||v* r² 13 + 30m "n2L3E [[ 11
+ +30m²,,² [| - 1| + 45m 2 n " [||2* 13]
+ 15m2 " || - 1 - || + 15m 3 nn² E |||| - - |2
+ 15m2,,22' [ -
-+11 |]] + 15m $ n22 L [||2 - 1|2
+ 15mm2n2 n2"Laa [|z* -2--1133
$ 30m2n' TT.2R [[V* - -1v*1|3] + 15m2 [||v 5² 11] + 200m?n22:33 [[V 1-4
+ n00m"nn2 3/²(1 - 3) [| 12 |1 +
33p [| 15*112]
+ +3p", ||s 1s 112
45m 45m i || 12
+ 15m²nn²La
[| 1 + 15m ' 2 [|| - bト1
+ +1mm
[| - + 15m 3 n2 1 [|
1
+ +15m"n ' [| - [[3]
< 120m²n2i '' [| V* - 1 |2] + 15m= 2 1 [| | - 1 + 30m 2n2 [l | - 1
+ 13 L E |||z - 1 + 15m nn [ at 2E || h- 1z 8 ||2]
+ 9, RR. [[|st - 1 + 15m 3n 2 2 || -
1 x+11
+ 15m=",20'"
- - + 15m "n2 L [|iz* - * - ||
+ 2, 2F [| - - 111
where the second inequality holds because 6, m, n 2 1 and a < 1; the third inequality follows from equation (0);: the last inequality is due to p < and 3 [0, 1].
Substituting the above results into equation 21 we have
E [[|S 1|2
<2p²E [||** - 15 + 2p ||| k+1 A
< 240m²r 2:40m?n2L2pp "n'''p²E [1] [+ - 12 + 30m 30m²Lm 2L² [1 - -1-1
34

---

60m2nn"2pp'B [[[V=] - 1v - + 2 [||Z 12
=30m2n²L²a pº ||| - 1z 11 + (180m²n2 + 2p² L [|IS* 15
40mm"n²L² ||| - - + 30m 3 a²' ||| - 1²1
-30m"n2 "0=n""=L'pp" p2E' [|iz--v* -1² + 30m n² L' p²E [|
- - - [2]]
< 22 p² E [| 11] + IE [|| 1s 113] - [|| 1|
+ [1] [ - 18 1|
|||] ) [180m2n 1,21; 2)p² E [|S 15
-60m²I.'p (E |||v* v" [| + E ||| x (
30m 2n² /²( E ||| ||
+ 1| 1 + B || 1 11
+ [| 2 - [
(28)
With the choice of parameters B = p. it holds that
sh B 1|2 xn-11 11 +
1z
21-
+
1 1/ 22
19
16n
17
Therefore.
1 1 112 + 1|z
1111
1| 2²112 1 16n + 3) Φ*
(29)
Combining the results of equations
28 and
29
we obtain
E [[istt 11]
I C2p² (F 1|z -1 1z-11]] E | 1% 111-1113
+R lIve
1
+E | 166-
+Cpp'r ||st 1s 15]1|] + Cap² (Tz [aatt]] + x
+ + (T(()+11))
where C2 = 270mm n I., C3 = 180m2 pn n EP?? + 2, C4 = =60(16 + m/ L., and -- -
C.4 The proof of Lemma 3.5
From the definition of p. it follows that
2= = -1=
< 14exp (-2(1- 12(1-1/VV) (-2
(w)R)) (30)
where the inequality holds by the fact that 1 - x x5 Therefore, when
2 + V2
3C3 12
R =
log
14
(W)
ā ā²
C,
8C (m² 12 --=l====''' -z" 12
Ig (z)) (2)
p
(1- a)a²* á 1-a ā
(1 - ā)ā
(31)
it holds that
a² d-āājā² ā 1-a
(1 ā)āT"
0² < min
3C,¹ C2, 36 C 9" p
8C17² (m2 L2 - z" 2 + Σ -=1
(g.(()) )|3)
(32)
35

---

We will use induction to prove that the following results hold for k 2 0:
*
1 ā
E 1z
12 12 1
x
4C1
E V - 1 || v 4C1
ā 0
k
100
(33)
1 ā k+1T00
E || 1s 1| v
Cn
where ā max {1
pm
pmp
2(3 + mpp)
For 0, since || |
12 IV 1 1 12 0, it is straightforward to verify that the first three
inequalities hold. Next, we verify that || 1/ also satisfies the inequality in 33 It holds that
|SS 15 = |aastMix
W. R)
11 T FastMix A W, R?
m
< 0²
11 A 1
m7
< 0² 91
p² Σ (z")
t=1
m
m
2p² Σ
gi (z²) gz(z') +2²² Σ
gi (2*)
< 2p2
L 1z
22 zz 1 + 2p²
gg (z)))
where the first inequality holds by Proposition B the second incquality follows from the fact that A|A 11 All ||A| for any A E 1g the third inequality is based on Young's inequality,
and the last inequality holds due to Assumption 2.3 From the upper bound of p² in equation
33). we have
ā 1 I 2n a
||S
For k 1, according to Lemma 3.1
km77
pmd
cp
< max
1
4
3 + TH
max
2(B + np)
From Lemmas 3.2 and
3.3
together with equation
we have
1 -
ā
E ||
1
<
3p²
[||
1 <
22000
4C1
[| 1v
PE [|
12
(1 D) [l
1 11] 0,
and
E |||s
- 15-119
< 2 ||S 13 + Cap² (E ( + E (00
1 ā
(1
< C3 3Ca
2 + C4
(ā 1)40
Cn2C
C6
< 1 1- á ā 2000
C,
36

---

Assume that the conclusion of equation have
33 holds for k S t. Then, for h = + 1, by Lemma 3.1 we
E
[1
x aE
[5'
+ +1
E
I' - 12
+E || 1z -1 11'-113 +
||
ā
x a v.-a'd
á'
+
á 1+1 p0
à'
+
4C1 ā $000
4C1
4C1
pm
pip
pm
max
max
B + qp
8
2(3 + mp))
3.immn
[m
max
pm
1
4
32
8(3 + mHp)
2 + mp)
max
pmp
min
3pm
3pm
max
μM
pmp
$
4
3 + 17
32
8(B + mp)
8
2(B + np)
++1
max
1
pmp
T
8
2(B + np)
(34)
where the second inequality is derived using the inductive hypothesis.
For E
|||
1z [1]] by Lemma 3.2 it holds that
E
Iz
1z
113 $ 3p²
E ||
1z
+
I'
1v 1 [ 1s'1(
1- ā
1-
1- ā 101
< 3pp
á
400
+
Φ0 + +
4C₁
4C₁
4n²Cr
ā
3
3
9
401
1 ā a²
20
4C1
where the second incquality holds by the inductive hypothesis, and the third inequality follows equation (32).
For E [| 1 1 note that
NNd
HId
1 1 1-p51-
S max
1
=
(35)
B + 7M
4
7H
By Lemma
3.2 obtain
E Z - -
S p 1
12
+ (1 p)
|
1
ā 11+
ā
S pp
00 + +(1 p)
a 10
40
40
Sp.
- à 1 1 ā
1+ Φ0 + +a
1 1- -
10
1
4C'
40¹
1 1- à
(1 ā + a)
40
a 22220
40
where the second inequality holds by the inductive hypothesis; the third incquality follows equa-
tion 32 and equation (35); the last equality is based the fact that 1 â +
For E [||
1 []]. by Lemma 3.3
follows that
E ||s
1|
S Cop² [ [||z -- 1 1 ||
12--1
|12] +
[|V'
1V
[[|
1
37

---

+ Csp²
|| - 17] + Cap² [E [1 + + [0] E (q(111)
1 1- ā a'
1 1-a a 20 + Csp² 3.a 1'-1000
$ Cap² 4.
+ Cap²
401
4n2C1
à²
1
á
1 ā a
(1 ()-
402-
o'
+
C3
40 + 361
334 ā -²=100
12n
4C
3C3
An2C1
1- ā 22.
Cn 01
where the second inequality follows from the inductive hypothesis and equation (34). while the third inequality holds due equation (32g.
This completes the proof for the case = + 1. The conclusion of Lemma 3.5 is established by induction.
C.5
The proof of Lemma 3.6
Under the parameter settings of Lemma
3.6 it follows from equation ( that
1 2²11² 112 1²1
1 x++ 2²11 - 2ny(8* g(zz)) g 2²)
Note that 8h Es 18%) by equation (1). we have
18t g(z") ) 2, 2²)
3nL²
(1 + az )²))| 12 3n
111-112 1
1
1
+ (g(z*) g(z ) x++1 -z") 2nja 22 -z"
11-
1 ++ 1/12
81)
og -((²") z* 2²) 3/ 2xt1 201
Therefore, holds that
++1 z² 2² S 1 z²112 ||z 1/122 12 + GrnI?
(1 +1 +2)) -1z*1
4
6ymL'a²
1
1s 11- (g(z)) g(zh+1)) 2, z²)
11
+ 2naa/(22 xxxx -g(zz), 2² -==) + 4n 2a² 2 L 12 11-
1
+
z +++ - 1²12 pn) lg/lttt1 - -1.
4
Rearranging the above equation, we obtain
1
3/4
3 +
+
1 k+
21112+
1 - =2 +2(g(z") - -g(z*+1) z zz)
17
2
4n
1
1z
z' z²112 + 4rja² 1,2 zk 1112 + 20x (g( - =g(z))) 2² - =z=)
1)
.n (1 + a²)l z 12 +
6ni2a²
1 1 x 11
Based on the parameter settings, we have
1 S (1 - um)
3u 2
3 a. 2na213 <
and
17
Anj
Thus, the following inequality holds:
{ + 3/ 2
3
1z ++1
2=1 +
x+1
2² + 2(g(z*) - g() x z²)
4n
38

---

(=+ 31
3
S (1 pm)
1|z z²1 + a
||
z²-111 + 20(g((z - z²)
2
4n
12nL²
(11 1/2 + +||2 1 11),
1
that is,
S Savk + 12nL² kptt1
(IIz* - -12 + 1 - 112
(36)
1
Next, we bound the consensus emrors. For |z 1z
++ || similar to equation 20
we have
1 112 + 2p² 15 1 11 2pº 1z -1
(37)
For ||St+1 +1 11, according to equation 21 we have
||
1s + 1|2 <
1
2p
S
15 + 2 A+ - A/1
Note that
|g:
- (1) (2)) - a ((()) (B))) -
- (3(2)-1)))
S 31g. (z ) - (.(2)) )| 30 -
30 (l (z 1]
< 6mI l|zzlzttt 1² + 3 | 2 11-111 2
S 18mL (|
k+1 1 + 18m L | z" 1| + 18mL 1 111
+ +9mL22112
x² 112 + 9m I. 9 z² 1|2 9m 1.2 2| -z*= 1
where the first and third inequalities hold due to Young's inequality, while the second inequality follows from equation 66)
The term
k+1
A 1|2 can be upper bounded by
A k++
112
m
(2 x+ a (g: - (z())) (g.(2)) a (g:(2)) (())
$ 18mI² |
1 18m I f1
1 18m 2 [ z 2²1 1/
+ +
1z 11= + 9m +m z
1z
1| + 9m 2 2 /ー 1|
18m1² (2p² 12
2p ||$ - 1s 12) + m 1 2| 1z
+ + - 1 2 1' 2" 1| + 9m 2 L22lz²* 111
18m
< 63m.T.1lzz - - +
9m + T.2 2
1
12 1 361j n.² S 15*
+ 18m² 1 | h++ - 1 + 9m 2 1-11
where the second inequality is based on equation 37 Recalling the definition of V it holds that 1/ zz 112
Thus, the consensus error ||
15 1 has the following bound:
| - 15*+1 < 2pp - 115 112 + 2p²1 A i+1 A 1112
< 126m f:2 (11Z) 1 + | - 11/))
(38)
+ (720 + 2) p²
- 15/1 + 72mm² T.m [? (1 +w²).
39

---

Similar to Lemma 3.5
we proceed to prove the conclusion of Lemma 3.6 using induction. Letting
2+ V2
3 (72ngmII +2)
207367'm²nI
4
R-
log 14 max
2/1 (W)
1
122 (1 (1-127) m7) ? 1
756n2mL.
96mm (m² [221220 =2² + Σ m
g z 112)
(1 (17 2
112 (1 un To
(39)
it holds that
1
11 (1 un
1 2
p² min
3 (72n + 2)
20736n n
(40)
(1- - un 2
n²² (1 -
To
7 96mm mm2 1 1|20 z" 1 + =
22 11
For h: = 0, we have
|SS 15 S S 1 S 2p²m 11 2p² Σ
m
||g 1
1²2
(1
To.
48yn2
2
For h = 1, we have
V s (1 - un) 1 (1- |ill Tp
2
IZ' 12 12 < 100 15 - 1221
(1- p87 ) wo
2
48n1.
and
|| -
< (72 13-1|3$(72100)
+ 2) p² - 1 + 72mm 2 T??p² p² (vp2 + To)
(1- m
42
< mL. mL² + 2) (72n72 + 2)
(1- k1)) yo
48mn
2 (1 pm 2
+ 72mm
24
207361""
122
(1
pm7
2
yo
48
2
Assume that
T 1 (1
jml) k
2
1 1 1|2 < 1²
(1
pM)
k+1
T
48n
2
|| - 158112 <
n12
(1
k+1
40
48
2
holds for all & < t. Then for k: = 1 + 1, we have
12n
r0 < (1 11--101 pnn) v² +
/ (1/Z²
12
1 11
S (u7) (1
wn
t
T +
12n.2
2
12211
(1
(
40
48nL²
= (1 (n) t+1
2
40

---

where the first inequality is based on equation (36 and the second inequality is due to the induction hypothesis.
For
1
it holds that
|z 12 1 11?
$
2p" | 1z k 1?2
+
-=s111
2
(1
1n
(1
++1
+ 2
(1
Mn 2
17
1
(1-
pM
yo
48nL2
2
48mm
I
2
[ul
t+2
48nL²
where the first incquality is based on equation 37 and the second inequality is due to the induction hypothesis and equation (40).
For |S
1s* 1|?. it holds that
||S - 1
126mL2p (II) -1= + 112)
+ (721)mm + +2) p²||st 15 + 72mm² 2 T.2p (1pht1 + v
< 126mL
(1-
2
2
2. n
(1
1101
756n m ?
48nL2
2
(721)mLL2 +2)
(1
2
1²²
(1
pm
yo
(721 + +2)
48mm T.2
2
2 (1 m9
72mm
2. (1
um77
4
2
2
422
(1- un ++
4
4.
where the first inequality is based on equation hypothesis and equation (40).
38 and the second inequality is due to the induction
Thus, the conclusion of Lemma 3.6
holds by induction.
C.6 The proof of Theorem 3.7
In this section, the upper bounds Theorem 3.7 are proved based on the linear convergence of the Lyapunov functions and the consensus errors established in Lemmas 3.5 and 3.6
Case I: L S VunL.
By Young's 's inequality, for any E [m.. it holds that
| z" 12 S 2||25 z 112 2||2K z" 1²1
According to Lemma
3.5 we have
1 k
1
K]
21
max {1
pm
pna
(1
3/4
B + T7
1|
z 2²11
8 2(3 mp)
2
pr)
and
E [|
xK12] [12] < [||Z k_ 1z ||2
1 1 à
<
+
4C1
< 3
2
max
{1
pm
2(B + mp) 1) K
pnp
8
41

---

where the last inequality holds by C1 2 3/(8)). Therefore, for any [m]]
{1 =(
2(3 nnu) 1 )
[1 2 zz 2-11²] =00=00(
pmi
Mi
E
-
8
By the fact that S "r the number of iterations for [1|2," z² 11 - is
B + pmn
= 0
log
-
pm
ppm
(
)
+ log
pm
log
(41)
LIFO Calls:
Under the parameter settings of Lemma 3.1 the expected LIFO calls have the upper
bound:
O (mn + (pmn + (1 -1-pp0 ()-)))
O (mn + (pmn + K)
T.
11
T.
{
T. {Er vmn)) 31) T.
log ()))
mn + mn max
L Vmn S
min
(42)
= -0((
((mo (mm+++ + mn
L
log
Computation Rounds: In each iteration, the number of computation rounds depends the node with the maximum computation rounds, that is, max4e[m] Σn=1 <h.- Therefore, we first bound E|max;e m)] Σ}=1 c.
Lemma C.1. Let Y, Σz=1 Eag, where Ety Y; Binomial q). holds that
Bernoullig) (q) are i.i.d. random variables, so that
max Y; kE(m
S 2mg + log m.
Proof. Firstly, show that Y, is locally Gaussaan 15] generating function of Y, satisfies
For all [-1,1], 1], the moment
e M
= E
c Ei Ess
= ((1 q) + get)
((1 g) + q(1 L 17))
= (1 + qt + q12)"
S nqg+n
where the first inequality holds due to ex < + x + x2, x E [-1, 1], and the second inequality follows + ea.
Then we have
exp
L max Y FE[m]
) < E
exp
t max Y v.)
)] max eo [iE(m]
m
E
ngg
iE(m)
where the first inequality is based on Jensen's 's inequality.
Letting and taking the logarithm of the inequality, we have
I
max Y
< 2ng + log m.
[E(m)
This completes the proof.
42

---

We now derive the upper bound for the expected computation rounds:
n + pn + (1 - (1-p)E
max im(m
ck
Si.j
K
j=1
(n + (pm + 2ng + log m) K)
b
pm
+
+
log m
K
m
(43)
L
1
L
}
L
n +
n
max
L
Vmn
+
m
min
{ mn
+ log m
log
Th
L
I.
n
log
m
log
L
L
log
m μ
J
where the first step follows from Lemma C.1 and 1-p S 1, the second step from q b/mn, and the third step from the choice parameters p and
Communication Rounds: Based on the value of R in equation 31
we have
R Ō
(vx))
Ō
X2 (w)
Therefore, the communication rounds can be upper bounded by
VXL
)
=R= Ō Ô
log
(44)
Case II: T. 2 /mnl.
When L. 2 /mnL. similar to the proof of equation 41 we can upper bound the number of iterations
based on Lemma 3.6 Specifically, the number of iterations for l|z z=1 I is
(
K=o o
log
pm
o
log
(45)
LIFO Calls:
Under the parameter settings of Lemma 3.6 the LIFO calls required for each iteration (m.). Therefore, the total LIFO calls can be upper bounded by
/mnL.
O (mnK))
log
(46)
Computation Rounds: For each iteration, the computation rounds per node are O(n), and thus the total computation rounds are bounded by
(nk) = nn
( )
log
(47)
Under the parameter settings of Lemma 3.6 holds that R - Ô (Vx). The communication rounds are bounded by
Communication Rounds:
KR -R= Ō = (VVLL
XXL log ()))
(48)
Finally, combining the results of Case and Case II, we obtain that for any < S L, running Algorithm 2 with appropriate parameter settings find an e-suboptimal solution each node, with the expected LIFO complexity of
(mm++ + min minfmmL, v VmnLL) log (1) )
43

---

the expected computation rounds of and the communication rounds
ò
((n+
min(nL, v /n/m/// /n/mL]
log )
m
VXL 1
- )
log
D
The Proofs for Section 4
In this section, we will establish the complexity lower bounds presented in Section 4
The proofs of D.2 and D.3 respectively.
Theorems 4.2 and 4.4 are provided in Appendix D.I
D.1 The Proof of Theorem
47 established the LIFO complexity lower bound for the single-machin finite-sum problem. We extend this result to the decentralized setting and derive lower bounds with respect to the smoothness parameters L and L.
Luo et al.
Let d = dly and N mm. Without loss of generality, the algorithm can be assumed to start at (xx) y) = (0, Following Luo al. 477, we consider the function H Rd RRd - defined as
H(x,y:7,
||x|] x (By c) 2 11x
(49)
where
-1 1
B
E Rdxd
700
(w, 0,0....... O,, and w ( -2/
To characterize the zero-chain property [58 of H, define subspaces Fx
Fx span C1, C2. ......, cxt,
k = 1, 1....,d. d.
(0a),
k=
where (ei,...,ee:) ed} standard basis Rd.
Following lemma characterizes the properties of H.
Lemma D.1 (Luo et al. 47 Lemma 13]). The function H has following properties:
1. H is / + 2
2. For k < d, if (x, E Fx x Fu. then (x,H(x,)) (x,((x))) E FR+1 x FkHt
3. Letr (2 + T/7² + 4)/2. The saddle point of H is
x" (r, .....
y" pr,p2
pdl1
ndd
4. For l S d/2 and (x,y) Fs FR, holds that
xx - x"
2 +
y
y
1
1
24
x
+ I
2
44

---

Lemma D.2. For the parameters L 2 L. min L2 mnL > 10mn. and e < e- there exists a hard instance satisfying Assumptions 2.1
2.4 In order to find an e-suboptimal solution, the
LIFO calls of any LIFO algorithm is lower bounded by
Ω min min(mmL, v )
log )
1
Proof. Recalling that N = mn, we define a matrix sequence { such that U; E RdxNN U and U.U] = for any S i + j S N. we set parameters as
8N
Nu
1 miin(L?,NL')
-=
log
V 13/1² 2N
2e
hard instance f: Rd x Nd R can be constructed as fx, = f ( 1)xx
xxx,) where
fx(.y) = {H, v.y).
The global objective function f(x; )) is given by
N
1
f(x,y)
fig (x,
XH(Uxx,UU) U.y)
mn
N
i=1
Yy 2N
N
N ΣV. BU:
b
|
Σ
UTe
N
x
|ly
N
2N
Based on Á Nu/y, it is straightforward to see that f is y-sttooglyyoomeeyyysstteyyyyooee
Then. we verify that the function satisfies the smoothness Assumptions 2.2 and 2.3 It follows that, for any V1), (2) E R Nd x R
VV - v. Y2)1
1
X²
N
Σ
U. ( V U.y2))
N
U. (V, UN)) V,H(U,X, Unya)) ')
N
(U,, - U U.2
N
+ +UV,H U.y) VUH(UXX2 12
82 + 27
N
||U((x) - x2))1 + |1,ty - y2)ll
N2
1=1
22(8+ + +272)
(Ix: - xel1² + Ily: -22113
N²
1?
(|xx
x211²
+ lyı - yz1l 11]
N2
< 2 [|x] - xell*
+ Ily1 - y2 11
where the first inequality holds by Property in Lemma D.I and the second inequality follows from the setting of L.
45

---

Meanwhile, for any (x2, E Rd x RNd, it holds that
m
- [1Vg+++(11xxxxx ( (x
mR
1 - + [ (,o((xx))))-_((xxx)))))
N
1 N
[10] U,) U.ta))l
+ -
2 N
[VHH(Uxi - V U.y:)l
N
+ + U.y1) VyH(UUx,, Unre)1
22 + 27²))
N
Σ
|U,(11 - xx)) + U. - x2))l?
N
22 + +2y2)
(|xx x211 1/++1 |ly - -2all²)
N
1
(Ix) x2l1²
+ ||y: y2ll²)
< 2.2
[|x] - x211² + I1y- y2ll%
For any LIFO algorithm with at most [d/2] LIFO calls, by Property 2 in Lemma D.I the variable x has most [NV/22] non-zero coordinates. Therefore, there exist an index in such that U E Fa/2- Then by Property in Lemma D.I we have
E [||x - x 1I + Ily y 11 2 E U. (x - x 12 i0 (y--y")l y
d/2
(| x 1 11,,,."'1?))
2
4/2
2d
2
2
1- y2
d/22+2
where the third inequality holds by the Property in Lemma D.1 ie., U,,'* = (r,r2 (d)
Note that
d
( -
1 + 2) logg + 717 + v72 + 4)
d
- + 2) log
2
2
2
d
777 v/2+ +
2 + 2)
d
( + 2)+ + 1),
where the first inequality follows the fact that log(1 + x) < x and the second inequality holds by Va 6 < va + vb for a,b 0. Since NLL)/" > 10N, we have y /BN/(12/02 2N) < 1, which further implies
d 2 + 2) log(1r) < (d 4)y S (1/(1/))).
46

---

Thus, when the number of LIFO calls is less than [Ndd/2], we have E - -x11x ly - y- > Then the LIFO calls find an e-suboptimal solution is lower bounded by
Nd
VNN 1
log ())
min (mnt. vmnI.)
log )
2
This completes the proof of Lemma D.2
For the case min (T,2, mmm.)) = O(ymm) we have the following lemma.
Lemma D.3. For the parameters L 2 L, L/P > 2, and e < 1/8, there exists hard instance satisfying Assumptions 2.4 order find e-suboptimal solution, the LIFO calls of any LIFO algorithm is lower bounded by (mmn).
Proof. Let n, and y/ denote the i-th coordinates of the vectors x and y. respectively. Consider the functions yx. = f(1-1xxnt(xx y), where
mmn
VmnL
y(( = 11 1 + 2
(x, -
21y11 -
2 (Uh 1)2
2
2
for E [mn] and L = 122/2- - n.². It follows that the global objective takes the form
y(x,)) 18 mmn
x Rm R
i.
i
f(x,y) 11 1 1 +
x - 111
2 1lyl
l1y 111
2/mn
2/mm
It is clear that f is ju-Strogly-cconvee/--tttongg concave and the saddle point (x*, y satisfies
i
1.
L mnnu
For any (x1, (x2, E Run x pm we have
Vxfi, Vxfi, (x2, + - Fy (x),
1=1
(IVxf((x),))) Vx -
(In(xI- - X2) + vmnlere, -x + | - y2) + Vmnlee, (y y2)]l²)
ma
[2/llix) x211 2mm 1e;00 (x1 x2)11
mn
+2 yz2l + 2mn22 (y1 - y2)l
=2(1² + 31 (||x -x21 + |lyi 32
_ (I|x1 2 Ily: y2ll))
Thus, the function set [f is L-mean-squared smooth (L S L) and f is L-soohth
By the zero-chain property of f, if the LIFO calls are less than mn/2, it holds that
E [||x
x² 1| lyy - 11]
i
(L + 2mnnu22
i
212 + 2mnz²²
47

---

/2 11²
mm
1,2 2p²² + 2mmp2
(1
2mn
(1 122/2² + 2mn
mm
4mmn + >
Therefore, the LIFO calls find e-suboptimal solution is lower bounded by (mm)).
Combing the results of Lemmas D.2 and D.3 for the parameters L 2 L, Lip > 2, and < 0.003,
the LIFO calls of any LIFO algorithm is lower bounded by
Ω mn minfmnL, } log - )
D.2 The proof of Theorem 4K
For any decentralized LIFO algorithm, can perform at most m LIFO calls in each computation round. From the conclusion of Theorem 4.2, follows that the LIFO calls lower bounded by
Ω mn + min (mnL, vmnL) log (
Therefore, the computation rounds have the lower bound
1 m
min (mnL, vmnL] log
+ c )))
min nT., v /n/mI.
Ω
mn
Ω
log
1
1
(50)
Another instance is direct extension of the single-machine setting 89 define
For all E [m]] and [n]]
VL2 2
L -
-²
fx,(x,)) = f(x,y)
2 Ay
c
+
|x|
(51)
4p
2
where
-1
A
E Rdxd
can be verified that the function defined in 51 satisfies Assumptions 2.1 2.2 and 2.3 as all fi.j L-smooth. From the single-machine case it is straightforward deduce that the algorithm requires at least (2L μ (og(1/e)) iterations to achieve an e-sub-optimal solution. Since each iteration requires least one computation round, this implies lower bound the computation rounds of
( log ( (
L
(52)
Combining the results equations (50) and (5)) follows that the computation rounds have a lower bound of
min nL, / /n/mL) log
)
( (
n +
+
48

---

D.3 The proof of Theorem
The main idea of proving the lower bound on communication complexity extend the difficult
examples constructed by Zhang et al. [89] to the distributed setting. First, we divide all nodes into
three sets V1, V2,, and V3. where [V1
[V2 [m/3], and V3l m V [Vel Let dg dy = d.
f22 = (L2 12) V4 (2m),
0
1 -2
1
0
A1 =
A2
E Rddd
1 2
1
1
and A = (A1 + A2)/2. For i = 1, 1,2,.... ................................ m, the functions are constructed as fi,1(x, = y) y)) where
i AIy
1
m
+
ely
+
+
1x - 11y1,, ie Vi,
-
M
4
Ap
f((xy))
m
L
x
A2y
+ 1
|x|
1
2 |ll13
i V2.
(53)
[V2l
4
X
Ilyl1?
i E V3-
2
2
Then the global objective function takes the form
i Ay
1
f(x,y) x
2
e
1 2
11x
- 11x1
4u
We will prove that the constructed functions are --mean-squaree smooth, thereby satisfying Assump- tions 2.2 and 2.3 For any X1, X2, E Rd,
(x - | -
mn
[V - V=l( - Fyl((x2,
L. Ar -1y1--2):0 + +2)++(xx x2)
Σ
m AA (x1 - -x2) - p(y1 y22)
[2 4
|ii
1
i A2 -2)) -m(x1= x22
Σ
+
m
Ag (x1 -x2) - -M(y1 y22)
m
11/2 4
V2
VEV2
[3s 2
||x] x2112 + Ily; -2212
m L
[|A( - v2)1 + ||AT (x) - -1
MV 16
+ m 1,2
|A42Y11 - x22)1 +7+++1 +IAJ - -x,)13
+ + ||x] - -x212= + !1x: y212
11/2 16
2m
1 + 122)
(||xi x2112 + Ily1 - 22
La (||xI x211² 2 Ilyi y2 12)
where the inequality holds because || 1la S 4. || < 4 and Mi = [V/)-
49

---

For decentralized algorithm starting at (x".y*) = (0, 0), its communication complexity depends on the distance between V1 and 1/2 on the graph. which is denoted by D(V, V2). Based on the zero-chain property of the constructed function, the following lemma holds.
Lemma D.4. Consider the minimax problem with the objective functions 53) For any algorithm satisfying Definition 4.1 after R communication rounds, the algorithm' output has only the first [R/ 1 V2)] coordinates non-zero, while the remaining d - RR/ (V11 V2)_ coordinates are zero.
Proof. Initially, for a variable Vi. transmitting to V/2 requires at least D(V,, V2) communication until receiving values from V1. Similarly, the nodes in V will have at most the first coordinate non-zero until they receive the non-zero values returned from V22 (Nodes in V/3 do not contribute increasing the number of non-zero coordinates.) In subsequent steps, each additional non-zero coordinate needs at least D(V1, V2) communication rounds. After R communication rounds, the output of the algorithm will have only the first [R/D(V, V2)] coordinates non-zero, while the remaining [R/ (V1,, ] coordinates zero.
rounds. According to the constructed function (53). nodes in 1/2 will maintain
The following lemma establishes lower bound on the distance between the current point and the optimal solution.
Lemma D.5 (Zhang et al. FR x Fki it holds that
89 Theorem 3.5)). For d 2 max(4k, (lo((/,/,lo((/422)) and (x, y) E
x x x11 + I1y y" y=1 2 7h 11y - y1
E
16
where ((2 (2 1)2 4)/2 (0, 1) and 4/²/
Combing the result of Lemma D.4 it holds that for any decentralized first-order algorithm satisfying Definition 4.1 the output (x Youl after R communication rounds will satisfy
E
y y²11 2 D.
(54)
16
Lemma D.6 (Yuan et al. [88 Theorem IJ). For any m 2 and X2 E [0, cos( /mm))//m)) we can always
construct ring-latticn graph that the mixing matrix W satisfies Assumption 2.4and X2 (W) X2. and the diameter of the graph satisfies
D(V, V22 (vx))
With the above lemmas, we proceed to prove Theorem 4.4
Proof of Theorem 4.4 By equation (54), find an e-suboptimal solution, communication rounds R are lower bounded by
Ily -x'11)
log 1
R 2 D(V, V2) log
16E
For any æ >> it holds that (log(1 1 x))
-1
x- Thus, we have
1
1+ - -1)
log
log
> 1-7 7
1+ 2 10--1/10 1/ + 1)2 4
1/ + 1)2 4-
() 1
2r
i
4μ²
V 4
+
i
50

---

12
1
V
1
2
2
L
11
Based on the fact that 1 = (L22 - 1² 1/ where = - [m/3] and L 2 2p, follows that = (T.)). Therefore, for any decentralized LIFO algorithm, the communication rounds have the lower bound:
Ily y²113)
R2 D(V1, log
log
16E
L
)
Ω
D(V. V22
log
1
VXL Ω
log )
where the last step holds by Lemma D.6
51


Reviews:
[{"review_id": "s5bl3wLcqq", "reviewer": "Reviewer_nrCq", "summary": "In this paper, the authors consider decentralized finite-sum strongly convex–strongly concave saddle-point problems. To solve this problem, they propose a new variance-reduced algorithm called __DIVERSE__. The algorithm is a non-trivial combination of OGDA and Snapshot Gradient Tracking. They provide convergence guarantees along with new theoretical lower bounds, which match their upper bounds. To support their theoretical findings, they present experimental results demonstrating that the proposed method outperforms previous approaches.", "questions": "__Questions:__\n\n1.On page 28, right after line 669, there is an equation:\n$$\\sum_{i=0}^m ||g_i(z^{0})||^2 = \\sum_{i=0}^m ||g_i(z^{0}) - g_i(z^{\\star})||^2.$$\nHowever, this holds only if each $g_i(z^{\\star}) = 0$. I believe this is a mistake in your proof. Could you comment on this observation?\n\n__Recommendations:__\n\n1.It would be better to cite the following two papers on the snapshot technique for gradient tracking:\nhttps://arxiv.org/abs/2110.05282,\nhttps://arxiv.org/abs/2212.05273.\n\n2.To be more precise, DIVERSE is not based exactly on OGDA but rather on the Operator Extrapolation method (https://arxiv.org/abs/2011.02987), which shares similarities in the convergence analysis. Citing this work could help clarify the construction of the method.\n\n3.Please introduce the definition of $\\Delta^k$ in the main part of the paper.\n\n\nI may consider increasing my score if all of my questions are addressed.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strengths:__\n\n1. Well-written paper. \n\n2. Strong theoretical findings: novel lower bounds and a new algorithm. \n\n__Weaknesses:__\n\n1. The complexity of DIVERSE has an additional logarithmic factor compared to OADSVI. \n\n2. See the Questions section.", "was_revised": true, "final_justification": "From my perspective, this is a good theoretical paper. The main algorithm is based on idea of the work (https://proceedings.neurips.cc/paper_files/paper/2022/file/c959bb2cb164d37569a17fa67494d69a-Paper-Conference.pdf). I recommend to accept this paper.", "rebuttal": "Thank you for your careful review and constructive suggestions.\n\n> On page 28, right after line 669, there is an equation:\n$$\\sum_{i=1}^m\\\\| g_i(z^0)\\\\|^2 = \\sum_{i=1}^m\\\\|g_i(z^0)-g_i(z^\\star)\\\\|^2.$$\nHowever, this holds only if each $g_i(z^\\star) = 0$.  I believe this is a mistake in your proof. Could you comment on this observation?\n\nThank you for pointing out the issue in the proof.\nIt can addressed by modifying the upper bound of $\\\\| \\mathbf{S}^0 - \\mathbf{1} \\bar{\\mathbf{s}}^0 \\\\|^2$ and it does not affect our main results.\nSpecifically, we can upper bound $\\\\| \\mathbf{S}^0 - \\mathbf{1} \\bar{\\mathbf{s}}^0 \\\\|^2$ as\n\\begin{align*}\n\\\\| \\mathbf{S}^0 - \\mathbf{1} \\bar{\\mathbf{s}}^0 \\\\|^2 \n&= \\\\| \\mathtt{FastMix}(\\mathbf{\\Delta}^0, \\mathbf{W}, R) - \\frac{1}{m} \\mathbf{1} \\mathbf{1}^\\top \\mathtt{FastMix}(\\mathbf{\\Delta}^0, \\mathbf{W}, R) \\\\|^2 \\\\\\\\\n&\\le \\rho^2 \\\\| \\mathbf{\\Delta}^0 - \\frac{1}{m} \\mathbf{1} \\mathbf{1}^\\top \\mathbf{\\Delta}^0 \\\\|^2 \\\\\\\\\n&\\le \\rho^2 \\\\| \\mathbf{\\Delta}^0 \\\\|^2\\\\\\\\\n& = \\rho^2 \\sum_{i=1}^m \\\\| \\mathbf{g}\\_i(\\mathbf{z}^0) \\\\|^2\\\\\\\\\n& \\le 2 \\rho^2 \\sum_{i=1}^m \\\\| \\mathbf{g}\\_i(\\mathbf{z}^0) - \\mathbf{g}\\_i(\\mathbf{z}^\\star) \\\\|^2 + 2 \\rho^2 \\sum_{i=1}^m \\\\| \\mathbf{g}\\_i(\\mathbf{z}^\\star) \\\\|^2\\\\\\\\\n& \\le 2 \\rho^2 m^2 \\bar{L}^2 \\\\| \\mathbf{z}^0 - \\mathbf{z}^\\star \\\\|^2 + 2 \\rho^2 \\sum_{i=1}^m \\\\| \\mathbf{g}\\_i(\\mathbf{z}^\\star) \\\\|^2,\n\\end{align*}\nwhere the first inequality holds by Proposition B.2, the second inequality follows from the fact that $\\\\| \\mathbf{A} - \\frac{1}{m}\\mathbf{1} \\mathbf{1}^\\top\\mathbf{A} \\\\| \\le \\\\| \\mathbf{A} \\\\|$ for any $\\mathbf{A} \\in \\mathbb{R}^{m\\times d_z}$, the third inequality is based on Young's inequality, and the last inequality holds due to Assumption 2.3.\nThen we modify the setting of $R$ (equation (31) on page 27) by replacing the last term in the max  operator (in the logarithmic term) with \n$\\frac{8C\\_1\\eta^2 \\left(m^2 \\bar{L}^2 \\\\| \\mathbf{z}^0 - \\mathbf{z}^\\star \\\\|^2 + \\sum_{i=1}^m \\\\| \\mathbf{g}\\_i(\\mathbf{z}^\\star) \\\\|^2 \\right)}{(1-\\tilde{\\alpha})\\tilde{\\alpha}\\Phi^0},$\nwhich guarantees\n$\\rho^2 \\le \\frac{(1-\\tilde{\\alpha})\\tilde{\\alpha}\\Phi^0}{8C\\_1\\eta^2 \\left(m^2 \\bar{L}^2 \\\\| \\mathbf{z}^0 - \\mathbf{z}^\\star \\\\|^2 + \\sum_{i=1}^m \\\\| \\mathbf{g}\\_i(\\mathbf{z}^\\star) \\\\|^2 \\right)}.$\n\nCombining the above modified upper bounds of $\\\\| \\mathbf{S}^0 - \\mathbf{1} \\bar{\\mathbf{s}}^0 \\\\|^2$ and $\\rho^2$, we can achieve \n\\begin{align*}\n\\\\| \\mathbf{S}^0 - \\mathbf{1} \\bar{\\mathbf{s}}^0 \\\\|^2  \n\\le \\frac{1-\\tilde{\\alpha}}{4\\eta^2 C_1} \\tilde{\\alpha} \\Phi^0.\n\\end{align*}\n\nTherefore, we have obtain the desired result and the remaining proof after line 669 still holds.\nWe emphasize that the modification of $\\rho^2$ only affect the logarithmic term in $R$.\nHence, the overall communication complexity is still in the order of $TR=\\tilde{\\mathcal{O}}(\\sqrt{\\chi}L/\\mu \\log(1/\\epsilon))$, which is not changed.\n\n> It would be better to cite the following two papers on the snapshot technique for gradient tracking [A, B].\n\n> To be more precise, DIVERSE is not based exactly on OGDA but rather on the Operator Extrapolation method [C], which shares similarities in the convergence analysis. Citing this work could help clarify the construction of the method.\n\nThank you for these suggestions. We are happy to include the recommended references in  revision. \nSpecifically, we will cite references [A] and [B] in the literature review of decentralized optimization.\nWe will also cite reference [C] to clarify the connection between DIVERSE and the Operator Extrapolation framework.\n\n> Please introduce the definition of $\\mathbf{\\Delta}^k$ in the main part of the paper.\n\nThanks for your suggestion.\nWe will explicitly introduce the definition of $\\mathbf{\\Delta}^k$ in our revision. \nSpecifically, it is the aggregated matrix of local gradient estimators $\\\\{\\mathbf{\\delta}^k_i\\\\}_{i=1}^m$ (defined in equation (3)), i.e., \n\\begin{align*}\n\\mathbf{\\Delta}^k =\n\\begin{bmatrix}\n\\mathbf{\\delta}^k_1 \\\\\\\\\n\\vdots \\\\\\\\\n\\mathbf{\\delta}^k_m\n\\end{bmatrix}\n\\in \\mathbb{R}^{m \\times d_z}.\n\\end{align*}\n\n---\nReferences\n\n[A] Zhuoqing Song, Lei Shi, Shi Pu, and Ming Yan. Optimal gradient tracking for decentralized optimization. Mathematical Programming, 207:1–53, 2024.\n\n[B] Haishan Ye and Xiangyu Chang. Snap-shot decentralized stochastic gradient tracking methods. arXiv preprint arXiv:2212.05273, 2022.\n\n[C] Georgios Kotsalis, Guanghui Lan, and Tianjiao Li. Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation. SIAM Journal on Optimization, 32:2041–2073, 2022."}, {"review_id": "zJoAnO1gqH", "reviewer": "Reviewer_H3m2", "summary": "This paper studies the decentralized finite-sum minimax optimization problem under the strongly-convex-strongly-concave setting. The authors propose a DIVERSE algorithm, which achieves near-optimal complexities for local oracle calls, computation rounds, and communication rounds. The primary contribution is that the derived complexity bounds depend on the *global* smoothness parameters of the objective function, rather than the *local* (and often much larger) smoothness parameters that prior works rely on. The authors provide a rigorous theoretical analysis, establishing both upper bounds for their algorithm and nearly matching lower bounds for a broad class of decentralized first-order methods. The theoretical findings are validated by numerical experiments on a robust linear regression problem, where DIVERSE outperforms existing state-of-the-art algorithms.", "questions": "1. What do we use a stochastic gradient batch-size? The authors claim, “It is worth noting that existing decentralized minimax optimization methods require identical mini-batch size for all the nodes when constructing the local gradient estimator, which is sample inefficient.” Authors need to justify it.\n    \n2. What are the key techniques to enable a sharper bound?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper makes a contribution by providing a sharper bound in decentralized minimax optimization.\n    \n\n**Weaknesses:**\n\n- This paper does not provide insight into the algorithm design, rendering it to seem like a simple combination of several existing methods.\n    \n- Even though the theoretical analysis is correct and solid, it is better to highlight the key steps in the proof to provide more information to the audience. For example, the idea of establishing the lower bound.\n    \n- Some technical claims have not been fully justified. See **Question.**\n    \n- The experiments do not report error bars or any other measure of statistical significance.", "was_revised": true, "final_justification": "I have carefully read the author's responses to my comments and the feedback from the other reviewers. The author has addressed all of my questions and concerns effectively. I am now confident in supporting the publication of this manuscript and will maintain my initial high score.", "rebuttal": "Thank you for the positive evaluation and comments.\n\n> This paper does not provide insight into the algorithm design, rendering it to seem like a simple combination of several existing methods.\n\n**A1:** We have introduced the insight of our algorithm in Section 3.1. As mentioned in lines 159-165, the main difference between our DIVERSE and exiting methods [37, 44, 53] is that the mini-batch sizes of our  local gradient estimators $\\\\{\\delta_i^k\\\\}\\_{i=1}^m$ in equation (3) are not identical since the variables $\\\\{\\xi_{i,j}^k\\\\}_{i,j=1}^{m,n}$ are random. Therefore, the behaviors of all $m$ nodes are similar to that of the stochastic gradient estimator with large mini-batch $b$ on a single machine (see examples in A3 for intuition), which is the core idea to achieve the sharper complexity bounds that depend on the global smoothness. The above ideas and results have not appeared in existing works [37, 44, 53], since they only consider the fixed mini-batch size for all nodes.\n\n> Even though the theoretical analysis is correct and solid, it is better to highlight the key steps in the proof to provide more information to the audience. For example, the idea of establishing the lower bound.\n\n**A2:** Thank you for your suggestion. We sketch and highlight the key steps for the proof of our lower bound on LIFO calls (Theorem 4.2) as follows.\n\n- We first introduce Lemma D.1 to construct the function defined equation (48) and present its properties of smoothness, zero-chain, and saddle point.\n\n- We then introduce Lemma D.2 to achieve the second term $\\Omega( \\min \\\\{ mn L, \\sqrt{mn}\\bar{L}\\\\}/\\mu \\log ( 1/\\epsilon))$ by scaling and spiting the function defined equation (48), which leads to the construction of local functions $f_{i,j}$ in line 790.\n\n- Consequently, Lemma D.3 is introduced to achieve the first term $\\Omega(mn)$ in our lower bound by constructing the decoupled function defined in line 814. \n\n- Combining Lemmas D.2 and D.3 yields the final lower bound in Theorem 4.2.\n\nWe are happy to incorporate a sketched proof for Theorem 4.2 and other main results in our revision.\n\n> Some technical claims have not been fully justified. See Question.\n\n> What do we use a stochastic gradient batch-size? The authors claim, “It is worth noting that existing decentralized minimax optimization methods require identical mini-batch size for all the nodes when constructing the local gradient estimator, which is sample inefficient.” Authors need to justify it.\n\n**A3:** We first provide the intuition in the case of $n=1$. In this case, our method requires only a subset of nodes to compute their local gradients, since line 6 of Algorithm 2 involves the random variable $\\xi_{i,j}^k$. In contrast, all existing methods [37, 44, 53]  require all the nodes to compute their local gradients because the mini-batch sizes on all the nodes are identical and must be 1 (because $n=1$). This means existing methods have to compute the full gradient of the objective and they are sample inefficient.\n\nFor the general $n$, the stochastic batch-size allows our method to behave similar to solving the finite-sum problem with $mn$ components on a single machine, leading to the dependency on the global mean-squared smoothness parameter $\\bar{L}$ in the complexity. In contrast, the fixed batch-size in existing methods leads to the dependency on the local smoothness parameter $\\bar{L}_l$. Recall that $\\bar L$ is typically smaller than $\\bar{L}_l$, which means our method is more efficient.\n\nIf we ignore the difference among smoothness parameters (i.e., $\\bar L={\\bar L}_\\ell=L$), our method achieves the LIFO complexity of $\\mathcal{O}(mn + \\sqrt{mn}L/\\mu)$ while the state-of-the-art OADSVI [37] requires $\\mathcal{O}(mn + m\\sqrt{n}L/\\mu)$. The tighter dependence on $m$ is also attributed to the novel stochastic mini-batch sizes we have used.\n\n> What are the key techniques to enable a sharper bound?\n\n**A4:** The key technique is introducing the stochastic mini-batch sizes to achive the better dependence on the smoothness parameter. Please see A1 and A3 for the detailed explanation.\n\n> The experiments do not report error bars or any other measure of statistical significance.\n\n**A5:** Thanks for your suggestion. We have run our experiments by 10 times and present the the mean and standard deviation as follows. The three tables report the LIFO calls, computation rounds, and communication rounds required to achieve an accuracy of 1e-5 (i.e., $\\\\| \\mathbf{z} - \\mathbf{z}^\\star \\\\|^2 \\leq 10^{-5}$).\n\n- LIFO calls:\n| |a9a|w8a|ijcnn1|cod-rna|\n|-|-|-|-|-|\n|MC-SVRE|2.1e6 ±7.1e4|1.5e6 ±9.0e4|1.5e6 ±6.9e4|7.3e6 ±3.8e5|\n|OADSVI|2.5e6 ±1.3e5|2.9e6 ±2.5e5|1.8e6 ±2.1e5|5.6e6 ±6.8e5|\n|DIVERSE|8.1e5 ±6.7e4|6.1e5 ±7.2e4|4.6e5 ±1.3e5|2.1e6 ±1.8e5|\n\n\n- Computation rounds:\n| |a9a|w8a|ijcnn1|cod-rna|\n|-|-|-|-|-|\n|MC-SVRE|4.2e4 ±1.4e3|3.1e4 ±1.8e3|3.0e4 ±1.4e3|1.5e5 ±7.7e3|\n|OADSVI|4.9e4 ±2.7e3|5.8e4 ±5.0e3|3.6e4 ±4.2e3|1.1e5 ±1.4e4|\n|DIVERSE|2.9e4 ±3.7e3|2.0e4 ±4.0e3|1.7e4 ±6.0e3|5.4e4 ±4.2e3|\n\n\n- Communication rounds:\n| |a9a|w8a|ijcnn1|cod-rna|\n|-|-|-|-|-|\n|MC-SVRE|2.2e5 ±2.3e4|1.1e5 ±1.1e4|1.2e5 ±1.9e4|1.9e5 ±2.9e4|\n|OADSVI|4.6e4 ±1.5e3|4.7e4 ±3.1e3|3.1e4 ±2.7e3|4.7e4 ±6.1e3|\n|DIVERSE|4.2e4 ±8.3e3|2.5e4 ±8.7e3|2.5e4 ±9.1e3|3.9e4 ±7.1e3|\n\nExperimental results show that DIVERSE has lower variance in LIFO calls and communication rounds than existing state-of-the-art algorithms, indicating its stability.\n\n---\nReferences\n\n[37] Dmitry Kovalev, Aleksandr Beznosikov, Abdurakhmon Sadiev, Michael Persiianov, Peter Richtárik, and Alexander Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. In Advances in Neural Information Processing Systems, pages 31073–31088, 2022.\n\n[44] Luo Luo and Haishan Ye. Decentralized stochastic variance reduced extragradient method. arXiv preprint arXiv:2202.00509, 2022.\n\n[53] Soham Mukherjee and Mrityunjoy Chakraborty. A decentralized algorithm for large scale min-max problems. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 2967–2972. IEEE, 2020."}, {"review_id": "inBu6kmLJw", "reviewer": "Reviewer_TwzD", "summary": "This paper designs a variance-reduced optimistic gradient method with stochastic mini-batch sizes for distributed convex-concave finite-sum minimax problem. And the method could achieve a linear convergence rate depends on global smoothness(not local smoothness) in strongly-convex-strongly-concave situation. In addition, experiments show that performance of proposed method is better than existing methods.", "questions": "1 Could you share additional experimental results, such as accuracy with respect to LIFO, communication rounds, and computation rounds for the four datasets already included? If more datasets have been evaluated, including those results would further strengthen the empirical section and support the generality of the proposed method.\n\n2 In the convergence rate analysis, what specific challenges arise from the change in assumptions, and how are they addressed in your analysis? While I believe the modification of the assumptions is meaningful, it is unclear to me whether it introduces significant technical complications or fundamentally alters the existing analytical framework.\n\n3 I have some concerns regarding the novelty of the algorithm. The integration of variance-reduction techniques alone may not substantially deviate from existing methods in terms of analysis. Could you elaborate on the statement at the end of Section 3.1, where you mention that the change to the mini-batch size for the local gradient estimator is one of the key differences from existing work? Specifically, how is this change handled in the convergence rate analysis, and does it pose any unique analytical challenges?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1 The paper makes a reasonable adjustment to the assumptions, allowing the convergence rate to be analyzed in terms of both the upper and lower bounds with respect to the global smoothness parameter and the mean-squared smoothness parameter. This differs significantly from existing work that relies on local smoothness assumptions, which may be less realistic in heterogeneous data scenarios.\n\n2 The structure of the paper is clear, and both the algorithmic design and the theoretical contributions are well explained.\n\n3 The experiments include a wide range of baselines under comparable settings, and the reported results are convincing.\n\nWeaknesses\n\n1 The experimental section is relatively limited in terms of dataset diversity, which may restrict the generalizability of the results. Additionally, the absence of commonly reported evaluation metrics such as accuracy makes it difficult to comprehensively assess the practical effectiveness of the proposed method. As a result, the experimental validation appears somewhat narrow and could benefit from more thorough benchmarking.\n\n2 The main algorithmic contributions seem to lie in the incorporation of variance-reduction techniques and a modification to the minibatch size used for local gradient estimators, which is fixed in prior methods. While these changes are reasonable, they appear to be incremental improvements rather than fundamental innovations. The overall level of novelty is therefore somewhat limited.", "was_revised": true, "final_justification": "Considering the additional experiments provided by the authors and the theoretical proof of the proposed method in the paper, I believe the methodology is solid and its feasibility has been demonstrated experimentally. However, as I am not deeply familiar with this specific subfield, I am unable to strongly advocate for the acceptance of this paper.", "rebuttal": "Thank you for the positive evaluation and suggestions.\n\n> The experimental section is relatively limited in terms of dataset diversity, which may restrict the generalizability of the results. Additionally, the absence of commonly reported evaluation metrics such as accuracy makes it difficult to comprehensively assess the practical effectiveness of the proposed method. As a result, the experimental validation appears somewhat narrow and could benefit from more thorough benchmarking.\n\n> Could you share additional experimental results, such as accuracy with respect to LIFO, communication rounds, and computation rounds for the four datasets already included? If more datasets have been evaluated, including those results would further strengthen the empirical section and support the generality of the proposed method.\n\n**A1:** Thank you for your suggestion. The following three tables report the classification accuracy at 1e6 LIFO calls, 4e4 computation rounds, and 5e4 communication rounds, respectively.\n\n- Classification accuracy at 1e6 LIFO calls\n|Accuracy (%) |a9a|w8a|ijcnn1|cod-rna|\n|-|-|-|-|-|\n|GT-EG|71.66|38.83|42.77|63.65|\n|MC-SVRE|77.43|69.61|79.14|72.13|\n|OADSVI|77.40|69.78|78.25|75.20|\n|DIVERSE|82.53|84.94|80.26|80.41|\n\n- Classification accuracy at 4e4 computation rounds\n|Accuracy (%) |a9a|w8a|ijcnn1|cod-rna|\n|-|-|-|-|-|\n|GT-EG|71.74|39.01|42.77|63.65|\n|MC-SVRE|81.62|75.36|78.89|72.69|\n|OADSVI|81.89|75.52|78.19|78.86|\n|DIVERSE|82.67|88.49|81.16|81.70|\n\n- Classification accuracy at 5e4 communication rounds\n|Accuracy (%) |a9a|w8a|ijcnn1|cod-rna|\n|-|-|-|-|-|\n|GT-EG|71.80|39.33|42.81|63.68|\n|MC-SVRE|76.41|62.73|75.85|72.53|\n|OADSVI|82.64|87.70|90.26|82.84|\n|DIVERSE|82.67|88.51|90.26|82.85|\n\nThe results indicate that DIVERSE consistently yields the best performance in terms of classification accuracy.\n\nIn addition, we conducted adversarial training on the MNIST dataset using the following robust logistic regression model:\n\\begin{align*}\n\\min_{x \\in \\mathbb{R}^d} \\max_{\\substack{\\\\|y\\\\|\\_{\\infty} \\le M}} \\frac{1}{N} \\sum_{i=1}^N \\log \\left(1 + \\exp (-b\\_i (x + y)^\\top a\\_i)\\right) + \\frac{r\\_1}{2}\\\\|x\\\\|^2 - \\frac{r\\_2}{2}\\\\|y\\\\|^2,\n\\end{align*}\nwhere $x$ is the model parameter, $y$ is an adversarial perturbation constrained by $\\\\|y\\\\|\\_{\\infty}\\le M$, and $a_i \\in \\mathbb{R}^d$ and $b_i \\in \\\\{\\pm 1\\\\}$ denote the feature and label of the $i$‑th sample. \nThe experimental results are shown in the following three tables, where where \"Std\" denotes the standard test accuracy and \"Adv\" denotes the adversarial accuracy under $L_\\infty$ perturbations of radius 0.2.\n\n|LIFO calls|3e5| |5e5| |1e6| |\n|-|-|-|-|-|-|-|\n|Accuracy (%)|Std|Adv|Std|Adv|Std|Adv|\n|GT-EG|46.85|35.85|47.53|45.35|47.54|46.85|\n|MC-SVRE|96.26|19.16|98.50|53.36|98.61|78.01|\n|OADSVI|94.72|21.02|98.50|50.96|98.61|75.08|\n|DIVERSE|98.45|52.08|98.61|77.59|98.56|78.12|\n\n|Computation rounds|2e4| |3e4| |5e4| |\n|-|-|-|-|-|-|-|\n|Accuracy (%)|Std|Adv|Std|Adv|Std|Adv|\n|GT-EG|47.51|42.53|47.54|46.15|47.54|46.85|\n|MC-SVRE|98.61|30.78|98.61|67.34|98.61|78.01|\n|OADSVI|98.53|40.71|98.58|72.09|98.56|78.06|\n|DIVERSE|98.55|74.81|98.56|78.12|98.56|78.12|\n\n|Communication rounds|2e4| |3e4| |5e4| |\n|-|-|-|-|-|-|-|\n|Accuracy (%)|Std|Adv|Std|Adv|Std|Adv|\n|GT-EG|47.53|44.71|47.54|46.69|47.54|46.80|\n|MC-SVRE|47.86|44.61|55.76|38.53|87.24|24.55|\n|OADSVI|94.39|20.92|98.56|64.78|98.61|77.21|\n|DIVERSE|98.45|45.89|98.56|69.80|98.56|78.12|\n\nThese additional results on adversarial logistic regression with the MNIST dataset further support the generality of DIVERSE.\n\n> In the convergence rate analysis, what specific challenges arise from the change in assumptions, and how are they addressed in your analysis? While I believe the modification of the assumptions is meaningful, it is unclear to me whether it introduces significant technical complications or fundamentally alters the existing analytical framework.\n\n**A2:** Compared to previous works [37, 44, 53], the main assumption change is that only the global smoothness rather than local smoothness is required. To obtain the  tighter complexity bounds that depend on the global parameters $L$ and $\\bar{L}$, we have introduced the random variables $\\\\{\\xi\\_{i,j}^k\\\\}$ to construct the gradient estimators $\\\\{\\delta\\_i^k\\\\}\\_{i=1}^m$ with stochastic mini-batch sizes.\nThis scheme makes the algorithm behave more like in the finite-sum optimization on single-machine case (see the example in A3 to Reviewer H3m2 for intuition). The analysis becomes more difficult after the introduction of the random variables $\\\\{\\xi_{i,j}^k\\\\}$ since  the related local gradient estimators may have different batch-sizes.\nSpecifically, all of our analysis has to be conducted base on the global smoothness parameters $L$ and $\\bar{L}$ (see pages 19, 20, 24, and 25) rather than the larger local parameters in related works.\n\nMoreover, different with previous works [37, 44, 53] which only consider computation rounds and communication rounds, we also consider the LIFO calls and prove our algorithm is (nearly) optimal with respect to all the three criteria. We emphasize that the LIFO calls are not always proportional to the computation rounds in distributed setting due to the partial participated computation. \n\n> The main algorithmic contributions seem to lie in the incorporation of variance-reduction techniques and a modification to the minibatch size used for local gradient estimators, which is fixed in prior methods. While these changes are reasonable, they appear to be incremental improvements rather than fundamental innovations. The overall level of novelty is therefore somewhat limited.\n\n> I have some concerns regarding the novelty of the algorithm. The integration of variance-reduction techniques alone may not substantially deviate from existing methods in terms of analysis. Could you elaborate on the statement at the end of Section 3.1, where you mention that the change to the mini-batch size for the local gradient estimator is one of the key differences from existing work? Specifically, how is this change handled in the convergence rate analysis, and does it pose any unique analytical challenges?\n\n**A3:** We emphasize that the main difference between our algorithm and existing methods lies in the introduction of the random variables $\\\\{\\xi_{i,j}^k\\\\}$ (yielding stochastic mini-batch sizes), rather than the variance-reduction technique. \n\n- The stochastic mini-batch sizes enable the algorithm to behave more like the finite-sum optimization on single-machine, leading to the better dependency on smoothness parameters and $m$. Please see A2 for details.\n\n- Since the the gradient estimators $\\\\{\\delta_i^k\\\\}_{i=1}^m$ may have different mini-batch sizes, the existing analysis for the fixed batch-size does not work. Therefore, our analysis for the gradient estimators is quite different from the counterpart in existing work. Specifically, the analysis on the page 19, 20, 24, and 25 is based on the global smoothness parameter $L$ and $\\bar L$, while the analysis in exiting work [37, 44, 53] are based on the larger local parameters.\n\n---\nReferences\n\n[37] Dmitry Kovalev, Aleksandr Beznosikov, Abdurakhmon Sadiev, Michael Persiianov, Peter Richtárik, and Alexander Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. In Advances in Neural Information Processing Systems, pages 31073–31088, 2022.\n\n[44] Luo Luo and Haishan Ye. Decentralized stochastic variance reduced extragradient method. arXiv preprint arXiv:2202.00509, 2022.\n\n[53] Soham Mukherjee and Mrityunjoy Chakraborty. A decentralized algorithm for large scale min-max problems. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 2967–2972. IEEE, 2020."}, {"review_id": "WPoHAZu93v", "reviewer": "Reviewer_96So", "summary": "This paper addresses decentralized convex-concave finite-sum min-max optimization over networks and proposes the DIVERSE algorithm (Decentralized Variance-Reduced Optimistic Gradient with Stochastic mini-batch sizes). While the theoretical analysis is solid and the claimed complexity results improve upon existing works under strongly-convex-strongly-concave settings, the submission falls short in several key areas. In particular, the algorithmic novelty over prior methods is not sufficiently emphasized or clearly explained.  The experimental section is limited and does not adequately support the theoretical claims or demonstrate practical advantages.  Furthermore, the overall presentation lacks clarity, especially in conveying intuition and key technical contributions.", "questions": "1. Insufficient Clarification of Algorithmic Novelty​\nThe core contribution—stochastic mini-batch sampling—lacks thorough motivation. The authors should explicitly clarify:\n(a) How the Bernoulli sampling scheme overcomes the \"identical mini-batch size\" limitation (Lines 46–47) and enables partial participation across nodes;\n(b) How this design shifts complexity dependence from local smoothness parameters s ( $L_l, \\bar{L}_l$ ) to global ones ( $L, \\bar{L}$ ), with direct comparisons to methods like OADSVI [37]. This should be emphasized in Sections 1 and 3.1.\n​\n2.Inadequate Experimental Validation​\nExperiments are limited to robust linear regression (quadratic costs, Eq. 52) on a ring network. To demonstrate generality:\n(a) Include complex minimax benchmarks (e.g., GAN training or adversarial learning);\n(b) Test under data-heterogeneity scenarios (Example A.1) to validate superiority over GT-EG/MC-SVRE in practical settings where $\\bar{L} \\gg L$. \n\n3. Ambiguous Parameter Selection Rationale\nCritical parameters in Algorithm 2 $(p, b, \\alpha)$ are presented without derivation (Lemma 3.1). The authors must:\n(a) Justify design choices (e.g., $p=\\frac{\\bar{L}}{8 L} \\max  \\left( \\frac{\\mu}{L}, \\frac{1}{\\sqrt{m n}} \\right)$ ) in the main text or appendix;\n(b) Discuss practical implications of the $\\bar{L} \\leq \\sqrt{m n} L$ vs. $\\bar{L}>\\sqrt{m n} L$ cases on parameter tuning.\n\n4. Experiments Overlook Theoretical Highlights\nExperiments omit key innovations:\n(a) Performance under varying $\\frac{\\bar{L}}{L}$ ratios (to showcase global-smoothness dependency);\n(b) Communication rounds across topologies with different $\\chi$ values (Fig. 1's ring network inadequately validates O $\\left(\\frac{\\sqrt{x} L}{\\mu}\\right)$ complexity).\n(c) The authors fail to provide additional datasets, case studies, and code to support reproducibility and further validation of their approach.\n\n5. Writing and Presentation Issues\n(a) Definition gaps: Asymptotic notation $\\Omega(\\cdot)$ is undefined in Theorem 4.3;\n(b) Formatting inconsistencies: Indentation in Algorithms 1-2 and line breaks in Table 1 (e.g., DIVERSE computation rounds) require alignment;\n(c) Motivation clarity: The introduction inadequately explains the practical significance of global-smoothness dependency (e.g., acceleration in $\\frac{\\bar{L}}{L} \\gg 1$ regimes).", "limitations": "Acknowledged but not mitigated: The SC-SC assumption (Sec 2.1) is clearly stated but lacks:\n- Extension plans to nonconvex settings (e.g., GANs)\n- Discussion of relaxations (e.g., weak convexity)", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths \n1. Near-Optimal Complexity with Global Smoothness Dependence\n- Achieves tight computation complexity $\\tilde{O}\\left(m n+\\frac{\\min \\{m n L, \\sqrt{m n} \\bar{L}\\}}{\\mu} \\log \\frac{1}{\\epsilon}\\right)$\nand communication complexity $\\tilde{\\mathrm{O}}\\left(\\sqrt{\\chi} \\cdot \\frac{L}{\\mu} \\log \\frac{1}{\\epsilon}\\right)$.  First decentralized minimax method whose complexity depends solely on global smoothness parameters ( $L, \\bar{L}$ ) instead of conservative local bounds ( $L_l, \\bar{L}_l$ ).Matches lower bounds (Theorems 4.2-4.4), outperforming prior art by orders of magnitude under data heterogeneity (e.g., $10 \\times$ speedup when $\\bar{L} / L=\\Theta(\\sqrt{m})$ in Ex. A.1).\n2. Breakthrough Sampling Strategy: Stochastic Mini-Batches\n- Bernoulli-based batch sizing ( $b_{i, j}^k \\sim \\operatorname{Bernoulli}(q)$ ) enables:\n- Node partial participation: Weak nodes can skip iterations dynamically.\n- No synchronized batch sizes: Eliminates computation bottlenecks in heterogeneous systems.\n- Reduces expected per-iteration cost to $\\mathrm{O}(m n p+(1-p) b)$ vs. $\\mathrm{O}(m n)$ in existing methods.\n\nWeaknesses\n- Variance reduction (Section 2.2) and multi-consensus (Algorithm 1) are repurposed techniques \n- Lower bounds (Theorems 4.2-4.4) extend single-machine results vs. introducing new proof techniques\n- Insufficient justification for global smoothness focus (no real-data examples)\n- Parameter choices $p=\\frac{\\bar{L}}{8 L} \\max  \\left( \\frac{\\mu}{L}, \\frac{1}{\\sqrt{m n}} \\right)$ lack intuition\n- Table 1 formatting obscures complexity comparisons", "was_revised": true, "final_justification": "Thank you very much for your detailed feedback. You have answered all my questions and opinions. I will improve my score.", "rebuttal": "Thank you for your careful review and suggestions.\n\n## Weaknesses\n> Variance reduction (Section 2.2) and multi-consensus (Algorithm 1) are repurposed techniques\n\n**A1:** We emphasize that our novelty is the stochastic mini-batch sampling in the algorithm design, rather than the variance reduction and multi-consensus. Please see A6 for our detailed response to the stochastic mini-batch sampling.\n\n> Lower bounds (Theorems 4.2-4.4) extend single-machine results vs. introducing new proof techniques.\n\n**A2:** Recall that existing the lower bound on single-machine only considers mean-squared smoothness parameter $\\bar L$ [45], while our distributed setting additionally consider the global smoothness parameter $L$. Therefore, our construction requires a carefully scaling on the zero-chain function (48) to guarantee our instance satisfies the smoothness conditions with respect to both $L$ and $\\bar{L}$ (e.g., lines 788, 790, and 814), which is more challenging than the single-machine case.\n\n> Insufficient justification for global smoothness focus (no real-data examples).\n\n**A3:** See A9.\n\n> Parameter choices $p=\\frac{\\bar{L}}{8L}\\max\\\\{ \\frac{\\mu}{\\bar{L}},\\frac{1}{\\sqrt{mn}}\\\\}$ lack intuition.\n\n**A4:** See A8.\n\n> Table 1 formatting obscures complexity comparisons.\n\n**A5:** See A10.\n\n## Questions\n> Insufficient Clarification of Algorithmic Novelty.\n\n**A6:** Thanks for your suggestion. \n\n(a.1) Since $\\xi_{i,j}^k$ has Bernoulli distribution, we only need to compute $g_{i,j}$ when $\\xi_{i,j}^k=1$ (line 6 of Algorithm 2).\nTherefore, the batch size on the $i$-th node is $\\sum_{j=1}^m\\xi_{i,j}^k$, which is not fixed for different $i$ and overcomes the limitation of identical mini-batch sizes in previous works. \n\n(a.2) We explain the intuition for partial participation in the case of $n=1$. In this case, our method requires only a subset of nodes to compute their local gradients, since line 6 of Algorithm 2 means node $i$ does not compute its local gradient when $\\xi_{i,1}^k=0$. \nIn contrast, all existing methods [37, 44, 53] require all  the nodes to compute their local gradients because the mini-batch sizes on all the nodes are identical and must be 1 (because $n=1$). \nFor the general $n$, node $i$ still does not compute its local (stochastic) gradient when $\\xi_{i,j}^k=0$ occurs for all $j=1,\\dots,n$, enabling partial participation across nodes.\n\n(b) The design of stochastic mini-batch sizes allows our algorithm to behave more like solving the finite-sum problem with $mn$ component functions on a single machine. \nAs a result, our complexity bounds depend on the global smoothness parameters $L$ and $\\bar{L}$.\nIn contrast, the fixed mini-batch size used in exiting methods yield a complexity bound that depends on the worst local function,  and thus the corresponding results depend on the local smoothness parameters $L_l$ and $\\bar{L}_l$.\n\n> Inadequate Experimental Validation.\n\n**A7:** Thanks for you suggestion.\n\n(a) We conduct adversarial training on the MNIST dataset using the following robust logistic regression model:\n\\begin{align*}\n\\min_{x\\in\\mathbb{R}^d}\\max_{\\substack{\\\\|y\\\\|\\_{\\infty}\\le M}}\\frac{1}{N}\\sum_{i=1}^N\\log\\left(1+\\exp(-b\\_i(x + y)^\\top a\\_i)\\right)+\\frac{r\\_1}{2}\\\\|x\\\\|^2 - \\frac{r\\_2}{2}\\\\|y\\\\|^2,\n\\end{align*}\nwhere $x$ is the model parameter, $y$ is an adversarial perturbation constrained by $\\\\|y\\\\|\\_{\\infty}\\le M$, and $a_i\\in\\mathbb{R}^d$ and $b_i\\in\\\\{\\pm 1\\\\}$ denote the feature and label of the $i$‑th sample. \nThe experimental results are shown in the following three tables, where \"Std\" denotes the standard test accuracy and \"Adv\" denotes the adversarial accuracy under $L_\\infty$ perturbations of radius 0.2.\n\n|LIFO calls|3e5||5e5| |1e6||\n|-|-|-|-|-|-|-|\n|Accuracy (%)|Std|Adv|Std|Adv|Std|Adv|\n|GT-EG|46.85|35.85|47.53|45.35|47.54|46.85|\n|MC-SVRE|96.26|19.16|98.50|53.36|98.61|78.01|\n|OADSVI|94.72|21.02|98.50|50.96|98.61|75.08|\n|DIVERSE|98.45|52.08|98.61|77.59|98.56|78.12|\n\n|Computation rounds|2e4||3e4| |5e4||\n|-|-|-|-|-|-|-|\n|Accuracy (%)|Std|Adv|Std|Adv|Std|Adv|\n|GT-EG|47.51|42.53|47.54|46.15|47.54|46.85|\n|MC-SVRE|98.61|30.78|98.61|67.34|98.61|78.01|\n|OADSVI|98.53|40.71|98.58|72.09|98.56|78.06|\n|DIVERSE|98.55|74.81|98.56|78.12|98.56|78.12|\n\n|Communication rounds|2e4||3e4| |5e4||\n|-|-|-|-|-|-|-|\n|Accuracy (%)|Std|Adv|Std|Adv|Std|Adv|\n|GT-EG|47.53|44.71|47.54|46.69|47.54|46.80|\n|MC-SVRE|47.86|44.61|55.76|38.53|87.24|24.55|\n|OADSVI|94.39|20.92|98.56|64.78|98.61|77.21|\n|DIVERSE|98.45|45.89|98.56|69.80|98.56|78.12|\n\nDIVERSE consistently achieves higher adversarial accuracy than all baselines while maintaining comparable standard accuracy, highlighting its superiority on this adversarial logistic regression task.\n\n(b) For the scenario where $\\bar{L}\\gg L$,  see the experiments in A9 (a).\n\n> Ambiguous Parameter Selection Rationale\n\n**A8:** (a) In the single machine finite-sum problem, if the probability for computing the full gradient is $\\Theta(1/\\sqrt{mn})$ and the batch size is $\\Theta(\\sqrt{mn})$, then the LIFO calls optimality can be achieved [A]. Therefore, intuitively, if $p=\\Theta(1/\\sqrt{mn})$ and $b=\\Theta(\\sqrt{mn})$, the LIFO calls should also be optimal for the distributed setting. Furthermore, if we enlarge $p$ and $b$ properly, each iteration will include more LIFO calls, thereby reducing the total number of iterations (also the communication and computation rounds) while the total LIFO calls remain unchanged.\n\nTechnically  speaking, we first establish the lower bounds (Theorems 4.2-4.4) and then attempt to show that the proposed algorithm can achieve this bound. To this end, we work out these specific parameter settings and rigorously prove that the resulting upper bound nearly matches the lower bound.\n\n(b) When $\\bar{L}>\\sqrt{mn}L$, as discussed in lines 199-201 and Lemma 3.6, the algorithm computes the full gradient at each iteration, corresponding to $b=mn$ and $p=0$. When $\\bar{L}\\le\\sqrt{mn}L$, the parameter tuning follows the setting in Lemma 3.1, as explained in (a).\n\n> Experiments Overlook Theoretical Highlights\n\n**A9:** (a) We adjust the ratio $\\bar{L}/L$ on the a9a dataset following the method in Examples A.1 and A.3, where larger ratios correspond to increased heterogeneity among local functions. This adjustment effectively enlarges $\\bar{L}$ while keeping $L$ fixed, thereby allowing us to examine the algorithm’s dependence on the global smoothness parameter. The numbers of LIFO calls and computation rounds required to achieve an accuracy of 1e-3 (i.e., $\\\\|\\mathbf{z}-\\mathbf{z}^\\star\\\\|^2\\le 10^{-3}$) are reported below.\n\n|$\\bar{L}/L$|2.19|10.54|21.16|95.06|189.04|\n|-|-|-|-|-|-|\n|LIFO calls|5.61e5|2.25e6|5.47e6|2.78e7|3.60e7|\n|Computation rounds|2.23e4|6.24e4|1.69e5|5.87e5|7.21e5|\n\nThe results show that for $\\bar{L}\\le\\sqrt{mn}L$ (i.e., $\\bar{L}/L=2.19,10.54,21.16,95.06$), the numbers of LIFO calls and computation rounds increase nearly linearly with $\\bar{L}$, demonstrating our algorithm’s dependence on the global smoothness parameter $\\bar{L}$. When $\\bar{L}\\ge\\sqrt{mn},L$ (i.e., $\\bar{L}/L=189.04$), the parameter setting of DIVERSE reduces to the case described in Lemma 3.6. In this regime, the algorithm no longer scales with $\\mathcal{O}(\\sqrt{mn}\\bar{L})$ but instead achieves the improved dependence of $\\mathcal{O}(mnL)$.\n\n(b) We additionally conduct experiments on randomly generated communication networks with $\\chi$ values of 4.72 and 48.11. The following table reports the number of communication rounds required to reach an accuracy of 1e-5 under different network topologies and datasets.\n\n|$\\chi$|a9a|w8a|ijcnn1|cod-rna|\n|-|-|-|-|-|\n|4.72|6.83e3|5.57e3|3.41e3|7.49e3|\n|48.11|2.42e4|1.48e4|1.21e4|1.95e4|\n|190.23|4.24e4|2.56e4|2.58e4|3.92e4|\n\nThese results are consistent with the theoretical $\\sqrt{\\chi}$‑dependence of the communication complexity.\n\n(c) We have provided the code in the supplementary materials. Due to limitation of file size, we only include dataset a9a. All of datasets are public and can be accessed on the LibSVM website.\n\n> Writing and Presentation Issues\n\n**A10:** Thank you for the suggestions. \n\n(a) We will explitly define $\\Omega(\\cdot)$ in revision. For two non-negative functions $f(x)$ and $g(x)$, we write $f(x) =\\Omega(g(x))$ if there exist constants $c>0$ and $x_0$ such that $f(x)\\ge c , g(x)$ for all $x\\ge x_0$.\n\n(b) We will improve the presentation of Algorithms 1–2 and Table 1 in revision.\n\n(c) We will emphasize the practical significance of global-smoothness in revision.\n\n## Limitations\n\n**A11:** Thanks for your suggestion.\nSince the general nonconvex-nonconcave problem is intractable [B], we focus on the weakly-convex-weakly-concave (WC-WC) setting.\nWe can extend proximal point iteration (PPI) [C] to establish the following update\n$$\n\\begin{cases}\n\\\\{(\\hat x_i^k,\\hat y_i^k)\\\\}\\_{i=1}^m={\\rm FastMix}(\\\\{x_i^k\\\\},\\\\{y_i^k\\\\},\\hat{R}) \\\\\\\\\n\\\\{(x_i^{k+1},y_i^{k+1})\\\\}\\_{i=1}^m={\\rm DIVERSE}(\\\\{f_{i,j}(x,y)+\\frac{\\zeta}{2}\\\\|x-\\\\hat x_i^k\\\\|^2-\\frac{\\zeta}{2}\\\\|y-\\hat y_i^k\\\\|^2\\\\}\\_{i,j=1}^{m,n},\\\\{(\\hat x_i^k,\\hat y_i^k)\\\\}\\_{i=1}^m,\\alpha,\\beta,p,b,\\eta,R,K),\n\\end{cases}\n$$\nwhere first line encourages each $(\\hat x_i^k,\\hat y^k)$ be close to their average \nand the second line extends PPI [C] to decentralized setting by using DIVERSE to solve the following sub-problem\n$$\n\\min_{x\\in{\\mathbb R}^{d_x}}\\max_{y\\in{\\mathbb R}^{d_y}}\\frac{1}{mn}\\sum_{i=1}^m\\sum_{j=1}^n f_{i,j}(x,y)+\\frac{\\zeta}{2}||x-\\hat x_i^k||^2-\\frac{\\zeta}{2}||y-\\hat y_i^k||^2,\n$$\nwhich is SC-SC by taking appropriate $\\zeta$.\nWe think by appropriate parameter settings and careful analysis, the above scheme can solve WC-WC problems.\n\n---\nReferences\n\n[A] Li et al. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. ICML 2021.\n\n[B] Daskalakis et al. The complexity of constrained min-max optimization. STOC 2021.\n\n[C] Grimmer et al. The landscape of the proximal point method for nonconvex–nonconcave minimax optimization. Mathematical Programming, 2023."}]

Author rebuttal:

Meta-review: This paper studies decentralized smooth strongly-convex–strongly-concave finite-sum min-max problems and introduces a new method, DIVERSE, for solving them. The algorithm combines Optimistic Gradient Descent Ascent, stochastic mini-batch sampling, recursive variance reduction, and a fast consensus procedure. While each of these components is known, their careful integration in this work is non-trivial. The authors succeed in designing a method that is both
- provably convergent and
- optimal.
Under the stated assumptions, they establish tight complexity upper bounds for their method and complement them with matching lower bounds for the considered setting.

I view this as a strong theoretical contribution. The reviewers largely share this assessment. In particular, although Reviewer 96So did not update their score, their final justification indicates that they would have raised it, acknowledging that the authors had adequately addressed their concerns.

The paper does have some weaknesses, most notably the limited scope of numerical experiments. However, I believe this is a relatively minor issue compared to the theoretical depth and significance of the results.

Overall, I recommend **acceptance as a Spotlight**. The problem studied is fundamental, and achieving both lower bounds and an optimal method is an important milestone in optimization research.
Decision: Accept (spotlight)