A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
Authors: Samuel Horváth
Peter Richtarik
Venue: ICLR 2021 Poster (2021)
Keywords: distributed optimization
communication efficiency

Abstract: Modern large-scale machine learning applications require stochastic optimization algorithms to be implemented on distributed computing systems. A key bottleneck of such systems is the communication overhead for exchanging information across the workers, such as stochastic gradients. Among the many techniques proposed to remedy this issue, one of the most successful is the framework of compressed communication with error feedback (EF). EF remains the only known technique that can deal with the error induced by contractive compressors which are not unbiased, such as Top-$K$ or PowerSGD.  In this paper, we propose a new and theoretically and practically better alternative to EF for dealing with contractive compressors. In particular, we propose a construction which can transform any contractive compressor into an induced unbiased compressor. Following this transformation, existing methods able to work with unbiased compressors can be applied. We show that our approach leads to vast improvements over EF, including reduced memory requirements, better communication complexity guarantees and fewer assumptions. We further extend our results to federated learning with partial participation following an arbitrary distribution over the nodes and demonstrate the benefits thereof. We perform several numerical experiments which validate our theoretical findings.

Published as a conference paper at ICLR 2021
A BETTER ALTERNATIVE TO ERROR FEEDBACK FOR COMMUNICATION- EFFICIENT DISTRIBUTED LEARN- ING
Samuel Horváth and Peter Richtárik
KAUST
Thuwal, Saudi Arabia
(samuel .hrvathh, peter. eettr.
ABSTRACT
Modern large-scale machine learning applications require stochastic optimization algorithms to be implemented on distributed compute systems. A key bottleneck of such systems is the communication overhead for exchanging information (e.g., stochastic gradients) across the workers. Among the many techniques proposed to remedy this issue, one of the most successful is the framework of compressed communication with error feedback (EF). EF remains the only known technique that can deal with the error induced by contractive compressors which are not unbiased, such as Top-K or PowerSGD. In this paper, we propose new and theoretically and practically better alternative to EF for dealing with contractive compressors. In particular, contractive compressor into an induced unbiased compressor. Following this transformation, existing methods able to work with unbiased compressors be applied. We show that our approach leads to vast improvements over EF, including reduced memory requirements, better communication complexity guarantees and fewer assumptions, We further extend our results to federated learning with partial participation following an arbitrary distribution over the nodes, and demonstrate the benefits thereof. We perform several numerical experiments which validate our theoretical findings.
propose construction which transform any
INTRODUCTION
We consider distributed optimization problems of the form
min f(x) = f(x,, #ER
(I)
where x E Rdd represents the weights of a statistical model we wish to train, is the number of nodes, and f:: Rd > IR a smooth differentiable loss function composed of data stored on worker In classical distributed machine learning scenario, fi(x)) = EçuD; (xr) is the expected loss of model æ with respect to the local data distribution D2 of the form, and fc: IRd + R is the loss on the single data point Ç. This definition allows for different distributions PI..... D, on each node, which means that the functions fi ...... .n have different minimizers. This framework covers Stochastic Optimization when either n = or all D; are identical, Empirical Risk Minimization (ERM), when fz()) can be expressed
finite average, i.e, fe(x)) 1 Σm fay(2) for some fiz Rd R. and m, Federated Learning (FL) (Kairouz al. (019) where each node represents client.
Communication Bottleneck. In distributed training, model updates (or gradient vectors) have to be exchanged in each iteration. Due to the size of the communicated messages for commonly considered deep models (Alistarh et al.) (2166), this represents significant bottleneck of the whole optimization procedure. To reduce the amount of data that has to be transmitted, several strategies were proposed.
One of the most popular strategies is to incorporate local steps and communicated updates every few iterations only (Stich 2019a Lin et al. 2018a Stich & Karimireddy 2020) Karimireddy et al.)

---

Published as a conference paper at ICLR 2021
2019a Khaled et al. 2020). Unfortunately, despite their practical success, local methods are poorly understood and their theoretical foundations are currently lacking. Almost all existing error guarantees dominated by simple baseline, minibatch SGD (Woodworth et al. 2020
In this work, we focus on another popular approach: gradient compression. In this approach, instead of transmitting the full dimensional (gradient) vector 9 E R one transmits compressed vector C(g). where C IRd + Rd is (possibly random) operator chosen such that C(g) can be represented using fewer bits, for instance by using limited bit representation (quantization) or by enforeing sparsity. A particularly popular class of quantization operators is based on random dithering (Goodall
195T. Roberts 1962); see (Alistarh et al., 2016; Wenn et al. 2017 Zhang et al.) 2017; Horváth
et al. 2019a| Samnezami-Kebry. et al.) 2019). Much sparser vectors can be obtained by random sparsification techniques that randomly mask the input vectors and only preserve a constant number of coordinates (Wangni et al. 2018 Konečný & Richtárik 2018 Stich et al., 2018 Mishchenko et al. 2019b] Vogels et al. 2019). There is also a line of work (Horváth et al. 201 9a| Basu et 2019) in which a combination of sparsification and quantization was proposed to obtain more aggressive effect. We will not further distinguish between sparsification and quantization approaches, and refer to all of them as compression operators hereafter.
Considering both practice and theory, compression operators can be split into two groups: biased and unbiased. For the unbiased compressors, Cgg) is required to be an unbiased estimator of the update g. Once this requirement is lifted, extra tricks are necessary for Distributed Compressed Stochastic Gradient Descent (DCSGD) (Alistarh al., 2016 2018 Khirirat et al., 2018) employing such compressor to work, even if the full gradient is computed by each node. Indeed, the naive approach can lead to exponential divergence (Beznosikov et al. 2020), and Error Feedback (EF) (Seide et al.) 2014 Karimireddy et al., 20196) is the only known mechanism able to remedy the situation.
Contributions. Our contributions can be summarized as follows:
When used within the stabilizing EF framework, biased compressors (c.g.. Top-K) can often achieve superior performance when compared to their unbiased counterparts (c.g.. Rand-K). This is often attributed to their low variance, However, despite ample research in this area, EF remains the only known mechanism that allows the use of these powerful biased compressors. Our key contribution is the development of simple but remarkably effective alternative and this is the only alternative we know of of-hhich we argue leads to better and more versatile methods both in theory and practice. In particular, we propose general construction that can transform any biased compressor, such as Top-K, into an unbiased one for which we coin the name induced compressor (Section 3 Instead of using the desired biased compressor within EF, our proposal is to instead use the induced compressor within an appropriately chosen existing method designed for unbiased compressors, such as distributed compressed SGD (DCSGD) (Khirirat al. 2018), variance reduced DCSGD (DIANA) (Mishchenko et al., (019g) or accelerated DIANA (ADIANA) (Li et al., 2020). While EF can bee seen as a version of DCSGD which can work with biased compressors, variance reduced nor accelerated variants of EF were not known at the time of writing this paper.
Induced Compressor:
Better Theory for DCSGD. As secondary contribution, we provide new and tighter theoretical analysis of DCSGD under weaker assumptions. If f is µ--uasi convex (not necessarily convex) and local functions f. are osmmoott (weaker version of L-smoothness with strong growth condition), we obtain the rate O (5, exp
NT [6_ -1)D+++2//m where o, + 6-1 and
8 > 1 is the parameter which bounds the second moment of the compression operator, and T is the number of iterations. This rate has linearly decreasing dependence on the number of nodes n. which is strictly better than the best-known rate for DCSGD) with EF, whose convergence does not improve as the number of nodes increases, which is one of the main disadvantages of using EF. Moreover, EF requires extra assumptions. In addition, while the best-known rates for EF (Karimireddy et al.) 2019b; Beznosikov et al., 2020) are expressed in terms of functional values, our theory guarantees convergence in both iterates and functional values. Another practical implication of our findings is the reduction of the memory requirements by half; this is because in DCSGD one does not need to store the eтror vector.
Partial Participation. We further extend our results to obtain the first convergence guarantee for partial participation with arbitrary distributions over nodes, which plays key role in Federated Learning (FL..
2

---

Published as a conference paper at ICLR 2021
Algorithm 1 DCSGD
Algorithm DCSGD with Error Feedback
17 1: Input: {1) Ik=0 > 0, To
Input: {17 ]k=0 1 > 0, 20. cf = Vi E [n]]
2: for k ===0 0.1, 1...... T do
2: for k 1,... -.. do
3: Parallel: Worker side
3: Parallel: Worker side
4: for :or.. do
for io ........ do
5: obtain 0f
5: obtain g
6: send A C* (g.") ) to master
6: send A = (17 g. + e. to master
7: [no need keep track of errors]
7: e, = of 9 + e A
8: end for
end for
9: Master side
9: Master side
10: aggregate A = +
aggregate A -=
11:
broadcast A to each worker
11: broadcast A to each worker
12:
Parallel: Worker side for mor==l..... do
12: Parallel: Worker side
13:
13: for 1..... n do
14: 2.+1 =xx A²
14: x =x A
15:
end for
15: end for
16: end for
16:
end for
Experimental Validation. Finally, provide experimental evaluation array of classifi- cation tasks with CIFARIO dataset corroborating our theoretical findings.
ERROR FEEDBACK IS NOT A GOOD IDEA WHEN USING UNBIASED COMPRESSORS
In this section we first introduce the notions of unbiased and general compression operators, and then compare Distributed Compressed SGD (DCSGD) without (Algorithm T and with (Algorithm) ? Error Feedback.
Unbiased vs General Compression Operators. We start with the definition of unbiased and general
compression operators (Cordonnier 2018; Stich et al. 2018 Koloskova et al. 2019).
Definition (Unbiased Compression Operator). A randomized mapping C: R + RR is an unbiased compression operator (unbiased compressor) if there exists such that
[(((=)) x, E. [[(((())) < ||
Va Rd
this holds, we will for simplicity write E U()).
Definition (General Compression Operator). A (possibly) randomized mapping C: IR Rd is general compression operator (general compressor) if there exists À >> and ò 2 1 such that
F. [AAC(x) - =11²] s (1 })) ||||
Va E Rd
If this holds, will for simplicity write C C(8).
The following lemma provides link between these notions (see, e.g. Beznosikov et al. (0200). Lemma 1. IfC U(6), then holds with
J. i.e. C C(8). That is, U(6) C C(8).
Note that the opposite inclusion to that established in the above lemma does not hold. For instance, the Top-K operator belongs to C()), but does not belong to U(8). In the next section we develop a procedure for transforming any mapping C I H (and in particular, any general compressor) into a closely related induced unbiased compressor.
Distributed SGD with without Error Feedback. In the rest of this section, compare the convergence rates for DCSGD (Algorithm [T) and DCSGD with EF (Algorithm 2p. We do this comparison under standard assumptions (Karimi al. 2016 Bottou et al. 2018 Necoara et al. 2019 Gower et al. 2019 Stich 2019b Stich & Karimireddy 2020). listed next.
First, assume throughout that has unique minimizer x², and let f f(x*) > -00.
3

---

Published as a conference paper at ICLR 2021
Assumption 1 (u-quasi convexity). f is u--quasi convex, i.e.,
f (z), x² - z) + ||0 x11?
Vr E R
(4)
Assumption 2 (unbiased gradient oracle). The stochastic gradient used in Algorithms I and 2 satisfies
E x²1 - V[((a*), Vi,k.
(5)
Note that this assumption implies E Assumption ((L, -expected smoothness). Function f is (4, om)-smooth if there exist constants L >> 0 and o² 2 0 such that vi E [n] and Vz E Rd
[ n Ex= of |x*] =f((**)
E
|
||]
S 2L(f((=*)) -1) + 0
(6)
E [1+E 221(((>)) (500-~))+ +
where f is the minimum functional value of f: and [n]] = (1,2.....
This assumption generalizes standard smoothness and boundedness of variance assumptions. For more details and discussion, see the works of Gower et al. (2019); (Stich (2019b). Equipped with these assumptions, we are ready to proceed with the convergence theory.
Theorem (Convergence of DCSGD). Consider the DCSGD algorithm with n 2 nodes. Let Assumptions 3
hold and C E I1(5), where on 6-1 +1. Let D = 21. > (f((())(**)))))) ft). Then
there exist stepsizes n7 S 26.,L 1 and weights wh 2 0 such that for all T 2 1 we have
E [[f( - f+] + mE |||--
x- 1|]]
Lr exp
exp
aT
+ 36
(8. 1)D
18,
where 70 = -11000 II, W Ex w and Prob(E" x²) w² //T
5 = 1 (no compression), Theorem 2 recovers the optimal rate of Distributed SGD Stich 2019b) If 5 > 1, there is an extra term (5,, 1ID in the convergence rate, which appears due to heterogenity of
data ( (=²" O, but Σi= C(V ((v](("")) + in general). In addition, the rate is negatively affected by extra variance due to presence of compression which leads I. - ó, T. and d²/n 60 60/nn.
Next we compare our rate to the best-known result for Error Feedback (Stich & Karimireddy 2020 (n = 1), (Beznosikov al. 2020) (n 2 1) used with C U(5) C C(8)
[f(=")- 0 (5L exp
uT 3L
5D+02 Pf
One can note several disadvantages of Error Feedback (Alg. 2 with respect to plain DCSGD (Alg. T. The first major drawback is that the effect of compression ō is not reduced with an increasing number of nodes. Another disadvantage that Theorem 2 implies convergence for both the functional values and the last iterate, rather than for functional values only as it is the case for EF, On top of that, our rate of DCSGD as captured by Theorem 2 does not contain any hidden polylogarithmic factor comparing to EF. Another practical supremacy of DCSGD is that there is no need store an extra vector for the error, which reduces the storage costs by a factor of two, making Algorithm| a viable choice for Deep Learning models with millions of parameters. Finally, one does not need to assume standard L-smoothness in order to prove convergence in Theorem 2 while, one the other hand, L-smoothness an important building block for proving convergence for general compressors due the presence of bias (Stich & Karimireddy 2020 Beznosikov et al., al, (020).. The only term in which EF might outperform plain DCSGD O ( (NT) for which the corresponding term O(60² ((802/nyTT) This is due to the fact that EF compensates for the error, while standard compression introduces extra variance. Note that this is not major issue as it is reasonable to assume 6/n = (11) or, in addition, o² = 0 weak growth condition holds /Vaswani et al. 2019), which is quite standard assumption, one can remove effect of g² by either computing full gradient locally or by incorporating variance reduction also discuss the way how to remove the effect of in Theorem? 2 Putting all together, this suggests that standard DCSGD (Algorithm [ is strongly preferable, in theory, to DCSGD with Error Feedback (Algorithm 2 for C E U()).
such SVRG (Johnson & Zhang, 2013). In Section
4

---

Published as a conference paper at ICLR 2021
3 INDUCED COMPRESSOR: FIXING BIAS WITH ERROR- CEROR-COMPRESSIO
In the previous section, we showed that compressed DCSGD is theoretically preferable to DCSGD with Error Feedback for C E U()). Unfortunately, C()) & U(6), an example being the Top-K compressor (Alistarh et al. 2018 Stich al. 2018 This compressors belongs to C( d ). but does not belong to U[ for any 6. On the other hand, multiple unbiased alternatives to Top- K have been proposed in the literature, including gradient sparsification (Wangni al. 2018) and adaptive random
sparsification (Beznosikov et al. 2020).
Induced Compressor: We now propose general mechanism for constructing an unbiased compres- sor C E U from any biased compressor Ci E C. We shall argue that it is preferable to use this induced compressor within DCSGD, in both theory and practice, to using the original biased compressor C₁ within DCSGD + Error Feedback.
Theorem 3. For Ci E C()i) with X == 1, choose C2 E (d2) and define the induced compressor via C(x) = Ci(x) + C2(1 C1 (zx)..
The induced compression operator satisfies C E U(ō) with 5 = 62 (1 1/6.) + 1/6.-
To get some intuition about this procedure, recall the structure used in Error Feedback. The gradient estimator is first compressed with C. (g) and the error = g - (g) is stored in memory and used to modify the gradient in the next iteration. In our proposed approach, instead of storing the error e, we compress it with an unbiased compressor C2 (which can be seen as a parameter allowing flexibility in the design of the induced compressor) and communicate both of these compressed vectors. Note that this procedure results in extra variance as we do not work with the exact error, but with its unbiased estimate only. On the other hand, there is no bias and error accumulation that one needs to correct for. In addition, due to our construction, at least the same amount of information is sent to the master as in the case of plain Ci (g): indeed, send both (g) and C2(e). The drawback of this is the necessity to send more bits. However, Theorem [3 provides the freedom in generating the induced compressor through the choice of the unbiased compressor Cz. In theory, it makes sense to choose C2 with similar compression factor to the compressor C₁ we are transforming as this way the total number of communicated bits per iteration is preserved, up to the factor of two.
Remark: The rtopk, Mr (z, y) operator proposed by Elibol et al. of our induced compressor with x y. C1 = Top-ki and Co
22200) can be seen as special case Rand-k2- K2
Benefits of Induced Compressor. In the light of the results in Section 2 we argue that one should always prefer unbiased compressors to biased ones as long as their variances 8 and communication complexities are the same, e.g., Rand-K K over Top-K. K. In practice, biased/greedy compressors are in some settings observed to perform better due to their lower empirical variance (Beznosikov et al. 2020). These considerations give a practical significance to Theorem 3 as we demonstrate on the following example. Let us consider two compressors: one biased C₁ E C(6)) and one unbiased C2 E U(d2), such that 81 62 8, having identical communication complexity. e.g.. Top-K and Rand-K. The induced compressor C(x) = C, (z) + C2(x - (x)) belongs to U(6g). where 53 - (1 ( 1) < 8. While the size of the transmitted message is doubled, one can use Algorithm since C is unbiased, which provides better convergence guarantees than Algorithm 2 Based on the construction of the induced compressor, one might expect that we need extra memory as "the error" g (g) needs to be stored, but during computation only. This is not an issue as compressors for DNNs are always applied layer-wise (Dutta et al.) 2019). and hence the size of the extra memory is negligible. It does not help EF, as the error needs be stored at any time for each layer.
|
EXTENSIONS
We now develop several extensions of Algorithm rellevant to distributed optimization in general, and to Federated Learning in particular. This is all possible due to the simplicity of our approach. Note that in the case of Error Feedback, these extensions have either not been obtained yet, or similarly to Section 2 the results are worse when compared to our derived bounds for unbiased compressors.
Partial Participation with Arbitrary Distribution over Nodes. In this section, we extend our results to variant of DCSGD utilizing partial participation, which is of key relevance to Federated
5

---

Published as a conference paper at ICLR 2021
10
NJ Ranc-1
Too 1+
102L
Top 1 EF
M0 Rand-1
Funcion vake
10
20t
101
10
10-7-
10-13
10
60
60
100
40
60
100
Iterat ons
Iterations
Figure Comparison Top-1 1 (+ EF) and NU Rand-1 1 on Example from Beznosikov al. (022))
Learning. In this framework, only a subset of all nodes communicates to the master node in each communication round. Such framework was analyzed before, but only for the case of uniform subsampling (Sattler et al. 2019 Reisizadeh et al., 2020). our work, we consider a more general partial participation framework: we assume that the subset of participating clients is determined by fixed but otherwise arbitrary random set- mapping S (a "sampling") with values in 2|n], where [n] = (1. n To the best of our knowledge, this is the first partial participation result for FL where an arbitrary distribution over the nodes is considered. On the other hand, this is not the first work which makes use of the arbitrary sampling paradigm; this was used before other contexts, e.g., for obtaining importance sampling guarantees for coordinate descent (Qu et al. 2013) primal-dual methods (Chambolle et al.) 2018), and variance reduction (Horváth & Richtárik 2019
Note that the sampling $ is uniquely defined by assigning probabilities to all 2n subsets of [n]. With each sampling S we associate probability matrix E R²*x" defined by P.; == Prob((i.]) }} C S). The probability vector associated with S is the vector composed of the diagonal entries of P: p = (PI......P. Pn) E IR", where P: = Prob(i E S). We say that is proper if p. > for all i. easy show that b = [|S]] Trace (P) = Pi, and hence b can be seen the expected number of clients participating in each communication round.
There
algorithmic changes due this extension: line of Algorithm does not iterate every node, only over nodes i S* where S* ~ S, and the aggregation step in line 9 is adjusted to lead to unbiased estimator of the gradient, which gives A LiEst mp. A.
To prove convergence, we exploit the following lemma.
Lemma 4 (Lemma 1, Horváth & Richtárik (2019).. Let S1, S.....,Sn be vectors in Rd and let Ç = E Ss be their average. Let E be proper sampling. Then there exists v E IR" such
P pp < Diag (p P2U2. ... ,,)
(8)
Moreover, ifS S, then
E
Σ FES
The following theorem establishes the convergence rate for Algorithm Srrithhm[wiii with partial participation.
Theorem 5. Let Assumptions 1 hold and C E U(8), then there exist stepsizes n² S
20gL and
weights w 2 0 such that
[[S(ET) - [+] + joE
100
x 1013]
S Lr exp 48,7 + 36 (6-0- (1
ur
where , W T. and D are defined in Theorem
ag = maxxejni (%/o..) J. and og bag (6-1)
For the case $ [n] with probability 1, one can show that Lemma holds with v 0, and hence we exactly recover the results of Theorem 2 In addition, we can quantify the slowdown factor with respect to full participation regime (Theorem 2b. which is 8 max p. assume the distribution S to be fixed, it can be easily extended to several proper distributions Sy 's we can even handle a block-cyclic structure with each block having an arbitrary proper distribution Sy over the given block j combining analysis with the results of Hichner al. (2019).
21, While in our framework we

---

Published as a conference paper at ICLR 2021
TemGrad EF Temßrad
70-
10a
60
Train
50
60
30-
10a3
20-
Temnrad
Tennrad
10
50
opochs
cpachs
Trasn loss
10"1
70-
10-2
60
50-
10"
TemGrad
TernGrad EF TemGraa
TemGrad
40
50
epochs
opochs
Figure Algorithm I vs. Algorithm 2 on CIFARIO with ResNet18 (bottom), VGG11 (top) and
TernGrad as compression.
Obtaining Linear Convergence. Note that in all the previous theorems, we can only guarantee a sublinear O1/r) convergence rate. Linear rate is obtained in the special case when D 0 and o² = 0. The first condition is satisfied, when f = fz() for all i E [n], thus when x* is also minimizer of every local function f.. Furthermore, the effect od D can be removed using compression of gradient differences, as pioneered in the DIANA algorithm (Mishchenko et al. 2019a). Note that a² 0 if weak growth condition holds (Vaswani et al., 2019). Moreover, one can remove effect of o² by either computing full gradients locally or by incorporating variance reduction such as SVRG (Johnson& & Zhang 2013). was shown by Horváth et al. (2019b) that both o² and D can be removed for the setting of Theorem 2 These results be easily extended to partial participation using our proof technique for Theorem 5 Note that this reduction is not possible for Error Feedback the analysis of the DIANA algorithm is heavily dependent the unbiasedness property. This
points to another advantage of the induced compressor framework introduced in Section 3
Acceleration. We now comment the combination of compression and acceleration/moomnttuu This setting is very important to consider as essentially all state-of-the-an methods for training deep learning models, including Adam (Kingma & Ba 2015 Reddi et al. 2018), rely on the use of
momentum in one form or another. One can treat the unbiased compressed gradient as a stochastic gradient (Gorbunov et al. 2020) and the theory for momentum SGD (Yang al., 2016] Gadat et al. L & Richtárik 2017) would be applicable with an extra smoothness assumption. Moreover, it is possible to remove the variance caused by stochasticity and obtain linear convergence with an accelerated rate, which leads to the Accelerated DIANA method (Li et al. 2020). Similarly to our previous discussion, both of these techniques are heavily dependent on the unbiasedness property. It is an intriguing question, but out of the scope of the paper, to investigate the combined effect of momentum and Error Feedback and see whether these techniques are compatible theoretically.
5 EXPERIMENTS
In this section, we compare Algorithms [ 2 for several compression operators. If the method contains + EF", " it means that EF applied, thus Algorithm is applied. Otherwise, Algorithm D is displayed. To be fair, we always compare methods with the same communication complexity per iteration. All experimental details can found in the Appendix.
Failure of DCSGD with biased Top-1. In this experiment, we present example considered in Beznosikov et al. (2020). which was used as a counterexample to show that some form of error correction is needed in order for biased compressors to work/provably converge. In addition, run experiments on their construction and show that while Error Feedback fixes divergence, it is still significantly dominated by unbiased non-uniform Sparsification(NU Rand-1), which works by only
7

---

Published as a conference paper at ICLR 2021
Rand K (Wangni et al.)
80-
K
Train l055
10"1
Top K
Induced comoressor
70-
10-2
50-
Rand-K < (Wlrggri all Tap-K
10"
40
Induced compressor
10
Top-K K
10
20
50
opochs
cpachs
80-
70-
60
Trase lo3s
50
Rand (Wangni
Rand K (Wangni
30
Top-K
Induced compressor
Induced compressor
Top K
Top K
50
epochs
opachs
Figure Comparison of different sparsification techniques with and without usage of Error Feedback on CIFARIO 10 with Resnet18 (top) and VGG1I (bottom). K = 5% d, for Induced compressor C₁ is Top-K/2 and C2 is Rand-K/2 (Wangni al.).
keeping non-zero coordinate sampled with probability equal to l=//Z_ [m],, where |z| denotes element-wise absolute value, as can be seen in Figure ! The details can be found in the Appendix.
compare Error Feedback for Unbiased Compression Operators. In our second experiment, the effect of Error Feedback in the case when an unbiased compressor is used. Note that unbiased
compressors are theoretically guaranteed work both with Algorithm [ and 2 We can see from
Figure that adding Error Feedback can hurt the performance; we use TernGrad (Wen et al.) 2017) (coincides with QSGD (Alistarh al., 2016) and natural dithering (Horváth et (2019a) with the infinity norm and one level) as compressors. This agrees with our theoretical findings, In addition. for sparsification techniques such as Random Sparsification or Gradient Sparsification (Wangni et al., 2018). we observed that when sparsity is set to be 10 %, Algorithm|] converges for all the selected values of step-sizes, but Algorithm 2
diverges and smaller step- needs be used. This is an important observation as many practical works (Li et al.) 2014 Wei et al. 2015 Aji & Heafield [2017] Hsieh et al. 2017 Lin et al. 20 2018b Lim et al. 2018) use sparsification techniques mentioned in this section, but proposed to use EF, while our work shows that using unbiasedness property leads not only to better convergence but also to memory savings.
Unbiased Alternatives to Biased Compression. In this section, we investigate candidates for unbiased compressors than can compete with Top-K, one of the most frequently used compressors. Theoretically. Top- is not guaranteed to work by itself and might lead to divergence (Beznosikoy et al. 2020) unless Error Feedback is applied. One would usually compare the performance of Top-K with EF to Rand-K, which keeps K randomly selected coordinates and then scales the output by d/K to preserve unbiasedness. Rather than naively comparing to Rand-K, we propose to use more nuanced unbiased approaches. The first one is Gradient Sparsification proposed by Wagni et al. (Wangni et al. 20188), which we refer to here as Rand-K (Wangni et al.), where the probability of keeping each coordinate scales with its magnitude and communication budget. As the second alternative, we propose to use our induced compressor, where C₁ is Top-a and unbiased part C2 is Rand-(K - a) (Wangni et al.) with communication budget K a. It should be noted that a can be considered as hyperparameter to tune. For our experiment, chose it to be K/2 for simplicity. Figure 3 suggests that our induced compressor outperforms all of its competitors as can be seen for both VGG11 and Resnet18. Moreover, induced compressor well as Rand-K K do not require extra memory to store the enror vector. Finally, Top-K without EF suffers a significant decrease in performance, which stresses the necessity of error correction.
8

---

Published as a conference paper at ICLR 2021
6 CONCLUSION
In this paper, we argue that if compressed communication is required for distributed training due to communication overhead, it is better to use unbiased compressors. We show that this leads strictly better convergence guarantees with fewer assumptions. In addition, we propose a new construction for transforming any compressor into an unbiased one using a compressed EF-like approach. Besides theoretical superiority, usage of unbiased compressors enjoys lower memory requirements. Our theoretical findings are corroborated with empirical evaluation.
As a future work we plan to investigate the question of the appropriate choice of the inducing compressor C. Our preliminary studies show that there is much to be discovered here, both in theory and in terms of developing further practical guidelines to those already contained in this work. The question (theoretically) optimizing for C₁ and C2 is difficult, as it necessitates a deeper theoretical understanding of biased compressors, which is currently missing. An alternative is to impose some assumptions on the structure gradients encountered during the iterative process, or to perform an extensive experimental evaluation desired tasks provide guidelines for practitioners.
REFERENCES
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, 2017.
Dan Alistarh, Jemry Li. Ryota Tomioka, and Milan Vojnovic. QSGD: Randomized quantization for communication-optimaa stochastic gradient descent. arXiv preprint arXiv: 161.022 2016.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advances Neural Information Processing Systems, pp. 5973 5983, 2018.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-SGDD Distributed SGD with quantization, sparsification and local computations. In Advances in Neural Information Processing Systems, pp. 11668-14679, 2019.
Aleksandr Beznosikov, Samuel Horvath, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint 2002:22002.124100 2020.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Antonin Chambolle, Matthias J Ehrhardt, Peter Richtárik, and Carola-Bibiane Schonlieb. Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications. SIAM Journal on Optimization, 28(4)2278322888 2018.
Cean-Baptiste Cordonnier. Convex optimization using sparsified stochastic gradient descent with memory. Technical report, 2018.
Aritra Dutta, El Houcine Bergou, Ahmed M Abdelmoniem, Chen- Ho, Atal Narayan Sahu, Marco Canini, and Panos Kalnis. On the discrepancy between the theoretical analysis and practical implementations of compressed communication for distributed deep learning. arXiv preprint arXiv:1911.08250, 2019.
Hubert Eichner, Tomer Koren, H Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi-cyelic stochastic gradient descent. arXiv preprint 19Xiv:1904.10120, 2019.
Melih Elibol, Lihua Lei, and Michael I Jordan. Variance reduction with sparse gradients. arXiv preprint XXI::2001.00623,, 2020.
Sébastien Gadat, Fabien Panloup. Sofiane Saadane, et al. Stochastic heavy ball. Electronic Journal of Statistics, ((1):461-529) 2018.
WM Goodall. Television by pulse code modulation. Bell System Technical Journal, 30(1):33-44 49, 1951.

---

Published as a conference paper at ICLR 2021
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory of sgd: Variance reduction, sampling, quantization and coordinate descent. In The 23rd International Conference on Artificial Intelligence and Statistics, 2020.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. Proceedings of the 36th International Conference on Machine Learning, Long Beach, California. 2019.
Benjamin Grimmer. Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity. SIAM Journal on Optimization, 29(2); (0122:3350-1300 2019.
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, pp. 770-778, 2016.
Samuel Horváth and Peter Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. Proceedings of the 36th International Conference on Machine Learning, 2019.
Samuel Horváth, Chen- Yu Ho, L'udovit 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 preprini arXiv:1904.05115. 2019b.
Kevin Hsieh, Aaron Harlap, Nandita Vijaykumar, Dimitris Konomis, Gregory R Ganger, Phillip B Gibbons, and Onur Mutlu. Gaia: Geo-distributed machine learning approaching LAN speeds. In 14th Symposium on Networked Systems Design and Implementation, pp. 629-647, 2017.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315 315-323, 2013.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewice condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-81 191-811. Springer, 2016.
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for on-device federated learning, arXiv preprint 1rXiv:190000337. 2019a.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signSGD and other gradient compression schemes. arXiv preprint arXiv: 191.v91901.09947, 201 9b.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprint 1806.066 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Published as conference paper at the 3rd International Conference for Learning Representations, San Diego 2015.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. arXiv preprint arXiv:1902.000 003400 2019.
Jakub Konečný and Peter Richtárik. Randomized distributed mean estimation: Accuracy vs. commu- nication. Frontiers in Applied Mathematics and Statisties, 4:62, 2018.
10

---

Published as a conference paper at ICLR 2021
Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. A simpler approach obtaining an (1/t)) convergence rate for the projected stochastic subgradient method. arXiv preprint arXiv:1212.2000 2012.
Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. In 1/th {USENIX] Symposium Operating Systems Design and Implementation ((OSDI) 14), pp. 583-598, 2014.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. arXiv preprint 2rXfv:2002./1364 2020.
Hyeontaek Lim, David G Andersen, and Michael Kaminsky. 3LC. Lightweight and effective traffic compression for distributed machine learning. arXiv preprint arXiv: /802.003880 2018.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local SGD. arXiv preprint arXiv: 0888.00721 2018a.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. ICLR 2018 International Conference on Learning Representations, 2018b.
Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods. arXiv preprint arXiv: 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: /901:::90000000000 2019a.
Konstantin Mishchenko, Filip Hanzely, and Peter Richtárik. 99% of parallel optimization is inevitably a waste of time. arXiv preprint arXiv: 1901::9900009939 2019b.
Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175(1-2)69--007, 2019.
Zheng Qu, Peter Richtárik, and Tong Zhang. Quartz: Randomized dual coordinate ascent with arbitrary sampling. In Advances in Neural Information Processing Systems, pp. 865-873, 2015.
Ali Ramezani-Kebrya, Fartash Faghri, and Daniel M Roy. NUQSGD: Improved communication efficiency for data-parallel SGD via nonuniform quantization. arXiv preprint arXiv: 2019.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. ICLR 2018 International Conference Learning Representations, 2018.
Amirhossein Reisizadch, Aryan Mokhtari. Hamed Hassani, Ali Jadbabaic, and Ramtin Pedarsani. Fedpaq: A communication-cfficti federated learning method with periodic averaging and quan- tization. In International Conference on Artificial Intelligence and Statistics, pp. 2021-2031, 2020.
Peter Richtárik and Martin Takáč. Parallel coordinate descent methods for big data optimization. Mathematical Programming, 156(1-2):433-484 2016.
Lawrence Roberts. Picture coding using neeudo-random noise. IRE Transactions Information Theory, 642):145154, 1962.
Felix Sattler, Simon Wiedemann, Klaus-Rober Müller, and Wojciech Samek. Robust and commanication-effeieen federated learning from non-iid data. IEEE transactions on neural networks and learning systems, 2019.
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 Fifleenth Annual Conference of the International Speech Communication Association, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. ICI. 2015 International Conference on Learning Representations, 2015.
11

---

Published as a conference paper at ICLR 2021
Sebastian U Stich. Local SGD converges fast and communicates little. ICLR 2019 International Conference on Learning Representations, 2019a.
Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint 10Xiv:9907.04322 2019b.
Sebastian Stich and Sai Praneeth Karimireddy. The frror-feedbcck framework: Better rates for SGD with delayed gradients and compressed communication. ICLR 2020 International Conference on Learning Representations, 2020.
Sebastian U Stich, Jcan-Baptin Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, pp. 4447-4455 2018.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1195-1204, 2019.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems, pp. 14236-14245, 2019.
Jianqiao Wangni, Jialei Wang, Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. In Advances in Neural Information Processing Systems, pp. 1299-1309, 2018.
Jinliang Wei, Wei Dai, Aurick Qiao, Qirong Ho, Henggang Cui, Gregory R Ganger, Phillip B Gibbons, Garth A Gibson, and Eric P Xing. Managed communication and consistency for fast data-parallel iterative analytics. In Proceedings of the Sixth ACM Symposium on Cloud Computing, pp. 381-394, 2015.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Tergrad: Temary gradients reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, pp. 1509-1519, 2017.
Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? arXiv preprint arXiv:2002.0788 2020.
Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint wwXiv:1604.03257 2016.
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Liu, and Ce Zhang. Zipml:
Training lincar models with end-to-end low precision, and little bit of deep learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 4035-0044 JMLR. org, 2017.
12

---

Published as a conference paper at ICLR 2021
TemGrad Temßrad
80-
70-
Trainloss
40
30
TemnGrad Temrraa
20
epochs
cpachs
10r
Temored EF TemGrad
10r3
1ra6
19"
TemrGaad
Ternörad
epochs
opachs
Figure Algorithm vs. Algorithm 2 on CIFARIO with ResNet18 (bottom), VGG11 (top) and TernGrad as compression.
APPENDIX
A EXPERIMENTAL DETAILS
To be fair, always compare methods with the communication complexity per iteration. We report the number of epochs (passes over the dataset) with respect to training loss and testing accuracy. The test accuracy obtained by evaluating the best model in terms of validation accuracy, A validation accuracy is computed based on 10 % randomly selected training data. We tune the step-size using based on the training loss. For every experiment, we randomly distributed the training dataset among 8 workers; each worker computes its local gradient- based on its own dataset. We used local batch size 32. All the provided figures display the mean performance with one standard error over 5 independent runs. For a fair comparison, we use the same random seed for the compared methods. Our experimental results are based on Python implementation of all the methods running in PyTorch. All reported quantities independent of the system architecture and network bandwidth.
Dataset and Models. We do an evaluation CIFARIO dataset. We consider VGG11 (Simonyan & Zisserman 2013) and ResNet18 (He et al. 2016) models and step-sizes 0.1, 0.05 and 0.01.
A.1 EXTRA EXPERIMENTS
Momentum. In this extra experiment, we look at the effect of momentum on Algorithm [ 2 We set momentum to 0.9. Similarly to Figure 2 we work with the unbiased compressor, concretely Tern- Grad (Wen al. 2017 (coincides with QSGD (Alistarh al. 2016) and natural dithering (Horváth) et al. 2019a) with the infinity norm and one level), to see the effect of adding Error Feedback. We can see from Figure that adding Error Feedback can hurt the performance, which agrees with our theoretical findings.
B EXAMPLE 1, BEZNOSIKOV ET AL. (2020)
In this section, we present example considered in Beznosikov al. (2020). which was used
counterexample to show that some form of error correction is needed in order for biased compressors to work/provably converge. In addition, while Error Feedback fixes divergence, it is still significantly dominated by unbiased non-u non-uniform sparsification can be seen in Figure The construction follows.
experiments their construction and show that
13

---

Published as a conference paper at ICLR 2021
Consider d = 3 and define the following smooth and strongly convex quadratic functions
fi(x) = (a, x)²² + |1011 f2(x) = (b, xb, |
fa(Ø) = (c, x²) + ||00||
where -(33,2,2), = -3, 12 -3). Then, with the initial point x = (1,1,1), 1> 0
ff2(2") (9. -11,9). Vfa(=")= t
Vfi(2 = 2( (11,99,9)
2 (9.9. -11).
Using the Top-1 compressor, we get
c(Vfs(z")) 20,00- (00-11.0), -(Vf(="))= = (0,00,
(0,0,
The next iterate of DCGD is
3 Σ
1)
11m) c(V)(()))) = (1+ 1+ 6
ra.
Repeated application gives x² (1 117 z0, which diverges exponentially fast to too since 6
1) >>
As initial point, we use T) in our experiments and we choose step size T. where L is smoothness parameter of 3/4 (fi + + fa). Note that vector is the unique minimizer of f.
C
PROOFS
C. PROOF OF LEMMA II
We follow which holds for C U(6).
cx)2) - 2 =1
[=)]]]
2/ (
[x))) .x) ||]]|
|||||
1
||-||
which concludes the proof.
14

---

Published as a conference paper at ICLR 2021
C.2 PROOF OF THEOREM 2
We use the update of Algorithm| 1 to bound the following quantity
E || 2=1 |x*]
||
x01
17
E
(C 2tth
2²)
|z*]
2
1
E
C+ (of")
1z0k
n
a| *
x"'
T/th
V ), -x") +
(n7²)²
E
C (of)) - o 11 +
g
x
n
1|
x=1 ||
)
E
(6 1) Σ
+
n2
||
x01
- n/² (V](x*),,* x* - -x*) +
2T (n((((²))))) - (*) + (ōn - -1) i=1
-(((0)) -13)) + (n)t)200²
- -mm 1|at - =2*11 -2n (1-
+
80²²
( (6n- 1)D1 +
11
Taking full expectation and 1/a S 26,I we obtain
E - =011p]] s (1 pmn*) E |1a** x" 2011]]
B||1at1-
-="" (fa")
f*] + (T-)3 (16.- 1)D + n
802
The rest of the analysis is closely related to the one of Stich 2019h). We would like to point out that similar results to Stichh (2019b) were also present in Lacoste-Julics al. 2012 Stich al. 2018 Grimmer 2019).
We first rewrite the previous inequality the form
k+1 S (1 an )r r/*s* st + (n²)²c,
(10)
where n* E ||aa* x*1| x=1]] s E [f(x*) - [r] a= pi, c (6n 1)D 60² n
We proceed with lemmas that establish a convergence guarantee for every recursion of type 10
Lemma 6. Let (r*) Jzz. Jez0 be as in (T)) for a > O and for constant stepsizes 1y* = rj vk 2 O. Then it holds for all T 2 O:
aT
S r exp
+ ad
d
Proof. This follows by relaxing 100) using F. [f(*t]
s 2 0,and unrolling the recursion
T-1
n $ (1 an)r 0z² s (1 an) Tr 0 + on
an)* s (1
an
o _
(11)
a
15

---

Published as a conference paper at ICLR 2021
Lemma 7. Let fr" Ik20. h=> vk 2 O, with parameter R =
h220 in [ 0 and for decreasing stepsizes n/" a(r+t))
2d and weights w = (K + k). Then
2ak²n ru
2c
w + or
T+I < 7
+
WT 0=0
aT
where W = -E w
Proof. We start by re-arranging 100 and multiplying both sides with w w
w - an"")) yr
1/t + on "
r/
a(k + (K + 2)r * a(x + 2 + c
S aa(k + 1)2, - a(x + k)2
where the equality follows from the definition of T7 and w and the inequality from (k + k)( 2) (xs
1)2 < (k + k 1)2. Again we have a telescoping sum:
T WT
a(k + T u
3x
c(T +1)
+
WT
WT
aW?
with
WT Σx w ok ( + (2x+T)(++1) T(T+1) 1
2
and W (2++))(T++))
2(x+T)147)
S (k + 7)2 for n.
2
By applying these two estimates we conclude the proof.
The convergence can be obtained as the combination these two lemmas.
Lemma 8. Let fr* 1220 h220 in (TOp. 0. Then there exists stepsizes 1/" S 3 and weighs w 0, WT = Ek_o k w such that
T
of
36c
w + T+1 < 32dro exp
+
WT
2d
aT
A=
Proof of Lemma
For integer
T 2 O, we choose stepsizes and weights as follows
T <
d
1/
1
# (1 - )
(k+1)
(1- a (kk+1)
g)
d'
d
r/a 1
if
and &s lo:
= 0, w (K k to)²
d
2
if and ls 2 to. n²
a
a(k + k to)
for
2d and to 11 We will now show that these choices imply the claimed result.
We start with the case T For this case, the choice 17 gives
w + T+ < a1 an) (T+1) To en
Po exp
lann (T + 1)] en
aT
< dr exp
d
aT
16

---

Published as a conference paper at ICLR 2021
If T d then we obtain from Lemma
6 that
af
to I r exp
2d
ad
From Lemma we have for the second half of the iterates:
Σ
s T+1==
1
Σ
s
ar
S
8an2pto
4c
WT
WT
T
aT
h=0
k=to
Now we observe that the restart condition f satisfies:
ak 2
rx2
exp
R²c
aT
4c
T
T
2d
dT
S
4ar
exp
2d
+
aT
because
These conclude the proof.
Having these general convergence lemmas for the recursion of the form (TO), the proof of the theorem
follows directly from Lemmas and 8 with = = o², d = 26, L It is easy to check that condition n²th T5,
is satisfied.
C.3 PROOF OF THEOREM 3
We have show that new compression is unbiased and has bounded variance. We start with the first property with = 1.
E (z) + C2(2 C1())) = Ec, [Ec, [1(() Cz(r - Cc(=C))CCCC Ee, [C + x C1(x) x;
where the first equality follows from tower property and the second from unbiasedness of Cz. For the second property, we also use tower property
E [[c)(() - x C2(x - C= = Ee, Ec, |[C - (((=))==+C( (z))
s <62 1)Ec, [|C(((t) x<|²]
S (82 1) (1- - 5, ||
where the first and second inequalities follow directly from and 33)
C.4 PROOF OF LEMMA HORVÁTH & RICHTÁRIK 2019
For the first part of the claim, it shown that P pp is positive semidefinite (Richtárik Takáč 2016), thus we can bound P pp" nDiag (P pp = Diag (p o v), where = nl| Ps). which implies that (8) holds for this choice of v.
For the second part of the claim, let 1iES 1 if E S and 1 = 0 otherwise. Likewise, let Lijes if i, and Li,E otherwise. Note that E E[Lees] p. and [Li,es]] = Paj. Next, let us compute the mean of == Eies Ge;
mp.
E E
=
E
Σ
E
Σ
n
1
Σ
"
4 E np
[ies]
Σ n
G = C. (12)
np;
np:
17

---

Published as a conference paper at ICLR 2021
Let A = (a1....,,0 anl R where a, St and let be the vector of all ones in R". We now
p:
write the variance of X in form which will be convenient establish bound:
E |X [X]]
E
|X
|[
E
Σ
||<1
REB
C.T Sj
= E
lijes
- -11-1
np: nipj
1.j
Ci Co
5 Ci
Σ
Pij
npi nops
Σ (pi) -p:P))a. aj
n
1
T ((P pp ) A ATA) A) e.
(13)
n²
Since by assumption we have P -pp 3 Diag (p o v), we can further bound
e
(Diag (po o A Σ Epviilaall
To obtain (). remains to combine this with 13
C.5 PROOF OF THEOREM 5
Similarly to the proof of Theorem 2. use the update of Algorithm
D to bound the following quantity
n
||a4tt 201 6
1
E
Σ
C²
(g)"),
x*
xx
l +
np;
iist
E
C* (aft)
1iot
mps
iESt
B S
|| l
x²
2
n (V fl (2*
) -x*)+ +
2
(2
E
ch (9 - 1 1
Σ
ch (oft)
100
+E
1
ch
(g*)
100))
np
72
iESN
100
x² 2
1/th (V [V](x*) )x - xx*)
(n
E
+6 8 6-1 || +
Σ x
lark
n²
Pi
(1 wr)²) )) ||/.* - x² -12- - -21 (1 -- (f(x*) -() +
802
( - 11D (1 + as)
n
Taking full expectation and x²*
< Z. we obtain
E ||aa*tl=** =01]]] < (1 um >
|
x011?
112] n [fx*)) - fr] + (n²² (6s (1-1)) + (1 as)
80²
n
The rest of the analysis is identical to the proof of Theorem 2 with only difference e = (6g - 1)D + 0g) da?
18


Reviews:
[{"review_id": "sdv5cFzU_7E", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper studies compression of gradients in distributed training with the goal of minimizing communication costs.  The main contribution of the paper is the development of an *induced compressor* that takes as input, a possibly biased compressor, and outputs an unbiased compressor with similar error variance as compared with the original compressor.  As the output of the induced compressor is unbiased, it obviates the need for error feedback, which is needed when biased gradient estimates are used.\n\nReason for Score:\n\nI vote for accepting the paper.  \n--> The idea of an induced compressor is simple (after the fact), and elegant, and advances state of the art in gradient compression. \n-->The paper has solid theoretical reasoning via a convergence analysis that does demonstrate that for certain (common) parameter choices the induced compressor is expected to have better convergence than the biased counter part\n-->   Satisfactory experiments to back up the theoretical insights. In particular, the output of the induced compressor requires more bits as compared with the underlying biased compressor. Empirical results show that, an induced compressor obtained from a class of biased compressors (e.g., top K gradients) has better performance than a biased compressor from that class with the same communication cost.\n\n\nPros:\n\n--> This paper resolves a problem of current gradient compression techniques: the good compressors that require a small number of bits/values to represent the gradients are inevitably biased, and the bias needs to be compensated via error feedback techniques. It shows that there are good unbiased compressors and provides a recipe for constructing them.\n\n--> The paper is well-written and based on a sound theoretical reasoning.\n\nCons:\n--> I would like a more detailed discussion on the effect of the unbiased compressor, that is used in the development of the induced compressor. How sensitive is the performance/compression to the choice of the unbiased compressor? \n--> I wonder how the theory would apply to weakly convex or non-convex settings. \n\n==================================\nComment after author responses.\nOn reading the author's responses to my (and other) review comments, my recommendation remains unchanged. This is a solid piece of work. \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "envU7SkBtlZ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an approach to reduce communication overhead in distributed training. The developed approach consists of a compressor operator (C(g)) that reduces the size of such messages (g). Specifically, the authors proposed a technique that transforms any biased compressor (e.g., Top-k) into an unbiased one, referred to as induced compressor, with better convergence guarantees and properties than the former. The advantages of the induced compressor are supported by a theoretical framework developed in the context of distributed compressed stochastic gradient descent (DCSGD). Moreover, the theoretical findings are validated with experiments in the CIFAR-10 dataset using two different image classifiers (Resnet-18 and VGG11 networks.).\n\nPros:\n- The contribution of the paper is very nice. The idea to turn a biased compressor into an unbiased one is appealing and makes totally sense to me.\n- The theory part is good and gives interesting insights.\n\nCons:\n- The experimental evaluation is not convincing. It is restricted to one dataset only. Why did the authors not perform experiments on a second dataset to validate the approach?\n- In my understanding one uses compression methods in FL to reduce the communication overhead. The proposed approach, however, seems to double the number of bits transmitted. The dimension \"transferred bits\" is missing in the experiments. I would like to see some comparison of Top-k + EF and the proposed approach wrt to bits transmitted vs. accuracy.\n- Does the proposed approach also work well for non-iid data? How does the approach work with methods combining sparsity and communication delay, e.g., Sparse Ternary Compression (Sattler et al. 2020).\n\nMore experimental evaluation is required to better understand the benefits and limits of the proposed method.", "extra_scores": {}, "extra_text": {}}, {"review_id": "TqmhCmn_PhL", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \n\nThis paper proposes a framework of compressed communication that can be used to deal with error induced by contractive compressors and can serve as a superior alternative to the existing framework (compressed communication with error feedback (EF)). The proposed framework outperforms EF in terms of memory requirement, communication complexity, and technical assumptions. The extension to federated learning with partial participation, and the numerical experiments on real-world dataset illustrate the applicability of this framework.\n\nStrength:\n\n1. The paper compares two algorithms, i.e., distributed compressed SGD (DCSGD) and compressed communication with error feedback (EF), by analyzing their convergence rates. The paper provides a new theoretical analysis for DCSGD, with weaker technical assumptions and tighter bounds.\n\n2. The induced compressor proposed in the paper can transform any biased compressor into an unbiased one, which can then be used in various existing methods designed for unbiased compressors.   \n\nComments: \n\n1. The paper concludes that the standard DCSGD algorithm is preferable to DCSGD with error feedback by comparing two algorithms' best-known convergence rates. It may not be appropriate because it is possible that the rate of standard DCSGD is theoretically tighter than that of DCSGD with error feedback (i.e., better theoretical bound). In other words, the difference in bounds of two algorithms is possibly due to the different theoretical analysis methods or different technical assumptions used in two algorithms, rather than the algorithm itself. How do those analysis methods used for finding convergence rates in two algorithms compared to each other? How can we make sure that the improvement is caused by the algorithm itself, but not the theoretical bounds?\n\n2. Federated learning with partial participation has been studied in other works. I suggest the authors citing these papers and highlighting the differences. For example,\n(1) Reisizadeh, Amirhossein, et al. \"Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization.\" International Conference on Artificial Intelligence and Statistics. 2020.\"\n(2) Sattler, Felix, et al. \"Robust and communication-efficient federated learning from non-iid data.\" IEEE transactions on neural networks and learning systems (2019).\n\n3. The benefit of using a biased compressor is its low variance; this is what improves the performance. However, if a biased compressor is transformed into an unbiased one using an induced compressor, then don't we lose the benefits of using such a biased compressor? What is the benefit of transformation using an induced compressor if the variance is not low anymore? Why not use an unbiased compressor (e.g., C2) directly? Is it because of the additional unbiased \"error feedback\" the induced compressor can provide?\n\n4. In experiments (Figure 3), authors compare various methods with one set of compressors (1) Rand-K; (2) Top-K + EF; (3) induced compressor with C1 = Top-K/2 and C2 = Rand-K/2; (4) Top-K, where K is a tunable parameter but is the same among all compressors. I wonder how their performances vary if the compressors use different values of K. For example, how do the compressor Rand-K/2 and the induced compressor with C1 = Top-K/2 and C2 = Rand-K/2 compare to each other (i.e., using unbiased C2 directly instead of transformation)? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "RXz31UUh8rL", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Quality and Clarity**\n\nThe paper is generally well written barring a few typos (see Queries and Suggestions below). The problem is clearly described and the solution is well motivated. The main theoretical result (Theorem 2) might be a bit hard to parse for readers unfamiliar with the theoretical results in this space but the overall explanation is clear.\n\n**Originality and Significance**\n\nThe main approach for converting biased compressor to unbiased compressors appears to be novel and flexible. The theoretical analysis of distributed compressed SGD using unbiased compressors can also be useful to the community since the derived upper bound can be easily applied to any unbiased compressor.\n\n**Strengths**\n\n1. The approach for converting biased compressors to unbiased compressor does not seem to have been stated in this fashion before and provides an elegant framework for combining previous approaches. \n\n2. The convergence analysis of unbiased compression is general and can be applied to any unbiased compressor and thus should be useful to the community as a whole.\n\n3. The proposed approach appears to be more flexible than biased compression + EF and the authors show how it can be extended to Federated Learning settings, and also admit techniques like variance reduction and acceleration using momentum.\n\n**Weaknesses**\n\n1. Neither the theoretical analysis (comparison of upper bounds) nor the experiments (comparisons for some specific biased and unbiased compressors) in this paper convincingly show that the proposed approach will always be theoretically and practically better than Error Feedback.\n\n2. The right choice of unbiased compressor $\\mathcal{C}_2$ for a given biased compressor $\\mathcal{C}_1$ is not clear. The authors show that if $\\delta_2 = \\delta_1$ then the upper bound of Theorem 2 will be tighter for the induced compressor $\\mathcal{C}$ than for $\\mathcal{C}_2$. However it is not clear if that will be enough to outperform EF since there will still be some extra variance. Indeed in the experiments the authors consider several unbiased compressors and while Top-a + Rand-(K-a) seems to beat Top-K + EF no general guidelines are offered.\n\n2. The flexibility of the proposed approach which makes it amenable to the extensions  in Section 4 is not illustrated in the experiments which are limited to a direct comparison of the proposed approach with EF.\n\n**Queries and Suggestions**\n\n1. Why do both $\\mathcal{C}_1(g)$ and $\\mathcal{C}_2(e)$ need to be communicated if $\\mathcal{C}$ is unbiased? (paragraph after Theorem 3)\n\n2. While I understand that it is probably not possible to demonstrate that the proposed approach will outperform EF in every single scenario, I believe including some guidelines about choosing biased and unbiased compressors appropriately will greatly increase the impact of this work. For eg. Are all combinations of biased and unbiased compressors acceptable? Should one just care about ensuring that $\\delta_1 = \\delta_2$? What are good choices of unbiased compressors for some popular biased compressors? If it is possible to answer these questions, the paper will definitely be more useful to readers.\n\n3. I would also recommend adding experiments on at least one of the extensions from Section 4 to highlight the flexibility of the proposed approach.\n\n4. Typos: \ni) Missing 'of' in Section 2, line 4.\nii) Last term in RHS of first equation in C.1 should be $+||x||^2$\niii) Missing '2L' in 3rd inequality in C.2\niv) Superscripts and subscripts have been interchanged in some terms in the proofs of Lemmas 6 and 7.\nv) Second term in LHS of first equation of C.3 should be $\\mathcal{C}_2(.)$\n\nOverall, while I am not quite convinced that the paper achieves its stated goal of showing that the proposed unbiased compression approach always outperforms biased compression + EF, I believe it adds enough to the discussion in this space to merit acceptance.\n\n**Comments after Author Response**\n\nI thank the authors for their response. My opinion of the potential of this paper to encourage further discussion in this area is unchanged. I can already see from the response on choice of biased and unbiased compressors to combine that there is plenty of scope for future work that builds on this idea. Regarding the comparison with EF, I appreciate the additional intuition provided in the author response on the drawbacks of EF and hope to see improvements to EF or more exhaustive comparisons between EF and the approach proposed in this paper in future work. As I had already recommended acceptance I am leaving my score unchanged. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I agree with the reviewers' comments. The technique proposed in the paper is very interesting, and although the method itself is not particularly surprising (it's "just" chaining two compressors), it's a really nice way of framing and studying the problem. On the other hand, the experiments _are_ relatively weak, and I think there is significant potential for improvement here (especially with an added 9th page of text). I encourage the authors to add some more convincing experiments in future versions of the paper.
Decision: Accept (Poster)