EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
Year: 2022

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 O(1/T ) convergence rate for smooth nonconvex problems, beating the previous bound of O(1/T ), 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, can have a large impact on the practice of communication efficient distributed learning.

heading: 1 Introduction
text: 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 over-parameterized, which means that they involve more parameters than the number of available training data points [Arora et al., 2018]. Naturally, these circumstances should inform the design of optimization methods that could be most efficient to perform the training.
First, the reliance on sophisticated model architectures, as 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
*King Abdullah University of Science and Technology, Thuwal, Saudi Arabia. †This paper was written while Ilyas Fatkhullin was an intern at KAUST.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
computing [Verbraeken et al., 2019]. Due to its enormous size, the data needs to be partitioned across a 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
min 𝑥∈R𝑑
[︃ 𝑓(𝑥) def = 1
𝑛 𝑛∑︁ 𝑖=1 𝑓𝑖(𝑥)
]︃ , (1)
where 𝑥 ∈ R𝑑 represents the parameters of a machine learning model we wish to train, 𝑛 is the number of workers/nodes/machines, and 𝑓𝑖(𝑥) is the loss of model 𝑥 on the data stored on node 𝑖. We specifically focus on the development of new and more efficient communication efficient firstorder methods for solving (1) 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 1).
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 a connection between EF and EF21. Finally, experimental results are described in Section 5.

heading: 2 Background and Motivation
text: To better motivate our approach and contributions, we first offer a concise walk-through over the key considerations, difficulties, advances and open problems in this area.

heading: 2.1 Two families of compression operators
text: Compression is typically performed via the application of a (possibly randomized) mapping 𝒞 : R𝑑 → R𝑑, where 𝑑 is the dimension of the vector/tensor that needs to be communicated, with the property that it is much easier/quicker to transfer 𝒞(𝑥) 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., 2019a], or via a combination of these and other approaches [Horváth et al., 2019a, Beznosikov et al., 2020].
There are two large classes of compression operators 𝒞 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 𝒞 : R𝑑 → R𝑑 is an unbiased compression operator, or simply just unbiased compressor, if there exists a constant 𝜔 ≥ 0 such that
E [𝒞(𝑥)] = 𝑥, E [︀ ‖𝒞(𝑥) − 𝑥‖2 ]︀ ≤ 𝜔‖𝑥‖2, ∀𝑥 ∈ R𝑑. (2)
The family of such operators will be denoted by U(𝜔). Further, we say that a (possibly randomized) map 𝒞 : R𝑑 → R𝑑 is a biased compression operator, or simply just biased compressor, if there exists a constant 0 < 𝛼 ≤ 1 such that
E [︀ ‖𝒞(𝑥) − 𝑥‖2 ]︀ ≤ (1 − 𝛼) ‖𝑥‖2, ∀𝑥 ∈ R𝑑. (3)
The family of such operators will be denoted by B(𝛼). It is well known that, in a certain sense, the latter class contains the former. In particular, it is easy to verify that if 𝒞 ∈ U(𝜔), then (1 + 𝜔)−1𝒞 ∈ B(1/(1+𝜔)). However, the latter class is strictly larger, i.e., it contains compressors which do not arise via a scaling of an unbiased compressor. A canonical example of this is the Top-𝑘 compressor, which
preserves the 𝑘 largest (in absolute value) entries of the input, and zeros out the remaining entries, and for which 𝛼 = 𝑘/𝑑. We refer to [Beznosikov et al., 2020, Safaryan et 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 an appropriate way, greedy biased compressors, such as Top-𝑘, are often empirically superior to their unbiased counterparts [Seide et al., 2014], such as Rand-𝑘. 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., non-distributed) setting, albeit even here we do not have convincing theory that would explain this. Indeed, both Top-𝑘 and Rand-𝑘 impart the same distortion in the worst case, which happens when the energy is distributed uniformly across all entries of the input vector, and it 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 a separation can be made [Beznosikov et al., 2020]. While insightful, this is not satisfactory. Indeed, the gradients produced by methods such as gradient descent evolve in a 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 it 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 a 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 [Khirirat 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 [Horvá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],
v) achieve Nesterov acceleration in the strongly convex regime [Li et al., 2020],
vi) how to analyze these methods in the nonconvex regime [Mishchenko et al., 2019, Horváth et al., 2019a, Li and Richtárik, 2020],
vii) achieve acceleration in the nonconvex regime [Gorbunov et al., 2021], and even how to
viii) apply unbiased compressors to Hessian matrices to obtain communication-efficient secondorder 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 as 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 R3. However, divergence of gradient descent enhanced with biased compressors such as Top-𝑘 was observed empirically much sooner, and a fix for this problem, known as error feedback (EF), or error compensation (EC), was suggested by Seide et al. [2014]. This fix remained a heuristic until very recently.
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 data3 setting was performed by Beznosikov et al. [2020], 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 Gorbunov et al. [2020b], who developed the first linearly convergent methods EC-GD-DIANA and EC-LSVRG-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 et al. [2019] designed special types of biased quantization operators. However, these quantization schemes are unable to compress gradients below 𝒪 (𝑑)4, and the suggested methods require hyperparameters which cannot be efficiently estimated.

heading: In particular, whether it is possible to obtain a linearly convergent error-
text: compensated method in the general heterogeneous data setting, relying on general biased compressors only, is still an open problem.
The current state-of-the-art theoretical result for error-compensated methods in the smooth nonconvex regime are due to Koloskova et al. [2020, Theorem 4.1], 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 𝑇 communication rounds it is possible to find a random vector ?̂?𝑇 with the guarantee
E [︁⃦⃦ ∇𝑓(?̂?𝑇 ) ⃦⃦2]︁ = 𝒪 (︂ 𝐺2/3
𝑇 2/3
)︂ , (4)
under the bounded gradient assumption which requires the existence of a constant 𝐺 > 0 such that
‖∇𝑓𝑖(𝑥)‖2 ≤ 𝐺2 (5) holds for all 𝑥 ∈ R𝑑 and all 𝑖 ∈ {1,2, . . . ,𝑛}. This was a slight improvement in rate over an result obtained by Lian et al. [2017], who instead use the bounded dissimilarity assumption
1
𝑛 𝑛∑︁ 𝑖=1 ‖∇𝑓𝑖(𝑥) −∇𝑓(𝑥)‖2 ≤ 𝐺2. (6)
A summary of the limitations of known results for EF-based methods is provided in Table 1.
In this work we argue that the bounded gradients (5) and bounded dissimilarity (6) assumptions are too strong5, and that the sublinear rate (4) is not what one should expect from a good analysis of a well designed error-compensated firstorder method. Instead, one could hope for the faster 𝒪(1/𝑇) rate, which is what one obtains with methods using unbiased compressors [Gorbunov et al., 2021, Theorem 2.1]. The resolution of these issues is an open problem.

heading: 3 Summary of contributions
text: In this work we address and resolve the aforementioned challenges. Our key contributions are: 3Problem (1) 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. 4This is very limiting as in large scale learning, 𝑑 is enormous, and one usually needs to use dramatic sparsification such as Top-1. 5The bounded gradient (5) and bounded dissimilarity (6) assumptions are too strong as they are rarely satisfied. For example, neither hold even for simple quadratic functions. To see this, let 𝑓𝑖(𝑥) = 𝑥⊤A𝑖𝑥, where A𝑖 ∈ R𝑑×𝑑. Since ∇𝑓𝑖(𝑥) = B𝑖𝑥, where B𝑖 = A𝑖 + A⊤𝑖 , the bounded gradient assumption requires the vectors sup𝑥 max𝑖 ‖B𝑖𝑥‖ to be bounded, which is not the case, unless all matrices B𝑖 are zero. The bounded dissimilarity assumption (6), which can be written in the form 1
𝑛 ∑︀𝑛 𝑖=1 ‖(B𝑖 − 1 𝑛 ∑︀𝑛 𝑗=1 B𝑗)𝑥‖
2 ≤ 𝐺2, also does not hold, unless B𝑖 = B𝑗 for all 𝑖,𝑗, which reduces to the identical data regime, which is of limited interest.
Assumptions Complexity Theorem 𝑓𝑖 is 𝐿𝑖-smooth 𝑓 is lower bounded by 𝑓 inf E [︁⃦⃦ ∇𝑓(?̂?𝑇 ) ⃦⃦2]︁ ≤ 2(𝑓(𝑥0)−𝑓 inf )𝛾𝑇 + E[𝐺0]𝜃𝑇 2 𝑓𝑖 is 𝐿𝑖-smooth 𝑓 is lower bounded by 𝑓 inf 𝑓 satisfies PL condition E [︀ Ψ𝑇 ]︀ ≤ (1 − 𝛾𝜇)𝑇E [︀ Ψ0 ]︀ 3
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 a more aggressive variant, EF21+ (see Section 4.6), which has an even better empirical behavior. We show that if 𝒞 is deterministic, the same theorems capturing the convergence of EF21 hold for EF21+ as 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 H.

heading: 4 Main Results
text: 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 to the simplest first order method which uses biased compressors but does not employ error feedback: distributed compressed gradient descent (DCGD).
Let 𝑥𝑡 be the 𝑡-th iterate, shared by all 𝑛 nodes. Each node 𝑖 first computes its local gradient ∇𝑓𝑖(𝑥𝑡), compresses it using some 𝒞 ∈ B(𝛼), and sends the compressed gradient 𝒞(∇𝑓𝑖(𝑥𝑡)) to the master. The master aggregates all 𝑛 messages via averaging, and performs the optimization step
𝑥𝑡+1 = 𝑥𝑡 − 𝛾 𝑛 𝑛∑︁ 𝑖=1 𝒞(∇𝑓𝑖(𝑥𝑡)). (7)
As mentioned before, this method can diverge, even in simple quadratic problems in low dimensions [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 ∇𝑓𝑖(𝑥†) to be all zero, even if 𝑥† is the minimizer of 𝑓 , the application of 𝒞 to the gradients ∇𝑓𝑖(𝑥𝑡) will introduce a nonzero distortion even if 𝑥𝑡 ≈ 𝑥†. Indeed, in view of (3), all that can be guaranteed is that
E [︁⃦⃦ 𝒞(∇𝑓𝑖(𝑥𝑡)) −∇𝑓𝑖(𝑥𝑡) ⃦⃦2]︁ ≤ (1 − 𝛼) ⃦⃦∇𝑓𝑖(𝑥𝑡)⃦⃦2 ,
which can be large if the norm of ∇𝑓𝑖(𝑥𝑡) is large. So, the method is intrinsically unstable around 𝑥†, and hence can not converge to 𝑥†.
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 𝒞 to progressively vanishing vectors introduces progressively vanishing 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.

heading: 4.1 Markov compressors
text: Assume we are given a sequence of input vectors {𝑣𝑡}𝑡≥0 (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 a compressor 𝒞 ∈ B(𝛼). 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: {𝒞(𝑣𝑡)}𝑡≥0. However, while these estimates can be communicated efficiently, they are not getting “better”. That is, the distortion E [︁ ‖𝒞(𝑣𝑡) − 𝑣𝑡‖2 ]︁ 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, 𝑣*, we could output 𝑣* + 𝒞(𝑣𝑡 − 𝑣*) at iteration 𝑡 instead. Since 𝑣𝑡 → 𝑣*, the distortion between the input and the output at iteration 𝑡 is
E [︁⃦⃦ 𝑣* + 𝒞(𝑣𝑡 − 𝑣*) − 𝑣𝑡 ⃦⃦2]︁ = E [︁⃦⃦ 𝒞(𝑣𝑡 − 𝑣*) − (𝑣𝑡 − 𝑣*) ⃦⃦2]︁ (3)≤ (1 − 𝛼) ⃦⃦𝑣𝑡 − 𝑣*⃦⃦2 → 0.
So, the distortion issue is fixed! Moreover, if we assume the master knows 𝑣*, then the output vector at each iteration can be communicated cheaply as well, since all we need to communicate is the
Algorithm 1 EF21 (Single node)
1: Input: starting point 𝑥0 ∈ R𝑑, learning rate 𝛾 > 0, 𝑔0 = 𝒞(∇𝑓(𝑥0)) 2: for 𝑡 = 0,1, 2, . . . , 𝑇 − 1 do 3: 𝑥𝑡+1 = 𝑥𝑡 − 𝛾𝑔𝑡 4: 𝑔𝑡+1 = 𝑔𝑡 + 𝒞(∇𝑓(𝑥𝑡+1) − 𝑔𝑡) 5: end for
compressed vector 𝒞(𝑣𝑡 − 𝑣*). It will be useful to think of this operation as a new compressor, called 𝒞𝑣* , one that takes 𝑣𝑡 as an input, and gives 𝑣* + 𝒞(𝑣𝑡 − 𝑣*) as its output. That is, we can define
𝒞𝑣*(𝑣) def = 𝑣* + 𝒞(𝑣 − 𝑣*). (8)
While the compressor 𝒞𝑣* 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 𝑣𝑡 − 𝑣* → 0 to construct a 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 in constructing a compressor, let’s call it ℳ, such that the distortion between ℳ(𝑣𝑡) and 𝑣𝑡 vanishes as 𝑡 → ∞, then it must be the case that 𝑣𝑡 −ℳ(𝑣𝑡) → 0. So, we can compress this vanishing vector instead. This idea gives rise to the following recursive definition of ℳ:
ℳ(𝑣0) def= 𝒞(𝑣0) (9)
ℳ(𝑣𝑡+1) def= ℳ(𝑣𝑡) + 𝒞(𝑣𝑡+1 −ℳ(𝑣𝑡)), 𝑡 ≥ 0 (10) Note that (10) is similar to (8), with one key difference: we are using the previously compressed vector ℳ(𝑣𝑡), which is known, instead of the limit vector 𝑣*, which is unknown. This property also makes our new compressor non-stationary, i.e., it has a Markov property.
It is easy to establish (see Appendix B) that under some assumptions about the speed at which the input sequence 𝑣𝑡 converges to 𝑣*, it will be the case that E [︁ ‖ℳ(𝑣𝑡) − 𝑣𝑡‖2 ]︁ → 0. For instance, if
the convergence rate of the input sequence is linear, then the distortion will converge to 0. While this is 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.

heading: 4.2 Compressed gradient descent using the Markov compressor
text: For simplicity, consider solving problem (1) in the 𝑛 = 1 case, i.e., the problem
min 𝑥∈R𝑑 𝑓(𝑥), (11)
using the compressed gradient descent method featuring the Markov compressor. Start with 𝑥0 ∈ R𝑑, stepsize 𝛾 > 0, and let ℳ(∇𝑓(𝑥0)) = 𝒞(∇𝑓(𝑥0)). After this, for 𝑡 ≥ 0 iterate:
𝑥𝑡+1 = 𝑥𝑡 − 𝛾ℳ(∇𝑓(𝑥𝑡)) (12) ℳ(∇𝑓(𝑥𝑡+1)) = ℳ(∇𝑓(𝑥𝑡)) + 𝒞(∇𝑓(𝑥𝑡+1) −ℳ(∇𝑓(𝑥𝑡))). (13)
Note that the situation here is more complicated than the abstract setting described earlier since now there is interaction between the input sequence {∇𝑓(𝑥𝑡)}𝑡≥0 of gradients and the sequence ℳ(∇𝑓(𝑥𝑡)) of compressed gradients via the Markov compressor. Indeed, the output of ℳ at iteration 𝑡 influences the next iterate 𝑥𝑡+1 (via (12)), which in turn defines the next input vector 𝑣𝑡+1 = ∇𝑓(𝑥𝑡+1) in the sequence, and so on. To lighten up the heavy notation in (12) and (13), it will be useful to write 𝑔𝑡 = ℳ(∇𝑓(𝑥𝑡)). Using this new notation that hides the fact that 𝑔𝑡 is the application of the Markov compressor to the gradient, the method described above is formalized as Algorithm 1. This is precisely our proposed new variant of error feedback, EF21, specialized to the single node problem (11).
Algorithm 2 EF21 (Multiple nodes)
1: Input: starting point 𝑥0 ∈ R𝑑; 𝑔0𝑖 = 𝒞(∇𝑓𝑖(𝑥0)) for 𝑖 = 1, . . . , 𝑛 (known by nodes and the master); learning rate 𝛾 > 0; 𝑔0 = 1𝑛 ∑︀𝑛 𝑖=1 𝑔 0 𝑖 (known by master) 2: for 𝑡 = 0,1, 2, . . . , 𝑇 − 1 do 3: Master computes 𝑥𝑡+1 = 𝑥𝑡 − 𝛾𝑔𝑡 and broadcasts 𝑥𝑡+1 to all nodes 4: for all nodes 𝑖 = 1, . . . , 𝑛 in parallel do 5: Compress 𝑐𝑡𝑖 = 𝒞(∇𝑓𝑖(𝑥𝑡+1) − 𝑔𝑡𝑖) and send 𝑐𝑡𝑖 to the master 6: Update local state 𝑔𝑡+1𝑖 = 𝑔 𝑡 𝑖 + 𝒞(∇𝑓𝑖(𝑥𝑡+1) − 𝑔𝑡𝑖) 7: end for 8: Master computes 𝑔𝑡+1 = 1𝑛 ∑︀𝑛 𝑖=1 𝑔 𝑡+1 𝑖 via 𝑔 𝑡+1 = 𝑔𝑡 + 1𝑛 ∑︀𝑛 𝑖=1 𝑐 𝑡 𝑖 9: end for
4.3 Distributed variant of EF21
The main method of this paper, which we now present as Algorithm 2, is an extension of Algorithm 1 to the general finite-sum problem (1). In particular, we apply the Markov compressor individually on each node to the local gradients ∇𝑓𝑖(𝑥𝑡), and communicate the compressed gradients to the master. Recall that we only need to communicate the vectors 𝒞(∇𝑓𝑖(𝑥𝑡+1) − 𝑔𝑡𝑖) since the additive terms 𝑔𝑡𝑖 appearing in the Markov compressor were communicated in the previous round. Master then averages all gradient estimators, obtaining 𝑔𝑡+1 = 1𝑛 ∑︀𝑛 𝑖=1 𝑔 𝑡+1 𝑖 , which can be done by performing
the calculation 𝑔𝑡+1 = 𝑔𝑡 + 1𝑛 ∑︀𝑛 𝑖=1 𝑐 𝑡 𝑖, where 𝑔
𝑡 is the average from the previous round which the master maintains, and 𝑐𝑡𝑖 = 𝒞(∇𝑓𝑖(𝑥𝑡+1) − 𝑔𝑡𝑖) are the compressed messages. After this, the master takes a gradient-like step, and broadcasts the new model to all nodes.
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 𝒞, which are not met in practice, they are identical. Theorem 1. Assume that 𝒞 is deterministic, positive homogeneous and additive. Then EF (Algorithm 3; see appendix) and EF21 produce the same sequences of iterates {𝑥𝑡}𝑡≥0.
Note that while the Top-𝑘 compressor is deterministic and positively homogeneous, it is not additive. Likewise, compressors arising via rescaling of unbiased compressors are 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 new variant, EF21. This connection is also what justifies our naming decision: EF21 – error feedback mechanism from the year 2021.

heading: 4.5 Theory
text: We make the following assumption throughout:
Assumption 1 (Smoothness and lower boundedness). Every 𝑓𝑖 has 𝐿𝑖-Lipschitz gradient, i.e.,
‖∇𝑓𝑖(𝑥) −∇𝑓𝑖(𝑦)‖ ≤ 𝐿𝑖 ‖𝑥− 𝑦‖
for all 𝑥, 𝑦 ∈ R𝑑, and 𝑓 inf def= inf𝑥∈R𝑑 𝑓(𝑥) > −∞.
If each 𝑓𝑖 has 𝐿𝑖-Lipschitz gradient, then it is straightforward to check by Jensen’s inequality that 𝑓 is 𝐿-Lipschitz, with 𝐿 satisfying the inequality 𝐿 ≤ 1𝑛 ∑︀ 𝑖 𝐿𝑖. It will be also useful to definẽ︀𝐿 def= ( 1𝑛 ∑︀𝑛𝑖=1 𝐿2𝑖 )1/2. By the arithmetic-quadratic mean inequality, we have 1𝑛 ∑︀𝑖 𝐿𝑖 ≤ ̃︀𝐿. Let
𝐺𝑡 def =
1
𝑛 𝑛∑︁ 𝑖=1 ⃦⃦ 𝑔𝑡𝑖 −∇𝑓𝑖(𝑥𝑡) ⃦⃦2 , (14)
a quantity which will appear in both our theorems. In EF21 we use 𝒞 ∈ B(𝛼), where 0 < 𝛼 ≤ 1, and define 𝜃 = 1 − √ 1 − 𝛼 and 𝛽 = 1−𝛼
1− √ 1−𝛼 . We now formulate our first complexity result.
Theorem 2. Let Assumption 1 hold, and let the stepsize in Algorithm 2 be set as
0 < 𝛾 ≤ (︃ 𝐿 + ̃︀𝐿√︂𝛽
𝜃
)︃−1 . (15)
Fix 𝑇 ≥ 1 and let ?̂?𝑇 be chosen from the iterates 𝑥0, 𝑥1, . . . , 𝑥𝑇−1 uniformly at random. Then
E [︁⃦⃦ ∇𝑓(?̂?𝑇 ) ⃦⃦2]︁ ≤ 2 (︀𝑓(𝑥0) − 𝑓 inf )︀
𝛾𝑇 +
E [︀ 𝐺0 ]︀
𝜃𝑇 . (16)
Note that √︀ 𝛽/𝜃 = (1+ √ 1−𝛼) 𝛼 − 1 ≤ 2 𝛼 − 1 is decreasing in 𝛼. This makes sense since larger 𝛼
means less dramatic compression, which leads to smaller √︀
𝛽/𝜃, and this through (15) allows for larger stepsize, and hence fewer communication rounds. We now introduce the PL assumption, which enables us to obtain a linear convergence result.
Assumption 2 (Polyak-Lojasiewicz). There exists 𝜇 > 0 such that 𝑓(𝑥) − 𝑓(𝑥⋆) ≤ 12𝜇 ‖∇𝑓(𝑥)‖ 2 for all 𝑥 ∈ R𝑑, where 𝑥⋆ = arg min𝑥∈R𝑑 𝑓(𝑥). Theorem 3. Let Assumptions 1 and 2 hold, and let the stepsize in Algorithm 2 be set as
0 < 𝛾 ≤ min ⎧⎨⎩ (︃ 𝐿 + ̃︀𝐿√︂2𝛽 𝜃 )︃−1 , 𝜃 2𝜇 ⎫⎬⎭ . (17) Let Ψ𝑡
def = 𝑓(𝑥𝑡) − 𝑓(𝑥⋆) + 𝛾𝜃𝐺 𝑡. Then for any 𝑇 ≥ 0, we have
E [︀ Ψ𝑇 ]︀ ≤ (1 − 𝛾𝜇)𝑇E [︀ Ψ0 ]︀ . (18)
Our theorems hold for an arbitrary choice of the initial vectors {𝑔0𝑖 }, and not just for 𝑔0𝑖 = 𝒞(∇𝑓𝑖(𝑥0)). For instance, if 𝑔0𝑖 = ∇𝑓𝑖(𝑥0) is used, then E [︀ 𝐺0 ]︀
= 0, and the second term in (16) and the last term in E [︀ Ψ0 ]︀ vanish.
4.6 EF21+: Use 𝒞 or the Markov compressor, whichever is better
We now briefly describe 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 𝒞 and the Markov compressor generated. So, EF21+ can be thought of as a hybrid between DCGD (see (7)) and EF21. The decision about which compressor to use is made by each node 𝑖 individually, based on which of the distortions ‖𝒞(𝑠) − 𝑠‖ and ‖ℳ(𝑠) − 𝑠‖ is smaller, where 𝑠 = ∇𝑓𝑖(𝑥𝑡+1).

heading: 4.7 Dealing with stochastic gradients
text: In Section H (see Algorithm 5) we describe a natural extension of EF21 to the setting where full gradient computations are replaced by stochastic gradient estimators, i.e., we use a random vector 𝑔𝑡𝑖 ≈ ∇𝑓𝑖(𝑥𝑡). We also outline how convergence analysis is performed in this regime.

heading: 5 Experiments
text: We first consider solving a logistic regression problem with a non-convex regularizer,
𝑓(𝑥) = 1
𝑁 𝑁∑︁ 𝑖=1 log (︀ 1 + exp (︀ −𝑦𝑖𝑎⊤𝑖 𝑥 )︀)︀ + 𝜆 𝑑∑︁ 𝑗=1 𝑥2𝑗 1 + 𝑥2𝑗 , (19)
where 𝑎𝑖 ∈ R𝑑, 𝑦𝑖 ∈ {−1,1} are the training data, and 𝜆 > 0 is the regularizer parameter. We set 𝜆 = 0.1 in all experiments. At each set of experiments we use Top-𝑘 with 𝑘 = 1 [Alistarh et al., 2017] as a canonical example of biased compressor 𝒞.
Datasets. The datasets were taken from LibSVM [Chang and Lin, 2011], and were split into 𝑛 = 20 equal parts, each associated with one of 20 clients. The last part, of size 𝑁−20 · ⌊𝑁/20⌋, was assigned to the last worker. That is, we consider the distributed regime with heterogeneous data. A summary can be found in Table 3. The details on hardware and implementation can be found in Section A.
Experiment 1: Stepsize tolerance. In our first experiment (see Figure 1) we test the robustness/tolerance of 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 to work with larger or even much larger stepsizes.
Experiment 2: Fine-tuning 𝑘 and the stepsizes. We now showcase the superior communication efficiency of EF21 and EF21+ over classical EF. In this set of experiments, we fine-tuned 𝑘 (for Top-𝑘) and stepsizes individually for each method (details are given in Appendix A). For comparison, we also included distributed gradient descent (GD), which can be seen as EF21 with 𝑘 = 𝑑 (no compression), into the mix.
In Figure 2 we can see that in all cases, the proposed methods outperform EF in terms of the the number of bits sent to the server per client (bits/𝑛), 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. Further experiments, including deep learning experiments, are presented in Appendix A.

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

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.

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.