Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity
Authors: Qihao Zhou
Haishan Ye
Luo Luo
Venue: NeurIPS 2024 poster (2024)
Keywords: distributed optimization
minimax optmization
second-order similarity
Primary area: optimization

Abstract: This paper considers the distributed convex-concave minimax optimization under the second-order similarity.
We propose stochastic variance-reduced optimistic gradient sliding (SVOGS) method, which takes the advantage of the finite-sum structure in the objective by involving the mini-batch client sampling and variance reduction.
We prove SVOGS can achieve the $\varepsilon$-duality gap within communication rounds of 
${\mathcal O}(\delta D^2/\varepsilon)$, 
communication complexity of ${\mathcal O}(n+\sqrt{n}\delta D^2/\varepsilon)$,
and local gradient calls of 
$\tilde{\mathcal O}(n+(\sqrt{n}\delta+L)D^2/\varepsilon\log(1/\varepsilon))$, 
where $n$ is the number of nodes, $\delta$ is the degree of the second-order similarity, $L$ is the smoothness parameter and $D$ is the diameter of the constraint set.
We can verify that all of above complexity (nearly) matches the corresponding lower bounds.
For the specific $\mu$-strongly-convex-$\mu$-strongly-convex case, 
our algorithm has the upper bounds on communication rounds,  communication complexity, and local gradient calls of $\mathcal O(\delta/\mu\log(1/\varepsilon))$, ${\mathcal O}((n+\sqrt{n}\delta/\mu)\log(1/\varepsilon))$, and $\tilde{\mathcal O}(n+(\sqrt{n}\delta+L)/\mu)\log(1/\varepsilon))$ respectively, which are also nearly tight.
Furthermore, we conduct the numerical experiments to show the empirical advantages of proposed method.

Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity
Qihao Zhou
Haishan Ye
School of Data Science, Fudan University zhough20efudan, edu.
School of Management, Xi an Jiaotong University SGIT Al Lab, State Grid Corporation of China yehaishan@xjj tu. edu. cn
Luo Luo"
School Data Science, Fudan University Shanghai Key Laboratory for Contemporary Applied Mathematics luoluo@fudan. edu. cn
Abstract
This paper considers the distributed convex-concane minimax optimization under the second-order similarity. We propose stochastic variance-reduced optimistic gradient sliding (SVOGS) method, which takes the advantage of the finite-sum structure the objective by involving mini-batch client sampling and variance reduction. We prove SVOGS can achieve the e-duality gap within communication rounds of (*)) communication complexity of O(n + V D²/e), and local gradient calls of On + (Vnō D)D² /e log(1/E)), where n is the number nodes, 5 is the degree of the second-order similarity, L is the smoothness parameter, and is the diameter of the constraint set. We can verify that all above complexity (nearly) matches the corresponding lower bounds. For the specific soapmngyyoccoeeeesssssoooog-o-eo
case, our algorithm has the upper bounds communication rounds, communication complexity, and local gradient calls of ( log(1/e)) O((n+ /nō/ μ1) log(1/e) and O(n (n++(Vnn (vnō L)/1 log(1/ respectively, which are also nearly tight. Furthermore, we conduct the numerical experiments show the empirical advantages of the proposed method.
Introduction
We study the distributed minimax optimization problem
min max f(z, 1) #EX yE3'
Σ f(t,v))
where fa is the differentiable local function associated with the i-th node, and X' C &d and y C Rd the constraint sets. We interested in the centralized setting, where there are one and n - client nodes that collaboratively solve the minimax problem. Without loss of generality, we assume the function fi located on the server node and the functions f2..... fn are located on the client nodes. This formulation is cornerstone in the study of game theory, aiming to achieve the Nash equilibrium
node
22 covers a lot of applications such as signal processing (23 optimal
control [1]. adversarial learning (44) robust regression [5 35 and portfolio management 52
"The corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

We focus on the first-order optimization methods for solving The classical
minimax problem. approaches including extra-gradient (EG) method 224. -awwadd forward (FBF) [51. optimistic gradient descent ascent (OGDA) 43 dual extrapolation 39 and so
forth 33 38 achieve the optimal first-order oracle complexity under the assumption of Lipschitz
continuous gradient [1.
42 [5] For the objective with finite-sum structure, the stochastic variance 14
reduced methods I 10
30 53 can reduce the cost of per iteration by using the inexact gradient
and lead to the better overall computational cost than full-batch methods. It is natural to design the parallel iteration schemes by directly using above ideas to reduce the computational time in distributed setting.
The communication complexity is primary bottleneck in distributed optimization. The local functions in machine learning applications typically exhibit homogeneity [5] 18], which is helpful to improve the communication efficiency. One common measure used to describe relationships among
local functions is the second-order similarity, e.g., the Hessian of each local function differs by finite quantity from the Hessian of global objective. Based on such characterization, several communication
efficient distributed optimization methods have been established 44 8 19 20 25
29
46
48
[0 [66..
The highlight of these methods is their communication complexity bounds mainly depend on the degree of second-order similarity, which is potentially much tighter than the results depend on the
smoothness parameter 6 7
[1|
13
16.
21 22 25 26
28
32
36
37 47).
Recently, Khaled and Jin 20 Lin et al. [29] showed iterations with partial participation can further reduce the communication complexity, improving the dependence on the number of nodes. They pro- posed stochastic variance reduced proximal point methods for convex optimization, which allow only one of clients to participate into the communication the most of rounds. Additionally, Beznosikov et al. [8] combined partial participation with volume of communication complexity for minimax optimization. However, these methods [8] 20 29]
based method, reducing
increase the communication rounds, which result in more expensive time cost in communication than the full participation strategies 5 (55. In other words, the partial participation methods [8] 20 29]
only reduce the overall volume of information exchanged among the nodes, while the advantage of parallel communication enjoyed in full participation methods is damaged.
In this paper, we propose novel distributed minimax optimization method, called stochastic variance- reduced optimistic gradient sliding (SVOGS), which uses the mini-hatch client sampling to balance communication rounds, communication complexity, and computational complexity. We prove SVOGS simultaneously achieves the (near) optimal communication complexity, communication rounds, and local gradient calls for convex-concave minimax problem under the assumption of second-order similarity. We also conduct numerical experiments to show the superiority of SVOGS.
2 Preliminaries
We focus on the distributed optimization in client-sever framework for solving minimax problem ( The notation fi presents the local function on the i-th node. We assume the function fi is located on the server and the other individuals are located on clients. We stack variables E RRd and E Rd, as the vector z = [2; y] E IRd, where = d, + dy. We let Z == x y C Rd and define the projection operator (v) == arg min z || - w|l for given E Rdd We also denote the vector
functions F; _ + Rd and F: Rd R2d as
[()))= = [ V fz ff((
1 n
and F(z): := Σ (((2).
We consider the following common assumptions for our minimax problem.
Assumption 1. We suppose the constraint set Z C Rd is non-empty, closed, and convex.
Assumption 2. We suppose the constraint set Z C Rd is bounded by diameter D > 0, i.e., we have ||=, 22| D for all 21, 22 E Z.
Assumption 3. We suppose each local function f. Rdd xRdy + R is smooth. i.e., there exists L 0 such that (21) - F.(22)ll < L || - zell for all E [n]] and 21, 22 E Rdd
Assumption 4. We suppose each differentiable local function fi ; Rdd x Rdy + R is convex-concave, i..., we have fa(x, y) 2 fa(a', (a',v) + (V.Isaa'' .v), x - x²) and fi(w) S f(v') + (VyJi(y'), ) v/)
for all i E [n]. x, x' d and y. v E 1d..
2

---

Assumption 5.
We suppose the global objective f R x R - IR is strongly-coovex-strong concave, ie., there exists
O such that the function f(x, v) | Ilvll is convex-concave.
Besides, we introduce the assumption of second-order similarity to measure the homogeneity in local functions S 8 19 20
Assumption 6. The local functions fi...., fu Rd, x RR li are twice differentiable and hold the 5-second-orde similarity, i.e., there exists 8 > 0 such that
[[ - 4 {(r,))| 58
for all i [n], Rd and y Rd
We measure the sub-optimality of the approximate solution (z, y) Z by duality gap, that is [xx', (xx',)) v).
Gap(æ, max (x, v/) min y'Ey
''EX
We also consider the criterion of the gradient mapping for given 2 (x. y)
54 that is,
f+(;) 2 -=p===
where > 0. The gradient mapping f is natural extension of gradient operator F(z). Noticing that we have {+) F(z) if the problem is unconstrained (i.e., 2 = Rd), and the condition & (2) duality gap, the norm of gradient mapping is a more popular measure in empirical studied since it is
is equivalent to the point is a solution of the problem. Compared with the
easy to achieve in practice.
For the specific the square of Euclidean distance to the unique solution =x (2r, y) 2, that
case, we can also measure the sub-optimality by
|| = || = || x 1| + 1 y
Moreover, we use notations (-)), (.) and (2(-) to hide constants which do not depend on parameters of the problem, and notations (-),, 6(.), and (2(-) to additionally hide the logarithmic factors of n,
T., l and
3 Related Work
For convex-concave minimax optimization, the full batch first-order methods 24
33 34 38
51] can achieve e-duality gap within at most OLDD2 /s) iterations. Applying these idea to distributed setting naturally leads to the communication rounds of O(LD²/s) /s) and each round requires all of the n nodes compute and communicate their local gradient.
In seminar work, Beznosikov et al. (5] proposed Star Min-Max Data Similarity (SMMDS) algorithm. which additionally consider the second-orders similarity (Assumption 6 by involving gradient sliding technique 27 455 The SMMDS requires communication rounds of (8 /s), which benefits from the homogeneity in local functions. Each round of this method needs to communicate/compute the local gradient of all n nodes, and perform the local updates on the server within Ó(L/ō log(1/ag local iterations, which results the overall communication complexity of O'n /E) and local
gradient complexity of ((rō + L)D² log(L/E)). Later, Kovalev et al. (25) introduced extra- gradient sliding (EGS), which further improves the local gradient complexity O(nnö + D² is worth pointing out that the communication rounds of (() /s) achieved by SMMDS and EGS matches the lower complexity bound under the second-order similarity assumption [5]. However, these methods enforce all nodes to participate into communication in every round, which does not sufficiently take the advantage of finite-sum structure in the objective.
Recently, Beznosikov et which uses the variance-reduced clients participate into the communication in most of the rounds. The TPAPP can achieve point Rd such that (x)]I < for unconstrained case within the communication rounds of O(n8² D² /s).
proposed Three Pillars Algorithm with Partial Participation (TPAPP),
method [I [0] to encourage only one of

---

Table 1: The complexity of achieving B[Gap(a, 2) S in convex-concave case.
Methods
Commonication Rounds
Communication Complexity
Local Gradient Complexity
EG 2
LD2
mf.2
O a7.2
SMMDS X
( A.2
( mA
6 ())++ log :
EGS
0 ADD
0 (>AAp
O [ L)D
SVOGS
0 502
(n + .MAD2
Ö(n + (VR6+1))
log +)
(Algorithm
Lower Bounds
0 am2
22x + seap2
2(n + LVTA+LID
(Theorem
Table 2:
The complexity of achieving Bi|[ - 111 1 < e in the strongls-comvex--trongyy
which require the assumption of > n. *The complexity of TPAPP depends on local iterations number H, where "TPAPP (a)" and "TPAPP (b)" correspond to (F[L/(Vnd)) and H-[8 8 (gg(40mI./))) respectively.
concave case. "hhese methods use permutation compressors 49
Methods
Communication Rounds
Communication Complexity
Local Gradient Complexity
EG
24
O log t)
0 a log +)
0 a14 log +)
SMMDS 5
O log )
O uf log !)
① n6+L log )
EGS 25
0 log )
0 log 2
0 nd+1 log t
OMASHA 41
0 f log )
((n + 2/
log )
0 2 log 2
TPA 8
(((n vm
log !
((1n + yml
log !
(( + x + (.) log 2)
TPAPP g
(((n
x log +)
((n
log +)
((n + ن b) log +)
TPAPP (b)
3
(((n + v
log 2)
(((n+
vT log )
Ó((n v log )
SVOGS
0 log +
((I + yeid log +
Ö((n اااهكي log -
(Algorithm
Lower Bounds B. Theorem
a( $ log t)
a((n+ + w log t)
a((n+ + م log t)
communication complexity of O(n5² /c). and local gradient complexity of O & The theoretical analysis of TPAPP for the constrained problem requires the objective being strongly- convex- wwwtssttloooocccaaee In addition, we can also reduce the communication complexity by using the permutation compressors [49] for sigh-dimeniooall problem 4 g. which achieves the similar
complexity to existing partial participation methods [8]
We present the complexity of existing methods and compare them with our results in both general convex-concave case and strongly-convex boongllycovvex-stronngyyooooo -strongyy-concave case in Table
4 Stochastic Variance-Redueed Optimistic Gradient Sliding
We propose stochastic variance-reduced optimistic gradient sliding (SVOGS) method in Algorithm |
The design of our algorithm starts from reformulating problem T as follows
min max 1 n1
n Σ (fi(z,)) v) fz()))) (z,
(3)
zEX vEy
((x.)))
The idea of gradient sliding (27 on minimax optimization can be viewed as iteratively solving the
surrogate of problem (3) within the quadratic approximation of g(z, y) 5 25). Recall that the
AAlthough the complexity of TPAPP for achieving [+) < is established for the unconstrained
case, its analysis additionally assume that the sequences generated by the algorithm are bounded by 1) > 0 g Theorem 5.12].

---

Table 3: The complexity of achieving E y)1l S e in convex-concave case. The TPAPP
additionally assumes = I2 and the sequence generated by the algorithm is bounded by D 0.
Methods
Communication Rounds
Communication Complexity
Local Gradient Complexity
TPAPP
O nu
O 0
SVOGS
log )
mAD ((n+
log !
O(n+ (vin++ ve
log
(Algorithm
Algorithm 1 Stochastic Striaace-Reducee Optimistic Gradient Sliding (SVOGS)
1: Input: initial point 20 = (xx,2) ./) E 2, step size 17, accuracy {Ex KK
communication rounds K,
mini-hatch size b. probability p E (0, 1], weights a (0, 1);
2: Initialization: w =
w 20 (x", v²) E Z, 2! 20 for all i [n]:
3: for k = 0, 1,2, 2,.,.... K do
4: z = (1 7)2² + +
5: Sample S 1i ..... .bb , uniformly and independently from [n];
6: 8 = F( - Fi (w 1) + 1
Σ (B)(**) - Fi F=(=*) Fi 1)+ Fi Fi(wa=1)
jE8K
a
Σ (Fy(2h) Fi((a) F,(3 + 11(2=-1)))
b
JESt
7: 6 === t -
8:
Find a E Rd such that 1|ue - -th113 < Ek. where at is the solution of the problem
min max REX DEy
fi( + 2m
1| 2/
11 wyy 11
(2)
2n
9:
gk+l = wh:
w+1 { 1
with probability p.
10:
k
with probability 1- p.
end for
optimistic gradient descent ascent (OGDA) method [3 43 iterates with
1++1
Pz(2 17( (F + F( F(z
optimistic gradieni
where >> is the step size. is well-known that OGDA achieves optimal convergence rate under the first-order smoothness assumption 42 55), which motivated us construct the quadratic approximation of g(z, v) by using the optimistic gradient of g at (x* y²) in the linear terms, that is
g(x,v) v) = g( v)
=g(a*, x/²) + Vag(a ) + Vog(** )* vag(a 11 x
2²) +
||
x11
211
optimistic gradient with respect to
(5)
VVvol s y )²) V Vyg(**>
1/
y $12
2n
optimistic gradient with respect
Applying approximation (5) to formulation which iteratively solve the sub-problem
obtain the optimistic gradient sliding (OGS),
(x k+1 .8
K+1
sJ arg min max g(2, D) + fi 9) SEX gEy
(6)
5

---

We can verify function g(r, y) is 8-smooth under Assumption 6 which indicates taking 17 (11/)) and solving the sub-problem sufficiently accurate can find an E-suboptimal solution within the iteration numbers of O(8D2// /E) and ((8/ulog(1//) for the convex-concave case and the strongly- sonve--strongly-conens
case respectively (see Section (5). 'he dependence on å implies OGS benefits from the second-order similarity in local functions, while each of its iteration requires the communication and the computation of the exact gradient f(r, y) within the complexity of O(n).
The key idea to improve the cost each iteration is involving the mini-batch client sampling and variance reduction with momentum 2 26 Specifically, we estimate the optimistic gradient in formulation (5) as follows
G(**) G(=") G(2-)))
Σ (((w-))+GGs(e JESN
-G(("))))() Gy(w aaG)(=*) - C,
8
momestuna DenM
where G(z) :- F(z) F((+), S* S [n]] is the random index set, w is the snapshot point which updated infrequently iterations, and a (0. 1) is the momentum parameter. Applying the optimistic gradient estimation (7) to formulations (6). we achieve our stochastic variance-reduced optimistic gradient sliding (SVOGS) method (Algorithm) T.
The proposed SVOGS enjoys the mini-batch partial participation in the steps communication and computation in most of rounds, which is the main difference between SVOGS and existing methods 5 8 26]. Concretely, taking the mini-batch size |s @(vn) ) for SVOGS can simultancously balance communication rounds, communication complexity and local gradient complexity. The SVOGS keeps both the benefit of parallel communication like full participation methods (i.e., SMMDS (5] and EGS (25) and the low communication cost like existing participation methods (i.e., TPAPP (8). Additionally, the communication advantage of SVOGS also makes the algorithm achieves better local gradient complexity than sute-of-thhearty aate 5 26].
The Complexity Analysis
In this section, we provide the complexity analysis of proposed SVOGS (Algorithm I to show its superiority. In particular, we let μ = 0 for the convex- convex-concave case to the ease of presentation.
We analyze the convergence of SVOGS (Algorithm
[
by establishing the Lyapunov function
th
7
1
|| * - ==1 + 2(F((*=1) F1(22-1)= F(2*) + Fi(e*),
17
2
(8)
1 64r)
11
=² 112
f| 11 (2 + nn4) 4n)
2
1| =²11?,
2pm
where we take weight 7 S 1/8 and the step size S 1/(25)) which always guarantees th 2 0 by using Young's inequality and the similarity assumption (see detailed proof in Appendix B).
We show that the decrease of Lyapunov function in expectation as follows.
Lemma 1. Suppose Assumptions 7 f and with 0 < 6 L, running SVOGS (Algo- a = max {1 - 7p/(6() - -7)), pnuu + +n)) y <
rithm 7 with n S min 1//, 1/8. 25 (b + 1)/b S a, 41y6 /b S a44(4)), and E S c- min { || - 111 1|at x ||3}
for some e = poly(u, 6), then we have
E +1 E1 < max {1- {1-
(1-
7/4
-
pdda
E[
E [[Ia**
E [llw*
17
6(1 7)" 27 + mp
167
2m
(9)
5.1
The Convex-Concave Case
For the convex-concave case, we use Jensen's inequality and the convexity (concavity) to bound the duality gap at u Σk-1 nt as follows
K-1
( < max
(f(u v/) f(x', ,,,,))))
S max #E2
1
Σ u( 2). (10)
(z E K
K
K=
k=U

---

Applying Lemma 1 by summing over inequality
9 we can bound the right- hanht-hand&e side of (O) via the =+11)), and achieve the following theorem.
terms of > k= E || af [|²] and Σ K
k=
-
E
[||w*
Theorem 1. Suppose Assumptions 7
2
and hold with 0 < å < L and D > 0. we
run Algorithm|] ! with
[vn]] 1.
p
l/ 8), oi = min { //b/(44), 1/(3)))))) * 11 for some Ç - poly (L, 6, n, D, 8) and
a = 1, and Ex min { min {lla II1
11
= poly(o). Then we have
K-1 E(F(w"). 2) #E2 K
10D2
E +
K K-1
Σ k==
max
1
where u Uavg
nk
2
K
k=0
Theorem 1 shows we can run SVOGS with step size 7 = ((1/6) and communication rounds of K (oD/E) to achieve the e-sub-optimality in expectation. Additionally, each communication round contains the expected communication complexity of 6(1 p) - np = O /n) ), leading to the
overall communication complexity of O(n + D2
The sub- sub-problem 2 in SVOGS 8f Algorithm I minimax problem with + 1/n) 1/n)-mmoothhh smooth and -i-sstongyy-ooovee... (aanivex-(1///) (tto/nn)srroonyycooo coongvy objective. Therefore, the setting of εş and r in the theorem indicates the condition ||u* - á² 1|2 S Ex: can be achieved by the local iterations number of O(LL + 0) log(Ex)) = ÓLL/6 log(1/s)) on the server (c.g., use EG (24)). Additionally, each round of SVOGS contains the expected local gradient complexity of b(1 p) + np O(vn) ) to achieve the (mini-batch) optimistic gradient o². Hence, the overall local gradient complexity of Ö(n + (vnō D) / (1)() We formally present
SVOGS is ((((Vn To/6lo(( the upper complexity bounds of SVOGS for the convex-concave case as follows.
Corollary 1. Following the setting of Theorem 7 we can achieve E|Gap (v S e within commu-
nication rounds of (6 /E), communication complexity of On + vnó /E), and local gradient complexity of Ó + (vnó + LyD3// log(1/E)), where u 2k= u
K-1
5.2 The Strongly- Sanplly-Connn -oo--oee--ttoogly-Coooee
Case
By appropriate settings of SVOGS, Lemma leads the following linear convergence of our Lyapunov function in the strongly-convex concave case.
Theorem 2. Suppose Assumptions
and hold with 0 < μ $ 8 < L, we run Algorithml with
b [mn (vT, 6/ = p= min Vn, 0/m} 8), n min { Vayb// (48), 1/(3))) }.
max {1 (6p - 7)), pu/((2 + mp)), and e c-l min {1] 11, 11 2* [1]] for
some poly(H, 8). Then we have
K
| < max 1
T/14
1
piu
40
6(1 7)
2y + mp
We then apply Theorem 2 with K = (66/ and analyze the complexity like the discussion after Theorem which results in the upper complexity bounds follows.
Corollary 2. Following the setting of Theorem 2 we can achieve E [|I= =11]]] S e within
communication rounds of (8 / log(1 /e)), communication complexity of (0((((n++n)))) log(1/e)), and local gradient complexity of Ö((n + (Vrō L)/n) log(1/s)).
5.3 Making the Gradient Mapping Small
For the convex-coneave case (under the assumptions of Theorem small gradient mapping by solving the regularized problem
D. we can achieve the points with
X || x 10
> Ily y01
min max f(x, v) = [(x, y) + 2 FEX yEy
(11)
2
for some À > O. Noticing that the function f(x, y) is (L + A)-smooth, >-strongly-convex-.. X- strongly-coneave and 8-similarity. Then Corollary 2 implies running SVOGS (Algorithm 1 by iterations number K O(6D/ VeDD/V/logL///// to solve problem (11) with X O(VE/D) can
7

---

achieve B||| BII S E, which results in the complexity shown in Table For the strongly-
convex-stronglyy-omme case, the complexity of achieving = (1 S
nearly matches the
complexity of achieving E[Il** 2"1 [| I e. We defer the detailed derivation for these results of making the gradient mapping small to Appendix
The Optimality of SVOGS
In this section, we provide the lower complexity bounds for solving our minimax problems by using distributed first-order oracle (DFO) methods. The class of algorithms considered in our analysis follows the definition of Beznosikov et [8) which is formally described in Appendix [D] Compared with existing lower bound analysis for second-orde ooder similarity only focusing on communication [S] 8), we additionally study the computation complexity by considering the local gradient calls. The results in this section imply the complexity of proposed SVOGS (nearly) matches the lower bounds on the communication rounds, the communication complexity and the local gradient calls simultaneously.
6.1 The Lower Bounds for Convex-Conent Case
We first provide the following lower bounds for convex-concave case.
Theorem 3. For any 0 < & I, 3, D > and & S (D2/(12/2)) there exist T-smooth and convex-concave functions fi,..., IRd x gdy with 8-second-order similarity, and closed convex set Z X' x y with diameter D. In order to find an approximate solution 2 = (z. y) of problem 4 such that [[Ga((z)] I E. any DFO algorithm needs at least M(&D2 /e) communication rounds.
Theorem 4. For any 0 < 6 < L, n 2 2, D > and S. 8D2 ((16/2n) ), there exist L-smooth and convex-concave functions JI,...,Ja Sn
Rd x Rdy with 5-second-order similarity, and closed convex sel Z X y with diameter D. In order to find an approximate solution z = (xr,y) of problem 77) such that [[]ap(==]] S s, any DFO algorithm needs at least 2(n + /no /e) communication complexity and Q2(n vn /e) local gradient calls.
The lower bounds on communication round and communication complexity shown in Theorem 3add
match the corresponding upper bounds of SVOGS shown in Corollary [ However, the lower bound on local gradient complexity shown in Theorem 4 only nearly matches the result of Corollary in the case of /no (L).. Therefore, we also provide the following lower bound on local gradient complexity to show the tightness of dependence on the smoothness parameter L.
Lemma 2. For any L > n, > O and e < 8D2/(AV2) there exist L-smooth and comeex-concave functions fa....,fa Rds x Rdy with 8 b-second-order similarity, and closed convex set Z X' y with diameter D. order find an approximate solution (I.y) of problem (7) such that E[Gap(z)] S e. any DFO algorithm needs at least Ω(n + LD2 /E) local gradient calls.
Combining the results of Theorem 4 and Lemma we achieve the following lower bound on local gradient complexity, which nearly matches the corresponding upper bound shown in Corollary [
Theorem 5. For any 0 < 8 < n2
0 and S 8D2 (166 there exist L-smooth and comvex-concave functions fa...., fn Rds x Rdy with 8- 5-second-orde similarity, and closed convex set Z X' y with diameter D. In order to find an approximate solution z = (xx y) of problem (7) such that E[Gap[z)] < any DFO algorithm needs at least Q(n + (Vnō + L)D /E) local gradient calls.
The constructions in our lower bound analysis is based on the modifications on the blinear functions provided by Han al. [14), which are originally used analyze the minimax optimization in non- distributed setting. We provide detailed proofs in Appendix E In related work, Beznosikov et al. [5] also provide the lower bound 12 (matching the result of Theorem 3 for communication rounds by using the regularized function, which is different from our construction in the proof of Theorem 3 addition, our lower bounds on the communication complexity and the local gradient complexity shown in Theorem and 5 are new.

---

10"
10"
10
SMMDS
SMMDS
SMMDS
Gradiere Mapping
Grodiers Mapping
Gradiers Manping
10-2
10-
10
TRAPP
TRAPP
TPAPP
SVOGS
20
10
10
10
10
10
Communication Rounds
Complexity
Local Calls
Figure 1: Results for convex-concave minimax problem 12 on a9a.
10
10-2
10
SMMDS
SMMDS
SMKDS
10
TRAPP
2.10-
TPAPP
-00
TPAPP
100
N10
110
10
10-a
10-4
10000 Communication Complexity
25000 100000
Communication Rounds
Gradient Calls
Figure 2: Results for stronfyy-oovee--toonyyy-oooeee minimax problem on a9a.
6.2 The Lower Bounds for
Case
The tight lower bound on communication rounds in moangly-covvex-stonnnyyyyy provided by Beznosikov et al. [5] Theorem 1]. We present the result as follows.
case has been
with L 2 max(p, (p, ò} and 2 3, there exist L-smooth and convex-concave functions fi,...; fn Rdd xRd with d-second-order similarity such that the function f(x, y) = Ei= fi(x, is possronngyycoovve----sttooo satrongly-concave. conccvvee. In order to find a solution of problem D such that Bi[l= =1] < e, any DFO algorithm needs at least 215/p log(1/e) communication rounds.
Theorem 6 (55). For any μ.
The tight lower bound on communication complexity has been provided by Beznosikov et al. [.. We follow their construction to establish the lower bound on local gradient complexity, nearly matching the corresponding upper bound of our SVOGS. We formally present these lower bounds as follows.
Theorem 7. For any μt 5, L 0 with L 2 (,, and 2 2, there exist L-smooth and convex- concave functions f1,..., fa Ted. Rdd with 5-second-order similarity such that the function f(x,y) Ei f((x, y) is
In order to find a solution of problem such that -[1|===11] < e, any DFO algorithm needs at least D (n(++ /nd p.) log(1/e)) communication complexity and 12(n + (vnō L) p/) (og)) local gradient calls.
7 Experiments
We conduct the experiment on robust linear regression [5 15 constrained convex-concave minimax problem
35
Concretely, we consider the
N
min | S R_
(a, + b.)2
(12)
RR
2N
and the unconstrained strongly
eroogll-coovvexe convex convex-stronlly concave minimax problem
A
3
min max 2N
(a, + b.)²
| llv112
(13)
ZER yERR
where contains the weights of the model, describes the noise, and {(as, N is the training set.

---

100
13
10
10
10
Grademt Vacc0mn
Gradent Merrding
20-10
BG
14011)
20-10
SHHDS
SHIDSS
SHYDS
10-12
EG5
10-12
EG5
10-11
805
T7/p0
500G5
10'44
SyDeS
TRAFF
30-14
TRUPP
SVOGS
20
60
50
100
2000 10030
13000
20003
2030:
40000
60000
00003 100030
Figure 3: Results for concavee minimax problem (22 on w8a.
56
EG
10
SMHOS
30
SVMOS
70
SHYDS
ECS
EG5
EC5
TRAFF
TRAF
10
5VOE5
10-1
SVDOS
20
5VOES
10
5353 10000
25000
20000
4:000
acéco 10000n
Figure Results for srongl--omeee-sttnggyyyoomee minimax problem 13 on w8a.
We compare the proposed SVOGS (Algorithm) D with baselines Extra-Gradient method (EG) 224 Star Min-Max Data Similarity algorithm (SMMDS) [5], Extra-Gradier Sliding (EGS) 25 and Three Pillars Algorithm with Partial Participation (TPAPP) B We test the algorithms on real- world datasets "a9a" (N 32, 561, d' 123), "w8a" (N 49, 749, d' 300) and "covtype" (N = 581, 012, = 54) from LIBS VM repository [9] and set the nodes number n = 500. For set R, 2 and R, 0.05, respectively.
problem
We implement all the methods by Python 3.9 with NumPy and run on a machine with AMD Ryzen(TM) 7 4800H core with Radeon Graphics 2.90 GHz CPU with 16GB RAM. We solve the sub-problem in SVOGS (Algorithm[)) []. SMMDS [5] EGS 255. and TPAPP (8) by Extra-Gradient method of Korpelevich (24). We tune the step-size of SVOGS from {0.01, 13. The probability p is tuned from (po, 5po, 10po). where po = min v
6/u). The batch size determined from [Lbu/10], [6o/5], [bu] J. with by = 1/po- We set the other parameters by following our theoretical analysis. We set the average weight as 7 = p. For the momentum parameter, we set a = 1 for convex-comcave case and
max(1 n// (6(1 7)), pmp/(22 + nu)) for strongly-convex- strongly-concave case, where we estimate μ by max (X, 3} for problem (I3). For the sub-problem solver, set its step-size according to the smoothness parameter of sub-problem, i.e., 1/(I 1/n)- In addition, we estimate the smooth parameter I. and the similarity parameter 8 by following the strategy in Appendix C of Beznosikov et al. 5
We present the experimental results in Figure to for datasets "a9a" and "w8a". The results for dataset "covtype" is displayed in Appendix H due to the space limitation. We can observe that our SVOGS outperforms all baselines in terms of the local gradient complexity. Additionally, the SVOGS requires less communication rounds than classical EG and existing partial participation method TPAPP, and it requires significantly less communication complexity than full participation methods EG, SMMDS and EGS. All of these empirical results support theoretical analysis.
8 Conclusion
This paper presents a novel distributed optimization method named SVOGS, which use the second- order similarity local functions and the finite-sum structure in objective solve the convex-concale minimax problem within the near-optimal complexity. Our theoretical results are also validated by the numerical experiments. future work, it is interesting to use our ideas to improve the efficiency of distributed nonconvex minimax optimization under the second-order similarity.
10

---

Acknowledgments and Disclosure of Funding
Luo and Zhou supported by the Major Key Project of Pengcheng Laboratory (No. PCL2024A06).
National Natural Science Foundation of China (No. 62206058), Shanghai Sailing Program (22YF1402900) and Shanghai Basic Research Program (23JC1401000), Ye is supported in part by the National Natural Science Foundation of China under Grant 12101491 and in part by the National Key Research and Development Project of China under Grant 100202..
References
[1] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In Conference on Learning Theory, 2022.
[2] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1555 2018.
[3] Yossi Arjevani and Ohad Shamir. and optimization. Advances in Neural Information Processing Systems, 2015.
Communication complexity of distributed convex learning
[4] Aleksandr Beznosikov and Alexander Gasnikov. Compression and data similarity: Combination of two techniques for communication-efficin solving of distributed variational inequalities. In International Conference Optimization and Applications, 2022.
[5] Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Dis- tributed saddle-point problems under data similarity. Advances in Neural Information Processing Systems, 2021.
[6] Aleksandr Beznosikov, Pavel Dvurechenskii, Anastasiaa Koloskova, Valentin Samokhin, Se- bastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gan attra-gradient for variational inequalities. Advances in Neural Information Processing Systems, 2022.
[7] Aleksandr Beznosikov, Peter Richtárik, Michael Diskin, Max Ryabinin, and Alexander Gas- nikov. Distributed methods with compressed communication for solving variational inequalities, with theoretical guarantees. Advances in Neural Information Processing Systems, 2022.
[8] Aleksandr Beznosikov, Martin Takác, and Alexander Gasnikov. Similarity, compression and local steps: three pillars of efficient communications for distributed variational inequalities. Advances in Neural Information Processing Systems, 2023.
[9] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
[10] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient. Advances in Neural Information Processing Systems, 2019.
[1I] Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference Artificial Intelligence and Statistics, 2021.
[12] Bahman Gharesifard and Jorge Cortés. Distributed continuous-time convex optimization on weight-balanced digraphs. IEEE Transactions Automatic Control, 59(3):781-78, 2014.
[13] Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, 2021.
[14] Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. Journal of Machine Learning Research, 25(2):1-866 2024.
[15] Hadrien Hendrikx, Lin Xiao, Sebastien Bubeck, Francis Bach, and I Laurent Massoulie. Statisti- cally preconditioned accelerated gradient method for distributed optimization. International conference machine learning, 2020.

---

[16] Charlie Hou, Kiran K. Thekumparampil, Giulia Fanti, and Sewoong Oh. Efficient algorithms for federated saddle point optimization. arXiv preprint:2102.06333 06333, 2021.
[17] Adam Ibrahim, Waiss Azizian, Gauthier Gidel, and Joannis Mitliagkas. Linear lower bounds and conditioning of differentiable games. In International conference on machine learning. 2020.
[18] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji. Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. Foundations and trends@) in machine learning, 14(1-2):1 12200,0 2021.
[19] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In International conference on machine learning, 2020.
[20] Ahmed Khaled and Chi Jin. Faster federated optimization under second-order similarity. In International Conference on Learning Representations, 2023.
[21] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local GD on heterogeneous data. arXiv 1reprint:1900004770 2019.
[22] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, 2020.
[23] Seung-Jean Kim and Stephen Boyd. minimax theorem with applications to machine learning. signal processing, and finance. In IEEE Conference Decision and Control, 2007.
[24] Galina M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[25] Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to optimal distributed optimization under similarity. Advances in Neural Information Processing Systems, 2022.
[26] Dmitry Kovalev, Aleksandr Beznosikov, Abdurakhmon Sadiev, Michael Persiianov, Peter Richtárik, and Alexander Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. Advances in Neural Information Processing Systems, 2022.
[27] Guanghui Lan. Gradient sliding for composite optimization. Mathematical Programming, 159; 201-235, 2016.
[28] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg non-iid data. International Conference Learning Representations, 2019.
[29] Dachao Lin, Yuze Han, Haishan Ye, and Zhihua Zhang. Stochastic distributed optimization un- der average second-order similarity: Algorithms and analysis. Advances in Neural Information Processing Systems, 36, 2024.
[30] Luo Luo, Cheng Chen, Yujun Li, Guangzeng Xie, and Zhihua Zhang. A stochastic proximal point algorithm for saddle-point problems. arXiv preprint: / /909.06946, 2019.
[31] Luo Luo, Guangzeng Xie, Tong Zhang, and Zhihua Zhang. Near optimal stochastic algorithms for finite-sum unbalanced convex-concave minimax optimization. arXiv preprint:2106.01166 2021.
[32] Grigory Malinovsky, Kai Yi, and Peter Richtárik. Variance reduced ProxSkip: algorithm, theory and application to federated learning. Advances in Neural Information Processing Systems, 2022.
[33] Yu Malitsky, Projected reflected gradient methods for monotone variational inequalities. SIAM Journal Optimization, 25(1):502-520 2015.
12

---

[34] Yura Malitsky and Matthew K. Tam. A forward- barkwdd splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization, 30(2):1451-1422, 2020.
[35] Ulysse Marteau-Ferey, Francis Bach, and Alessandro Rudi. Globally convergent newton methods for ill-conditioned generalized self-concordant losses. Advances in Neural Information Processing Systems, 2019.
[36] Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. ProxSkip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference on Machine Learning, pages 15750-15769. PMLR, 2022.
[37] Aritra Mitra, Rayana Jaafar, George J. Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 2021.
[38] Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15:229-251, 2004.
[39] Yurii Nesterov. Dual extrapolation and its applications solving variational inequalities and related problems. Mathematical Programming, 109(2)3119334, 2007.
[40] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
[41] Ivano Notarnicola, Mauro Franceschelli, and Giuseppe Notarstefano. A duality- -baeed approach for distributed min-max optimization. IEEE Transactions on Automatic Control, 64(6):2559- 2566, 2019.
[42] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-coneave bilinear paddle-point problems. Mathematical Programming, 185(1):1-35, 2021.
[43] Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845-848, 1980.
[44] Meisam Razaviyayn, Tianjian Huang, Songtao Lu, Maher Nouiehed, Maziar Sanjabi, and Mingyi Hong. Nonconvex min-max optimization: Applications, challenges, and recent theoreti- cal advances. IEEE Signal Processing Magazine, (55): 66, 2020.
[45] Alexander Rogozin, Alcksandr Beznosikov. Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. arXiv preprimt:2022.07733 2021.
[46] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-efficien distributed optimization using approximate newton-type method. In International conference on machine learning, 2014.
[47] Sebastian U. Stich. Local SGD converges fast and communicates little. preprint:885.. 09767, 2018
arXiv
[48] Ying Sun, Gesualdo Scutari, and Amir Daneshmand. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. SIAM Journal on Optimization, 32(2):354-335 2022.
[49] Rafat Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint::11100033000 2021.
[50] Ye Tian, Gesualdo Scutari, Tianyu Cao, and Alexander Gasnikov. Acceleration in distributed op- timization under similarity. In International Conference on Artificial Intelligence and Statistics, 2022.
[51] Paul Tseng. A modified
splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431-444 2000.
13

---

[52] Panos Xidonas, George Mavrotas, Christis Hassapis, and Constantin Zopounidis. Robust multiobjective portfolio optimization: A minimax regret approach. European Journal of Operational Research, 262(1):299-36)) 2017.
[53] Guangzeng Xie, Luo Luo, Yijiang Lian, and Zhihua Zhang. Lower complexity bounds for finite-sum convex-concave minimax optimization problems. In International Conference on Machine Learning 2020.
[54] Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A catalyst framework for minimax optimization. Advances in Neural Information Processing Systems, 33:5667-5678, 2020.
[55] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1):901-935, 2022.
[56] Yuchen Zhang and Xiao Lin. DiSCO: Distributed optimization for self-concordant empirical loss. In International Conference on Machine Learning. 2015.
14

---

Appendix
The appendix contains additional details supporting the main text. Section A starts with basic results. Section[B] shows the non-negativity of our Lyapunov function. Section C provides the proof of upper bounds for the proposed method. Section D formally defines the algorithm class in lower bound analysis. Section [ and provide the lower complexity bound for both convex-concave and monnngly-coove--ttonnglly gradient mapping small. Section H presents more experimental results.
cases. Section demonstrates the complexity of making the
Some Basic Results
We introduce the following lemmas for our later analysis.
Lemma 3 (Lin al. [29 Proposition B.IJ). the local functions .i....;la RRds Rdv + R hold
the ô-second-orler similarity, then each (F: - F) is Ö-Lipschifz continuous, i.e, we have
[I (21) - (F: (22)) S 81|21 22
for all 21; 22 Rd and E [n].
Lemma 4 (Alacaoglu and Malitsky [1] Section 8)). Let F (Fr) be a filtration and {r²} } be
a stochastic process adapted to F with E[r R+1 [F = 0. Then for any K E N, x. E 2, and any compact set C Z, have
K
K
E
max
x)
S max ||00 #EC 2
REC
2
k=
R=0
In related work, Beznosikov et al. 8 Assumption 4.3] considers the following second-order similarity assumption that is slightly different from our Assumption Assumption 7. The local functions fi...., .n Rd x dy IK are twice differentiable and hold the saaverage-second-ee similarity, i.e, there exists > 0 such that
for all x E Rdd,, Rdd, and j E [m]..
We present the relationship between ô-average-secood-oordd similarity (Assumption 7 and d-second- order-similarity (Assumption 6
Proposition 1. For twice differentiable local functions fi...., fn IR x Rd + R, we have
If functions {fr hold the ō-average-secnn seaegee-econd--oode similarity, then they also hold the 8-second-
order similarity.
functions ( hold the 8-second-order similarity, then they hold the 25-average-second order similarity.
Proof. If functions (fi) hold the d-average- similarity, then for all j E [n]) we have
|V f(x,v) =
fzr, - f2 v)
(z,)(Iz)) fz, v) 1 80
n
where we use the convexity of 113. This implies functions {f also hold the 5-second-order similarity.
functions (f1) hold the å second-order similarity, then for all j E [m], we have
V (z, - (²,i(vl))
n
f3(2, v) (116::/)))V///,...33333+V/7/ v²,((,,)) s (28),,
n
15

---

where we use the Young's ss inequality for the matrix 2-norm. This implies functions {fi)-= hold the av-aaage-seecod-ordd similarity.
B
The Non-Negativity of Lyapunov Function
Our convergence analysis is based on the following Lyapunov function
1
+ 11 2=11 + 2(F((= - F1(2h-1) - F(z²)) + Fi Fi(t)), 2 -2 2=
L 2
7 I - 2 +112+ (2 + THH)
1
* 11
+
2pm 11 - =1-
64m
2n
Noticing that we can always guarantees & 2 by taking 7) S 1/(320), because the Young's inequality and Lemma 3 iidiicates
t 1
?
1|2 ==1
1
|F(=
((==-1)
Fi((=-1) - F(=*) + (=*))11
64n8
1
6470²11 11
-1-h 12 +
112
- z²a 11=
641
1 ? ||=# f=--2"1 =11
1
8² ||
- 64 -1 =01/2
1
|| 1
1)
64n02
64m
Z 2m
(1 12817
zz 2 2 0,
where we also use 7 S 1/8.
C The Proofs for Upper Complexity Bounds
We provide the proofs for results in Section 5
C.1 Proof of Lemmal
In later analysis, we denote [+[[]] as the expectation with respect to the random sampled set & in round & and denote 1/+1//2|]] as the expectation with respect to the random update of the snapshot point w in round k. Specifically, we take the constant
c c: 10=100+ + 64m62
204887282 + 96n/ + 64y /4 2
(14)
for the statement of Lemma 1
We first provide several lemmas that will be used in the proof of Lemma] Lemma 5. Under the setting of Lemma we have
!
2E [18+= E,(50%, ttt
4n52
4nooa² E [112* 211]
E [llat 2*113]-
+
E E112* -
11-1
27
b
b
and
2E (0 Fi(aa) F(z"), t - =-7}
<
25
E |||a*
ut 112] + E [||a* 2²11 22plE [||a* -1=
1
E *112** 1
|13]
/
64n
+ 6646
2
[||a" - -\]13] 2E [(F(2*) F1(²*) =(25+1) Fi
Fi (+1),, 2h1 2n)]
1
+ 4n
E ||| - - + 41p52 [||=* - (.-1113)
2alE [(F(=*) -Fi F(2 (1= + Fi ( "), -2")]
16

---

Proof. Firstly note that
Es |0 - - Fi ( F + Fi ()
According to the uniform and independent sampling and Lemma 3 we have
E |110* Ea Ex(o"]11]] S 21E
Σ
- (F(==) =((o
JESH
a
-3y(( - (F(*4) -B(((t) - - F((h-1))
+ 2E
b
JESU
2 E
Σ (FF)((*t) - Fy(w(-1)) -F)((t))))))))))
- (F((t) - F(wx -
6²
JES
2a²
+ 6
E
Σ [1(g)(+t) - 15((--1)) - (F(**)
F(2 11
JESt
2 IF
Σ
((B((*))- - F5(( -F)(x-1)))))))))) (F(=*) - F F(u)
S nb
2a
+ nb
E
Σ (1((((=))) 1)(+ (F((*) F( f(=*-1))]1
5=1
25
2
- b
E
||
x
113 +
E ||| -
According to the above bound on E. [[|5* R& 1 [[1]] we achieve the first result as follows
2E [(8* Ex[0"1, atth - }
s E [llat - [1]] + 21y [115* T& [ [|3]
217
$ E - 1| + 4n0² || w 11] +
4no²a² b
E [1|
1
21
Again using Lemma
3 we achieve the second result as follows
2E [(E + (itt F(x*), at 2²)]
-22E [(F(=*) - Fi (2*)) + (F( - -F) (x²)) -F(t)))))
- at - =
F(=
[(F - F( -z")]
--21E [(F(xd)) Fi( F(iT) +Fi(Et), att - 2 2E (F(at) F(2²)()))))))))))))) 8t 10---"2) =²
2E -2F((F(=*) - (1 - F(aht)+ + Fi(sttl), 1), /t - |
-EE((((=A) - (= - F(2)+1)+ + +Fi(ghtl) ) }²
20E [KF(2*) - f1 1(= (1) *
2&E [<F(=)) - F=(x - F(2"11 + F1 k- (1)), 1),²²² - =>
28
EE [llat - -²'1 + " [|aa - x² 20] - 2n [llat - xx" 11] +
1
E [||2* - =² A+ [1
64n
+ 64 [l|ā* - [2] 21E (FF(2 - Fi (2*) - F( + Fi
k ++1 2, - 2")
+ 1
F. [|I=* - |13 + 41 [|| - - [|2]
4n
2aE [(F(**) - (1() - F(** + F
F1(2* (2* x (22x~1), -
17

---

Lemma 6. Under setting of Lemma L we have
[11a* -x11 - 1E [l [[-1]]]
3/1 2
[lIi* - =1]
817
1
E []1:/*
- -
1 E [1|=601 - [1]]
+ -1
(3)) + 3/0 E [1] [1 u/ [1]
167
32n
8n7
2 E [Ilus* =0-]
7
E [11e** - الم [11 - 1=]
21
4n)
Proof. From the facts ||a + b112
2 211a|12 ||1112 and l|aaa + Bll2 2 ||a||2 3/1b11. we have
E [1
= 11] - 167
[l =* $1]
E [|| - - 1|] + 167
E
[l
- u 11]]
8n
32n
-I [lle**
-i/9113] S
?
E [||c* - si 11-
Y E [llur 11]] +
TE
[l 111
21
4n
2n
7
E 1110*
- a0-1/1
I E [lke - 1|2 +
E [l|a* - w²a 11.
217
4n
1677
and
3/1
E [lla** - -20113] S -uIE [||akt| - -20113 + 3ul [lla* - u²a 1/1
2
where we use the setting S 1/8 in the second inequality.
Lemma 7. Under setting of Lemma we have
E [11**1] k+1 - =1] + 2E -F(())-Fi((") ) - F(s*+1)
+ Fi (2 2 - 2*)]
2
[lwe* - 2 1|]] + 7 2/11 E [|| k+1 [|]
[[1a 1²1 + "E
E
64m
4n
pm
1
E |||a* 2=1 + 2alE (F( (1= F2 12(22111 F( F1 (2
(z*), )) ,² 2">
"
E [||=*
-
+
41j0"
E [||w-=1-><11]] 16n
211
1
E
[|| t a 11]
64n
7
28
+ 64no²
-3p
E !lli* -u²(1?)
+ 2B
|||i*
n²
||||= - -2"11
817
17
(7 mm))
Hld
E [1|00* - =1]
2 [l|w* - 21
27 + TJ2
pm
- 2m
Proof. The optimality of a implies
(nF) + ah - 2- - (x
- 2 0.
(15)
Combine equation 15 with the update rule Line of Algorithm I [and (-7F(x²),, - aat) 2 0.
we achieve
(2 at - mntt at - =²) 5 =²0)
- F((=), - =2²).
(16)
17
18

---

Using the result of equation
T6]. we have
2
1/tt
2²1
2
k
2
2
+
2k att - -2") | - 12
77
"
2y
||
z" 11
+
(w
2,, at - x²) - 2 att -2-)
7
2
11tt
11
(
at n0 att -2
27
11 k x" 2 +
(w*
2, 4t - -²²)- -2(8 at - -(²-
11
11t - 2* 21 - 2(F2 - =F 2²)
11 101 11 + 2 1l1o - -2²12- 2 11o0 aat113 2 112 201
11
11
11
1 7 11a 112 - -2(0 - -Ex 10 aatt 2t + 2 2²))
160 + Fi (itt) - F(="), at - 2²)
Taking the expectation on above result and using the fact
E 118 - -E216"1, 2t - -=>>| = E E& (8+ - Ex1001,22 - -=*}]| = 0,
we obtain
E |1aa - =1 S E
11a x²112 + - 1100* - - I1 - -11-112 - $12# ==1??
1111**
- 11
1 ? 1/th - 20113 - 2E [66t - Ex 1001,,,00 att - )
(17)
1
2E
[[Ex10*] - Fi Fi(1))) - F(("),,00 āth - 2²)]
Applying Lemma 5 to bound the term 2 [(8* R2x (54), att - > in equation 17 we obtain
E
[1
- 2" [[]
17
> ==113= + 2 1/ - =111 - 2 - 2110²* - -ah112 211=* - =11 1/4 - 7 1
<
E
2* 112
1)
4nj6
E |||0* w - -12| + 4nj2a² 2
E |||a* z² 1|
b
b
28
E ||aat - u² 1|]
3
w |1/a* 1111 +
1
E |||a* - 1 + 64m0² 2 |||a* - u(11?))
2
64n
2E [(((a)) - F2(2 - F(ck+1) + (2
), x+11 - )= + 4nj a [l|e* - 2
2nE [(((*)) - (=*)) - F(=x-1) + Fi F1 k-1 1; 2b= - =")]
1 E [lIa* - ==] + E [lleot - ==] I E [||u* a =011
E [1aa* [=]
17
17
n
17
1 E [|lat - -s/1 + 64n)
1
4n0² b
E [11e* - ++1 113]
-
E [lIe*
w² [11]
81)
4n10a²
(20²
b + +4702a2 E
[[1Ek - 2/ 1 +
+ 64475
E Blliit - [
(18)
3/1
-2E [T(())) - F, (=²) - F(sh+1) + Fi k+1 2, - -+x11==²)) ====|
[lla* - =11]
2
-2oE [(F(2*) - R²(2²) - =((* + ), # - --11]
where we use the setting 7 < 1/8 in the second inequality.
19

---

Then we consider the terms related to û. Firstly, we have
E
[lla*
2=1
- [||e
2" 2=1
- E [Ila*
w²1
2 B "
[1la*
A112
- 2-" 11
"1
1]
"
(19)
Applying Lemma 6 and plugging equation 19 into equation 18 we have
E [[|a 2" [1²]] + 21F [<((=*) - (= F(sh+!) + (2 (0,=11=2)))
"
1 E [1| [11=At] 2* | + 2 417
+ 64m
Illu* = [2]]
1 E [||=* - =2=1]]] + 20 [[ (F(=*-1) - Fi(=*-11 1) - F(=²) + Fi (i()))) 2t - 2*)]
a
E [[|=* - 111] + 7 E [l =*1[²] E [||2* =² ||2] WI [1| 22 2=1]
+
64n
r7
4n6²
2
1 EE [llat 2x113]]
[||2*
w
||]] 112]
+
E [láE u² ||1 - 2*1]]
b
7
167)
7
28
64nj0 + 34 E [lla* ut [1]
2 E
[l/
a0 113]
81)
211
(20)
where we use the fact that 256 /b+ 256 0² S a to bound the coefficient before the term
of E |||2* - - [|3].
Then we add the term
7 + 20
FE [|] 2" [1]] +
EE [1l
= [1]
(21)
-
pn
to both sides of equation 20 and use the update rule in Line 10 of Algorithm to obtain
7 + m E
I1 6+1 - = [|] = 7 2 E
[1l10 2 11]]
pn
pm
7 + 2 n/
1
E [||
- 21]] + (7 + 1 n1) p)
E [||l* - 2² 113]
"
pm
and
7 +
(7 + (1))(1-)) p)
(1-D+ -(1-2)
(7 + ) (7 +
p7
(7+) )mn)
= -(1-
pnj
) )
(r + )m)
"
pn
pnj
27 +
pd
Combining all above results, we achieve
1 1-2 7
E [| 1+1 - =" =11 + +2 ((((**) -
-Fit))-F(('))) - - F(s + Fi F1 2 - =>>>
2
[[|2At11 2 + 7 E [lwe* - 11] + + _m E [[] 21]
+ 64m
E
4n
pm
1 2
E |||=* - x² 101 + 2a1 (1(2*-1) 11 F( + Fi (2*),, 2*}]
"
E
[||**
*
+ 4nj0²
E |11 -o-t--=-0 x11]
1 E |||=* ut(1?
64n)
16.
7
28
+ 64no2
3p
E [lii*
n² 11]
+
-B
[||i**
n² ||||=+11=-0 =1
811
17
(7 + }111))
+
27 + TTF1
illl
pm
E [|| 1k 21
- 2n
2
I||w* - =2.12)
20

---

Lemma 8. Under setting of Lemma
1 we additionally assume E[D* I 80 holds, then we have
{
B|4 + I < <max
77
E[ 8
E
[|Ia* * - at =
JE E
[[| a" [1?]
6(1 ((1-7)'
27 + mp
16n
2n
Proof.
Recall that the definition of our Lyapunov function is
t²
7
1| - =111² +1(++(((=-)) - -1(2 -((=)) + Fi (= 2t - -2")
1
(22)
1
* 12- + 7 1| - 2/11 (27 + my))
+
11*
1100* =01122
64n
4n
2pm
Recall that we take constant e by equation 14 then the condition
Ek S min {1lat =11111 =²1]3]
guarantees
E [lai 1I] S 2* min { [lae *11] E [lli* - =
where
1
{t 32n
+ 25a + 64n02 + 3/ +
2 ") + 2 2E[4"1
"
(23)
100 + 64y6" 1
+ 2048r
96nu + 64v (
100 + 64n82
+ 2048 + 96nu + 64 / 21/
The inequality (3
is based on the assumption E| Σ $
Note that we have
|| z=1
|/
a+1
||
I*|| + || - then
7
28
+ 2
+
64n8²
+ 3/
E [lla* - [1]]
[llat un ||11=*t1 201l]
817
"
1
9
+
282
64782
+ +3/
[llat [1] + E [la ut =llllat 1I]]
81)
2
+
E
|1|i*
I11
- =='1l]
"
9 +
28
64y782 + 3/3) E [laa* u²(13]] + n7
2T [lat - lllla - ==1
81)
1
2E +
+ 2
[l|i*
u²11 [I]
$
E [1|a* ** 113
321
According to Lemma
we have
7
+
/1
E
[||abt] 6+1 - 2* [19] + 2E [(F(E*) - Fi(z - -((xtt)) + Fi(x+t1), 2641 2²)
17
2
+
1
E
|||
- 2 111 + 41
- E I1ww* - 111 + + +170 E [||w+11 - zz 1121
641)
pr)
?
E
[||**
101 + 2x (F(2 - -Fi (2 - F(z*) + F1 (2*), ck 2*}
+ a
1
E
||22*
1|? +
4702
E
211 -1
+ 32m
1
E |||a* a 112
64n
b
1
E
[||a*
a*
111
3
[l]
w
[d|1 + (1-
pmp
(7 + 1m))
[|| 1lo** - ==1
167)
2m
2 + m1p1
prj
21

---

From the fact that 7/ I 1, we have
1-2 ?
$ (1
mp
1 (1-²)) + 2
6(1 - 7)
"
and according to the fact that 4n02 /b- S at/ (47), we obtain
1 1-> 7 + / 2
E
||| x+1 - 2" 11 + 2E | (F((**) - Fi Fi(= - =(**+1)++ + Fi(z x - =²0)
R. [||2 - + 7 EE [llu** - 111 ? 12m E. [|] 2- !1?
64n
4n
pn
6(1 - >>) (1 (1-2 + 1
E [1 k -=- + (1 (1- 2% + 7711
(7 + (M1))
mll
prp
E [llu** 22 2=]]
2
pn
1
+ 2aB ((F(===1) 13-Po Fi Fi(== (=*-1) F=**) + Fi )= - -="}] +
E [||=* - 11
11=--==-117
64n
7 E [ == ||
1 E [||=* 10113]]
? [lle** - 11].
2n
1677
2n1
The definition 22 and the setting a max {1 - mu/ - 7)), ())),1 pmua/ (27 + mua} implies
E k- 11 S aE[0*]
E [|Ia* - ut 2E [llve** 1t/
(24)
167
2n
Then we provide the proof of Lemma
Proof. We firstly use the induction to prove
E S $0
holds for all & E N.
Note that it holds for ls = O. Assume we have E[ I Φ0 holds, then Lemma & means it holds
E c k
< max
{1-
4/4
E B[
< EE [ < T
6(1 7)
2y + mp
which finish the induction.
The result of above induction implies the condition of Lemma g always holds. Therefore, we can apply Lemma 8 to achieve equation (24). which finishes the proof of Lemma 1
C.2 Proof of Theorem
We firstly introduce the following quantities for analysis
en(22h)
20
Σ
(P(=*) 12(2*) F(w* P3(w"=1)),0) k z),
b
JES
e12(2,h) k)) = 2na
Σ (F(z*) - F1(2*) F(zh-1) )) + F5 2, - 2)/
b
(25)
jESt
e2(2,h) = || - =1|2 - pl1z* - =2122 - -(1 (1- - p>llw* - =1(2
v*()) (3) = (1 (1)7)]lz+t+) -212 ? |1 ==1|2 +
1111 - - 112
1
16
Specifically, we take the constant
E²
nE
Ç == min
(26)
16(9nLD + 3n max [[]((")]] + D)2' 4(12))28++1
22

---

and
à == 100 + 2048: + 21 < 102 + 00/0
(27)
for the statement Theorem Theorem
We then provide several lemmas that will be used in the proof of
Lemma 9. Under the setting of Theorem 7 we have
2 + Fi (ū*), at - 2)
1 11 2
I 4LDDIu* - + 2( (u ) - w²) +
- w01 +
1617
+ 1610011a - 12 ((F(2t) Fi(=)) F(: + F1 (2 , - 2)
+ 1 1| - 11 + 21)020' a²
1
2 // - 112 - (0( - Fi (=*) - F(s*-1) + (==--)),, 2),
21
where Dr == maXie(n] sup [2(()]]
Proof. Note that the sequence (z) is bounded on 2 E Z, since we have
Dr max sup [F(( S max sup sup (z) (= (IF s LD + max (1))( zE|n] ZEZ
(E EE2
iE|n]
(28)
The Lipschitz continuity of F() impies
[ - Dr S 11 -aad)-Fi(s) Fi(()] S LDD,
then we have
- 10 + Fi(1"), at -2
11((==1))) ==2(F(=²) - F1(x*) + - -((t)) ((((A-))))) + +1a(a"), - 2)
-2((F(x²) Fi("*) F(at)) + +Fi(a*), Ett - 2)
-2(P(n"), at -(((("),a*=2) =2)
-2(F(=*) - -(=-))>(=*)))))) - F(a + F1( ); at 2111)
-2(F(=*) - (= - F(s + (( 2)
-2a(F(2") F1 - ((=*-1)- Fi(( (10et1)),,,, a² - 2)
(29)
2a(F(z²) - -F - -(=h-1)++ F1((2-11)
2)
1
< 4LD|Iu* - + 2(F(u²), w²) + (BLD + (DD))(() u² +
1| - 1
161
+ +16702111 - w²12 - 2(F(=*) - F1( - F(ght1) Fi (2/+1), 2 22)
1 11 11:--it' 1/2 + 2 -
21
- -
- F(=*11) + Fi(=* 1), 2 - z).
Lemma 10. Under the setting of Theorem 7 the quantities defined in equation 25 hold
K
max (=(=) + E xE2
en (2, k)) + (12(2,)) + I [ez(z,h) ki)
max #E2
p
k=0
2r7
K-1
202 b
K-1 E
max 4/| -112 +
Σ km
E [||2* 1011 +
2p +
=E2
0
+ +(2p+ 1pp
811282
K --1 Σ
E [1läk-u*h 127
23

---

Proof. Applying Lemma
with x² = = Fu = ), Fs = o(5" ..... ..,,, ) for k 2 1, and
pl+t1
2n
b Ejest Fz(ah)
F(**) Fj 1) + F(u and using R& [x(rrt+1] = 0, we have
K-1
K
K-1
E max 2E2
Σ (2((2,)
E max
Σ k=0
(nttt 22)
S max =E2 2
11 - 2112 +
Σ k=0
E [|]
=E2
k=0
211² 8
K
< max
1|=00
+
E |||** * - 11]]
=E2 2
b
k=0
Similarly we can obtain
K-1
21
K
E
max 2E2
e12(2, kb)
S max =E2 2
-1=00
=112+ +
EE [1Ie* - =1--111-
b
==
k=0
Applying Lemma 4 with x=0 = 20, Fo = o( F& = oSS0
Sk- ,
) for k > 1. and
,k+1= = p2 h+1 + (1 p)u* - and using the fact that [[[]] 1|||
* ++1 ||3 (1 - p) || , || = 0
and Ex (rdh +++ 1 = 0, we have
K-1
K
E
max 22Z
e2 c2 k)
= 2E
max =E2
(1
k+1 x)
S
max || - 21|² + Σ || 11
2E2
k=0
k=0
K
< max xE2
||20 - 2112 + +p1 - p)
Σ
E ||
- 10
k=
where we use
E
[|nktt
b+1
[2]] = E BB++ 1/2 BB 1/2 k+1 21 w 2
E | [||1 k+1
11²] [+
|| [| (w 11
= E [pl|z
||2 + (1 - -)) lppa ++1 + (1 - p) p)v=* [13]
= p(1 - D) [||=
w+11
Note that 2h = wk=1
then we have
K-1
max sEZ
T7
(2) +
E
max 2E2
en h)) + k2)(2,k) + 2 k))
p
k=
2n 8
K-1
27 282 K-1
< 4 max 2E2
|| - 2|1 +
E -
Σ k=
E 1112- 111]
b
k=
K-1
+ +y(1 p)
E
[||
w 113
k=
+ 2n 82
K-1
an2a252 22 K-1
< 4 max zE2
||
=1| -
E -
+
E -
= 112]
b
k=0
K --1
4n
4n2
K-1 1 Σ
+ 2p
E [liat - w* 1+1 +
+
+ 2p
E
[1(a* 111
b
b
0=
k=0
- =212 + 22 K-1
20720²
K-1
< 4 maxx 2E2
|1
Σ k=
E [|Ia* 10113] + 2p +
Σ
E [lle** =0(13]]
b
k=0
82
K
+ 2p
E.. [lla* k - ~111
where we use Young's inequality and a S 1.
24

---

Now we provide the proof of Theorem !
Proof. The optimality of út implies for all 2 E 2, we have
(nF) + at ot 2 - a=)200
20. 0.
(30)
Combine equation 30 with the update rule in Line 7 of Algorithm I. we achieve
1z at n700 at - 2) S - (F1 (Fi(1)), at 2).
(31)
Then we have
1 77
2 (ūt 2/ att 2) -1 1²2
||a
1 k =||3
11
2
1
21
(w
2t 5t 2) 2(8 att 2)
7
2
11a
x
112
(5
ak
110*, at 2)
"1
24
1 11tt -11
11 211
(w
2t athh 2) 2(6 attt -2)
211
1
77
17
2(F (i²), at
2)
11
=11²
1/00**
=11² - 2 110
1//13 - 2
-11=* 2 - ==112
1 1- 7 11th - =x11
2(8* + Fi (aa) ) ahth - 2)
112 =112 2 II =112
2 1 -2/113
11 - -2112
1 1-7 7 11at 2²1
7
"
- 2(TE5* + Fi Fi at 2) + e1n R:) + =12((2,)) R)),
(32)
Combining the results of equation 32 with Lemma
we have
1 -llat - z|12 S - || # =||² + 1I - z||² - 2
l - 1i1112 - 2 1| =||2
7)
1)
1 1-9 ? 11at - 111 - -2(E5* + Fi Fi(t a²a - 2) +
1
+ 1
cI1 c2112, k))
e12 (2, k)
17
17
n
5 11 =112 + 2 1100 =||2 7
1u= 1/113 - -11 - ==12-
| 11 11
1)
1)
4vj
+ 2(F(ut)) x- w²) + (12LD + 6Dp) ))1( - -1 + 1| 111
16n
+ 1670011a* - 11 16 2(F((*)
F1(* =(tx+t) + F1 (1(2++1) - 2)
+ 2n02 - - F(2 + Fi (2 - 2)
+ -en(z,,) k)) + h))2(z,h)
(33)
where we use the fact 7 S 1/4.
From the fact that ||a + b1l2 2 2 |||a|| |bb12 and 3 I|aa + bb12 2 ||a|/2 311b112, we have
1
1
1/ =1112 < || ++1 21122 + 4n , u 112
4n
81)
(34)
7 1
1//12
+
112
| 111 112.
17
2n
25

---

Plugging equation
34 into equation 33) we achieve
1
|aat
=11²
1 =|1
? 1 =1|2
7 11 -
1 - || 111
17
11
81
|1 - u² 112 + +2(F((()) = - -ut + (12LD+ +6Dx) - u²11
+
4n
1
12 - 2 - -FF((=) - R((5 - F(ghtl) + Fi (i ), 2 -
167
+ 16102 - 1² - 20 (Fx) - R2 - -(( + +1 )) - 2)
+ +n78 a
- -2112=-2 1|2 - 27
11e - 11 + 2 212² 1
1
1
en (2,
-=12(2, ki)
"
1)
- || - z11 + 2 21 - =112 - 11 - =11
1
1
1| 1 - 2/ 1|
$
"1
1)
16n
2 1 1|2 + 2(F - w²) + (12LD+6DF) )1(" 1666--''" -v01l
+
21
2(F(=*) F((=t) F(*ht)) + Fi F2 (z ), 1, -2) 2n10² 2 - 112
-2a(F(=²)- - Fi Fi(1 - F(=*-1) 1) +
(=*-1)) ),==,,,,+--
+ (16706' +
1
11et - u 11112 + - en (2, k) + _112(2,)) k).
217
Note that the fact
11at - z/1² = -
1| z|12
1
+
1 +1aat w* 111 -
2
|lat -11||= =||,
1)
11
")
then we have
2
2(F ( nh - -2) 5
|+++1 - ==113 11at - r&112
+
|1at
||||| |+1 =||
7
1)
+ 1 12 + w 2|12
2
11 2|12
1
|| - 2/11
17
167
2
1100 x - *+ 113 (12LD + 6D>) & - u²1 + 21102 a 211 - -
21
- -((((²)) - F1 (=(²) - F(: + [1(=*t1 (1=++)),,,)) ),, x+ - 2)
(= - F1((²)) - -(==- 1) +
- z)
+ *(1600' + 1
1
l1at - 11 + e11 k) + 17
12222, k)
2n1
17
S |1aht1 =11²
1
|| k+1 xx112 7
|| 21
7
166
2n
2(F(=*) -F((**) - F(2+ + (2
) 2,2 2)
+ 1 - =x12 + 7 1/ =112 - -1 =112 + 22110 22l1 - ----11²
1)
11
+ 2a(FF(= (o))= -F( - F(z*)
+ Fi (=²) ) z)
+ 12LD + +6Dr + 2D
|lit w²1l + 16710 3110 111
1)
+ (2((),))) + - k)
< 1- ||=601 - -x112 - 7 || ||
k+1 - =1122-
1
| - =2²12
71
1p
16n
-((((2 -Fi(2*) - FF( + F1(2
2 2, 2)
26

---

+ 7 7
1 2112+
7
1 =212 + 2:102 2 - 12
17
mp
+ -FF(z - F(z*) + Fi Fi (2 2t -2)
+ 1212 6Dr + 2D
110t - -w11l + 16110211 - -u²=1²
(an(es.k) (k) + k2) + I (e2((z
7 11 w²
+ "
p
21
The parameters settings implies 2788 1 1/(16)). then we have
K-1 1
2 R
max
(F("") =)
K
h=0
K-1
< max 4o (1((2) (z)+ +
max ZEZ
en(z,)) + k1) + 2 2e2(2, k)
(35)
sE2
p
K-1
(112LDD + Dn 2D) 11a - - 1617 82 -ax13)
Recall that we take by equation
27 then the setting
E min { {, a min {llØ* - 21, I|, 11 - =
satisfies the condition on Ej Lemma D Then we apply Lemmal with μ and 1 and sum over equation (9 with & = O..... K I to obtain
at [2] + 2E [llw* st(1e]) s [ p 1| - -2211
(36)
A=
Note that parameter settings y y p satisfy
1/ (/ + 8), b= [/n]], and min (V76/(40), 1/335)
4 82
1
411282
46 7b
7 2
and 1+ 7 = 2.
<
2p +
< 2p
+
5
(37)
b
32'
b
b
1652
p
Substituting equations
36 and (37
into equation
35 and applying Lemma 10
we obtain
K-1
E
max
Σ
(F(u))
u²
2)
K
k=0 0
(4 + 8 2)
max |1200 =/12 zE2
2nK
K-1
817282
(12mLD + 6DDD + 2D) ||ū - - + (167202 +
b + 2p 1 - i2/12)
+
2nk
k=0
10D
GnLD + Dr + D
V 12:1282 +
11
7)
10D2
9mLD + 3n maxie(m] [b(2))||| DD V
12 82 +
C,
1)
"
where we the equation (28)
to bound Dr.
Recall that we take constant ( by equation 26
then we get the bound
E
max
K
((( -2)
5 n
10
+
8
K
2
k=0
27

---

C.3 Proof of Corollary 1
Proof. Theorem means we can achieve E[Gap( (avg) I E by taking the communication rounds of
200
D Em
O 6D2
K
O
En
Consider that the expected communication complexity in each round is O(6(1- -)) + + Olvn) and the server need communicate with all client initialization within the communication complexity of On), the overall communication complexity is
((n) + K O(vn) = VndD²
Note that the objective of the sub-problem in Line 8 of Algorithm D is (L + 1/n)-smooth-(L/)) (amnglyyycoovexxm/nnnsstttroooo
the local gradient complexity for solving the sub-problem is ((1 + nL) log (og(m -.). Therefore, the overall local gradient complexity is
(n)) + K. (O(Vn) + O ((1 7L) log(s- +)))
80D
((VV) +0 (11 L
LD + DF
$
= =(()) + +0
log
5
(Vnō + D
n
log
C.4 Proof of Theorem
Proof. We can verify that the parameter setting of Theorem satisfies the condition of Lemma Then we can apply Lemma] to obtain
E < max
1
Tp
Th
(38)
24 + mp 6(1 7)
C.5 Proof of Corollary 2
Proof. Recall that set the parameters
b
min
Vn,
min
nh
+
V7b 1
7/44
mmd
1) min
a max
46
328
6(1
7)
27 + 1/44
We can lower bound
pnp
pdd
1
7
a 2213 1
2y
mp
2p + 7p
2
+
1
>
8
(39)
Tpa
P
Then the number of communication rounds is
Y + mp
1
=
1
+
log
pmu
( + log
(() +
328
328 +
log
Vanb
(() + +
1
1
log
Vp
28

---

Note that
1
8
5
8
min Vn, 6
8
+
S min
VT.
+
8
p
vpbl μ
11
1
min
VTz á
5
8
min
Vn.
8
1 8 8max
1
vn
0
then we have K
(68
Consider that the expected communication complexity in each round is
O p) nu)) O (V 7
and the server need to communicate with all client in initialization within the communication complexity of O(n), the overall communication complexity
(n)) + K (Vn+ +Vn 5) =o (((n+ Vnd
log !)
Note that the objective of the sub-problem in Line of Algorithm I is (L + 1/m)-smooth-(1//n (in))-ooovee-//mmssssstooggg/o
the local gradient complexity for solving the sub-problem is O + nD) log(e)). Therefore, the overall local gradient complexity is
O(n) K
(0
ny 5
+ +0 + TL) log(c))
Onn) + +0
log
0
VTi
1 8
+ +0 ((1
L
) log 11)
((n n++
Vnd
L
δ
1
o
log
log
((+ vnō
+ I.
Ö
log
D The Algorithm Class
We formally define the distributed first-order oracle (DFO) algorithm as follows.
Definition 1 (DFO Algorithm). Each node has its own local memories M and Mÿ for the x- and y-variables with initialization M MM [0] for all E [n]]. Specifically, the server has memories M and M These memories {M and {M?) can be updated as follows:
Communication from clients server: During one communication round, we sample uniformly and independently batch S of any size b and ask client with number from S to share some vector of their local memories with the server, i.e. can add points 2's s to the local memories of the server according to the next rule:
1 E span
FT, U I iES
and
s E span
U. iES
where E MM and y: MM. the batch size is equal to b we say that it costs communication complexity from clients to the server. Batch of the size n is equal to the situation, when all clients send their memories to the server.
Communication from server to clients: During one communication round, we sample uniformly and independently batch S of any size b and ask the server share some vector of its local
29

---

memories with the clients with numbers from S, i.e. can add points 2 v to the corresponding local memories of client as
d span [11,
and 1/5 span 31
where 3i M and yi E M. and say that it costs communication complexity. Local computations: During local computations each client can make any computations using fü. i.e. add points 24 V/ to the corresponding local memory of client as
d/. Esaa {Øl, aa (x"))"))
and vl E Esan (v', Vufi (a",
for given x',x" E M and yf vf" E EM. And we use local gradient calls to count the times when v and Vy are applied to any one of (fi)-
The final global output calculated as & E MM. D E M?.
Our Definition T follows the algorithm class of Beznosikov al. g Definition C.7], but additionally take the communication from the server to the clients into considerations.
E Proofs for Lower Bounds in Convex-Concave Case
In this section, we provide the proofs of the lower bounds for solving the problem
min max f(x vEy
Σ f(x,,))
(40)
by DFO algorithms, where the diameters of closed convex sets X and y are Rr and Ry respectively. We define the subspaces (Fx 12
k=
F sspan (p..,.e ek),
for S d, for 0,
{Od].
which is used in the following proofs of lower bounds.
E.1 Proof of Theorem 3
We first define the function set with server (i 1) and clients (i 22..., as follows
Ry Tr.
x
A1y
- 1 = (mod 3);
4
2vd
f((2,))
8
(41)
xx"
A2y.
1 = (mod 3),
4"
O,
otherwise.
Then corresponding global objective is
8
RR T 6
f(x, v)
Ay
c
(42)
where
1
0
-2
-1
-2
0
1
A1
Aq
1
0
1
-2
(43)
Proposition 2. For any the functions Sela, 3) and f(, y) defined by equations satisfy
41 and
42
30

---

1. The function fi is L-soooth with L 2 5 and convex-concave for all i E [m], and the function set {fi]==1 holds 6-second- order similarity. Thus, the function is also convex-concave.
2. For 1 < k S d L, we have
8Rg Ryy
min Gap(a, v) = min max f(, max min f(x 2 (2.))
6 bvd(+1) (44)
zEXnF& VEY
BE ZER
Proof. The smoothness and the convexity (concavity) are easy to verify. The similarity holds because
( V vx, (22f2(1, v) (x, v
va Vzz((z, v) 0;
V f1. fz.(()))= V fz. V
fz.(z. foff((,,)) V (x. O: 11 / w)ll
(11(((1)))) (2,((,))) /1
5
I1V (2222(111) V (x,,),,))
| (2 w) + | -, / w))l
+
S 6;
8
3
5
222//(11))) V fx, v) <
V2 by /3(2, w| + |2 / (a, w)|l S
+
S 6.
8
The function f(x, y) defined by our equation (42) is identical to the function fco(1, y) defined by
Han et al. [4 Proposition 3.31 F by replacing their notation L with our å and taking = 3. Then
Proposition 3.31 of Han et al. [4] directly prove the result of equation
The structure of A₁ and A2 results the following lemma.
Lemma 11. For the function set (41 all (x,z) E Fx x Fx and = 0,..., we huve
Fu+1 Fk-1;
(i, E Iı UI2,
Vi((x E
Fr Fk:
otherwise,
where the index sets are defined as I == {(i, k) =i-12 (mod 3) k = (mod 2)} and
I2 = k(i,k): i 1 = (mod 3), (mod 2)}.
Now we provide the proof of Theorem
Proof. Consider the minimax problem 40 with functions
41 and 42
R₂ = Ry D, n > 3 and
d |8D? /33/2=] - 1. Then the assumption S 5D? (12v2) 2) implies d > 3. Lemma 11 means
that we need at least one communication round to increase the number of non
non-zero zero coordinate, i.c.
(ar, v) ZnF k. Running any DFO algorithm with communication rounds of K [(d ( 2
we have d/2 E [K + 1) < (d + 1)/2 and Proposition 2 liplies
8D2
6D2
8D2 3 +1) ZE.
E[Gap(æ, v)1
min (x.3)E
Gap(x, v)
6/d(k +1)
6 ((2(+1)
Hence, we achieve the lower bound on the communication rounds
8D2
8D2
K
11 Ω
6v2s
F.2
Proof of Theorem 4
We first define the function set with one server (i = 1) and
1 clients (f=2...,,)) 1) as follows
VnuRg
eTz,
i= 1,
8vd
fx =
(45)
vnd
T
Σ
eja y,
i 2> 2.
8
j=( mo)d
We follow the notation of Han al. [14 arXiv version:
31

---

Then corresponding global objective is
8R 8ynd
f(z, U) = 8/n x Ay
ci x;
(46)
where ej is the j-th basis column vector, a3 is the j-th row of A, A, ()- mad (n-1) c3
A 0 and A is defined in equation
We provide the following proposition and lemmas for the proof of Theorem
Proposition 3. For any d 2 3. f((x.)) v) and f(z.y) v) defined equations 44 and (46) satisfy
1. St is L-smooth with L 2 v and convex-concave, function set {fi) has ó second-onder similarity. Thus, I conver-concave.
2. For 1 < k S d 1, we have
max min ((r,y) 2 8R R. yED DEA
min Gap(a, (#.))E2nF3
= min max ( 2EXnFE yEY
8V ndl //nd(( (k 1)
(47)
Proof. The smoothness and convexity (concavity) are easy to check. And the similarity can be verified following the methods of Beznosikov et al. [8] Lemma C.8]. The function far y) defined by our equation (6) is identical to the function fcc(2, y) defined by Han et al. [14] Proposition 3.31] by
replacing their notation L with our /nō/4 /4. Then Proposition 3.31 of Han et al. [14] directly prove
the result of equation 47).
Lemma 12. Consider the minimax problem 40 with functions 45
and
46
R
R = D.
d = 6DD2 [n))] - and & S 8D2
/DD0 /16 2n) We let M [(d
1)/2
R(DD2 /0D22/(/1s))) (vns)).
then any point (z, y) E Z Fi satisfies Gap(z, ,, y) 2E.
Proof. The assumptions on and M imply d 2 3. and d/2 S (M + 11 S (d 1)/2. Then Proposition 3 means
8D2
6D2
5D2
Gap(æ, v) (s.9)E2nF3,
min Gap(z,v) 2
2
2E.
8 8/ s/nd(M M +1] 8 2n +1)
4v/2nd 1)
Lemma 13. Consider the minimax problem (40) with functions (45) and (46) and any DFO
algorithm with V communication complexity and C local gradient calls. In expectation, only the first M S min /n, /n coordinates of the final output can be non-zero while the rest of the d M coordinates are strictly equal to zero.
Proof. At initialization, M = M = Fo- Let's analyze how M and M change through local computations. For the i-th client, we add the following points to M and My as
x E span (a', Any'), and y E span {er T(i 1).1/ ATx'.
where x' E MM and y' E EM"
It is easy to see that the server can make the first coordinate of y non-zero using e,, and broadcast this progress to other clients. Only updates of the type A.y/ or A T' will help in this regard. Since A, only contains rows from the matrix A such as the (i - 1)-th row, (n + - 1)-th row, etc., make the first coordinate of x in the global output non-zero, we need and can only use the Ag matrix. It can be noted that by using Ag, first coordinate x non-zero. Furthermore, to make more progress, we need to use Ay and so on. We conclude that must constantly transfer progress from the node currently needed (to make the next coordinate x non-zero; then of y) to the server, and then to other nodes.
also make the second coordinate of y non-zero after making the
By definition, one communication round involves communication with all clients or only with batches of some uniform and independent clients. When we sample without replacement, the success probability of communication round clients with batch size b (i.c., making one coordinate
32

---

non-zero) is n-I (or when = n), which is also the expected number of non-zero zero coordinates that can be obtained with b communication complexity and at least b local gradient calls (as each use of the matrix necessarily comes from gradient call). When we sample with replacement by a batch size b, it is equivalent to that we sample without replacement by batch size 1 for b times. Assuming that we have communication rounds with batch sizes (sampling without replacement) of 2...... for $1, $ Sn times, then the communication complexity we spent is V ンÿ= j8, and the minimum gradient calls we spent is C = Σラ= jsj. This implies the expected number of non-zero m- coordinates is M j=1
--T3 Sn. Therefore, the expected total number of non-zero coordinates in the global output is at most M for and M - for (or we can say M). By comparing expressions of V, and M, we can have M s 2V/n and M s 2C/n, completing the proof.
Then prove Theorem 4 by combining Lemma 12 and 13
E.3
Proof of Lemma 2
We choose the function set as
L
LRy 2vd e Vi [n]]
TT Ay 2
(48)
where defined as equation
(43) The structure of results the following lemma.
Lemma 14. For the function set 48 all (x, v) E FR Fx and k 0, ,,..., have
V f) Fk+1 Fk+11
One can follow the similar method as the proof of Theorem 4 to prove the following proposition and lemma for the proof of Lemma? 2
Proposition 4. For any d 2 3. fi and f(x,y) defined equation (48
satisfy
1. ft is L-smooth and convex-concave, cuneertionaav set {fi has 5 second-order similarity for any
8>0 0. Thus, f is convex-concave.
2. For 1 < k < d 1, have
LR, Ry /
min Zr
Gap(z. = min max f(z, max min min f(z,8) ZEXnFL yEy
2
BEETFA ZE
Lemma 15. Consider the minimax problem
44 with the function set
48
R Ry D.
d = |8D2/ (1/2(((22) any point (z, E zn F3, satisfies Gap(z, y) 2
and 8D2 (D4/( We let M [(d 1)/2 2
S(TTD2 /ε), then
Then we can prove Lemma 2 by combining Lemma 14 and 15
E.4 Proof of Theorem 5
Proof. In the case of Vād 2 Q(L), the problem with with functions (45 and (46 in Theorem implies the lower bound on the local gradient complexity of
Ω n + vnoDa - n (Vno L)D2
In the case of L 2 2( (()))), the problem with function 48) on the local gradient complexity of 2(LD2 Q(n /d L) D /e). Combining these two cases, we achieve the lower bound on the local gradient complexity 9(n + (Vnō + L))² O
in Lemma 2 implies the lower bound
F Proofs for Lower Bounds in Strongy-Coneex-StronyyyCCCCsss
Case
We follow similar steps as in Appendix F to prove Theorem 7 detailed theorems and lemmas below and prove them by one.
Firstly we divide it into several
33

---

Theorem 8. For any p. L > 0 with L 2 max(u, 8} and n 2 2, there exist L-smooth and convex- concave functions f1....,2 Jn TRd x TR with ô-second-order similarity such that the function f(zyy) Dist f((x, y) p-stroonghy-convex-e sosooveerssttonnii--oomaass In order to find a solution of problem such that E[
any DFO algorithm needs least ( log(1/e)) communication complexity and (2((n + vnd/p) log(1/E)) local gradient calls.
Lemma 16. For any 6, L > 0 with L 2 mu. 6} and n 2 2, there exist L-smooth and convex- IR x R with d-second-orde similarity such that the function f(z,y) = = -i= f((z, 3) is ju-strongly-conver weteee---strongyy-coo
concave functions fa.....
In order to find solution of problem ( such that E 2" [1 any DFO algorithm needs at least (LLl gradient calls.
local
Theorem 9. For any μ. J,,811 L > O with 2 maxiu, 83 and n Z 2, there exist L-smooth and convex-coneave functions fi..... R R with 8-second-order similarity such that the function f(z.
D fZ V) is -u comtoyyccattt concave. In order to find solution of problem 1 such that E|[l= =01 I any DFO algorithm needs at least
M((n + (y'n L) log( (e)) local gradient calls.
F.1 Proof of Theorem
We introduce the function set as in 8 which is similar to equation (45
that
||=||
2
|
+
1
y
i 1,
2
2
16p
f((,8)= =
(49)
8/n
T
+
1 1
|2
lell
i >> 2.
4
2
2
j=((-1) mod (n-1)
Then corresponding global objective
f(x v)
8 I x Ay +
11
|
11 2
|lyl
82
e
(50)
16n
where all the notation keeps the same the former section.
We point out that the global objective with constant 8, and
function (50) with local functions (49) satisfies Assumptions 1 and 6
2 8. See Lemma C.8 of Beznosikov al. [ for details.
We provide the following lemmas for the proof of Theorem
Lemma 17, Consider the minimax problem (40) with functions (49 and (50) and run any DFO
algorithm with V communication complexity and C local gradient calls. In expectation, only the first
M < min /n. 2C /c coordinates of the final output can be non-zero while the rest of the coordinates strictly equal to zero.
Proof. Follow the proof of Lemma
13
Lemma 18 (Beznosikov et al. 8 Theorem C.10D.. Let p > 0, E N. M E N. There exists
a centralized distributed saddle-point problem with functions (49 and (50). in which 2" * and
Z max (2 log, (a/ (4v 22), 2M} where a 16np² (52 and q = (2+ va² + 40) / E (0, 1). Then for any output (ă. 9) of any DFO algorithm leaving d M coordinates zero, one can obtain the following estimate:
16
x
11 +
110 1²1 = Ω
exp
M
11:0
y²1
1
8a
16
Then prove Theorem 8 by combining Lemma 17 and a8d noting that to reach solution of E-accuracy requires
2V
2C 2 M
((1
8
log -
02
min
n
n
34

---

F.2 Proof of Lemma 16
introduce the function set as
I
f(x.v) f1(2,))
Ay + ||=11
" l1v1l +
c.v. 4p
Vi [n].
(51)
where
-1
A
Note that since all the nodes have the same function, this function set 51 satisfies Assumptions 3 and 6 for L, μu and any 5 > The structure of A results following lemma.
Lemma 19. For the function set 51 all (2,y) F x Fs and = 0, .,....d - we have
Vflaz, v) Fk+1 X Fk+1.
Lemma 20, Let p., > n E C E N. There exists centralized distributed saddle- saddle-point problem with functions 511. in which 2" + 0 and d 2 max log, (a/v2); 4C) where = μ¹² IT? and 1 - 20x 2/a² + a E 1). Then for any DFO algorithm, the output (v))))) after C local gradient calls will satisfies
11
11 - 5²1 c
(52)
16
Proof. Follow the proof of Theorem 3.5 by Zhang et al. and P2 By μ..
55
which we take Lx Ly Lay
Then we can prove Lemma by combining Lemma T9 and 20 and noting that to reach solution with e-accuracy needs at least log(L/e)) local gradient calls from equation (52
F.3 Proof of Theorem
Proof. In the case of ny + vnō 2 S2(L), the problem with with functions 44 and implies the lower bound the local gradient complexity of
50 in Theorem
Ω ((m
viδ (( log
1
nn
log
In the case of T. > Mny + vno), the problem with function (51 in Lemma 16 implies the lower
bound on the local gradient complexity of (og(1o)) S2((n + (yno L)/H) log(1 (ee)). Combining these cases, Q(n+ + (Vnō + L)/u) log(1/s)).
achieve the lower bound the local gradient complexity of
G Making the Gradient Small
In constrained case, we can also use gradient mapping to measure the sub- sub-optimality of a solution that is
F+(2)= : =- 2-P2(=-7F()
For the L-smooth convex-concave function S. consider the constrained problem
A
A 11 v
min max f(x, f(x, v) 2 2012 #ex
35

---

10-
12-4
Graden Vacring
10-2
10-1
10
Cradeen
10
20-1
SPMIDS
SHIDSS
SHNISS
ES5
10-1
EG5
E65
T20pp
TRAFP
TRAPP
5W0GS
5VOGS
20
60
56
50
100
120
2000
10030
13000
20005
2030:
40020
60000 00002 100030
Figure 5: Results for convex-concave minimax problem
on covtype.
307
3MMS55
SHYDS
10"
565
TIAPP
10"
565
TRAPP
216
syDns
10
SVDES
10-4
10-11
23
20
2500 5:00 7555
15850 12500
20303
40000
62000
Figure 6: Results for strongly-oonexx-trnngglyyyoo minimax problem on covtype.
where f is -sstronlyy-covve---sttoonyyy
and bounded by diameter D. From the the result of Theorem we have E || - -- - (1 xA/6)* ||=0 - 2*1 for some constant E (0, 1). then we have
2k Pz (2k -((((=k) 1(2 -29)) =01)
Pz(=K) -Pz (*t - [(p(a 2(= - =001)
E
E
((= -\(2 -
(2 11] + AE [| - =011]]
E
E {(=*) -ド ||| + ATE =
LE
||| || + AE |||= - ==01]]
where we use the property of the projection that 1! -P2(2e)) S || 22 and the gradient
mapping holds that J (22) = 0. Then we have
||
< 2T || 5* ||| + 2F -291"
< - (
K |120 - -0- 2
2 |||=* - =00
< <22L(11-XM)) xA/6)* D22
Let À = (4D() and K = O(6/)lo((LEE), then we have E' [| )11²] S
Hence, the complexity of communication rounds is K = O (5D) log log(LL/)) We verify that the corresponding communication complexity is Ö((n + vnoD/ (1/(1 and the local gradient complexity is Ö( + (vñō + L)D/ V log(1/s)) by following the discussion in Appendix C.5
H More Experimental Results
We present the experimental results dataset "covtype" in Figure and 6
36

---

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:
[Yes] See Section |
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: [Yes] See Section g
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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]
37

---

Justification:
[Yes] See Section 2 and Appendix A|G
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but 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
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: [Yes] See Section 7
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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 are appropriate to the research performed.
While NeurIPS 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) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
38

---

Answer: [Yes]
Justification: [Yes] We include the code in the supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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 NeurIPS code and data submission guidelines (https guwdes/ddeeeeee Cooeeeoodeesssseeeeee //nips.com / ssiniioiscyp 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 as much information as possible supplemental material (appended the paper) is 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: [Yes] See Section 7 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: [No] Error bars not reported due their potential obscure the clarity convergence dynamics in the graph representation.
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
39

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: [Yes] See Section and Appendix
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 compute required for each of the individual experimental runs 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 make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:/ppp.//.aa......//////////a
Answer: [Yes]
Justification: [Yes]
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- eration 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: [NA] The paper focuses on optimizing algorithmic enhancements unrelated to potential social impacts.
Guidelines:
The answer NA means that there 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.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
40

---

The conference expects that many papers will be foundational research and not tied 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 an 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 a 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses 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 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. Lieenses 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: [Yes] The original paper for used LIBSVM dataset is cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
41

---

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: [NA]
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an 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 details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 Ethies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing 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, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "WRMWUn933I", "reviewer": "Reviewer_Vpvu", "summary": "This manuscript considers solving (strongly) convex (strongly) concave distributed minimax optimization problem. The authors proposed a stochastic variance-reduced optimistic\ngradient sliding method with node sampling, named SVOGS, which achieves complexity nearly matches the obtained lower bound.", "questions": "- The authors bring the results for minimization in Ref. [25] directly to compare with the results for the minimax problem in this paper. Does this mean that the minimax problem in this paper does not have additional difficulties compared with the minimization problem?\n- The distinction between the optimistic gradient and extra-gradient methods for minimax problem should be clarified. The reviewer is curious about the possibility that the EG method in Ref. [25], combined with node sampling, could also achieve similar results.\n- Refer to Weaknesses for more concerns to be addressed properly.", "limitations": "The (strongly) convex (strongly) concave distributed minimax optimization problem considered in this work is not applicable to most machine learning tasks and is thus of limited significance in this area.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper improves the complexity of existing algorithms through the adoption of node sampling, especially when dealing with a large number of nodes. The theoretical results are well-supported by simulation experiments.\n- The complexity results are thoroughly compared with existing results.\n- The paper is well-organized and easy to read.", "weaknesses": "- The algorithm design is straightforward. The novelty of the algorithm is limited to the node sampling aspect, which is a simple and obvious adaptation from the existing methods, e.g. Ref. [5]. The authors should further clarify the unique characterisics of the algorithm.\n- It seems to the reviewer that incorporating uniform and independent node sampling (c.f., Line 5 in Algorithm 1) does not present any new challenge to the convergence analysis as compared to existing methods. The authors should further clarify the technical contribution of their approach.\n- The experiments utilize toy datasets, e.g., a9a, which may limit the generalizability of the results.\n- The rationality of Assumption 2 should be discussed in more detail to ensure its validity and relevance to the study.\n- Theorems 1 and 2 requires many hyperparameters to be set to exact values that depend on the parameters of the problem. In practice, these parameters are often very difficult to obtain, which may weaken the theoretical results in this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Results for minimization in Ref. [25]**\n\nRef. [25] studies both minimization and minimax problems. We only compare their results for the minimax problem (Table 1-3).\n\nThe minimax problem is indeed more difficult than the minimization problem. For example, Section 3 of Ref. [25] considers the strongly convex minimization problem by archiving the complexities depend on $\\sqrt{\\delta/\\mu}$ and $\\sqrt{L/\\mu}$, and Section 4 of Ref. [25] considers the strongly-convex-strongly-concave minimax (strongly monotone variational inequality) problem by archiving the complexities depend on $\\delta/\\mu$ and $L/\\mu$. Noticing that the lower bounds in Section 6.2 of our paper show such dependence on $\\delta/\\mu$ and $L/\\mu$ cannot be improved for this minimax problem, which means it is more difficult.\n\n**Combine EG [25] with node sampling**\n\nCompared with our result, applying the node sampling (variance reduction) [1] to EG method [25] will lead to the additional term $\\sqrt{n}$ in the complexity of communication rounds, because EG framework cannot benefit to the mini-batch sampling.\n\nFor ease of understanding, we follow the notations and settings of the Algorithm 1 for single machine in Ref. [1] to illustrate this issue (the problem in distributed case is similar). The essential step in the analysis for Algorithm 1 of Ref. [1] is their equation (9) in Lemma 2.9, that is \n$$\n\\begin{aligned}\n & \\mathbb{E}_k[2 \\tau\\langle F\\_{\\xi_k}(w_k)-F\\_{\\xi_k}(z\\_{k+1 / 2}), z\\_{k+1}-z\\_{k+1 / 2}\\rangle] & \\\\\\\\\n\\leq & \\mathbb{E}_k[2 \\tau\\\\|F\\_{\\xi_k}(w_k)-F\\_{\\xi_k}(z\\_{k+1 / 2})\\\\|\\\\|z\\_{k+1}-z\\_{k+1 / 2}\\\\|] & \\text { (Cauchy-Schwarz) } \\\\\\\\\n\\leq & \\frac{\\tau^2}{\\gamma} \\mathbb{E}_k[\\\\|F\\_{\\xi_k}(z\\_{k+1 / 2})-F\\_{\\xi_k}(w_k)\\\\|^2]+\\gamma \\mathbb{E}_k[\\\\|z\\_{k+1}-z\\_{k+1 / 2}\\\\|^2] & \\text { (Young's ineq.) } \\\\\\\\\n\\leq & (1-\\alpha) \\gamma\\\\|z\\_{k+1 / 2}-w_k\\\\|^2+\\gamma \\mathbb{E}_k[\\\\|z\\_{k+1}-z\\_{k+1 / 2}\\\\|^2], & \\text { (Assumption 1(iv)) }   \n\\end{aligned}\n$$\n\nwhere $\\tau=\\sqrt{1-\\alpha}\\gamma/L$ and Assumption 1(iv) is the mean-squared Lipschitz continuous condition on $F_j(\\cdot)$ such that $\\mathbb{E}\\big[\\\\|F_j(u)-F_j(w)\\\\|^2\\big]\\leq L^2\\\\|u-w\\\\|^2$ for all $u,w\\in\\mathcal{Z}$.  \nDirectly adapting above analysis to our distributed problem will leads to an extra term of $\\sqrt{n}$ in the complexity of communication rounds (compared with the methods without node sampling), since the third line in the loop of Algorithm 1 of Ref. [1] only draws one sample $\\xi_k$. To match the results of our paper, we desire to introduce the mini-batch sampling like our Algorithm 1 (Line 6) into the framework of EG, which is replacing the term \n$$F_{\\xi_k}(w_k)-F_{\\xi_k}(z_{k+1/2}) $$\nwith\n$$\\frac{1}{|\\mathcal S^k|}\\sum_{j\\in\\mathcal S^k} (F_{j}(w_k)-F_{j}(z_{k+1/2})),$$\nwhere $\\mathcal S$ follows the notation in our Algorithm 1.\nThen the above derivation becomes\n$$\\begin{aligned}\n&\\mathbb{E}\\_{\\mathcal S^k}\\left[2 \\tau\\left\\langle\\frac{1}{|\\mathcal S^k|}\\sum_{j\\in\\mathcal S^k}(F_j(w_k)-F_j(z\\_{k+1/2})), z\\_{k+1}-z\\_{k+1/2}\\right\\rangle\\right]\\\\\\\\\n\\leq & \\mathbb{E}\\_{\\mathcal S^k}\\left[2 \\tau\\left\\\\|\\frac{1}{|\\mathcal S^k|}\\sum_{j\\in\\mathcal{S}^k}(F_j(w_k)-F_j(z\\_{k+1/2}))\\right\\\\|\\\\|z\\_{k+1}-z\\_{k+1/2}\\\\|\\right]\\\\\\\\\n\\leq & \\frac{\\tau^2}{\\gamma} \\mathbb{E}\\_{\\mathcal S^k}\\left[\\left\\\\|\\frac{1}{|\\mathcal S^k|}\\sum_{j\\in\\mathcal S^k}(F_j(z\\_{k+1/2})-F_j(w_k))\\right\\\\|^2\\right]+\\gamma \\mathbb{E}\\_{\\mathcal S^k}[\\\\|z\\_{k+1}-z\\_{k+1/2}\\\\|^2]\\\\\\\\\n= & \\frac{\\tau^2}{\\gamma} \\frac{1}{|\\mathcal S^k|^2}\\mathbb{E}\\_{\\mathcal S^k}\\left[\\sum_{i,j\\in\\mathcal S^k}\\\\|F\\_{i}(z\\_{k+1/2})-F\\_{i}(w_k)\\\\|\\\\|F_j(z\\_{k+1/2})-F_j(w_k)\\\\|\\right]+\\gamma \\mathbb{E}_k[\\\\|z\\_{k+1}-z\\_{k+1/2}\\\\|^2]\\\\\\\\\n= & \\frac{\\tau^2}{\\gamma}\\frac{1}{n^2}\\sum\\_{i,j=1}^n\\\\|F\\_{i}(z\\_{k+1/2})-F\\_{i}(w_k)\\\\|\\\\|F_j(z\\_{k+1/2})-F_j(w_k)\\\\|+\\gamma \\mathbb{E}_k[\\\\|z\\_{k+1}-z\\_{k+1/2}\\\\|^2]\\\\\\\\\n\\leq & (1-\\alpha)\\gamma\\\\|z\\_{k+1/2}-w_k\\\\|^2+\\gamma \\mathbb{E}_k[\\\\|z\\_{k+1}-z\\_{k+1/2}\\\\|^2] ,\n\\end{aligned}$$\n\nwhere we use independent uniform  sampling in the second equality and the stronger Lipschitz continuous condition $\\\\|F_j(u)-F_j(w)\\\\|\\leq L\\\\|u-w\\\\|$ for all all $u,w\\in\\mathcal{Z}$ and $j\\in [n]$ (corresponds to Assumption 3 in our paper) in the last inequality.\nUnfortunately, we obverse that the final upper bound cannot be sharpen even if we have introduced the mini-batch sampling like our method, which implies combining the EG method in Ref. [25] and the sampling [1] requires the more iteration numbers (more  communication rounds in distributed case). In contrast, our derivation in the equations on Line 482-484 show the proposed OG-based method can enjoy the benefit from the mini-batch sampling.\n\n**Combing Ref. [5] with node sampling**\n\nRef. [5] proposed SMMDA, which is based on the FBF framework. Noticing that Ref. [8] proposed TPAPP method by combining node sampling with the FBF framework in Ref. [5]. However, TPAPP cannot achieve the results like our SVOGS.\n\n1. TPAPP does not consider how to make the duality gap small in the general convex-concave case, which is addressed by SVOGS (see Table 2).\n\n2. For the measure of distance, the complexities of TPAPP depend on the setting of local iteration number $H$, which leads to its communication complexity and local gradient complexity cannot simultaneously be (near) optimal.\nIn contrast, our SVOGS method is simultaneously (near) optimal to all complexities (see Table 2). \n\n3. In addition, Table 3 shows SVOGS has better complexity to make the gradient small than TPAPP.\n\n**Unique characteristics of the algorithm**\n\nSee above discussions.\n\n**Datasets and hyperparameters in experiments**\n\nSee Author Rebuttal.\n\n**Rationality of Assumption 2**\n\nThe condition of bounded domain is common in the analysis of convex-concave minimax optimization (monotone variational inequality), e.g., Lemma 3 of [1] and equation (24) of [5]. And the practical problem (12) in our experiments indeed satisfies this assumption.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ujcgLTumZ6", "reviewer": "Reviewer_qmRX", "summary": "The paper studies distributed min-max optimization under the assumption of second-order data similarity, i.e. the hessians of the objectives at different nodes are close enough. For the classes of (strongly)-convex-(strongly)-concave functions with Lipschitz gradient, lower complexity bounds are proposed. Moreover, an algorithm SVOGS is proposed that strictly reaches the lower bounds in communications and up to a logarithmic factor in local gradient calls. Therefore, the paper almost closes the gap in distributed centralized min-max optimization with data similarity.", "questions": "I did not find the difference between the number of communication rounds and communication complexity. It seems that Algorithm 1 sends the same amount of information at each communication round. So why is communication complexity different from the number of communication rounds?", "limitations": "The work is theoretical and does not have negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The problem, assumptions and results are clearly stated.\n2. An algorithm optimal in communications and near-optimal in gradient calls is proposed. That closes the complexity gap for the class of distributed min-max optimization problems with second-order similarity.\n3. Overall, the paper has a readable structure.", "weaknesses": "There still remains a gap in the local gradient calls complexity. Maybe it can be overcome with the usage of gradient sliding technique.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Why is the communication complexity different from the number of communication rounds?**\n\nRecall that the communication complexity in our paper refers to the overall volume of information exchanged among the nodes.\nWe take the convex and concave case as an example (Theorem 1) to explain why the communication complexity is different from the number of communication rounds.\n\n1. The results of Theorem 1 (discussion in Line 147-177) shows we require the communication rounds of $K={\\mathcal O}(\\delta D^2/\\varepsilon)$ to achieve the desired accuracy $\\varepsilon$.\n\n2. We requires the communication complexity of ${\\mathcal O}(n)$ to achieve $F(z^0)=\\frac{1}{n}\\sum_{i=1}^n F_i(z^0)$ in initialization.\n\n\n3. The index set ${\\mathcal S}^k$ with $|{\\mathcal S}^k|=b$ means the term of sums in Line 6 of Algorithm 1 takes the communication complexity of ${\\mathcal O}(b)={\\mathcal O}(\\sqrt{n})$ at each iteration.\n\n4. The communication for the full gradient term $F(w^{k-1})$ in Line 6 of Algorithm 1 does not need to be performed at every iteration. \nNotice that Line 10 performs $w^{k+1}=z^{k+1}$ with probability $p=\\Theta(1/\\sqrt{n})$ and performs $w^{k+1}=w^{k}$ (no communication) with probability $1-p=1-\\Theta(1/\\sqrt{n})$, \nwhich means only the case of $w^{k+1}=z^{k+1}$ needs to communicate to achieve the full gradient with the communication complexity of ${\\mathcal O}(n)$.\nTherefore, the overall the expected communication complexity related to the full gradient term is ${\\mathcal O}(pn)={\\mathcal O}(\\sqrt{n})$ at each iteration.\n\nBased on above analysis, we can conclude the overall communication complexity is \n$$ n + {\\mathcal O}(b+pn)K = {\\mathcal O}(n+\\sqrt{n}\\delta D^2/\\varepsilon),$$\nwhich is different from the communication rounds \n$$K={\\mathcal O}(\\delta D^2/\\varepsilon).$$\n\n\nIn addition, the full participation methods (e.g., EG [24], SMMDS [5] and EGS [25]) requires the communication for the full gradient at every iteration, which leads to the more expensive communication complexity of ${\\mathcal O}(n\\delta D^2/\\varepsilon)$.\n\n**There still remains a gap in the local gradient calls complexity. Maybe it can be overcome with the usage of gradient sliding technique.**\n\nThe comparisons in Table 1-2 show the local gradient calls complexities in our results match the lower bounds up to logarithmic factors. \nWe thank the reviewer for pointing out that the gap of logarithmic factors could possibly be overcome with the usage of the gradient sliding technique. We believe this is an interesting future direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fD1Xj5rltA", "reviewer": "Reviewer_DkHm", "summary": "The paper proposes SVOGS, and improved algorithm for distributed minimax optimization by client mini-batch sampling and gradient variane reduction. Theoretical rates on communication complexity and gradient computations are provided, along with their lower bounds. The analysis shows that SVOGS achieves the corresponding lower bounds. A numerical example is provided to justify the efficacy.", "questions": "See above", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The presentation is clear and the notations are clean. \n\n2. The paper is theoretically solid, with comprehensive thereotical results. The lower bounds, although based on some tricks and results from prior works, provide novel contribution to the field of minimax optimization.", "weaknesses": "The main drawback is the experiment section. The proposed method is only tested on one small dataset, and the paper lacks the basic information on how SVOGS is implemented and tuned (e.g., parameter $b, p, \\alpha, \\gamma$ in Algorithm 1). It seems to me that the proposed method requires much heavier fint-tuning than prior methods thus less practically convenient. The implementation details should be provided to justify the true practical value of this method. \n\nAlso, it should be tested on more datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**The implementation details**\n\nWe tune the step-size $\\eta$ of SVOGS from $\\\\{0.01,0.1,1\\\\}$. The probability $p$ is tuned from $\\\\{p_0,5p_0,10p_0\\\\}$, where $p_0=1/\\min\\\\{\\sqrt{n}+\\delta/\\mu\\\\}$. The batch size $b$ is determined from $\\\\{\\lfloor b_0/10\\rfloor,\\lfloor b_0/5\\rfloor,\\lfloor b_0\\rfloor\\\\}$, with $b_0=1/p_0$.  \n\nWe set the other parameters by following our theoretical analysis. \nWe set the average weight as $\\gamma=1-p$.\nFor the momentum parameter, we set $\\alpha=1$ for convex-concave case and $\\alpha=\\max\\\\{1-\\eta\\mu/6,1-p\\eta\\mu/(2\\gamma+\\eta\\mu)\\\\}$ for strongly-convex-strongly-concave case, where we estimate $\\mu$ by $\\max\\\\{\\lambda,\\beta\\\\}$ for problem (13). For the sub-problem solver, we set its step-size according to the smoothness parameter of sub-problem (2), i.e., $1/(L+1/\\eta)$. \n\nIn addition, we estimate the smooth parameter $L$ and the similarity parameter $\\delta$ by following the strategy in Appendix C of Ref. [5]. \n\nBased on above appropriate setting, our SVOGS achieves better performance than baselines. We are happy to provide the detailed parameters setting in our revision.\n\n**It should be tested on more datasets**\n\nWe have provided additional experimental results on datasets w8a ($N=49,749$, $d'=300$) and covtype  ($N=581,012$, $d'=54$). Please refer to the PDF file in Author Rebuttal. We can obverse the proposed SVOGS performs better than baselines on these datasets. We are happy to involve the additional experimental results into our revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their appreciation of our work. 

Both Reviewer Vpvu and Reviewer DkHm have raised questions about experiments. We provide the response as follows.

**The implementation details (hyperparameters)**

We tune the step-size $\eta$ of SVOGS from $\\{0.01,0.1,1\\}$. The probability $p$ is tuned from $\\{p_0,5p_0,10p_0\\}$, where $p_0=1/\min\\{\sqrt{n}+\delta/\mu\\}$. The batch size $b$ is determined from $\\{\lfloor b_0/10\rfloor,\lfloor b_0/5\rfloor,\lfloor b_0\rfloor\\}$, with $b_0=1/p_0$.  

We set the other parameters by following our theoretical analysis. 
We set the average weight as $\gamma=1-p$.
For the momentum parameter, we set $\alpha=1$ for convex-concave case and $\alpha=\max\\{1-\eta\mu/6,1-p\eta\mu/(2\gamma+\eta\mu)\\}$ for strongly-convex-strongly-concave case, where we estimate $\mu$ by $\max\\{\lambda,\beta\\}$ for problem (13). For the sub-problem solver, we set its step-size according to the smoothness parameter of sub-problem (2), i.e., $1/(L+1/\eta)$. 

In addition, we estimate the smooth parameter $L$ and the similarity parameter $\delta$ by following the strategy in Appendix C of Ref. [5]. 

Based on above appropriate setting, our SVOGS achieves better performance than baselines. We are happy to provide the detailed parameters setting in our revision.

**More datasets**

We have provided additional experimental results on datasets w8a ($N=49,749$, $d'=300$) and covtype  ($N=581,012$, $d'=54$). Please refer to the PDF file in Author Rebuttal. We can obverse the proposed SVOGS performs better than baselines on these datasets. We are happy to involve the additional experimental results into our revision.

Meta-review: This paper studies convex-concave minimax problems in distributed settings, focusing specifically in settings where the instance satisfies a second order similarity bound. This latter condition refers to an upper bound on the Hessian of the difference between all pairs of objectives within the finite sum. Under such assumption, it is shown that algorithms converge with improved rates, compared to those which simply quantify convergence with smoothness (it should be mentioned that the rates under second-order similarity are never worse than those based on smoothness, from the fact that $L$-smoothness implies $2L$-similarity). The paper also provides matching lower bounds.

Reviewers were mostly positive about this submission. However, it appears that the technical contributions of this work are somewhat marginal:

1. The idea of using gradient sliding appears in [5], and the idea of subsampling nodes is quite standard in distributed optimization.
2. The lower bound is also an adaptation of [42] which is by now quite standard.

Furthermore, the property of Hessian similarity is quite strong. Despite these concerns, and due to the mostly positive assessment of the work, I recommend acceptance.
Decision: Accept (poster)