Optimal Algorithms for Decentralized Stochastic Variational Inequalities
Authors: Dmitry Kovalev
Aleksandr Beznosikov
Abdurakhmon Sadiev
Mikhail Persiianov
Peter Richtárik
Alexander Gasnikov
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex optimization
variational inequalities
stochastic optimization
saddle point problems
decentralized optimization

Abstract: Variational inequalities are a formalism that includes games, minimization, saddle point, and equilibrium problems as special cases. Methods for variational inequalities are therefore universal approaches for many applied tasks, including machine learning problems. This work concentrates on the decentralized setting, which is increasingly important but not well understood. In particular, we consider decentralized stochastic (sum-type) variational inequalities over fixed and time-varying networks. We present lower complexity bounds for both communication and local iterations and construct optimal algorithms that match these lower bounds. Our algorithms are the best among the available literature not only in the decentralized stochastic case, but also in the decentralized deterministic and non-distributed stochastic cases. Experimental results confirm the effectiveness of the presented algorithms.

Optimal Algorithms for Decentralized Stochastic Variational Inequalities
Dmitry Kovalev KAUST, Saudi Arabia dakovaleev@@gail. com
Aleksandr Beznosikov
MIPT HSE University and Yandex, Russia anbeznosikov@gmail. com
Abdurakhmon Sadiev MIPT, Russia sadiev. aa@phystech. edu
Michael Persiianov
MIPT, Russia
persiianov mwipphystecchh.mmmmmmmmmmmm edu
Peter Richtárik KAUST, Saudi Arabia
Alexander Gasnikov
MIPT, HSE University and ITTP RAS! Russia gasnikov@yandex.rg
peter retee.riihtarrikkkasst edu.sa
Abstract
Variational inequalities are a formalism that includes games, minimization, saddle point, and equilibrium problems as special cases. Methods for variational inequali- ties are therefore universal approaches for many applied tasks, including machine learning problems. This work concentrates on the decentralized setting, which is increasingly important but not well understood. In particular, we consider decen- tralized stochastic (sum-type) variational inequalities over fixed and time vvrying networks. We present lower complexity bounds for both communication and local iterations and construct optimal algorithms that match these lower bounds. Our algorithms are the best among the available literature not only in the decentralized stochastic case, but also the decentralized deterministic and non-distributed stochastic cases. Experimental results confirm the effectiveness of the presented algorithms.
Introduction
Variational inequalities broad and flexible class of problems that includes minimization, saddle point, Nash equilibrium, and fixed point problems as special cases; see [24] [ for an introduction.
Over the long history of modern research on variational inequalities spanning at least half a century, the community developed their own methods and theory, differing from the approaches in their sister field, optimization. The ExtraGradient MirrorProx methods due 33 foundational standing in the variational inequalities field that gradient descent occupies in the optimization literature. As in the case of gradient descent, many modifications [31 and variants [66] of these methods were proposed and studied in the variational inequalities literature.
[50] 3
have a similar
"King Abdullah University of Science and Technology 1 Moscow Institute Physics and Technology Institute for Information Transmission Problems RAS
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Applications of variational inequalities
In recent years, there has been significant increase research activity in the study of variational inequalities due to new connections to reinforcement learning [58] 32] adversarial training 44], and
GANs [28] particular, [21 26 47
20
42 60 show that even one considers the classical (in
the variational inequalities literature) regime involving monotone and strongly monotone inequalities, it is possible to obtain insights, methods and recommendations useful for the GAN community.
In addition to the above modern applications, and besides their many classical applications in applied mathematics that include economies, equilibrium theory, game theory and optimal control ( variational inequalities remain popular in supervised learning (with non-separable loss [3]; with non- separable regularizer [3),, unsupervised learning (discriminative clustering [6);; matrix factorization
4.). image denoising 22 18]
robust optimization [9] and non-smooth optimization via smooth
reformulations [56
1.2 Processing on the edge
With the proliferation of mobile phones, wearables, digital sensors, smart home appliances, and other devices capable of capturing, storing and processing data, there is an increased appetite to mine the richness contained these sources for the benefit of humanity. However, the same time, the traditional centralized approach relying on moving the data into single proprictary warchouse for processing via suitable machine learning methods is problematic, and new modus operandi is on the rise: processing the data at the source, on the edge, where it was first captured and where it is by the client's devices that own the data. There are many reasons for a gradual shift in this direction, including energy efficiency and data privacy.
stored (37 46 35
key necessary characteristic for any viable algorithmic approach to work in such massively decentralized regime is the ability to support decentralized processing reflecting the fact that the devices are connected through network of a potentially complicated topology, possibly varying in time. A central authority may be absent in such a system, and the methods need to rely on communication patters that correspond the existing connection links.
1.3 Decentralized algorithms for variational inequalities
In this paper we study
algorithms for solving variational inequalities over decentralized communication networks.
In this regime, number of nodes (workers, devices, clients) are connected via communication network, represented by a graph. Each node can perform computations using its local state and data, and is only allowed to communicate with its neighbors in the graph.
Decentralized algorithms over fixed communication networks find their applications in sensor net- works [1], network resource allocation [ cooperative control 277,, distributed spectrum sensing
7 power system control [55] and, of course, in machine learning (53) Recently, decentralized
methods over time-varying networks have gained particular popularity due to their relevance to federated learning 337 35 where communication failures between devices are common problem.
Decentralized minimization methods are well studied optimal algorithms for such problems are known in the fixed network topology regimes.
49
36
In particular, lower bounds and and time-varying 39 63 30
However, in significantly more general and hence potentially much more impactful formalism of variational inequalities, the question of optimal and efficient decentralized methods is still open.
Motivated by these considerations, our work is devoted to advancing the algorithmic and theoretical foundations of decentralized variational inequalities, in both the fixed and varying network regimes.
1.4 Our contributions and related work
We now briefly summarize our main contributions.
(a) Lower bounds

---

We present the first lower bounds for the communication and local computation complexities of decentralized variational inequalities in the stochastic (finite sum) case, in both the fixed and time-varying network topology regimes. See Table 1
Existing literature contains lower bounds for non- oon-distri finite-sum variational inequalities 20 which we recover as special case. Existing literature also contains lower bounds for deterministic decentralized variational inequalities in the fixed [13 and time-varying [2] regimes. Our bounds
covers these results too. See Table 2 (Appendix
(b) Optimal decentralized algorithms
We construct four new algorithmss for stochastic (finite sum) decentralized variational inequali- ties: two for fixed networks, and two for time-varying networks. Two of these algorithms match our lower bounds, and are therefore optimal in terms of communication and local iteration complexities. These are the first algorithms for stochastic (finite sum) decentralized variational inequalities over fixed and time-varying networks. See Table L
Moreover, our results offer linear communication complexity for deterministic decentralized strongly monotone variational inequalities, which is an improvement upon the sublinear results of 14 IK 10 12 Additionally, our algorithms have better guarantees on local computations than the methods
developed by 2 See Table 2 (Appendix
Let us also single out a number of works on decentralized saddle point problems or VIs which are not suitable for comparison with our results: [67 5 consider non-monotoonemiinty) problems, 45 does
not prove convergence, 4 assumes data homogeneity, and + considers a discrete problem.
Table I: Summary of upper and lower bounds for communication and local computation complexities for finding an s-solution for strongly monotone stochastic (finite-sum) decentralized variational inequality over fixed and varying networks. Convergence is measured by the distance to the solution.
Reference
Communication complexity
Local complexity
Weaknesses
Multheijee and Chakmbbrrt
log
ax à 2d log $
wenk communictiion ratos weak local computation mites
Rezosillww (12)
(Vx log" +)
(1 log Jobu log
multiple gossip no linear convergence
Beznosikov et al.
R
o (vx lox" !)
o (n los !)
multiple gossi no linear convergence
Rogozin
25
(vx kog +)
< (n//x kog
weak local computation
Alle
popprr)
(meelv/ni vT & Ioc #) 10
(max)(//s vxl log
Alc
Alg
chis paper)
0 (v*x log t)
0 (Vi 6 log 2)
multiple gossip
Lower
Beznosikov al.
8 <( (vx3 lox
0 (5: los !)
Thm
paper)
2 (vV7 log
(VT log #)
Beznoskkov at al.
10
o (x log x
(wxx log 1 + mx AA
Dr homogeneity no linear exuvereeee
Time- varying
Upper
Beznosikov al.
(x log' !)
a & los 1) (maxly/Fxx1 lox
multiple linear convergesse
Alg.
puper)
o [ixx log :) cun
Alp.
Eig
this paper)
o (x log t clio
o (VT log +) ""
maltiple gossip
Lower
Beznosikor al.
8 (x lox!)
a (1. lox
This puper)
8 (x !)
(VT log !)
41 for saddle point problems; 12) deterministic; ()) stochastic, but finite sum; 19: convex- concave (monotone) case (we re- analyzed for strongly monotone case); R-connected graphs [11 are also considered. For simplicity comparison with other works, we put B = I. To get estimates for B o 1, one noed to change x to Bx: can include additional factors such as n log }. log L. for full complexities, see details in Section 4
Notation: μ = constant of strong monotonicity of operator F, L= Lipschitz constants of Lmn,, X characteristic number of the network Assumptions und 2.4] size of the local datuset.
(c) Optimal non-distribuued//enttaaiiad algorithms
We believe is notable that despite the generality of our setup and algorithms, our results, when specialized to handle this simpler case, improve upon the current state-of-the-art results in the non-distribbute//cnnaaliiii setting. In particular, unlike existing methods, our algorithms support batching: while the complexity of the best available algorithms grows with the batch size, our algorithms are not sensitive to this. This property is of crucial importance when working in the See Table (Appendix G
large batch mode, which is used in the practice [6 7 Z1.
3

---

(d) Experiments
Numerical experiments bilinear problems and robust regression problems confirm the practical efficiency of our methods, both in the non-distributed stochastic setup and in the decentralized deterministic one.
2 Problem Setup and Assumptions
We write (x, : =;= Jitli to denote the standard inner product of vectors æ, y E RR, where Iy corresponds to the i-th component of x in the standard basis in R This induces the standard (2-norm in I in the following way: || := V(z,z).
x). To denote the Kronecker product of two matrices A E Rm and B R we use A & B E Rumxxn. The identity matrix of size denoted by I.. We write in] == f1.2..... ................................ n). N the set of positive integers.
2.1 Variational inequality
We study variational inequalities (VI) of the form
Find z" E *Rd such that (F(="), 2²) + ((()) 0, Ve R
where F Rd TRd is an operator, and g Rdd - U [+oo) convex function. We also assume that g is proximal friendly, i.e. the computation of the operator prox, pg (z) arg mingeRR (3)(3) + & y - = (with p > 0) is done for free or costs very low.
proper lower semicontinuous
To showcase the expressive power of the formalism we now give a few examples of variational inequalities arising in machine learning.
Example 1 [Convex minimization). Consider the convex regularized minimization problem:
min f()) g(),, =E
where f is typically a smooth data-fidelity term, and g possibly nonsmooth regularizer, we define F(:) = (=).,. then it be proved that =' dom g is solution for ① if and only if =* dom g is a solution for @ So, the regularized optimization problem 2 can be cast as a VI (
While minimization problems are widely studied in separate literature, the next class of problems is much more strongly tied to variational inequalities.
Example 2 [Convex-concave saddles). Consider the convex-concave saddle point problem
min max f(x y) + 91 (x) - g2(v), *ER*> yERdy
where 91 and 92 can also be interpreted as regularizers. If we let F(z) == F(x, y) [V=f(z,)), V of y)] and 9(2) g(z, y) 91 g then it can be proved that 2" E dom a solution for if and only if 2 E dom g is a solution for 3 So, convex-concave saddle point problems can be cast as VI II..
Saddle point problems are strongly related to variational inequalities. In particular, lower bounds for the former are also valid for the latter. Moreover, upper bounds for variational inequalities are valid for saddle point problems. However, what is perhaps more important is that these lower and upper bounds match. This is in contrast to minimization, where the lower bounds are weaker.
2.2 Decentralized variational inequalities
We consider the decentralized case of problem ①I. namely assume that F is distributed across M workers,
F(z) = Σ (2).
(4)
while each Fm : Rdd - IRd. m [M], has the finite sum structure
Fm.(2).
(5)
The data deseribing Fm being stored on worker m. For example, Fm, can correspond the value of the operator the äth data point of the m-th dataset.

---

2.3 Assumptions
Assumption 2.1 (Lipschitzness). Each operator Fm is L-Lipschitz continuous, i.e. for all u, R we have |l (u) - Fm (v)ll S L| v/|.
Further, the collection of operators is L-average Lipschitz continuous, i.c., for all u, U E E it holds E (m)) (m) L" I|u ell?.
In the context of 2 and 3 L-Lipschitzness of the operator means that the functions f(x) and [z, y) are L-smooth.
Assumption 2.2 (Strong monotonicity). Each operator Fm is j-strongly monotone, i.e., for all u, U. E I
we have (u) (.) (v); v) 2 uullu -ul?.
In the context of 2 and B strong monotonicity of F means strong convexity of f() and strong convexity-strong concavity of f(r,y).
2.4 Communication and gossip
Typically, decentralized communication realized via gossip protocol [68 15 50
which is merely
matrix- multiplication with gossip matrix W, described below, which is different in the fixed and time-varying cases. Let {z (Z1,...., Fad) (RR)) =.... RM be the consensus space.
Assumption 2.3 (Fixed network 633 For a fixed network, communication can be modeled via an undirected connected graph, G (V, E), where V = [n]] are vertices (workers) and & = ((,,)) j e }} are edges. Note that (f,j) E & if and only if there exists communication link between agents and j. The gossip matrix W satisfies the following three assumptions: 1) W is symmetric positive
semi-defniit;; 2) kerW 3 L: 3) W supported on the vertices and edges of the network only:
wi, # 0 if and only if = j or (i,j) E E.
To characterize the matrix W, which captures the properties of the network, we denote Amax (W) = 1 the maximum eigenvalue of W, A (W) as the minimum positive eigenvalue of W, and the characteristic number X = Amax (W)/A min (W)= = 1/\tiin
Assumption 2.4 (Time-varying network [51]. )) For a time-varying network, at any moment f, com- munication network can be modeled E() = {(i,j) j E V} are directed edges. B-connectedness means that for any time t, the graph (t(t) with the set of edges U E(t) is connected. To describe the gossip protocol for time-varying case, we define the multi-consensus gossip matrix
directed B--conectted graph, G(t) = E()), where
4TT-1
Wl(1) = LM
II W(7). T=E
(6)
One can also observe that multiplication with the matrix WT requires to perform multiplication with T gossip matrices Wt)).... W(t tt T - 1). i... it requires T decentralized communications. We further assume that the gossip matrices ((t) (for G(t)) and Wp (t) satisfy: 1) W supported
on the nodes and edges of the network: (t) * 0 if and only if i = j or (i.j) E E(t); 2)
kerW (1) L: range (1) C {z (Rd)a EM Am 0}: 4) there exists a characteristic
number x such that [[a(()= 2|1 < (1 x >||=| for all E range W (t))..
3 Lower Bounds
Our lower bounds apply specific class of algorithms which are, loosely speaking, allowed to communicate with neighbors, and compute any local first-order information. We now give formal definition.
Definition 3.1 (Oracle), Each agent vn has its own local memory Mn with initialization M,, = {0}. Mm is updated as follows. At each iteration, the algorithm either performs local computations or communicates.
Local computation: At each local iteration, device m can sample uniformly and independently batch S., of any size b from (Fm,i) and adds to its Mm finite number of points z, satisfying
span (2', Eimes Fm (2"), proxps (span {2" Eimes,, Fm (an.a((2") (z")))}
5

---

for z', 22, ,2" E Mm and p 0. Such call needs local computations to collect the batch. Batch of size n represents Fm:
Communication: Upon communication rounds among the neighboring nodes, and at communica- tion time I, Mm is updated according to
Mm == span {Ul.m)eeco M.}.
(8)
Output: The final global output is calculated as & E span {Um- Mm {
The structure of the above definition is typical for distributed lower bounds 633 and for stochastic lower bounds 30). In particular, Definition 3.1 includes all the approaches for working with stochastic problems, such as SGD or variance reduction techniques (SVRG, SARAH). Note that while algorithm invoke the deterministic oracle (full Fm)) in local computations, in the work lower bounds the re-distributed case [29]. there no such possibility. This narrows the class of algorithms for which results of [29] are valid. In particular, they can not do SVRG-type updates.
Theorem 3.2 (Lower bound fixed network). For any L Z > and X > 1. n E and K, N E N, there exists decentralized variational inequality (satisfying Assumptions 2.7 2Indd 2.2 H (where is sufficiently large) with z' + over a fixed network (satisfying Assumption 2.3 with a gossip matrix W and characteristic number X. such that for any output 2 of any procedure (Definition 3.1 with K communication rounds and N local computations, it holds that Eill & 2 201 is
Ω exp
80
K VX
RB
and Ω
exp
16
N
R
1+
21
2n
+
where Rg 11:0 112 and I
V
Corollary 3.3. In the setting of Theorem computations required to obtain an c-solution (in expectation) is lower bounded by
3.2 the number of communication rounds and local
Ω (vV (1((1+)))
loog
[1 )= and Ω ((nnnvninn
log
n2
respectively.
Theorem 3.4 (Lower bound time varying network). For any L 2 0 and > 3, n E N and K. N N, there exist a decentralized variational inequality (satisfying Assumptions Aand 2.2 on Rd (where d is sufficiently large) with x" + O over time-varying network (satisfying Assumption 2.4 with a sequence of gossip matrices (t)) and characteristic number X, such that for any outpur of any procedure (Definition 3.1 with K commmnication rounds and N local computations. it holds that E[[l2 -=- [1]
Ω exp (T
64
K Bx
RB
and Ω
exp
16
N
R
-1)
2n
where
R3 |1:0 1|2 and I V
Corollary 3.5. In the setting of Theorem 3.4 the number of communication rounds and local computations required to obtain an E-solution (in expectation) lower bounded by
2 (Bx (1
Ri
and Ω ((n /n log
loog
respectively.
See proof's for Theorems 3.2 and 3.4 in Appendix C The proof uses the idea (example of bad functions) of con-distributed deterministic lower bounds from 72 This idea is further extended to distributed stochastic VIs.
Note that in the time-varying case, the lower bounds for communication differ by the constant B from the estimates that were previously encountered in the literature [12] This is due to the fact that we consider a more general setup with R-connected graph (see Assumption while the existing literature lower bounds focuses on the simpler B case.

---

4 Optimal Algorithms
Since in the decentralized gossip protocol each local worker yn stores its own 2m vector, we consider the problem
(9) where we use new notation: z (z MM) T and x² = (zi...., "T) T Additionally, here we introduce the lifted operator F: (Rd)M + (Rd) given as F(z) = (f), ...,, Far (#M)) and the lifted operator g ( + IR U { defined by g(z) = x2 Em=i g(m)).
Find z" ERR)) M such that (F(z"), (,z"),2 2 z²) ) + g(z) g(z") ) 2 O Vz E (R*)
One can note that 3 is set of M unrelated variational inequalities with their own variables. But the original problem ( 2²) + of (2) 9=]"" To eliminate this issue and move on to problem
+ is a sum of variational inequalities with the same variables:
it is easy to get the following modification of
Find z² E such that (F(z"), 2²) g(z) g(z") 2 0, Vz E C,
(10)
where L is the consensus space. Problem I0 is equivalent to ①
Due to Assumptions 2.1 and F is L-LLipschizz continuous, T-average Lipschitz continuous and s-strrngly monotone.
2.2
4.1
Fixed networks
We present Algorithm D for fixed networks. In Appendix we give discussion and intuition. In particular, we give the deterministic variant as well as the non-distributed version of Algorithm The next result gives the iteration complexity of Algorithm
Algorithm 1
Theorem 4.1 (Upper bound fixed net-
work). Consider the problem (TOp for
1: Parameters: Stepsizes 17, O, momentums a, 8, batchsize b E (1,..., n), probability p (0,1)
+ b under Assumptions 2. and
2: Initialization: Choose z w E (dom g)M, y
over a fixed graph G (Assumption
2.3 with a gossip matrix W. Let {z*} be the sequence generated by Algo- rithm 7 Twtt tuning of n. 0, a, B,y as described in Appendix D Then, given
C+. Put
z", w w", y
3: for 0, 1, 2... do
4: Sample j 1 mm,b independently from [n]
5: S ,
E > 0, the number of iterations for z² 2= i
6: Sample Jm.1 ,61//2 1...,Jmmb
k+1/2 independently from [r]
Eillz*
7: sk+ sk+1/2 1/2 = 1m
k+1/2
Jm.b 1/2
k-1/2
O
( +x+
+ Vob
1 II
Vx
log
8:
8t Ejes F (F,(z²)
F, FF((w=1)
See the proof in Appendix D Let discuss the results Theorem. First of all, we are interested in how to obtain the complexity of communications and local computations from iterative com- plexity. At each iteration we require (in average) O(b+ + pn) local computations, because we need to store batch b twice and with probability p we update the point w k+1 w+1 by z², this requires calcu- lating the full F in the next iteration. Then, as the optimal one can choose p b/n. Then with such choice of p we have the following local and communication complexities
+a F (2((( 1 (+F))(((2*-1)) -F,(tt + +F(w
9:
A 8hh (y aly -y²
10:
b+1 prox (xt +n(w* kk -2*) -)
11:
k++ 1/2 Ejett1// (F,(z*+1) ) (w
+ +F(
12:
ykt =y² 0(W & La) - 3(A 1+1/2 yk))
13: wh+1 {
with probability p
wh
with probability 1 1-p
14: end for
(z) (Fi.).())) ... FM. (T,
(EA)) 1
(L.....b)
([n +x + VnL + +/
log
and ([ b
vx log log
respectively (since each iteration Algorithm performs O(1) communications).
Hence, with = we have the complexities the same as Table Depending on max (VT; vx). we have the optimality of either local communications or decentralized communications, One can
7

---

note that it is enough to take b 2 L and guarantee the optimal communication complexity (see Corollary 3.3) but we have non-optimality in local iterations.
To make the algorithm optimal both in terms of communications and local computations, we need to slightly modify it. One can make it using Chebyshev acceleration (see Algorithm 3 Appendix Following 133.l. we can construct a polynomial P such that 1) P(W) is a gossip matrix, 2) multiplication by P(W) @ Ia requires (W) multiplications by W (i.e. vx (W) communication rounds) 3) (P())) f Then we can modify Algorithm by replacing W by P(W) and get
Sb) under Assumptions 2.1 2.2 a fixed connected graph 9 (Assumption 2.3 with a gossip matrix W. Let {z") } be the sequence generated by Algorithm I with Chebyshev polynomial P(W) gossip matrix and with tuning of 17 8 a, B,7 as described in Appendix D iterations for E[[| z" z" [ < E is
Theorem 4.2 (Upper bound fixed network). Consider the problem TO (or
Then, given > 0, the number of
o (
1 vpb 1
log 1
In this case, the communication complexity of one iteration is X. and the local complexity (in average) still O( + pn). Then with p = 1/n we get the following local and communication complexities
o ([ [[ vn + b log )
and O ([vx++
+ vX los
respectively. To get optimal results from Table
1 we just need to take b = T./i/1..
Algorithm 2
In contrast to algorithms of E 33
(the closest papers in theoretical con-
1: Parameters:
Stepsizes Ny. n2 0 > O, momentums a, T, parameters v, v, batchsize b E n..
vergence), our Algorithm | needs
multi-consenuusShhebyeyee accelera- tion for both optimal rates. but can work without these additional proce- dures. Algorithms [4 [3] requires
probability E 10,
2: Initialization: Choose z0 w E (dom g) y E
(R') x" L Put z- 2", w w yf y = x =
x", my M
(Vx Vogo 1)) iterations for Cheby- shev acceleration, which makes the al- gorithms less practical.
3: for k = 0.1.2... do
4: Sample Im.
sm, independently from [m] 5: 5 = Um. It.
4.2 Time-varying networks
6: Sample Jm, k+1/2
independently from [n] ..... Jmbb
k+//2
7:
gk+1/2 1/2 = 1m
1+1/2 ..... Jm.b
1/2
We present Algorithm for time- varying networks. It needs to compute WT using (6. it requires T communi- cations. In Appendix B we give a dis- cussion and intuition of this algorithm. The next result gives the iteration com- plexity of Algorithm 2
8:
8t
F (F,(z²) EEES
Fy F (w"-11)
+a F (2 - F)((a-111) + +F(w
9:
A = 8h - vz yh alyx - -y
10:
z ++ = prox, 1:8 (x + w( w(wk =xt) - -1)=
11:
ye = Ty + (1 - -)
Theorem 4.3 (Upper bound - time varying network). Consider the prob- lem TT) (or
12:
x xx* * + (1 x)x
① + (5) under Assump-
13:
A = v-' 1 (y- + xx² + z b+] + 7(x* + xx + vz
tions 2.7 and 2.2 over a sequence of time- varying graphs G(k) (Assumption
14:
gk+1/2 $ jjsstti/ (F, - Ff(w*()
+ +F(wk)
2.4 with gossip matrices (k). Let be the sequence generated by Algorithm 2 with T 2 B and tun- ing of parameters as described in Ap- pendix D Let the choice T T guaran- tees contraction property (Assumption 2.4 point 4) with xT). Then given
15:
A -ー -yy + xt) + 3x* + 1/-11/2)
16:
y x+1 = yh -
17:
x ++1 = x² (Wr(T)) 2 (E + m²)
18:
m x+I 7 A + m
(Wr(Tk) (n + m²)
19:
y k+1
f yh + T(y
O. the number of iterations for
20:
X
k+l x ((Wr(TT)) & La + +x{)
El|l
< is k -x-11 -2'
2 with probability p
21: w k+1 =
δ (x((T)+ + x + 11)
w with probability 1 1-2
Vbp
22: end for
8

---

Note that an important detail of the method is that T > B. This limitation is due to the fact that network B-connected. In particular, for B > 1 can happen that in some communications use empty graphs. Therefore, the requirement T 2 B is natural to guarantee the contraction property (Assumption 2.4, point 4). This means that B > 1 we have to use multi-consensus (6)
let us this case first. The same way as in fixed graph case we choose p = 1/n. Then we get the estimates on communications and local calls
But with B = T' = 1, we can avoid
o (xx²+ +
V L 1
log 1
If we put = 1, we have the same estimates as in Table !
Now consider general case with any B. We multi-gosssp step and take T 1. In particular, let us choose T = [x In 21. Than using O and point 4 of Assumption 2.4 we can guarantee that [ z1I < } ||=1|² Therefore, (T) 2, but we need T communications per iteration. With p n/ and 6 Ly//L, the iteration complexity from Theorem 4.3 can be rewritten follows
o ([1
VOL Z
log log
Using that per iteration we make O(B [x 21) communications and (Iv///L) local computations, we get
([ VTL + x log
commn-s and O [[n+ Ly
L + v log ! local calls.
These results are reflected in Table
5 Experiments
We now perform several experiments with the goal of corroborating our theoretical results. Note though that are the first who consider the decentralized stochastic (finite-sum) setting for VIs, and hence there are no competing methods. Therefore, we compare the non-distributed finite sum setting and decentralized deterministic setting separately.
5.1 Variance reduction
In this section, we compare the main methods for solving strongly monotone non con-distributed stochastic (finite-sum) variational inequalities with oi-diitribbted version of our Algorithm
Problem. We first consider bilinear problem:
min max 1 Σ x T A,y. yEAU 1m1
(1I)
where A is the unit simplex in Rdd We use the same experimental setup as in M. in particular consider policeman and burglar matrix from (54] and two test matrices from 55
Setting, For comparison, we took methods from Table 3] In particular, we chose EG-Alc-Alg1
Figure Comparison epach complexities Algo- rithm EG-Alc-Aig1, EG-Alc-Alg2 and EG-Car on
and EG-Alc-Alg2 from [I] EG-Car from [17] The parameters of all methods are selected in two ways: 1) as described in the theory of the corresponding papers, and 2) tuned for the best convergence. We run all methods with different batch sizes. The comparison criterion is the number of epochs (one full gradient epoch).
with matrix from [54]. Dashed lines give conver-
gence with theoretical parameters, solid lines with tuned parameters.
Results. The plots from Figure show that in the case of theoretical choice of parameters, our Algorithm is ahead of other methods for any batch size (including b b= 1). In the case of tuning parameters, the specialized method from
Ir is better than our algorithm. See more experiments with other matrices in Appendix

---

5.2 Decentralized methods
In this section, we compare the state-of th-the- methods for solving strongly monotone decentralized variational inequalities over fixed and time-varying networks with our Algorithms and 2
Problem. We now consider robust linear regression:
min max 1 Irllse N
Σ (w (2: + r2) yz) 2 |1w011 2/ 1r111
(12)
where wo are model weights, {(r,, W)) are pairs of the training data, r; are noise vectors, and and B are regularization parameters. The noises r; resist training the model, thereby inducing more robustness and stability.
Setting. For comparison, we took methods from Table 1 for decentralized problems over fixed and time-varying networks. In particular, we choose EGD-GT from 48. EGD-Con from T 12 and Sliding from [4]. Note that only EGD-Con has a theory for fixed and time-varying networks, despite this, we use all methods in both cases.
For a fair comparison, we consider the deterministic setup, i.e., each worker can compute full gra- dients. We take datasets from LiBSVM [I9] and divided unevenly across M 25 workers. For communication networks we chose the star, the ring and the grid topologies. For time-varying networks, the topologies remain the same, but the locations of the vertices in them change ran- domly. All methods are tuned for the best convergence. The comparison criterion is the number of communication rounds.
Figure 2: Comparison communication complexities of Algorithm I EGD-GT, EGD-Con and Sliding over fixed networks.
5.2.1 Fixed networks
Results. The plots from Figure 2 show that our Algorithm is ahead of other methods. Among other things, it is ahead of Sliding from [4. which has fast theoretical communication com- plexity. However, this happens when the dataset relatively homogeneous and uniformly di- vided across the devices. In our setting, this not the case. See more experiments with other datasets in Appendix F2.
5.2.2 Time-varying networks
Figure 3: Comparison communication complexities of Algorithm 2 EGD-GT, EGD-Con and Sliding on PP over time-van sene-varying networks.
Results. The plots from Figure 3 show that our Algorithm is ahead of other methods in the case of the grid network. In the case of the ring topology, EGD-Con shows the best results. Indeed, such an algorithm in fact implements centralized communications via decentralized protocol and this approach is not always the fastest, but reliable. See more experiments with other datasets in Appendix F2.2
Acknowledgments
This work supported by grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D730321 PP000002))) and the agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00133
References
[1] Ahmet Alacaoglu and Yura Malitsky, Stochastic variance reduction for variational inequality methods. arXiv preprint
2021.
10

---

[2] Ahmet Alacaoglu, Yura Malitsky, and Volkan Cevher. Forward-reflected-backe backward method with variance reduction. Computational Optimization and Applications. 80, 11 2021.
[3] Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Optimization with sparsity-inducing penalties. arXiv preprint arXiv: 108. 07750 2011.
[4] Francis Bach, Julien Mairal, and Jean Ponce. Convex sparse matrix factorizations. arXiv preprint arXiv:0812. 1869, 2008.
[5] Babak Barazandeh, Tianjian Huang, and George Michailidis. A decentralized adaptive mo- mentum method for solving a class of min-max optimization problems. Signal Processing, 189:108245, 2021.
[6] Heinz Bauschke and Patrick Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. 01 2017.
[7] Juan Andrés Bazerque and Georgios Giannakis. Distributed spectrum sensing for cognitive radio networks by exploiting sparsity. IEEE Transactions on Signal Processing..5(3))) 5883):1847- 1862, 2009.
[8] Amir Beck, Angelia Nedić, Asuman Ozdaglar, and Marc Tehoulle. An o (1/k) gradient method for network resource allocation problems. IEEE Transactions on Control of Network Systems, 1(1):64-73, 2014.
[9] Aharon Ben-Tal Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust Optimization. Princeton University Press, 2009.
[10] Aleksandr Beznosikov, Pavel Dvurechensky. Anastasia Koloskova, Valentin Samokhin, Se- bastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. arXiv preprint
2021.
[11] Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. arXiv preprint arXiv:2202.0777 07262, 2022.
[12] Aleksandr Beznosikov, Alexander Rogozin, Dmitry Kovalev, and Alexander Gasnikov. Near- optimal decentralized algorithms for saddle point problems over time-varying networks. Lecture Notes in Computer Science, page 246-20 257, 2021.
[13] Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle- point problems: Lower bounds, optimal algorithms and federated GANs. arXiv preprint drXiv:2010.13112,220 2020.
[14] Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Dis- tributed saddle-point problems under data similarity. Advances in Neural Information Processing Systems, 34, 2021.
[15] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Iransactions on information theory, 226))2200-22300 2006.
[16] Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. arXiv preprint
1106,, 2018.
[17] Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. arXiv preprint arXiv: 190..0207000666 2019.
[18] Antonin Chambolle and Thomas Pock. A first-ordes primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120-144 2011.
[19] Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions intelligent systems and technology (TIST), 2(3):1127, 2011.
11

---

[20] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien, Reducing noise in gan training with variance reduced extragradient. arXiv preprint arXiv:1904.088 085988 2019.
[21]
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv:1711.00144 2017.
[22] Ernie Esser, Xiaoqun Zhang, and Tony Chan. A general framework for class of first order primal-dual algorithms for convex optimization in imaging science. SIAM Journal on Imaging Sciences, 3(4):1015-1046, 2010.
[23] F. Facchinei and J.S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering. Springer New York, 2007.
[24] Francisco Facchinei and Jong-Shi Pang.
Variational Inequalities and Complementarity Problems. Springer Series in Operations Research. Springer, 2003.
[25] Lingwen Gan, Ufuk Topcu, and Steven Low. Optimal decentralized protocol for electric vehicle charging. IEEE Transactions Power Systems, 28(2):940-955 2012.
[26] Gauthier Gidel, Hugo Berard, Gačtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. variational inequality perspective on generative adversarial networks. arXiv preprint arXiv:1802.10551, 2018.
[27] Pontus Giselsson, Minh Dang Doan, Tamás Keviczky, Bart De Schutter, and Anders Rantzer. Accelerated gradient methods and dual decomposition in distributed model predictive control. Automatica, 49(3):829 0033899-33,,.,, 2013.
[28] Ian Goodfellow, Jean Bouget-Abadie Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems (NIPS), 2014.
[29] Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. arXiv preprint arXiv:2 08280, 2021.
[30] Hadrien Hendrikx, Francis Bach, and Laurent Massoulie. An optimal algorithm for decentralized finite sum optimization. arXiv preprint 20X.::2000..06675 2020.
[31] Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the con- vergence of single-call stochastic extra-gradient methods. arXiv preprint arXiv: 08465, 2019.
[32] Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 1 119, pages 4890-4900. PMLR, 2020.
[33] Thorsten Joachims. support vector method for multivariate performance measures. pages 377-384, 01 2005.
[34] Anatoli Juditsky, Arkadii S. Nemirovskii, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prec algorithm, 2008
[35] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.044 2019.
[36] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized sgd with changing topology and local updates. arXiv preprint Ttt::2003.10422 2020.
[37] Jakub Konečný. H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. NIPS Private Purti Machine Learning Workshop. 2016.
12

---

[38] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[39] Dmitry Kovalev, Elnur Gasanov, Peter Richtárik, and Alexander Gasnikov. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. arXiv preprini arXiv:2 106.04469. 2021.
[40] Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 33, 2020.
[41] Huan Li and Zhouchen Lin. Accelerated gradient tracking over time-varying graphs for decentralized optimization. arXiv preprint arXiv:2104.02555 2021.
[42] Tengyuan Liang and James Stokes. Interaction matters: A note non-asymptotic local convergence of generative adversarial networks. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 907-915. PMLR, 16-18 Apr 2019.
[43] Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jerret Ross, Tianbao Yang. and Payel Das. A decentralized parallel algorithm for training generative adversarial nets. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[44] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. International Conference on Learning Representations (ICLR). 2018.
[45] David Kateos-Núñer and Jorge Cortés. Distributed subgradient methods for saddle-poid problems. In 2015 54th IEEE Conference on Decision and Control (CDC), pages 1462-5467, 2015.
[46] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communicationn-eficceeen learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
[47] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv:1807.02629, 2018.
[48] Soham Mukherjee and Mrityunjoy Chakraborty. A decentralized algorithm for large scale max-max problems. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 2967-2972 2020.
[49] Angelia Nedic. Distributed gradient methods for convex machine learning problems networks: Distributed optimization. JEEE Signal Processing Magazine, 37(3):92-101, 2020.
[50] Angelia Nedić and Asuman Ozdaglar. Distributed subgradient methods for multi-agent opti- mization. IEEE Transactions on Automatic Control, 54(1):48-61, 2009.
[51] Angelia Nedich, Alex Olshevsky, and Wei Shi. A geometrically convergent method for dis- tributed optimization over time-varying graphs. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 1023-1029. IEEE, 2016.
[52] 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 251,, 01 2004.
[53] Arkadi Nemirovski. Prox-method with rate of convergence 0(1/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):22--251, 2004.
[54] Arkadi Nemirovski. Mini-course convex programming algorithms, 2013.
13

---

[55] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming, SIAM Journal on optimization, 19(4):1574- 1609, 2009.
[56] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 107(1): 2005.
[57] Yurii E Nesterov. A method for solving the convex programming problem with convergence rate (1/k* 2). In Dokl. akad. nauk Sssr, volume 269, pages 343-547, 1983.
[58] Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P. How, and John Vian. Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In Proceedings of the 34th International Conference Machine Learning (ICML), volume 70, pages 2681-2690. PMLR, 2017.
[59] Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle- point problems. In Advances in Neural Information Processing Systems, pages 1416-1424, 2016.
[60] Wei Peng, Yu-Hong Dai, Hui Zhang, and Lizhi Cheng. Training gans with centripetal accelera- tion. Optimization Methods and Software, 35(5)9955-973, 2020.
[61] M. Rabbat and R. Nowak. Distributed optimization sensor networks. Third International Symposium on Information Processing in Sensor Networks, 2004. IPSN 2004, pages 20-27, 2004.
[62] Alexander Rogozin, Alexander Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. arXiv preprint arXiv:2102.07755: 2021.
[63] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. arXiv preprint 17Xiv:1702.08704, 2017.
[64] Kunal Srivastava, Angelia Nedié, and Dušan Stipanović. Distributed min-max optimization in networks. In 2011 17th International Conference on Digital Signal Processing (DSP), pages 1-8, 2011.
[65] Vladislav Tominin, Yaroslav Tominin, Ekaterina Borodich, Dmitry Kovalev, Alexander Gas- nikov, and Pavel Dvurechensky. On accelerated methods for saddle-point problems with composite structure. arXiv preprint
2021.
[66] Paul Tseng, A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431-4466 2000.
[67] Wenhan Xian, Feihu Huang, Yanfu Zhang, and Heng Huang. A faster decentralized algorithm for nonconvex minimax problems. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 15865-258777 Curran Associates, Inc., 2021.
[68] Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems and Control Letters, 53(1))65-78, 2004.
[69] Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurmans. Maximum margin clustering. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2005.
[70] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduuee optimiza- tion for class of canconvex-nonconean minimax problems. arXiv preprint arXiv:2002.0662. 2020.
[71] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv: 1904009944 2019.
14

---

[72] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the saddle point problems. arXiv preprint arXiv:1912.07481, 2019.
[73] Chen Zhu, Yu Cheng, Zhe Gan, Siqi Sun, Tom Goldstein, and Jingjing Liu. Freelb: Enhanced adversarial training for natural language understanding. arXiv preprint arXiv:1909.11766 2019.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A], theoreti-
cal paper
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes], Section 2
(b) Did you include complete proofs of all theoretical results? [Yes]. Appendix C, D, E
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A], run simple experiments just for theoretical purpose, it is easy to rerun it
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]. all methods are tuned as in the theory original papers (c) Did you report error bars (e.g., with respect the random seed after running ex- periments multiple times)? [N/A], we run simple experiments just for theoretical purpose
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A], we simple experiments just for theoretical purpose, they require no computing power and can be run on any laptop
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] Section 5.2, we cite LibSVM
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "Za3yPrLtt-3", "reviewer": "Reviewer_LbuJ", "summary": "This paper studies decentralized stochastic variational inequalities (SVI). The authors present lower bounds for the communication and computation complexities of decentralized SVI. The authors construct new algorithms that achieve the optimal rates matching the lower bounds, for both fixed and time-varying networks.", "questions": "-", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper studies an interesting problem and the results seem solid and comprehensive. The writing and exposition can be improved to give more context and intuition to the readers. ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "U3p48Hsw8ef", "reviewer": "Reviewer_JEvK", "summary": "Methods for variational inequalities are applied to solve problems in optimization, machine learning, image processing, game theory, etc. This paper provides a lower complexity bound in communication and computation for decentralized stochastic variational inequalities under some conditions. Then optimal algorithms are proposed to match these lower bounds. This paper considers a strong monotone operator for which linear convergence is derived. ", "questions": "+ In the complexity, the term $n\\log{1\\over \\epsilon}$ is not included in the computation, and the term $\\sqrt{n\\chi}\\log{1\\over \\epsilon}$ is not included in the communication (they are both in Theorem 4,2). When $\\sqrt{n}\\geq {L\\over \\mu}$, this term can not be ignored. \n+ It seems that the difference between Algorithm 4 and the algorithms in [1] is not just in the gradient estimator. In [1], the extragradient requires two proximal operators in each iteration, while the FBF has different update orders in the iteration. Since the non-distributed case is also interesting, it would be better to have more discussion in the supplementary material.    ", "limitations": "+ The parameter for the algorithm requires the strong convexity constant, which may not be easy to obtain. It may limit this algorithm's application for many nonconvex machine learning problems. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The lower bound in the complexity is provided. In general, finding the lower bound is not easy. \n+  Optimization algorithms are proposed to match the lower bound. \n\nWeakness\n+ The strong assumption may limit the vast application of the proposed algorithms. It requires strong monotonicity for the convergence of the proposed algorithms. Is it possible to show the convergence for general problems? ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IobNwRXCz4b", "reviewer": "Reviewer_4cfY", "summary": "This paper considers the decentralized variational inequality problem and focuses on the setting when the VI is strongly monotone. Particularly, it studies the optimal stochastic algorithm under the finite sum setting through deriving a lower communication/computation complexity bound and an algorithm that achieves the bound. Numerical experiments are also presented for the proposed \"optimal\" algorithm. ", "questions": "In addition to the above mentioned weaknesses, there are a number of typos/issues throughout the paper:\n\n1. The definition of (7) can be problematic:\n\nIt is in fact described in the equation that the new iterate $z$ is taken from the span of $z'$, and $\\sum_{i_m} F_{m,i_m}(z^{''})$ for some given $z', z^{''} \\in {\\cal M}_m$. \n\nThis seems to suggest that $z',z^{''}$ have to be fixed. This is different from the framework of [29,59,68] which defines $z$ to be in the span of $\\{ z', \\sum_{i_m} F_{m,i_m}(z'') : z', z'' \\in {\\cal M}_m \\}$. That said, this seems to be merely a typo since the paper mainly adopting the results from [29,59,68].\n\n2. In (3), it should be $\\max_y$ instead of $\\min_y$?\n\n3. In line 761, \"for the fixed it is real distance\" misses the word \"graph\". ", "limitations": "The limitations have been described in the reviews of \"Weaknesses\" and \"Questions\". ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: The settings considered for the optimal decentralized stochastic VI algorithms is new. Furthermore, the proposed \"optimal\" algorithms have demonstrated promising performance as reported from the numerical experiments.\n\n**Weaknesses**: While the settings considered for the optimal algorithm is new, it seems that the technical novelty is limited. Moreover the reviewer finds a number of issues with the definition of the problem class considered. As follows, \n\n1. The reviewer is concerned about the role of the convex function $g$ as stated in (1) in the lower bound analysis. In fact, as seen in (7)-(8) of Sec. 3, [also (19) in Appendix C], the class of algorithm under consideration seems to be independent of $g$, i.e., the lower bounds are applicable only when $g = 0$. This leads to the further confusion as the proposed \"optimal\" algorithms actually use a proximal operator depending on $g$, which made the algorithms to be outside of the algorithm class analyzed in Sec. 3. Strictly speaking, the said result is still giving a lower bound complexity to solving the VI problem, yet it should be motivated clearly in the analysis setup for why $g$ can be ignored. \n\n2. From a quick scan on the appendix, it seems the key analysis depends mainly on [68]. The said reference has not been discussed in the main paper while it is necessary to discuss the main novelty here, e.g., in terms of the proof techniques?", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept