EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization
Authors: Laurent Condat
Kai Yi
Peter Richtárik
Venue: NeurIPS 2022 Accept (2022)
Keywords: distributed optimization
federated learning
communication
compression
randomized algorithm
variance reduction
error feedback

Abstract: In distributed or federated optimization and learning, communication between the different computing units is often the bottleneck and gradient compression is widely used to reduce the number of bits sent within each communication round of iterative methods. There are two classes of compression operators and separate algorithms making use of them. In the case of unbiased random compressors with bounded variance (e.g., rand-k), the DIANA algorithm of Mishchenko et al. (2019), which implements a variance reduction technique for handling the variance introduced by compression, is the current state of the art. In the case of biased and contractive compressors (e.g., top-k), the EF21 algorithm of Richtárik et al. (2021), which instead implements an error-feedback mechanism, is the current state of the art. These two classes of compression schemes and algorithms are distinct, with different analyses and proof techniques. In this paper, we unify them into a single framework and propose a new algorithm, recovering DIANA and EF21 as particular cases. Our general approach works with a new, larger class of compressors, which has two parameters, the bias and the variance, and includes unbiased and biased compressors as particular cases. This allows us to inherit the best of the two worlds: like EF21 and unlike DIANA, biased compressors, like top-k, whose good performance in practice is recognized, can be used. And like DIANA and unlike EF21, independent randomness at the compressors allows to mitigate the effects of compression, with the convergence rate improving when the number of parallel workers is large. This is the first time that an algorithm with all these features is proposed. We prove its linear convergence under certain conditions. Our approach takes a step towards better understanding of two so-far distinct worlds of communication-efficient distributed learning.

EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization
Laurent Condat" KAUST
Kai Yi KAUST
Peter Richtárik
King Abdullah University of Science and Technology (KAUST) Thuwal 23955-6900, Kingdom of Saudi Arabia
Abstract
In distributed federated optimization and learning, communication between the different computing units is often the bottleneck and gradient compression is widely used reduce the number of bits sent within each communication round of iterative methods. There are two classes of compression operators and separate algorithms making use of them. In the case of unbiased random compressors with bounded variance (c.g., rand-k), the DIANA algorithm of Mishchenko et al. (2019), which implements variance reduction technique for handling the variance introduced by compression, is the current state of the art. In the case of biased and contractive compressors (e.g., top-k), the EF21 algorithm Richtárik et al. (202I), which instead implements an error-feedbact mechanism, is the current state the art. These two classes of compression schemes and algorithms are distinct, with different analyses and proof techniques. In this paper, we unify them into single framework and propose a new algorithm, recovering DIANA and EF21 as particular cases. Our general approach works with new, larger class of compressors, which has two parameters, the bias and the variance, and includes unbiased and biased compressors as particular cases. This allows us inherit the best of the two worlds: like EF21 and unlike DIANA, biased compressors, like top-k, whose good performance in practice is recognized, DIANA and unlike EF21, independent randomness at the compressors allows to mitigate the effects of compression, with the convergence rate improving when the number of parallel workers is large. This is the first time that an algorithm with all these features is proposed. We prove its linear convergence under certain conditions. Our approach takes a step towards better understanding of two so-far distinct worlds of communication-efian distributed learning.
be used. And like
Introduction
In the big data the explosion in size and complexity of the data arises in parallel to shift towards distributed computations (Verbraeken et al. 2021). as modern hardware increasingly relies on the power of uniting many parallel units into system. For distributed optimization and learning tasks, specific issues arise, such as decentralized data storage. In the modern paradigm of federated learning (Konečný al.) 2016, McMahan et al.) 2017]] Kairouz et al.) 2021;; Li al., 2020a). potentially huge number of devices, with their owners' data stored on each of them, are involved in the
*Corresponding author. Contact: see hutps:/lcondat.giitubb.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

collaborative process of training global machine learning model. The goal is to exploit the wealth of useful information lying in the heterogeneous data stored across the network of such devices. But users are increasingly sensitive to privacy concerns and prefer their data to never leave their devices. Thus, the devices have to communicate the right amount of information back and forth with distant server, for this distributed learning process to work. Communication, which can be costly and slow, is the main bottleneck in this framework. So, it is of primary importance to devise novel algorithmic strategies, which are efficient in terms of computation and communication complexities. A natural and widely used idea is to make use of (lossy) compression, to reduce the size of the communicated messages (Alistarh al. 2017 Wen et al.) 2017; Wangni et al. 2018 Khaled & Richtárik 2019
Albasyoni et al. 2020 Basu et al. 2020 Dutta et al. 20200 Sattler et al. 2020; Xu et al. (021))
In this paper, we propose a stochastic gradient descent (SGD)-type method for distributed optimization, which uses possibly biased and randomized compression operators. Our algorithm is variance-reduced (Hanzely & Richtárik] [019)] Gorbunov et al. [2020a] Gower et al. (2020); that is, it converges to the exact solution, with fixed stepsizes, without any restrictive assumption on the functions to minimize.
Problem. We consider the convex optimization problem
minimize zERd
Σ RRx)) 1=1
f(x)
where d > is the model dimension; R Rd + R U (+xx) is proper, closed, convex function
(Bauschke & Combettes, 2017), whose proximity operator prox. x + arg min
ye (y -
-11*)) is easy compute, for any 7 > 0 (Parikh & Boyd 2014 Condat et al. 2022a by: n 2 1
the number of functions; each function ft : R2 R is convex and smoothh, for some L; > 0:
that is. ft is differentiable on IR and its gradient ff is Li-Lisschitz continuous: for every x E Rd
and x' Rd. [[) f.(xx)) S Li x'Il.
We set Lmaxx max; Li and L V E. Lg. The average function
π Σm St is L- smooth, for some L S L S Liaax A minimizer of f + R is supposed to exist. For any integer m 2 1, we define the set I'm = -I,...,,m!
Algorithms and Prior Work. Distributed proximal SGD solves the problem ( by iterating x² = -prox, (x' Ex= 9i), where y is a stepsize and the vectors gf are possibly stochastic estimates of the gradients Vf((z"), which are cheap to compute or communicate. Compression is typically performed by the application of a possibly randomized operator C IR - Rdd that is, for any x, C(a) denotes realization of random variable, whose probability distribution depends on Compressors have the property that it is much casier/faster to transfer C(x) than the original message
Ir. This can be achieved in several ways, for instance by sparsifyyng the input vector (Alistarh
ctt al.
2018), or by quantizing its entries (Alistarh et al. 2017| Horváth et al.) 2019 Gandikota
et al.
2019: Mayekar & Tyagi 2021; [aha al.) 2021). ). via combination of these and other approaches (Horváth et al. 2019 Albasyoni et al. 2020 Beznosikov et al., 2020). There are two classes of compression operators often studied in the literature: 1) unbiased compression operators, satisfying a variance bound proportional to the squared norm of the input vector, and 2) biased compression operators, whose square distortion is contractive with respect the squared norm of the input vector; we present these two classes in Sections and 2.2 respectively.
DIANA with unbiased compressors. An important contribution to the field in the recent years is the variance-reduced SGD-type method called DIANA (Mishchenko et al. 2019). which uses unbiased compressors; it is shown in Fig. [ DIANA was analyzed and extended in several ways, including bidirectional compression and acceleration, see, e.g., the work of Horváth et al. (2022); Mishchenko et al. (2020): Condat & Richtárik (2022); Philippenko & Dieuleveut (2020) Li et al. (2020b): Gorbunov et al.] (2020b), and Gorbunov et al. (2020a); Khaled et al. (2020) for general theories about SGD-type methods, including variants using unbiased compression of (stochastic) gradients.
Prior work:
Prior work: Error feedback with biased contractive compressors. Our understanding of dis- tributed optimization using biased compressors is more limited. The key complication comes from

---

Table 1: Desirable properties of a distributed compressed gradient descent algorithm converging to an exact solution of ( and whether they are satisfied by the state-of-the-an algorithms DIANA and EF21 and their currently-knowe known analysis, and the proposed algorithm EF-BV.
DIANA
EF21
EF-BV
handles unbiased compressors in ((w) for any w 2 0
/
handles biased contractive compressors in B a)) for any a E (0.1] handles compressors in C(), w) for any 1/ E (0, 1), w
/
X
52
/
recovers DIANA and EF21 as particular ar cases
X
x
the convergence rate improves when n is large
X
with pre-scaling with < 1, so that C" = XC B(a) is used instead of C
the fact that their naive use within methods like gradient descent can lead to divergence, as widely observed in practice, see also Example 1 of Beznosikov et al. (2020). Error feedback (EF), also called error compensation, techniques were proposed to fix this issue and obtain convergence, initially as heuristies (Seide et al., (014)). Theoretical advances have been made in the recent years in the analysis of EF, see the discussions and references in Richtárik et al. (202I) and Lin et al. (2022). But the question of whether it is possible to obtain a linearly convergent EF method in the general heterogeneous data setting, relying on biased compressors only, was still an open problem; until last year, 2021, when |Richtárik al. (202T) re-engineered the classical EF mechanism and came up with a new algorithm, called EF21. It was then extended in several ways, including by considering server-side compression, and the support of a regularizer in [ by Fatkhullin al. (202 EF21 is shown in Fig.
Motivation and challenge. While EF21 resolved an important theoretical problem in the field of distributed optimization with contractive compression, there are still several open questions. In particular, DIANA with independent random compressors has a J factor in its iteration complexity; that is, it converges faster when the number n of workers is larger. EF21 does not have this property: its convergence rate does not depend on n. Also, the convergence analysis and proof techniques for the two algorithms are different: the linear convergence analysis of DIANA relies on ||== x²12 and ||4 V fi(x"") Il tending zero, where x²' is the estimate of the solution x² at iteration and h is the control variate maintained at node i, whereas the amalysis of EF21 relies on ( H)) (x') (f+ [R) (x*) and || v f=(==)ll tending zero, and under different assumptions. This work aims filling this
gap. That is, we want to address the following open problem:
Is it possible to design an algorithm, which combines the advantages of DIANA and EF21? That is, such that:
a. It deals with unbiased compressors, biased contractive compressors, and possibly even more.
b. It recovers DIANA and EF21 as particular cases.
c. Its convergence rate improves with n large.
Contributions. We answer positively this question and propose a new algorithm, which we name EF-BV, for Error Feedback with Bias- Variance decomposition, which for the first time satisfies the three aforementioned properties. This is illustrated in Tab. [ More precisely, our contributions are:
1. We propose new, larger class of compressors, which includes unbiased and biased contrac- tive compressors as particular cases, and has two parameters, the bias and the variance w. third parameter Way describes the resulting variance from the parallel compressors after aggregation, and is key to getting faster convergence with large n., by allowing larger stepsizes than in EF21 in our framework.
2. We propose a new algorithm, named EF-BV, which exploits the properties of the compressors in the new class using two scaling parameters and v. For particular values À and v, EF21 and DIANA are recovered particular cases. But by setting the values of X and optimally with respect to 1), w, Way in EF-BV, faster convergence can be obtained.
3. We prove linear convergence of EF-BV under a which is weaker than strong convexity of + R. Even for EF21 and DIANA, this is new
condition of f + R.
3

---

4. We provide new insights on EF21 and DIANA; for instance, we prove linear convergence of DIANA with biased compressors.
2 Compressors and their properties
2.1 Unbiased compressors
For every w introduce the set U(w) of unbiased compressors, which randomized operators of the form C: RR + Rd satisfying
[[C(=)] = and BII[(()) - = w||=|| Væ E R
(2)
where E[.) denotes the expectation. The smaller w, the better, and w = 0 if and only if = Id, the identity operator, which does not compress. We can remark that if C U(w) is deterministic, then = Id. So, unbiased compressors are random ones. A classical unbiased compressor is rand-k, for some k E Ia. which keeps & elements chosen uniformly at random, multiplied by d and sets R.
the other elements to 0. It is easy to see that rand-k belongs to U(w) with w - (eznosikov
al. 2020).
2.2 Biased contractive compressors
For every a E (0, 1]. we introduce the set B(a) of biased contractive compressors, which are possibly randomized operators the form C: _2d + Rdd satisfying
B[l[C(x) - x=|3] < (1-x))1=13
Ex
We the term 'contractive' to reflect the fact that the squared norm in the left hand side of (3) is smaller, in expectation, than the one the right hand side, since - a < 1. This is not the case be arbitrarily large. The larger a, the better, and 1 if and only if C Id. Biased compressors need not be random: a classical biased and deterministic compressor is top-k, for some l E Ia, which keeps the elements with largest absolute values unchanged and sets the other elements to O. It is easy to that top-k belongs to BB(a) with y/2 (Beznosikov et al.
in ( where
2020).
2.3 New general class of compressors
We refer to Beznosikov et al. 2020)) Table in Safaryan et al. (2021). Zhang et al. (2021) Szlendak al. (2022). for examples compressors ((w) or B(a)), and Xu et al. (2020) for a system- oriented survey.
In this work, introduce new, more general class of compressors, ruled by parameters, to allow for a finer characterization of their properties. Indeed, with any compressor C, we can do a bias-variance decomposition of the compression error: for every & E Rd,
[[[[C()) x||3] = [=]] - x + E [|((a) B[]())]]]
bins
variance
Therefore, better characterize the properties of compressors, propose to parameterize these two parts, instead of only their sum: for every [0, 1) and w 2 O, we introduce the new class C(1), w) of possibly random and biased operators, which are randomized operators of the form C Rd + Rd satisfying, for every Rdd, the two properties:
[[C(=) - x n||=|||
(ii - E(C()) < 3
Thus, 17 and w control the relative bias and variance be arbitrarily large, but the compressors will be scaled in order to control the compression error, as we discuss Sect. (2.5). On the other hand, we must have y < since otherwise, no scaling can keep the compressor's discrepancy under control.
compressor, respectively. Note that w can
We have the following properties:

---

1. C17, 0) is the class of deterministic compressors in B(a), with 1 1- = n/2
2. C(O, w) = ((w), for every w 2 In words, its bias 1j is zero, the compressor is unbiased with relative variance w.
3. Because of the biri-veri decomposition if C E ((),w) with 17² + w < 1, then
C E B(a) with
(5)
4. Conversely, ifC E B(a)), one easily sees from that there exist S v1 and S ax such that w()
Thus, the new class C(n, w) generalizes the two previously known classes (ww) and B(a). Actually, for compressors in U(w) and B((x), we can just use DIANA and EF21, and our proposed algorithm EF-BV will stand out when the compressors are neither in U(w) nor in B(a);; that is why the strictly larger class C(1y, w) is needed for our purpose.
We present new compressors in the class C(7,w) in Appendix A
2.4 Average variance of several compressors
Given n compressors C, i E In, we are interested in how they behave in average. Indeed distributed algorithms consist, every iteration, in compressing vectors in parallel, and then averaging them. Thus, we introduce the average relative variance Wav 2 0 of the compressors, such that, for every Iy Rd In.
E
ト
Σ
(c((z,) ((lx))BCCC ((la)-BG((()))
Way 71
10.1?
(6)
When every C; is in C(n,w) for some [0, and w 0, then way but way can be much smaller than w, and we will exploit this property in EF-BV. We can also remark that >i C C(1,, W
E
An important property is the following: if the C, are mutually independent, since the variance of sum of random variables is the sum of their variances, then
Way
There are other cases where the compressors are dependent but wav is much smaller than w. Notably, the following setting can be used to model partial participation of m among n workers at every iteration of a distributed algorithm, for some E In, with the C, defined jointly as follows: for every i In and x; e Rd.
{ ay if iEEE
(a(aa)
10
otherwise
where 52 is a subset of Z, of size m chosen uniformly at random. This is sometimes called m-nice sampling (Richtárik & Takáč 2016 Gower et 2021 Then every C, belongs to U(w), with m- and, as shown for instance in Qian et al. 2019) and Proposition in Condat & Richtárik
2002
is satisfied with
72 m
w (= = m == 1).
Wav
m(n n n-1
2.5 Scaling compressors
A compressor C E C(n. w) does not necessarily belong to BBaa) for any (0, since can be arbitrarily large. Fortunately, the compression error can be kept under control by scaling the compressor, that is, using XC instead of C, for some scaling parameter À 1. We have:
Proposition 1. LerC E C(n, w). for some 7 E (0.1) 1) and w 2 0, and X E (0, 1). Then XC e C(T',w)) with w/ = X2w and n' Xn de (0,
Proof. Let x E Rd. Then E ||]((x) [])(()]] = [[<())) < \WWll=|1 and
[[[[C()]] - =|| s (l[E(((=)) - 2|| (1 |)|| (21 - - >)//=//
5

---

So. scaling deteriorates the bias, with r/ 2 but linearly, whereas it reduces the variance w quadratically. This is key, since the total error factor (1/)2 + w' can be made smaller than by choosing À sufficiently small:
Proposition 2. Let & C(n, for some 1/ E 10, 1) and w 2 O. There exists X E (0, 1] such that AC E B(a)), for some
(1 À + Xn) X2w (0, 1). and the best such X, maximizing a, is
(1 - 1)) + :1
1 1-11 1
X min
Proof. We define the polynomial P + (1 - - 2n) + APw. After Proposition and the discussion in Sect. 2.3] we have to find X E [0 such that P(X) 1. Then AC E B(x)), with 1 a P()). Since P is a strictly convex quadratic function on [0, with value and negative derivative 1) at À = O, its minimum value on [0, 1] is smaller than 1 and is attained at Ar, which either satisfies the first-order condition 0 = (A) = 2(1 77) + 22((11 - r7) + +w), or, if this value larger than 1, is equal to
2 recovers Lemma 8 of Richtárik et al. (202T) according to which, for C E U(w), X E ( w+I with X = - For instance, the scaled rand- - compressor, which keeps elements chosen uniformly at random unchanged and sets the other elements to corresponds to scaling the unbiased rand-k compressor, seen in Sect. 2.1 by À a
In particular, if 17 = O. Proposition
We can remark that scaling is used to mitigate the randomness of a compressor, but cannot be used to reduce its bias: if w 0, X = 1.
Our new algorithm EF-BV will have two scaling parameters: X, to mitigate the compression error in the control variates used for variance reduction, just like above, and v, to mitigate the error in the stochastic gradient estimate, similar way but with w replaced by wav, since we have seen in Sect. 2.4 that Way characterizes the randomness after averaging the outputs of several compressors.
3 Proposed algorithm EF-BV
We propose the algorithm EF-BV, shown in Fig. 1 It makes use of compressors C; E C(n, for some 17 [0. 1) and
0, and introduce Way I such that (6) is satisfied. That is, for any Rdd the (x). for i E: In and t 2 O, are distinct random variables; their laws might be the same or not, but they all lie in the class C(1, Also, (xx) and C₁ (x"), for i + l', independent.
The compressors have the property that their input is the zero vector, the compression error zero, want compress vectors that close to zero, at least converge to zero, to make the method variance-reduced That is why each worker maintains a control variate hý, converging, like V fxx"), to (z())) for some solution x". This way, the difference vectors fx("=) h converge and these are the vectors that are going to compressed. Thus, EF-BV takes the form of Distributed proximal SGD, with
oi = h + vCt (V(((=)) - Mt).
where the scaling parameter v will be used to make the compression error, averaged over i, small; that is, to make g 1 >n of close to f((=)). In parallel, the control variates are updated similarly as
M = h + Xe (V/((=') M)),
where the scaling parameter À is used make the compression error small, individually for each i; that is, to make h(+11 close to fa(t))
3.1
EF21 as particular case of EF-BV
There are two ways to recover EF21 as a particular case of EF-BV:
If the compressors C are in B(a), for some a E (0, 1), there no need for scaling the compressors, and we can use EF-BV with X = = T. Then the variable h in EF-BV becomes redundant with the gradient estimate g6 and we can only keep the latter, which yiclds EF21, shown in Fig.

---

Algorithm EF-BV proposed method
Algorithm 2 EF21
Algorithm DIANA
(Richtárik et al. 2021)
(Mishchenko al. 2019)
Input: nº, .i..... h
ha R
Input:
x., Nr hn E R" -i M1
Input:
x. , hi E B.,
E (0, 11, 11 12 0.
Σ
4
> O.
-== 1m 12 > 0,
P [0.1]
A (0.
for f = 1...... do
for L 0.1..... do
for = 0. l...... do
for ..2...., in paral-
for ..2,...;
: n in paral-
for i 1.2.... .., in paral-
lel do
lel do
Icl do
di = C (Vf((x') - m.) 11
d: C: (V[((x)) - 11) htt1 h +
d: = (V n!)
+ Ad;
h h + Xd
send df to master end for master:
send de to master
send de to master end for at master: d' Σi=1 of
end for master:
n Ei= of d'
d' n - of
6 h² Ad
h h == ht' + df
h = h² + Ad
++ li' + vdle
9 h' + d'
0+1 h' 4 d
= prox (2 60" -19'"t
x +1 = prux, xx
79 +1)
1+ prox x
79 11
broadcast +1 to all workers
broadcast w all workers end for
broadcast
to all workers
end for
end for
Figure I: In the three algorithms, g is an estimate of V / (x²",, the h are control variates converging to (ar"")) and their average h² = Ei= H& is maintained and updated by the master. EF21 is a particular case of EF-BV, when
+1
A and the compressors are in BBaa); then g²+1 is simply equal h+41 for every 2 O. DIANA is particular case of EF-BV, when v 1 and the compressors are in U(w); then g² is an unbiased estimate of Vf(x').
2. If the scaled compressors XC; are in B(a), for some a E (0. and À E (0, 1) (see Proposition 2 one can simply use these scaled compressors in EF21. This is equivalent to using EF-BV with the original compressors C₁₁ the scaling with À taking place inside the algorithm. But we must have v X for this equivalence to hold.
Therefore, we consider thereafter that EF21 corresponds to the particular case of EF-BV with = A E (0. and XC; E B(a),, for some (0, 1]. and is not only the original algorithm shown in Fig. I which has no scaling parameter (but scaling might have been applied beforehand to make the compressors B(ax)).
3.2 DIANA as a particular case of EF-BV
EF-BV with v = 1 yields exactly DIANA, as shown in Fig. DIANA was only studied with unbiased compressors C U(w), for some w > 0. In that case, E [ (x(x), that g is an unbiased stochastic gradient estimate; this is not the case in EF21 and EF-BV, in general. Also, is the usual choice in DIANA, which is consistent with Proposition 2
4 Linear convergence results
We will prove linear convergence of EF-BV under conditions weaker than strong convexity of f + R. When R = O, we will consider the Lojysk--wjssiwiizzzzz (PL) condition f: f is said to satisfy the Pf. condition with constant ya > 0 if, for every x E TRdd, || / [=))| 2 2p([(xx) f*), where f (x+ for any minimizer x= of f. This holds if, for instance, f is ju-strongly convex; that is, f -1- is convex. In the general case, we will consider the Kurdyka-Lojasievits
(KL) condition with exponent 1/2 (Attouch & Bolte 2009 Karimi et al. 2016) on f + R: f + R is said to satisfy the KE, condition with constant μ > if, for every & E R2 and u E aR()).
VV 2 2
-R*),
(7)
where / = [x*) and R = R(x*), for any minimizer x² of f + R. This holds if, for instance, R = 0 and f satisfies the PL condition with constant μ. so that the KL condition generalizes the PL
7

---

condition to the general case R + O. The KL condition also holds if f + R is p--strongly convex (Karimi al. 2016). for which it is sufficient that f j--stronlyy convex, or R pesttongly convex.
In the rest of this section, we assume that Cę E w)), for some E [0, 1) and w 2 0, and we
introduce Way such that O is satisfied. According to the discussion in Sect. 2.5 (see also Remark I [ellow), we define the optimal values for the scaling parameters À and v:
1-
S³ = min (1 11)2 Wax 1)
1-11
X = -imi
7)2 +
Given (0, and E (0, we define for convenience r (1 + Xn)) + X2w, Tav (1 - v + vn) 2 wav, as well s*
2r and 0* == 5 (1 + 8*) /
Note that if 1, according to Proposition I and AC B(a), with =--r.
Our linear convergence results for EF-BV are the following:
Theorem 1. Suppose that 0 and satisfies the PL condition with some constant μ 0. In EF-BV, suppose that E (0, 1], À E (0, 1] is such that r < 1, and
1
0 O<>S +
(8)
For every 0, define the Lyapunov function V f(x') 5 ? V - mIll?
28"h n
where f = f(xx), for any minimizer x² of f. Then, for every
maxx (1 (1-7 +
E E <
2 To
(9)
Theorem Suppose that f R satisfies the the KL condition with some constant μ 0. In EF-BV, suppose that E (0, 11, À E (0, 1] is such that r < 1, and
O<75
(10)
Fax 2L IN
r
Vt 2 0, define the Lyapunov function V² = f(x') + -(
7
Vf((z") - hill?
20- Ti
where f* = f(x*) and R = R(xx)) ). for any minimizer of R. Then, for every 2
r r+1 To
E
max
(11)
I1
2714
Remark (choice of X, 1/, y in EF-BV). In Theorems and 2 the rate is better if is small and ? large. So, we should take 7 equal the upper bound in (8) and (10), since there is no reason choose smaller. Also, this upper bound is large if r and Tav are small. As discussed in Sect. [2.5 and rav minimized with À X and D² (which implies that rav S r 1), this is the recommended choice. Also, with this choice of X, v, there is no parameter left to tune in the algorithm, which is a nice feature.
2.5
Remark (low noise regime). When the compression error tends to zero, i.e. n) and w tend zero. and we use accordingly X - 1, v > 1, such that / remains bounded, then C - Id, r - 0, and 1 + 0. Hence, EF-BV reverts to proximal gradient descent x*+1 = prox,, (=x ff(x'))
Remark 3 (high noise regime). When the compression error becomes large, i.e. 1J + 1 or w + +o0, then - and 1-y. Hence, the asymptotic complexity of EF-BV achieve e-accuracy, when
θ
is
Tay
Tav i
1 1-r
+
+1
log
(12)
p
T
8

---

4.1 Implications for EF21
Let us assume that X, that EF-BV reverts EF21, as explained in Sect. 3.1 Then, if we don't assume the prior knowledge of Wav- or equivalently if way = w. Theorem with r = fav recovers the linear convergence result of EF21 due to Richtárik al. 202T), up slightly different constants.
However, in these same conditions, Theorem 2 new: linear convergence of EF21 with R + 0 was only shown in Theorem 13 of Fatkhullin al. (002I), under the assumption that there exists μ > 0, V+)(= 2 (1( + R(x)
such that for every x E Rd 7/ x p
R*) -*) This condition generalizes the PL condition, since it reverts to when R= O, but it different from the KE. condition, and it is not clear when it is satisfied, in particular whether it is implied by strong convexity of f + R.
The asymptotic complexity to achieve c-accuracy of EF21 with y =
L+L/s (+ is (
log
(where we recall that r= a, with the scaled compressors B(a))). Thus, for a given problem and compressors, the improvement of EF-BV over EF21 is the factor / Tax (12). which can be small if n is large.
Theorems 1 and 2
provide new insight about EF21: if we exploit the knowledge that Cj C(n, w) and the corresponding constant wav, and Wav < w, then Tav < r, so that, based on ( and (TO). can be chosen larger than with the default assumption that Tav r. As a consequence, convergence
will be faster. This illustrates the interest of our new finer paramcterization of compressors with 1), w, Wav. However, it is only half the battle to make use of the factor Zax. in EF21: the property wav < w is only really exploited if y = v² in EF-BV (since Tav is minimized this way). In other words, there is no reason to set v À in EF-BV, when larger value of is allowed in Theorems T and 2 and yields faster convergence.
4.2 Implications for DIANA
Let us assume that 1, so that EF-BV reverts to DIANA, explained in Sect. 3.2 This choice is allowed in Theorems T and 2 so that they provide new convergence results for DIANA. Assuming that the compressors unbiased, i.e. C E U(w) for some 2 0, we have the following result DIANA (Condat& & Richtárik 2022 Theorem with v2):
Proposition 3. Suppose that f is p-strongly convex, for some > 0, and that in DIANA, X
0 O<7S Loax + Lmael1 war" + w) En [V(((=") hgll² where x² is the minimizer of f + R. which exists
For every t 2 0, define the Lyapunov function 4 == I| x x+11==
(2 +
and is unique. Then, for every t 2 0, E[4'] < (max (1 [1-,4, 7/4
1+t 1+w ) Φ0.
Thus, noting that r I that r+l with different Lyapunov function. Theorems and and have the advantage over Proposition 3 that linear convergence is guaranteed under the PL or KE assumptions, which are weaker than strong convexity of f. Also, the constants L and L appear instead of Lmax- This shows a better dependence with respect to the problem. However, noting that
1 +w
1tg the rate is exactly the same in Theorem but
_ Itw' Fav Wav. 4w, the factor / /Ex
r
scales like Wavil, which is worse that Wav- This means that y can certainly be chosen larger in Proposition 3 than in Theorems [ [ leading to faster convergence.
However, Theorems I and 2 bring major highlight: for the first time, they establish convergence of DIANA, which is EF-BV with v = 1, with biased compressors. We state the results in Appendix [ by lack of space. In any case, with biased compressors, it is better to use EF-BV than DIANA: there is no interest in choosing 1 instead faster convergence.
v² which minimizes r and allows for larger 7, for
Finally, we can remark that for unbiased compressors with Way < 1. for instance if Way & with larger than w, then V* = _+iي & 1. Thus, in this particular case, EF-BV with v = 1²* and DIANA are essentially the same algorithm. This another sign that EF-BV with À = X* and v = V² is generic and robust choice, since it recovers EF21 and DIANA in settings where these algorithms shinc.

---

Sublinear convergence in the nonconvex case
In this section, we consider the general nonconvex setting. In ( every function fi is supposed L--moothh for some L; > 0. For simplicity, we suppose that R = 0. As previously, we set
== V= Ei= L. The average function f = Ei= fi is L-smooth, for some L I L. We also suppose that f is bounded from below; that is, fin = inf ZER f(z) > -C.
(1 Xn) + X Tay (1 (1-v+ vn) wawa as well as s = J and == s(1 + s) _ Our convergence result is the /
Given À (0. 1| and E (0,1), we define for convenience
following:
Theorem 3. In EF-BV, suppose that v E (0, 11. A E (0, 1] is such that r < 1, and
0<7S
(13)
L+ L+L L+ TTx
For everyt t 1, let i be chosen from the iterates x. pxx1, _x),...
x--1
uniformly random. Then
E || < 2(f(x))-f0)) fintt
G
(14)
y
0t
where G n E V/((2') - 1.1
Experiments
We conducted comprehensive experiments illustrate the efficiency of EF-BV compared to EF21 (we use biased compressors, so we don't I include DIANA in the comparison). The settings and results detailed in Appendix [and some results are shown in Fig. [ see the speedup obtained with EF-BV, which exploits the randomness of the compressors.
pile vig comart M4
21:01
C1.EV
E7-07
38.1
2721
652
0721
1921
0290
133
30
5 11.4
E7.24
120
07:07
2721
02-7
8111
201
072L
2000
12-1
6V/
127
Figure 2: Experimental results. We plot f(x²) f with respect to the number of bits sent by each node during the learning process, which is proportional to th. Top row: comp- d/2), overlapping { 1. Middle row: comp-(1. d/2). overlapping 2. Bottom row: comp- (2, d/2), overlapping
E ==1
10

---

References
Albasyoni, A., Safaryan, M., Condat, L., and Richtárik, P. Optimal gradient compression for distributed and federated learning, preprint arXiv:2010.03246. 2020.
Alistarh, D., Grubic, D., Li, J., Tomioka. R., and Vojnovic, M. QSGD: Communication effficieen SGD via gradient quantization and encoding. In Proc. 31st Conf. Neural Information Processing Systems (NIPS), pp. 1709-1720, 2017.
Alistarh, D., Hoefler, T., Johansson, M., Khirirat, S., Konstantinov, N., and Renggli, C. The convergence of sparsified gradient methods. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2018.
Attouch, H. and Bolte, J. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program., 116:5-116, 2009.
Barnes, L. P., Inan, H. A., Isik, B., and Özgür, A. rTop-k: A statistical estimation approach to distributed SGD, JEEE Sel. Areas Inf. Theory, 13)):897-907, November 2020.
Basu, D., Data, D., Karakus, C., and Diggavi, S. Osparse-Loccl-SSG Distributed SGD With Quan- tization, Sparsification, and Local Computations. IEEE Journal on Selected Areas in Information Theory, 1(1):217-226, 2020.
Bauschke, H. H. and Combettes, P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York, 2nd edition, 2017.
Beznosikov, A., Horváth, S., Richtárik, P., and Safaryan, M. On biased compression for distributed learning. preprint arXiv:2002. 12410, 2020.
Chang. C.-C. and Lin, C.-. LibSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):27, 2011.
Condat, L. and Richtárik, P. MURANA: A generie framework for stochastic variance-reduced optimization. In Proc. of the Mathematical and Scientific Machine Learning (MSML) conference, 2022.
Condat, L., Kitahara, D., Contreras, A., and Hirabayashi, Proximal splitting algorithms for convex optimization: A tour of recent advances, with new twists. SIAM Review, 2022a. to appear.
Condat, L., Malinovsky, G., and Richtárik, P. Distributed proximal splitting algorithms with rates and acceleration. Frontiers Signal Processing, 1, January 2022b.
Dutta, A., Bergou, E. H., Abdelmoniem, A. M., Ho, C. Y., Sahu, A. N., Canini, M., and Kalnis, P. On the discrepancy between the theoretical analysis and practical implementations of compressed communication for distributed deep learning. In Proc. of AAAI Conf. Artificial Intelligence, pp. 3817-3824, 2020.
Fatkhullin, I., Sokolov, I., Gorbunov, E.,, Li, Z., and Richtárik, P. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. preprint 1r.02:2110.03294, 2021.
Gandikota, V., Kane, D., Maity, R. K., and Mazumdar, A. vgSGD: Vector quantized stochastic gradient descent. preprint 19t.:1911.0097... 2019.
Gorbunov, E., Hanzely, F., and Richtárik, P. unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In Proc. 23rd Int. Conf. Artificial Intelligence and Statistics (AISTATS), 2020a.
Gorbunov, E., Kovalev, D., Makarenko, D., and Richtárik, P. Linearly converging enror compensated SGD. In Proc. of 34th Conf. Neural Information Processing Systems (NeurIPS), 2020b.
Gower, R. M., Schmidt, M., Bach, F., and Richtárik, P. Variance-reduced methods for machine learning. Proc. of the IEEE, 108(1 11: 1968 -988-1983, November 2020.
Gower, R. M., Richtárik, P., and Bach, Stochastic quasi-gradient methods: Variance reduction via Jacobian sketching, Math. Program., 188: 1et1115592,. July 2021.

---

Hanzely, F. and Richtárik, P. One method to rule them all: Variance reduction for data, parameters and many new methods. preprint arXiv:1905.1 1266, 2019.
Horväth, S., Ho, C.-Y., Horváth, L., Sahu, A. N., Canini, M., and Richtárik, Natural compression for distributed deep learning. preprint 1n..vv1195.10000
2019.
Horváth, S., Kovalev, D., Mishchenko, K., Stich, S., and Richtárik, Stochastic distributed learning with gradient quantization and variance reduction. Optimization Methods and Software, 2022.
Kairouz, P. et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2), 2021.
Karimi, H., Nutimi, J., and Schmidt, M. Linear convergence of gradient and proximal-gradice methods under the Polyak-F.ojasiewvv condition. In Frasconi, P., Landwehr, N., Manco, G., and Vreeken, J. (eds.), Machine Learning and Knowledge Discovery in Databases, pp. 795-811, Cham, 2016. Springer International Publishing.
Khaled, A. and Richtárik, P. Gradient descent with compressed iterates. In NeurlPS Workshop on Federated Learning for Data Privacy and Confidentiality, 2019.
Khaled, A., Sebbouh, O., Loizou, N., Gower, R. M., and Richtárik, P. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. preprint arXiv:2006. 11573, 2020.
Konečny, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D. Federated learning: Strategies for improving communication efficiency. In NIPS Workshop on Private Multi Multi-Party Machine Learning, 2016.
Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 3(37):50-60, 2020a.
Li, Z., Kovalev, D., Qian, X., and Richtárik, P. Acceleration for compressed gradient descent in distributed and federated optimization. In Proc. of 37th Int. Conf. Machine Learning (ICML), 2020b.
Lin, C.-Y., Kostina, V., and Hassibi, B. Differentially quantized gradient methods. IEEE Trans. Inf. Theory, 68(9):6078-66)) 6097, September 2022.
Mayekar. P. and Tyagi. H. RATQ: A universal fixed-length quantizer for stochastic optimization. IEEE Trans. Inf. Theory, 67(5):3133-3154 2021.
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and Agüera Arcas, B. Communication- efficient learning of deep networks from decentralized data. In Proc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), volume PMLR 54, 2017.
Mishchenko, K., Gorbunov, E., Takáč, M., and Richtárik, P. Distributed learning with compressed gradient differences. urXiv:1901 .09269, 2019.
Mishchenko, K., Hanzely, F., and Richtárik, P. 99% of worker maater communication in distributed optimization is not needed. In Proc. of 36th Conf. on Uncertainty in Artificial Intelligence (UAI), volume 124, pp. 979-988, 2020.
Parikh, N. and Boyd, S. Proximal algorithms. Foundations and Trends in Optimization, 3(1):127-239, 2014.
Philippenko, C. and Dieuleveut, A. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv:2006.1455 14591, 2020.
Qian, X., Sailanbayev, A., Mishchenko, K., and Richtárik, P. MISO is making a comeback with better proofs and rates. urXiv:1906 1996601474, June 2019.
Richtárik, and Takáč, M. Parallel coordinate descent methods for big data optimization. Math. Program, 156:433 4844 2016.
12

---

Richtárik, P., Sokolov, L,, and Fatkhullin, I. EF21: A new, simpler, theoretically better, and practically faster error feedback. In Proc. of 35th Conf. Neural Information Processing Systems (NeurIPS). 2021.
Safaryan, M., Shulgin, E., and Richtárik, Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. Information and Inference: Journal of the IMA, 2021.
Saha, R., Pilanci, M., and Goldsmith, A. J. Democratic source coding: An optimal fixed-length quantization scheme for distributed optimization under communication constraints. preprint arXiv:2103.07578, 2021.
Sattler, F., Wiedemann, S., Müller, K.-R., and Samek, W. Robust and communication- -fffccient federated learning from non-ii.d. data. IEEE Trans. Neural Networks and Learning Systems, 31 (9):3400-3411 2020.
Seide, F., Fu, H., Droppo. J., Li, G., and Yu, D. 1-bit stochastic gradient descent and application to data-parallel distributed training of speech DNNs. In Proc. of Annual Conf. of Inl. Speech Communication Association (Interspeech), 2014.
Szlendak, R., Tyurin, A., and Richtárik, P. Permutation compressors for provably faster distributed nonconvex optimization. In Proc. of Int. Conf. on Learning Representations (ICLR), 2022.
Verbraeken, J., Wolting, M., Katzy, J., Kloppenburg, J., Verbelen, T., and Rellermeyer, A survey on distributed machine learning. ACM Computing Surveys, 53(2):1-33, March 2021.
Wangni, J., Wang, J., Liu, J., and Zhang, T. Gradient sparsification for communication-effiiien distributed optimization, In Proc. of 32nd Conf. Neural Information Processing Systems (NeurIPS), pp. 1306-13181 1316, 2018.
Wen, W., Xu, C., Yan, F., Wu, C., Wang. Y. Chen, Y., and Li, TernGrad: Ternary gradients to reduce communication in distributed deep learning. In Proc. of 31st Conf. Neural Information Processing Systems (NIPS), pp. 1509-1519, 2017.
Xu, H., Ho, C.-Y,, Abdelmoniem, A. M., Dutta, A., Bergou, E. H., Karatsenidis, K., Canini, M., and Kalnis, P. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report, KAUST, 2020.
Xu, H., Ho, C.-Y., Abdelmoniem, A. M., Dutta, A., Bergou, E. H., Karatsenidis, K., Canini, M., and Kalnis, P. GRACE: A compressed communication framework for distributed machine learning. In Proc. of 41st IEEE Int. Conf. Distributed Computing Systems (ICDCS), 2021.
Zhang, J., You, K., and Xie, Innovation compression for communication-efiin distributed optimization with linear convergence. preprint arXiv:2105.06697, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [N/A] This is theoretical work. There are many open questions on extending the convergence results to other settings, but this is room for future work, not really limitation.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
13

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [No] We do not provide code but the methods are easy to implement. Existing code for DIANA or EF21 can easily be adapted by changing the stepsizes. All the information reproduce the experiments is provided.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [No] From our experience there is little influence of the random
seed.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e-g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're ro using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "hfuqcDDLvN2", "reviewer": "Reviewer_6of8", "summary": "This paper introduced a new communication-efficient distributed training method called EF-BV, which can be treated as a combination of previous method EF21 and DIANA.  The paper gives its linear convergence analysis under certain  conditions in the main part and experiments on relatively small dataset is provided in the appendix. This paper is well written  and easy to follow.", "questions": "See Weaknesses.", "limitations": "The paper discusses a new variant on a technique in distributed training. As far as I’m concerned, there is no serious issue or limitation that would impact society.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper proposed EF-BV which includes unbiased and biased compressors as its particular cases. The linear convergence analyses are detailed and technically sound. Assumptions underlying the proposed method are simpler compared to previous methods.\n\nWeaknesses: \n\n1.The main part can be more concise (especially for the introduction part)and including empirical results.\n\n2.Given the new introduced hyper-parameters, it is still not clear whether this new proposed method is empirically useful. How to choose  hyper-parameters in a more practical training setting?\n\n3.The empirical evaluations can not well supported their theoretical analysis. As the authors claim running experiments with 24 A100 GPUs, all methods should be compared in a relatively large scaled training task. Only small linear regression experiment results are reported, where communication is not really an issue.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ds3_ke5ueM", "reviewer": "Reviewer_HvEY", "summary": "This paper unifies the two distinct compress techniques: DIANA and EF21, into a single framework. This new algorithm, which is named EF-BV, has advantages over the combined two techniques. First, EF-BV allows biased compression, which is not allowed by DIANA. Second, EF-BV introduces randomness, which improves the performance compared to EF21. EF-BV's convergence is provided.", "questions": "+ The data in the distributed nodes are homogeneous because they are split after the random shuffle. It would be interesting to see the results for heterogeneous as well.  ", "limitations": "+ The result is only for functions satisfying the PL or KL conditions. Though these conditions are weaker than strongly convex, many problems do not satisfy these conditions. ", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The new framework allows more compression techniques than previous algorithms.\n+ The convergence results improve the existing one for EF21. \n\nWeakness\n- Removing the biasedness for DIANA has been done in recent work: Zhang, J., You, K., & Xie, L. (2021). Innovation compression for communication-efficient distributed optimization with linear convergence. _arXiv preprint arXiv:2105.06697_. This result is for decentralized optimization, which is more difficult than the centralized one considered in this paper. \n- EF-BV is only compared with EF21 for the biased compression. It would be interesting to see the comparison with DIANA as well.  \n- Even the benefit of EF-BV over EF21 is not too much in the numerical experiment. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Au0cg7Nq8a", "reviewer": "Reviewer_LBgw", "summary": "This work addresses the problem of compressing the information exchanged between the workers and the parameter-server for distributed optimization. There have been several works in the recent literature that consider this, and subsequently propose various compression mechanisms (eg. top-K, rand-K, quantization, etc.) to reduce the communication demand for various iterative algorithms. \n\nIn this work, firstly, the authors propose a slightly different perspective towards the characterization of such compressors. Existing works characterize a compressor $C(\\cdot)$ using the *expected compression error* defined as $\\mathbb{E}\\lVert C(x) - x \\rVert^2$, where $x \\in \\mathbb{R}^d$ is the compressor input and $d$ is the dimension. Consequently, the *expected compression error* is upper bounded in different ways, depending on whether the compressor is *unbiased* or *biased but contractive*. In this work, the authors propose an alternative and finer characterization of any compressor by decomposing the *expected compression error* into two terms: The **bias** of the compressor, and the **variance** of the compressor, as follows: \n\n$\\mathbb{E}\\lVert C(x) - x \\rVert^2 = \\lVert \\mathbb{E}[C(x)] - x \\rVert^2+ \\mathbb{E}[\\lVert C(x) - \\mathbb{E}[C(x)] \\rVert^2]$,\n\nwhere the first and second terms on the R.H.S. are the **bias** and **variance** respectively. Consequently, they propose a new class of compressors, $C(\\eta, \\omega)$, where $\\eta$ characterizes the bias, whereas $\\omega$ characterizes the variance of the compressor. They show that for appropriate values of $\\eta$ and $\\omega$, the class $C(\\eta, \\omega)$ boils down to known classes of compressors, such as *unbiased compressors* or *biased contractive compressors*, implying that $C(\\eta, \\omega)$ is a more general characterization of compressors.\n\nFollowing this, they propose the notion of **average relative variance** that characterizes the variance when compressed outputs from different workers are averaged at the parameter server. Furthermore, they also show that the bias and variance of any compressor $C(\\cdot) \\in C(\\eta, \\omega)$ can be traded-off by appropriately scaling the output of $C(\\cdot)$, i.e. using $\\lambda C(\\cdot)$ instead of $C(\\cdot)$, for some $\\lambda \\in (0,1]$. They subsequently show that with an appropriate choice of the scaling $\\lambda$, the *scaled compressor*, $\\lambda C$ can be made contractive with minimal bias (which is desirable).\n\nAfter this, the authors use this alternative characterization to propose a unified framework to generalize two existing works: **DIANA** *(Mishchenko et al.)* and **EF21** *(Richtarik et al.)*. DIANA studies the utility of unbiased compressors for distributed optimization. At every iteration, DIANA maintains a control variate **h** and predicts the (approximate) gradient from the control variate by doing a first-order predictive coding from compressed gradient differences. To do this prediction, it utilizes a parameter $\\lambda$ that controls the variance of the descent direction -- this is also referred to as **Variance Reduction**. On the other hand, EF21 studies biased contractive compressors, and shows that the idea of predictive first-order coding of DIANA can also be extended to mitigate the bias of contractive compressors, as long as the control variates converges to a point, implying that the sequence being compressed goes to 0. EF21 shows that compressing gradient differences (or, first-order predictive coding) implicitly does error-feedback to ensure convergence. However, it does not explicitly do anything to control the variance of the descent steps.\n\nIn the context of both of these works, EF-BV (short for **Error-Feedback with Bias-Variance Decomposition**) uses the *bias-variance decomposition* of the class $C(\\eta, \\omega)$ of compressors, that uses appropriate scaling to do both -- $\\rm (i)$ Updating the control variate from compressed gradient difference, and $\\rm (ii)$ Obtaining the descent direction from the control variate. To do $\\rm (i)$, the scaling is chosen so that the individual compression error at each worker is small, whereas to do to $\\rm (ii)$, the scaling is chosen so that the error in the (globally averaged) descent direction at the parameter server is small (this is where the characterization of **average relative variance** comes into picture). To do $\\rm (i)$ and $\\rm (ii)$, the optimal scaling makes use of the bias-variance decomposition parameters $\\eta$ and $\\omega$. EF-BV does separate scaling for both, allowing the algorithm designer a finer control on the compression error.\n\nFinally, the authors show how this approach subsumes DIANA and EF-21, while giving analytic convergence results. They prove linear convergence for objective functions that satisfy the Kurdyka-Lojasiewicz (KL) condition, which is a generalization of Polyak-Lojasiewicz (PL) condition for regularized objective functions. To do this, they choose appropriate values of the scaling parameters for $\\rm (i)$ and $\\rm (ii)$ as mentioned above. Subsequently, they also show how their approach has new implications for DIANA and EF-21.\n\n\n\n", "questions": "The paper is well-written. However, I have some questions and suggestions and I would be grateful if the authors address them. I would be happy to change my rating if these concerns are adequately addressed:\n\n1. The authors propose a general class of compressors $C(\\eta, \\omega)$, and mention in line 103: \"... It deals with unbiased compressors, biased contractive compressors, and possibly even more ...\" When I read this line, \"possibly even more\" made me wonder if it's really that obvious? Does the class $C(\\eta, \\omega)$ actually include compressors that are not obtained from a simple re-scaling of existing compressors in $\\mathbb{B}(\\alpha)$ or $\\mathbb{U}(\\omega)$? The authors do mention **mix-(k,k')** and **comp-(k,k')** -- however, they also note that similar compression errors can be obtained for appropriately designed **top-K** or **rand-K** compressors too. Is it not clear why one would prefer using **mix-(k,k')** or **comp-(k,k')** over these. In other words, the answer of the following question is not obvious to me, \"Are there compressors in the new proposed class $C(\\eta, \\omega)$ that perform better than existing compressors in any sense?\" A possible answer to this question might be: Even if the total compression error is the same, does the distinction of bias and variance for these compressors enable EF-BV to achieve a better convergence rate than with simply **top-(k + k')** or **scaled rand-(k + k')**? If what I mention here holds true, the authors should explicitly discuss this somewhere in the paper. Another possible answer to this question might be the concatenated use of compression and quantization operators that provide a different way of trading-off the bias and variance (some relevant references are mentioned in pts. 5-(b) and 5-(c) below).\n\n2. The authors define the **relative average variance** in order to characterize the variance of the compressed outputs averaged at the parameter server. But they make no mention of the **relative average bias** -- is it because for independent and identical compressors at the workers, global averaging at the parameter server makes no difference to the bias? If that is the case, I would request the authors to explicitly mention it somewhere (perhaps a footnote). If average variance is considered, it is only natural to discuss about the average bias, since a primary hinging idea of this work is the bias-variance decomposition of the compressors.\n\n3. The authors should reference the proofs for Propositions 4 and 5 in Appendices. A.1 and A.2, for the bias and variance of **mix-(k,k')** and **comp-(k,k')** to relevant sections App. D and App. E.\n\n4. Since the authors emphasize that the **average relative variance** can be *much smaller* than the individual variances of compressors at the workers due to large number of workers (n), they are requested to add an explicit discussion regarding how the communication / iteration complexity of EF-BV varies with the number of workers (n). Is the improvement only because of appearance of $\\omega_{av}$ in place of $\\omega$ or are there other expressions too through which \"n\" affects the convergence rate?\n\n5. The authors have missed several relevant references:\n\n      (a) The authors claim in line 508 that they *\"propose\"* **comp-(k,k')**: However, a concatenated application of top-k and rand-k has already been studied in the following: ***Leighton Pate Barnes, Huseyin A. Inan, Berivan Isik, Ayfer Ozgur, \"rTop-k: A Statistical Estimation Approach to Distributed SGD\", https://arxiv.org/abs/2005.10761***.\n\n      (b) More recent works using error-feedback wherein the convergence rate (at least for smooth and strongly convex functions) go beyond just *linear convergence* to *linear convergence with rates approaching uncompressed gradient descent*. In particular, ***Chung-Yi Lin, Victoria Kostina, Babak Hassibi, \"Differentially Quantized Gradient Methods\", http://128.84.4.18/abs/2002.02508*** studies quantization methods, and uses error feedback to ensure that gradients are *always evaluated* on the unquantized trajectory. Another work: ***Rajarshi Saha, Mert Pilanci, Andrea J. Goldsmith, \"Democratic Source Coding: An Optimal Fixed-Length Quantization Scheme for Distributed Optimization Under Communication Constraints\", https://arxiv.org/abs/2103.07578*** builds on top of this strategy to achieve dimension independent linear convergence rates close to the unquantized linear convergence rates.\n\n      (c) Some other recent relevant works on quantization for distributed optimization: ***Venkata Gandikota, Daniel Kane, Raj Kumar Maity, Arya Mazumdar, \"vqSGD: Vector Quantized Stochastic Gradient Descent\", https://arxiv.org/abs/1911.07971*** and ***Prathamesh Mayekar, Himanshu Tyagi, \"RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization\", https://arxiv.org/abs/1908.08200*** -- It is important to mention them because quantization is inevitable in the system implementation of any distributed optimization algorithm. So, the bias-variance tradeoffs for concatenated application of various compression and quantization strategies (in order to show that they lie in $C(\\eta, \\omega)$) is relevant to further justify and substantiate the importance of the new general class of compressors $C(\\eta, \\omega)$.\n", "limitations": "The work does not have any major limitations or potential negative impact. Some minor suggestions for clarification/improvement have been mentioned in the previous sections **Questions** and **Limitations** of the review.\n\nOne thing that I would appreciate if the authors cleared it up for me, \"How extensively does the framework proposed in this paper require the independence of the compressors across different workers?\" I understand it is not necessary as the authors mention *m-nice sampling* -- however, even for this scheme, the set $\\Omega$ of participating workers is selected uniformly at random which simplifies the analysis. Do the authors have any comments on if $\\omega_{av}$ is a sufficient way to characterize the average relative variance, and how to derive expressions for $\\omega_{av}$ in settings where the compressors across different workers are different? For example, different number of bits used to quantize the updates of each worker? In other words, \"Is $\\omega_{av}$ still much smaller than $\\omega$ in such under a worst-case scenario where the individual compressors at workers are heterogeneous?\" *Clarification -- This is not a major limitation of the work, just a suggestion to consider since it is a more practical scenario.* The authors should add a brief discussion on it because communication compression is a relevant aspect of federated learning and the assumptions of i.i.d. compressors or i.i.d. client selection rarely hold in such settings. Discussing this will perhaps broadens the impact of the paper.\n\nAnother suggestion I would have for the authors is to have some numerical experiments in the main body of the paper. An application-oriented theoretical research like this work is better appreciated with substantive numerical experiments, especially since the analyses solely can often not be tight. I understand the page limitations, but just a suggestion to put the experiments in the main body of the paper instead of the supplementary, in case the work is accepted and they get an additional page.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**: The work is mostly original, although it builds heavily on the works of Mishchenko et al. (DIANA) and Richtarik et al. (EF21). The authors have placed their work appropriately in the context of both these works and also discussed implications of their proposed framework for these existing works. The idea of characterizing estimators using the bias-variance decomposition is a common trick in Estimation & Detection Theory and Signal Processing. However, their application in the context of distributed optimization and its implications in tuning hyper-parameters as done in this work is non-trivial.\n\n**Quality**: The quality of this paper is good. The authors have put in appreciable effort in placing their work in the context of existing works and spent a considerable portion of the paper discussing prior works and how this work improves on top of them. The bibliography is mostly adequate -- however they have missed some recent relevant references that I am aware of and have mentioned in pts. 5-(a), 5-(b), and 5-(c) of **Questions** in the next section of the review. \n\n**Clarity**: For a major portion of the paper, the clarity is good and everything is well-explained. It is well-placed in the context of two of the most related works -- DIANA and EF21, and heavily builds on top of them. However, there were some places that confused me a little when I was reading the paper. Some of them might have gotten clear later in the paper (or over multiple reads, i.e. I had to read a couple of paragraphs multiple times to grasp its significance). I have mentioned them as follows:\n\n1. In line 91, the authors write \"... DIANA with independent random compressors has a $\\frac{1}{n}$ factor in the increase of iteration complexity due to the use of compression. That is, when n is very large, as is typically the case in practice, the iteration complexity does not suffer from the use of compression. EF21 does not have this property: its convergence rate does not depend on the number n of workers.\" -- It is not clear how DIANA and EF21 are being compared here. The authors say that in both of them, the iteration complexity does not suffer from increasing number of workers (n) -- why the use of \"however\" then? Are the authors saying -- DIANA performs better if there are more workers, i.e. as 'n' increases, whereas EF21 does not? If that is the case, perhaps this paragraph needs some rephrasing.\n\n2.   In lines 101-106, the authors make some claims regarding the desiderata of a distributed optimization algorithm. under communication constraints. A suggestion -- The authors should explicitly specify how EF-BV addresses them by reverting back to these points later in the paper after EF-BV is introduced.\n\n**Significance**: The contributions of this work are significant. Specifically, I imagine the bias-variance characterization of compressors to have an impact on guiding the design of distributed algorithms for other settings, beyond EF-BV such as fully decentralized or peer-to-peer settings or federated learning with local averaging. In particular, the bias-variance can be traded-off differently beyond just a simple scaling as done in this work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept