Distributed Extra-gradient with Optimal Complexity and Communication Guarantees
Authors: Ali Ramezani-Kebrya
Kimon Antonakopoulos
Igor Krawczuk
Justin Deschenaux
Volkan Cevher
Venue: ICLR 2023 poster (2023)
Keywords: Unbiased Quantization
Variational Inequality
Extra-gradient
Adaptive Sep-size

Abstract: We consider monotone variational inequality (VI) problems in multi-GPU  settings where multiple processors/workers/clients have access to local stochastic dual vectors. This setting  includes a broad range of important problems from distributed convex minimization to min-max and games. Extra-gradient, which is a de facto algorithm  for monotone VI problems, has not been designed to be communication-efficient. To this end, we propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs. We provide an adaptive step-size rule, which  adapts to the respective noise profiles at hand and achieve a fast rate of  ${\cal O}(1/T)$ under relative noise, and an order-optimal ${\cal O}(1/\sqrt{T})$ under absolute noise  and show distributed training accelerates convergence. Finally, we validate our theoretical results by providing real-world experiments and training generative adversarial networks on multiple GPUs.


Published as a conference paper at ICLR 2023
DISTRIBUTED EXTRA-GRADIENT WITH OPTIMAL COMPLEXITY AND COMMUNICATION GUARANTEES
Ali Rabrzani-Kebryar Kimon Antonakopoulos" Igor Krawezuk* Justin Deschenaux") 1
Volkan Cevher
fali Vali@uio.no
$ name lastname@epfl.cc.
ABSTRACT
We consider monotone variational incquality (VI) problems in multi-GPU settings where multiple beocessorswworkers/ccieeee have access to local stochastic dual vectors. This setting includes a broad range of important problems from distributed convex minimization min-max and games. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication- efficient. To this end, we propose quantized generalized extra-grade extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs. We provide an adaptive step-size rule, which adapts to the respective noise profiles at hand and achieve a fast rate of O1//T) under relative noise, and an order- optimal O(L/VT) under absolute noise and show distributed training accelerates convergence. Finally, we validate our theoretical results by providing real-world experiments and training generative adversarial networks on multiple GPUs.
INTRODUCTION
The surge of deep learning across tasks beyond image classification has triggered a vast literature of optimization paradigms, which transcend the standard empirical risk minimization. For example, training generative adversarial networks (GANs) gives rise to solving a more complicated zero-sum game between a generator and discriminator (Goodfellow et al., 2020). This can become even more complex when the generator and the discriminator do not have completely antithetical objectives and e.g., constitute more general game-theoretic setup. A powerful unifying framework which includes those important problems as special cases is monotone variational inequality ( (VI). Formally, given monotone operator A IRd Rdd i.e.
(A(x) A(x'), x 2 0 for all x,x' Rd
our goal is to find some x* E Rdd such that:
(A(x"), x x²) 2 0, for all x E Rd.
(VI)
Several practical problems can be formulated (VI) problem including those with convex-like structures, e.g., convex minimization, saddle-point problems, and games (Facchinei & Pang. 2003; Bauschke & Combettes, 2017; Antonakopoulos al., 2021) with several applications such as auction theory (Syrgkanis et al., 2015), multi-agent and robust reinforcement learning (Pinto et al., 2017), adversarially robust learning (Schmidt et al., 2018), and GANs.
For various tasks, it is widely known that employing deep neural networks (DNNs) along with massive datasets leads significant improvement in terms of learning (Shalev-Shwartz & Ben-David, 2014). However, DNNs can no longer be trained on a single machine. One common solution is to train on multi-GPU systems (Alistarh et al., 2017). Furthermore, federated learning (FL), multiple clients, e.g., a few hospitals several cellphones learn model collaboratively without sharing local data due to privacy risks (Kairouz et al., 2021).
"These authors contributed equally to this work. Department of Informatics, University of Oslo. Work performed at EPFL (LIONS) and Aalborg University. I LLboratory for Information and Inference Systems (LIONS), EPFL. Open source code will be released ht https::////. //pp:://iii whw...thbb.....g......g com/l. i. ONS kPPll//genx

---

Published as a conference paper at ICLR 2023
To minimize a single empirical risk, SGD is the most popular algorithm due its flexibility for parallel implementations and excellent generalization performance (Alistarh et al., 2017: Wilson et al., 2017). Pata-parallel SGD has delivered tremendous success in terms of scalability: (Zinkevich et al., 2010; Bekkerman et al., 2011; Recht et al., 2011; Dean et al., 2012; Coates et al., 2013; Chilimbi et al., 2014; Li al., 2014; Duchi al., 2015; Xing et al., 2015; Zhang al., 2015; Alistarh et al., 2017; Faghri et al., 2020; Ramezani-Kebrya et al., 2021; Kairouz et al., 2021). ). Data-parallel SGD reduces computational costs significantly. However, the communication costs for broadcasting huge stochastic gradients is the main performance bottleneck in large-scale settings (Strom, 2015; Alistarh et al., 2017; Faghri et al., 2020; Ramezani Gamezani-Kebbya et al., 2021; Kairouz et al., 2021).
Several methods have been proposed to accelerate training for classical empirical risk minimiza- tion such as gradient (or model update) compression, gradient sparsification, weight quantiza- tion/sparsification, and reducing the frequency of communication though local methods (Dean et al., 2012; Seide et al., 2014; Sa et al., 2015; Gupta al., 2015; Abadi et al., 2016; Alistarh al., 2017; Wen et al., 2017: Zhou et al., 2018: Bernstein et al., 2018; Faghri et al., 2020; Ramezani- Kebrya et al., 2021; Kairouz et al., 2021). In particular, unbiased gradient quantization is interesting due to both enjoying strong theoretical guarantees along with providing communication efficiency the fly. i.e. convergence under the same hyperparameteres tuned for uncompressed variants while providing substantial savings in terms of communication costs (Alistarh et al., 2017; Faghri et al., 2020;
et al., 2021). Unlike full-precision data-parallel SGD, where each pro- cessor is required to broadcast its local gradient in full-precision i.e., transmit and receive huge full-precision vectors at each iteration, unbiased quantization requires each processor to transmit only a few communication bits per iteration for each component of the stochastic gradient.
In this work, we propose communication-effiiee
variants of a general first-order method that achieves the optimal rate of convergence with improved guarantees on the number of communication bits for monotone VIs and show distributed training accelerates convergence. We employ an adaptive step-size and both adaptive and non-adaptive variants of unbiased quantization schemes tailored to Vls.
There exist three major challenges to tackle this problem: 1) how to modify adaptive variants of unbiased quantization schemes tailored to solve general VIs; 2) can achieve optimal rate of convergence without knowing noise profile and show benefits of distributed training?: 3) can we validate improvements in terms of scalability without compromising accuracy in large-scale settings? We aim to address those challenges and answer all questions in the affirmative:
1.1 SUMMARY OF CONTRIBUTIONS
We propose quantized generalized extra-gradient (Q-GenX) family of algorithms, which employs unbiased compression methods tailored to general VI-solvers. Our framework uni- fies distributed and communication-effiiee variants of stochastic dual averaging, stochastic dual extrapolation, and stochastic optimistic dual averaging.
Without prior knowledge on the noise profile, we provide adaptive step-size rule for Q-GenX and achieve a fast rate of O1/TT) under relative noise, and an order-optimal O(I/VT) in the absolute noise case and show that increasing the number of processors accelerates convergence for general monotone VIs.
We validate our theoretical results by providing real- experiments and training genera- tive adversarial networks on multiple GPUs.
1.2 RELATED WORK
We overview a summary of related work. Complete related work is provided in Appendix B. Adaptive quantization has been used for speech communication (Cummiskey et al., 1973). In machine learning, adapting quantization levels (Faghri et al., 2020), adapting communication frequency in local SGD (Wang& & Joshi, 2019), adapting the number of quantization levels (communication budget) over the course of training (Guo et al., 2020; Agarwal et al., 2021), adapting gradient sparsification scheme over the course of training (Khirirat et al., 2021), and adapting compression parameters across model layers and training iterations (Markov et al., 2022) have been proposed for minimizing single generalized extra- atra-gradieet family
empirical risk. In this paper, we propose communication-efiin of algorithms with adaptive quantization and adaptive step-size for general (VI) problem. In the
2

---

Published as a conference paper at ICLR 2023
VI literature, the benchmark method is EG, proposed by Korpelevich (1976), along with its variants including (Nemirovski, 2004; Nesterov, 2007). Rate interpolation between different noise profiles under an adaptive step-size has been explored by Antonakopoulos et al. (2021). However, their results are limited to centralized and single-GPU settings. Beznosikov et al. (2021); Kovalev et al. (2022) have proposed communication-eeficenn algorithms for VIs with finite-sum structure and variance reduction in centralized settings and (strongly) monotone VIs in decentralized settings, respectively. Unlike (Beznosikov et al., 2021; Kovalev al., 2022), achieve fast and order-optimal rates with adaptive step-size and adaptive compression without requiring variance reduction and strong monotoncity, and improve variance and code-length bounds for unbiased and adaptive compression.
PROBLEM SETUP
Our objective throughout this paper is solve VI with A Rd - IRd being a monotone operator'.
Moreover, in order to avoid trivialities, we make the following mild assumption:
Assumption (Existence). The set X := fx* R x" solves (VD) is non-empty.
Let C denote non-empty compact test domain. A popular performance measure for the evaluation of a candidate solution for VI the so-called restricted gap function defined as:
(x)
suup A(x), -x).
(Gap)
xEC
Gap is used to measure X's performance mainly because it characterizes the solutions of VI via its zeros. Mathematically speaking, we have the following proposition:
Proposition (Nesterov 2009). Let C be non-empty convex subset IRd. Then, the following holds
1. G 2 for all C
2. If Gaape (x) = 0 and C contains a neighbourhood of then x a solution of VI.
Proposition 1 is extension of an earlier characterization shown by Nesterov (2007); we refer the reader to (Antonakopoulos et al., 2019; Nesterov, 2009) and references therein.
From algorithmic perspective, primarily consider the generic family of iterative methods, which have access to a stochastic first-order oracle, i.e., a black-box feedback mechanism (Nesterov, 2004). The respective iterative algorithm can call the oracle over and over at (possibly) random sequence of points Xo, XI,... When called at x, the oracle draws an i.i.d. sample w from (complete) probability space (I2, F)) and returns stochastic dual vector g(x; w) given by
g(x; w) = A(x) + (xx
(2.1)
noise. We consider two important noise profile models, i.e., absolute and relative noise models formally described in the following assumptions:
where wxx; denotes the measurement
Assumption (Absolute noise). Let x E Rd and P.. The oracle g(x; w) enjoys these proper- ties: 1) Almost sure boundedness: There exists some M > O such that [|g[x; w) < M a.s.; 2)
Unbiasedness: E. [g(x:w)] = A(x); 3) Bounded absolute variance: E (x; < o2.
The conditions in Assumption 2 are mild and hold for standard oracles, in particular, in the context of adaptive algorithms (Kavis et al., 2019; Levy et al., 2018; Bach & Levy, 2019; Antonakopoulos & Mertikopoulos, 2021) and typically guarantee convergence rates in ((1/VT) (Nemirovski et al., 2009; Juditsky et al., 2011; Antonakopoulos et al., 2021). Alternatively, one may consider the relative noise model following (Polyak, 1987):
Assumption 3 (Relative noise). The oracle g(x; w) satisfies: 1) Almost sure boundedness: There exists some M > 0 such that (l)(x:))]l+ I M a.s; 2) Unbiasedness: E [][[x;w]] = A(x); 3) Bounded relative variance: There exists some > 0 such that E [x[U(x; w) I clIA(x)
While Assumption 2 enough for obtaining the typical O(IVVT) rate in stochastic settings, As- sumption 3 may allow to recover the well-known order-optimal rate of ((1TT) in deterministic
Notations provided in Appendix
3

---

Published as a conference paper at ICLR 2023
Algorithm I Q-GenX: Loops are executed in parallel on processors. At certain steps, each processor computes sufficient statistics parametric distribution to estimate distribution of dual vectors.
Input: Local data, parameter vector (local copy) Xr, Y, learning rate {yeh,, and set of update steps 2 for t = 1 to T do
if E 24 then
for i= 1 K do
Compute sufficient statistics and update quantization levels
for i
1oo K do
Compute V4,, encode C₁ + CODE Q(Qe, (V), and broadcast Ci, Receive Ct,, from each processor i and decode Ve, f- DEQ o CODE(C,,i l,)
Aggregate X X++1/2 + X; f Σ Vr,t
Compute 1/2, encode d < CODE Q(Qa. (V,,, and broadcast di, Receive di,t from each processor i and decode Vi,411/2 f- DEQ o CODE(d 4,)
10
Aggregate V++1 Y, K Vk.41/2 and update X 14+1
settings. Intuitively, this improvement is explained by the fact that the noisy measurements vanish while we approach solution of VI. In Appendix J, we highlight random coordinate descent and random player updating as popular examples, which motivate Assumption
3 QUANTIZED GENERALIZED EXTRA-GRADIENT
3.1 SYSTEM MODEL AND PROPOSED ALGORITHM
We now describe the algorithmic framework unifying communication-effiiin variants of generalized sttra-gradient (HG) family of algorithms. In particular, we consider a synchronous and distributed system with K processors along the lines of e.g., data-parallel SGD (Alistarh et al., 2017; Faghri et al., 2020; Ramezani-Kebry. et al., 2021; Kairouz et al., 2021). These processors can be cellphones and hospitals in FL or GPU resources in data center. In multi-GPU systems, processors partition large dataset among themselves such that each processor keeps only a local copy of the current parameter vector and has access to independent and private stochastic dual vectors. At each iteration, each processor receives stochastic dual vectors from all other processors and aggregates them. To accelerate training, stochastic dual vectors are first compressed by each processor before broadcasting to other peers and then decompressed before each aggregation step. We focus on unbiased compression where, in expectation, the output of the decompression of compressed vector the same as the original uncompressed vector. We use Qe, to denote a random and adaptive quantization function where the quantization levels l may change over time. We use Ve, e to denote the original (uncompressed) stochastic dual vector computed by process k at time t.
Using multiple processors reduces computational costs significantly. However, communication costs to broadcast huge stochastic dual vectors is the main performance bottleneck in practice (Alistarh et al., 2017). order to reduce communication costs and improve scalability, each processor receives and aggregates the compressed stochastic dual vectors from all peers obtain the updated parameter quantization levels optimized at
......,, ".,...,,,,,e.. le+1) denote the sequence iteration with 0 = to < e ..... < < Lo41 = 1. We now define quantization function Qe,:
vector. Let l = (Co, .....,.................
Definition (Random quantization function). Let E Z4 denote the number of quantization levels. Let u E [0. 1] and C (Cu, ...... E, l denote the sequence of quantization levels at iteration I with to e
< [o-) 1. Let T(u) denote the index of a level such that
T(u) 5 u < E (()+1 Let (u) = (u - (/ r(w)+1 (((w)) be the relative distance of u. to
level Tu)) + We define the random function ge, (w) [0,]] + {lo.l...... .i....,e, Ls la+1) such that qe, (u) ((() with probability 1 ((u)) and qe, (u) = (7)++1 with probability & (u). Let q E Z.,
and v E Rdd. We define the random quantization of v as follows:
Qv =[vll, @ (se, (wi)....... (ua))
where denotes the element-wise
www.eeiseeeaaaaaa (Hadamard) product.
4

---

Published as a conference paper at ICLR 2023
Let Vi, Qe. (Va.e) and V2,4+1/2 Qe. 1V4,+1/22) denote the unbiased and quantized stochastic dual vectors for & E [K] and / (7]. We propose quanlized generalized extra-gradient (Q-GenX) family of algorithms with this update rule:
K
X2+1/2 Xx
7
VE,
K
k=
(Q-GenX)
Y41 =Yi -
Σ
V2,++1/2
X1+1 7011
where (Vi,o, ...) and (V4,1/2, 1/2, Vk.3/2. are the sequences of stochastic dual vectors computed and quantized by processor k E [K]. Provided that Vh, and 1/, stochastic dual vectors for
k E [K], then K Ex= VE,t and K Em V2,1+1/2 remain unbiased stochastic dual vectors.
Q-GenX is described in Algorithm 1. In general, the decoded stochastic dual vectors likely be different from the original locally computed stochastic dual vectors.
particularly appealing feature of (Q-GenX) formulation that it enables to unify communication- efficient and distributed variants of wide range of popular first-order methods for solving VIs. In particular, one may observe that under different choices of Vg., and V 1/22 conmunication-effiiin variants stochastic dual averaging (Nesterov, 2009), stochastic dual extrapolation (Nesterov, 2007), and stochastic optimistic dual averaging (Popov, 1980; Rakhlin & Sridharan, 2013; 3; Hsieh et al., 2021; 2022) in multi-GPU settings are special cases of Q-GenX:
Example 3.1. Distributed stochastic dual averaging: Consider the case where Vy, and
Vr,e+1/2 1/2 (AeX++++11/) + U2,+1/2). This setting yields to X = X2 and hence
0x,1+1/2 Ôk.t 1/22 Therefore, Q-GenX reduces to the communication-eeficcenn stochastic
dual averaging scheme:
K
Y Yi
1
Σ
9k.t
K
(Quantized DA)
k=1
Xt-1 M+1V
Example 3.2. Distributed stochastic dual extrapolation: Consider the case where V/, = G
(A(X,) +Uk,)) and V4 1//21/2 = 04.r+1/2 = Qe, (A(X++1/2) + U2.++1/2 are noisy oracle queries X, and X1+1/2. respectively. Then Q-GenX provides the communication-effiiieenn variant of the Nesterov's stochastic dual extrapolation method (Nesterov, 2007):
X X
gk.t
K
(Quantized DE)
Y = - K
92,2+1/2
k=
X++1 = =74+1Y44
Example 3.3. Distributed stochastic optimistic dual averaging: Consider the case Vi,e =
0i,1-1/2 Qe, (A(X,- + UR,1-1/2) and Ve,41/22 9h.++1/2 = Qe, (A(X,=122) + 1/2)
are the noisy oracle feedback at X,-1/2 and X,+1/2, respectively. We then obtain the communication- efficient stochastic optimistic dual averaging method:
K
X Xx
-u.t-11
K
1=1
K
(Quantized OptDA)
Yo41
Yt
Sk.441/2
K
k=1
X = Ye41
5

---

Published as a conference paper at ICLR 2023
This general formulation of Q-GenX allows to bring these variants under umbrella and provide theoretical guarantees for of them in a unified manner.
3.2 ENCODING
To further reduce communication costs, top of quantization. Let E Z,.. We first note that a vector v E IR" can be uniquely represented by tuple (IIvll,, S, u) where |iv|l, is the L norm of v. = [sgn(vi): (ysn(v),..... ".ron),......... s.g((ua) consists of signs of the coordinates us', and u [ui....,
apply ceimaationnnhooretcallll coding schemes
the normalized coordinates. Note that 0 Σ u4 S 1 for all i E [d]. The overall encoding, i.e., composition coding and quantization, CODE o Q[1vl,, S, qe.) RR+ {=1]a {lo. (i.. L, ) {0. 1)* in Algorithm I uses standard floating point encoding with C. bits to represent the positive scalar ||vllg encodes the sign of each coordinate with one bit, and finally applies an integer encoding scheme L {fo. fi...., ( + {0, 1) to efficiently encode each quantized and normalized coordinate 2e, (u,) with the minimum expected code-length. The overall decoding DEQ o CODE: {0. 13" R2 first reads O2 bits to reconstruct l|vll,- Then it applies Wp-1, : {0, } - (lo, f...... e (.+1))))))). } to reconstruct normalized coordinates. The encoding/decoding details are provided in Appendix K.
... Udd with u4 | /
3.3 ADAPTIVE QUANTIZATION
Instead of using heuristically chosen sequence of quantization levels, adaptive quantization estimates distribution of uncompressed original vectors, i.c., dual vectors, by computing sufficient statistics of parametric distribution, optimizes quantization levels to minimize the quantization error, and updates those levels adaptively throughout the course of training as the distribution changes. Let Fo. Pq) denote a complete probability space. Let qe, PQ represent d variables sampled independently for random quantization in Definition 1. Let v E Rd denote stochastic dual vector to be quantized. Given v, we measure the quantization error by the variance of vector quantization, which is the trace of the covariance matrix:
Ege, (v) v113 |ivl
Σ of (u; 1=1
(3.1)
where и, = lusl/llvll and oz Rs) Eag, [(ge, (u) u) (f u) (())) is the variance for normalized coordinate u. We optimize by minimizing the quantization variance:
min E., [1lQe, (x) Axx:)
RCC
where C= (e: S est,, Vj. to = 0, ls+1 = 1} denotes the set of feasible solutions.
Since random quanitzation and random samples are statistically independent, we can solve the following equivalent problem:
min Eeg F.g. [[[Q,, (g(x(:)) - ((x::))]
(Min
LEE
To solve Van, we first sample J stochastic dual vectors (g(xiiw)), ((x:e)))......::::..... ((x;w))) Let (r) denote the marginal cumulative distribution function (CDF) of normalized coordinates conditioned on observing (19(x;; wy) By the law of total expectation, MinVar can be approximated by:
min Σ [g((x;;;)111 1 Σ
(.) min Σ/ (e) (F) (QAda) L.EC
REEC
i=0
where F(u) = E/= (u) is the weighted sum of the conditional CDFs with by = [lg(x;; w)) E (1)x
Finally, we solve QAda efficiently by either updating levels one at time or gradient descent along the lines of (Faghri et al., 2020).
2 A more fine- fine-graine grained analysis can be done by considering two sequences of adaptive levels one for Vi. and another one for V/,441/2's. s. While in this paper, we quantize both sequences with the same quantization scheme, it is possible to further reduce quantization errors by considering two fine-grained quantization schemes the cost of additional computations processors.

---

Published as a conference paper at ICLR 2023
4 THEORETICAL GUARANTEES
We first establish a variance error bound for general unbiased and normalized compression scheme and a bound on the expected number of communication bits to encode Qe(v), i.e. the output of CODE o Q, which is introduced in Section 3.2. The detailed proofs are provided in the appendix.
Let i == maxisiçe lstz/Ez and du = (2/E1) )2/l))min(g.2) mmin( Under general L normalization and sequence of s quantization levels L, we first establish an upper bound on the variance of quantization:
Theorem (Variance bound). Letv RR, q E4, and s E Et. Let == (lo..... (6....)..+1)) denote sequence of quantization levels defined in Definition 1. The quantization of v in Definition I is unbiased, i.e., (e(]] = V. Furthermore, we have
Eq [alllleevv - -vll]] <Qlivll2
(4.1)
where EQ indicator function.
2+7 =Z+2 1 mi 1id= S d + (lidmmlag 1) 1 2 dul and is the A
Theorem 1 implies that if g(x; w) is an unbiased stochastic dual vector with bounded absolute variance o², then Qe(g(x;w) w)) will be an unbiased stochastic dual vector with a variance upper bound
Eqa². Note that, the dominant term & (ddmmaa 1 [d < den. + (4idmmtanz - 1) 1 1fd 2 drs) monotonically decreases as the number of quantization levels increases. Unlike (Alistarh al., 2017, Theorem 3.2) and Heanezani-Kebrye et al., 2021, Theorem 4) that hold under the special cases of 2 normalization with uniform and exponentially spaced levels, respectively, our bound in Theorem holds under general L normalization and arbitrary sequence of quantization levels. For the special case of L normalization in the regime of large d, which is the case in practice, our bound in Theorem is (l1 vd), which is arbitrarily smaller than O ((vd/s) and O *Vd) in (Alistarh et al., 2017, Theorem 3.2) and Haamzann-Keebyye
al., 2021, Theorem 4), respectively, because & is adaptively designed to minimize the variance of quantization. Furthermore, unlike the bound in (Faghri al., 2020, Theorem 2) that requires an inner optimization problem over an auxiliary parameter the bound in Theorem I is provided in an explicit form without an inner optimization problem, which matches the known 2 () lower bound.
Theorem 2 (Code-length bound). Lei Pj denote the probability of occurrence of & (weight of symbol E,) for j E [s]. Under the setting specified in Theorem 1. the expectation E. Eq [[COE o (()e(((;(w)): E)ll of the number of bits to encode Qe(g(x;w)) is bounded by
( Pý log(1/p)) -po)d).
E Eu [CODE o Q(Qe(((x;=);:
(4.2)
Note (Po...., (Pos....PP+1) Ps+1} can be computed efficiently using the weighted sum of the conditional CDFs in QAda and quantization levels. We provide their expressions in Appendix E. Unlike (Alistarh et al., 2017, Theorem 3.4) and (Ramezani-Kelle special cases of L2 normalization, our bound in Theorem 2 holds under general L normalization. For the special case of T,2 normalization with Vd as in (Alistarh al., 2017, Theorem 3.4), our bound in Theorem 2 can be arbitrarily smaller than (Alistarh et al., 2017, Theorem 3.4) and (Ramezani-Kebry)
et al., 2021, Theorem 5) that hold under the
al., 2021, Theorem 5) depending on {po..... Po+1 Compared (Faghri et al., 2020, Theorem 3), our bound in Theorem 2 does not have an additional nE,,d term. We show that a total expected number of O ((K/fc) bits are required reach an gap, which matches the lower bound developed for convex optimization problems with finite-sum structures (Tsitsiklis & Luo, 1987; Korhonen & Alistarh, 2021).
We finally present the convergence guarantees for Q-GenX given access to stochastic dual vectors under both absolute noise and relative noise models Assumptions 2 and 3, respectively.
Theorem 3 (Q-GenX under absolute noise). Let C C R denote compact neighborhood of solution for (VI) and let D2 == supxec ||X 12 Suppose that the oracle and the problem (VT) satisfy Assumptions and 2, respectively, Algorithm is executed for T iterations on K processors with an adaptive step-size 7t = K(1 + Σ
E Σk_ [V,, V2,441/22l?>- 1/2, and quantization levels are updated J times where Eg with variance bound EQ.i in (4.1) and code-length bound Nq.
7

---

Published as a conference paper at ICLR 2023
in (4.2) is used for T iterations with Σj=1 T} T. Then have
E Gapc
G
- X
T
V -
-
(E
+ +o)
T
VTK
In addition, Algorithm requires each processor to send at most 7 E TyNq,s communication bits per iteration in expectation.
We now establish fast rate of (1/TT) under relative noise and mild regularity condition:
Assumption 4 (Co-coercivity). Let 3 0. We assume that operator A is 3-cocoercive:
(A(x) A(x), x x' 2 A1|A(x) A(x')I? for all x, x, R2
(4.3)
For panoramic view of this class of operators, we refer the reader to (Bauschke & Combettes, 2017). Remark 1. The order-optimal rate of (L//VT) under absolute noise does not require co-cocercivity, Our adaptive step-size also does not depend the noise model co-coercivity. Co-coercivity is required only to achieve fast rate of (1)TT) in the case relative noise.
Theorem 4 (Q-GenX under relative noise). Ler C R denote a compact neighborhood of a solution for (VI) and let D sup xec |[ - -ool?. Suppose that the oracle and the problem (VI) satisfy Assumptions 3, and 4, Algorithm is executed T iterations on K processors with an adaptive xt-1
step-size K(1 + +
(/,+1/2112)-1// and quantization levels are updated J times where& E with variance bound EQ. in (4.1) and code-length bound Nq.; in (4.2) is used for T3
1lVa, _
iterations with Σ 1= T3 = T. Then we have
T E Gape
(
((c ((e+
E1=1 (
x =0
KT
In addition, Algorithm requires each processor send most & E/=1 TyNq.s communication bits per iteration in expectation.
To the best of our knowledge, results in Theorems 3 and 4 are the first ones proving that increasing the number of processors accelerates convergence for general monotone VIs under an adaptive step size. Theorems and 4 show that we can attain a fast rate of (1/TT) and an order-optimal (L1vVT) without prior knowledge the noise profile while significantly reducing communication costs.
Compared to saddle point problems, our rates are optimal. This can be verified by lower bounds in (Beznosikov et al., 2020). For convex problems in deterministic settings, the rate be improved to ()) via acceleration. However, is known that in the stochastic and distributed settings, rates cannot be improved even with acceleration. E.g.. for convex and smooth problems under absolute noise model, the lower bound of 2 (TR) can be established by (Woodworth et al., 2021, Theorem 1) and setting the number of gradients per round to one.
In Appendix I, we build on Theorems 3 and to capture the trade-off between the number of iterations to converge and time iteration, which includes total time required to update model on each GPU.
5 EXPERIMENTAL EVALUATION
In order to validate our theoretical results, we build on the code base of Gidel et al. (2019) and run an instantiation of Q-GenX obtained by combining ExtraAdam with the compression offered by the torch_ cgx pytorch extension of Markov et al. (2022), and train WGAN-GP (Arjovsky et al., 2017) on CIFARIO (Krizhevsky, 2009).
Since torch_cgg uses OpenMPI (Gabriel et al., 2004) as its communication backend, we use OpenMPI as the communication backend for the full gradient as well for fairer comparison. We deliberately do not tune any hyperparameters to fit the larger batchsize since simliar to (Gidel et al., 2019), we do not claim to set new SOTA with these experiments but simply want to show that our theory holds up in practice and can potentially lead to improvements. For this, present basic
8

---

Published as a conference paper at ICLR 2023
230
Mode GenBP DiscBP PenBP
Total
UQ4
2.99
7.40
1.59
12.96
UQ8 2.99
7.65
1.69
13.29
FP32 3.00
8.36
1.69
14.05
184 4000
308
6FF 0107 F
Figure 1: FID evolution during training (left). We compare full-precision ExtraAdam with a simple instantiation of Q-GenX. FID stands for Frechet inception distance, which is standard GAN quality metric introduced in (Heusel et al., 2017). Fine grained comparison of average backward () times generator, discriminator, gradient penalty well as total training time (s) (middle and right). The .backward function is where pytorch DistributedDDtaaarrllle (DDP) handles gradient exchange.
experiment showing that even for a very small problem size and heuristic base compression method cgx, we can achieve a noticeable speedup of around 8%. We expect further gains to be achievable for larger problems and more advanced compression methods. Given differences in terms of settings and the lack of any code, let alone an efficient implementations that can be used a real-world setting (iee. CUDA kernels integrated with networking), it is difficult to impossible to conduct fair comparison with Beznosikov et al. (2021). More details and a comparison with QSGDA of Beznosikov et al. (2022) are provided in Appendix H. We are not aware of any other existing method dealing with the same problem in our paper without the cost associated with variance reduction.
We follow exactly the setup of (Gidel et al., 2019) except that share an effective batch size of 1024 across nodes (strong scaling) connected via Ethernet, and use Layernorm (Ba et al., 2016) instead of Batchnorm (loffe& & Szegedy, 2015) since Batchnorm is known to be challenging to work with in distributed training as well as interacting badly with the WGAN-GP penalty. The results are shown in Figure 1 (left) showing evolution of FID. We note that we do not scale the learning rate any other hyperparameters to account for these two changes so this experiment is not meant to claim SOTA performance, merely to illustrate that
1. Even with the simplest possible unbiased quantization a relatively small-scale setup, we can observe a speedup (about 8%).
2. This speedup does not drastically change the performance.
We compare training using the full gradient of 32 bit (FP32) to training with gradients compressed to 8 (UQ8) and bits (UQ4) using a bucket size of 1024. Figure (middle and right) shows a more fine grained breakdown of the time used for back propagation (BP) where the network activity takes place. GenBP, DiscBP and PenBP refer to the backpropagation for generator, discriminator, and the calculation of the gradient penalty, respectively. Total refers to the sum of these times.
CONCLUSIONS
We have considered mononote VIs in synchronous and multi-GPU setting where multiple processors compute independent and private stochastic dual vectors in parallel. We proposed Q-GenX, which employs unbiased and adaptive compression methods tailored to a generic unifying framework for solving VIs. Without knowing the noise profile in advance, we have obtained an adaptive step-size rule, which achieves fast rate of O(1/T") under relative noise, and order-optimal O(Iv/T) in the absolute noise case along with improved guarantees on the expected number of communication bits. Our results show that increasing the number of processors accelerates convergence.
Developing new VI-solvers for asynchronous settings and establishing convergence guarantees while relaxing co-coercivity assumption the operator interesting problems left for future work. Expected co-coercivity has been used as a more relaxed noise model (Loizou et al., 2021). It is interesting to study monotone VIs under expected co-coercivity and adaptive step-sizes in the future.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors would like thank Fartash Faghri, Yang Linyan, Ilia Markov, and Hamidreza Ramezanikebrya for helpful discussions. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation pro- gramme (grant agreement n" 725594- time-data). This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 100021_205011. 205011
The work of Ali Ramezani-Ketin Kebrya was in part supported by the Research Council of Norway, through its Centre for Research-based Innovation funding scheme (Visual Intelligence under grant no. 309439), and Consortium Partners.
This work is licensed under a Creative Commons "Attribution 3.0
CC
Unported" license.
BY
REFERENCES
Martín Abadi, Paul Barham, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: A system for large-scale machine learning. In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2016.
Saurabh Agarwal, Hongyi Wang, Kangwook Lec, Shivaram Venkataraman, and Dimitris Papailiopou- los. Adaptive gradient communication via critical learning regime identification. In Proceedings of Machine Learning and Systems (MLSys), 2021.
Dan Alistarh, Demjan Grubic, Jemyy Z. Li, Ryota Tomioka, and Milan Vojnovic. QSGD:
Communication-cffae SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Kimon Antonakopoulos and Panayotis Mertikopoulos. Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Kimon Antonakopoulos, Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror-prox algorithm for variational inequalities with singular operators. Advances Neural Information Processing Systems (NeurIPS), 2019.
Kimon Antonakopoulos, Thomas Pethick, Ali Kavis, Panayotis Mertikopoulos, and Volkan Cevher. Sifting through the noise: Universal first-order methods for stochastic variational inequalities, In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning (ICML), 2017.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint arXiv: 1607.06400 2016.
Francis Bach and Kfrr Yehuda Levy. universal algorithm for variational inequalities adaptive to smoothness and noise. In Conference Learning Theory (COLT), 2019.
Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2017.
Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up Machine Learning: Parallel and Distributed Approaches. Cambridge University Press, 2011.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD: Compressed optimisation for non-convex problems. In International Conference on Machine Learning (ICMI), 2018. 2018.
10

---

Published as a conference paper at ICLR 2023
Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle-pon point problems: Lower bounds, optimal and robust algorithms. arXiv preprint arXiv:2010.13112, 2020.
Alcksandr Beznosikov, Peter Richtárik, Michael Diskin, Max Ryabinin, and Alexander Gasnikov. Distributed methods with compressed communication for solving variational inequalities, with theoretical guarantees. arXiv:2110.03313, 2021.
Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. arXiv preprint arXiv:2202.07266. 2022.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https: http:///wwwww....... com/. Software available from wandb.com.
Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project Adam: Building an efficient and scalable deep learning training system. In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2014.
Adam Coates, Brody Huval, Tao Wang, David Wu, Bryan Catanzaro, and Andrew Y. Ng. Deep learning with COTS HPC systems. In International Conference on Machine Learming (ICML), 2013.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. WILEY, 2006.
P. Cummiskey, Nikil S. Jayant, and James L. Flanagan. Adaptive quantization in differential PCM coding of speech. Bell System Technical Journal, 52(7):1105-115) 1973.
Peter Davies, Vijaykrishna Gurunanthan, Niusha Moshrefi, Saleh Ashkboos, and Dan Alistarh. New bounds for distributed mean estimation and variance reduction. In International Conference Learning Representations (ICLR), 2021.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoc Le, and Andrew Y. Ng. Large scale distributed deep networks. In Advances in Neural Information Processing Systems (NeurIPS), 2012.
John C. Duchi, Sorathan Chaturapruek, and Christopher Ré. Asynchronous stochastic convex optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
Peter Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 11(2):994-200 1975.
Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and complemen- tarity problems. Springer, 2003.
Fartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel M. Roy, and Ali Ramezani- Kebrya. Adaptive gradient quantization for data-parallel SGD. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Edgar Gabriel, Graham E. Fagg, George Bosilca, Thara Angskun, Jack J. Dongarra, Jeffrey M. Squyres, Vishal Sahay, Prabhanjan Kambadur, Brian Barrett, Andrew Lumsdaine, Ralph H. Castain, David J. Daniel, Richard L. Graham, and Timothy S. Woodall. Open MPI: Goals, concept, and design of a next generation MPI implementation. In Proceedings, 11th European PVM/MPI Users' Group Meeting. pp. 97-104, Budapest, Hungary, September 2004.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julies A variational inequality perspective on generative adversarial networks. In International Conference on Learning Representations (ICLR), 2019.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11):139-144 2020.
Jinrong Guo, Wantao Liu, Wang Wang, Jizhong Han, Ruixuan Li, Yijun Lu, and Songlin Hu. Accelerating distributed deep learning by adaptive gradient quantization. In IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), 2020.
11

---

Published as a conference paper at ICLR 2023
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In International Conference on Machine Learning (ICML), 2015.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to a local nash equilibrium. In Advances in Neural Information Processing Systems (NeurlPS), 2017.
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In Conference Learning Theory (COLT), 2021.
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism. Journal of Muchine Learning Research, 23:1-49, 2022.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICMI), 2015.
Anatoli Juditsky, Arkadi Semen Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Kairouz, H. McMahan, B. Avent, Bellet, M. Bennis, N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings. R. G. L. D'Oliveira, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, B. Gibbons, M. Gruteser, Harchaoui, C. He, L. He, Huo, Hutchin- son, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Liu, P., M. Mohri, R. Nock, A. Özgür, R. Pagh, M. Raykova, H. Qi, D. Ra- mage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, Wang, L. Xiong, Z. Xu, Q. Yang, X. Yu, H. Yu, and S. Zhao. Advances and open problems in federated learning. Foundations and x in Machine Learning, 14(1-2):1 11100,0,-21, 2021.
Ali Kavis, Kfir Yehuda Levy, Francis Bach, and Volkan Cevher. UnixGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Sarit Khirirat, Sindri Magnússon, Arda Aytekin, and Mikael Johansson. A flexible framework for communication--ffiiinee machine learning. AAAI Conference on Artificial Intelligence, 2021.
Janne H Korhonen and Dan Alistarh. Towards tight communication lower bounds for distributed optimisation. In Advances Neural Information Processing Systems (NeurIPS), 2021.
Galina Michailovna Korpelevich. The extragradient method for finding saddle points and other problems. Ékonom. matematicheskie metody, 12:747-756, 1976.
Dmitry Kovalev, Aleksandr Beznosikov, Abdurakhmon Sadiev, Michael Persiianov, Peter Richtárik, and Alexander Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. arXiv preprini arXiv:2202.027771 2022.
Alex Krizhevsky. Learning multiple layers features from tiny images. 2009. Technical report, University of Toronto.
Kfir Yehuda Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceleration. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor- YornYiing Su. Scaling distributed machine learning with the parameter server. In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2014.
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julies Stochas- tic gradient descent-ascen and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
12

---

Published as a conference paper at ICLR 2023
Yura Malitsky, Golden ratio algorithms for variational inequalities. Mathematical Programming. 184: 383 383-410, 2020.
Ilia Markov, Hamidreza Ramezanikebrya, and Dan Alistarh. Project CGX: Algorithmic and system support for scalable deep learning on a budget. arXiv:2111.08617 2022.
Arkadi Semen Nemirovski. Prox-method with rate of convergence (11/l) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems.
SIAM Journal on Optimization, 15(1):229-2514 2004
Arkadi Semen Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochas- tic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4): 1574-1609, 2009.
Yurii Nesterov. Introductory Lectures on Convex Optimization: Basic Course. Kluwer Academic Publishers, 2004.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319-444 2007.
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical PregtttccaPoorrama Programming, 120(1):221-259, 2009.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In International Conference Machine Learning (ICML), 2017.
Boris Teodorovich Polyak. Introduction to Optimization. Optimization Software, 1987.
Leonid Denisovich Popov. A modification of the Arrow-Hurwicz method for search saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845-844 848, 1980.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems (NeurIPS), 2013.
Ali Ramezani- Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M.
-enneaani-Kebyy,,
Roy. NUQSGD: Provably communication-effiienn data- Laralla SGD via nonuniform quantization. Journal of Machine Learning Research (JMLR), 22(1 1-), 2021.
Benjamin Recht, Christopher Ré, Stephen J. Wright, and Feng Niu. HOGWILD!: A lock-free
approach to parallelizing stochastic gradient descent. Advances Neural Information Processing Systems (NeurIPS), 2011.
Christopher M. De Sa, Ce Zhang, Kunle Olukotun, and Christopher Ré. Taming the wild: unified analysis of HOGWiLD!-style algorithms. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adver- sarially robust generalization requires more data. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In INTERSPEECH, 2014.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Fedor Stonyakin, Alexander Gasnikov, Pavel Dvurechensky, Mohammad Alkousa, and Alexander Titov. Generalized mirror prox for monotone variational inequalities: Universality and inexact oracle, 2018.
Nikko Strom. Scalable distributed DNN training using commodity GPU cloud computing. In INTERSPEECH. 2015.
13

---

Published as a conference paper at ICLR 2023
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
John N. Tsitsiklis and Zhi-Quan Luo. Communication complexity of convex optimization. Journal of Complexity, 3(3):231-243, 1987.
Jianyu Wang and Gauri Joshi. Adaptive communication strategies achieve the best error-runtime trade-off in local-update SGD. In Proceedings of Machine Learning and Systems (MLSys), 2019.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. TemnGad: Temary gradients reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stem, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Blake E Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Conference on Learning Theory (COLT), 2021.
Eric P. Xing, Qirong Ho, Wei Dai, Jin Kyu Kim, Jinliang Wei, Seunghak Lee, Xun Zheng, Pengtao Xie, Abhimanu Kumar, and Yaoliang Yu. Petuum: A new platform for distributed machine learning on big data. IEEE transactions on Big Data, 1(2):49-67, 2015.
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. International Conference Machine Learning (ICML), 2017.
Sixin Zhang, Anna Choromanska, and Yann LeCun. Deep learning with elastic averaging SGD, In Advances in Neural Information Processing Systems (NeurIPS), 2015.
Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou. Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients. 4rXiv:1606.06166, 2018.
Martin A. Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 2010.
A APPENDIX
Notation. We use E[:]. || 11. 11 Ilo. and || ||+ to denote the expectation operator, Euclidean norm, number of nonzero elements of vector, and dual norm, respectively. We use | | to denote the length of binary string, the length of vector, and cardinality of set. We use lower-case bold letters to denote vectors. Sets are typeset a calligraphic font. The base-2 logarithm is denoted by log, and the set of binary strings denoted by {0, 1)". We use [n]] denote (l...., n for an integer n.
Content of the appendix.
The appendix is organized as follows:
Complete related work is discussed in Appendix B.
Special cases of Q-GenX are provided in Appendix C.
Theorem (variance bound) proved in Appendix D.
Theorem 2 (code-length bound) is proved in Appendix E.
Theorem 3 (Q-GenX under absolute noise) is proved in Appendix F.
Theorem (Q-GenX under relative noise) is proved in Appendix G.
Additional experimental details included in Appendix H.
Trade-off between number of iterations and time per iteration is provided in Appendix I.
Popular Examples motivating Assumption 3 are provided in Appendix
The encoding/decoding details provided in Appendix K.
14

---

Published as a conference paper at ICLR 2023
B FURTHER RELATED WORK
Unbiased compression. Seide et al. (2014) proposed SignSGD, efficient heuristic scheme to reduce communication costs drastically by quantizing each gradient component to two values. (This scheme is sometimes termed IbitGG (Seide et al., 2014).) Bernstein al. (2018) later provided convergence guarantees for a variant of SignSGD. Note that the quantization employed by SignSGD is not unbiased, and so new analysis was required. Alistarh et al. (2017) proposed quantized SGD (QSGD) focusing on the uniform quantization of stochastic gradients normalized to have unit Fuclidean norm. Their experiments illustrate a similar quantization method, where gradients are normalized to have unit 7, norm, achieves better performance. We refer to this method as QSGDinf or Qinf in short. Wen et al. (2017) proposed TemGrad, which can be viewed as a special case of QSGDinf with three quantization levels. HamezanniKebbry et al. (2021) proposed nonuniform quantization levels (NUQSGD) and demonstrated superior empirical results compared to QSGDinf. Recently, lattice- quantization has been studied for distributed mean estimation and variance reduction (Davies et al., 2021).
Adaptive quantization has been used for speech communication and storage (Cummiskey et al., 1973). In machine learning, several biased and unbiased schemes have been proposed to compress networks and gradients. In this work, focus on unbiased and coordinate- wise schemes to compress gradients. Zhang et al. (2017) proposed ZipML, which is an optimal quantization method if all points to be quantized are known a priori. To find the optimal sequence of quantization levels, dynamic program is solved whose computational and memory cost is quadratic in the number of points to be quantized, which in the case of gradients would correspond their dimension. Faghri et al. (2020) have proposed two adaptive gradient compression schemes where multiple processors update their compression schemes in parallel by efficiently computing sufficient statistics of a parametric distribution. Adaptive quantization methods in (Faghri et al., 2020) are applicable only when minimizing single empirical risk. In addition, convergence guarantees in (Faghri et al., 2020) are established for smooth nonconvex optimization with fixed step-size. In this paper, generalized EG family of algorithms with an adaptive and unbiased quantization scheme for a general (VI) problem. Furthermore, we establish improved variance and code-length bounds and optimal convergence guarantees for nonconvex problems with an adaptive step-size.
propose communication-ffiicnn
variants of
Adaptive gradient compression has been studied in other contexts when minimizing single empirical risk, such as adapting the communication frequency in local SGD (Wang & Joshi, 2019), adapting the number of quantization levels (communication budget) over the course of training (Guo al., 2020; Agarwal et al., 2021), adapting gradient sparsification scheme over the course of training (Khirirat al., 2021), and adapting compression parameters across model layers and training iterations (Markov et al., 2022). We focus on unbiased and normalized quantization and adapt quantization levels to minimize quantization error for generalized EG family of algorithms, which has not been considered in the literature.
First-order methods solve VIs. In the VI literature, the benchmark method is extra- gradient (EG), proposed by Korpelevich (1976), along with its variants including (Nemirovski, 2004; Nesterov, 2007). Furthermore, there have been a line of work that aims to focus on establishing convergence guarantees though adopting an adaptive step-size policy. To that end, we review the most relevant works below.
For unconstrained problems with an operator that is locally Lipschitz continuous (but not necessarily globally), the Golden Ratio Algorithm (GRAAL) of Malitsky (2020) achieves convergence without requiring prior knowledge of the problem's 's Lipschitz parameter. Moreover, such guarantees are provided in problems with a bounded domain by the Generalized Mirror Prox (GMP) algorithm of Stonyakin et al. (2018) under the umbrella of Hölder continuity.
A more relevant method that simultaneously achieves O(/vTT) rate in non-smooth and/or stochastic problems and an O(1TT) rate in smooth ones is the recent algorithm of Bach & Levy (2019). This algorithm employs an adaptive, AdaGrad-like step-size policy which allows the method to interpolate between these regimes. On the negative side, this algorithm requires a bounded domain with (Bregman) diameter that is known in advance.
15

---

Published as a conference paper at ICLR 2023
In optimization community, similar rate interpolation guarantees between different noise profiles has been explored by Antonakopoulos et al. (2021). However, their results are limited to centralized, single GPU settings.
While all these algorithms concern standard single-GPU settings with having access to full-pree coll-precision stochastic dual vectors, we consider multi-GPU settings, which has not been considered before.
Beznosikov et al. (2021); Kovalev et al. (2022) have proposed communication-efficin algorithms for VIs with finite-sum structure and variance reduction in centralized settings and (strongly) monotone VIs in decentralized settings, respectively. Unlike (Beznosikov et al., 2021; Kovalev et al., 2022), achieve fast and order-optimal rates with adattive step-size and adaptive compression without requiring variance reduction and strong monotoncity, and improve variance and code-length bounds for unbiased and adaptive compression.
Detailed comparison with (Antonakopoulos et al., 2021; Alistarh et al., 2017; Faghri et al., 2020; Ramezani- Kebryya et al., 2021). In this section, elaborate and provide detailed comparison with the most relevant related work (Antonakopoulos et al., 2021; Alistarh et al., 2017; Faghri et al., 2020; Ramezani- Camezani-Kebrya et al., 2021).
Although our results build upon the extra-gradient literature Korpelevich (1976), as Antonakopoulos et al. (2021) does, in this paper, we address monotone V// convex-concave min-max problems in distributed and large-scale settings, which has not been considered in Antonakopoulos et al. (2021) that strictly refers to strictly single-GPU and centralized setting. The considered distributed framework complicates the analysis in a significant manner, since we have to simultaneously treat two different rypes of randomness. In particular, on one hand, we face randomness associated with the compression scheme (which is necessary to achieve substantial communication savings in distributed setup) where on the other hand we deal with different noisy feedback models stemming from inexact operator calculations (before any compression takes place), which together result in efficient implementations at each GPU. We show benefits of distributed training in terms of accelerating convergence for general monotone VIs.
Unlike (Alistarh et al., 2017, Theorem 3.2) and Hannezani-Kebryee et al., 2021, Theorem 4) that hold under the special cases of 1,2 normalization with uniform and exponentially spaced levels, respectively, our bound in Theorem 1 holds under general L normalization and arbitrary sequence of quantization levels. For the special case of L normalization in the regime of large d, which is the case in practice, bound in Theorem is ((1 which is arbitrarily smaller than O(Vd/s) and Vd) in (Alistarh al., 2017, Theorem 3.2) and (Ramezani-Kelle respectively, because { is adaptively designed to minimize the variance of quantization. Furthermore, unlike the bound in (Faghri et al.. 2020, Theorem 2) that requires an inner optimization problem over an auxiliary parameter p. the bound in Theorem 1 is provided in an explicit form without an inner optimization problem, which matches the lower bound.
et al., 2021, Theorem 4),
Unlike (Alistarh et al., 2017, Theorem 3.4) and (Ramezani-Kedl under the special cases of T/2 normalization, our code-length bound in Theorem 2 holds under general L normalization. For the special case of I,2 normalization with /d as in (Alistarh et al., 2017, Theorem 3.4), our bound in Theorem 2 can be arbitrarily smaller than (Alistarh al., 2017, Theorem 3.4) and (Ramezani-Kebhl (Faghri et al., 2020, Theorem 3), our bound in Theorem 2 does not have additional ne,, term.
et al., 2021, Theorem 5) that hold
et al., 2021, Theorem 5) depending on {po.... 1. Compared to
C SPECIAL CASES OF Q-GENX
In this section, we show that under different choices of Vk, and Vs,411/2, one can obtain communication--effciien variants of stochastic dual averaging (Nesterov, 2009), stochastic dual extrapolation (Nesterov, 2007), and stochastic optimistic dual averaging (Popov, 1980; Rakhlin & Sridharan, 2013; Hsich et al., 2021; 2022) in multi-Ga UPU settings as special cases of Q-GenX.
Example C.1. Communication-efficee Vh, = O and V/.41/2 = 0x.411/2 = =Q,, (A(X++1/2)) + Un2-1/22- This setting yields to Xz+1/2 = X, and hence 0k,141/2 9k.t V/.41/2- Therefore, Q-GenX reduces to the communication-
stochastic dual averaging: Consider the case where
16

---

Published as a conference paper at ICLR 2023
efficient stochastic dual averaging scheme:
Y1+ = K-1
Ok.t
(Quantized DA)
k=
X++1 74+1 141=74+1Y44
Example C.2. Communication--ffcienn stochastic dual extrapolation: Consider the case where
Vk.t = Ōk. = (A(())))) and V/,e+1/2 = 9x,e+ 1/2 = Qe. (A(Xx++112))) +U,,))+UUUUU2///3 are noisy
oracle queries X, and Xt+1/2- respectively. Then Q-GenX provides the communication-efficcenn variant of Nesterov's stochastic dual extrapolation method (Nesterov, 2007):
K
Tt
X = =X,-
OR.t
K
x=1
(Quantized DE)
Y(4 Yr K
1x,2+1/2
Xe+1 -7++1Y++
Example C.3. Communication-effiieent stochastic optimistic dual averaging: Consider the case
Vk. = 9k,r-1/2 = Qe, (1() + 1/22
and V2, = 9x.++1/2 = Qe, (A((x-112) +
Uk,+1/2) are the noisy oracle feedback at X,-1/2 and X respectively. We then obtain the communication-efficiee stochastic optimistic dual averaging method:
X1+1/2 =x,-
9k.t
K
k=1
K
(Quantized OptDA)
Y41 V/ K-1
g
k=1
X4+1 10411141
D PROOF OF THEOREM (VARIANCE BOUND)
uy = | Bo =- 60, and Bj = [6 (j+1] for j E [s]. Let Ve(v) = EnelllQe(v) - v
denote the variance of quantization Eq. (3.1). Then we have
Ve(v) = MM E(h+
-1-w,) +
(Ls+1 1:41-4;)uu (2)
(D.1)
a.EB.
5=1 M.EB
We first find the minimum ky that satisfies (Lz-1 u)(u e,) S kjj? for E B, and [s). The minimum ky can be obtained by changing the variable u = L,0:
(Cst1/e, (0 1)
K2 15056411/1
0²
(D.2)
(0--1/1-11
4(lg+1/Ez)
We note that lft2/lz and (x - 1)2/ (4r) monotonically increasing function of x for x: > Furthermore, note that
1
Σ
[v]
M. B
17

---

Published as a conference paper at ICLR 2023
Substituting Eq. (D.2) into Eq. (D.1), upper bound Ve(v) is given by
Ve(v) lvll e + E-
1
Σ a,E8
(41 21) u,)uk
In the rest of the proof, the following known lemma.
Lemma 1. Let Rd. Then, for all 0 < p < 4, we have ll
[llb S d2/p-1/9
We note that Lemma holds even when 1 and || lla is merely seminorm.
We now establish an upper bound on En, (2 Wz)uu.
Lemma 2 (Ramezani-Kebrye et al. 2021, Lemma 15), Let p E (0, 1) and u E Bg. Then we have ull u) Kpti (2-p) uP where
1/p ( 1 (1-1)
Kº = 2/p- 2/p 2/p-1/
(D.3)
Let S, denote the coordinates of vector v whose elements fall into the (i + 1)-th bin, ie.
Sj = (i: ui E B3} for E [s]. For any < 1 and q 2 have
| Σ uf 1|v1| E.E
lusl
SE
$ || 1 ||
< || 1
$ 1ivldd
where the third inequality holds as ||vlp < 1/vl//d/p-112 using Lemma and the last inequality
holds as ||vll S ||v|22 for 2 2. Using Lemmas and 2, we establish an upper bound on Ve(v):
Ve(v) < 11112
+ Kyli (2-)
4
2
For 2 1, we note that ||v ||
2-
mmn
2-p
2 i.e.
2+2-
1
ve(v) - v
+
K,lp (2- mi
(D.4)
2
Note that the optimal p minimize EQ obtained by minimizing:
1/p ,) 1 1 1-p81p
1/p
X(p)
where 8 fid
Taking the first-order derivative of A(p). the optimal pa is given by
8-11 822
p
(D.5)
0, <<2
Substituting (D.5) into (D.4) gives (4.1), which completes the proof.
E PROOF OF THEOREM 2 (CODE-LENGTI BOUND)
Let denote the length of binary string. In this section, obtain upper bound on E. CODE Q(Qr(g((; w)) E)], Lee, the expected number of communication bits per iter- ation. We recall from Section 3.2 that is uniquely represnted by the tuple ([[vllg 8, u). We first
18

---

Published as a conference paper at ICLR 2023
encode the norm |/vll using C bits where. In practice, standard 32-bit floating point encoding.
We then one bit to encode the sign of each nonzero entry of u. Let Sj {i: un 1 (+il) and N2 : S for j [s]. We now provide the expression for probabilities associated with our symbols to be coded, i.e., {lo, f1....; fs+1). The associated probabilities can computed using the weighted sum of the conditional CDFs of normalized coordinates in QAda and quantization levels:
Proposition 2. Let j E [s]. The probability of occurrence of lg (weight of symbol (j) is given by
2 u- ( --
dF(u)+ + [ fitt lstz u dF(u) e
Pj = Pr(e))
Je, 44+1
where F is the weighted sum of the conditional CDFs of normalized coordinates in QAda. addition. we have
Po Pr(Lu 0) /-- d1 1- dF(uu) and pa+1 Pr(ls+1 =1) [( 14-l, lo dF(u).
E1
We have an upper bound on the expected number of nonzero entries as follows:
Lemma 3. Let E Rd. The expected number of nonzeros in Qe(v) is given by
Eq Qel(vvll (1 -o)dd.
(E.1)
We then send the the associated codeword to encode each coordinate of u. The optimal expected code-length for transmitting one random symbol is within one bit the entropy of the source (Cover & Thomas, 2006). So the number of required information bits to transmit entries of is bounded above by (L) + 1) where (L) = - ش5= 1 Pj log(p,) ) is the entropy in bits. Putting everything together, we have
E, I CODE Q(Qe()(x; 1)1 < C. + (1- (H(L) + L)d
where C 0(1) is universal constant. Finally, we note that the entropy of source with outcomes is upper bounded by log(n).
F PROOF OF THEOREM 3 (Q-GENX UNDER ABSOLUTE NOISE)
We note that the output of Algorithm follows the iterates of (Q-GenX):
X441/2 X,
Yt
VeL
K
k=1
(Q-GenX)
Y41 Y2 K-11
V2,4+1/2
X N411+++
We first prove the following Template Inequality for (Q-GenX), which is useful milestone to prove both Theorems 3 and 4.
Proposition (Template inequality). Let X E Rd. Suppose the iterates Xt of (Q-GenX) updated with some non oon-innreasing step-size schedule 7/. for t 1, 1/2, ... Then, we have
T
XII
1
V V X,41/2 x)
V2,441/2 - V2,
76
2
2K
(R.1
T
Σ
Xr
- X X
2
19

---

Published as a conference paper at ICLR 2023
Proof. We first decompose Ek= V 11,411/2,X4111 X) into two terms and note:
12, 22--1/2 X2+1/2-XX x) SA + SB.
where
1 K
SA 00411/2:4+4122 X(+1)
K
and
K
SB
1
Σ
1 Xe41 x).
K
Note that the update rule in (Q-GenX) implies:
SB = (Y,
- X)
(Y, N+l1 Yo41, X,+1 - xx +
n+l1 R Ye41 - 1241,X441 - -x)
7a
1
(wee - M441 X x}+ ( (--- ---
(-
1
(77011 X)
76
7441
71
1 (1-21 2)
(Xt - X(+1, X - XX +
(-Xe-1, -X).
n
7+11 m
By algebraic manipulations, we can further show that
SB = 7 (2) 2 - x1e _ [1 - x1e 2
1X+41-Xell
+ (1) - -) (211i1112 - 2 111x+2112
"11xet1 - x112) -X(13)
711
5 27 |x 1
2 |X++1 xI2
1
_ || X 11:
1
1
||
27
2
2
where the last inequality holds by dropping +
Rearranging the terms in the above expression and substituting Sn, we have
1 27'
1 _
1
1
X,+1
XII <
|x, X11
-|x, X1+1112
|
2
27:
27411
27/
Vk.+1/2 Xe+1 -x)
X
x|
_ ||x - 11+1112+
1
1
|
2%y
24
2
27/e
- (ee1)
1
(10+1//2x(+111 -x.
K
(F22
On the other hand, we have
2
Ve,s X x)
(X, 1411/22141122 X)
K
(F3)
1 1 xI1 - |X+ Xe+1/211 1 11 XI
20

---

Published as a conference paper at ICLR 2023
Substituting X X1+1 and dividing both sides of (F.3) by Yr have
1
1
VK Xx+1/2 - -Xo11 =
||x,
Xx+111.
||x
Xe+1/211
K
27/t
2%
(F.4)
1
|xx+1/2 -x++1l22.
2%
Combining (F.2) and (F.4), we have
K
V XL-1/2- x) s
_1
1
XII -I1
1
| xII?
1
)1
1
27
27e+1
2
27x²"
K
+
V1,0-1/2
Dhies Xx+1/2 - X1+1)
K
k=1
||X,
X1+1/211
|| X2+1/21l..
2/x
2n'
Summing the above for L 1,..., T and telescoping, have
T
K
V4,41/22 X241/2
X)
||
xII
|r+1
x11
271 1|
K
2711
27T+1
2yr++
T
+
Vi.+2/2
Vale X X(+1)
1
1|
X,-1/21/
X,
|8et1 - X041/2ll..
27
27
Substituting X1 =0, 0. we have
K
T
Mee11/2,e41112
x)
1
|
+
Va.41/22 Vh,e Xe41/2 Xeti)
K
2yT+1
K
T
T
||
X,-1/2
X
|X X.-1/211
2
2
(F.5)
By applying Cauchy-Sehwarz and triangle inequalities, we have
K
Va V - Va.,, X,+1/2 - Xe41) s
Σ
Verll-ll (Ne11/2 X441)l..
(E6)
K
1=1
Furthermore, since ab < - K2 b2 have
2za
K
T
K
Vast1/2 Velr Xe41/2 - X(+1) 5
7t
1VV.e41/2- Ve.e)12
K
2K²
k=
(F.7
| Xe+111..
2%
Substituting (F.7) into (F.5) and applying the convexity of || the proof.
I2 we obtain (F.I), which completes
"The substitution X; is just for notation simplicity and can be relaxed at the expense of obtaining slightly more complicated expression.
21

---

Published as a conference paper at ICLR 2023
The following lemmas show how additional noise due compression affects the upper bounds under absolute noise and relative noise models in Assumptions 2 and 3, respectively. Let qe ~ Po represent d variables sampled i..d. for random quantization in Definition 1. We remind that qe is independent of the random sample w ~ IP in Eq. (2.1). We consider a general unbiased and normalized compression scheme, which has a bounded variance as in Theorem and bound on the expected number of communication bits to encode Qe(v), i.e., the output of CODE o Q introduced in Section 3.2, which satisfies Theorem 2. Then we have:
Lemma 4 (Unbiased compression under absolute noise). Let x E Rdd and u ~ P. Suppose the oracle (xx:w)) satisfies Assumption 2. Suppose Qe satisfies Theorems I and 2. Then the compressed Qe (x( satisfies Assumption 2 with
E [[(Qe(((;;)) - A(x)112 S <EQM² +0².
(F.8)
Furthermore, the number of bits to encode (x((x)))) is bounded by the upper bound in (4.2).
Proof. The almost sure boudedness and unbiasedness are immediately followed by the construction of the unbiased Qe. In particular, we note that the maximum additional norm when compressing Qe(g(x:w) w)) happens when all normalized coordinates of g(x:w), w), which we call them ui .1...., Ud are mapped to the upper level (w)=-1 in Definition 1. The additional norm multiplier is bounded
by Ei (lr(1)) - u;)² S Σー upper bound is constant. The final property also holds as follows:
== ug = 1. Then we have Qe(g(x; w)) I 2M a.s., so the additional
Eq, [1[Qe(((x:)) A(x) [ Eg [l(Qe(((x:))) g(x; w) - A(x)1
En [1(ee((x;:))) (12 +E [[)((x))]
I cQ [llg(x; [13] +
I c2 o²
where the second step holds due to unbiasedness of qe and the last inequality holds since w)(x: S M a.s.
Lemma 5 (Unbiased compression under relative noise). Let x E Rd and w ~ P. Suppose the oracle (x): satisfies Assumption 3. Suppose Qe satisfies Theorems I and 2. Then the compressed
w)) satisfies Assumption 3 with
E [[)]e(((;w))) - [xx S Furthermore, the number of bits to encode (g(xxx:)) w)) is bounded by the upper bound in (4.2).
(F.9
Proof. The almost sure boudedness and unbiasedness are immediately followed by the construction of the unbiased Qe. The final property also holds as follows:
Eay [[(Qe(((xw)) - A(x) b
= Eq [IQe(((x;))) g(x: + E. [I]U(x:W)
I BwE [[lg(x; w) W|l + Ax]] 11
Bv [IU(x;w) A || +c||A(x)11 12
cq (Ew [|| w) 1) + || + cl|A(x))
I (eo(c + 1) + c) A(x)
where the first and fourth steps hold due to unbiasedness of qe and the noise model, respectively.
We now prove our main theorme:
Theorem 5 (Q-GenX under absolute noise). Let C C Rdd denote compuct neighborhood of solution for (VI) and let D² == supxec ||X - Xool2. Suppose that the oracle and the problem (VI) satisfy Assumptions and 2, respectively, Algorithm is executed for T iterations on K processors with an adaptive step-size 7t = -(11 + Σ Ek [V, - V2.+1/211?>> 2-1//2 and quantization levels are updated J times where E with variance bound EQ.i in (4.1) and code-length bound Nq.
(4.2) is used for T7 iterations with E T, =T. Then we have
-0
= (E'NVi9 VEq. T/MTM + +
E Gape C
Σ
X X
VTK
22

---

Published as a conference paper at ICLR 2023
In addition, Algorithm requires each processor send most 7े E/= TyNq.s communication bits per iteration in expectation.
In the following, prove the results using the template inequality Proposition and noise anslysis in Lemma 4.
As preliminary step, we prove this proposition for adaptive step-size with non-adaptive Qr. which satisfies Theorem 1.
Proposition 4 (Algorithm I under absolute noise and fixed compression scheme). Under the setup
described in Theorem with an adaptive step-size "tt K (1 + Ek VVV VR,5+1/211* -2.+1/22133-1// and non-adaptive Qe satisfying Theorem I, we have
G T t=1
1
T Σ
=0 -0
(VEqM - + t0)D²
E
Gapc
VTK
Proof. Suppose that we do not apply compression, ie., EQ = 0. By the template inequality Proposi- tion 3, we have
|
K VV Ve,el1?. (F.10)
Σ
X - x) -
27T+1
2K
11.
Let denote the LHS and RHS of (F.10 by SA = ET=
E
X x) and
SB = 2 and monotonicity of operator A, we have
2 +
1
> Ek= [IV - Vr,el1 respectively. Then, by the noise model (2.1)
2
K
T
K
SA= =
Σ
((Xx41/2).
x)
X x)
K
K
t=1
k=1
1=1
k=1
K
K
2 Σ
X111//
X -x)
T K
T
K
= Σ
X)+ -T112
Σ
1
X -x)
K
K
where A = A for k E [K]. Therefore, by rearranging the terms Eq. (F.10) using above inequality,
we have
K
T
K
T
(Xx
(1441/2,X441/2 -X
K
(F.11)
|| 11
V4.++122 Vaeel..
2YT+1
2K²
By taking supermom on both sides of Eq. (F.11), dividing by T. and taking expectation, we have
E
sup Sup
(Ax
X7-1/2 - x)] < (s: S2 + +S)
(F.12)
where
S = E
S2
E
ΣT 7: E II 1 V2.c113.. and S3 = -x
2x7+1
2
supx Σtn ( 2k=1 Uk.41122 X141/2
We now bound S,, S2. and Sa from above,
23

---

Published as a conference paper at ICLR 2023
individually. For S1, we have
D
S = E
2/1+1
D
T K
E
+
Vi.. 11,4+1/2112
2K
1=
1=1
D
1
E
[I
V2,1+/22|2
(F.13)
2K
k=1
D
Σ 2(B
EIIV 14 1//2 122
2K
D
$ 2K
11 + 4KTo2.
We also have
K
Sa
R
2K
7t
VV,441/2- v..
(=1
k=1
T
K
741
V2.e41/2 - V2,
+
7
1V Va.ell
K
K2
2
K2
S 2E
Σ
7t
7++1 K2
Ko²
+ 1 E
Ye+1
||
De,ell?
K2
K2
200 +
1
E
Σ
ΣK
VK.e+1/22
Vi
2K
ΣJ ΣK [|
1
K
2000
Vk,el13
2K
K
20
+
1
1+
[ineet122 - V1,
2K
1
$ 20 +
V
4
2K
(F.14)
Finally note that
S3
E
sup
U Uk/41/2 X X)
(F.15)
T
K
K
= E
sup
Uk.411/2
X)
- E
sup [=1
Uk Xe41/2)
K
1=1
k=1
We bound the first term in the RHS of (F.15) using the following known lemma:
Lemma (Bach & Levy 2019). Let Tud be convex set and : C -> T. be a 1-strongly convex w.E.f. a norm Ill. Assume that h(x) minxec h(x) < D2 D2/2 for all x E C. Then, for any martingle
difference (Z.)
T R.d and any x C, we have
D 2
E
2z
Σ
[ z 12).
24

---

Published as a conference paper at ICLR 2023
Using Lemma 6, the first term in the RHS of (F.15) is bounded by
D
sup
1/2-
E
|0x,+1/21
2K
(F.16)
D'oVT
2vK
Similarly, can bound the second term in the RHS of (F.15). Combining the results in Eq. (F.13), Eq. (F.14), and Eq. (F.16) and applying Lemma 4, we obtain the upper bound Proposition
Applying Proposition 4 with the scaled step size schedule in Theorem 3, we complete the proof for an adaptive compression scheme along the lines of (Faghri et al., 2020, Theorem 4).
G PROOF OF THEOREM 4 (Q-GENX UNDER RELATIVE NOISE)
We first remind the theorem statement:
Theorem 6 (Q-GenX under relative noise). Let C Rdd denote compact neighborhood of solution for (VI) and let D) supxec || Xoll2. Suppose that the oracle and the problem (VI) satisfy Assumptions 1, 3, and 4, Algorithm 1 is executed for 'I' iterations on K processors with an adaptive step-size = ((1 + Ei=1 Vi=-E Ekm [|Ve, - 1/,2+1/2113)-11 and quantization levels are updated J times where l with variance bound EQ. in (4.1) and code-length bound NQ.; in (4.2) is used for T; iterations with Ej=1 T3 = T. Then we have
E Gapc
(
E x =0
I
( ([ Ej=1
=0
((e ((e+1)
T
KT
In addition, Algorithm requires each processor to send at most bits per iteration in expectation.
2 T E TyNq.s communication
Suppose that we do not apply compression, i.e., <Q 0. We first remind the template inequality in (F.1), which holds for any 7/t and noise model:
1
x)
-
7
2
2K
T
Xe
X X1-1/211.
2 (=1
In the following proposition, we show that under "e and relative noise model in Theorem 4, En E || + [|A(,)) is summable in the sense that E B[11((x++1a)]l
||A(X,) [2] (1//T)).
Proposition 5 (Sum operator output under relative noise). Let X denote solution of (VI). Under the setup described in Theorem 4, we have:
E [[|A((X+1/2)]] [|A(X)1
S
(G.1)
2
25

---

Published as a conference paper at ICLR 2023
Proof. Substituting X X* into B Ek=1 1,.4112,xx-11 x)] and applying the law of
total expectation, we have:
K
K /4441/2:4441// - (1011/2xx)]0
x+)
E E(V441//1X411/2 x X [
=
K
K
[Ax(X++1/2)) X1-1/2 x*)
E
K
k=1
(G.2)
E
12) x-)
E
(A(X++1/2) - A(X*), Xx+1// x*1
where the fourth and fifth inequalities hold due to the definition of the monotone operator Eq. (VI)
and B-cocoecivity in Eq. (4.3), respectively.
Applying the lower bound in Eq. (G.2) into Eq. (F.1), obtain:
X
1
K
3B(IA(((++122)
E
V - V2,111
27T+1
2K
t=l
k=
(G.3)
T
1
|
X141/211
7t
Moreover, by lower bounding (LHS) of the above:
[[|
Σ
BLLK
|AAX
(G.4)
1=1
1=1
1 1444//2113
(G.5)
with the second inequality being obtained by the relative noise condition. On the other hand, applying A(Xx+1/2)11
and B-cocoecivity in Eq. (4.3) imply 1 2 (()))(()))) It follows that:
T
BI|A(X,+1//)) 11/2 +
Σ
XX
XX+11/2112
2
7t
T
T
82
81IA(X
||(())) A(X++1/2)1
1=1
T
T
8²
E
311A(X
+
Σ
[|A(X,) - A(X
A(X++1/2)1
2
7t
1=1
1
min
B,
82
E
|A(xx+1/2211 [|A(X.) A(x++122)1
(G.6)
7
82
min
B,
[1(()))11
7/0
82
T
min
B,
1/ K
Σ
|A(X))
2
A
1
min
{3.
82
T
E
K
2c
70
t=1
1=1
26

---

Published as a conference paper at ICLR 2023
where the last inequality holds due to the relative noise condition. Combining the above inequalities we get the following:
T
K
|
T
K
122
E
+
%
V24+1/2
-
(G.7)
2yr+1
2K
=
and
1
min {
B2 E
Σ
T
1/K
K
I [2]
S
B
X
1
T
K
1 1k,,
2c
70
2
2K
1=1
km
1=1
kml
(G.8)
Therefore, by adding the above inequalities we get:
8
B
B
K
Σ
VIVe 1/21:11 + min {B.
1
82
T
E
1/K K
12
2c
70
-=1
k=
1=1
Rm
(G.9)
K -
S
2E
V -
2Y1+1
2K
1=1
We now establish an upper bound on the R.H.S. of Eq. (G.9). We first note that:
V 1,/+1/2 Va.el13]
2
T
K (Tt 7411) Σ
T
K
E
Vk.+1122 - Vn +
Σ
|Va.44122 - Va,.11a]
2K
2K2
k=1
tm
k=1
E
2K
(4M²)
(Th
7+11)
+ 2K
Tt+
VVR,42/22
VeL
1=1
1=1
R=1
22
T
K
S E
71
7++1
| 12,++1/2
11.
K
2K
T
K
<
E
22M
2K
7(+1
|| Mi,e+1/2 Vh.el1
t=1
K
2M
|V,,4+122
Vr.e113]
7T+1
(G.10)
Therefore, an upper bound on the R.H.S. of Eq. (G.9) is given by
8
E
K
[V.411221 +
1
min {g.
g2
Σ
T
<
R
X +
2c
70
YT+1
k=1
(G.11)
To establish lower bound on the L.H.S. of Eq. (G.9), we first note that:
K
T
K
1
E
V Va.el
=
1
K2
K2
t=1
(G.12)
K2
T++1
27

---

Published as a conference paper at ICLR 2023
We also note that:
82
T
min
{3,
[1|KK
Σ
| VR,441/2 - vk,+
4c
(G.13)
B
B
B1/K K
+
min
{B.
8
Σ
T
IE
1/
K
2c
2c
70
1=1
t=1
1=1
Hence, combining, Eqs. (G.11)((G.13,, we can find an upper bound on E
73
K
min {3,
,3
E
1
1|
E
4c
70
T++1
7T+1
[||X*1|2 + 1]B(
TT
$ ||| + 1|
77
with the last inequality being obtained by Jensen's inequality. So we have
4c
max
(G.14)
7T+
K
3
B2
Similar to the proof of Theorem have
sup(A(X),
xx)]
1
(S S2 + Sa)
(G.15)
x
T
where
S
E
2+7+1
D2
S2
E
2K
1
-==1 To.
Σk 11 Pa..12]. and S3 =
E
sup
ΣT
K
UK X -x+11/2)
By (G. we have
K Pk.ll? S E
E
(G.16)
2K2 (=1
7T+1
k=
We decompose S3 into two terms S3
EE supx ΣT=
(
E Uk441/2/
E ET EK 1/,441/2,
Let the supremum on the first terms is attained by X XO. We can also establish an upper bound on the first term using Lemma 6:
28

---

Published as a conference paper at ICLR 2023
T
K
K
E
sup
U X)
R.
U UK,+1/2;
K
K
1)2
K
E
U 12,441/2112
2K
k=1
(G.17)
D
cll c|IA(XX+1/2211
2vK
1
X 1
c
2vK
2
where the last inequality holds by Proposition 5. Finally, by the law of total expectation, we have:
T
K
T K
E
Uk.41122 (411/2) =
B[U,,,41/2 (x41/2))X = (G.18)
Substituting Eq. (G.14), Eq. (G.17), and Eq. (G.18) into Eq. (G.15), we have
ElGape XT+1/21 o { (
D 1
(G.19)
Following similar analysis as in Proposition 4 and applying Lemma 5 with the scaled step size schedule in Theorem we complete the proof for an adaptive compression scheme along the lines of (Faghri et al., 2020, Theorem 4).
H EXPERIMENTAL DETAILS AND ADDITIONAL EXPERIMENTS
In order to validate our theoretical results, we build on the code base of Gidel et (2019) and run an instantiation of Q-GenX obtained by combining ExtraAdam with the compression offered by the barch_ogx pytorch extension Markov et al. (2022), and train a WGAN-GP (Arjovsky et al., 2017) CIFARIO (Krizhevsky, 2009).
Since torch_egx uses OpenMPI (Gabriel et al., 2004) as its communication backend, we use OpenMPI the communication backend for the full gradient well for fairer comparison. We deliberately do not tune any hyperparameters to fit the larger batchsize since simliar to (Gidel et al., 2019), do not claim set theory holds up in practice and can potentially lead to improvements. For this, we present a basic experiment showing that even for very small problem size and heuristic base compression method of cgx, we can achieve a noticeable speedup of around 8%. We expect further gains to be achievable for larger problems and more advanced compression methods. Given differences in terms of settings and the lack of any code, let alone an efficient implementations that can be used in real-world setting (i.e. CUDA kernels integrated with networking). difficult impossible conduct fair comparison with Beznosikov et al. (2021).
SOTA with these experiments but simply want to show that
We follow exactly the setup of (Gidel et al., 2019) except that we share an effective batch size of 1024 across nodes (strong scaling) connected via Ethernet, and use Layernorm (Ba et al., 2016) instead of Batchnorm (loffe & Szegedy, 2015) since Batchnorm is known to be challenging to work with in distributed training as well as interacting badly with the WGAN-GP penalty. The results are shown in Fig. 2a, showing evolution of FID and Fig. 2b showing the accumulated total time spent backpropagating. We note that we do not scale the learning rate any other hyperparameters to account for these two changes so this experiment is not meant to claim SOTA performance, merely to illustrate that
29

---

Published as a conference paper at ICLR 2023
50000
FP 32
400
350
F9 32
40000
UQ bit
UQ 0 bit
Total time (5)
300
30000
250
100
50
3000
4000
5000
updates
Generator updates
(b) Total time spent on backpropagation and gradient exchanges
(a) FID evolution during training
Figure 2: Comparing full gradient ExtraAdam with a simple instantiation of QGenX. FID stands for Frechet inception distance, which is a standard GAN quality metric introduced in (Heusel et al., 2017).
UDB
12
time (s)
Time per (5)
10
GenBP
DiscBP
PenBP
Total
Mode
UQ4
2.99
7,40
1.59
12.96
UQ8
2.99
7.65
1.69
13.29
FP32
3.00
8.36
1.69
14.05
CorBP
DiscBP
PerBP
Total
Figure 3: Fine grained comparison of average backward () times generator, discriminator, gradient penalty well total training time. The .backward function where pytorch DDP handles gradient exchange
30

---

Published as a conference paper at ICLR 2023
Figure 4: Comparing Q-GenX with QSGDA
QSGDA 8 bit
500
Q-GenX bit
400
FID
300
hmmwl Aul,, p onh yom
mm Mh wwwn
200
100
0
1000
3000 Generator updates
2000
4000 5000
1. Even with the simplest possible unbiased quantization on a relatively small-scale setup, we can observe speedup (about 10%).
2. This speedup does not drastically change the performance.
We compare training using the full gradient of 32 bit (FP32) training with gradients compressed to 8 (UQ8) and 4 bits (UQ4) using a bucket size of 1024. Figure 3 shows more fine grained breakdown of the time used for back propagation (BP) where the network activity takes place. GenBP, DiscBP and PenBP refer to the backpropagation for generator, discriminator and the calculation of the gradient penalty, respectively. Total refers to the sum of these times.
We used Weights and Biases (Biewald, 2020) for all experiment tracking. Our time measurements performed with pythons time. i () function which has microsecond precision Linux, measuring only backward propagation times and total training time, excluding plotting, logging etc. The experiments were performed on Nvidia V100 GPUs per node) using Kubernetes cluster and an image built on the torch_egr _ex Docker image.
H.1 COMPARISON WITH QSGDA
Figure 4 compares Q-GenX with QSGDA of Beznosikov et al. (2022), the only method without explicit variance reduction. Due to the extra-gradient template, Q-GenX is able to make steady progress without variance reduction.
TRADE-OFF BETWEEN NUMBER OF ITERATIONS AND TIME PER ITERATION
In this section, build our theoretical results in Theorems 3 and 4 to capture the trade-off between the number of iterations to converge and time per iteration, which includes total time required to update model each GPU.
31

---

Published as a conference paper at ICLR 2023
Using the results of Theorems 3 and 4, we can obtain the minimum number of iterations required to guarantee an expected gap of e, which is a measure of solution quality. In particular, under absolute noise model and average gradient variance bound EQ = -i= Tequ/T, the minimum number of iterations guarantee expected gap of e is T(e, EQ) = (Eq - Now suppose that the time per iteration, which includes overall computation, encoding, and communication times to compute, compress, send, receive, decompress and update one iteration, is denoted by A. Decreasing the number of communication bits, i.c., compressing more aggressively increases the sufficient number of iterations T'(e, EQ) and decreases time per iteration, A, due to communication savings, which captures the trade-off. Theoretically, the best compression method is the one with the minimum overall wall-clock time bounded by T(c, (Q) The exact optimal point depends on the specific problem to solve (dataset, loss, etc.) and the hyperparameters chosen (architecture, number of bits, etc.), which together determine Eq and the implementation details of the algorithm, networking, and compression, along with the cluster setup and hyperparameters, which together influence A. We defer more refined analysis of the optimal point to future work.
J EXAMPLES MOTIVATING ASSUMPTION 3
In this section, we provide some popular examples which motivate Assumption 3:
Example J.1 (Random coordinate descent (RCD)). Consider a smooth convex function f over Ed. At iteration t, the RCD algorithm draws one coordinate is E [d] uniformly at random and computes the partial derivative U4,2 = 0f/00l /Or.. Subsequently, the i-th derivative is updated as X1,+11 X d- a . Ui,t where a > denotes the step-size.
This update rule can be written in an abstract recursive form as x = x =x-ag(x;11 (4) where 9: (x::)u) d- Of /0r y and j drawn uniformly at random from the set of basis vectors fci....,ca. ca) C Rd. We note that Elyg [i]] (x()). Furthermore, since 0 /0ar; 0 at the minima of f. we also have /(x";/² = 0 x* is minimizer of J, ie., the variance of the random vector g(x: j)) vanishes at the minima of f. It is not difficult to show that (x; /4) [ O(I [z)) which satisfies Assumption with A = Vf.
Example J.2 (Random player updating). Consider an N --player convex game with loss functions fi. i E [N]. Suppose, at each stage, player is selected with probability p. to play an action following its individual gradient descent rule X Xx,, ///p, Vi, where V,, V ViJ((X,) denotes player i's individual gradient at the state X; = (X1,t1-., Nx,e) and p; is included for scaling reasons.
Note that [[Vi] = A(X,) where Ax(x) = V.fi(z) for i E [N]. It is not difficult to show that V, is an unbiased oracle for A, and since all individual components of A vanish at the game's 's Nash equilibria, is also straightforward to verify that V2 satisfies Assumption 3.
K ENCODING
To further reduce communication costs, we can apply information-thhorrrtiallyy inspired coding schemes on top of quantization. In this section, we provide an overview of our coding schemes along the lines of (Alistarh et al., 2017; Faghri et al., 2020: Beinezani-Kebbree We first note that a vector v E IRd can be uniquely represented by a tuple (llvllg: s, u) where || is the L norm of v, s := (sgn(v1)..... s.g...,,,gn((u. = [u....., ua]" with u; = |esl/ llvll are the normalized coordinates. Note that 0 < u; S 1 for all i E [d]. We define a random quantization function as follows:
al., 2021). Let q Z4.
consists of signs of the coordinates v; ss and
Definition 2 (Random quantization function). Let E 24 denote the number of quantization levels. Let u E [0, 1] and e = ..p....,.+)) denote a sequence of s quantization levels with 0 = to < < < lg lo+1 1. Let (u) denote the index of level such that (r(u) S (r(w)+1 Let E(u) (u ((())) ) (E- (-()) be the relative distance of u to level ((u)+ + We define the random function qe(u) [0 (lo....,ett) } such that ge(u) = Er(u) with probability 1 E(u)
and qe(u) ((())1 with probubility E(u). Let q E E. and v IRd. We define the random quantization of v as follows:
Qe(v) == Ivll,, S (ge(u)), .... ge(ua)]
where S denotes the element-wise ToaeiieeeHaammmaa (Hadamard) product.
32

---

Published as a conference paper at ICLR 2023
We note that qe (ge(us)) are independent random variables. The encoding CODE Q[llvll. s, R+ x {=1]2 {lo..... Lo+1 1ad + {0, uses a standard floating point encoding with C, bits to represent the positive scalar [|v|lg, encodes the sign of each coordinate with one bit, and finally applies integer encoding scheme V/
f1.....;,++1] + (0, 1)" ef- ficiently encode each quantized normalized coordinate qe qe(u;) with the minimum expected code-length. Depending on how much knowledge of the distribution of the discrete alphabet of levels is known, a particular lossless prefix code can be used to encode qe- In particular, if the distribution of the frequency of the discrete alphabet { f1.......... (e+1) is unknown but it is known that smaller values are more frequent than larger values. Elias recursive coding (ERC) can be used (Elias, 1975). ERC a universal lossless integer coding scheme with a recursive and efficient encoding and decoding schemes, which assigns shorter codes to smaller values. If the distribution of the frequency of the discrete alphabet (lo: f (x+1) } known or can be estimated efficiently, we use Huffman coding, which has an efficient encoding/decoding scheme and achieves the minimum expected code-length among methods encoding symbols separately (Cover & Thomas, 2006).
The decoding DEQ CODE: 10, + Rd in Algorithm first reads C. bits to reconstruct ||v|l Then it applies V {0, 1 - {4o, fi....,,ee L to decode the index of the first coordinate, depending on whether the decoded entry is zero or nonzero, it may read one bit indicating the sign, and then proceeds to decode its value. It then decodes the next symbol. The decoding continues mimicking the encoding scheme and finishes when all quantized coordinates are decoded. Note that the decoding will fully recover Qe(v) because the coding scheme is lossless. One may slightly improve the coding efficiency in terms of the expected code-length by encoding blocks of symbols at the cost of increasing encoding/decoding complexity. We focus lossless prefix coding schemes, which encode symbols separately due to their encoding/decooding simplicity (Cover & Thomas, 2006).
To implement efficient Huffman code, we need to estimate probabilities w.r.t. the symbols in our discrete alphabet {lo, f..... fs+1). This discrete distribution can be estimated by properly estimating the marginal probability density function (PDF) of normalized coordinates along the lines of e.g., (Faghri et al., 2020, Proposition 6).
Given quantization levels l and the marginal PDF of normalized coordinates, K processors can construct the Huffman tree in parallel. A Huffman tree of a source with 8 + 2 symbols can be constructed in time (s)) through sorting the symbols by the associated probabilities. It well-known that Huffman codes minimize the expected code-length:
Theorem 7 (Cover & Thomas 2006, Theorems 5.4.1 and 5.8.1). Let 7 denote a random source with discrete alphabet Z. The expected code-length of an optimal prefix code compress 7 is bounded by HtZ) - ]|L]= < (Z) + 1 where H (Z) S logo (1z) is the entropy of Z in bits.
33


Reviews:
[{"review_id": "TYS9Cm23Urb", "reviewer": "Reviewer_Qv34", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper focuses on co-coercive variational inequalities and proposes a quantized generalized extra-gradient (Q-GenX) for solving these problems in multi-GPU settings where multiple processors/workers/clients have access to local stochastic dual vectors. In terms of theory, the paper proves $O(1/T)$ convergence of Q-GenX under relative noise and $O(1/\\sqrt{T})$ under absolute noise. ", "summary_of_the_review": "As I mentioned in my review the idea of the paper is interesting. However, there are many issues in terms of presentation and numerical evaluation. \n\nIn my opinion, a fair score for the current version of the paper is \"3: reject, not good enough\" or \"5: marginally below the acceptance threshold\". \n\nAt this point, I give a score of 5 to this work. ", "strength_and_weaknesses": "The paper has interesting results, however, it has several issues in terms of presentation that do not allow me to suggest acceptance at this stage. Let me provide more details below. \n\n1. The paper claims that it solves general monotone problems while truly focusing on a much smaller class of VIPs for which the analysis is typically much easier. This is the class of co-coercive VIPs. \n\n2. On top of the co-coercivity condition, the authors mentioned \"Moreover, in order to avoid trivialities, we make the following mild assumption\" to refer to assumption 1. However, Assumption 1 assumes that the problem has a unique solution as well. Thus it is far from general monotone or even general co-coercive. \n\n3. In the expression of the co-coercive condition the dual norm is used without further explanation. Note that the standard co-coercivity holds for euclidean norms. \n\n4. For co-coercive problems assuming bounded variance, bounded noise or relative noise (growth condition) are unnecessary and quite strong assumptions. Please check the results of paper [1] where these conditions have not been used. \nThe authors spend half a page providing examples where Ass. 2 and 3 are satisfied which is good for pedagogical reasons but the examples are standard for anyone familiar with noise assumptions in stochastic algorithms. This space could have been used for the numerical experiment (which is not part of the main paper)\n\n5. Proposition 1 is a well-known result. As presented now it gives the impression that this is a contribution of the authors. The authors mention: \"Mathematically speaking, we have the following proposition:\" \n\n6. Presentation of Section 3 is confusing as it involves quantities that appear later in the paper. What is $Q_{\\ell_t}$ what is $V_{k,t}$, etc. A good idea for clarity will be to introduce a notation paragraph at the beginning of that section 3. Note that definition 1 only appears in section 3.2 while it should have been presented before section 3.1\n\n7. In section 4 a proof sketch is provided in the main paper which takes half a page. This space could have been used for the experiments which as it is mentioned in several parts of this work is one of its main contributions. At the moment there are no experiments in the main paper. \n\n8. Main Issue: \nEven if one checks the experiments in the appendix (not a requirement for the reviewer) the paper has no comparison with closely related works that use compression on top of distributed algorithms for solving VIPs. The authors mentioned the works of Beznosikov et al. (2021); Kovalev et al. (2022) and say that they are concurrent works. This is not true. Beznosikov et al. (2021) for example, is 1-year-old paper. \n\nIn the numerical evaluation, a proper comparison with algorithms from the above papers should be presented. \n\nA highly related paper, that also focuses on co-coercive VIPs, and to the best of my knowledge has state-of-the-art performance in terms of distributed methods with compressors for VIPs is paper [2]. This is also non-concurrent work as it appears some time ago. A formal comparison with the distributed methods with compressed communications presented in that work is highly recommended.  \n\nMissing references:\n\n[1] Loizou, Nicolas, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. \"Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity.\" Advances in Neural Information Processing Systems 34 (2021): 19095-19108.\n\n[2] Beznosikov, Aleksandr, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. \"Stochastic gradient descent-ascent: Unified theory and new efficient methods.\" arXiv preprint arXiv:2202.07262 (2022).", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NR4-CcFim0", "reviewer": "Reviewer_PUDg", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This work studies distributed (synchronous) algorithms for monotone variational\ninequality (VI) optimization, generalizing convex minimization, saddle-point\nproblems, and games. Specifically, it proposes a quantized, general\nextra-gradient framework called \"Q-GenX\" that unifies previous methods.  This\napproach uses unbiased and adaptive compression techniques for communicating\nlocal stochastic gradients, and it uses an adaptive learning rate rule for\nwhich the authors prove convergence guarantees: $O(1/T)$ under relative nosie\nand $O(1/\\sqrt{T})$ in the presence of absolute noise. For this VI problem,\nthey show that increasing the number of processes can accelerate convergence.\nLastly, they train GANs on multiple GPUs in the appendix to support their\ntheoretical results.\n\n", "summary_of_the_review": "This work is polished and well-organized, but the comparison to prior works and\nexperiments to support the Q-GenX algorithm seem to be lacking. The algorithm\nis clean and practical, and come with strong theoretical guarantees. This paper\ncould be accepted to ICLR, but it would benefit from addressing the weaknesses\npointed out above.", "strength_and_weaknesses": "**Strengths:**\n- This paper is very well written and provides a comprehensive survey of\n  related works.\n- The Q-GenX algorithm is indeed practical, and the authors provide strong\n  theoretical guarantees about its performance.\n\n**Weaknesses:**\n- The exact contributions of this work over previous methods (aside from the\n  unification aspect) should be made more clear. The discussion after Theorem 5\n  talks about more processors leading to faster convergence, but how does this\n  convergence rate compare to existing methods for different slices of the VI\n  problem (e.g., convex, saddle-points)?\n- Given the nature of this paper, there should be some experiments in the main\n  body. Some GAN experiments are discussed in Appendix H, but it seems\n  incomplete.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "D0T8rICacm_", "reviewer": "Reviewer_4SD9", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper considers a monotone variational inequality to be solved in a Federated learning setup, with a central server and multiple clients. They develop a version of the extra gradient (EG) algorithm in this setting where the bottleneck is the communication: In their algorithm, communications between the central server and the clients are compressed.\n\nThe resulting algorithm is a version of EG with compression and they show convergence rates in terms of the restricted gap function under different assumptions on the noise in the stochastic \"gradient\". The stronger assumption on the noise ensures zero noise at the optimum and therefore recover the deterministic rate of EG. Besides, the authors compute the communication cost and show reduction in number of bits communicated at each round.", "summary_of_the_review": "A solid work that considers an idealized setting (monotonicity) but provides precise and competitive guarantees for both the computation complexity and the communication complexity of the proposed algorithm.", "strength_and_weaknesses": "Strength\n\n- The compression part of the paper is precise and specific. The compression operators are described and the number of bits communicating is computed. I am not sure, but these calculations seem to be new. So there is also a contribution here, additional to the optimization part (analysis of EG) \n\n- The optimization part (EG algo) seems equally solid. Convergence is in restricted gap and recover the deterministic result as a special case.\n\n-The assumptions on the noise cover several types of stochastic gradients\n\n-The meta algorithm actually covers several algorithms for monotone VI\n\n\nWeaknesses\n\n-In many applications of ML, monotonicity does not hold (Monotonicity is like convexity). This paper deals only with the monotone case", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "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": {}}]

Author rebuttal:

Decision: Accept: poster