Year: 2021

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 Randk; MASHA1) and contractive (such as Topk; 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.

text: 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 Randk; MASHA1) and contractive (such as Topk; 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.

heading: 1 INTRODUCTION

heading: 1.1 THE EXPRESSIVE POWER OF VARIATIONAL INEQUALITIES
text: 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 a century (Korpelevich, 1976; Harker & Pang., 1990; Facchinei & Pang, 2003). It 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 et 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 to 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 to 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 in studying GANs and alternative adversarial learning models (Madry et 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 as auction theory (Syrgkanis et al., 2015) and robust and multi-agent reinforcement learning (Pinto et al., 2017).
In summary, VIs have recently become a potent tool enabling new advances in practical machine learning situations reaching beyond supervised learning where optimization problems and techniques, which can be seen as special instances of VIs and methods for solving them, reign supreme.

heading: 1.2 TRAINING OF SUPERVISED MODELS VIA DISTRIBUTED OPTIMIZATION
text: 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-parametrized 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 a 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 (Konečný et al., 2016; Smith et al., 2018; Ghosh et al., 2020; Gorbunov et al., 2021). A particularly 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 (Seide et al., 2014; Alistarh et al., 2017). If the number of parallel workers is large enough, the noise introduced by compression is reduced, and training with compressed communication will often lead to the comparable test error while reducing the amount of communicated bits, which results in faster training, both in theory and practice (Mishchenko et al., 2019; Gorbunov et al., 2021).

heading: 1.3 TWO CLASSES OF COMPRESSION OPERATORS
text: We say that a (possibly) stochastic mapping Q : Rd ! Rd is an unbiased compression operator if there exists a constant q 1 such that
EQ(z) = z, EkQ(z)k2  qkzk2, 8z 2 Rd. (1) Further, we say that a stochastic mapping C : Rd ! Rd is a contractive compression operator if there exists a constant 1 such that
EkC(z) zk2  (1 1/ )kzk2, 8z 2 Rd. (2)
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 z 2 Rd is kzkbits := bd. To describe how much a compression operator reduces its input vector on average, we define the notion of expected density, defined via := 1bdEkQ(z)kbits, where kQ(z)kbits denotes the number of bits needed to represent the quantized vector Q(z). Note that  1. For the Randk operator (Alistarh et al., 2018; Beznosikov et al., 2020) we have q = d/k and = k/d.

heading: 1.4 TOWARDS COMMUNICATION-EFFICIENT DISTRIBUTED METHODS FOR VIS
text: While classical VI algorithms, such as the extragradient method originally proposed by Korpelevich (1976) and later studied by many authors (Nemirovski, 2004; Juditsky et al., 2008), were not designed to work in a distributed environment, virtually all methods that were (Yuan et al., 2014; Hou et al., 2021; Deng & Mahdavi, 2021; Beznosikov et al., 2021b;c) do not consider the general VI problem, 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. (2014), which relies on rounding to the nearest integer multiple of a 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.

heading: 2 SUMMARY OF CONTRIBUTIONS
text: In this paper, we investigate whether it is possible to design communication-efficient algorithms for solving distributed VI problems by borrowing generic communication compression techniques
(1) and (2) from the optimization literature (Seide et al., 2014; Alistarh et al., 2017; Mishchenko et al., 2019; Gorbunov et al., 2021; Richtárik et al., 2021) and adapting and embedding them into established and efficient methods for solving VIs (Korpelevich, 1976; Nemirovski, 2004; Juditsky et al., 2008; Alacaoglu & Malitsky, 2021). Whether or not this is possible is an open problem.
In summary, we design the first provably communication-efficient algorithms for solving general distributed VI problems (see Section 3, Equation 3) in the deterministic (see (4)) and stochastic (see (5)) regimes, supporting both unbiased (MASHA1 = Algorithm 1) 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 1 we give a high level overview of existing methods for VIs, and contrast them with our methods and results. We now elaborate a bit more:

heading: 2.1 TWO DISTRIBUTED PROBLEMS: DETERMINISTIC AND STOCHASTIC
text: 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}Mm=1, where M is the number of devices/machines, which can be evaluated in each communication round, and ii) stochastic, where each monotone operator Fm : Rd ! Rd has a finite-sum structure on its own, and only a single operator in the sum can be evaluated in each iteration. In contrast to previous works, we study general constrained VIs in the distributed setup (see Section 3), and not merely saddle point problems.
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 (1) or contractive (2) 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., 2021). Our method based on unbiased compressors is called MASHA1 (Algorithm 1), and our method based on contraction compressors is called MASHA2 (Algorithm 2). Both are designed to handle the deterministic and also the stochastic setting, and both are enhanced with bespoke variance-reduction techniques for better theoretical and practical performance. Due to space
restrictions, we only describe MASHA1 in the main body of the paper, and relegate MASHA2 and the associated theory to Appendix B.

heading: 2.3 THEORETICAL COMPLEXITY RESULTS
text: We establish a number of theoretical complexity results for our methods, which we summarize in Table 2. We consider the strongly convex - strongly concave regime as well as the more general convex - concave regime. In the first case we obtain linear convergence results (O(log 1/✏)) in terms of the distance to solution, and in the latter we obtain fast sublinear convergence results (O(1/✏)) 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/q and 1/ , respectively. Then we get that from the point of view of the transmitted information, MASHA1 is better by a factor p 1/q + 1/M in comparison with the original extragradient.

heading: 3 PROBLEM FORMULATION AND ASSUMPTIONS
text: Let us first introduce basic notation. We write hx, yi := Pd
i=1 xiyi to denote the standard Euclidean inner product of vectors x, y 2 Rd. This induces `2-norm in Rd as usual: kxk := p hx, xi. We also introduce the proximal operator, defined as proxg(z) := argminu2Z{g(u) + 1 2ku zk 2 }, which is well defined for proper lower semicontinuous convex functions g : Rd ! R [ {+1}.

heading: 3.1 PROBLEM FORMULATION
text: We study distributed variational inequality (VI) problems of the form
Find z⇤ 2 Z such that hF (z⇤), z z⇤i+ h(z) h(z⇤) 0, 8z 2 Z, (3)
where Z is a nonempty closed convex subset of Rd, F : Rd ! Rd is an operator with certain favorable properties (e.g., Lipschitzness and monotonicity), and h : Rd ! R [ {+1} is a proper lower semicontinuous convex function. We assume that the training data describing F is distributed
across M workers/nodes/clients
F (z) := 1M MP
m=1 Fm(z), (4)
where Fm : Rd ! Rd for all m 2 {1, 2, . . . ,M}, and for some results we further assume that Fm is of a finite-sum structure as well:
Fm(z) := 1 r rP i=1 Fm,i(z). (5)

heading: 3.2 ASSUMPTIONS
text: Next, we list two key assumptions - both are standard in the literature on VIs.
Assumption 1 (Lipschitzness in mean) For all clients m = 1, 2, . . . ,M , the operator Fm(z) : Rd ! Rd is Lipschitz in mean with constant Lm 0 on Z . That is,
1 r rP i=1 kFm,i(z1) Fm,i(z2)k2  L2mkz1 z2k 2 , 8z1, z2 2 Z. (6)
For problem (4), Assumption 1 is to be interpreted to hold with r is equal 1, i.e., with Fm = Fm,1.
Assumption 2 (Monotonicity and convexity) (SM) Strong monotonicity/strong convexity. There exist non-negative constants µF , µh such that µh + µF > 0, and the following statements hold:
hF (z1) F (z2), z1 z2i µF kz1 z2k 2 , 8z1, z2 2 Z, (7)
h(z1) h(z2) hrh(z2), z1 z2i µh 2 kz1 z2k 2 , 8z1, z2 2 Z. (8)
(M) Monotonicity/convexity. hF (z1) F (z2), z1 z2i 0, h(z1) h(z2) hrh(z2), z1 z2i 0, 8z1, z2 2 Z. (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 on 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 (4)–(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.

heading: 4.1 THE ALGORITHM
text: MASHA1 is a modification of the extrastep method. At the beginning of each iteration of Algorithm 1, each device knows the value of F (wk), hence it can be calculated z̄k locally. z̄k is a convex combination of zk and wk with momentum parameter ⌧ (typically, ⌧ is close to 1). Also Algorithm can compute zk+1/2 locally. Then it sends the compressed version of the difference Fm(zk+1/2) Fm(wk) to the server, and the server does a reverse compressed broadcast. As a result, an unbiased estimate of F (zk+1/2) F (wk) appears on each node. Also, the nodes receive a bit of information bk. This bit is generated randomly on the server and is equal to 0 with probability ⌧ . Then, all devices make a final update on zk+1, and also update the wk+1 = zk+1 point if the bk = 1 or save it from the previous iteration wk+1 = wk. In the case when the point wk+1 = zk+1, we need to exchange the full values of Fm(wk+1) in order that at the beginning of the next iteration the value of F (wk+1) is known to all nodes. In the stochastic case, Algorithm 1 has the same form, the only thing that changes is that one need to generate a function number (batch number) from 1 to r. We use a possibly difference compressor on each device and also on the server. To distinguish between them, we will use the following notation: Qdevm , qdevm , devm and Qserv, qserv, qserv. Note that, if Q is the identity quantization, i.e., Q(x) = x, then MASHA1 is a distributed analogue of the method from Alacaoglu & Malitsky (2021).
It is important to note main differences from minimization problems. For minimization problems, compressed gradient methods are constructed on the gradient descent or the accelerated gradient
Algorithm 1 MASHA1 (handling unbiased compressors) Parameters: Stepsize > 0, number of iterations K. Initialization: Choose z0 = w0 2 Z . Server sends to devices z0 = w0 and devices compute Fm(w0) and send to server and get F (w0) for k = 0, 1, 2, . . . ,K 1 do
for each device m in parallel do z̄ k = ⌧zk + (1 ⌧)wk
z k+1/2 = prox h(z̄k F (wk)), Generate ⇡km from {1, . . . , r} independently Compute Fm(zk+1/2) & send Qdevm (Fm(zk+1/2) Fm(wk)) to server Compute Fm,⇡km(z k+1/2) & send Qdevm (Fm,⇡km(z k+1/2) Fm(wk)) to server
end for for server do
Compute Qserv 
1 M MP m=1 Q dev m (Fm(z k+1/2) Fm(wk)) & send to devices
Compute Qserv 
1 M MP m=1 Q dev m (Fm,⇡km(z k+1/2) Fm,⇡km(w k)) & send to devices
Sends to devices one bit bk: 1 with probability 1 ⌧ , 0 with with probability ⌧ end for for all devices in parallel do
z k+1 = prox h ✓ z̄k Q serv  1 M
MP m=1 Q dev m (Fm(z k+1/2) Fm(wk))
F (wk)
◆
z k+1 = prox h ✓ z̄k Q serv  1 M
MP m=1 Q dev m (Fm,⇡km(z k+1/2) Fm,⇡mk (w k))
F (wk)
◆
if bk = 1 then w k+1 = zk+1
Compute Fm(wk+1) & send it to server; and get F (wk+1) as a response from server else
w k+1 = wk
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 on simple problems. The second key difference is that we need not compress Fm(zk+1/2) itself, but the difference Fm(zk+1/2) F (wk). We will also see the importance of this approach in the experiments. The later idea is similar to the approach used in the DIANA, VR-DIANA (Mishchenko et al., 2019; Horváth et al., 2019), MARINA (Gorbunov et al., 2021) and EF21 (Richtárik et al., 2021) methods in optimization.

heading: 4.2 THEORY
text: We now establish convergence of MASHA1 in both regimes: deterministic and stochastic (finite-sum). Our analysis relies on the following Lyapunov function:
Vk := ⌧kz k z ⇤ k 2 + kwk z⇤k2, (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 u2C [hF (u), z ui+ h(z) h(u)] . (11)
Here we do not take the maximum over the entire set Z (as in the classical version), but over C – a 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 z⇤ lies in C; for details see the work of Nesterov (2007).
Theorem 1 (Convergence of MASHA1) Let Assumption 1 be satisfied. Then, if one of cases from Assumption 2 is additionally fulfilled, the following estimates hold for the iterates of MASHA1:
• for strongly-monotone/convex case with stepsize 0 <  min np
1 ⌧ 4Cq ; 1 ⌧4(µF+µh) o and Cq :=q
qserv M2 PM m=1(q dev m +M 1)L 2 m:
E [VK ]  1 · µF+µh16 K 1 · V0,
• for monotone/convex case with  p 1 ⌧ 4Cq :
E ⇥ Gap(z̄K) ⇤  8maxu2C[kz0 uk2] K , where z̄ K = 1K K 1P k=0 z k+1/2 .
For proof, see Appendix A.
An important issue of convergence is the choice of ⌧ . If ⌧ = 0 we have the fastest convergence rate, on the other hand, this means that we must send full Fm in each iteration (because we update wk). This is disadvantageous from a communication point of view. The next corollaries give the rules for the right choice of ⌧ , as well as the iterative (in deterministic case), oracle (in stochastic) and communication complexities of Algorithm 1 in both cases. The method without quantization (for example, the ordinary distributed extragradient method) in one iteration transmits the number of information proportional to ⌦(bdM) bits, then here we measure the communication complexity in terms of ⌦(bdM). In literature about method with compression, it is typical to consider only devices compression (Alistarh et al. (2017); Mishchenko et al. (2019); Horváth et al. (2019); Gorbunov et al. (2021); Beznosikov et al. (2020)), 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). It means we choose qserv = 1 and serv = 1.
Corollary 1 (Convergence of MASHA1 in the deterministic case) Let the deterministic problem (3)–(4) be solved by MASHA1 with precision ". Let Assumption 1, and one of the two cases from Assumption 2 be satisfied. If we choose
⌧ = 1 := 1 1M MP
m=1
dev m , (12)
then we have the following estimates for the total # of iterations and the total # of transferred bits from devices to the server:
• in the strongly-monotone/convex case:
O ⇣h 1 +
Cqp (µF+µh)
i log 2kz
0 z⇤k2 "
⌘ iters, O ⇣h 1 + p Cq
µF+µh
i log 2kz
0 z⇤k2 "
⌘ bits,
• in the monotone/convex case
O
✓ Cq maxu2C[kz0 uk2]p
"
◆ iters, O ✓p Cq maxu2C[kz0 uk2]
"
◆ bits.
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 extragradient method is O
Lmaxu2C
⇥ kz 0 uk 2 ⇤ " 1 . Let us consider the case when Lm = L for
all m 2 {1, 2, . . . ,M} and qdevm = qdev. Then MASHA1 has communication complexity O ⇣ Lmaxu2C ⇥ kz 0 uk 2 ⇤ " 1 p (1 + qdev/M) ⌘ . If (1 + qdev/M) < 1, we outperform the
standard uncompressed extragradient method. For example, for if we consider RandK operator = 1/qdev. This means that we have O ⇣ Lmaxu2C ⇥ kz 0 uk 2 ⇤ " 1 · p 1/qdev + 1/M ⌘ .
Corollary 2 (Convergence of MASHA1 in the stochastic case) Let the stochastic problem (3)–(5) be solved by MASHA1 with precision ". Let Assumption 1 and one of the two cases from Assumption 2 be satisfied. If we choose
⌧ = 1 min 1 r ;
then we have the following estimates for the total # of oracle calls and the total # of transferred bits:
• in the strongly-monotone/convex case:
O ⇣h max ⇣ r; 1 ⌘ +max ⇣ p r; 1p ⌘ Cq
(µF+µh)
i log 2kz
0 z⇤k2 "
⌘ calls,
O ⇣h max (1; r ) + max ⇣p r 2; p ⌘ Cq
µF+µh
i log 2kz
0 z⇤k2 "
⌘ bits,
• in the monotone/convex case
O ✓ max ⇣ r; 1 ⌘ Cq maxu2C[kz0 uk2]
"
◆ calls, O ✓ max ⇣p r 2; p ⌘ Cq maxu2C[kz0 uk2]
"
◆ bits.
In the case of a finite sum, in addition to the number of transmitted information, it is not iterations are 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 to calculate full Fm, and the calculation of Fm should be avoided. For deterministic case (when r = 1) estimates from Corollary 2 is the same as in Corollary 1.

heading: 5 EXPERIMENTS

heading: 5.1 BILINEAR SADDLE POINT PROBLEM
text: We start our experiments with a distributed bilinear problem:
min x2Rd max y2Rd
f(x, y) := 1M MP
m=1 fm(x, y), fm(x, y) := x>Amy + a>mx+ b > my + 2 kxk 2 2 kyk 2 ,
(13) where Am 2 Rd⇥d, am, bm 2 Rd. This is a saddle point problem, and F is written as follows: F (x, y) := (rxf(x, y); ryf(x, y)). This operator is strongly monotone and, moreover, all functions Fm are (kAmk2 + )-Lipschitz. Therefore, such a distributed problem is well suited for the primary comparison of our methods. We take d = 100 and generate positive definite matrices Am and vectors am, bm randomly.
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 with natural dithering Horvath et al. (2019), classical error feedback with Top 30% compression, as well as 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 in Figure 1.
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 of the quantized extragradient method shows the efficiency of our approach in which we compress the differences Fm(zk+1/2) F (wk).

heading: 5.2 ADVERSARIAL TRAINING OF TRANSFORMERS
text: We now evaluate how compression performs for variational inequalities (and for saddle point problems, as a special case) in a more practically motivated scenario. Indeed, saddle point problems (special case of variational inequalities) have sample applications in machine learning (see Appendix D), including adversarial training. We consider one of these tasks and train a transformer-based masked
language model (Vaswani et al., 2017; Devlin et al., 2019; Liu et al., 2019) using a 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 w max k⇢1ke,...k⇢Nke
1 N NP n=1 l(f(w, xn + ⇢n, yn)2 + 2 kwk 2 2 k⇢k 2 ,
where w are the weights of the model, {(xn, yn)}Nn=1 are pairs of the training data, ⇢ is 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-efficient during training (Ryabinin 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), use the adversarial training configuration of Zhu et al. (2019), and follow system design considerations for preemptible instances (Ryabinin et 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 et al., 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 216 elements, sending smaller ones uncompressed. These small tensors represent layer biases and LayerNorm scales (Ba et al., 2016) that collectively amount to  1% of the total gradient, but can be more difficult to compress than regular weight tensors. Finally, since Power is a biased compression algorithm, we use error feedback (Karimireddy et al., 2019; Richtárik et al., 2021) 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., 2021). 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.
The learning curves in Figure 2 (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.

Review summaries:
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.   

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.  

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.