Decentralized Local Stochastic Extra-Gradient for Variational Inequalities
Authors: Aleksandr Beznosikov
Pavel Dvurechensky
Anastasia Koloskova
Valentin Samokhin
Sebastian U Stich
Alexander Gasnikov
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex optimization
variational inequalities
saddle point problems
gossip

Abstract: We consider distributed stochastic variational inequalities (VIs) on unbounded domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that, in particular, covers the settings of fully decentralized calculations with time-varying networks and centralized topologies commonly used in Federated Learning. Moreover, multiple local updates on the workers can be made for reducing the communication frequency between the workers.
We extend the stochastic extragradient method to this very general setting and theoretically analyze its convergence rate in the strongly-monotone, monotone, and non-monotone (when a Minty solution exists) settings. The provided rates explicitly exhibit the dependence on network characteristics (e.g., mixing time), iteration counter, data heterogeneity, variance, number of devices, and other standard parameters. As a special case, our method and analysis apply to distributed stochastic saddle-point problems (SPP), e.g., to the training of Deep Generative Adversarial Networks (GANs) for which decentralized training has been reported to be extremely challenging. In experiments for the decentralized training of GANs we demonstrate the effectiveness of our proposed approach.

Decentralized Local Stochastic Extra-Gradient for Variational Inequalities
Aleksandr Beznosikov
Innopolis University, MIPT HSE University and Yandex anbeznosikovrgmail.co
Pavel Dvurechensky
Anastasia Koloskova
WIAS
EPFL anastasia koloskova@epfl.co ch
Valentin Samokhin IITP RAS samohin. htaabii.wyy@@hyytechheem edu
Sebastian U. Stich
Alexander Gasnikov MIPT, HSE University and IITP RAS
CISPA
stich@cispa.de
gasnikovyyandex.zz
Abstract
We consider distributed stochastic variational inequalities (VIs) unbounded domains with the problem data that is heterogeneous (non-lID) and distributed across many devices. We make very general assumption on the computational network that, in particular, covers the settings of fully decentralized calculations with time-narying networks and centralized topologies commonly used in Fed- erated Learning. Moreover, multiple local updates on the workers can be made for reducing the communication frequency between the workers. We extend the stochastic extragradient method to this very general setting and theoretically ana- lyze convergence rate the strongly-monotone, monotone, and non-monotone (when Minty solution exists) settings. The provided rates explicitly exhibit the dependence on network characteristics (e.g., mixing time), iteration counter, data heterogeneity, variance, number of devices, and other standard parameters. As special case, our method and analysis apply to distributed stochastic saddle-point problems (SPP), e.g., the training of Deep Generative Adversarial Networks (GANs) for which decentralized training has been reported to be extremely chal- lenging. In experiments for the decentralized training of GANs demonstrate the effectiveness of our proposed approach.
Introduction
In large-scale machine learning (ML) scenarios the training data is often split between many devices, such as geographically distributed datacenters mobile devices [3 Decentralized training methods can learn an ML model with the same accuracy as if all the data would be aggregated on one single server [54] 5. At the same time, training in a decentralized fashion has many advantages traditional centralized approaches in such core aspects as data ownership, privacy, fault tolerance,
Research Center for Artificial Intelligence, Innopolis University
Mooccow Institute of Physics and Technology
I Weierstrass Institute Applied Analysis and Stochastics
$ Institute for Information Transmission Problems RAS
CISPA Helmholtz Center Information Security
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

and scalability. A particular instance of the decentralized learning setting is Federated Learning (FL), where the training orchestrated by a single device or server that communicates with all the participating client devices [62 38), In contrast, in fully decentralized learning (FD) scenarios the devices only communicate with their neighbors in the communication network graph with possibly arbitrary topology [54] Thus, decentralized algorithms are important in scenarios where centralized communication is expensive, not desired, or impossible.
There have been tremendous advances recently in the development, design, and understanding of decentralized training schemes
50. In particular, such aspects 55,, communication efficiency (through local updates [52 A4l or
95
54
X4
9
90
as hata-heterogeneityy [90]
78
compression [89 451) , and personalization [93 R have been studied. However, all these advances
were aimed at training with single-criterion loss functions leading to minimization problems, and they
do not apply to more general problem classes. For example, the training of Generative Adversarial Networks (GANs) 28 requires simultaneous competing optimization of the generator and the diseriminator objectives, i.e., solving a non-convex cooovex-non--one non-concvve aaddee-point problem (SPP). This problem structure makes GANs notoriously difficult to train even in the single-node setting 27 15 16, not talking about training over decentralized datasets
Our goal in this paper is solving decentralized stochastic SPPs, and, more generally, decentralized stochastic Minty variational inequalities (MVIs) 64 37
In a decentralized stochastic MVI, the data is distributed over M 2 1 devices/nodes and each device m E [M] has access to its local stochastic oracle Fm.2,, {.. for the local operator Fn == D. (2, Em). The data &. in the device m follows an unknown distribution Dm that can be different for each device m E [M]- The devices are connected via a communication network forming a graph such that two devices can exchange information if and only if the corresponding nodes are connected by an edge in this graph. The goal
is, while respecting the communication constraints, to find cooperatively a point 2 E IR" such that, for all z E R",
M
2) S.
(I)
A special instance of decentralized stochastic MVIs is the decentralized stochastic SPP with local objectives fm(2,,) v) == 1...-.,,. (m v, Em]]:
min max ZER" YER"M
f(z.v) v) := 3 EM fm fm
(2)
The relation to VI can be seen by considering the variable = = M and the gradient field (=)
[x) [- ()) In the special case when f(x, y) is convex-concave, the corresponding operator
F(z) = x +M= Im.,,. (2, Em is monotone. However, in the context of GANs training, where x and are the parameters of the generator and the discriminator, respectively, the local losses I'm (v., y) are possibly
in x, y and one can not assume the monotonicity of F in
general, see also 21I
In this paper, we develop novel algorithm for solving problems and 2 Note that the gradient descent-ascent scheme for the problem may diverge even in the simple convex-concave setting as a building block and combine them with gossip-type communication protocol 98 12 on arbitrary, possibly time-varying, network topologies. One of the main challenges due to the communication constraints is a "network error" induced by the impossibility of all the devices to reach the exact consensus, i.e., to have exactly the same information about the current iterate of the algorithm. Thus, each device stores local variable, and only approximate consensus among the devices can be achieved by gossip steps 47 Unlike other decentralized algorithms M S8
with M device 15] Thus, unlike 58
we use extragradient updates 48 37
our method avoids multiple gossip steps per iteration, which leads to better practical performance and the possibility to work on time-varying networks. Moreover, our method allows for multiple local updates between communication rounds to reduce the communication overhead. This also makes our approach suitable for communication- and privacy-restricted FL or fully decentralized settings [TOI..
Our contributions. 1) Based on extragradient updates, we develop a novel algorithm for distributed stochastic MVIs (and, as a special case, for distributed stochastic SPPs) with heterogeneous data. Our scheme supports very general communication protocol that covers centralized settings as in Federated Learning, fully decentralized settings, local steps both the centralizee//dcentraliiee settings, and vime-nayying network topologies. In particular, we are not aware of earlier works

---

proposing or analyzing extragradient methods with local steps for the fully decentralized setting or decentralized algorithms for stochastic MVIs over time-varying networks.
2) Under the very general communication protocol and in the three settings of MVIs, i.e., with an oper- monotone, or non-monotone under the Minty condition, we prove the convergence of our algorithm and give an explicit dependence of the rates on the problem parameters: characteristics of the network (e.g., mixing time), data heterogeneity, the variance of the data, number of devices, and other standard parameters. These theoretical results translate to the corresponding three settings SPPs (strongly-com ceoonnll-covve-sseeee stronssystooyyyoooo concavv, convex- manex-concave, non-convex coonee--no--oone non-concave under Minty condition). All our theoretical results are valid in the important heterogeneous data quantifiable way how different properties, e.g., data heterogeneity.
ator that is strongly-monotone
regime and allow judging the scale of the noise in the data, and network characteristics, influence the convergence rate of the algorithm. Even for decentralized settings, our results are novel for timevarrying graphs and three different settings of monotonicity. See also Table that gives more details on our contribution compared to the existing literature. The main challenge of our analysis is to deal with the very general assumption about the communication protocol and cope with the errors caused by the stochastic nature and heterogeneity of the data and limited information exchange between the nodes of the com- munication network. As byproduct of independent interest, analyze the stochastic extragradient method with biased oracle on unbounded domains, which was not done so far in the literature.
3) We verify our theoretical results in numerical experiments and demonstrate the practical effectiveness of the proposed scheme. particular, we train the DCGAN (7] architecture on the CIFAR-10 10 5il dataset.
1.1 Related Work
The research MVIs dates back at least to 1962 64 with the classical book 41 and the recent
works [59] 56
1
21
VIs arise in a broad variety of applications: image denoising 25 [4] game
theory and optimal control [26] robust optimization [)) and non-smooth oprimization via smooth reformulations A 73. ML, MVIs and SPPs arise in GANs training
[19
reinforcement
learning 76
36
and adversarial training 660
Extragradient. The extragradient method (EGM) was first proposed in 48 generalized as the mirror-prox method for deterministic problems in 73 and for stochastic problems with bounded variance in [37] Yet, if the stochastic noise not uniformly bounded, the EGM may diverge,
15 66
Reference
basc meilod
jrbirary newwrrk
Lime-varying
local upslates
DO mullippi gossip steps
SM
M
NM
Beznssisov ct al
Alg.
Stoch. ES
Barazandeh ot el. 2021
Stnch. ES
X
X
X
X X
Lia 2019 60
Dater: prox
X
X
Makherjee and Chakrahetty 2020
Deter, ES
K
Traknakis et al. 2020 00
Stoch. DA
X
X
Rugazin al. 202] [0]
Deter, ES
X
X
X
Xian
X
Beznosiloo et al. 2021
11 Alg
Stoch. ES
X
X
Deng and Maixdavi 202
M1
Stoch. DA
x
Hou 2121
x
x
Ours
Stoch. ES
homogencous case, con-convex-coccavc SPP (other works use minty condition
NM this column does not apply to
algorithms.
Table Comparison of approaches for distributed trongll-monotone (SM), monotone (M), and mon-monttoee (NM) VIs or, respectively, Definitions of columns: base method the non-distn non-distributed algorithm that is taken as the basis for the distributed method, typically it is either the extragradient method (EGM) or the descent-ascent (DA); arbitrary network supporting fully decentralized vs. only centralized topology; line-varying time-varying network topology: local updates method supporting local steps between communications; multiple gossip steps - at one global iteration the method does not use many iterations of gossip averaging to reach a good consensus accuracy; SM, M, NM monotonicity assumption, see Assumption 3.2
conexxconcave, www.-oooooonoccneeececce
SPPs.
decentralized method supporting
Decentralized algorithms for MVIs and SPPs are the most closely related to our work. In Table [ we summarize their features and make a comparison with our algorithm, showing that, e.g., existing methods do not support arbitrary time-varying network typologies. The methods that use multiple rounds of gossip averaging (sparse communication) per iteration [58] [1] can give near-optimal theoretical rates, but often unstable in practice. Thus, it is preferable have only one sparse
3

---

The second column of the table refers to standard algorithms that are extended distributed settings in the corresponding work. In particular, the algorithm of [59 requires expensive proximal updates. The closest work to ours is [II] where decentralized EGM without local steps analyzed in the (strongly-)monotton
communication per iteration
59
69
91
80
97
setting. Unlike our more general algorithm with local steps, theirs require multiple gossip updates in each iteration which is not desired in practice. For the FL, i.c. centralized, setting, |ii studies the EGM with local steps in the atrongly-monotor setting, and 20 32 study the descent-ascent method with local steps. Yet, all three works do not consider arbitrary time-varying graphs as in our work.
Algorithm
In this section, we present and discuss the proposed algorithm (Algorithm 1 that is based on two main ideas: (i) the extragradient step, as in the classical methods for VIs 18 7 and (ii) the gossip averaging 122 F widely used in decentralized optimization methods and in the literature on diffusion strategies distributed learning [82 S3 99 61]. Unlike these papers that propose
algorithms for optimization problems by exploiting gradient descent, our algorithm is based on the extragradient method and is designed to solve VIs and SPPs. Moreover, unlike the mentioned works, method also allows for local steps in-between the communication rounds and for time-varying networks and has non -symptooto theoretical convergence rate guarantees.
Each step of Algorithm 1 can be divided into two phases. The local phase (lines 4-6) consists of a step of the stochastic extragradient method at each node using only local information. As in the non-distributed case, the nodes first make an extrapolation step "to look into the future" and then an update based on the operator value at the "future" point. This is followed by the communication phase (gossip step) (line 7), during which the nodes share and average local iterates with their neighbors in the communication network graph corresponding to the iteration The averaging process Ar m
involves the weights wh,; which are the elements of the matrix W called the mixing matrix:
Definition 2.1 (Mixing matrix). We call a matrix W E [0; M]]MMM a mixing matrix if it satisfies the following conditions: 1) W is symmetric, 2) W is doubly stochastic (W1 = 1, 1 1" = 17, where 1 denotes the vector of all ones). 3) W is aligned with the network: Wij * if and only i = j or the edge (i, j) is in the communication network graph.
Reasonable choices of mixing matrices are, for example, (i) W = IM Amas (L.T. where L is the Laplacian matrix of the network graph at the step and Ias the identity matrix, or (ii) using some local rules in the graph, based on the degrees of the neighboring nodes [98]. Note that our setting has great flexibility since in- between the iterations the topology of the communication graph is allowed to change, and the matrix W that encodes the current structure of the network, changes accordingly. This encoded line 2, where the matrix W is generated by some rule W which can have different nature. Examples include deterministic choice of a sequence of matrices W sampling from a time-varying probability distribution on matrices. Even local steps without communication can be encoded with diagonal matrix W*.
Algorithm 1 Extra Step Time- Varying Gossip Method
parameters: stepsize 7 > (W* Ju20 rules distributions for mixing matrix in iteration k. initialize: z0 E 2, Vm = =
1: for k = 0,
do
2: Sample matrix W from W
3: for each node m do
4: Generate independently ck ~ DE. Sm
k+11/3
~ Dr.
5:
2 k+1/3
7F (ok ck
2m
k+2/3 = * 77 (zm 2m
k+1/3 c+1/33
6:
Sm
7: A+1 -+1= EiENa w im
k+2/3
Am
8: end for
9:
end for
To ensure that it is possible to approach the consensus between the nodes, we need the following assumption the mixing properties of the matrix sequence W

---

Assumption 2.2 (Expected Consensus Rate). We assume that there exist a constant E (0, and an integer 7 2 such that, after K iterations, for all matrices Z E RRdxM and all integers I E {O....,K/ K/T}.
Ew ||, - S (1 (1-1)))11)) -) -
(3)
where Wi, Wtr W(+1)7-1 we use the matrix notation Z = [=I....,,,]] 2 = 1 with 2 1 -m=1 Am, and the expectation Ew is taken over distributions of W and indices t E (Ir,... (1 1)
This assumption ensures that, after gossip steps with such time-varying matrices, improve the consensus between the nodes, i.e., how close each Zm is to E, by the factor of T-p Importantly, in this case, some matrices W* can be, for example, the identity matrix (which corresponds to performing only local steps in iteration k))
Assumption has been recently quite popular in the literature on distributed optimization methods Moreover, it is very general and covers many special cases of decentralized and centralized algorithms. For example, if we fix W W for some fixed connected graph, we get _ 11 then it is decentralized algorithm on this graph. If, at the same time, we set the matrix W = 37
72
easy to see that we get analog of the centralized setting with the averaging over all nodes performed in each communication step. If we take W = W for some fixed connected graph at every 5-th step IM. we have a decentralized (and, in particular, centralized) algorithm and communications after each T iterations. Generic Assumption 2.2 covers also many other settings of time-varying decentralized topologies, e-g., random topologies, cliques, B-connected graphs
and in other steps use W
with local steps S
30
70 Below we show that, under an appropriate choice of the stepsize, our extragradient method provably converges under such a general assumption that covers centralized and decentralized settings. local steps in both centralized and decentralized settings, and changing topologies of the communication graph. Even for decentralized settings, this is novel for time-varying graphs and three different settings of monotonicity which we consider.
35
3 Setting and Assumptions
In this section, we introduce necessary assumptions that are used to analyze the proposed algorithm. Assumption 3.1 (Lipschitzness). For all m, the operator (2) is Lipschitz with constant L, i.e.,
FL Fm (22)l - 2||a1 =22l:
V2i, 22.
(L)
This is a standard assumption that is used in the analysis of all the methods displayed in Table !| Assumption 3.2. We consider three scenarios for the operator F, namely, when F' is strongly- monotone, monotone and non-monotone, but with an additional assumption:
(SM) Strong monotonicity. There exists μ > such that, for all 21, 22.
(F(x1) - F (22), 21 22) 1||21 22 11
(SM)
(M) Monotonicity, For all æ1, 22, it holds that:
(F(z1) F(22), 21 - =22 2 0.
(M)
(NM) Non-monotonicity (Minty). There exists 2² such that, for all 2,
(F(z), x²) 20 0.
(NM)
Assumptions
SM
M and are standard and classical assumptions in the literature on VIs.
Assumption NM is sometimes called the Minty or Variational Stability condition and it has been
widely used recently by the community as structured variant of monomonotyy
[8
59
39
33
21
particularly, since it is appropriate in GANs training 57 58 22
The next assumption is standard for the stochastic setting.
Assumption 3.3 (Bounded noise). (m.gg)) is unbiased and has bounded variance, i.e., for all 2,
E F2, (2] Fm (z), Fm Fm(
(4)
5

---

Our last assumption reflects the variability of the local operators compared to their mean and is
usually called D-heterogeneity. This assumption is widely used in the analysis of local-steps (and
not only) algorithms for minimization problems 40 96 30 85
17 24 Moreover, [20 32
use this assumption for the analysis of centralized local-steps methods for SPPs. The authors of [58] assume D O for the decentralized training of GANs. Even in this case algorithms" analysis can be challenging.
Assumption 3.4 (D--heterogeneitt)) The values of the local operator have bounded variablility, i.e., for all 2,
D2. D?.
(5)
4 Main Results
In this section, we present the convergence rate results for the proposed method under different settings of Assumption 3.2 To present the main result, introduce notation zh := MI Σ 2m=1 2 1/3 = M
*
Em= 1==1 2m for the averaged among the devices iterates and E E+1 Σ 1++ for the averaged among the devices and iterates sequence, a.k.a. ergodic average. Finally, we denote A I DD= o²) which plays the role of the consensus error, i.e., the error caused by the p
impossibility of reaching the exact consensus between the nodes. Note that the data heterogeneity appears in the convergence rates only through the quantity A.
Theorem 4.1 (Main theorem). Let Assumptions 2.2
3.1 3.3 3.4
hold and the sequences zh 26 be
generated by Algorithm D that is run for K >> 0 iterations. Then,
Gtoogly-monotone case: under Assumption 3.2 SM), with 7
Ô (min
2
akk
it holds that
[L
E [| -
Ô 0 - -1120==111
112
exp (-
nkp 240
+
arMK
x²
#
xe
1²
(6)
Monotone case: under Assumption
3.2 M), for any convex compact s.I. 20,
C and
}} it holds that
max ||z - S Ic, with 7 = 0 min T
D Ko
K
supzec E (F(2), 0
ofe VMK
v VLNEVA VK
+
(A 1
(7)
KL
Under the additional
assumption that, for all 12
|
with
7
o min E: Kot
+
22
we have that
supsec [F(()), Ek - =)] = K
+
ofe VMK
LAAVA K374
(1
(8)
K
Non-monotone case: under Assumption
3.2 NM) and if ||=0|| S 2 1=111=11| S a
with 7
min 1 1x 22 (K=TE>> )
E
|
T Ek |F+
(L292 d² 20
+ LΩVA
VLDA374 VK
M
$
$1)
Under the additional assumption that, for all k, ||
< Ω with
O min
D2
To
KT.
we have that
E
1 K+1 1 -
12 (1-22 + +
d M
(LDA)2/3 K1/3 + LLVA).
(10)
The proof of the theorem given in the supplementary material, where one can also find explicit dependence of the rates on the stepsize before it is chosen optimally. We underline that the standard
analysis [37] does not apply for the following reasons. Firstly, unlike [17], in our problem I the feasible set is not bounded, which is especially important for the analysis in the monotone and

---

non-monotone settings. Secondly, our algorithm has an additional communication step (line 7) between the computational nodes, which leads the impossibility for all the nodes have the same information about the global operator F(z) and about the current iterate z. This, in order, leads to a biased oracle that, unlike existing works, has to be analyzed in the setting of an unbounded feasible set, which is quite challenging. To analyze our variant of the extragradient method, we successfully handle this challenge. Our key steps are to bound the bias (see, c.g., the last two terms in the r.h.s. of Lemma C.8 that are caused by the network errors), prove the boundedness in expectation of the sequence of the iterates for monotone (see Section C.3. of the supplementary material) and non-monotone (see Section C.4.I of the supplementary material) cases, which may be of independent interest and which we have not seen in the literature, even in the non-distributed setting with biased stochastic oracles. Proving the boundedness is challenging due to the noise caused by the stochasticity and heterogeneity of the data and network effects due to the imperfect exchange of information. Surprisingly, in the end, we still manage analyze our algorithm under the very general Assumption 2.2 and we are not aware of any results with similar generality of the settings: different network topologies (including vine-varying), distributed architectures, different monotonicity assumptions.
The provided convergence rates have an explicit dependence on the problem parameters: the network that is characterized by the mixing time and the mixing factor p, the data heterogeneity D (these three quantities appear in the convergence rates only through the quantity A), the variance o² of the noise in the data, the Lipschitz constant L, the strong monotonicity parameter μa, the number of nodes/devices M. Thus, our rates allow judging how different properties, e.g., data heterogeneity, noise level, and network characteristies influence the convergence rates. This, in particular, opens up an opportunity for a meta-optimization process if we can design the network and change M, t, p to achieve faster convergence.
We now discuss the convergence results obtained in the theorem, and also compare them with already existing algorithms (see Table I and their guarantees. Firstly, all the estimates have similar several-term structure. The first term corresponds to the deterministic setting and is similar to existing methods for smooth VIs in the non-distributed setting. Only in the strongly-convex case, there is an additional factor T/p that increases the condition number L/p of the problem. The second (stochastic) term is also standard for the non-distributed setting and corresponds to the stochastic nature of the problem. Note that, for a very general distributed setting, we have managed to obtain the corresponding terms similar to the non-distributed setting. Moreover, we can the benefit of exploiting distributed computations: the leading stochastic term depends on a²/ /M that decreases as the number M of the nodes increases. The other terms correspond to the consensus error A and due to the imperfect communications between the nodes, i.e., that all the nodes can't have exactly the same information about the current iterate. Importantly, in all the cases, this error does not make the overall convergence worse since the dependence on K is no worse in these terms than the dependence on K in the stochastic term. In the experimental section, we illustrate that the network error is not an artifact of the analysis but is indeed present in practice.
Theorem 4. is formulated for fixed budget of iterations K and the corresponding stepsizes "y that depend on K, which is pretty standard in the literature 37 8 10, where many algorithms fix the stepsize depending
the budget of the iterations. In Section of the supplementary material, we present a simple restarting procedure that allows to extend the results of Theorem 4. to any-time convergence without a-priori fixing K. The idea is set K, 2 for t 0, 1,... and restart the algorithm after each K₂ iterations. We next make refined comments for each particular setting of monotonicity.
Strongly-monotone case: In the centralized setting with local updates, our rate is slightly better than in [.]. Unlike our algorithm. centralized algorithms with local steps for SPPs in 20 [2] are based on the gradient descent-ascent method that may diverge in the stochastic setting even for bilinear problems. Moreover, their analysis implies very small stepsize 7 ~ up (cf. ours ? (.), )
which greatly slows down the convergence of the algorithm.
For the decentralized setting, [1] propose an optimal algorithm with the rate matching the lower bound which they also give. Our rate is worse probably because of the generality of the Assumption
2.2
On the other hand, our algorithm is more practical since it avoids using multiple gossip steps at each iteration. Also, our algorithm is more general, allowing us to work with time-varying topologies and local steps even in the decentralized setting.
7

---

Monotone case: The quantity sep E (F)),, --2=-222, -2]] in the convergence rates estimates reflects the stochastic nature of the problem and is a counterpart of the standard restricted gap (or merit) function 75 Gapc(u)
2)}. When F is a monotone operator, if (ū) = 0 and C contains a neighborhood of úł, then 75 á is solution to ① and even more: it is a strong solution to the corresponding variational inequality, i.e., for all z, (F â z) s O. Thus, Gup is an appropriate measure of suboptimality in this setting and 7 guarantees that after sufficient number of iterations, we obtain approximate solution in expectation. Importantly, for Z. neither nor z are assumed to be bounded. As in the previous works on non-distributed algorithms for MVIs 75 [1, use G (u) with an arbitrary compact set that contains 2 and 2* (this can be a large set). Further, ( is a refined version of the general result 7 under the additional assumption of the boundedness of the averaged iterates. If the boundedness does not hold, still have Moreover, 7 and S hold for the same method, and to run the algorithm, there no need to know in advance whether the generated sequence is bounded not.
supsec (F(2),
consider MVIs with monotone operator in distributed setting. Our algorithm is more general than theirs: our algorithm supports time-varying networks and local steps between communications. The algorithm in [TT uses multiple gossip steps between the updates of the iterates. On the one hand, this allows decreasing the consensus error A. On the other hand, this leads to an additional factor the number of communications compared to our estimates: the first term in their bound is /X times larger than ours, where X 1 is some condition number of the mixing matrix. Moreover, multiple gossip steps may be impractical if the communication is performed through unstable channels is expensive for some reason. The paper [& setting.
Only
considers only deterministic
The same as in the previous case remark on the boundedness of zt 2" assumed to obtain (I0) applies in this case. Further, in this setting, the convergence is guaranteed up to some accuracy that is governed by the stochastic nature of the problem (the -teremm) and by the distributed nature of the problem (the A-terms), With this respect, the results are similar to the non-distributed stochastic extragradient method 7 and the distributed method [58] analyzed in the homogeneous case = To the best of our knowledge, convergence up to arbitrarily small accuracy can be guaranteed only for deterministic distributed methods [59], i..., in much simpler
Non-monotone case:
setting than ours. Moreover, the methods of (59) are not the most robust since they require evaluating the proximal operator of a function and it is assumed that this can be done in closed form, which is computationally expensive and may not hold in practice.
Note that, based our result, it is possible to achieve convergence up arbitrarily small accuracy if one considers the homogeneous case with D = Indeed, choosing the right batch size, for example, proportionally to K with a > O, one can replace o² by K in and I0 and get convergence guarantees.
Experiments
In this section, we present two sets of experiments to validate the performance Algorithm I In Section 5.1 verify the obtained convergence guarantees two examples: monoooye and a monotone bilinear problems, and in Section 5.2, we explore the non-monotone case with an application to GANs training. Extended details of the experimental setup can be found in the supplementary material.
5.1 Verifying Theoretical Convergence Rate
First, we focus on the verifying whether the actual behaviour of Algorithm is predicted by the theoretical convergence rate in Theorem
with the objective functions (x, = 2||=|| + bx y ||y/12 e where v, y. Cm E F.. aet a R and m E {1..... M This set of functions satisfy Assumptions 3.1 3 3.4 with constants
Setup. We consider a distributed bilinear SPP
a, L a² b². D = max ||cm - e||. In this section, we use ring topology on M 20 nodes with uniform averaging weights, and we set the dimension = 5. b 1, D R 3, and keep = 1. The value of the parameter p in this setting is approximately 0.288 40 Table 1]. To satisfy Assumption 3.3] we gen- erate stochastic gradients by adding to the exact gradients unbiased Gaussian noise with variance o².
8

---

1,00
= 0, y=
1073
1073
10 1000
100
2003
4000
5000
8000
20000
40000 03833
D0000
Figure 1: Convergence of Algorithm with constant stepsize in the presence stochastic noise in strongly- monotone (left) and monotone (right) cases. We observe linear convergence up to am error floor depending on the noise variance and problem parameters (cf. Theorem 4.J. In Section A.2 of the supplementary material we show convergence arbitrary accuracy with decreasing stepsizes.
Convergence Behaviour: In Figure D we show the convergence of Algorithm I with a fixed stepsize on the mrongly-monotone
and monotone (a 0) instances. In the strongly-monotee case, we see a linear convergence to some level defined by the heterogeneity parameter and the noise. The convergence for the con-sstonglymoonotee convergence up to some level (for bilinear problems this behavior is expected from the theoretical point of view 48 Note that the convergence to some limiting accuracy is expected since when constant stepsize is used in stochastic optimization/stochattt
problem is slower, but we also see linear
variational inequalities with strong convexity/monotonicityy, algorithms are usually guaranteed to converge only to a vicinity of the solution, see, e.g., Theorem 2 in [66]. This is also in accordance with Theorem that, for fixed stepsize, guarantees the convergence to some non-zero limit accuracy and says that, to achieve the zero eπror, needs to choose decreasing stepsize. We additionally validate in Section A.2 of the supplementary material that with a decreasing stepsize, the algorithm can converge to the zero error.
Itcration to reach
Iterations reach é 0.01
Iteration to reach 0.01
1007
1200
1200
1032-
500
002
502
903-
635
203
22
40
25
60
100
16
15
20
25
70
1W7
11p
Figure 2: Verifying O
convergence rate for the strongly-monotone noiseless (a² 0) case.
p K
Dependence on the Heterogeneity parameter D. In the second set of experiments, we aim to verify the dependence on the data heterogeneity parameter D. Therefore, we consider the setting when o² = 0. From our theory, equation 66) we predict that the most significant term in the convergence rate when o² 0 scales as O p"K= (since the primary goal of this experiment is to study the dependence on p. D, K. we omit all the other fixed parameters for simplicity). We take o. 1 and conduct experiments with the number of iterations needed achieve the 1 Σm m= 1 2 201 2112 < e, for different E. In all these experiments, the stepsize is tuned error 57 individually.
First, we verify the power of in the bounds. For this experiment, we keep D, p constant and vary the accuracy As we can from the leftmost subplot in Figure 2 the number of iterations scales as K x T confirming the predicted O R= dependency of the error on K. Next, we measure the number iterations sufficient reach the error 5 0.01 while varying D. The middle plot shows that the number of iterations scales proportionally to D (showing D x K). Lastly, we depict the number of iterations reach 0.01 while changing the graph parameter p and again observe x K. Summarizing, these experiments verify the O D term in the convergence rate.
5.2 Training GANs
Our algorithm allows combining in the distributed learning setting different communication graph topologies, as well as local steps. Thus, our goal in this section is to illustrate this empirically with the experiments on GANs training. In Section A. of the supplementary material, we discuss to what extent our theoretical results hold for GANs training.

---

Data and model. We consider the CIFAR-10 10 [51] dataset containing 60000 images, equally dis- tributed over 10 classes. We increased the size of the dataset by 4 times using transformations and adding noise. We simulate distributed setup of 16 nodes on two GPUs and use Ray [67 To emulate the heterogeneous setting, we partition the dataset into 16 subsets. For each subset, we select major class that forms 20% of the data, while the rest of the data split is filled uniformly by the other classes. As a basic architecture we choose DCGAN 779 network architecture can be found in Section A.
conditioned by class labels, similarly to [65 (the We chose Adam 42] as the optimizer. We make one local Adam step and then one gossip averaging step with time-varying matrices W to Algorithm
Setting. We compare the following three topologies (and the corresponding matrices w*>): Full. Full graph at the end of each epoch, otherwise local steps. This means that we make 120 communication rounds (by communication round we mean the exchange of information between a pair of devices) in an epoch.
Local. Full graph the end of each 5th epoch, otherwise local steps. This means that we make 24 communication rounds in an epoch (in average: 4 epochs without communications and epoch with
120 rounds).
Clusters. At the end of each epoch, clique clusters of size 4 are randomly formed (in total 4 cliques). This means that we make 24 communication rounds in an epoch.
Note that the communication budget of the first approach is 5 times larger.
We use the same learning rate equal 0.002 for the generator and discriminator. The rest of the parameters and features of the architecture can be found in the supplementary material.
Results. The results of the experi- ment are presented in Figure 3 and Figure 6 (Section
Ouster
Cluster
300
Fall
Local
Local Futl
A.3 In terms of the number local epochs, all the methods converged quite close to
each other and produced similar im- ages. In terms of communications, Local and Cluster topologies lead to much better results, and the Cluster topology is slightly better than the Local.
506
1001
2590
2009
2500
530
3000
LCC3
2300
2213
Olster
150
100
Conclusion
Local Apocre
Local spedto
Figure 3: Comparison of the three network topologies in DCGAN distributed decentralized learning on CIFAR-10. FID Score and Inception Score vs the number of communications (two top). and the same Scores the number of local epochs (two bottom). The experiment was repeated times on different random data splitting, the maximum and minimum deviations are depicted in the plots hy the shade.
We propose a novel efficient al- gorithm for solving decentralized stochastic MVIs and SPPs under very general assumption on the net- work topology and communication constraints. In particular, our method is the first decentralized extragradient method with local steps for time- varying network topologies. Moreover, for the proposed algorithm, we prove the convergence rate thcorem in the S.M, M and NM cases. In the numerical experiments, we verify that the dependence of our rates on the data hetero- geneity parameter D is tight in the SM case, and cannot be further improved in general. By training DCGAN decentralized topology. demonstrate that method is effective on practical DL tasks. As a future work it would be interesting to generalize such algorithms for problems.
Acknowledgments
This research of A. Beznosikov has been supported by The Analytical Center for the Gov- ernment of the Russian Federation (Agreement No. 10-2021-00144 dd. 01. 11,221, IGK The work by P. Dvurechensky in Section C.3 was funded by the Deutsche Forschungsgemminschaatt (DFG, German Research Foundation) under Germany's Excellence Strategy The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).
00000D730331P5000000
10

---

References
[1] Artem Agafonov, Pavel Dvurechensky, Gesualdo Scutari, Alexander Gasnikov, Dmitry Kam- zolov, Aleksandr Lukashevich, and Amir Daneshmand. An accelerated second-order method for distributed stochastic optimization. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2407-2413, 2021.
[2] Sulaiman A Alghunaim and Kun Yuan. A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing, 2022.
[3] Kimon Antonakopoulos, Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror-prox method for variational inequalities with singular operators. Advances in Neural Information Processing Systems 32 (NeurlPS), pages 8455-8465. Curran Associates, Inc., 2019.
[4] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. arXiv preprint arXiv: 2015.
[5] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat. Stochastic gradient push for distributed deep learning. In Proceedings of the 36th International Conference on Machine Learning (ICML). PMLR, 2019.
[6] Babak Barazandeh, Tianjian Huang, and George Michailidis. decentralized adaptive mo- mentum method for solving class of min-max optimization problems. Signal Processing, 189:108245, 2021.
Babak Barazandeh, Davoud Ataee Tarzanagh, and George Michailidis. Solving class of non-convex min-max games using adaptive momentum methods. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3625-3629, 2021.
[8] Aurélien Bellet, Rachid Guerraoui, Mahsa Taziki, and Mare Tommasi. Personalized and private peer-to-peet peer machine learning. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (AISTATS), volume 84, pages 473-481. PMLR, 2018.
[9] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust Optimization. Princeton University Press, 2009.
[10] Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradi- ent descent-ascent: Unified theory and new efficient methods. arXiv preprint arX1v:2202.07262. 2022.
[11] Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle- point problems: Lower bounds, optimal algorithms and federated GANs. arXiv preprint arXiv:2010.13112. 2021.
[12] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2588-230, 2006.
[13] Brian Bullins and Kevin A. Lai. Higher-order methods for convex-concave min-max optimiza- tion and monotone variational inequalities. arXiv preprint arXiv:2007.04528. 2020.
[14] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications imaging. Journal of mathematical imaging and vision, 40(1): 2011.
[15] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien Reducing noise in GAN training with variance reduced extragradient. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[16] Tatjana Chavdarova, Matteo Pagliardini, Sebastian U. Stich, Francois Fleuret, and Martin Jaggi. Taming GANs with lookahead-minmax. In International Conference on Learning Representations (ICLR), 2021.

---

Curran [17] Amir Daneshmand, Gesualdo Scutari, Pavel Dvurechensky, and Alexander Gasnikov. Newton method over networks is fast up to the statistical precision. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2398-2409, PMIR, 18-24 Jul 2021.
[18] Cong D Dang and Guanghui Lan. On the convergence properties of non-Euclidean extragradi- ent methods for variational inequalities with generalized monotone operators. Computational Optimization and Applications, 60(2):277-310, 2015.
[19] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference on Learning Representations (ICLR), 2018.
[20] Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intellignnce and Statistics (AISTATS), pages 1387-1395. PMLR, 2021.
[21] Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured minconvex-nonconeee min-mas optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2746-2754. PMLR, 2021.
[22] Zehao Dou and Yuanzhi Li. On the one-sided convergence of adam type algorithms in non-convex non-concave min-max optimization. arXiv preprint arXiv:2109. 14213, 2021.
[23] Pavel Dvurechensky, Darina Dvinskikh, Alexander Gasnikov, César A. Uribe, and Angelia Nedić. Decentralize and randomize: Faster algorithm for Wasserstein barycenters. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Besa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, NeurlPS 2018, pages Associates, Inc., 2018.
[24] Pavel Dvurechensky, Dmitry Kamzolov, Aleksandr Lukashevich, Soomin Lee, Erik Ordentlich, César A. Uribe, and Alexander Gasnikov. Hyperfast second-order local solvers for effi- cient statistically preconditioned distributed optimization. EURO Journal on Computational Optimizatioon, page 100045, 2022. (accepted), arXiv:2102.08246
[25] Ernie Esser, Xiaoqun Zhang, and Tony Chan. A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM Journal on Imaging Sciences, 3(4): 1045:1015-1 2010.
[26] F. Facchinei and J.S. Pang. Fintte-Dimessionll Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering. Springer New York, 2007.
[27] Gauthier Gidel, Hugo Berard, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial nets. In International Conference on Learning Representaatinns (ICLR), 2019.
[28] Ian Goodfellow, Jean Abbdie- Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems (NIPS), 2014.
[29] Eduard Gorbunov, Pavel Dvurechensky, and Alexander Gasnikov. An accelerated method for derivative-fis -free smooth stochastic convex optimization. arXiv preprint arXiv: 1802.0000, 2018.
[30] Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: efficient methods. In International Conference on Artificial Intelligence and Statistics, pages 3556-3564. PMLR, 2021.
Unified theory and new
[31] Hadrien Hendrikx, Lin Xiao, Sehastien Bubeck, Francis Bach, and Laurent Massoulie, Statisti- cally preconditioned accelerated gradient method for distributed optimization. In International Conference on Machine Learning, pages 4203-4227. PMLR, 2020.
[32] Charlie Hou, Kiran K Thekumparampii, Giulia Fanti, and Sewoong Oh. Efficient algorithms for federated saddle point optimization. arXiv preprint arXiv:2102.080 2021.
12

---

[33] Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Advances in Neural Information Processing Systems, 33:1622:: 13:11623--6234,, 2020..
[34] Alfredo N lusemm Alejandro Jofré, Roberto Imbuzeiro Oliveira, and Philip Thompson. Extra- gradient method with variance reduction for stochastic variational inequalities. SIAM Journal Optimization, 27(2):686-724 2017.
[35] A. Jadbabaie, Jie Lin, and A.S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6);988-001,, 2003,
[36] Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119, pages 4890-4900) PMLR, 2020.
[37] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror- prororrpooxxoooo algorithm. Stochastic Systems, 1(1):17-58, 2011.
[38] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D' Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977 2019.
[39] Aswin Kannan and Uday V Shanbhag. Optimal stochastic extragradient schemes for pseu- domonotone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74(3):779-82) 820, 2019.
[40] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In International Conference Artificial Intelligence and Statistics (AISTATS), pages 4519-4529, 2020.
[41] David Kinderlehrer and Guido Stampacchia. An Introduction to Variational Inequalities and Their Applications. Society for Industrial and Applied Mathematics, 2000.
[42] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412 2014.
[43] Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? In International Conference on Machine Learning, pages 2698-2707 PMLR,
2018.
[44] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized sgd with changing topology and local updates. In Proceedings of the 37th International Conference Machine Learning (ICMI.). PMLR, 2020.
[45] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Proceedings of the 36th Inter- national Conference on Machine Learning (ICML), volume 97, pages 2019.
PMLR.
[46] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Leurning. volume 97 of Proceedings of Machine Learning Research, pages 3478-3487. PMIR, 09-15 Jun 2019.
13

---

[47] Lingjing Kong. Tao Lin, Anastasia Koloskova, Martin Jaggi. and Sebastian U. Stich. Consensus control for decentralized deep learning. In Proceedings of the 38th International Conference Machine Learning (ICML.. PMLR, 2021.
[48] Galina Korpelevich. The extragradient method for finding saddle points and other problems. Eknomika Matematicheskie Metody, 12:747-756, 1976.
[49] 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 preprint arXiv: 2e...000.44,,
[50] Roman Krawtschenko, César A. Uribe, Alexander Gasnikov, and Pavel Dvurechen- sky. Distributed optimization with quantization for computing wasserstein barycenters. arXiv:2010.14323, 2020. WIAS preprint 2782.
[51] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton, Cifar- 10 (canadian institute for advanced research). http:// cs. toronto.............. http//rrizccii cifar.ifrr.../ .htll 2009.
[52] Guanghui Lan, Soomin Lee, and Yi Zhou. Communication ized and stochastic optimization. Mathematical Programming, Dee 2018.
algorithms for decentral-
[53] Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. arXiv preprint arXiv: 1705.0980000 2017.
[54] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decen- tralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems 30 (NIPS), pages 5330-53444 5340. Curran Associates, Inc., 2017.
[55] Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In Proceedings of the 38th International Conference Machine Learning (ICML), 2021.
[56) Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal algorithms for minimax optimization. In Proceedings of Thirty Third Conference on Learning Theory (COLT), volume 125, pages 2738-2779, PMLR, 2020.
[57] Mingrui Liu, Youssef Mrouch, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative ad adversarial nets. arXiv preprint urXiv:/9122 1940, 2019.
[58] 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.
[59] Weijie Liu, Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil, Zebang Shen, and Nenggan Zheng. A decentralized proximal point-type method for saddle point problems. arXiv preprint arXiv:1910. 1910.14000,,,,,,,, 2019.
[60] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018.
[61] Alexey S. Matveev, Mostafa Almodarresi, Romeo Ortega, Anton Pyrkin, and Siyu Xic. Diffusion-based distributed parameter estimation through directed graphs with switching topology: Application of dynamic regressor extension and mixing. IEEE Transactions on Automatic Control, 67566422564 2022.
[62] H. Brendan McMahan, Fider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated learning of deep networks using model averaging. arXiv preprint 1502.556,, 2016.
[63] 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.026299 2018
14

---

[64] George J. Minty. Monotone (nonlinear) operators in Hilbert space. Duke Mathematical Journal, 29(3):341
336,, 1962.
[65] Mehdi Mirza and Simon Osindero. Conditional generative adversarial nets, arXiv preprint arXiv:1411.174 2014.
[66] Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revisiting stochastic extragradient. arXiv preprint arXiv:1905.11. 2019.
[67] Philipp Moritz. Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I Jordan, et al. Ray: A distributed framework for emerging {AI] applications. In 13th { {USENIX) Symposium on Operating Systems Design and Implementation ({OSDI) 18), pages 561-577, 2018.
[68] Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I. Jordan, and Ion Stoica. Ray: A distributed framework for emerging ai applications. 2018.
[69] Soham Mukherjee and Mrityunjoy Chakraborty. decentralized algorithm for large scale min-max problems. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 2967-2972. 2020.
[70] Angelia Nedic, Alex Olshevsky, Asuman Ozdaglar, and John N. Tsitsiklis. On distributed averaging algorithms and quantization effects. IEEE Transactions Automatic Control, 54(1 25210 2009.
[71] Angelia Nedić and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48 (116))))6662)22000 2009.
[72] Angelia Nedich, Alex Olshevsky, and Wei Shi. A geometrically convergent method for distributed optimization over time-varying graphs. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages
IEEE, 2016.
[73] 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.
[74] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming. 103(1):127-152, 2005.
[75] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathemutical Programming. 109(2):319-344, 2007.
[76] Shayegan Omidshafici, 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 on Machine Learning (ICML), volume 70, pages 2681-2690. PMLR, 2017.
[77] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 8026-8037. Curran Associates, Inc., 2019.
[78] S. Pu and A. Nedić. Distributed stochastic gradient tracking methods. Math. Program., 2020.
[79] Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint 1eXiv:/511.064/ 2015.
[80] Alexander Rogozin, Alexander Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. arXiv preprint arXiv:2102.07758, 2021.
15

---

[81] Alexander Rogozin, Mikhail Bochko, Pavel Dvurechensky, Alexander Gasnikov, and Vladislav Lukoshkin. An accelerated method for decentralized distributed stochastic optimization over time-varying graphs. In 2021 60th IEEE Conference Decision and Control (CDC), pages 3367-3373, 2021.
[82] Ali H. Sayed. Chapter 9 diffusion adaptation over networks*the work was supported in part by nsf grants eecs-060126, 26, eecs-0725441, ccf-0942936, and ecf-101191s In Abdelhak M. Zoubir, Mats Viberg. Rama Chellappa, and Sergios Theodoridis, editors, Academic Press Library in Signal Processing: Volume 3, volume 3 of Academic Press Library Signal Processing, pages 323-453. Elsevier, 2014.
[83] Ali H Sayed, Sheng- Yuan Tu, Jianshu Chen, Xiaochuan Zhao, and 7aid J Towfic. Diffusion strategies for adaptation and learning over networks: an examination of distributed strategics and network behavior. IEEE Signal Processing Magazine, 30(3):155-177 2013.
[84] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Op- timal algorithms for smooth and strongly convex distributed optimization in networks. In Proceedings of the 34th International Conference on Machine Learning (ICML). 2017.
[85] Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effiee using approximate newton-type method. In Eric P. Xing and Tony Jebara, editors, Proceed- ings of the 31st International Conference on Machine Learming, volume 32 of Proceedings of Machine Learning Research, pages 1000-1008, Bejing, China, 22-24 Jun 2014. PMLR.
distributed optimization
[86] Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944-95) 2015.
[87] Sebastian U Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations (ICLR), 2019.
[88] Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint (XXiv:9907.04232, 2019.
[89] Hanlin Tang, Xiangru Lian, Shuang Qiu, Lei Yuan, Ce Zhang, Tong Zhang, and Ji Liu. Deepsqueeze: Decentralization meets error-compensated compression. arXiv preprint arXiv:1907.07346, 2019.
[90] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D²: Decentralized training over decentralized data. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pages 4848 4856. PMLR, 2018
[91] Ioannis Tsaknakis, Mingyi Hong, and Sijia Liu. Decentralized min-max optimization: For- mulations, algorithms and applications in network poisoning attack. In ICASSP 2020 2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 5755-5759, 2020.
[92] César A Uribe, Soomin Lee, and Alexander Gasnikov. A dual approach for optimal algorithms in distributed optimization over networks. arXiv preprint arXiv: 1809.00710 2018.
[93] Paul Vanhaesebrouck, Aurélien Bellet, and Mare Tommasi. Decentralized collaborative learning of personalized models over networks. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 54, pages 509-517.
PMLR, 2017.
[94] Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-effiienn SGD algorithms. arXiv preprint arXiv:1808.075700 2018.
[95] E. Wei and A. Ozdaglar. Distributed alternating direction method of multipliers. In 20/2 IEEE
5 Stst IEEE Conference on Decision and Control (CDC), pages 5445-5450, 2012.
[96] Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local SGD for heterogeneous distributed learning. In Advances Neural Information Processing Systems 33 (NeurIPS), 2020.
16

---

[97] 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 25865-25877. Curran Associates, Inc., 2021.
[98] Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(():65-77, 2004.
[99] Siyu Xie and Lei Guo. Analysis of distributed adaptive filters based on diffusion strategies over sensor networks. IEEE Transactions on Automatic Control, 63(11))3643-366 2018.
[100] Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. Sgd converges global minimum in deep learning via star-convex path. arXiv preprint 1XXiv:9901.00411 2019.
[101] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J. Smola. Parallelized stochastic gradient descent. Advances Neural Information Processing Systems 23, pages 2595 Curran Associates, Inc., 2010.
17

---

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], mostly theoretical 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 3
(b) Did you include complete proofs of all theoretical results? [Ys]] Supplementary Material
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]. Section A.1
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] Section 5.2
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes], Section
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 eite the creators? [Yes]. Section 5.2, we eite CIFAR and DCGAN
(b) Did you mention the license of the assets? [N/A], use open assets
(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]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or 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 Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
18


Reviews:
[{"review_id": "zl6qj2PXtaT", "reviewer": "Reviewer_dmBR", "summary": "This paper studies distributed stochastic variational inequalities (VIs) problems on unbounded domains while the data on different devices might be heterogeneous (non-IID). The authors propose a new algorithm that (1) the gossip matrix is drawn from some distribution in very communication and (2) multiple updates are made on every device between two communications. The authors prove that the proposed method speedups in all strong-monotone, monotone, and non-monotone cases. Comprehensive experiments show that the proposed method have faster speeds in solving distributed stochastic saddle-point problems (SPP), e.g., to training Deep Generative Adversarial Networks (GANs).", "questions": "Please clarify the difference and advantages from the following papers:\n\nA. H. Sayed, Diffusion adaptation over networks, vol. 3, pp. 323-453, 2014.\n\nA. H. Sayed, S. Y. Tu, J. Chen, et al, Diffusion strategies for adaption and learning over networks: an examination of distributed strategies and network behavior, IEEE Signal Processing Maganize, vol. 30, no. 3, pp. 155-171, 2013.\n\nS. Y. Xie, L. Guo, Analysis of distributed adaptive filters based on diffusion strategies over sensor networks, IEEE Transactions on Automatic Control, vol. 63, no. 11, pp. 3643-3648, 2018.\n\nS.A. Alghunaim, K. Yuan, A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing. 2022.\n\nA.S. Matveev, M. Almodarresi, R. Ortega, A. Pyrkin, S. Xie. Diffusion-based Distributed Parameter Estimation Through Directed Graphs with Switching Topology: Application of Dynamic Regressor Extension and Mixing. IEEE Transactions on Automatic Control. 2021.", "limitations": "The authors did not discuss the limitations and potential negative societal impact of their work, while no significant issues are identified.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n+ The idea makes sense. Multiple diffusions on devices between two communications can certainly speedups the training.\n+ The experiments are nice for a theory-intensive paper. The results are in agreement with the theory.\n+ The proofs are comprehensive and clear. I do not find any major flaws.\n+ The authors provide the source code of the experiments.\n\nCons:\n- The motivations are quite straightforward. I am concerned it is not novel. Please clarify the difference and advantages from the following papers:\n\nA. H. Sayed, Diffusion adaptation over networks, vol. 3, pp. 323-453, 2014.\n\nA. H. Sayed, S. Y. Tu, J. Chen, et al, Diffusion strategies for adaption and learning over networks: an examination of distributed strategies and network behavior, IEEE Signal Processing Maganize, vol. 30, no. 3, pp. 155-171, 2013.\n\nS. Y. Xie, L. Guo, Analysis of distributed adaptive filters based on diffusion strategies over sensor networks, IEEE Transactions on Automatic Control, vol. 63, no. 11, pp. 3643-3648, 2018.\n\nS.A. Alghunaim, K. Yuan, A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing. 2022.\n\nA.S. Matveev, M. Almodarresi, R. Ortega, A. Pyrkin, S. Xie. Diffusion-based Distributed Parameter Estimation Through Directed Graphs with Switching Topology: Application of Dynamic Regressor Extension and Mixing. IEEE Transactions on Automatic Control. 2021.\n\n- The paper seems written in a rush. Many typos exist.", "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": "w2ckSbpKWc", "reviewer": "Reviewer_zZ6M", "summary": "This paper focuses on decentralized local stochastic extra-gradient for variational inequalities.\nThis paper uses extra-gradient as the main tool to solve saddle point problems which satisfy variational inequalities.\nThe results of this paper are not surprise but still have their own value.", "questions": "No.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The techniques in this paper are regular and the results of this paper are not surprise.\nBut the results of this paper have their own value.", "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": "hQtcddfGG8", "reviewer": "Reviewer_n86C", "summary": "This paper proposed a decentralized extra-gradient method with intermittent communications to solve distributed variational inequalities problem, and one important scenario is federated GAN training or federated adversarial training. They consider the setting where clients are connected with a decentralized network and clients only synchronize with its neighborhood. They provide the convergence rate for strongly monotone, monotone and non-monotone cases. The rates make sense. They also provide experiments validating their algorithms' effectiveness and efficiency.", "questions": "Please refer to weakness part.", "limitations": "This is pure theory paper so I did not see any negative societal impact.", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nAs far as I know, this paper is the first to analyze the extragradient method, a celebrated algorithm in minimax/variational inequality optimization, in decentralized and intermittent communication settings. Due to the rise of federated GAN and adversarial robust training, distributed minimax problems received increasing attention from optimization and ML community. Hence, the theoretical results in this paper have its own value.\n\nWeakness:\nMy main concern is that the authors assume unbounded parameter domain, but in the monotone setting, we have to assume the parameters are bounded to get a meaningful convergence bound, i.e., in equation (7), they have to assume max_{z,z'}||z-z' || is bounded. I understand that adding projection may collapse existing proof, but assuming bounded domain without projection operator looks unreasonable to me.", "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": "UMI4QsA_nSE", "reviewer": "Reviewer_nETb", "summary": "In this work, the authors address the problem of solving minty variational inequality in decentralized optimization. They extend extra-gradient to this setup and prove convergence results under different assumptions on the operator (strong monotonicity, monotonicity, existence of Minty solution) and a weak assumption on the network topology (expected multi-step contraction). These theoretical results are further complemented by experiments on a syntactic problem and GANs.", "questions": "1. In (7) and (8) the supremum is outside the expectation while for stochastic VIs it is more common to have supremum inside the expectation and there is a standard process to achieve this in the centralized case. Actually, it is more meaningful to have the supremum inside the expectation because the gap function should be used as a measure for every realization. Therefore, I am wondering if we can get a result of this kind here or if there is any technical difficulty that makes the authors to present results like this.\n\n2. In the experiments, the authors observe linear convergence in the bilinear case when there is no noise. I understand why this should be the case in the centralized case. However, in the decentralized case with data heterogeneity, the presence of network error should prevent the iterates from converging, as we see in the strongly monotone setup. Could you please explain why this is not observed in the bilinear case?", "limitations": "Fine", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work nicely complements the existing literature by providing an exhaustive analysis on decentralized extra-gradient for solving VI problems. On the positive side, the assumption made in this work about the network allows us to take into account various communication schemes. Moreover, their convergence rates feature explicit dependence on different constants of the problem and the network. \n\nOn the downside, the proposed algorithm can only partially handle the case of non-monotone operators with minty solutions. In fact, both $\\sigma$, the standard deviation of the noise, and $D$, the variability among nodes appear in the bounds (9) and (10) in terms that do not depend on $K$. Even if $D=0$, one still needs to increase the batch size to get better accuracy. This is probably a problem that already needs to be addressed in the centralized case.\n\nI also feel that it is not clear what the authors want to convey through section 5.2. We can probably also get the same types of results with other decentralized algorithms that are mentioned in related work.", "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