EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
Authors: Peter Richtárik
Igor Sokolov
Ilyas Fatkhullin
Venue: NeurIPS 2021 Oral (2021)
Keywords: error feedback
distributed learning
communication compression
TopK
contractive compressor
distributed training
distributed optimization

Abstract: Error feedback (EF), also known as error compensation, is an immensely popular convergence stabilization mechanism in the context of distributed training of supervised machine learning models enhanced by the use of contractive communication compression mechanisms, such as Top-$k$. First proposed by Seide et al [2014] as a heuristic, EF resisted any theoretical understanding until recently [Stich et al., 2018, Alistarh et al., 2018]. While these early breakthroughs were followed by a steady stream of works offering various improvements and generalizations, the current theoretical understanding of EF is still very limited. Indeed, to the best of our knowledge, all existing analyses either i) apply to the single node setting only, ii) rely on very strong and often unreasonable assumptions, such as global boundedness of the gradients, or iterate-dependent assumptions that cannot be checked a-priori and may not hold in practice, or iii) circumvent these issues via the introduction of additional unbiased compressors, which increase the communication cost. In this work we fix all these deficiencies by proposing and analyzing a new EF mechanism, which we call EF21, which consistently and substantially outperforms EF in practice. Moreover, our theoretical analysis relies on standard assumptions only, works in the distributed heterogeneous data setting, and leads to better and more meaningful rates. In particular, we prove that EF21 enjoys a fast $\mathcal{O}(1/T)$  convergence rate for smooth nonconvex problems, beating the previous bound of $\mathcal{O}(1/T^{2/3})$, which was shown under a strong bounded gradients assumption. We further improve this to a fast linear rate for Polyak-Lojasiewicz functions, which is the first linear convergence result for an error feedback method not relying on unbiased compressors. Since EF has a large number of applications where it reigns supreme, we believe that our 2021 variant, EF21, will have a large impact on the practice of communication efficient distributed learning.	

EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
Peter Richtárik KAUST*
Igor Sokolov KAUST
llyas Fatkhullin KAUST' & TU Munich
Abstract
Error feedback (EF), also known error compensation, is an immensely popular convergence stabilization mechanism in the context of distributed training of super- vised machine learning models enhanced by the use of contractive communication compression mechanisms, such as ko First proposed by Seide et al. [2014) as heuristic, EF resisted any theoretical understanding until recently [Stich et al.) 2018 Alistarh et al., 2018). While these early breakthroughs were followed by steady stream of works offering various improvements and generalizations, the current theoretical understanding of EF is still very limited. Indeed, to the best of our knowledge, all existing analyses either i) apply to the single node setting only, rely on very strong and often unreasonable assumptions, such global bound- edness of the gradients, or iterate-dependen assumptions that cannot be checked a-priori and may not hold in practice, iii) circumvent these issues via the intro- duction of additional unbiased compressors, which increase the communication cost. In this work fix all these deficiencies by proposing and analyzing a new EF mechanism, which we call EF21, which consistently and substantially outperforms EF in practice. Moreover, only, works in the distributed heterogeneous data setting, and leads to better and more meaningful rates. In partieular, we prove that EF21 enjoys fast ( /T) convergence rate for smooth nonconvex problems, beating the previous bound (11/T//3), which was shown under a strong bounded gradients assumption. We further improve this to fast linear rate for Dolyyk-LLjasiewiin functions, which is the first linear convergence result for an eтror feedback method not relying on unbiased compressors. Since EF has large number of applications where reigns supreme, we believe that our 2021 variant, EF21, can have a large impact on the practice of communication efficient distributed learning.
theoretical analysis relies standard assumptions
Introduction
In order to obtain state-of-the-art performance, modern machine learning models rely on elaborate architectures, need to be trained on data sets of enormous sizes, and involve a very large number of parameters. Some of the most successful models are heavily weer-parameterized which means that they involve more parameters than the number of available training data points [Arora et al.) [0088.. Naturally, these circumstances should inform the design of optimization methods that could be most efficient to perform the training.
First, the reliance sophisticated model architectures, opposed to simple linear models, generally leads to nonconvex optimization problems, which are more challenging than convex problems (Jain) and Kar 2017 Second, the need for very large training data sizes necessitates the use of distributed
Kiig Abdullah University of Science Technology, Thuwal, Saudi Arabia. This paper was written while llyas Fatkhullin was an intern at KAUST.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

computing /Verbrakken et al. 2019]. Due to its enormous size, the data needs to be partitioned across number of machines able to work in parallel. Typically, for further efficiency gains, each such machine further parallelizes its local computations using one or more hardware accelerators. Third, the very large number of parameters describing these models exerts an extra stress on the communication links used to exchange model updates among the machines. These links are typically slow compared to the speed at which computation takes place, and communication often forms the bottleneck of distributed systems even in less extreme situations than over-parameterized training where the number of parameters, and hence the nominal size of communicated messages, can be truly staggering. For this reason, modern efficient optimization methods typically employ elaborate lossy communication compression techniques to reduce the size of the communicated messages.
Due to the above reasons, in this paper we are interested in solving the nonconvex distributed optimization problem
1 TI
min ZER
f(x)
f((z)
where Rd represents the parameters of a machine learning model we wish to train, n is the number of workers/nodes/machinn
and fi(z) ) is the loss of model x on the data stored on node i. We specifically focus on the development of new and more efficient communication efficient first- order methods for solving ① utilizing biased compression operators, with a special emphasis on clean convergence analysis which removes the strong and often unrealistic assumptions, such as the bounded gradient assumption, which are currently needed to analyze such methods (see Table [.
The remainder of the paper is organized as follows. In Section 2 we describe the key concepts, results and open problems that form the motivation for our work, and summarize our main contributions. Our main theoretical results are presented in Section 4 In Section 4.4 we establish connection between EF and EF21. Finally, experimental results are described in Section 5
2 Background and Motivation
To better motivate our approach and contributions, we first offer concise walk-through over the key considerations, difficulties, advances and open problems in this area.
2.1 Two families of compression operators
Compression is typically performed via the application of (possibly randomized) mapping C Rd + Rd, where d the dimension of the vector/tensor that needs to be communicated, with the property that it is much easier/quicker to transfer C(x) than it is to transfer the original message This can be achieved in several ways, for instance by sparsifying the input vector [Alistarh et al., 2018), or by quantizing its entries [Alistarh et al. 2017 Horváth et al., [019a]. via combination of these and other approaches [Horváth et al. 2019a Beznosikov et al. 2020
There are two large classes of compression operators C often studied in the literature: i) unbiased compression operators satisfying a variance bound proportional to the square norm of the input vector, and ii) biased compression operators whose square distortion is contractive with respect to the square norm of the input vector.
In particular, we say that a (possibly randomized) map C Rd + Rd is an unbiased compression operator, or simply just unbiased compressor, if there exists constant 2 0 such that
E [C(()) = x, [[[(()) x 1² s w||,
Vx E Edd
The family of such operators will be denoted by U(w). Further, we say that (possibly randomized) map C: : IRdd - R is a biased compression operator, or simply just biased compressor, if there exists constant 0 < a S such that
E [[[C(x) - x 12] s (1 a:) ||=1
Vo ERd
(3)
The family of such operators will be denoted by B(ax). It is well known that, in a certain sense, the latter class contains the former. In particular, it is easy to verify that if C E U(w), then (1 + - e B(1(0=))) However, the latter class is strictly larger, i.e., contains compressors which do not arise via scaling of an unbiased compressor. A canonical example of this is the Top-k compressor, which

---

preserves the k largest (in absolute value) entries of the input, and zeros out the remaining entries, and for which a k/d. We refer to [Beznosikov et al. 2020 Safaryan al. 2021 Table 1] for more examples of unbiased and biased compressors, and to Xu et al. 2020 for a systems-oriented survey.
When used in appropriate way, greedy biased compressors, such as Top-k; often empirically superior to their unbiased counterparts (Seide et al., [014], such as Rand-k. Intuitively, such greedy compressors retain more of the "information" or "energy" contained within the message, and hence introduce less distortion. This is beneficial in practice, at least in the simplistic single node (i.e., -on-distributed) setting, albeit even here we do not have convincing theory that would explain this. Indeed, both T and Rand-k impart the same distortion in the worst case, which happens when the energy is distributed uniformly across all entries of the input vector, and is not easy to capture theoretically that this worst case situation will not happen repeatedly throughout the iterations. As a result, there is currently no separation between the worst case complexity of first order methods, such as gradient descent, combined with biased vs related unbiased compressors [Beznosikov et al., 2020). If one makes a-priori statistical assumptions on the distribution of the messages/gradients that need to be compressed, such separation can be made [Beznosikov al., 2020). While insightful, this is not satisfactory. Indeed, the gradients produced by methods such as gradient descent evolve in non-stationary way, and hence modeling them as samples coming from a fixed distribution raises questions. Further, gradient compression affects the iterates and hence also the gradients that will be produced in all subsequent iterations, which is another phenomenon not captured by the aforementioned approach.
2.2 Error feedback: what is good for, and what we still do not know
The difference between what we know about unbiased and biased compressors is larger still in the distributed setting.
In particular, unbiasedness turns out to be very effective tool facilitating the analysis of distributed first order methods utilizing unbiased compressors, and for this reason, the landscape of methods using such compressors is very rich and relatively well understood. For example, using unbiased compressors we know how to
i) analyze distributed compressed gradient descent [Kirirat et al. 2018 Mishchenko et al. 2020).
ii) remove the variance introduced by compression to achieve faster convergence Mishchenko et al.] 2019 Horváth et al., 2019b Mishchenko et al. 2020).
iii)
perform bidirectional compression at the workers and also at the master (Hovväth et al. 2019a Philippenko and Dieuleveut) 2020 Gorbunov et al. (2020b).
iv) develop a general theory for SGD which, besides more standard methods, also includes variants using unbiased compression of (stochastic) gradients [Gorbunov et al.) 2020a
Khaled et al. 2020 Li and Richtárik 2020
achieve Nesterov acceleration in the strongly convex regime ct.
2020].
vi) how to analyze these methods in the nonconvex regime MMishchenko et al. 2019 Horváth
et al. 2019a Li and Richtárik 2020).
vii) achieve acceleration in the nonconvex regime [Gorbunov al. 202 and even how to
viii) apply unbiased compressors to Hessian matrices to obtain communication-efficcenn second- order methods [Islamov et al., 2021].
The situation with general biased compressors (i.e., those that do not arise from unbiased compressors via scaling) is much more challenging. The key complication comes from the fact that their naive use within first order methods, such gradient descent, can lead to divergence. We refer the reader to (Karimireddy et al. 2019, Counterexamples 1-3] and [Beznosikov et al.) 2020 Example 1] for illustrative examples. In the latter, the gradient descent "enhanced" with the Top-1 compressor leads to exponential divergence when applied to the problem of minimizing the average of three strongly convex quadratics in R However, divergence of gradient descent enhanced with biased compressors such as Top-k was observed empirically much sooner, and a fix for this problem, known as error feedback (EF), or error compensation (EC), was suggested by [Sede et al. 2014). This fix remained a heuristic until very recently.
3

---

The first theoretical breakthroughs focused on the simpler single-node setting (Stich et al. 2018 Alistarh et al., 2018). The first analysis in the general distributed heterogeneous data setting was performed by Beznosikov et al. [020]. and was confined to the strongly convex regime. While without compression, one can expect a linear rate, the rate in [Beznosikov et al. 2020 is linear only in the special case of an over- parameterized regime (i.e., the regime in which the loss functions on all nodes share a common minimizer) with a requirement of full gradient computations on each node. These deficiencies were later fixed by Gorbbnnv et al. (2020b), who developed the first linearly convergent methods EC-GD-DIANA and EC-LSVAG-DIANA and also analyzed the convex case. Further. Qian et al. [2020a b) showed that error- compensated methods can be accelerated in the sense of Nesterov Nesterov 2004) and can be combined with variance reduction techniques. However, these advances were achieved through the use of additional unbiased compressors or extra communication of full vectors, and hence via an increase in communication in each round. In the orthogonal line of works, |Sun et al. [2020), Magnússon al. [2019) designed special types of biased quantization operators. However, these quantization schemes are unable to compress gradients below O (d and the suggested methods require hyperparameters which cannot be efficiently estimated.
In particular, whether it is possible to obtain a linearly convergent error- compensated method in the general heterogeneous data setting, relying on general biased compressors only, is still an open problem.
The current state-of-the-arr theoretical result for error-compensated methods in the smooth non- convex regime are due to Koloskova et al. [2000] Theorem 4.11, who consider the more general problem of decentralized optimization over a network. In the case when full (as opposed to stochastic) gradients are computed on each node, they show that after T communication rounds it is possible to find a random vector x² with the guarantee
G2/3
E
|
-
T2/3
under the bounded gradient assumption which requires the existence of a constant G such that
[f(aa)] < G²
(5)
holds for all x E Idd and all i (n.). This was a slight improvement in rate over an result obtained by Lian et al. [2117) who instead use the bounded dissimilarity assumption
- G
(6)
A summary of the limitations of known results for EF-based methods is provided in Table [
In this work we argue that the bounded gradients (5) and bounded dissimilarity 66) assumptions are too strong and that the sublinear rate 4 not what one should expect from a good analysis of a well designed error- compensamee first- order method. Instead, one could hope for the faster ((1/r) rate, which what one obtains with methods using unbiased compressors [Gorbunov et al. 2021 Theorem 2.1]. The resolution of these issues is an open problem.
3 Summary of contributions
In this work we address and resolve the aforementioned challenges. Our key contributions are:
'Problem is in the heterogeneous data regime if no similarity among the functions (and hence among the data stored across different nodes giving rise to these functions) is assumed.
*This is very limiting as in large scale learning, d is enormous, and one usually needs to use dramatic sparsification such as Top-
too strong as they are rarely satisfied. For example, neither hold even for simple quadratic Tunctions. To see this, let fe(z) = x A.r, where (z) B,r, where B; = A; + A,,, the bounded gradient assumption requires the vectors sup,, max; ||,z to be bounded, which not the case, unless all matrices B, are zero. The bounded
'The bounded gradient (5) and bounded dissimilarity (6) assumptions
A; E Rddd, Since V
dissimilarity assumption 6). which can he written the form En= [[ 1/ Σi= Ba]= S G2, also
does not hold, unless B, B, for all i.j. which reduces the identical data regime, which is of limited interest.

---

Algorithm
SCVX
nCVX
DIST
key limitation
bounded gradients:
X
Stich et al.
2018
Cordonnier [0118
sublinear rate in sC case
EF-SGD
X
single node only
Stich and Karimireddy
2019
EF
/
K
single node only
Ajallocian and Stich
2020
SignSGD
moment hound;
Karimireddy ct al.
2019
x
/
X
single node only
EC.SGD
lincar rate only
x
/
Beznosikov ct al.
2020
if V fi(x)) [ = 0 vi
EC-SGD
linear rate only using an extra unbiased compressor
x
/
Gorbunov et al.
2020b
Doublesqueeze
bounded compression error;
/
/
Tang et al. 20200]
slow (1/22/8) rate in nCVX case
QssprreeSGDD, CSER
bounded gradients;
/
Basu et al. 2019 Xic et al. 2020
slow (1//1/33) rate in nCVX case
EC-SGD
bounded gradients; slow (11/72/3) rate in nCVX
Koloskova et al. 2000
Table 1: Known results for first order methods using biased compressors. sCVX supports strongly convex functions, nCVX= supports nonconvex functions, DIST works in the distributed regime. Tdecentralized method
Assumptions
Complexity 2 2(1(2))
Theorem
L--smooth f is lower bounded by flat fi is Ly-smooth
G 8T
E
77
f lower bounded by fint
E
V
S (1 7/1) TE [VO]
f satisfies PL condition
Table 2: Summary of complexity results obtained in this paper. Quantities: PL constant;
stepsize; G see V Lyapunov function defined in Theorem 3
A. New error feedback mechanism. We propose a new error feedback (resp. error pensation) mechanism, which we call EF21 (resp. EC21) see Algorithms| and Unlike most results compensation, EF21 naturally works in the distributed heterogeneous data setting.
2
Standard assumptions and fast rates. Our theoretical analysis of EF21 relies on standard assumptions only, which are:
i) L--smoothness of the individual functions fú, and ii) existence of global lower bound fin't E IR on
We prove that under these assumptions, EF21 enjoys the desirable O(/r)) convergence rate, which improves upon the previous (1/22/3) state-of-the-ant result of Koloskova et al. [2020] both in terms of the rate, and in terms of the strength of the assumptions needed to obtain this result. These complexity results are summarized in the first row of Table 2
C. Linear rate for assumption that f satisfies the Solyykk-Ljasiewae inequality. EF21 enjoys linear conver- gence rate. This improves upon the results of Beznosikov et al. [2020], who only obtain linear rate the case when (x() an alternative to the linear convergence results of Gorbunov et al. (2020b), who needed to
functions. We show that under the additional
for all where
arg min f. and provides
introduce additional unbiased compressors into their scheme, and hence additional com- munication, in order to obtain their results. Our complexity results are summarized in the second row of 2
Empirical superiority. We show through extensive numerical experimentation on both synthetic problems and deep learning benchmarks that EF21 consistently and substantially outperforms EF in practice. One of the reasons behind this is the fact that our method is able to admit much larger learning rates. Since EF has a large number of applications
5

---

where it reigns supreme, we believe that EF21 will have a large impact on the practice of communication efficient distributed learning.
E. A more aggressive variant. We further propose more aggressive variant, EF21+ (see Section[466 (.6).. which has an even better empirical behavior. We show that C is deterministic, the same theorems capturing the convergence of EF21 hold for EF21+ well.
F. Stochastic setting, We describe an extension to the stochastic setting, i.e., when each node computes a stochastic gradient instead of the exact/full gradient, in Appendix
4
Main Results
Since we are about to re-engineer the classical error feedback technique, it will be useful to take a step back and re-examine the issues inherent the simplest first order method which uses biased compressors but does nol employ error feedback: distributed compressed gradient descent (DCGD).
Let x' be the t-th iterate, shared by all n nodes. Each node first computes its local gradient V fxx". compresses it using some E B(a)), and sends the compressed gradient f( to the master. The master aggregates all n messages via averaging, and performs the optimization step
Σ C(VS(z))).
As mentioned before, this method can diverge, even in simple quadratic problems in low dimen- sions [Beznosikov et al. 2020]. Let us look at this problem from a different angle. Assume, for the sake of an intuitive argument, that the sequence of iterates actually converges to some Since in general there is no reason for the gradients V ff((!) to be all zero, even if æ is the minimizer of f. the application of to the gradients V fa(") will introduce a nonzero distortion even x² ze x². Indeed, in view of (3), all that can be guaranteed is that
E [[(((V(((())) - V=('a)) s (1 [VA(')]]
which can be large if the norm of V fx(= is large. So, the method is intrinsically unstable around at, and hence can not converge to x
Our idea is to fix this issue by compressing different vectors instead of the gradients, vectors that would hopefully converge to zeros instead. Since in view of (3) the application of C to progressively vanishing vectors introduces progressively vamishing distortion, the stabilization problem would be solved. But what vectors should we compress? In order to answer this question, it will be useful to consider a simpler and more abstract setting first, which we shall do next.
4.1 Markov compressors
Assume we are given a sequence of input vectors {o"}e2 (e.g., gradients) generated by some algorithm. This sequence does not necessarily converge to zero. Our goal is to produce a sequence of "good" and "easy to communicate" (to some entity, which we shall call the "master") estimates of these vectors, making use of compressor C BB)).. Let us proceed through several steps of discovery.
Naive idea. The first and naive approach, described above, is to simply output the sequence of compressed inputs: (C(e"))12-- However, while these estimates can be communicated efficiently, they are not getting "better". That is, the distortion [[[C(=*) (1]]3] is not necessarily improving.
Good but not implementable idea. What can we do better? Consider the following idea. If we knew, hypothetically, the limit of this sequence, v², we could output v" + C(v² o²) at iteration instead. Since of + o., the distortion between the input and the output at iteration t is
||o'" -C6'-
||c(o' - 0²) (u' " )²)
B
(1 a) ||u' v0 v 0.
So, the distortion issue fixed! Moreover, we assume the master knows v then the output vector at each iteration can be communicated cheaply as well, since all we need to communicate is the

---

Algorithm EF21 (Single node)
Input: starting point æ" E R. learning rate 7 > go c(Vf(()))
2: for = 0,1,2 ,.,T"- - do
3: x²t1 xf 7g"
4: ge+l = g" + C(( - -9)
5: end for
compressed vector C(o² v*). It will be useful think of this operation
compressor, called Cu+, one that takes of as an input, and gives v² + C(e" - 0*) as its output. That is, we can define
(u) def v² C(v v²).
While the compressor C.- satisfies all our requirements, it is not implementable, since the vector is not known. We will now use this intuition to construct an implementable mechanism.
Good and implementable idea. In the above construction, we have used the fact that to construct good mechanism, but one that is not implementable. How can we fix this issue? The rescue comes from the recursive observation that if we indeed succeed constructing a compressor, let's 's call it M,, such that the distortion between M(v") and v' vanishes as - oc, then it must be the case that 8² M(v') - So, we can compress this vanishing vector instead. This idea gives rise to the following recursive definition of M:
+
M(0") del C(v")
(9)
M(+
M(r') +C( ((ott1-(((")) t20
(10)
Note that (1O) is similar to (8, with one key difference: we are using the previously compressed vector M(v)), which is known, instead of the limit vector v², which is unknown. This property also makes our new compressor non-stationary, i.e., has a Markov property.
It is easy to establish (see Appendix B that under some assumptions about the speed at which the input sequence v² converges to v², will the case that [LM('')) x01 - O. For instance,
the convergence rate of the input sequence is linear, then the distortion will converge to O. While this interesting on its own, let us deploy our new tool, which we call Markov compressor, in the context of gradient descent, and then in the context of distributed gradient descent.
4.2 Compressed gradient descent using the Markov compressor
For simplicity, consider solving problem in the n 1 case, i.e., the problem
min f(x), #ERd
(11)
using the compressed gradient descent method featuring the Markov compressor. Start with x Rd stepsize 7 > 0, and let
After this, for t 2 O iterate:
2141 x' 2'-2M((f(=")) ((V M
(12)
-MV
(13)
Note that the situation here is complicated than the abstract setting described carlier since now there interaction between the input sequence [=f(")))22 gradients and the sequence (x))) of compressed gradients via the Markov compressor. Indeed, the output of M at iteration t influences the next iterate *++ (via (12) ). which in turn defines the next input vector
g (x in the sequence, and
To lighten up the heavy notation (12) and (13, it will be useful to write g' (>)((>))) Using this new notation that hides the fact that g is the application of the Markov compressor to the gradient, the method described above formalized as Algorithm [T This precisely our proposed new variant of eπror feedback, EF21, specialized to the single node problem (II)
7

---

Algorithm 2 EF21 (Multiple nodes)
Input: starting point xº E RR. 9i )(()))))) for i 1,..., (known by nodes and the
master); learning rate 7 > 0: go Ei= of (known by master)
2: for = 0,1,2.....;
do
3: Master computes x
xf ng and broadcasts x1 to all nodes
4: for all nodes i = 1, 1,...,77 in parallel do
5: Compress - C(V )) gf) and send cf to the master
6: Update local state of +1 o CC(V((xx+)) -
7: end for
8: Master computes g = 1 Dim1 Di
++1 via gag"t getl = g" + n Σ
9:
end for
4.3 Distributed variant EF21
The main method of this paper, which we now present as Algorithm 2 is extension of Algorithm I to the general finite-sum problem (T). In particular, we apply the Markov compressor individually on each node the local gradients (z'),, and communicate the compressed gradients to the master. Recall that we only need to communicate the vectors C(V (z gf) since the additive terms of appearing in the Markov compressor averages all gradient estimators, obtaining g"+11 = Σ g which can be done by performing the calculation y +1 g² Σn c where oe is the average from the previous round which the master maintains, and = C(V ((Vf((=')) g are the compressed messages. After this, the master takes gradient-like step, and broadcasts the new model to all nodes.
communicated in the previous round. Master then
4.4 Relationship between EF and EF21
While this is not at all apparent at first sight, it turns out that EF and EF21 are related. In particular, under certain conditions on the compressor C, which are not met practice, they are identical.
Theorem 1. Assume that C is deterministic, positive homogeneous and additive. Then EF (Algo- rithm 3 see appendix) and EF21 produce the same sequences of iterates {x" {x')12o-
Note that while the Top-k compressor deterministic and positively homogeneous, is not additive. Likewise, compressors arising via rescaling of unbiased compressors randomized, and hence do not satisfy the first condition. Still, the above theorem sheds some (at least to us) unexpected light on the close connection between EF and our variant, EF21. This connection is also what justifies our naming decision: EF21 error feedback mechanism from the year 2021.
4.5 Theory
We make the following assumption throughout: Assumption
(Smoothness and lower boundedness). Every J has Læ-ipsshitzz gradient, i.e.,
[Vf((z) vii(vi) S L; || [|x--(] yll
for all x, E Rd,, and finl def inf f(x) -c.
If each fú has Lipshitt gradient, then it straightforward to check by Jensen's 's inequality that f is L-Lipschitz, with L satisfying the inequality L. < E, L., It will be also useful to define
def E. 1/2 By the arithmetic-quadrate mean inequality, have 1 -. Li < L. Let
T
Gt del
o
(14)
quantity which will appear in both our theorems. In EF21 we use C E B(a)) where 0 < S 1, and We now formulate our first complexity result.
define 0 = 1 vI- - a and 3 = 1-VI-a
1-a

---

Theorem 2. Let Assumption 7 hold, and let the stepsize in Algorithm 2 be set
0<7s L4
(15)
Fix T 2 and let So be chosen from the iterates x., ,..,..,,?? uniformly at random. Then
E [[V[((>>) 11] 2 ( -
I
G
(16)
S
8T
Note that v (++vI-a)
- is decreasing in This makes sense since larger means less dramatic compression, which leads to smaller /8/0, and this through (15) allows for larger stepsize, and hence fewer communication rounds. We now introduce the PL assumption, which enables us to obtain linear convergence result.
Assumption 2 (Polyak- Lojasak--ojsseewiezz.. There exists μ 0 such that f(x) f(x²) * [+)] for all x E R2, where x² arg min (xx).
Theorem 3. Let Assumptions and hold, and let the stepsize in Algorithm
be set as
0 イ S min {
-1
23
0
(17)
2μ
Let & del f(x²)= f(x²) G..
Then for any T 2 0, we have
E
S (1 - y IE |
(18)
Our theorems hold for an arbitrary choice of the initial vectors {o }. and not just for g. (( (z
For instance, if of fz is used, then E [G"] 0, and the second term in 16 and the last
term in E O vanish.
4.6
EF21+: Use C the Markov compressor, whichever is better
We now briefly deseribe a new hybrid method, called EF21+, which often performs particularly well in practice. Full description and the analysis of EF21+ are deferred to Section G In every communication round, EF21+ allows each node to compress using the "best" of C and the Markov compressor generated. So, EF21+ be thought of hybrid between DCGD (see (7) and EF21. The decision about which compressor to use is made by each node i individually, based on which of the distortions |[C(s) s|| and (sM - s|] is smaller, where (((*+1))
4.7 Dealing with stochastic gradients
In Section H (see Algorithm 5) we describe a natural extension of EF21 to the setting where full gradient computations replaced by stochastic gradient estimators, i.c., we use a random vector of R0 fz("). We also outline how convergence analysis is performed in this regime.
5
Experiments
We first consider solving a logistic regression problem with non-convex regularizer,
x
[(x)
log (1 + exp (-yaa x²))
(19)
N
+ x
where E Rd, De E (-1,1) are the training data, and X > 0 is the regularizer parameter. We set 0.1 all experiments. each set of experiments we use Top-k with à: = [Alistarh al. 2017 as a canonical example of biased compressor C.

---

Dataset
N (total # of datapoints)
d (# of features)
N₃ of datapoints per client)
phishing
20
11,055
68
552
mushrooms
20
8,120
112
406
a9a
20
32,560
123
1,628
w
20
49,749
300
2,487
Table 3: Summary the datasets and splitting of the data among clients.
Datasets. The datasets were taken from LibSVM [Chang and Lin 201 and were split into n = 20 equal parts, each associated with one of 20 clients. The last part, of size N 20 [N/20], was assigned to the last worker. That is, we consider the distributed regime with heterogeneous data. A summary The details on hardware and implementation can found Section A
can be found in Table 3
Stepsize tolerance. In our first experiment (see Figure I we test the robust- ness/tolerance EF, EF21, and EF21+ to large stepsizes. Note that while for all stepsize choices, EF gets stuck at a certain accuracy level, EF21 and EF21+ do not suffer from this issue, and are hence able work with larger even much larger stepsizes.
Experiment 1:
EF
EF21
EF21+
12.
10"
10
10-1
10-2
10
10
30
20502
40020
20000
40002
22000
40000
abic
JbRAh
Figure The performance of EF, EF21, and EF21+ with Top-1 compressor, and for increasing stepsizes. Representative dataset used: a By 1x, 2x, 4x (and so on) we indicate that the stepsize was set multiple of the largest stepsize predicted by our theory.
Fine-tuning is and the stepsizes. We showcase the superior communication efficiency of EF21 and EF21+ over classical EF. In this set of experiments, we fine-tuned & (for Top-k) and stepsizes individually for each method (details are given in Appendix AA. For comparison, we also included distributed gradient descent (GD), which can be seen as EF21 with k d (no compression), into the mix.
Experiment 2:
phishing
mushrooms
a9a
wBa
10"
10
10-4
10-4
10-
10
10
20000
100000
200300
50000
103000
Eaih
POEAT
PG
Figure 2: Comparison of EF21, EF21+ to EF with Top-k for individually fine-tuned & and fine-tuned stepsizes for all methods.
In Figure we can that in all cases, the proposed methods outperform EF in terms of the the number of bits sent to the server per client (bits/n), and rapidly converge to the desired accuracy, whereas EF is stuck at some accuracy levels in all cases. Moreover, in all experiments, classical GD shows the worst convergence rate. Note that EF21 tolerates larger, and EF21+ much larger, stepsizes than EF.
Further experiments. Appendix A
Further experiments, including deep learning experiments, are presented in
10

---

References
Ahmad Ajallocian and Sebastian U Stich. Analysis of SGD with biased gradient estimators. arXiv preprint arXiv:2008.0000 2020.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances Neural Information Process- ing Systems (NIPS), pages 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-SGD: Distributed SGD with quantization, sparsification, and local computations. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint 200.::2000...,110, 2020.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
Lean-Baptiste Cordonnier. Convex optimization using sparsified stochastic gradient descent with memory. Master's thesis, 2018.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In The 23rd International Conference Artificial Intelligence and Statistics (AISTATS), 2020a.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging error compensated SGD. In 34th Conference on Neural Information Processing Systems (NeurIPS), 2020b.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. arXiv preprint arXiv:2102.07845, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
Samuel Horváth, Chen-Yu Yu Ho, L'udovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint arXiv:1905. 10988. 2019a.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv: 19X4.v/904.05 15, 155, 2019b.
Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed second order methods with fast rates and compressed communication. arXiv preprint arXiv:2102.07158, 2021.
Prateek Jain and Purushottam Kar. Non-convex optimization for machine learning. Foundations and Trends in Machine Learning. 10(3-4):142-3333 2017.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In 36th International Conference on Machine Learning (ICML), 2019.
11

---

Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert M. Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint arXiv:2006. / 1573, 2020.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprini arXiv: arXiv:/866.005 186600677, 2018.
Anastasia Koloskova, Tao Lin, S. Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations (ICLR), 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, 2009.
Zhize Li and Peter Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint arXiv:2006.07013, 2020.
Zhize Li. Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient
descent in distributed and federated optimization. In International Conference on Machine Learning (ICML), 2020.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference Machine Learning (ICML), 2021. arXiv:2008. 10898.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems (NIPS), 2017.
Sindri Magnússon, Hossein Shokri- GaaakiiiGaadiolleii,,, and Na Li. On maintaining linear convergence of dis- tributed learning and optimization under limited communication. arXiv preprint 1rXiv:/902.11/66 2019.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09200 2019.
Konstantin Mishchenko, Filip Hanzely, and Peter Richtárik. 99% of worker-master communication in distributed optimization is not needed. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), volume 124, pages 979-988, 2020.
Yurii Nesterov. Introductory lectures on convex optimization: basic course (Applied Optimization). Kluwer Academic Publishers, 2004.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, nigh-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006. 1 14591, 2020.
Xun Qian, Hanze Dong, Peter Richtárik, and Tong Zhang. Error compensated loopless SVRG for distributed optimization. OPT2020: 12th Annual Workshop on Optimization for Machine Leurning, 2020a.
Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed SGD can be accelerated. arXiv preprini urXiv:2010.0009), 2020b.
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compres- sion in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA, 2021.
12

---

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 Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Sebastian Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv: Tee.1.9999.939 2019.
Sebastian U. Stich, J.-B. Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurlPS), 2018.
Jun Sun, Tianyi Chen, Georgios B. Giannakis, and Zaiyue Yang, Qinmin amd Yang. Lazily aggregated quantized gradient innovation for communication--ffieee federated learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Hanlin Tang, Xiangru Lian, Chen Yu, Tong Zhang, and Ji Liu. DoubleSquee7e: Parallel stochastic gradient descent with double error-compensated compression. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2020.
Joost Verbracken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan Rellermeyer. A survey distributed machine learning. ACM Computing Surveys, 2019.
Cong Xie, Shuai Zheng, Oluwasanmi Koyejo, Indranil Gupta, Mu Li, and Haibin Lin. CSER: Conmunication-efficceenn SGD with error reset. In Advances in Neural Information Processing Systems (NeurIPS), pages 12593-12605, 2020.
Hang Xu, Chen- Yu Ho, Ahmed M Abdelmoniem, Aritra Dutta, El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, and Panos Kalnis. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report, KAUST, 2020.
13


Reviews:
[{"review_id": "tXTvQvkvplF", "reviewer": "Reviewer_EY42", "summary": "This paper studies the Error Feedback (EF) technique in distributed optimization. The paper proposes a new version called EF21 and claims this is theoretically and practically better. A new scheme for EF compression named Markov compressor is proposed. The writing quality is great and the paper is easy to follow. However, some of the statements are flawed which substantially compromise the quality of this paper.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. For starters, one of the main contributions of EF21 is to converge at a rate of $1/T$ instead of $1/T^{2/3}$. Here the author makes a mistake in line 133, saying Koloskova et al. [2020, Theorem 4.1] assumes a bound on the full gradient on worker i. However, the actual assumption in that paper was a bound on the *stochastic* gradient on worker i. These two are notably different as the latter incorporates the sampling noise. If the sample complexity is not considered (which seems to be the case of EF21), it's not surprising that a $1/T$ rate is achieved (this is like saying GD improves upon SGD). In fact, if we remove the sampling noise in Koloskova et al. [2020, Theorem 4.1], a $1/T$ rate is straightforward to obtain. The paper claims in the abstract EF21 \"beats\" the previous bound of $1/T^{2/3}$, which is confusing. Also Koloskova et al. [2020] works in the decentralized case, which is more challenging than the setting in this paper.\n\n2. Could you provide a data-parallel setting where we need communication compression but no sampling? I cannot think of any since communication overhead is usually observed in deep learning tasks and sampling is a must rather than an option. Having said that, the application of EF21 is very limited. The authors provide empirical results on deep learning tasks in the appendix, but mini-batching is used there, which is not aligned with the theory or logistic regression task. Also the data heterogeneity issue is confusing: In data center training where we are able to shuffle the dataset, we can usually reduce the intra-worker variance. Heterogeneous data usually takes place in the federated learning, where the execution of EF21 shown in the paper clearly does not cover.\n\n3. Based on 1 and 2, the main improvement of Markov compressor upon EF is data heterogeneity where $||\\nabla f_i||$ can be large when the algorithm converges. However, the only case the Markov compressor can address this seems to be in non-stochastic case. If we use stochastic gradient in the Markov compressor, the error bound does not approach zero either. How EF21 handles this issue remains unclear. \n\n4. The authors conduct different experiments  but the results are not convincing. First, # Gbits/n is used as X-axis for all figures. However, for compression algorithms the convergence speed with respect to iterations or time are also important since when communication is reduced, the compression can become a new overhead. If the paper claims EF21 is practically better, other X-axis should be provided. Second, some of the plots for baselines are omitted for no reason, which is serious. Specifically, in the Resnet18 on CIFAR-10 experiment, EF and EF21 seems to perform similar under 128X, however only EF21 is shown under 512X while EF at 512X is not shown. Note that validation performance is not informative here, since the design of EF21 does not consider generalization.\n\nClarification on my review after reading the author response\n===\nWhile I appreciate the author answering my questions, but it appears some of my concerns were misunderstood. Specifically:\n\n**On the problem with improved rates**\n\nI did not state anywhere in my review that $G=0$, as author claimed. Let me rephrase: this is the problem with the baseline comparison. Take Koloskova et al. [2020] as example (other baselines such as Tang et al. [2020] has similar issue), in their Theorem 4.1, the convergence bound is shown as\n$O\\left(\\frac{\\bar{\\sigma}}{\\sqrt{T}} + \\frac{G^{2/3}}{T^{2/3}} + \\frac{1}{T}\\right)$, where $\\bar{\\sigma}^2$ and $G$ are assumed to be the bound on the variance and magnitude of the *stochastic* gradients, respectively. Now, since EF21's rate is shown in non-stochastic case, for comparison, the authors convert the baseline bound as follows: drop the first term (which makes sense since $\\bar{\\sigma}=0$); and keep the second term. That's where my confusion comes from, as $G$ is clearly correlated with the stochastic gradient in their analysis, so how do you justify the removal of term $\\frac{1}{T^{2/3}}$ in EF21 is due to EF21 being better algorithm/analysis, but not because the fact that two settings are different so that the conversion of baseline results is loosen? This happens because the authors converted a result from a more general setting to a special case, which could implicitly worsen the baseline result. In fact, there is no obvious way to detach the stochastic noise from $\\frac{G^{2/3}}{T^{2/3}}$ term without reproving the baselines in the non-stochastic case, so I don't fully understand how is it an improved rate.\n\nTo make this even clearer, consider this example (not relevant to the paper, just for illustration): suppose we prove algorithm A having rate $O(1/T)$ on smooth functions while algorithm B having rate $O(\\rho^T)$ on smooth and strongly convex functions. Clearly, algorithm A is analyzed in a more general setting (analogous to Koloskova et al. [2020]). Can we say B is better than A by directly converting these bound in any way? Apparently not. In fact, the only way to make conclusion on rate comparison is to reprove A or B in the other setting.\n\n(**In response to author's follow-up question on why Gower et al (2019) can do the conversion correctly**): I thank the authors for bringing up this paper as it is a perfect example for illustrating the problem. In a nutshell, you can convert a result from a general case to a special case by setting zero to variables, but not in every case. It depends on how the baseline result is shown. Gower et al (2019) does an analysis for SGD, take their Theorem 3.1 as example, they show the convergence rate by $\\mathbb{E}||x^k-x^*||^2 \\leq (1-\\gamma\\mu)^k\\mathbb{E}||x^0-x^*||^2 + 2\\gamma\\sigma^2/\\mu$ in their Equation (10). Now this result can be converted to GD with valid conversion since the term relates to stochastic sampling is the second one, and they can easily convert by setting $\\sigma=0$. However, in this paper the conversion is problematic (I acknowledge setting $\\sigma=0$ is correct in my review, it's the $G$ term that has problem) because you cannot detach the effect of stochastic gradient from $G$. Put it another way, if the baseline result looks like $O(\\sigma/\\sqrt{T}+{1}/{T^{2/3}} + 1/T)$, then your conversion would be correct since now only the first term relates to the sampling and you can easily convert the result by setting $\\sigma=0$ but that's not the case here.\n\n**On the problem with application**\n\nIn my original review, I raised the question of naming an application setting where we need communication compression but no sampling, to which EF21 can be applicable. The author states in their response that one application of EF21 is federated learning, which seems a little off to me. As we know, federated learning usually involves a large number of nodes, so a typical algorithm (such as FedAvg, SCAFFOLD) requires client sampling. However, in the multiple node version of EF21, it requires all the nodes to participate in each iteration and need to be synchronized at the end of each iteration. So if I understand it correctly, EF21 can be used in federated learning only under the following two conditions:\n\n(1) The number of nodes cannot be too large so that global synchronization is possible and negligible.\n\n(2) The number of data samples on each node (client) cannot be too large so that full gradient computation is not an overhead. \n\nI don't really understand how this is applicable, please correct me if anything in my statement is incorrect.\n\n**On the problem of extension to stochastic case**\n\nMaybe I did not state it well in the original review. My claim is that stochastic gradient actually breaks the intuition of EF21 which makes it not easy to extend. Here's why: the intuition of EF21 is illustrated in line 271: $\\mathbb{E}||\\mathcal{M}(v^t)-v^t||^2\\rightarrow 0$, while this is true for full gradient because as the algorithm converges, the magnitude of full gradient will approach zero. However, it's not clear to me why it still holds for stochastic gradient, especially the case where all the data samples have different local minimas (not quite the heterogeneity as mentioned in the paper). Specifically, could you explain why such quantity still approaches zero if $v^t$ contains sampling noise? \n\nThe authors state in their response that error feedback is orthogonal to stochastic approximation, and the latter should be handled by other variance reduction algorithms like SVRG, I'm confused. Because the baseline algorithms like DoubleSqueeze, Q-local-Sparse clearly works with stochastic approximation without involving variance reduction parts.\n\nThe author pointed out a stochastic analysis is included in the appendix I, however, no rate is shown in that analysis and that analysis ends with \"It is straightforward...to establish complexity results for our stochastic variant of EF21 .\" If the authors believe the statement of my original review \"$O(1/T)$ rate is straightforward to obtain in baseline\" is unjustified because \"such a rate is not included in their paper\", I politely ask the authors to apply the same standard to the paper, and avoid using such statement to justify your results. Because, the rate of EF21+ too, is not shown in the paper or appendix. As pointed out by authors in their response: \"Simply claiming this does not make it true\". Please correct me if I'm wrong.\n\n**Summary**\n\nI believe all my concerns are specific on the technical issues. The idea of Markov compressor is interesting, so I've decided to raise my score slightly to give some more credit. However, at this point, I still don't think this paper meets the acceptance bar of NeurIPS as the issues I raised are serious and closely related to the main contribution of this paper, unless the authors can prove I misunderstood them all.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper discusses a new variant on a technique in distributed training. There is, from my perspective, no serious issue or limitation that would impact society.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "SFIXYNX2bh6", "reviewer": "Reviewer_emqQ", "summary": "This paper proposes a new EF mechanism to solve nonconvex distributed optimization problem. The new proposed algorithm has the following advantages：1）Theoretical analysis relies on standard assumptions only as compared to others assumptions used in previous works, and leads to better an more meaningful rates. In specific, the convergence rate is improved from O(1/T^{2/3}) to O(1/T). 2) This paper provides the first linear convergence result for an error feedback method not relying on unbiased compressors. The successful results relies on the proposed recursive Markov compressor. Experimental results are provided to verify their theoretical observations.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written, and the idea is well-presented. As mentioned in this paper, the core idea of the paper is to use the propose recursive Markov compressor. In the theoretically sides, the recursive Markov compressor actually reduces the gradient approximation error, and thus provides better theoretically  results. This idea may share the same spirit of the stochastic variance reduction method in classical nonconvex optimization that reducing the approximation error by  using the previous gradient.  Although I do not go through the proof in details, I believe the proposed method works in theory. Correct me if I am wrong.\n\nThe drawback of the proposed method is about  practical usage. First, the nonconvex distributed optimization setting used in this paper is simple Synchronous SGD with distributed data.  Synchronous setting is time-consuming, and not that popular in practice. \nThe more interesting setting should give to the asynchronous setting.  It will be interesting to extend this idea to asynchronous setting.  \n\nOverall, I think the authors in this paper propose a interesting idea by using recursive  trick to solve the  nonconvex distributed optimization problem. In specific, the convergence rate is improved from O(1/T^{2/3}) to O(1/T) ). Moreover, This paper provides the first linear convergence result for an error feedback method not relying on unbiased compressors.  Therefore, I tend to accept this paper at this point for its theoretical contribution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3hours"}, "extra_text": {}}, {"review_id": "I-_EvWs6zqi", "reviewer": "Reviewer_HmR5", "summary": "This paper introduces a new simple method for error feedback (or error compensation) for enhancing distributed compressed gradient descent-based (CGD) algorithms. The paper is well written, and theoretical and experimental results are convincing.  Some minor clarifications on the methods and related works could improve the understanding of this work. ", "questions": "", "limitations": "", "rating": 7, "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": "Strengths: \n- The paper is well written, reads easily, and most central ideas are communicated clearly. \n- Theoretical and empirical results showcase good performance gains.\n- Assumptions underlying the proposed method are simpler compared to competing alternatives. \n\nWeaknesses:\n- Some parts of the paper could benefit from further clarification: \n1. Why is $\\Psi$ used as a metric for Polyak-Lojasiewicz functions? \n1. Do Figs. 1, 2, and the experiments in the appendix indicate both uplink (from workers to server) and downlink (from server to workers) communication cost?\n\n-  There is some related work on quantizing gradient differences or innovations for federated learning, referenced below. How is this work different from the referenced ones? \n\n  - K. Mishchenko, E. Gorbunov, M. Takác, and P. Richtárik,“Distributed learning with compressed gradient differ-ences,”arXiv preprint:1901.09269, Jan 2019.\n\n  - S. Magnússon, H. Shokri-Ghadikolaei and N. Li, \"On Maintaining Linear Convergence of Distributed Learning and Optimization Under Limited Communication,\" in IEEE Transactions on Signal Processing, vol. 68, pp. 6101-6116, 2020, doi: 10.1109/TSP.2020.3031073.\n\n  - J. Sun, T. Chen, G. B. Giannakis, Q. Yang and Z. Yang, \"Lazily Aggregated Quantized Gradient Innovation for Communication-Efficient Federated Learning,\" in IEEE Transactions on Pattern Analysis and Machine Intelligence, doi: 10.1109/TPAMI.2020.3033286.\n\n\nOther comments: \n1. In line 24 of the abstract, there is a word missing in “can a large impact”\n1. In line 198 “If we new” should be “If we knew”.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is mainly theoretical work. The Societal impact depends on how the proposed method is applied to solve real problems.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper's strength and appeal is in proposing a simple modification to the Error Feedback mechanism that has both theoretical and empirical benefits.  The idea and mechanism proposed in the paper could have significant implications in important problems include distributed optimization and in optimization under various constraints (communication restricted, memory restricted, privacy restricted, etc).  The proposed EF21 mechanism is also nicely and clearly motivated and presented.  For these reason, I think the paper can make for an interesting oral presentation. 

The ACs and myself were disappointed by the the authors choosing to restrict the scope of the paper to presenting the core idea only, without much applications and extensions.  It is much more useful to the community and makes for a much stronger paper to include these in the paper, so as to justify importance of the core idea.  While the paper is certainly "acceptable" without them, in order to be a milestone paper and a foundational reference, these further applications and extensions are appropriate.  This is certainly much preferred to splitting the contribution into multiple papers each with 1 MPU (minimum publishable unit) worth of content.  In a sense the recommendation for an oral presentation is on credit, and based on the expectation that this will urge the authors to make the paper more comprehensive and complete.

I should also say that I found the comment regarding reviewer scores at a workshop entirely inappropriate.  While I appreciate the author's frustration with scores they disagree with, the author response is meant to point out factual issues with the reviews and address reviewer questions, and the authors also have the option of commenting on review quality.  But the paper should speak for it's own merit, and including recommendation letters for the paper, let alone vague and anonymous scores without justification, is not part of the reviewing process.  Furthermore, the criteria in a broad conference such as NeurIPS and in a technical workshop are different.  In particular, for a broad conference, it would be appropriate to include a better discussion and examples of applications and extensions so as to help show the significance of the results to the reviewers, as representatives of the general audience.
Decision: Accept (Oral)