Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees
Authors: Aleksandr Beznosikov
Peter Richtárik
Michael Diskin
Max Ryabinin
Alexander Gasnikov
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex optimization
compression
variational inequalities
saddle point problems

Abstract: Variational inequalities in general and saddle point problems in particular are increasingly relevant in machine learning applications, including adversarial learning, GANs, transport and robust optimization. With increasing data and problem sizes necessary to train high performing models across various applications, we need to rely on parallel and distributed computing. However, in distributed training, communication among the compute nodes is a key bottleneck during training, and this problem is exacerbated for high dimensional and over-parameterized models. Due to these considerations, it is important to equip existing methods with strategies that would allow to reduce the volume of transmitted information during training while obtaining a model of comparable quality. In this paper, we present the first theoretically grounded distributed methods for solving variational inequalities and saddle point problems using compressed communication: MASHA1 and MASHA2. Our theory and methods allow for the use of both unbiased (such as Rand$k$; MASHA1) and contractive (such as Top$k$; MASHA2) compressors. New algorithms support bidirectional compressions, and also can be modified for stochastic setting with batches and for federated learning with partial participation of clients. We empirically validated our conclusions using two experimental setups: a standard bilinear min-max problem, and large-scale distributed adversarial training of transformers.

Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees
Aleksandr Beznosikoy
Innopolis UniV HSE University and Yandex, Russia
aubezmosikov@@mail.com
Peter Richtárik
Michael Diskin
KAUST Saudi Arabia
HSE University and Yandex, Russia mi michael. w.disiinngmmil.c.mmmm com
peter reter..rihhtarikkkass.ccc edu.
Max Ryabinin
Alexander Gasnikov
Yandex and HSE University, Russia
MIPT, HSE University and IITP RAS, Russia gasnikovyyandex.rg
mryabininO@gmail. com
Abstract
Variational inequalities in general and saddle point problems in particular in- creasingly relevant in machine learning applications, including adversarial learn- ing, GANs, transport and robust optimization. With increasing data and problem sizes necessary to train high performing models across various applications, we need rely on parallel and distributed computing. However, in distributed train- ing, communication among the compute nodes is key bottleneck during train- ing, and this problem is exacerbated for high dimensional and over-parameterized models. Due to these considerations, it is important to equip existing methods with strategies that would allow reduce the volume of transmitted information during training while obtaining model of comparable quality. In this paper, we present the first theoretically grounded distributed methods for solving varia- tional inequalities and saddle point problems using compressed communication: MASHA1 and MASHA2, Our theory and methods allow for the use of both unbi- ased (such as Randk; MASHA1) and contractive (such as Topk; MASHA2) com- pressors. New algorithms support bidirectional compressions, and also can be modified for stochastic setting with batches and for federated learning with partial participation of clients. We empirically validated our conclusions using two exper- imental setups: standard bilinear min-max problem, and large-scale distributed adversarial training of transformers.
"Research Center for Artificial Intelligence, Innopolis University
1 MMsscow Institute Physics and Technology
*King Abdullah University of Science and Technology $ Institute Information Transmission Problems RAS
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Introduction
1.1
The expressive power of variational inequalities
Due to their abstract mathematical nature and the associated flexibility they offer in modeling various practical problems of interests, variational inequalities (V]) have been an active area of research in applied mathematics for more than half century [65]] G1l 22 It is well known that VIs can be used formulate and study optimization problems, saddle point problems (SPPs), games and fixed point
problems, for example, in an elegant unifying mathematical framework
[
Recently, a series of works by various authors [1 and GANs (28). This allows to successfully transfer established insights and well-known techniques from the vast literature on VTs/SPSs, such averaging and extrapolation, to the study of GANs. Be- sides their usefulness in studying GANs and alternative ad adversarial learning models [57]. VIs/SPPs have recently attracted considerable attention of the machine learning community due their ability to model other situations where the minimization of single loss function does not suffice, such as auction theory M supervised learning with non-separable loss 39 or non-separable regularizer i and reinforcement learning 69 66 38.
26 58
10
built a bridge between VIs/SPss
In summary, VIs have recently become potent tool enabling new advances in practical machine learning situations reaching beyond supervised learning where optimization problems and tech- niques, which can be seen as special instances of VIs and methods for solving them, reign supreme.
1.2 Training of supervised models via distributed optimization
On the other hand, for classical and much better understood supervised machine learn- ing/minimization problems, researchers and practitioners face other challenges, which, until cently, have been outside of VI's research. Indeed, the training of modern supervised machine learning models in general, and deep neural networks in particular, is still extremely challenging. Due to their desire to improve the generalization of deployed models, machine learning engineers need rely on training datasets of ever increasing sizes and elaborate over-para models [5]. Supporting workloads of such unprecedented magnitudes would be impossible without com- bining the latest advances in hardware acceleration, distributed systems and distributed algorithm design
83
When training such modern supervised models in a distributed fashion, communication cost is of- ten the bottleneck of the training system, and for this reason, a lot of effort was recently targeted A par-
at the design of communication efficient distributed optimization methods <S| ticularly successful technique for improving the communication efficiency of distributed first order optimization methods is communication compression. The idea behind this technique is rooted in the observation that in practical implementations it often advantageous to communicate messages compressed via (often randomized) lossy compression techniques instead of communicating the full messages [A 2 If the number of parallel workers is large enough, the noise introduced by com- pression reduced, and training with compressed communication will often lead to comparable test error while reducing the amount of communicated bits, which results in faster training, both in
76 25 29
theory and practice (59 29
1.3 Two classes of compression operators
The paper focuses on compression methods for distributed VIs and SPPs. Let us give the main definitions. We say that a (possibly) stochastic mapping Q I Rd is an unbiased compression operator if there exists a constant g 2 1 such that
RQ(=)= z, [][@(=)11 < 4/1213
Ve Ve
(1)
Further, we say that a stochastic mapping C Rd there exists constant d 2 1 such that
Rd is a contractive compression operator
E||C(=) - =1I² < (1 - 1/1), Ve E Rdd
(2)
b the number of bits needed to represent a single float (e.g., 32 or b 64), then the number of bits needed to represent generic vector E R2 is || == bd. To describe how much

---

compression operator reduces its input vector on average, we define the notion of expected density, denoted via 8-1 bd ( bats- where [[Q()) 3)) Ibiss is the number of bits needed represent the
quantized vector Q Note that 3 2 1. For the Randk operator 3 10 we have q = B = d/k.
1.4 Towards communication--ffiiiee distributed methods for VIs and SPPs
Classical VI/SPP algorithms such as the Extra Gradient method originally proposed by later studied by many authors [62 AI, including in a distributed environment 77
46 and
52 73
Among them, a number of works stand out trying to solve the communication bottleneck challenge
using various approaches such as local steps, data- similarit etc. SS B4 16
III 12). But despite
the fact that the use of compression is one of the most popular communication-efficci approaches for distributed minimization problems, no work has yet paid attention to the compression technique neither for distributed SPPs nor for VIs, with the exception of the work [S which relies round- ing to the nearest integer multiple of a certain quantity. This compression mechanism does not offer theoretical benefits and does not even lead to convergence the solution since the errors introduced through rounding persist and prevent the method from solving the problem.
2 Summary of Contributions
In this paper, we investigate whether it is possible to design communication-effiiienn algorithms for solving distributed VI/SPP by borrowing generic communication compression techniques Q
and 2 from the optimization literature 75 2
59
29
72 and embedding them into established,
efficient methods for solving VIs/SPPs problem. In summary,
46
11
II Whether or not this is possible is an open
we design the first algorithms with compression for solving general distributed VI/SPP (see Section Equation 3 in the determànistic (see 4 stochastic (see (44) and federated (see (54) regimes, supporting both unbiased (MASHA1 = Algorithms
3
and contractive (MASHA2 Algorithms 2 compressors. Convergence of all our methods are analyzed in strongly-monotove (strongly convex strongly concave), monotone (convex concave) cases.
non-moontonnemiint (non-commvx-nonn-com
2.1 Two types of compressors
We develop two approaches for distributed VIs/SPPs depending on whether we use unbiased | or contractive compressors, since each type of compressor demands a different algorithmic design and different analysis. In particular, contractive compressors are notoriously hard to analyze even for optimization problems 44 722. Our method based on unbiased compressors is called MASHA1 (Algorithm D. and our method based on contraction compressors is called MASHA2 (Algorithm
2.2 Theoretical complexity results
We establish a number of theoretical complexity results for our methods, which we summarize in Ta- ble (Appendix(A) We consider the strongly monotone (strongly convex- strongly concave), mono- tone (convex- concave) regimes as well as the more general non-monotone/minty (non-convex-non- concave) regime. In the strongly monotone case we obtain linear convergence results (O(log) 1/e) in terms of the distance to solution, in the monotone we obtain fast sublinear convergence results (O()))) in terms of the gap function, and in the non-monotone case we have sublinear convergence results (O(1/e²) in terms of the Euclidean norm of the operator. To get an estimate for the num- ber of information transmitted, one need to multiply the estimates from Table I by 1/3. Then we get that from the point of view of the transmitted information (and also time for communications), MASHA1 is better by factor 11/3 + 1/M (M number of workers) in comparison with the clas- sical Extra Gradient. It means that we get an acceleration of min vB: /M} times. For example, ADIANA from 4 (the theoretical SOTA method with unbiased compressions for strongly convex minimization) has the same accelaration. The same situation is with MASHA2, The method has the same compression dependent multiplier as ECLK from M (the theoretical SOTA with contractive compression for minimization). Based on these facts, we hypothesize that MASHA1 and MASHA2 have unimprovable estimates (see Appendix B
3

---

2.3 Stochastic case and variance reduction
MASHA1 and MASHA2 are designed to handle the deterministic setting. But often, in practice, the computation of the full operators/gradients is expensive, then we need to deal with stochastic realizations. In particular, a popular case when each operator/gradient has finite-sum structure on its own, c.g. finite-sum of batches. For this issuc, consider two modifications: VR-MASHA1 (Algorithm D and VR-MASHA2 (Algorithm p). Both are enhanced with bespoke variance-reduction techniques for better theoretical and practical performance. These results can be interesting in the non-distributed case. As far as we know, we are the first who consider variance reduction for non- monotone VIs. We found only one paper non-comvex-conean saddle point problems 87 under the PL condition. See Appendix for details.
2.4 Federated learning and partial participation
Federated learning 45 42 is an important and popular branch of distributed methods. Therefore, good bonus for the algorithm is that it can be easily adapted for it. In federated setup where the computing devices are mobile phones, tablets, personal computers etc, the importance of communication bottleneck is even higher. In such circumstances, devices can have weak and slow connections, or they can even disconnect for a while. At such moments, it is not necessary to interrupt the learning process, and only available devices can be used. Therefore, introduce two modifications: PP-MASHA1 (Algorithm 7 and PP-MASHA2 (Algorithm D that support the mode of partial participation of devices in the learning process. For minimization problems, combination of quantization and partial participation occurs in 33 68
The results are contained in Appendix
2.5 Bidirectional compression
Most methods, especially with contractive compressors, only compression when transferring information from devices to the server. Meanwhile, quite often in practical situations, the transfer
of information from the server to the device is also expensive 32
g1 [8 In such situations it also
makes sense to compress the information when sending it from the server to the agents. We can highlight some works bidirectional unbiased [68] and contractive compressors 190 81 55 23
for distributed minimization problems. But most of these methods have their small shortcomings in theoretical analysis such deterministic setting only, homogeneity of local functions, etc. All our methods MASHA1, MASHA2 and their modifications support bidirectional compression. See Appendix D and for details.
2.6 Experiments
Toy experiments bilinear problems show that methods with compression for minimization prob- lems may not work (diverge) for SPPs. Also we verify that MASHA1 and MASHA2 are much better than the classical Extra Gradient with added unbiased compression. Experiments adversarial training of large-scale transformer (ALBERT) show the practical importance of compression dis- tributed methods for large SPPs.
Problem Formulation and Assumptions
3.1 Problem formulation
We study distributed variational inequality (VI) problem
Find z" e Rdd such that (F(2*),=-2") 0, V2 Rd
(3)
where F' Rd + gd is an operator with certain favorable properties (e.g., Lipschitzness and monotonieity). We assume that the training data describing F' distributed across M work- ers/nodes/clients
M Σ (z), m==1
F(z) = M
(4)

---

where Fm R - R for all m E , M). Next, we give main examples of VIs to show the breadth of this formalism.
Example 3.1 (Minimization) Consider the minimization problem:
min f(z).
(5)
Suppose that F(z)= == fz). Then, if f convex, it can be proved that =" E Rd is solution for if and only if Rd is a solution for 5 And if the function f is non-conver, then x" IRd is a solution for and only if ff(²) 0, ie. z" is stationary point.
Example 3.2 (Saddle point problem) Consider the saddle point problem:
min max g(x. y). zER yERdy
(6)
Suppose that F(2) == F(x,y) (Vgg(r,)) V yz, y) and 2 Rd x Rdy Then, if g is
convex-concave, it can be proved that 2" 2 is solution for 3 if and only if 2 is solution
for O And if the function is nan-convxx-no--oneee
then z" E Z is a solution for 3 if and only if V v=9(=" y²) = 0 and V v,g(=*, y²) 0, i.e. x² is stationary point.
minimization problems are widely researched separately from variational inequalities. The study of saddle point problems often is associated with variational inequalities, therefore saddle point problems are strongly related to variational inequalities.
Example 3.3 (Fixed point problem) Consider the fixed point problem:
Find z" E TRdd such that T(=*) =
where Rd + Id an operator. With F(z) = T(z), can be proved that IRd is solution for B and only F(2*) i.e. 2" IR is a solution for 7
3.2 Assumptions
Next, we list two key assumptions both are standard in the literature on VIs.
Assumption 3,4 (Lipschitzness) The operator F is L-Lipschitz continuous, i.e. for all 21, 22 Rdd we have [1F(2z) F(22)ll S L||a1 - 22ll-
Each operator Fm is Lm -ipschhiz continuous, i.e. for all R2 E
Rd it holds (Z1(
M
Fm (22))) < 1. 22|1. Let us define new constant L as follows 2 =
1
Σ L2
m=1
For saddle point problems, these properties are equivalent to smoothness.
Assumption 3.5 (Monotonicity) We need three cases of monotonicity
(SM) Strong monotonicity. The operator F p-strongly monotone, i.e. for all 21, Rd we have (F(z1) - F(2),, 22) p1 |2
(M) Monotonicity. The operator F monotone, i.e. for all 21, 22 E Rd we have (F(21)
F F(22). 21 22) 2 0.
(NM) Non-monotonicity. The operator F is non-monotone (minty), and only if there exists z"
d such that for all z E Rd we have (F(2), - 2*) 2
The last assumption is called the minty variational stability condition. It is not general non- monotonicity, but is already associated in the community with montooootyyyy
14 37
53 43
36 19), particularly with the setup, which is somewhat appropriate for GANS 5 52
4
MASHA
In this Section we present new algorithms and their convergence. Section 4. is devoted to the algo- rithm (MASHA1) with unbiased compression. Section 4.2 to algorithm (MASHA2) with contractive

---

compression. Appendix gives modifications for the stochastic case Section F and for the feder- ated learning
Section
Appendix is devoted the hypothesis about optimality of MASHA1
and MASHA2.
4.1 MASHA1: Handling Unbiased Compressors
Before presenting our algorithm, let discuss which approaches be used construct it. As discussed in Sections a compression methods play an important role in distributed minimiza- tion problems. All these methods modifications of the classical GD. For instance, the authors of [2] compress stochastic gradients. Therefore, it is a natural idea to use GD-type methods for Vis well. But it is well-known fact that GD-type methods can give bad convergence estimates (see Section B.1 from (67]) or do not converge at all (see Section 7.2 and 8.2 from 27 ) even on the simplest SPPs and VIs. From practical point of view, this approach can also fail (see QSGD and EF in Section 5.1 In the non-distributed case, this problem has long been solved and the Extra
Gradient method 46 62
41 is used instead of GD:
_k+1/2 2t FF((=", gh+1
(8)
This method is optimal for both VIs and SPPs and has an estimate of convergence (4/a) in the strongly monotone case. Therefore, the second idea for the compressed method to add compres- instead of F(2*) and F(2*+1/2). In Section we analyse this method, but gives an estimate Ô (1 + g/M) 1/2)), which considerably worse in terms of 1/4 than the original Extra Gradient method. The key problem is that in the analysis one has to deal with [[Qx(F(<*+122) - Qx+1/2 1/2 (F(2))) With- out compression operators, such difference is easily evaluated using Assumption 3.4 But when the compression operators are different (in fact the same, but have different randomness) we cannot make a good estimate for this term. The idea arises use the same randomness in both steps of the method g namely to substitute Qu (F(t)) and (x((((+11/)) But then *+11/2 depends on the randomness Qk. and hence Qu (F(*st11)) is biased, which further complicates the analysis. For exactly the same reasons, the various optimistic/single call modifications
sion operators the method (8) c.g. use (F²((² and 1x=1/2(
70 26 35
[ of the Ex-
tra Gradient method did not work for either. We have also test the method with compressions in practice (see CEG in Section B.J). and it turns out to be worse than the method we will present below. In the end. the use of variance reduction and negative momentum techniques [ is key in creating our algorithm. These tricks are not in themselves relevant to distributed problems, but, in case, they help in creating MASHA1 and MASHA2.
Algorithm MASHA1
Parameters: Stepsize 7 > 0, parameter 7 E (0; 1), number of iterations K.
Initialization: Choose 20 w E Z.
Devices send Fm (w to server and get F(w²)
for k = 0, 2,,,,,.... K - do
for each device m in parallel do ,++1/2 -2 (1 7 T)w Sends 9th Q (F h11/2) Fmm (w) to server end for
(w)
for server do
Sends to devices g² Qserv
M M 2m=1 Fm
Sends to devices one bit by with probability - O with with probability f end for
for each device in parallel do
=k+1 = 2 1+122 7 If by then k.t zt, sends F, (w to server and gets F(w++))
else k+1 wi
end for end for
At the beginning of each MASHA1 iteration, all devices know the value of F(w*), hence they can calculate the value of x+1/22 locally without communications, Further, each device sends the com-

---

pressed version of the difference Fm (12) (w)) to the server. The compression on these transfers done by their local {Qu operators. The server aggregates the information from de- vices, averages it, compresses by Qeev operator and makes a broadcast to all devices. As a result, an unbiased estimate of F(2 F(w") appears at each node. Also, the nodes receive one bit of information by. This bit is generated randomly on the server and is equal to with probability 1 - r (where 1 - is small). Note that by can be generated locally, it is enough to use the same random generator and set the same seed on all devices. Next, the devices locally make a final update on 2 +++ The final step is an update of w if by- = 1, then ** 1 = z* or otherwise w =++ w². In the case when w = 2t, we need to exchange the uncompressed values of Fmm (ww++1) in order to ensure that the beginning of the next iteration the value of F( known to all agents. We use a possibly difference compressor on each device and also on the server. To distinguish between them, we denote the following notation: Qthy 9m guher and Quer, gutry, 3
Theorem 4.1 Let Assumption 3.4 and one case of Assumption a.re are satisfied. Then for some step y the following estimates on MASHA1 number of iterations achieve e-solution holds
in strongly monotone case (in terms of Ell
2011 E): 011 + PV1= log = :
Cg
in monotone case (in terms of E max; ed Ec (F((), ( & KK-1 x 1/2) u)] ~E): O -
C -
in non-monotone case (in terms of E.| Ek=0 || ~ 22): 0 (-(1-T)
where C2 - - Em M
do L2, (M- 1)(²).
A full description of the algorithm, as well as a full statement of the theorem with proof, can be found in Appendix D
The bounds in Theorem are related to r. Let us find an optimal way to choose it. Note that (in average) once per 1/(1-7) iterations (when by 1), we send uncompressed information. Based on this observation, we can find the best option for т. Let us analyze the case of compressions only on the devices' side (g = 1). For simplicity, we put Qtyy = Q with gth q and 3 = B, also Lm L = L. Since compression is done only devices, we assume that the server's broadcast is cheap and we only care about devices. Then at each iteration the device sends O (1/8 + 1 - r) bits each time information compressed by /3 times and with probability From where we immediately get the optimal choice for T:
we send the full package.
Let Assumption 3.4 and one case of Assumption 3.3 are satisfied. Then for some step Y and 1 = 1/3 the following estimates on MASHA1 number of iterations achieve e-solution holds
Corollary 4.2
in strongly monotone case:
O(3
98
+
Lo
L p
!)
in monotone case: (V
q8 MT
+ + LI
( M + 3) 1.211
in non-monotone case:
We can see that MASHA1 can outperform the uncompressed Extra Gradient method. Let us compare them in the strongly monotone case. The communication complexity of the Extra Gradient method is (LL))). MASHA1 has communication complexity 0f + 1/8. l/r). For practical compressors TC.. B Z q. Then, one can note that the communication complexity of MASHA1 differs from the complexity of the uncompressed method by an additional factor (///M + 1/a). It is easy to see that even for a small number of devices M and expected density 8. this factor is less than 1, hence MASHA1 outperforms the uncompressed method. We think that this factor (V//M + 1/8) is theoretically unimprovable and optimal - see Section for details.
One can also consider the case of bidirectional compression (g + 1). Table (line 3) shows the result for ze dev = q. gserv gdev / and 1 1/3.
4.2
MASHA2: Handling Contractive Compressors
The use of contractive compressions is more complex issue. particular, it known that if one simply put contractive cospressor instead of an unbiased one, the method may diverge even for
7

---

quadratic problems [T]. To fix this, an error compensation technique 78 point of this approach to keep untransmitted information and add it to new package at the next iteration. This is the main difference between MASHA2 and MASHA1. MASHA2 introduces additional sequences ex en for the server's and devices' error. To define contractive operators on devices and on the server, we introduce the following notation: Chty, , ,ddv and Caey, g Brer.
44 79
is used. The
Algorithm 2 MASHA2
Parameters: Stepsize y > 0, parameter T, number of iterations K.
Initialization: Choose 20 w E Z, e 0, e O.
Devices send Fm (w=) to server and get F(w")
for 0, K do
for each device in parallel do
gkt1/2 = T2 + (1 T)w 7F (w=) Sends 9m = Ouhy (7 (m
"m (w*) + tem) to server
c++ = em + 7 ml (+11/12 - - Fm (wx) gm
end for
for server do
Sends to devices g² = C 1 Em Iih + ct
ek+1 = + 17 Σm= gm Sends to devices one bit by with probability T,, O with with probability end for for each device in parallel do
2 2 = 2 1/2 7
If by then w = sends Fm (u to server and gets F(w++1)
else wx+ w.
end for
end for
In the case of MASHA1, the key theoretical issue was the choice of a basic method (we discussed this at the beginning of Section 4.1. MASHA2 raises another problem for theoretical analysis, how to combine MASHA1 and the error feedback technique. The analysis
methods with error com- pensation for the minimization problem min (xx is entirely tied to the existence of the function
179 Zil 72). In particular, the differences (f(-) ((()-ffee ff(=)) appear in the whole analysis and is key in the technical lemmas. As result (f(.) f(*)) is used
convergence criterion even in the strongly convex case. But for VIs there is no function f. only the operator F (the existence of g(x, y) in SPP setup does not save the situation). This problem solved in the proof of Theorem
4.3 by using additional sequence +|/2+1 w*Il
Theorem 4.3 Let Assumption 3.4 and one case of Assumption 3.5 are satisfied. Then for some step y the following estimates on MASHA2 number of ilerations achieve e-solution holds
in strongly monotone case (in terms of [[|| - 2- 101 E): 011 + 8 gut L log 1): MVT
in monotone case (E max:ec| (F(()) ( KK11 x+1//2 - w/} ~ E): O 8 gom 11==0==11
8VI-7
in non-monotone case (in terms of E K-1 |[ ~ 22); O (8tt gum 12221=0=="11
(2(1-)
full listing of the algorithm, as well as a full statement of the theorem with proof, can be found in Appendix
The same way as in Section we can consider only devices' or bidirectional compression. In
particular, in the line of Table we put results for gaerv = 1, gdev 8, Lm L and
-- = 3. In the line 4 of Table there are results for gserv = gdev 6, I'm T. and
- -- = B.
8

---

Experiments
5.1 Bilinear Saddle Point Problem
We start our experiments with a distributed bilinear problem, i.c. the problem @ with
gm y) = x. Amy + a + b + || l1v11
where Am E Rdxdd Om: bm E R This problem is X-strongly convex convex-strongly strongly-concat and, moreover, all functions Im are || Am Ammll--smooth Therefore, such a distributed problem well suited for the primary comparison of our methods. We take d = 100 and generate positive definite matrices Am and vectors Om, dm randomly, is chosen as max Am 1
The purpose of the experiment is to understand whether the MASHA1 and MASHA2 methods are superior to those in the literature. As a comparison, we take QGD 2 with Random 30%, classical Error Feedback (78 with Top 30% compression, as well as CEG (Section H Compressed Extra Gradient, each step of which we use Random 30%. MASHA1 (Algorithm M we also used Random 30%, in MASHA2 (Algorithm 2 for best convergence.
Top 30%. See Figure The stepsizes of all methods are chosen
Figure 1: Comparison MASHA1 (Algorithm I and MASHA2 (Algo-
We see on Figure that methods based on gradient descent (QSGD and EF) converge slowly. This confirms that one needs to specifically designed for saddle point problems (for example, the extra- gradient method), and not classical optimization methods. The much slower convergence of CEG shows the efficiency of our approach in which compress the differences F', (=+1//2) F(w*). MASHA2 wins MASHA1, This shows that in practice a contractive compressor can perform better than an unbiased one with the same parameters.
rithm 2 with Error Feedback, QGD and Compressed Extra Gradient
(CEG) in iterations and in Mbytes for
0500
OSCD
1011
method
30/
Ag
lleration, N
Tranumitted cata, Mayses
5.2 Adversarial Training of Transformers
We now evaluate how compression performs for variational inequalities (and for saddle point prob- lems, as special case) in a more practically motivated scenario. Indeed, saddle point problems (special case of variational inequalities) have sample applications in machine learning, including ad- versarial training. And our goal is show that compression provides important improvements for such lcage-scale problems as well. We train a transforme--bar based masked language model [8] |8 56
using fleet of 16 low-cost preemptible workers with T4 GPU and low- wow-bandwidth interconnect. For this task, we use the compute-efficient adversarial training regimen proposed for transformers by 99 54 Formally, the adversarial formulation of the problem is the min-max problem
1 Σ I(f(w, + Pas yn. 1110
min max w [pallse N
where w are the weights of the model, ((r,s ) are pairs of the training data, p is the so- called adversarial noise which introduces a perturbation in the data, and are the regularization parameters. To make our setup more realistic, we train ALBERT-large with layer sharing 47]. which was recently shown be much more communication-efficii
during training 74 20 We train our model on combination of Bookcorpus and Wikipedia datasets with the same optimizer (LAMB) and parameters as in the original paper [47] use the adversarial training configuration of 191] and follow system design considerations for preemptible instances ! In LAMB optimizer we change the original positive momentum to negative momentum, as MASHA, This means that we do not exactly use MASHA in these experiments, but combination of MASHA and LAMB. In fact this the theoretical methods are combined with
approach is typical, e.g., papers Adam.
26

---

In terms of communication, we consider 4 different setups for gradient compression: the "baseline" strategy with uncompressed gradients, full 8-bit quantization [1 50 mixed 8-bit quantization, and Power compression S4 with rank r-8. For mixed 8-bit quantization and Power we only apply compression to gradient tensors with more than 2 elements, sending smaller ones uncompressed. These small tensors represent layer biases and LayerNorm scales 6 that collectively amount to s 1% of the total gradient, but can be more difficult to compress than regular weight tensors. Finally, since Power is biased compression algorithm, we use error feedback ++ [2] with a modified formulation proposed by [84] For all experimental setups, we report learning curves in terms of the model training objective, similarly to [44
[4). To quantify the differences in training loss better,
also evaluate the downstream performance for each model on several popular tasks from [5 after each model was trained on approximately 80 billion tokens. Finally, we measure the communication efficiency of each proposed strategy by measuring the average wall time per communication round when all 16 workers are active.
The learning curves in Figure (upper) follow a predictable pattern, with more extreme compression techniques demonstrating slower per-iteration conver- gence. One curious exception to that is full 8-bit quantization, which was unable to achieve competitive loss. The remaining three setups converge similar loss values below 2. Both the baseline and mixed 8-bit compression show similar values in terms of downstream performance, with Power compression showing mild degradation. But in terms of information transfer time, methods using compression (especially Power) are significantly superior to the method without compression. This makes it possible to use such techniques to increase the training time without sacrificing quality.
Figure 2: (upper left) ALBERT training objective convergence rate with different compression algorithms: (upper right) ALBERT train- ing objective convergence rate with different compression algorithms (zoomed); (lower) Average wall time per communication round with standard deviation over repetitions and downstream evaluation scores on GLUE benchmark tasks after at 80 billion training tokens 1= op- timizer steps).
uncompresses
10
pure B-tt
2.4
9:5
Objuctive
rixedd Bibtt
power
2.3
zower
moad B-tr
Dijjective
training
2.3
2.0
3.8
Billins of tokens
Billons tolers
Sctup
Avg time
|CoLA
MNLI
MRPC
QNLI QQQ KTE
SST2
STS-B WNLI
Baseline
8.79 +: 0.03
45.2
81.1
83.0
88.3
89.0
67.8
85.5
89.4
18.3
Full 8 bit
4.42 1: 0.07
N/A
N/A
N/A
N/A
N/A
NIA
NIA
NIA
N/A
Mixed 8-bit
4.61 + 0.08
48.8
81.3
88.7
88.
85.2
64.3
88.3
87.5
16.9
Power
1.57 + 0.05
43.9
80.5
83.6
88.6
86.0
47.2
88.5
88.5
16.9
Conclusion
In this paper present algorithms with unbiased and contractive compressions for solving dis- tributed VIs and SPPs. Our algorithms are presented in deterministic, stochastic and federated ver- sions. All basic algorithms and their modifications support bidirectional compression. Experiments confirm the efficiency of both our algorithms and the use of compression for solving large-scale VIs in general.
In future works it is important to address the issue of the necessity to forward uncompressed infor- mation in some iterations. Although full packages are rarely transmitted, this is slight limitation of our approach. Lower bounds for compression methods are also an interesting area of research. At the moment there are neither such results for VIs and SPPs, nor for mininizations. In Appendix B we only hypothesize the optimality of our methods and back it up with analogies, provable lower estimates could complete the story with compressed methods.
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-0014 dd. 01.11.2021, IGK 000000D7303221550000)
10

---

References
[1] Ahmet Alacaoglu and Yura Malitsky, Stochastic variance reduction for variational inequality methods. arXiv preprint arXiv:2102.08352, 2021.
[2] Dan Alistarh, Demjan Grubic, Jenry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-effiieenn SGD via gradient quantization and encoding. In Advances Neural Information Processing Systems, pages 1709-1720, 2017.
[3] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, 2018.
[4] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1):8194 8244, 2017.
[5] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
[6] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization, 2016.
[7] Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Optimization with sparsity-indueing penalties. arXiv preprint arXiv: 2011.
[8] Babak Barazandeh, Tianjian Huang, and George Michailidis. A decentralized adaptive mo- mentum method for solving class of min-max optimization problems. Signal Processing, 189:108245, 2021.
[9] Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator The- ory in Hilbert Spaces. Springer, second edition edition, 2017.
[10] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased com- pression for distributed learning. arXiv preprint arXiv:2002.124100 2020.
[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] Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Dis- tributed saddle-point problems under similarity. arXiv preprint arXiv:2107.10706, 2021.
[13] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in gan training with variance reduced extragradient. arXiv preprint 2019.
[14] Cong D Dang and Guanghui Lan. On the convergence propertics of Euclidean extragradi- ent methods for variational inequalities with generalized monotone operators. Computational Optimization and Applications, 60(2):277-300, 2015.
[15] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference Learning Representations, 2018.
[16] Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1387-1395. PMLR. 2021.
[17] Tim Dettmers. 8-bit approximations for parallelism in deep learning. ICLR, 2015.
[18] Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT, 2019.
[19] Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured nonconvex-nonconcaat min-max optimization. International Conference on Ar- tificial Intelligence and Statistics (AISTATS), pages 2746-2754, PMLR, 2021.

---

[20] Michael Diskin, Alexey Bukhtiyarov, Max Ryabinin, Lucile Saulnier, Quentin Lhoest, Anton Sinitsin, Dmitriy Popov, Dmitry Pyrkin, Maxim Kashirin, Alexander Borzunov, Albert Vil- lanova del Moral, Denis Mazur, Ilia Kobelev, Yacine Jernite, Thomas Wolf, and Gennady Pekhimenko. Distributed deep learning in open collaborations. CoRR, abs/2106. 10207, 2021.
[21] Zehao Dou and Yuanzhi Li. On the one-sided convergence of adam-type algorithms in non- convex non-concave min-max optimization. arXiv preprint (tth:2109.142133, 2021.
[22] Francisco Facchinei and Jong-Shi Pang. Fimite-Dimensionel Variational Inequalities and Com- plementarity Problems. Springer Series in Operations Research, Springer, 2003.
[23] lyas Fatkhullin,, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. Ef21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.03294, 2021.
[24] William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint arXiv:2101.0396 2021.
[25] Avishek Ghosh, Raj Kumar Maity, Arya Mazumdar, and Kannan Ramchandran. Communica- tion efficient distributed approximate Newton method. In IEEE International Symposium Information Theory (ISIT), 2020.
[26] Gauthier Gidel, Hugo Berard, Gaötan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective generative adversarial networks. In International Confer- ence on Learning Representations, 2019.
[27] Ian Goodfellow. Nips 2016 tutorial: Generative adversarial networks. arXiv preprint
arXiv:1701.001660 2016.
[28] lan J. Goodfellow, Jean Pouget-Abadic Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. In Neural Information Processing Systems, 2014.
[29] Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non-convex distributed learning with compression. In 38th International Conference on Ma- chine Learning. 2021.
[30] Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum opti- mization problems: The results and construction. arXiv preprint (rXiv:2103.08288) 2021.
[31] T. Harker and J.-S. Pang. Finite-dimensional variational inequality and nonlinear comple- mentarity problems: a survey of theory, algorithms and applications. Mathematical program- ming, 1990.
[32] Samuel Horvath, Chen- Yu Ho. Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárík. Natural compression for distributed deep learning. arXiv preprint arXiv: 10988 2019.
[33] Samuel Horváth and Peter Richtárik. A better alternative error feedback for communication- efficient distributed learning. arXiv preprint arXiv:2006.1 / 1077, 2020.
[34] Charlie Hou, Kiran K Thekumparampil, Giulia Fanti, and Sewoong Oh. Efficient algorithms for federated saddle point optimization. arXiv preprint 2122v:21 2021.
[35] 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 1908 2019.
[36] Yu-Guan Hsich, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore ag- gressively, update conservatively: Stochastic extragradient methods with variable stepsize scal- ing. Advances in Neural Information Processing Systems, 33: 13:23323162234 2020.
[37] Alfredo N Jusem, Alejandro Jofré, Roberto Imbuzeiro Oliveira, and Philip Thompson. Extra- gradient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, 27(2)686-724, 2017.
12

---

[38] 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.
[39] Thorsten Joachims. support vector method for multivariate performance measures. pages 377-384, 01 2005.
[40] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive vari- ance reduction. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[41] Anatoli Juditsky, Arkadii S. Nemirovskii, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm, 2008.
[42] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. arXiv preprint 2019.
[43] Aswin Kannan and Uday V Shanbhag. Optimal stochastic extragradient schemes for pseu- domonotone stochastic variational inequality problems and their variants. Computational Op- timization and Applications, 74(3):779-82) 2019.
[44] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feed- back fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR, 2019.
[45] Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Pary Party Machine Learning Workshop, 2016.
[46] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[47] Zhen-Zhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self self-supervised learning of language representations. In International Conference on Learning Representations, 2020.
[48] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtarik. Acceleration for compressed gra- dient descent in distributed and federated optimization. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5895-5904. PMLR. 13-18 Jul 2020.
[49] Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local con- vergence of generative adversarial networks. Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 907-915. PMLR, 16-18 Apr 2019.
[50] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations, 2018.
[51] Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. arXiv preprint arXiv:1912.11942 2019.
[52] Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jerret Ross, Tianbao Yang, and Payel Das. decentralized parallel algorithm for training generative adversarial nets. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
13

---

[53] 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. 14380, 2019.
[54] Xiaodong Liu, Hao Cheng, Pengcheng He, Weizhu Chen, Yu Wang, Hoifung Poon, and Jianfeng Gao. Adversarial training for large neural language models. arXiv preprint wrXiv:204.08994, 2020.
[55] Xiaorui Liu, Yao Li, Jiliang Tang, and Ming Yan. A double residual compression algorithm for efficient distributed learning. In International Conference on Artificial Intelligence and Statistics, pages 333-143. PMLR, 2020.
[56] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: robustly optimized bert pretraining approach. ArXiv, 1tts/197..1110 2019.
[57] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In International Confer- ence on Learning Representations, 2018.
[58] 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. In International Conference on Learning Reprexentations, 2019.
[59] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 1e0:::99000000000 009269, 2019.
[60] Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of o o(L/k) for op- timistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4):3230-3251 2020.
[61] Soham Mukherjee and Mrityunjoy Chakraborty. A decentralized algorithm for large scale min-max problems. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 2967-2972, 2020.
[62] 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, 01 2004.
[63] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319 2007.
[64] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018
[65] Von Neumann and O. Morgenstem. Theory of games and economic behavior. Princeton University Press, 1944.
[66] 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 on Machine Learning (ICML), volume 70, pages 2681-2690. PMLR, 2017.
[67] Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle- point problems. In Advances in Neural Information Processing Systems, pages 1416-1424, 2016.
[68] Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guar- antees. arXiv preprint arXiv:2006. 14591, 2020.
[69] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In International Conference on Machine Learning, 2017.
[70] Leonid Denisovich Popov. modification of the arrow-hurwiez method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 2845):845-848, 1980.
14

---

[71] Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed sgd can be accel- erated. arXiv preprint arXiv:2010.00091, 2020.
[72] Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. arXiv preprint arXiv:2/06.05200 2021.
[73] Alexander Rogozin, Pavel Dvurechensky, Darina Dvinkikh, Alexander Beznosikov, Dmitry Kovalev, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. arXiv preprint arXiv:2102.07758, 2021.
[74] Max Ryabinin, Eduard Gorbunov, Vsevolod Plokhotnyuk, and Gennady Pekhimenko. Mosh- pit sgd: Communicationn-effccien decentralized training on heterogeneous unreliable devices, 2021.
[75] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data- lata-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
[76] V. Smith, S. Forte, C. Ma, M. Takáč, M. I. Jordan, and M. Jaggi. CoCoA: A general framework for communication-effcceent distributed optimization. Journal of Machine Learning Research, 18:1-49,20 2018
[77] Kunal Srivastava, Angelia Nedic, and Dusan Stipanovic. Distributed min-max optimization in networks. In 17th Conference on Digital Signal Processing, 2011.
[78] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. arXiv preprint 1.X9v08800007599 2018
[79] Sebastian Stich and Sai Praneeth Karimireddy, The error-feedback framework: Bet- ter rates for sgd with delayed gradients and compressed communication. arXiv preprint 1909.009000035000 2019.
[80] Vasilis Syrgkanis, Alckh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Neural Information Processing Systems, 2015.
[81] Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass error- compennatet compression. In International Conference on Machine Learning, pages 6165. PMLR, 2019.
[82] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez,
E. ukasz Kaiser, and Illia Polosukhin. Attention all you need. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 5998 6008. Curran Associates, Inc., 2017.
[83] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer. A survey on distributed machine learning. ACM Computing Surveys, 2019.
[84] Thijs Vogels, Sai Praneeth Karinireddy, and Martin Jaggi. Powersgd: Practical low-rank gra- dient compression for distributed optimization. Advances In Neural Information Processing Systems 32 (Nips 20/9), (2ONF), 2019.
[85] Alex Wang. Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv: 1804.07461, 2018
[86] Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. Advances in newral information processing systems, 29:3639-3644 2016.
[87] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for a class of arXiv:2002.09621, 2020.
minimax problems. arXiv preprint
[88] Deming Yuan, Qian Ma, and Zhen Wang. Dual averaging method for solving multi-agent saddle-point problems with quantized information. Transactions of the Institute of Measure- ment and Control, 36(1):38-44 2014.
15

---

[89] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the saddle point problems. arXiv preprint arXiv:1912.07481, 2019.
[90] Shuai Zheng, Ziyue Huang, and James Kwok. Communication-effiiini distributed blockwise momentum sgd with ertor-feedback. Advances in Neural Information Processing Systems, 12:11450-11461 2019.
[91] Chen Zhu, Yu Cheng, Zhe Gan, Siqi Sun, Tom Goldstein, and Jingjing Liu. Freelb: Enhanced adversarial training for natural language understanding. arXiv preprint 19X1v:99091170000 2019.
16

---

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? [Yes]. Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes], but we can only after de-anonymisation
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Section 5.1 and 5.2
(c) Did you report eтror bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]. Figure 2 left
(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], but we can only after de- anonymisation
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes], Section 5.2
(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 URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able 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]
17


Reviews:
[{"review_id": "o6KR5q9_xfz", "reviewer": "Reviewer_9vze", "summary": "The authors propose communication-compressed methods for solving a particular class of problems that they refer to as \"variational inequalities\". The authors prevent theoretical guarantees for their method, claim that a naive compressed-gradient based approach will fail in general, and present experiments demonstrating benefit to their technique over a naive compressed-gradient based.", "questions": "I do not have any questions for the authors", "limitations": "Negative societal impact is not an issue here.", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Major caveat to review\n- I have not had time to go deeply through the mathematical content of this paper, therefore my review will not be able to address this aspect\n- I apologise that my review thus addresses superficial aspects of the paper.\n\n### Strengths\n- the authors address a potentially practically useful problem, and produce both theoretical and experimental results on this topic.\n\n### Weaknesses\n- style violations. The authors greatly reduce the font-size of their figure captions, which as far as I am aware breaks the style rules, allowing them to fit more content into the 9 pages. This may sound a bit harsh, but I think that this is unfair to other authors who follow the rules and I would advocate for rejecting the paper for this reason.\n- the paper has not been properly proof-read. Basic aspects of the technical introduction contain errors. For instance, the saddle point problem is introduced as min-min on line 158 when as far as I am aware it should be min-max. Also on line 221, the symbol q^serv is used twice instead of the proper notation.\n- exposition. The exposition could be much clearer. For instance at line 154, no supporting intuition is offered about the mathematical form of the VI inequality, making it hard for an unfamiliar reader to build a working understanding of this topic.\n\n### Overall\nI want to apologise to the authors that my review is superficial. However, I am being clear about the fact that it is superficial. I want to add that I had a limited amount of time to review the work and ultimately needing to comment on things like style violations reduced the amount of time available to deal with the content.", "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": "Zq3zWYlcn5_", "reviewer": "Reviewer_X46K", "summary": "In this work the authors develop distributed communication-efficient methods for solving i)variational inequalities and ii)saddle point problems. The proposed algorithms (MASHA1 and MASHA2) utilize bidirectionally existing compression operators ( i) unbiased compression operator and ii) contractive compression operator) in order to reduce their communication cost in strongly monotone, monotone and non-monotone regimes. Convergence results are derived and presented for MASHA1 & 2 in all three regimes and numerical experiments showcase the merits suggested by the theory as well as the superior performance of the proposed methods compare to Extra Gradient. Stochastic variants (VR-MASHA1 and VR-MASHA2) with variance reduction are studied as well as connections to Federated Learning.  ", "questions": "The paper could certainly be improved substantially by more carefully revising the writing and the points mentioned in the 'Weaknesses section'.  Specifically the technical contributions and the description of algorithm 1 need to be more carefully rewritten. \n\nAlso as mentioned above the following parts need revising:\nThe sentence in lines 39-42 needs to be rephrased so that it has a clear meaning.\nline 53 : In 'implementations it often advantageous' there is an 'is' missing.\nline 56: Remove 'the' from 'lead to the comparable test error'.\nline 60: Remove 'Since' from the beginning of the sentence.\nline 79: Replace 'due to' with 'since'.\nline 87: Remove ''provably\nlines 130-131: Rephrase 'Moreover, devices can not only have a bad connection, in which one needs to compress data heavily, they can simply disconnect from the learning process'.\nlines 140-143: Need rephrasing.\nlines 209-221: The paragraph explaining MASHA1 needs to be rewritten. There are many typos and syntactic mistakes which make it hard to decipher the description of the algorithm.\nline 228 : Replace 'listing' with 'description'.\nline 230: 'an' is missing in 'Let us find optimal way to choose it'\nline 247 : Rephrase 'Then once can note that MASHA1 O(􏰖1/M + 1/β · L/μ) better than the uncompressed extragradient method. We think that the factor O(􏰖1/M + 1/β · L/μ) is unimprovable and optimal – see Section A.'", "limitations": "The authors addressed the limitations of the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper studies an interesting problem. Reducing the communication cost for distributed variational inequalities and saddle point problems is relevant in the area of machine learning. The paper provides convergence results for the proposed methods in many different regimes (strongly monotone, monotone and non-monotone operator regimes, deterministic, stochastic etc.). The theoretical results are also supported by illustrative experiments. \n\nWeaknesses: In my perspective the paper has two main weaknesses.\n1. Firstly, the writing of the paper requires a major revision. There are many typos, syntactic errors and sentences that do not make sense throughout the main body and the appendix. As a result many important points of the paper are not clearly conveyed such as the description of Algorithm 1. Further, the appendix needs also to be rewritten more carefully to make it easier to follow. Below I state a few examples that could be revised :  \n\nThe sentence in lines 39-42 needs to be rephrased so that it has a clear meaning.\nline 53 : In 'implementations it often advantageous' there is an 'is' missing.\nline 56: Remove 'the' from 'lead to the comparable test error'.\nline 60: Remove 'Since' from the beginning of the sentence.\nline 79: Replace 'due to' with 'since'.\nline 87: Remove ''provably\nlines 130-131: Rephrase 'Moreover, devices can not only have a bad connection, in which one needs to compress data heavily, they can simply disconnect from the learning process'.\nlines 140-143: Need rephrasing.\nlines 209-221: The paragraph explaining MASHA1 needs to be rewritten. There are many typos and syntactic mistakes which make it hard to decipher the description of the algorithm.\nline 228 : Replace 'listing' with 'description'.\nline 230: 'an' is missing in 'Let us find optimal way to choose it'\nline 247 : Rephrase 'Then once can note that MASHA1 O(􏰖1/M + 1/β · L/μ) better than the uncompressed extragradient method. We think that the factor O(􏰖1/M + 1/β · L/μ) is unimprovable and optimal – see Section A.'\n\n2. While the theoretical results are extensive the originality and technical contribution appears to be limited. Similar results have been obtained with the same compression operators in optimization problems and certain techniques are repetitive.", "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": "QSGYF4U2ppB", "reviewer": "Reviewer_1QcY", "summary": "In this paper, the authors consider solving distributed variational inequalities (VIs) with compressed communication. For unbiased compressors, they use the variance reduction (VR) technique to control the variance; while for contractive compressors, they further incorporate the error compensation mechanism to handle the bias. They prove convergence rates for the cases where the operator is strongly-monotone, monotone, or non-monotone with Minty's condition, and demonstrate the speedup compared with the uncompressed counterparts. They further show how to extend their methods to the stochastic setting and the federated learning setting with partial participation.", "questions": "- Could you please articulate the connections between the proposed methods and the existing ones? In particular, both MASHA1 and MASHA2 seem similar to the FBF method with variance reduction in [2]. Also, the proof starting at line 786 in the Appendix also seems to be related to Lemma 2.4 in the mentioned paper.  \n- Minor issues: \n    - The sentence from 39-42 is grammatically incorrect. \n    - Line 53: \"it often\" -> \"it is often\"\n    - Line 106: \"second norm\" -> \"Euclidean norm\"?\n    - The fourth line from last in Algorithm 1: \"$w^{k+1}=z^k$\" -> \"$w^{k+1}=z^{k+1}$\"\n    - Line 226: It should be $\\mathcal{O}(1/\\epsilon)$ instead of $\\mathcal{O}(1/\\epsilon^2)$?\n    - The reference number in the appendix seems to be off by one. ", "limitations": "Yes, the authors have mentioned the limitations in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- This is the first work to study communication compression techniques in the setting of distributed VIs. Given the increasing importance of saddle point problems and the necessity of designing communication-efficient algorithms, I think this work should be of interest to the community.\n- The presentation is mostly clear and easy to follow.\n- The results are comprehensive and seem technically sound.\n\n## Weaknesses\n\n- I don't see any serious problem, but as a mostly theoretical paper I feel its algorithmic novelty is somehow limited. For instance, the idea of combining VR techniques and gradient compression seems not new; it has appeared in [1]. Also, the algorithm MASHA1 as well as its analysis resemble those in [2], with the stochastic oracle replaced by the compressed operator.\n\n[1] Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed sgd can be accelerated. arXiv preprint arXiv:2010.00091, 2020.\n\n[2] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. arXiv preprint arXiv:2102.08352, 2021.", "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": "IIQ5LeAi990", "reviewer": "Reviewer_SxRG", "summary": "This paper designs and analyzes compression algorithms for solving three families of distributed VI/SPP problems. ", "questions": "N/A ", "limitations": "N/A ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the work include extensive theoretical and experimental results highlighting that its designed algorithms outperform existing algorithms for solving VI/SPP. In particular, the results for strongly-monotone, monotone and non-monotone problems are provided.  \n\nI don't see any major weaknesses from this paper. However, I would like to point out to typo errors in the paper: \n\n- Line 117-118: \"But often ...\" It is a run-on sentence. \n- Line 125: \"fro details\" -> \"for details\"\n- Line 241: \"in str-monotone case\" -> \"in strongly-monotone case\"", "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": "6CfERbe3clX", "reviewer": "Reviewer_CwZ6", "summary": "The paper proposes approaches to add compression to the communication steps involved in solving variational inequalities in a distributed fashion. The authors propose approaches for both unbiased and contractive compression along with theoretical analysis and two experiments to validate their approaches.", "questions": "1. Please address points 1 and 2 under Weaknesses above.\n\n2. Please include a conclusion section in the paper.\n\n3. The notation for local operators $F_m$ is used in Section 2.3 before it has been defined. Please define notation before using it.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This appears to be the first work to address the issue of compressed communication in distributed methods for solving variaitional inequalities. Moreover it proposes and analyzes separate schemes for both unbiased and contractive compressors.\n\n2. Results on the synthetic experiment of solving a bilinear saddle point problem clearly show that the proposed approaches require significantly fewer iterations than baselines for convergence.\n\nWeaknesses:\n\n1. The experiment on Adversarial Training of Transformers is not clear at all. Specifically it is unclear if any of the MASHA approaches have been implemented for this since the plots appear to contain only the baselines. Moreover  the size of the plots, and the font size of the text in them is extremely small and thus it is very hard to tell what is going on in them.\n\n2. It is not clear if MASHA1 will always reduce the communication cost. Corollary 1 appears to show that MASHA1 will have fewer iterations than the uncompressed case, but each round of iteration can involve upto 2 rounds (each way) of communication between the server and the clients. As the authors state in line 235, the average communication cost per round is ($1/\\beta + 1 - \\tau$) times the communication cost in the uncompressed case. It is not clearly stated if $1/\\beta + 1 - \\tau$ is smaller or larger than 1. If it is larger, then the communication cost would be higher than that of the uncompressed case from what I can tell.\n\n2. The paper appears to be incomplete with no conclusion sections and no discussion of limitations/future 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