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: ICLR 2022 Submitted (2022)
Keywords: convex optimization
saddle point problem
minmax problem
distributed optimization
quantization
compression

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 these and other applications, it is necessary 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 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. We empirically validate our conclusions using two experimental setups: a standard bilinear min-max problem, and large-scale distributed adversarial training of transformers.

Under review as a conference paper at ICLR 2022
DISTRIBUTED METHODS WITH COMPRESSED COMMU- NICATION FOR SOLVING VARIATIONAL INEQUALITIES, WITH THEORETICAL GUARANTEES
Anonymous authors Paper under double-blind review
ABSTRACT
Variational inequalities in general and saddle point problems in particular are in- creasingly relevant 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 parallel and distributed computing. However, in distributed training, com- munication among the compute nodes a key bottleneck during training, and this problem exacerbated for high dimensional and parameterareeedd 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 theoreti- cally 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 Randk: MASHA1) and contractive (such as Topk; MASHA2) compressors. We empirically validate our conclusions using two experimental setups: standard bilinear min-max problem, and large-scale distributed adversarial training of transformers.
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 (VI) have been an active area of research in applied mathematics for more than half century (Korpelevich) 1976 Harker & Pang 1990 Facchinei & Pang. 2003). is well known that VIs can be used to formulate and study convex optimization problems, convex-concave saddle point problems and games, for example, in an elegant
unifying mathematical framework (Korpelevich 1976 Bauschke & Combettes 2017).
Recently, Gidel al. (2019) pointed out that multi-player games can be cast as VIs, and proposed to study mini-max or non-zero-sum games formulations of GANs (Goodfellow et al., 2014) in this fashion. This allowed them successfully transfer established insights and well-known techniques from the vast literature on VIs to the study of GANs. In particular, oscillatory behavior of optimization methods (such as SGD) not originally designed solve VI problems is well understood in the VI literature, and established tools, such as averaging and extrapolation, can be successfully applied to the training of GANs. Besides their usefulness studying GANs and alternative adversarial learning models Madry al. 2018), VIs have recently attracted considerable attention of the machine learning community due to their ability to model other situations where the minimization of a single loss function does not suffice, such auction theory (Syrgkanis et al. 2015) and robust and multi-agent reinforcement learning (Pinto et all 2017).
In summary, VIs have recently become potent tool enabling new advances in practical machine learning situations reaching beyond supervised learning where optimization problems and techniques, which can be seen special instances of VIs and methods for solving them, reign supreme.

---

Under review as a conference paper at ICLR 2022
1.2 TRAINING OF SUPERVISED MODELS VIA DISTRIBUTED OPTIMIZATION
On the other hand, in the domain of classical, and hence also much better understood, supervised machine learning characterized by the fact that standard optimization techniques apply and work well, researchers and practitioners face other challenges that are currently beyond the reach of existing VI methods. 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 to rely on training datasets of ever increasing sizes and on elaborate over pere-aaamtteizee models (Arora et al. 2018). Supporting workloads of such unprecedented magnitudes would be impossible without combining the latest advances in hardware acceleration, distributed systems and distributed algorithm design (Verbraeken et al. 2019).
When training such modern supervised models in distributed fashion, communication cost is often the bottleneck of the training system, and for this reason, a lot of effort was recently targeted at the design of communication efficient distributed optimization methods (Konečný et al. 2016 Smith ett al. 2018 Ghosh et al., 2020, Gorbunov et al., 2021). A particularly successful technique for improving the communication efficiecyy of distributed first order optimization methods is commu- nication compression. The idea behind this technique is rooted in the observation that in practical implementations it often advantageous communicate messages compressed via (often randomized) lossy compression techniques instead of communicating the full messages (Seide et al. 2014) Alistarh al. 2017). If the number of parallel workers large enough, the noise introduced by compression reduced, and training with compressed communication will often lead to the comparable test error while reducing the amount of communicated bits, which results faster training, both in theory and practice (Mishchenko et al. 2019, Gorbunov et al. 202T.
1.3 Two CLASSES OF COMPRESSION OPERATORS
We say that a (possibly) stochastic mapping Q IRd + Rd is an unbiased compression operator there exists constant q 2 such that
EQ(z) = 2, [I]((=)1 - / V2 ed.
(1)
Further, we say that a stochastic mapping C Rd + Rdd is contractive compression operator if there exists constant 1 such that
E||C(=) =1|² < (1 - 1/0), Vz E R
If b is the number of bits needed to represent a single float (e.g., b = 32 or b = 64), then the number of bits needed to represent a generic vector E Rd is ||2||bis bits bd. To describe how much compression operator reduces its input vector on average, we define the notion of expected density, defined via 3 := by EE| Q(2)()) [bass where [IQ(=) |lbis denotes the number of bits needed to represent the
quantized vector ((2). ). Note that B < 1. For the Randk operator (Alistarh et al. 2018 Beznosikoy
al. 2020 we have q d/k and 3 k/d.
1.4 TOWARDS COMMUNICATION EFFICIENT DISTRIBUTED METHODS FOR VIs
While classical VI algorithms, such as the extragradient method originally proposed by Korpelevich (1976) and later studied by many authors (Nemirovski 2004 Juditsky al. 2008), were not designed to work in a distributed environment, virtually all methods that were ( (uaan et al. 2014 Hou et al. 2021 Deng & Mahdavi 2021 Beznosikov et 2021b cp do not consider the general but tackle the special case of saddle point problems only. Moreover, none of these distributed methods support communication compression, with the exception of the work of Yuan et al. (0014), which relies on rounding to the nearest integer multiple of certain quantity. This compression mechanism does not offer theoretical benefits and does not even lead to convergence to the solution due to the errors introduced through rounding persist and prevent the method from solving the problem.
problem,
2 SUMMARY OF CONTRIBUTIONS
In this paper, we investigate whether it is possible to design communication-effioe algorithms for solving distributed VI problems by borrowing generic communication compression techniques
2

---

Under review as a conference paper at ICLR 2022
Table 1: An overview of existing methods and their high-level properties. We develop the first provably communication-effcieen (via communication compression) algorithms for solving distributed VI problems.
Solves general Vis?
Supports distributed setup?
Supports Compressed Communication?
Has
Reference
strong
theory?
Korpelevich 1976
X
Nemurovski (004))
X
x
Goodfellow et al. (2014
X
x
x
Yuan ct al.
2014)
X
/
x
X
Hou et al.
(021)
x(I
x3
X(5)
Deng & Mahdavi
(2021
x(9
x(3
55
Beznosikov et al.
(021b
x(I
x(2)
Beznosikov al.
202lc
X(I
X
Beznosikov et al.
2021a
16)
X(2
This work
(1) Studies Saddle Point Probloms (SPPs) only.
(2) Achieves communication efficiency without compression but by assuming data similartyyhomnneeettyy by dramatically re-
stricting the problem class.
(3) Trics achieve communication efficiency via performing local steps as popular in Foderated Learning (Knnčnn et 2016
McMahan al. [2016] Li 2020 Employs local methods (such GD and SCAFFOLD (Karimireddy al. 2020
Does not achieve convergence to the solution; and the convergence criterion may not work for simple hilinear problems.
(5) They build method GD, which diverges simple bilinear problems.
(9) Uses dosentralized architecture.
19 Compression just by rounding nearest integer multiples some constant.
Applies to GANs only.
No theory.
and from the optimization literature (Seide al. 2014 Alistarh et al. 2017: Mishchenko
ct al. 2019: Gorbunov et al., 2021; Richtárik et al. (021)) and adapting and embedding them into
establis biseed and efficient methods for solving VIs (Korpelevich 1976: Nemirovski 2004 Juditsky
ct al. 2008 Alacaoglu & Malitsky 2021). Whether or not this is possible is an open problem.
In summary, we design the first provably communication-effiieen algorithms for solving general distributed VI problems (see Section 3 Equation B) in the deterministic (see 44) and stochastic
(see (5) regimes, supporting both unbiased (MASHA1 Algorithm I and contractive (MASHA2 Algorithm 2 compressors. Our methods are explicitly designed to be variance reduced to achieve better theoretical properties and better practical performance.
In Table | we give a high level overview of existing methods for VIs, and contrast them with our methods and results. We now elaborate bit more:
2.1 TWo DISTRIBUTED PROBLEMS: DETERMINISTIC AND STOCHASTIC
We study two distributed VI problems: i) deterministic, where the monotone operator F : Rd - Rd featured in the VI is the average of M operators {Fm m==1 vices/machines. which can be evaluated in each communication round, and ii) stochastic, where each monotone operator F.. Rd - Rdd has a finite-sum structure on its own, and only a single operator in the sum be evaluated in each iteration. In contrast previous works, we study general constrained VIs in the distributed setup (see Section 5 and not merely saddle point problems.
{ where AM is the number of de-
2.2 TWO NEW METHODS WITH COMPRESSED COMMUNICATION MASHA1 AND MASHA2
We develop two extensions of the extragradient / extrastep method of Korpelevich 1976 to distributed VIs depending on whether we use unbiased 11) or contractive compressors, since each type of compressor demands a different algorithmic design and a different analysis. In particular, contractive compressors are notoriously hard to analyze even for optimization problems (Karimireddy et al. 2019 Richtárik et al. 202T). Our method based on unbiased compressors is called MASHA1 (Algorithm
and our method based on contraction compressors is called MASHA2 (Algorithm 2 Both designed to handle the deterministic and also the stochastic setting, and both are enhanced with bespoke varioice-reduction techniques for better theoretical and practical performance. Due space
3

---

Under review as a conference paper at ICLR 2022
Table 2: Summary of our iteration complexity results for finding an s-solution for problem 3 in the deterministic (i.e., 44) and stochastic (i.e., 5 setups. In the strongly convex strongly convex case, convergence is measured by the distance to the solution. the convex-comee cenve--concave case, convergence is measured in terms of the gap function. Notation:
sum of the coefficients μr and μin of strong monotonicity of the operator F and strong convexity of h, L= maximum of local Lipschitz constants Lm R diameter (in Euclidean norm) of the optimization set, Rg initial distance to the solution, g = the variance parameter associated with an unbiased compressor (see () ô the variance parameter associated with contractive compressor (see 2); . the number of parallel clients/nodes; r = the size of the local dataset (see ) To simplify the bounds, we assume that compression occurs only the nodes, and the server transmits full information, additionally, assume that the expected density 33 of the compression operators satisfies this holds for Randk and Topk).
2
1/3 and = 1/8 (e.g..
Problem
Algorithm
Strongly convex strongly concave case
R log
MASHA1
1 1 q
+ g
1 + 8 80/21.
6 12a
Ra log
MASHA2
1
MASHA1
max (r, + 1) + 1 max (r, + 1) (1 + +
log
R
MASHA2
m V /mxx(r, y 1) 8L max(ra ( 1) 62
log
Problem
Algorithm
Convex-coneave case
+ LB
MASHA1
MASHA2
max 1111 # LR
MASHA2
restrictions, we only describe MASHA1 in the main body of the paper, and relegate MASHA2 and the associated theory to Appendix
2.3 THEORETICAL COMPLEXITY RESULTS
We establish number of theoretical complexity results for our methods, which we summarize in Table 2 We consider the strongly convex strongly concave regime well as the more general convex concave regime. In the first case we obtain lincar convergence results (O I/e)) in terms of the distance to solution, and in the latter we obtain fast sublinear convergence results (O(1/c) in terms of the gap function. To get an estimate for the number of information transmitted, one need to multiply the estimates from Table 1 by 1/4 and 1/8, respectively. Then we get that from the point of view of the transmitted information, MASHA1 better by a factor v1/g 1/M in comparison with the original extragradient.
3 PROBLEM FORMULATION AND ASSUMPTIONS
Let us first introduce basic notation. We write (x, v) = Dí 3.3h to denote the standard Euclidean inner product of vectors x; y E Rdd This induces fg-norm in Idd usual: ||æ||| == / (<r We also introduce the proximal operator, defined as pzox,(2) == arg min (gg()) + = ==| which is well defined for proper lower semicontinuous convex functions g Idd + R U {+00].
3.1 PROBLEM FORMULATION
We study distributed variational inequality (VI) problems of the form
Find Z such that (F(z"), 2-) + f==)) h(=²)*()()))))))() 0,
Vz Z,
(3)
where Z is nonempty closed convex subset of Rd F Rd - Rd is operator with certain favorable properties (e.g., Lipschitzness and monotonicity). and h bd + R U [+00] a proper lower semicontinuous convex function. We assume that the training data describing F is distributed
4

---

Under review as a conference paper at ICLR 2022
across M workers/nodes//lients
F(2) M
Σ (2)
(4)
where F' _d + Rd for all m E 21,2,.... M, and for some results we further assume that Fm is
of finite-sum structure well:
(2) == Σ (2)
(5)
3.2 ASSUMPTIONS
Next, we list two key assumptions both are standard in the literature on VIs.
Assumption (Lipschitzness in mean) For all clients
..,,...,A.................. M, the operator Fm(z):
Rd + Rd is Lipschitz in mean with constant Lm 2 0 on Z. That is,
(F,a(Zz)) - F < 11 22 22133 V21, E.
(6)
For problem Assumption is to be interpreted to hold with r is equal 1, i.c. with Fm Fm.1.
Assumption (Monotonicity and convexity) (SM) Strong monotonicity/strong convexity. There exist non-negative constants μr, . Hb, such that Ph + MF > O, and the following statements hold:
(F(2)) F (22). 22)
pr pFl|z1 21 2211
12 22 E Z,
(7)
h(2)) h(22) (Vh(2))
-22)
2 || - 2211
422, 22 E Z.
(8)
(M) Monotonicity/comveritt.
(F(z)) - F(z2), =1 =2) 2 0,
M2)) - 1(22) - (1 20,
V2i, 22 E E.
(9)
4 MASHA1: HANDLING UNBIASED COMPRESSORS
In this section we present only one of our two new algorithms: MASHA1 (Algorithm 1) the method that relies unbiased compressors. Due to lack of space, we include MASHA2 (Algorithm 2) the method that relies on contractive compressors in the appendix. Both algorithms are presented for two modes: deterministic 4 and stochastic [ 5 We denote the lines related to the deterministic regime in blue, and in red to the stochastic one. Black lines are common to both modes.
4.1 THE ALGORITHM
MASHA1 is modification of the extrastep method. At the beginning of each iteration of Algorithm
each device knows the value of F(w*), hence it can be calculated z locally. z is a convex combination of x and w with momentum parameter 7 (typically, 7 is close 1). Also Algorithm compute =41//2 locally. Then it sends the compressed version of the difference (=*+11122)) (m to the server, and the server does a reverse compressed broadcast. As a result, an unbiased estimate of F(2++1/2) F (ww*) appears on each node. Also, the nodes receive a bit of information by. This bit is generated randomly
the server and is equal to O with probability т. Then, all devices make final update on 2+1 and also update the #+1 = x+1 point if the by or save from the previous iteration w++ =² In the case when the point w++ exchange the full values of F., (w)+1) ) in order that at the beginning of the next iteration the value of -1) is known to nodes. In the stochastic case, Algorithm has the same form, the only thing that changes is that one need to generate function number (batch number) from use a possibly difference compressor on each device and also on the server. To distinguish between them, will use the following notation: Qelev gdee ggle and Qvery ghe gdt Note that, if Q is the identity quantization, i.e., ((z) = x, then MASHA1 is distributed analogue of the method from Alacaoglu & Malitsky 2021
*++ we need to
We
is important to note main differences from minimization problems. For minimization problems, compressed gradient methods constructed the gradient descent the accelerated gradient
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1 MASHA1 (handling unbiased compressors)
Parameters:
Stepsize y > 0, number of iterations K.
Initialization: Choose =0 = w E Z.
Server sends to devices 20 w and devices compute Fm (w") and send to server and get F(w") for = 0, 0,1,2..... K do for each device in parallel do z T2 R + (1 T)w*
1/2 prox (2x - ))(w))),
Generate TM from (1..... independently
Compute F' (=( & send Qm (Fm( (2/2) - Fm (w to server
Compute mm (=/+1/2) & send Qaay (Fm, (zh+1/2)- - Fm (w* to server
end for for server do
Compute Query
Σ
Qth (Fo (zt+1/2) (1o9)-Pmmm. P'm ((att)))) & send to devices
Compute Q
Σ Qday (Fi (2/+1/2) F Fort (w)*)) & send to devices
M
Sends to devices one bit by: with probability T, with with probability r end for for all devices in parallel do
2+1
prox hh
2k Q
Σ
Qday (Fi (2 Fm Fm((w(i)) -2 =F(w)))
3+1 pr
mk 7 Q
M
Qdey (Fmot (2h+1/2) - I'm ((t))) - (ZD(w()
M
m==1
then by w++11 = ==++1
Compute Fm ( & send server; and get F(wk+1) as a response from server
else
w+1 w
end if
end for end for
descent methods. Here, the extragradient method is taken as a basis. In the experiments, we will see the importance of this fact, i.e., gradient descent type methods will diverge even simple problems. The second key difference is that we need not compress Fn (2*+1/2) itself, but the difference (2 F(w*). We will also see the importance of this approach in the experiments. The later idea similar to the approach used in the DIANA, VR-DIANA (Mishchenko al. 2019) Horváth et al.) 2019) MARINA (Gorbunov et al. 202T) and EF21 (Richtárik et al. 2021) methods in optimization.
4.2
THEORY
We now establish convergence of MASHA1 in both regimes: deterministic and stochastic (finite-sum). Our analysis relies on the following Lyupunov function:
V == =|12* 2" 112 I|w 11
(10)
This criterion is used in the strongly monotone case. For the general monotone case, another convergence criterion is used the gap function:
Gap(z) sup [(F(u), u) h(2) h(u)]-
(11)
wEC
Here we do not take the maximum over the entire set Z (as in the classical version), but over C C
compact subset of Z. Thus, we can also consider unbounded sets Z. This is permissible, since such a version of the criterion is valid if the solution 2* lies in C; for details the work of Nesterov (2007).
Theorem (Convergence of MASHA1) Let Assumption bb satisfied. Then, if one of cases from Assumption 2 is additionally fulfilled, the following estimates hold for the iterates of MASHA1:

---

Under review as a conference paper at ICLR 2022
for stronnyy-oonooone/covwe case with stepsize 0 < y x min VI- 1-t
- and C.
30 [(pptta)]
gre M
Σ M
m== (1th"
M 1)
E [R S (1 -y.
M5+ K-1 Voo
for monotone/convex case with s
-I-I.
4C,
E [Gap(=*)]
8 smaxwed -=l= where
gK
R-1 1 K k=U
Σ 2k11/2
For proof, see Appendix
An important issue of convergence is the choice of If we have the fastest convergence rate, on the other hand, this means that we must send full Fm. in each iteration (because we update w*). This is disadvantageous from communication point of view. The next corollaries give the rules for the right choice of T, as well the iterative (in deterministic case), oracle (in stochastic) and communication complexities of Algorithm in both cases. The method without quantization (for example, the ordinary distributed extragradient method) in one iteration transmits the number of information proportional to (2ddM bits, then here we measure the communication complexity in terms of (bdd). In literature about method with compression, it is typical to consider only devices compression Alistarh et al. 2017 Mishchenko al 2019 Horváth et all 2019 Gorbunov et al. 2021 Beznosikov et al. (2200), because it is easier for server to broadcast information. In the next corollary we consider the transfer of information in one direction only (from devices to the server).
means choose geerv =1 and grerv
Corollary (Convergence of MASHA1 in the deterministic case) Let the deterministic problem
be solved by MASHA1 with precision e. Lel Assumption 7 and one of the two cases from Assumption 2 be satisfied. If we choose
3
Σ
gdev
(12)
M
then have the following estimates for the total # of iterations and the total # of transferred bits from devices to the server:
in the strongly-monntone/cooves case:
o (1
(B(urttm)) log 211=-==*12 iters,
([1I
VBC,
log 211 211=-~=-11"
bits.
Mptra
in the monotone/comve case
Co maxned || = VB
VBC, maxned |1 [1="==[[]] bits.
iters,
O
One can see that our Algorithm 1 can outperform the uncompressed extragradient method. Let us compare them in the monotone case. The communication complexity of the extragradi- ent method is O (I. (mmaxe [||=0 ull2] e-)). Let us consider the case when I.m L. for all m E {1,2,... M) and gdh deey Then MASHA1 has communication complexity
O maxaee |||=0 w e- VB(L gdev /M) If B(1 + /M) 1, we outperform the standard uncompressed extragradient method. For example, for if we consider RandK operator = 1/dder This means that we have (L.mxxeec [[|=0 u/ _ /1/pdor + +1/M)
g-
Corollary 2 (Convergence of MASHA1 in the stochastic case) Let the stochastic problem be solved by MASHA1 with precision Let Assumption 7 and one of the two cases from Assumption be satisfied. If we choose
r= min (+:
then have the following estimates for the total # of oracle calls and the total # of transferred bits:
7

---

Under review as a conference paper at ICLR 2022
in the strongly-monotoneecoowee case:
0
( max (r: + max (Vr: /3)
C₁
log ===1"- calls,
(pttun]]
o ((
Cg ([max max (1;r,)) + max (VrB2:
log 211= ----="" 11² bits,
in the monotone/convex case
o max (r
Co max. -1=0
calls,
o max (VrBR; v3)
Cg maxued [1 -ull)] bits.
In the case of finite sum, in addition to the number of transmitted information, it is not iterations important to us, but the number of calls to the oracle for Fm.r. This is due to the fact that it is r times more expensive calculate full Fo. and the calculation of Fn should be avoided. For deterministic case (when r = 1) estimates from Corollary 2 is the same as in Corollary 1.
5
EXPERIMENTS
5.1
BILINEAR SADDLE POINT PROBLEM
We start our experiments with distributed bilinear problem:
M min max f(x, y) 1 Σ fm((,y); wERd yERd
(m TT Any + a b + 2|1=| Ilvll?,
m=1
(13)
where Am E Raxd am, bm E Rd. This is a saddle point problem, and is written as follows: F(I, == (Vaf(I,)): y): - -V vyf(z, This operator is À strongly monotone and, moreover, all functions Fm are (l l2 + A)-Lisschit. Therefore, such distributed problem is well suited for the primary comparison of methods. We take d = 100 and generate positive definite matrices Am and vectors Om, bm randomly.
The purpose of the experiment is understand whether the MASHA1 and MASHA2 methods superior to those in the literature. As a comparison, we take QGD with natural dithering Horvath et al. 2019), classical error feedback with Top 30% compression, well an extra step method, each step of which is used with natural rounding. In MASHA1 (Algorithm 1) we also used natural dithering, in MASHA2 (Algorithm 2) Top30%. See results Figure
Figure I: Comparison MASHA1 (Algorithm and MASHA2 (Algorithm 2) with existing methods in iterations and in Mbytes.
Aggrtter
0GD
Emor footbace
tor
ton
38
Ttaratoo
Tranem22ea (OCA Mlstee
We see that methods based on gradient descent (QSG and EF) diverge. This confirms that one needs to use method specifically designed for saddle point problems (for example, the extragradient method), and not classical optimization methods. The much slower convergence the quantized extragradient method shows the efficiency of our approach in which we compress the differences F2 (2+++1 1/2) F.
5.2 ADVERSARIAL TRAINING OF TRANSFORMERS
We now evaluate how compression performs for variational inequalities (and for saddle point problems, special case) in more practically motivated scenario. Indeed, saddle point problems (special case variational inequalities) have sample applications in machine learning (see Appendix D) including adversarial training. We consider of these tasks and train transformer-based masked
8

---

Under review as a conference paper at ICLR 2022
language model (Vaswani al.) 2017: Devlin al. 2019: Liu al. 2019) using fleet of 16 low-cost preemptible workers with T4 GPU and low- bandwidth interconnect. For this task, we use the compute-efficient adversarial training regimen proposed for transformers by Zhu et al. (2019); Liu et al. (2020.. Formally, the adversarial formulation of the problem is the min-max problem
min Il IAellSe...-llev Se
max
1 N
Σ ((s(w, In + Pn, Un)? + 2 [|wl|/ 2 Ilel? n=1
)=)) where w are the weights of the model, {(rn; Yo)) i=1 are pairs of the training data, p the so-called adversarial noise which introduces a perturbation in the data, and À and / are the regularization parameters. To make our setup more realistic, we train ALBERT-large with layer sharing (Lan et al. 2020), which was recently shown to be much more communication et al. 2021 Diskin et al. 2021). We train our model on a combination of Bookcorpus and Wikipedia datasets with the same optimizer (LAMB) and parameters as in the original paper (Lan et al. 2020). +
during training (Ryabinin
use the adversarial training configuration of Zhu et al. (2019), and follow system design considerations for preemptible instances (Ryabinin al. 2021
In terms of communication, we consider 4 different setups for gradient compression: the "baseline" strategy with uncompressed gradients, full 8-bit quantization (Dettmers) 2015 Lin at. 2018), mixed 8-bit quantization, and Power compression (Vogels et al. 2019) 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 (Ba et al. 2016) that collectively amount 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 (Karimireddy et al., 2019 [Richtárik et al., 202T) with a modified formulation proposed by Vogels et al. (2019). For all experimental setups, we report learning curves in terms of the model training objective, similarly to (Fedus et al. 2021 Ryabinin et al. 202T). To better quantify the differences in training loss, we also evaluate the downstream performance for each model on several popular tasks from (Wang et al., 2018) 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.
Figure 2: (upper left) ALBERT training objective convergence rate with different compression algorithms; (upper right) ALBERT training objective convergence rate with different compression algorithms (zoomed); (lower) Average wall time per communication round with standard deviation over 5 repetitions and downstream evaluation scores on GLUE benchmark tasks after at 80 billion training tokens 10 optimizer steps).
10
2.4
6-21
riieed Sal
Oblettue
Billoms tokens
ons of bocems
Setup
Avg time
Avg score
CoLA
MNLI
MRPC|
QNLI
QQP
RTE
SST2
STS B WNLI
Baseline
8.79 + 0.03
71.96
45.2
81.1
83.0
88.3
89.0
67.8
85.5
89.4
18.3
Full 8-bit
4.42 + 0.07
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
Mixed 8-bit
4.61 + 0.08
72.12
48.8
81.3
88.7
88.1
85.2
64.3
88.3
87.5
16.9
Power
1.57 + 0.05
69.52
43.9
80.5
85.6
88.6
86.0
47.2
88.5
88.5
16.9
The learning curves Figure (upper) follow a predictable pattern, with more extreme compression techniques demonstrating slower per-iteration convergence. One curious exception to that is full 8-bit quantization, which was unable to achieve competitive training loss. The remaining three setups converge to 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.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. arXiv preprint arXiv:2102.08352 2021.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-cficcee SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikacl Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, 2018.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterivatton. Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton, Layer normalization, 2016.
Heinz H. Bauschke and Patrick L. Combettes. Conver Analysis and Monotone Openator Theory in Hilbert Spaces. Springer, second edition edition, 2017.
Aleksandr Beznosikov. Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint ar 2002 2020.
Aleksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova, Valentin Samokhin, Sebastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradee grrri-gradientt for variational inequalities. arXiv preprint arXiv:2 106.035,6 2021a.
Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle-point problems: Lower bounds, optimal algorithms and federated GANs. arXiv preprint arXiv:2010. 13/ 2021b.
Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Distributed saddle-point problems under similarity. arXiv preprint arXiv:2107.10771 2021c.
Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference Artificial Intelligence and Statistics (AISTATS), pp. 1387-1395, PMLR, 2021.
Tim Dettmers. 8-bit approximations for parallelism in deep learning. ICLR, 2015.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training deep bidirectional transformers for language understanding. In NAACL-HLT, 2019.
Michael Diskin, Alexey Bukhtiyarov, Max Ryabinin, Lucile Saulnier, Quentin Lhoest, Anton Sinitsin, Dmitriy Popoy, Dmitry Pyrkin. Maxim Kashirin, Alexander Borzunov, Albert Villanova del Moral, Denis Mazur, Ilia Kobelev, Yacine Jemnite, Thomas Wolf, and Gennady Pekhimenko. Distributed deep learning in open collahorations. CoRR, abs/2106. 10207, 2021.
hhtttss:/aaxxv..rreee http://///a////ee//// 10207
Darina Dvinskikh and Daniil Tiapkin. Improved complexity bounds in wasserstein barycenter problem. In International Conference on Artificial Intelligence and Statistics, pp. 1738-1746. PMLR, 2021.
Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research, Springer, 2003.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint urXiv:2101.0396 2021.
Avishek Ghosh, Raj Kumar Maity, Arya Mazumdar, and Kannan Ramchandran. Communication efficient distributed approximate Newton method. In IEEE International Symposium Information Theory (ISIT), 2020. doi: 1LL11///STT444822220000000
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequal- ity perspective on generative adversarial networks. International Conference on Learning Representations, 2019. URL TRLLstttss///oennoeee
Ian J. Goodfellow, Jean Poudet-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farles Sherjil Ozair. Aaron Courville, and Yoshua Bengio. Generative adversarial networks. In Neural Information Processing Systems, 2014.
10

---

Under review as a conference paper at ICLR 2022
Eduard Gorbunov, Konstantin Burlachenko. Zhize Li, and Peter Richtárik. MARINA: Faster non-convex distributed learning with compression. 38th International Conference on Machine Learning, 2021.
T. Harker and J.-S. Pang. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Mathematical programming. 1990.
Samuel Horvath, Chen- Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning, arXiv preprint arXiv: 1eXi::9055.1088,, 2019.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv: 1xXvv//00.05//5 15, 2019.
Charlie Hou, Kiran K Thekumparampil, Giulia Fanti, and Sewoong Oh. Efficient algorithms for federated saddle point optimization. arXiv preprint arXiv:2 06333000.33.. 2021.
Anatoli Juditsky, Arkadii S. Nemirovskii, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm, 2008
Sai Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Suresh. SCAF- FOLD: Stochastic controlled averaging for on-device federated learning. International Conference on Machine Learning (ICML), 2020.
Sai Praneeth Karimireddy, Quentin Rebjock. Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pp. 3252-3266 PMLR, 2019.
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-Party Machine Learning Workshop, 2016.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12: 747-756, 1976.
Zhen -honn Lan, Mingda Chen, Sehastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Alhert: A lite bert for self-supervised learning of language representations. In International Conference on Learning Representations, 2020.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50- 60, 2020. doi: 10. 10.11///S..222.297555444
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference Learning Representations, 2018. URL https: //opens ew net/ romm? SKShQQHHOW
Xiaodong Liu, Hao Cheng, Pengcheng He, Weizhu Chen, Yu Wang. Hoifung Poon, and Jianfeng Gao, Adversarial training for large neural language models. arXiv preprint (2ti::2004009994 2020.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Dangi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. ArXiv, abs/1907.1 1699,, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. arXiv preprint arXiv: 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018. URL htttttts///peeevv/// www.:ee..eeeeteeeeeeeeeeeeee www.:nne//oommmmmmmmmm wa
Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agūera y Arcas. Federated learning of deep networks using model averaging. arXiv preprint arXiv: 1602.05629, 2016.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.099 2019.
Arkadi Nemirovski. Prox-method with rate of convergence ((//t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15:229-251, 01 2004. doi: 10.1137/S 11211777/110222222444366622,,

---

Under review as a conference paper at ICLR 2022
Yurii Nesterov. Dual extrapolation and its applications solving variational inequalities and related problems. Mathematical Programming, 109(2):319 19-344,44444 2007.
Maher Nouiched, Maziar Sanjabi. Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. arXiv preprint 1rXiv:100..06297, 2019.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In International Conference on Machine Learning, 2017.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin, EF21: A new, simpler, theoretically better, and practically faster error feedback. arXiv preprint wrXiv22006.5203, 2021.
Max Ryabinin, Eduard Gorbunov, Vsevolod Plokhotnyuk, and Gennady Pekhimenko. Moshpit sgd: Communication-effiee effficeent decentralized training on heterogeneous unreliable devices, 2021.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training speech dnns. Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Smith, Forte, C. Ma, M. Takáč, M. Jordan, and M. Jaggi. CoCoA: general framework for
communication-efficee distributed optimization. Journal of Machine Learning Research, 18:1-49, 2018.
Vasilis Syrgkanis. Alekh Agarwal. Haipeng Luo, and Robert Schapire. Fast convergence of regularized learning in games. In Nearal Information Processing Syxtems, 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakoh Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.). Advances in Neural Information Processing Sys- tems 30. pp. 5998 6008. Curran Associates, Inc., 2017. URL http::/papers www.nnn..cc...c.... cct.pppcccppppe//// 713l-attent on- -ou--ol------aa-oa need. pdf
Joost Verbracken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer. survey on distributed machine learning. ACM Computing Surveys, 2019.
Thijs Vogels, Sai Praneeth Karinireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. Advances Neural Information Processing Systems 32 (Nips 2019), 32(CONF), 2019.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, Samuel R Bowman. Glue: A multi- task benchmark and analysis platform for natural language understanding. arXiv preprint 2018.
Deming Yuan, Qian Ma, and Zhen Wang. Dual averaging method for solving multi-agent saddle saddle-point problems with quantized information. Transactions the the Institute of Measurement and Control, 36(1):38 46, 2014.
doi: 12.1177714233111144447
URL htRpstsss:: /doi wwg./0....o............. 1ttp//111111771111111111111
Chen Zhu, Yu Cheng, Zhe Gan, Siqi Sun, Tom Goldstein, and Jingjing Liu. Freelb: Enhanced adversarial training for natural language understanding, arXiv preprint arXiv: 1909/990...0 1909.19764, 2019.
12


Reviews:
[{"review_id": "pjcKPdGiw1D", "reviewer": "Reviewer_RfLr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors study a well motivated problem. The algorithm developed has a solid theoretical framework from an optimization theory viewpoint. The convergence results seem non-trivial and thorough. However, some concerns exist.\n\n- A critical question that remains unanswered - from the viewpoint of theory - is whether there exist compressors that indeed lead to improved communication complexity over the uncompressed methods. In particular, the authors report that it is needed that $\\beta q^{(1+q/M)} < 1$ is required. However, for the randK compressor where $\\beta = (M+1)/Mq$ - assuming that the same compressor everywhere -  this relation is not satisfied. To complete the arguments purported in the paper, it seems necessary to provide this analysis for the randK compressor, or some other compressor that performs well. \n\n- The experimental section appears somewhat weak, I would have liked to see more.. Although the paper is motivated via GANs and adversarial training, results are only provided for the latter. Perhaps more importantly, the influence of various parameters (compressors, compression ratio, tau) on the performance is not studied. In effect, the experiments do not appear to be a sufficiently thorough validation of the theory. \n\n- The presentation can be improved by presenting and explaining the idea behind the basic centralized solution in the appendix, or before presenting the solution with the decentralized, compressed version.\n\n- From the communication complextity reported below Corollary 1, it is surprising that the compression-factor of the devices influences the total number of bits much more than the compression factor at the  server, essentially the communication complexity appears to be 2^{(1+q1)*log(q2)} bits, where q1,q2 respectively represent the variances of the quantizers of the devices and the servers respectively. It is also not transparent that this disparity in behaviour exists looking at Theorem 1, where the dependence on q1,q2 appears more symmetric (at least in an order sense). Please explain.\n \n", "summary_of_the_paper": "The paper develops a decentralized algorithm for solving variational inequalities with a certain structure motivated by machine learning applications. The key innovation is the utilization of compression (i.e., quantization) for communicating loss functions and their aggregates between a set of devices and a centralized server node, towards solving the inequalities using extragradient methods. The paper provides theoretical convergence guarantees that account for the quantization errors, and report the trade-off between the communication complexity    and the convergence.  ", "summary_of_the_review": "Overall, non-trivial theoretical analysis has been conducted to study the effect of compression on convergence. However, some concerns exist in terms of both theoretical justification need to be addressed. The experimental analysis could have been more thorough, though I consider this a relatively minor weakness given the extent of theoretical contribution in terms of convergence analyses. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nUIiLxOIEGq", "reviewer": "Reviewer_V1y7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Main techniques used and the good points about the paper \nBoth the algorithms basically extend the extragradient/extrastep method of solving variational inequalities to the distributed setting. So in particular they specify how this method can be modified to fit in a distributed regime and prove the convergence and give upper bounds on the total communication. \n\nMain drawbacks and technical issues with the paper \nI think this is an interesting modification of the prior known work but I do not believe that this is a significant research contribution and is an incremental adaptation of the extragradient/extrastep method. Also the convergence or upper bounds on communication while cumbersome are not non trivial and straightforward adaptations of the classical centralized setting proofs. I think a worthwhile theoretical contribution would be to prove lower bounds on how much communication overhead would be needed to solve variational inequalities in the distributed setting.  Or at the bare minimum have some kind of restriction assumptions on the algorithm and then prove lower bounds that could explain why this adaptation of the extragradient method is near optimal or non trivial.   \n\nPresentation of the paper. \nI think it would help the reader to first understand the classical solution to the variational inequality problem before jumping into the distributed solution. Section 4 is really abrupt and it would help to ease the reader into the distributed solution. Otherwise the paper looks okay.", "summary_of_the_paper": "The paper studies the communication needed in order for a group of distributed players to collectively solve a variational inequality problem. The paper provides two algorithms MASHA1, MASHA2 to do this that solve both the deterministic and stochastic cases.  They also provide experimental results on applying their techniques to Bilinear saddle point problem and adversarial training of transformers. \n\n", "summary_of_the_review": "The paper studies the communication needed in order for a group of distributed players to collectively solve a variational inequality problem. In particular they provide two algorithms MASHA1, MASHA2 to do this that solve both the deterministic and stochastic cases. \nThey also provide experimental results on applying their techniques to Bilinear saddle point problem and adversarial training of transformers. \nBoth the algorithms basically extend the extragradient/extrastep method of solving variational inequalities to the distributed setting. I think this is an interesting modification of the prior known work but I do not believe that this is a significant research contribution and is an incremental adaptation of the extragradient/extrastep method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YeLgdYTLL0n", "reviewer": "Reviewer_n8kw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes compression methods for solving variational inequalities. It is good to cover various settings such as unbiased vs. contractive, deterministic vs. stochastic. Detailed convergence analysis is also provided. However, I also have the following concerns. \n\n1. For practical problems such as GAN or adversarial training, the objective of min-max optimization is nonconvex-nonconcave, which results in a non-monotonic operator in variational inequalities. This more practical assumption has been considered in existing work with sound theoretical analysis (see reference [1] as below). The authors are encouraged to extend the analysis to the more practical nonconvex-nonconcave regime. \n\n2. In the paragraph right above Figure 2, the authors mentioned that “the learning curves on Figure 1(upper) follow a predictable pattern, with more extreme compression techniques demonstrating slower per-iteration convergence”. First, is Figure 1(upper) a typo? Should it be Figure 2(upper). Second, the learning curves in Figure 2(upper) are overlapping with each other (except for pure 8-bit in the upper-left figure). I am not sure how the authors get the observation that  “more extreme compression techniques demonstrating slower per-iteration convergence”. Besides, some discussion is needed to compare the compression ratio between 8-bit quantization and power compression with rank r=8. This is because power compression with rank r would decompose the dense matrix of size m\\*n into two matrices of size \nm\\*r and n\\*r. The exact compression ratio would depend on the values of m and n. \n\n3. In Figure 2(lower), it’s customary to also list average scores across different tasks in GLUE benchmark. It’s easier to compare different methods by checking their corresponding average scores. \n\n4. In Figure 1, it looks like that extra-step method also diverges (i.e., accuracy decreases as training goes). Since the extra-step method is specific for solving saddle point problems, it’s counter-intuitive when it diverges. \n\n5. It looks like there is no conclusion section at the end of this paper.\n\nReference:   \n[1] Diakonikolas, Jelena, Constantinos Daskalakis, and Michael Jordan. \"Efficient methods for structured nonconvex-nonconcave min-max optimization.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n", "summary_of_the_paper": "This paper considers the compression methods for solving variational inequalities (or saddle point problems in particular) in the distributed setting. Both unbiased (i.e., MASHA1) and contractive (i.e., MASHA2) compression methods have been proposed. Theoretical analysis is provided to show that the proposed method can converge. \n", "summary_of_the_review": "I have been working on related areas and have read this paper carefully.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WCg4r3AADM", "reviewer": "Reviewer_oTML", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The main weakness of this paper is regarding the theoretical results. \n\n- The authors consider a general notion of unbiased compression schemes in (1). Parameter $q$ is in general dimension-dependent (Alistarh 2017). The authors establish the bounds by treating $q$ as a constant term. However, this parameter can be very large in overparameterized settings, which motivate this paper as stated in the abstract. When $q$ is large, $C_q$ in Theorem 1 will be large too, which leads to very small learning rate. Similar issue happens when $\\tau$ is close to one. As authors mentioned $\\tau$ should be close to one to control communication costs. When $\\tau$ is close to one, the learning rate becomes very small, which does not lead to interesting results in terms of convergence. A similar issue happens in Corollaries 1 and 2.\n\n- I think the discussion after Corollary 1 is not accurate. In particular, the condition under which Algorithm 1 outperforms the standard uncompressed extragradient method is restrictive. It is more likely that the standard uncompressed extragradient method outperforms Algorithm 1 in terms of communication complexity. \n\n-  It will be nice if the authors provide concrete examples of interesting VI problems beyond saddle point problems in machine learning. It is also important to show that Assumptions 1 and 2 hold for such problems. Indeed, the experiments are also based on saddle point problems. \n\n- It is unclear how all nodes have access to $F(w^{k+1})$ at the beginning of the iteration $k+1$ while only some nodes with $b_k=1$ compute $F_m(w^{k+1})$?\n\n- In Table 1, the authors mentioned that ``(Deng & Mahdavi 2021) does not have strong theory since it cannot improve on non-compressed methods without assuming data homogeneity.'' I my view, a similar criticism applies to this work too. \n\n- \"we introduce the notion of expected density, defined ...\" This is not new. A similar notion based on the expected number of required bits has been proposed in the literature e.g., QSGD, NUQSGD, signSGD ...\n\n- The paper is not well-written. There are many typos that require a substantial revision. Some examples include: abstract, Section 1.4, footnotes in Table 1, first paragraph of Section 4.1, first paragraph of Section 5.2, ...\n\nMinor comment: \n- Section 4.2: \"We now establish convergence of MASHA1 in both regimes\": please specify \"both regimes\". \n\n- Some terms such as $\\tau$ and $b_k$ are defined only in Algorithm 1. It will be easier for readers if those terms are defined in the main text too.  ", "summary_of_the_paper": "The authors have considered general distributed variational inequalities problems and proposed two methods using unbiased and contractive compressors.They have evaluated their methods on saddle point problems including large-scale adversarial training of transformers. \n\n", "summary_of_the_review": "The paper has some interesting aspects for example large-scale adversarial training of transformers. However, given the issues regarding theoretical results, connection with related work, and clarify and presentation of the paper, I recommend rejection. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors consider two algorithms for solving (strongly) monotone variational inequalities with compressed communication guarantees, MASHA1 and MASHA2. MASHA1 is a variant of a recent algorithm proposed by Alacaoglu and Malitsky, while MASHA2 is a variant of MASHA1 that relies on contractive compressors (by contrast, MASHA1 only involves unbiased compressors). The authors then show that
- MASHA1 converges at a linear rate (in terms of distance to a solution squared), and at a $1/k$ rate when taking its ergodic averge (in terms of the standard VI gap function).
- MASHA2 converges at a linear rate (in terms of distance to a solution squared).

Even though the paper's premise is interesting, the reviewers raised several concerns which were only partially addressed by the authors' rebuttal. One such concern is that the improvement over existing methods is a multiplicative factor of the order of $\mathcal{O}(\sqrt{1/q + 1/M})$ in terms of communication complexity (number of transmitted bits) for the RandK compressor, which was not deemed sufficiently substantive in a VI setting (relative to e.g., wall-clock time, which is not discussed).

After the discussion with the reviewers during the rebuttal phase, the paper was not championed and it was decided to make a borderline "reject" recommendation. At the same time, I would strongly urge the authors to resubmit a properly revised version of their paper at the next opportunity (describing in more detail the innovations from the template method of Alacaoglu and Malitsky, as well as including a more comprehensive cost-benefit discussion of the stated improvements for the RandK/TopK compressors).
Decision: Reject