Natural Compression  for Distributed Deep Learning
Authors: Samuel Horváth
Chen-Yu Ho
Ludovit Horváth
Atal Narayan Sahu
Marco Canini
Peter Richtarik
Venue:  (2021)

Abstract: Modern deep learning models are often trained in parallel over a collection of distributed machines to reduce training time. In such settings, communication of model updates among machines becomes a significant performance bottleneck and various lossy update compression techniques have been proposed to alleviate this problem. In this work, we introduce a new, simple yet theoretically and practically effective compression technique: {\em natural compression ($C_{nat}$)}. Our technique is applied individually to all entries of the to-be-compressed update vector and works by randomized rounding to the nearest (negative or positive) power of two, which can be computed in a ``natural'' way by ignoring the mantissa. We show that compared to no compression,  $C_{nat}$ increases the second moment of the compressed vector by not more than the tiny factor  $\nicefrac{9}{8}$, which means that the effect of $C_{nat}$ on the convergence speed of popular training algorithms, such as distributed SGD, is negligible.  However, the communications savings enabled by $C_{nat}$ are substantial,  
leading to {\em $3$-$4\times$ improvement in overall theoretical running time}. For applications requiring more aggressive compression, we generalize $C_{nat}$ to {\em natural dithering}, which we prove is {\em exponentially better} than the common random dithering technique. Our compression operators can be used on their own or in combination with existing operators for a more aggressive combined effect, and offer new state-of-the-art both in theory and practice.

Under review as a conference paper at ICLR 2021
NATURAL COMPRESSION FOR DISTRIBUTED DEEP LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Modern deep learning models are often trained in parallel over collection of distributed machines to reduce training time. In such settings, communication of model updates among machines becomes significant performance bottleneck and various lossy update compression techniques have been proposed to alleviate this problem. In this work, we introduce a new, simple yet theoretically and practically effective compression technique: natural compression (Cnat). Our technique is applied individually to all entries of the to-be-compressed update vector and works by randomized rounding to the nearest (negative positive) power of two, which can be computed a "natural" way by ignoring the mantissa. We show that compared to compression, Cuat increases the second moment of the compressed vector by not more than the tiny factor 9/s, which means that the effect of Cnat on the convergence speed of popular training algorithms, such distributed SGD, is negligible. However, the communications savings enabled by Cuat are substantial, leading 3-4x improvement overall theoretical running time. For applications requiring more aggressive compression, we generalize Cuat natural dithering, which we prove is exponentially better than the common random dithering technique. Our compression operators can be used on their own or in combination with existing operators for a more aggressive combined effect, and offer new state-of-th--art both in theory and practice.
INTRODUCTION
Modern deep learning models (He et al. 2016) are almost invariably trained in parallel or distributed environments, which is necessitated by the enormous size of the data sets and dimension and complexity of the models required to obtain state-of-the-ar performance. In our work, the focus is on the fata-parallel paradigm, which the training data split across several workers capable of operating in parallel (Bekkerman et al., 2011 Recht et al. 2011). Formally, we consider optimization problems of the form
min f()) = Σ f(()). ZERd
where x E IRd represents the parameters of the model, n. is the number of workers, and fe: Rdd - TR is a loss function composed of data stored on worker i. Typically, fi modeled as function of the form fi(x) : EC-D, [z)], where D; is the distribution of data stored on worker i, and fo: IRd + R is the loss of model x on data point Ç. The distributions DI...., . Dn can be different on every node, which means that the functions f.....ff. may have different minimizers. This framework covers i) stochastic optimization when either
or all D; are identical, and ii) empirical risk minimization when fx( can be expressed as finite average, i.e, m. mi fij (x)) for some Sij Rd - IR.
Distributed Learning. Typically, problem (I) is solved by distributed stochastic gradient descent (SGD) (Robiins & Monro 1951, which works as follows: Stochastic gradients g, (I (x= are com- puted locally and sent to master node, which performs update aggregation g² Σ. (x(x*).
The aggregated gradient g² is sent back to the workers and each performs single step of SGD:
+++ = - xf g² where n > is step size.
A key bottleneck of the above algorithm, and of its many variants (c.g., variants utilizing mini- batching (Goyal et al. 2017). importance sampling (Horváth & Richtárik] 2019), momentum (Nes) terov 2013), variance reduction (Johnson & Zhang 2013)), is the cost of communication of the

---

Under review as a conference paper at ICLR 2021
typically dense gradient vector 9: (x"), and in a parameter-sever implementation with a master node, also the cost of broadcasting the aggregated gradient g². These are d dimensional vectors of floats, with d being very large in modern deep learning. It is well-known (Seide et al. [014 Alistarh et al., 2017 Zhang et al. 2017 Lin et al. 2018 Lim et al. 2018) that in many practical applications with common computing architectures, communication takes much more time than computation, creating a bottleneck of the entire training system.
Communication Reduction. Several solutions were suggested in the literature as a remedy this problem. In one strain of work, the issue is addressed by giving each worker "more work" to do, which results in better communication-to-com comomputttotttttioonnnnnn ratio. For example, one may use mini- batching to construct more powerful gradient estimators (Goyal et al., 2017). define local problems for each worker to be solved by a more advanced local solver (Shamir et al.. 2014| Richtárik & Takae 2016, Reddi et al., (016)) or reduce communication frequency (e.g., by communicating only once (McDonald et al. 2009 Zinkevich et al., 2010) or once every few iterations (Stich, 2018)),
An orthogonal approach to the above efforts aims to reduce the size of the communicated vectors instead (Seide et al., 2014 Alistarh et al. 2017 Wen et al. [017] Wangni et al. 2018] Hubara et al. 2017) using various lossy (and often randomized) compression mechanisms, commonly known in the literature as quantization techniques. In their most basic form, these schemes decrease the # bits used to represent floating point numbers forming the communicated d-dimensional vectors (Gupta et al.. 2015; Na et al., 2017), thus reducing the size of the communicated message by a constant factor. Another possibility is to apply randomized sparsification masks to the gradients (Suresh et al.. 2017]
Koncčny & Richtarik 2018 Alistarh et al., 2018 Stich et al.) (218)) or to rely on coordinate/bloce
descent updates-rules which are sparse by design (Fercoq et al. 2014).
One of the most important considerations in the area of compression operators is the compression- variance trade-off (Konečný& & Richtárik 2018 Alistarh et al., 2017 Horváth et al. 2019) For
instance, while random dithering approaches attain up to (( compression (Seide et al. 2014, Alistarh et al., 2017: Wen et al. (017), the most aggressive schemes reach (dd) compression by sending constant number of bits per iteration only (Suresh et al. 2017: Konečný & Richtárik 2018 Alistarh et al. [2018] |Stch et al., 2018). However, the more compression is applied, the more information is lost, and the more will the quantized vector differ from the original vector we want to communicate, increasing its statistical variance. Higher variance implies slower convergence (Alistarh et al.) 2017] Mishchenko et al., 2019), i.e., more communication rounds. So, ultimately, compression approaches offer a trade-off between the communication cost per iteration and the number of communication rounds.
Outside of the optimization for machine learning, compression operators very relevant optimal quantization theory and control theory (Elia & Mitter 2001: Sun & Goyal 2011 Sun et al. 2012).
Summary of Contributions. The key contributions of this work are following:
New compression operators. We construct a new "natural compression" operator (Cnati see Sec. 22 based on a randomized rounding scheme in which each float of the compressed vector is rounded to (positive or negative) power of 2. This compression has provably small variance, at most 1/s (see Thm D. which implies that theoretical convergence results of SGD-type methods are essentially unaffected (see Thm 6). At the same time, substantial savings are obtained in the amount of communicated bits per iteration (3.56x less for float32 and 5.82x less for float64). In addition, utilize these insights and develop new random dithering operator-naturel dithering (DPie; see Sec. 3) which is exponentially better than the very popular "standard" random dithering operator (see Thm We remark that Crat and the identity operator arise as limits of D and DP.s as s + 00, respectively. Importantly, our new compression techniques can be combined with existing compression and sparsification operators for a more dramatic effect State-of-the-at compression. When compared to previous state-of-the-art compressors such as (any variant of) sparsification and dithering-ttchniieee
argued before.
used in methods such as Deep Gradient Compression (Lin et al.) 2018). QSGD (Alistarh et al. 2017) and TernGrad (Wen et al. 2017) our compression operators offer provable and often large improvements in practice, thus leading to new state the art. In particular, given a budget on the second moment w 1 (see Eq (3) of a compression operator, which the main factor influencing the increase in the number of communications when communication compression is applied compared to no compression, our compression operators offer the largest compression factor, resulting in fewest bits transmitted (see Fig I..
Lightweight & simple low-level implementation. We show that apart from randomization pro- cedure (which is inherent in all unbiased compression operators), natural compression is computation- free. Indeed, natural compression essentially amounts to the trimming of the mantissa and possibly
2

---

Under review as a conference paper at ICLR 2021
1
2.5
4
Bio spociiaas
Figure 2: An illustration of nat. compression up with prohubil- ity 1-2.5 0.75, and (2.5))
Figure 1: Communication (in bits) vs. the second moment ss + 1 (see Ey (3) Jor several state of the art compreseers applied to a gradient of size d = 10 Our methods (Cuat and ) depicted with square marker. munication budget, natural dithering offers an exponential improvement on standard dithering, and whea used in composition with spersification. it offers an order of mag- nitude improvement.
plied to 2.5: Cunx
proh. 2-2-2" = 0.25. Thiis choice of probabilities en- that the compression operator unbiased, ie., E [Cuat (+)) = t.
any fixed com-
increasing the exponent by one. This is the first compression mechanism with such "natural" compatibility with binary floating point types.
Proof-of-concept system with in-network aggregation (INA). The recently proposed SwitchML (Sapio et al.) 2019) system alleviates the communication bottleneck via in-network aggregation (INA) of gradients. Since current programmable network switches are only capable of adding integers, new update compression methods are needed which can supply outputs in an integer format. Our natural compression mechanism is the first that is provably able to operate in the SwitchML framework as it communicates integers only: the sign, plus the bits forming the exponent of float. Moreover, having bounded (and small) variance, compatible with existing distributed training methods.
Bidirectional compression for SGD. We provide convergence theory for distributed SGD which allows for compression both at the worker and master side (see Algorithm [T.. The compression operators compatible with our theory form a large family (operators C E B(w) for some finite w 2 O: see Definition 2) This enables safe experimentation with existing and facilitates the development of new compression operators fine-tuned to specific deep learning model architectures. Our convergence result (Thm D applies to smooth and non-convex functions, and our rates predict linear speed-up with respect to the number of machines.
Better total complexity. Most importantly, we are the first to prove that the increase in the number of iterations caused by (a carefully designed) compression is more than compensated by the savings in communication, which leads to an overall provable speedup in training time. Read Thm 6 the discussion following the theorem and Table for more details. To the best of our knowledge, standard dithering (QSGD (Alistarh et al., 2017 is the only previously known compression technique able to achieve this with our distributed SGD with bi-directional compression. Importantly, our natural dithering is exponentially better than standard dithering, and hence provides for state-of-the -art performance in connection with Algorithm [
Experiments. We show that Cuat significantly reduces the training time compared to no compres- sion. We provide empirical evidence in the form scaling experiments, showing that Cuat does not hurt convergence when the number of workers is growing. We also show that popular compression meth- ods such as random sparsification and random dithering are enhanced by combination with natural compression or natural dithering (see Appendix (A]. The combined compression technique reduces the number of communication rounds without any noticeable impact on convergence providing the same quality solution.
2 NATURAL COMPRESSION
We define a new (randomized) compression technique, which we call natural compression. This is fundamentally function mapping t R to a random variable Craz (t) R. In case of vectors
& = (#i,..., T.) E Rdd we apply it in an element-wise fashion: (Cnat (x)) = Cn.r(1;). Natural compression Cust performs randomized logarithmic rounding of its input E R. Given nonzero I,
let IR be such that |t| = 2 (i.e., a logz [t). Then 2(0] < [|| = 2a < 2 a] and we round to
either sign())2lo),
to sign When t O, we set Caat (0) 0. The probabilities are chosen
so that Cnas (t) is an unbiased estimator of t, i.e., E [Caaa (t) = for all t. For instance, t = -2.75
will be rounded to either -4 or -2 (since - -2.75 S -2*), and / 0.75 will be rounded to either 1/2 or (since 2-1 < 0.75 < ). As a consequence, if is an integer power of 2, then Cunt.
will leave unchanged, see Fig.
3

---

Under review as a conference paper at ICLR 2021
Definition (Natural compression), Natural compression is random function Caat I ++ R defined as follows. We set (Oa = O. If + O, we let
Caa (t) = sign (t) Looza [f]], with p(t),
(2)
sign(() (1) 2 loga [e[], with 1 - -p(),
[logg [1]1-|e]
where probability p(() = 2 [N]]
Alternatively, (2) can be written as Ctar(t) sign(t): 22 141 + X(t)), where X(1)
Bernoulli(1 - p(t)); that is, X(1) = with prob. 1 - p(() and X(1) 0 with prob. p((). The key properties of any (unbiased) compression operator are variance, ease of implementation, and compression level. We characterize the remarkably low variance of Cuat and describe an (almost) effortless and natural implementation, and the compression it offers in rest of this section.
Cuat has a negligible variance: w = =1/s. We identify natural compression as belonging to large class of unbiased compression operators with bounded second moment (Jiang & Agrawal 2018 Khirirat al. 2018 Horváth et al. 2019), defined below.
Definition (Compression operators). A function C: Rdd -> Re mapping a deterministic input to a random vector is called compression operator (on Rd). We say that C is unbiased and has bounded
second moment (w 2 0) if
E [[((a)] x, EIIC(=)]I S (w 1|
Vz Rd..
(3)
C satisfies 1 we will write C E (ww).
Note that w 0 implies C(x) x almost surely. It easy that the variance of C(r) E B(w) is bounded as: [|C(x) - x|| S w ||=11| If this holds, we say that "C has variance w", The importance of (w() stems from two observations. First, operators from this class are known to be compatible with several optimization algorithms (Khirirat et al./ 2018 Horváth et al. 2019). Second, this class includes most compression operators used in practice Alisstrr et al. [011 Wen et al. [017] Wangni eet al., 2018 Mishchenko et al.) 2019). In general, the larger w is, the higher compression level might be achievable, and the worse impact compression has the convergence speed.
The main result of this section says that the natural compression operator Crat has variance 1/s.
Theorem 1. Cuat E B(//s).
Consider now similar unbiased randomized rounding operator to Caat; but one that rounds to one of the nearest integers (as opposed to integer powers of 2). We call it Cint- At first sight, this may seem like a reasonable alternative to Cuat. However, as we show next, Cint does not have a finite second moment and is hence incompatible with existing optimization methods.
Theorem 2. There is no w 2 0 such that Cint E ((w).
From 32 to 9 bits, with lightning speed. We now explain that performing natural compression of a real number in a binary floating point format is computationally cheap. In particular, excluding the randomization step, Crat amounts to simply dispensing off the mantissa in the binary representation. The most common computer format for real numbers, binary32 (resp. binary64) of the IEEE 754 standard, represents each number with 32 (resp. 64) bits, where the first bit represents the sign, 8 (resp. 11) bits are used for the exponent, and the remaining 23 (resp. 52) bits are used for the mantissa. A scalar t E R is represented in the form (s, (s,07, C6...., Cu, m1, M2, m223,, where
7
s,e,, my E {0,1) are bits, via the relationship t = (-1)* x 22-127 127 x (1 (1+m), == Σ e,2;, m 1=0
2 where is the sign, is the exponent and is the mantissa. A binary32 representation
of l -2.75 is visualized in Fig 4 In this case,
1, e7 1. ma mg 1 and hence
1 -= (-1)* x 22- x (1 + m)
x x (1 + 2 + 2-33 )= - 2.75.
clear that 0 S m 1, and hence 2 127
S |t| 126 Moreover, p(t)
12-126
2
2 - 11/ = m. Hence, natural compression of t represented as binary32 given as follows:
(-1)* 22-127 with probability 1-m. m,
(ta ( (-1)* x 22-12 with probability m.
4

---

Under review as a conference paper at ICLR 2021
Figure 3: Randomized rounding for natural (left) and standard (right) dithering (s levels).
Figure 4: IEEE 754 single-precision binary maaling-point format: binary32.
Observe that (-1)* 2c-127 is obtained from by setting the mantissa m zero, and keeping both the sign and exponent e unchanged. Similarly, (-1)* | x 2c-126 is obtained from by setting the mantissa m zero, keeping the sign 8, and increasing the exponent by one. Hence, both values can be computed from t essentially without any computation.
Communication savings. In summary, in case of binary32, the output Cnar(t) of natural compres- sion is encoded using the 8 bits in the exponent and an extra bit for the sign. This is 3.56x less communication. In case of binary64, we only need 11 bits for the exponent and bit for the sign, and this is 5.82x less communication.
Compatibility with other compression techniques We start with a simple but useful observation about composition of compression operators.
Theorem 3. JfC; B(wi) and C2 E Bl(2)), then C C2 E B(w12), where w12 wiw2 + w1 + w2, and C₁ o C2 is the composition defined by (C1 C
Combining this result with Thm. we observe that for any C E B(w), we have C E 1(0w/++1/s) Since Guat offers substantial communication savings with only negligible effect on the variance of C, key use for natural compression beyond applying as the sole compression strategy is to deploy it with other effective techniques as final compression mechanism (e.g.. with sparsifiers (Stich et al.) 2018)), boosting the performance of the system even further. However, our technique will be useful also as a post-compression mechanism for compressions that do not belong to B(w) (e.g.. TopK sparsifier (Alistarh et al. 2018)) ). The same comments apply to the natural dithering operator D defined in the next section.
NATURAL DITHERING
Motivated by the natural compression introduced See here we propose new random dithering operator which we call natural dithering. However, it will be useful to introduce more general dithering operator, one generalizing both the natural and the standard dithering operators. For 1 1sps +0c, let ||>||,, be p-norm: ||>||p- = (
Definition (General dithering). The general dithering operator with respect to the norm and with 1 < lo 1, denoted DC.v. is defined follows. Let 2 E Rdd If x = 0, we let DC.p.s (x) - 0. If + O. we let yi = / for all E [d]. Assuming C(I+= x sign(x;) x E(H)), where C E B(w) for some w 2 0 and E(v:) is random variable equal to I,, with probability T. 1
levels 0- 1g < 1--1 1 <
gen
8 1u+1 S y < lg for some E {0, 1, 1}. we let (DC..*(r))
Wi-be1
and to hu+1 with probability L.-W 1--1o11
Note that E [E(v:)] [[]]:)]=]] yt.
Standard (random) dithering, Diu.. Goodall 1951 Roberts 1962) is obtained as a special case of general dithering (which is also novel) for linear partition of the unit interval, 1--1 1/. 2/2. ..... (s-1)/s and C equal to the identity operator. D2.; operator was used in QSGD Alistarh et al. 2017) and D in Temgrad (Wen al. 2017). Natural dithering novel compression operator introduced in this paper- arises as special case of general dithering for C being an identity operator and a binary geometric partition of the unit interval: 1,-1 = 21- 21-2,1,-2 = 22-2 ...., = 2-1 For the INA application, we apply C = C.at to have output always in powers of 2, which would introduce extra factor of 9/s in the second moment. A comparison the & operators for the standard and natural dithering with gradients, each worker communicates the norm (1 float), vector of signs (d bits) and efficient encoding of the effective levels for each entry i 1, 2, ... . d. Note that D is essentially an application of Caat to all normalized entries x. with two differences: i) we can also communicate the compressed norm | ii) in Cuat the interval [0, 2 21-3] is subdivided further, to machine precision, and in this
levels applied to & 3/8 can be found in Fig When DC.P.* is used compress
5

---

Under review as a conference paper at ICLR 2021
Approach
Cw;
No. iterations
Bits per Iter.
Speedup
T (ww) = O(www + 1)
Wi + M
Factor
Baseline
identity
32d
New
Cuse
(9/s)
9d
3.2x-3.6x
Sparsification
54
(4/4)*
(33 + logg d)q
0.6x-6.0x
New
Cuas o Sa
(9i//s0)
(10 + log2 d)4
1.0-110.7x
Dithering
D
31 d(2 + 8)
1.8x-15.9x
New
D
(9/8 + nd a 2'00
31 d(2 log,
4.1x-16.0x
Baseline variant without compression. Speed measured hy multiplying the # communication rounds (ie., iterations T(ww) )1 by the bits sent from worker i to master (W; - M) per iteration. We noglect M W. communication in practice this often mach faster (sco e.g. (Mishebenko et (211)) for other cost/spced model see Appendix(D.] We do not just resitict to this scenario and We assume binary32 representation. The relativ # iterations sullicient to guarantec e optimality is (ww) == (ww + I)?, where e E (0, 1] (see Thm 0 Note that in the big n regime the iteration bound T(aw) ) is hetter to
Table The overall speedup of distributed SGD with compression nodes via Cw,
dithering. The Speedup Factor (T(wW) bik figures were calculated for d 10 0.1d 0.1d (10% sparsity). p = 2 and optimal choice of with respect speeduup.
(bowever,
very practical
usually small), while small
min (p. 2). x min(1, V72'-1). ).
lower bound for the Speedup Factor obtained
the upper
(0)-322
sense D can be seen as a limited precision variant of Cnat. As is the case with Cuat, the mantissa is ignored, and one communicates exponents only. The norm compression is particularly useful on the master side since multiplication by naturally compressed norm is just summation of the exponents. The main result of this section establishes natural dithering as belonging to the class B(w):
Theorem 4. D nat E B(w), where w = 1/8 + d'/-2>-* min {1, (1,'"/21-*) and r = min 2}.
To illustrate the strength of this result, we now compare natural dithering D to standard dithering Daa and show that natural dithering is exponentially better than standard dithering. In particular, for the same level of variance, DR. uses only levels while Dr.. uses 2* levels. Note also
that the levels used by Diat form a subset of the levels used by D (see Fig 22 We also confirm this empirically (see Appendix ...
Theorem 5. Fixing 8, natural dithering D has O(2e-1/s) times smaller variance than standard nst dithering D Fixing w, if 2*-1, then DP.. E B(w) implies that D BB9/s(w + 1) 1).
4 DISTRIBUTED SGD
There are several stochastic gradient-type methods (Robbins & Monro 1951 Bubeck al., 2015
Ghadimi & Lan 2013 Mishchenko et al. (219)) for solving ( that are compatible with compression
operators C B(w). and hence also with our natural compression (Cnat) and natural dithering (Dine) techniques. However, as none of them support compression at the master node we propose distributed SGD algorithm that allows for bidirectional compression (Algorithm in Appendix [D.I]. We note that there are two concurrent papers to ours (all appeared online in the same month and year) proposing the use bidirectional compression, albeit conjunction with different underlying algorithms, such as SGD with error feedback or local updates (Tang et al. 2019 Zheng et al., 2019). Since we instead focus on vanilla distributed SGD with bidirectional compression, the algorithmic part of our paper is complementary theirs. Moreover, our key contribution the highly efficient natural compression and dithering compressors- can be used within their algorithms as well, which expands their impact further.
We assume repeated access to unbiased stochastic gradients g;(x with bounded variance of for every worker i. We also assume node similarity represented by constant ÇZ and that f is L-smooth (gradient is L-Lipschitz). Formal definitions as well as detailed explanation of Algorithm I can be found in Appendix D We denote <² Ei 02 Σ" of and
(wM+1)((wrg +1) o² + (war +1ww
2 8 = 1 WM
(was +1)w
(4)
where CM E B(WM) is the compression operator used by the master node, Cw, E B(ww.) are the compression operators used by the workers and ww == max WW.

---

Under review as a conference paper at ICLR 2021
Gur No Compression
Cus
Compresion
0.8
Treeping
0.2
80
120
180
220
240
200
220
20
50
60
110
1.0
C-r Compression on
No Compression in
souraay
Trantrg
Trainegton
0.6
2:0 bale
0.5
85
14
0.2
0.0
100 120
200
6:0
1200 1300
2300
300
900
1300 1800 2303
Timess)
Figure 5: Train Loss and Test Accuracy of ResNetl and Alexnet CIFARIO. Speed-up is displayed with respect to time to execute fixed number of epochs, 320 and 200, respectively.
data transferred (GB)
200
In
Compresa Herwenk
254
speedup
100
19912
19916
19919
alaznet
proglennt
Icaption3
Incoption
remet50
(Ronato01
Uime(5)
Figure 7: Accumulated transmission size of 1 worker (CIFARIO on AlexNet).
Figure 6: Training throughput speedup.
60
60
ksniing 8u5
Guc
x2t x2 Gac
40
40
19
None
None
200
01
Gue
0.00
0.25
0.50
0.75
1.00
20
40
65
0.50
0.25
0.50
0.75
1.50
20
40
60
2415
spocts
bits
epachs
Figure 8: Train loss and test Aacuracy of VGGI1 on CIFAR1O. Green line: Cw. = D2222 Cas identity. Blue line: Cw: = 22. nat Cm = Cuat-
Theorem 6. Let Cm E (((M)) Cw, B(ww.) and 1/ 20L2/) where a, 8 are in (4 If a is picked uniformly at random from {0. 1.... 1), then 2(f(=))-(a")) + aLn E [[I < 7(2-BL7)T
(5)
2-BLn
where xt is an opt. solution of [T.. In particular, if we fix any and choose L(a+ep) and then E [IV]((")]] Se.
T >
The above theorem has some interesting consequences. First, notice that (5) posits O(1/r) conver- gence of the gradient norm to the value .م which depends linearly a. In view of 4 the more compression we perform, the larger this value becomes. More interestingly, assume
2-3Ly,
that the same compression operator is used at each worker: Cw = Cw.- Let Cw E B(ww)) and CM E B(WM) be the compression on master side. Then, T(war, complexity. In the special case of equal data on all nodes, i.e., ( = 0, we get a (w)+ +1)0 / and (wM+11 (1+ww/n) If no compression is used, then ww WM 0 and a+ t/t. So. the relative slowdown of Algorithm I used with compression compared to Algorithm used without compression is given by
2L(f(=")~ f(x )) (a++5)) its iteration
T(mm_ww) 2(0,0)
(WM + 1)
(wo+
+(--w//n)e // /ntt)) E (WM + 1, (WM + () + +1]]
The upper bound is achieved for n = (or for any n and E + 0), and the lower bound is achieved in the limit co. So, the slowdown caused by compression on worker side decreases with
7

---

Under review as a conference paper at ICLR 2021
In-Network
0.8
Aggregatton
Compression
3
-500
Ges:
0.5
Gar deterministic
ATE/s line
203
200
all relured
[02
100
ATEIs line rate (INA)
6- Comprnonee Auaten
ATE/S at line rate (Crat)
Number workers
Eooch
20
50
Figure 9: Violin plot of Aggregated Tensor Elements (ATE) per second. Dashed lines denote the maximum ATE/s under line rate.
Figure 10: Convergence com- parison for weak scaling.
More importantly, the savings in communiication due to compression outweigh the iteration slowdown, which leads to an overall speedup! See Table for the computation of the overall worker to master speedup achieved by our compression techniques (also see Appendix D.7 for additional similar comparisons under different cost/speed models). Notice that, however, standard sparsification does nor necessarily improve the overall running time- it can make it worse. Our methods have the desirable property of significantly uplifting the minimal speedup comparing to their "non-natural" version. The minimal speedup is more important as usually the number of nodes is not very big.
EXPERIMENTS
To showcase properties of our approach in practice, we built a proof-of-concept system and provide evaluation results. We focus on illustrating convergence behavior, training throughput improvement, and transmitted data reduction. Experimental setup is presented in Appendix B
Results. We first elaborate the microbenchmark experiments of aggregated tensor elements (ATE) per second. We collect time measurements for aggregating 200 tensors with the size of 100MB, and present violin plots which show the median, min, and max values among workers. Fig shows the result where we vary the number of workers between 4 and 8, The performance difference observed for the case of Cuat. along with the similar performance for Cnat deterministic indicate that the overhead of doing stochastic rounding at the aggregator is bottleneck.
We then illustrate the convergence behavior by training ResNetl 10 and AlexNet models on CIFAR1O. 10. Fig [ shows the train loss and test accuracy over time. We note that natural compression lowers training time by ~ 26% for ResNet1 10 (17% more than QSGD for the same setup, see Aliitarrh al. (211)) (Table 1)) and 66% for AlexNet, compared using no compression, while the accuracy matches the results in (He et al.) 2016) without any loss of final accuracy with the same hyperpa- rameters setting, while training loss is not affected by compression. In addition, combining Cuat with other compression operators, we can see no effect in convergence, but significant reduction in communication, e.g., 16x fewer levels for D w.r.t. D see Fig and for other compressions see in Appendix.
Fig
Next, we report the speedup measured in average training throughput while training benchmark CNN models on Imagenet dataset for one epoch. The throughput is calculated as the total number of images processed divided by the time elapsed. Fig 6 shows the speedup normalized by the training throughput of the bascline, that is, TensorFlow Horovod using the NCCL communication library. We further break down the speedup by showing the relative speedup of In-Network Aggregation, which performs no compression but reduces the volume of data transferred (shown below). We also show the effects of deterministic rounding on throughput. Because deterministic rounding does not compute random numbers, it provides some additional speedups. However, it may affect convergence. These results represent potential speedups in case the overheads of randomization were low, for instance, when using simply lookup for pre-computed randomness. We observe that the inmtenieatinn-ittenivvv intensive models (VGG, AlexNet) benefit more from quantization as compared to the computation intensive models (GoogleNet, Inception, ResNet). These observations are consistent with prior work (Alistarh et al., (017). To quantify the data reduction benefits of natural compression, we measure the total volume of data transferred during training. Fig 7 shows that data transferred grows linearly over time, as expected. Natural compression saves 84% of data, which greatly reduces communication time. Fig 10 studies weak scaling for training ResNet50 on ImageNet showing that Cuat in itself does not have negative effect on weak scaling. Further details and additional experiments including convergence experiments for Neural Collaborative Filtering (He et al. 2017) presented in Appendix A
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proceedings of the 2017 Conference on Empirical Methods Natural Language Processing, pp- 440-445. Association for Computational Linguistics, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1 1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cedric Renggli. The convergence of sparsified gradient methods. In S. Bengio, Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianche and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 5977-5987. Curran Associates, Inc., 2018.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations. In Advances in Neural Information Processing Systems, pp. 14695-14706, 2019.
Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357) 2015.
N. Dryden, T. Moon. S. A. Jacobs, and B. V. Essen. Communication quantization for data mata-parallel training of deep neural networks. In 2016 2nd Workshop on Machine Learning in HPC Environ- ments (MLHPC), pp. 1-8, Nov 2016. doi: 10. 109/ML.HP..2016.000
Nicola Elia and Sanjoy K Mitter. Stabilization of linear systems with limited information. IEEE transactions on Automatic Control, 46(9):1384-1400 2001.
Olivier Fercoq, Zheng Qu, Peter Richtárik, and Martin Takáč. Fast distributed coordinate descent for minimizing non-strongly convex losses. IEEE International Workshop Machine Learning for Signal Processing, 2014.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341 -23688, 2013.
W. M. Goodall. Television by pulse code modulation. The Bell System Technical Journal, 30(1): 33-49, Jan 1951. ISSN 0005-8580 doi: 10. 1538-730518175 .tb01365xx.
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training ImageNet in hour. CoRR,
2017.
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. Proceedings of the 32Nd International Conference on International Conference on Machine Learning- Volume 37, ICML'15. 15, pp. 1737-1766. JMLR.org, 2015.
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.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In Proceedings of the 26th International Conference on World Wide Web, WWW 17, pp. 173-182, 2017.
Samuel Horváth and Peter Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2781-2789, Long Beach, California, USA, 09-15 Jun 2019. PMLR.

---

Under review as a conference paper at ICLR 2021
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:1904.05115, 2019.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4700 4708, 2017.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran EI- Yaniv, and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. The Journal of Machine Learning Research, 18(1):6669-689) 2017.
Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. cisa-Bianchi, and R. Gameett (eds.), Advances in Neural Information Processing Systems 31, pp. Curran Associates, Inc., 2018.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pp- 315-323, 2013.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprini arXiv: 1806.0653, 2018.
D. P. Kingma and J. Ba. ADAM: A Method for Stochastic Optimization. In ICLR, 2015.
Jakub Konečný and Peter Richtárik. Randomized distributed mean estimation: accuracy vs communi- cation. Frontiers in Applied Mathematics and Statistics, 4(62):1-11, 2018.
Hyeontaek Lim, David G Andersen, and Michael Kaminsky. 3lc: Lightweight and effective traffic compression for distributed machine learning. arXiv preprint
2018.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In ICLR 2018 Internattaa Conference on Learning Representations, 2018.
Ryan McDonald. Mchryar Mohri, Nathan Silberman, Dan Walker, and Gideon S. Mann. Efficient large-scale distributed training of conditional maximum entropy models. In Y. Bengio, D. Schu- urmans, J. D. Lafferty, C. K. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems 22, pp. 1-31-, Curran Associates, Inc., 2009.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáë, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: /9010099000999 2019.
T. Na, J. H. Ko, J. Kung, and Mukhopadhyay. On-chip training of recurrent neural networks with limited numerical precision. In 2017 International Joint Conference Neural Networks (IJCNN,, pp. 3716-3723, May 2017. doi: 10. 1091119NN..0017.996666
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 693-701, 2.11.
Sashank J. Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póczos, and Alexander J. Smola. AIDE: Fast and communication efficient distributed optimization. CoRR, abs/1608. 06879, 2016.
Peter Richtárik and Martin Takáč. Distributed coordinate descent method for learning with big data. Journal of Machine Learning Research, (7(75)1--25. 2016.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pp. 400-407, 1951.
L. Roberts. Picture coding using pseudo-random noise. IRE Transactions on Information Theory, 12):145-154, February 1962. ISSN 0096- 1000. doi: 10.1109/TT..192.111777
10

---

Under review as a conference paper at ICLR 2021
Amedeo Sapio, Marco Canini, Chen- Yu Ho. Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan R. K. Ports, and Peter Richtárik. Scaling distributed machine learning with in-network aggregation. CoRR, abs/1903.06701, 2019. URL http:
www.ooggggbbaaaaoooe \/arxiv. org abs / 1933 06701
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and application data-parde data-parallel distributed training of speech dnns. In Interspeech 2014, September 2014.
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effiiccee distributed optimization using an approximate Newton-type method. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 1000-1008, Bejing, China, 2014. PMLR.
Sebastian U. Stich. Local SGD converges fast and communicates little. CoRR, abs/1805.099760 2018.
Sebastian U Stich, Caan-Bapiiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Resa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 4452 4463. Curran Associates, Inc., 2018.
John Sun and Vivek Goyal. Scalar quantization for relative error. In 2011 Data Compression Conference, pp. 302-302. IEEE, 2011.
John 7. Sun, Grace I Wang, Vivek K Goyal, and Lav R Varshney. A framework for bayesian optimality of psychophysical laws. Journal of Mathematical Psychology, 56(6))495-501, 2012.
Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and H. Brendan McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Conference on Machine Learning, 2017
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. DoubleSqueeza Parallel stochastic gradient descent with double-pass corpe-compenstted compression. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6155-6163 Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL/stt::/ppocceediie sangl9d.html
mlr press/v97/
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. In Advances in Neural Information Processing Systems, pp- 1306-1316, 2018.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, pp. 1519, 2017.
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning. volume 70 of Procedingss of Machine Learning Research, pp. 4043, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Shuai Zheng, Ziyue Huang, and James Kwok. Communication-efiice distributed blockwise momentum sgd with eeror-feedback. In Advances in Neural Information Processing Systems, pp.
14400-11460, 2019.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J. Smola. Parallelized stochastic gradient descent. J. D. Lafferty, C. K. I. Williams, Shawe-Taylor R. S. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems 23, pp. 2595-2603, Curran Associates, Inc., 2010.
11

---

Under review as a conference paper at ICLR 2021
Appendix
For easy navigation through the Paper and the Appendices, we provide a table of contents.
CONTENTS
Introduction
2
Natural Compression
3
3
Natural Dithering
4
Distributed SGD
5
Experiments
Extra Experiments
14
A.I
Convergence Tests CIFAR 10
14
A.I.I
DenseNet Hyperparameters:
14
A.1.2
AlexNet Hyperparameters:
15
A.1.3
ResNet Hyperparameters)
15
A.2
Convergence Tests ImageNet
15
A.3
Convergence Tests for Neural Collaborative Filtering
15
A.4
Diis D Empirical Variance
16
A.4.1
nat has exponentially better variance
16
A.4.2
D needs exponentially less levels achieve the same variance
17
A.4.3
D can outperform Dr. in the big regime
17
nat
A.4.4
Compressing gradients
17
A.5
Different Compression Operators
17
Experimental setup
20
Details and Proofs for Sections 2 and
22
Proof of Theorem
22
Proof of Theorem
22
Proof of Theorem
................................
23
Proof of Theorem
23
Proof of Theorem
23
C.6 Natural Compression and Dithering Allow for Fast Aggregation
24
Details and Proofs for Section
25
D.I Algorithm
25

---

Under review as a conference paper at ICLR 2021
D.2
Assumptions and Definitions
25
D.3
Description of Algorithm
25
D.4 Three Lemmas Needed for the Proof of Theorem 6
26
Proof of Theoreml6
27
D.6 A Different Stepsize Rule for Theorem
28
................................
D.7
SGD with Bidirectional Compression: Four Models
28
D.7.1
Model
29
D.7.2
Model 2
29
D.7.3
Model 3
29
7.44 4
Model 4
30
D.7.5
Communication strategies used in Tables 3
5
30
D.8
Sparsification Formal Definition)
31
Limitations and Extensions
31
13

---

Under review as a conference paper at ICLR 2021
2.0
2.0
1.0
1.5
No Compress on
1.
No Compression on
0.6
1.0
1.0
0.
Compresioe
0.0
Epochs
Timeeso
Timefming
Figure 11: DenseNet40 (k- 12)
Traningg 1145
Fraling bxss
1.5
0.0
1.0
1.0
0.4
0.5
0.2
0.
20
40
60
80
100
120
140
160
160 200
300
600
900
1200
1950
1820
2303
300
600
900
1205
1900
1860
2105
Eports
Timme))
Timee))
accuraty
0.8
Trantea hoa
Traaiing
0.6
0.5
0.5
213
0.2
Compresiion
0
20
40
60
50
100
120
140 160 180 200
300
6.00
900
300
600
900
Epochs
1.0
1.5
Cur Compression
15
Transing bas
Compeession
1.0
0.6
20hh lante
0.5
0.5
Juti tutar
0.2
0.0
100
160 200
200
100
300
Figure 12: AlexNet (Batch size: 256, 512 and 1024)
A EXTRA EXPERIMENTS
A.1 CONVERGENCE TESTS ON CIFAR 10
In order to validate that Cuat does not incur any loss in performance, we trained various DNNs on the Tensorflow CNN Benchmark the CIFAR 10 dataset with and without C.at for the same number of epochs, and compared the test set accuracy, and training loss. As mentioned earlier, the baseline for comparison the default NCCL setting. We didn't 't tune the hyperparameters. In all of the experiments, we used Batch Normalization, but no Dropout was used.
Looking into Figures 12 and 13 incurring any accuracy loss. As expected, the communication intensive AlexNet (62.5 M parameters) benefits more from the compression than the computation intensive ResNets (< 1.7 M parameters) and DenseNet40 (1 M parameters).
that Cuat achieves significant speed-up without
A.1.1 DENSENET HYPERPARAMETERS
We trained DenseNet40 (A: = 12) and followed the same training procedure as described in Huang ct al. 2017h. We used a weight decay of 10 and the optimizer as vanilla SGD. We trained for total of 300 epochs. The initial learning rate was 0.1, which was decreased by a factor of 10 at 150 and 225 epoch.
14

---

Under review as a conference paper at ICLR 2021
1.0
No Compression on
No Compression on
Taato
0.6
14 bale
0.4
A
0.5
Compresike
0.0
1200
Epocns
Timees)
Timess)
1.0
Compression
Trariing aa
No Compression
0.0
1.5
1.5
0.4
No compresioon
0.0
40
120
160
600
1200
1800
2400
3600
3000 5609 Timee)
2400
Epects
Timmr))
1.0
2.0
Compression
Trasiing 1al
Compression
sccunsy
0.8
0.4
No comprcaionn
40
80
120
160
200
240
200
320
600
12:00
1800 2400 3000 3620 4200
600
12:0 1802 2400 3000 3600 4200 Timess)
Timos)
Figure 13: ResNet (#layers: 20, 44 and 56)
A.1.2 ALEXNET HYPERPARAMETERS:
For AlexNet, chose the optimizer SGD with momentum, with momentum of 0.9. We trained on three minibatch sizes: 256, 512 and 1024 for 200 epochs. The learning rate was initially set to be 0.001, which decreased by a factor of 10 after every 30 epoch.
A.1.3 RESNET HYPPEPARAMETERS
All the ResNets followed the training procedure as described in He et al. (2016). We used a weight decay of 10 4 and the optimizer was chosen to be vanilla SGD. The minibatch size fixed to be 128 for ResNet 20, and 256 for all the others. We train for a total 64K iterations. We start with an initial learning rate of 0.1, and multiply it by 0.1 at 32K and 48K iterations.
A.2 CONVERGENCE TESTS ON IMAGENET
To further demonstrate the convergence behavior of Cust. we run experiments which conform to the ImageNet Large Scale Visual Recognition Challenge (ILSVRC), We follow publicly available benchmark and apply Cuat. on without modifying any hyperparameter, The model trains for 50 epochs on 8 and 16 workers, with default ResNet50 setup: SGD optimizer with 0.875 momentum, cosine lcarning rate schedule with 0.256 initial learning rate and linear warmup during the first epochs. The weight decay is set to 1/32768 and is not applied on Batch Norm trainable parameters. Furthermore, 0.1 label smoothing is used. As shown in 14 Cuat does not incur any accuracy loss even if applied on large distributed tasks.
A.3 CONVERGENCE TESTS FOR NEURAL COLLABORATIVE FILTERING
We also train Neural Collaborative Filtering (NCF) HH et 2017 on MovieLens-2001 Dataset using Cuat and compare its convergence to no compression. Neural Collaborative Filtering is big recommendation model with ~32 million parameters. We use a publicly available benchmark and apply Cnat on it without modifying any hyperparameter. The model trains for 20 epochs on 8 workers
with ADAM optimizer KKinmma & Ba 2015) (Ir= 4.5 10-3 B1 = 0.25, 82 = 0.5), global
https://qi com
Classi foasfiicaionn massffiicaiionn//5vl...
Recoomeendation/wcy
15

---

Under review as a conference paper at ICLR 2021
10
Conurision mcrters
0.7
Train
2.5
0.6
8.4
0.5
0.4
poires
0.3
venees
0.1
Cor cresiion workers
Compemsion wooterr
10
20
30
40
50
10
20
30
50
10
20
30
50
Epoch
Eeoch
Ecoch
Figure 14: ResNet50 on ImageNet
batch-size of 2200 and a dropout ratio of 0.5. No weigt decay is applied. Fig 15 shows that Cuat: performs similar to compression both in terms of training loss and test hit rate.
No Compression
0.8
Cnac
94
loss
Train
Rate
92
90
0.4
No Compression
88
Cast
500
1000
1500
250
500
750
1000
1250
1500
1750
Steps
Figure 15: Neural Collaborative Filtering Moviel 20
A.4 DP.5 VS. D.. EMPIRICAL VARIANCE
In this section, we perform experiments to confirm that D level selection brings not just theoretical but also practical performance speedup in comparison D We measure the empirical variance of De." and D For D we do not compress the norm, We first generate a random vector x of by level selection. Our experimental setup is the following. size d 10S. with independent entries with Gaussian distribution of zero mean and unit variance (we tried other distributions, the results were similar, thus we report just this one) and then we measure normalized empirical variance
compare just variance introduced
[[((z) x01
(x)
||=||
We provide boxplots, each for 100 randomly generated vectors & using the above procedure. We perform this for p 1, 2 and p oc. We report our findings in Fig 16 Fig and and Fig T8 These experimental results support our theoretical findings.
A.4.1
D..a HAS EXPONENTIALLY BETTER VARIANCE
In Fig 16 we compare D and D for u = 5, i.e., we use the same number of levels for both compression strategies. In each of the three plots generated vectors with different norm. We find that natural dithering has dramatically smaller variance, as predicted by Thm
15.0
2500
0.25
12.5
Varlance KCC-4P
2000
1500
7.5-
0.15
500
12
222
Figure 16: DP.s P.. with

---

Under review as a conference paper at ICLR 2021
A.4.2 nst NEEDS EXPONENTIALLY LESS LEVELS TO ACHIEVE THE SAME VARIANCE
2n That is, we give standard dithering an exponential advantage in terms of the number of levels (which also means that it will need more bits for communication). We now study the effect this change on the variance. We observe that the empirical variance is essentially the same for both, predicted by Thm
In Fig 17 we the number of levels for D
0.975
0.28
Vettecc IBSt-4
Varience IiSe-44
1.000
2 E0.570
0.24
0.995
Variance
0.965
0.22
0.20
0.985
0.16
022
Figure 17: D D with v 2--1
A.4.3
DP.6 CAN OUTPERFORM nat IN THE BIG REGIME sta
We now remark the situation when the number of levels is chosen be very large (see Fig 18 While this is not a practical setting as does not provide sufficient compression, it will serve as illustration of fundamental theoretical difference between D and DP:s in the which we want to highlight. Note that while D converges to the identity operator as s + oc, which enjoys zero variance, D converges to Cuat instead, with variance that can't reduce below = l/s. Hence, for large enough one would expect, based on our theory, the variance of Di to be around l/s, while the variance of DDPs be closer zero, In particular, this means that D can, in practically meaningless regime, outperform D In Fig 18 we choose oo and 32 (this large). Note that, as expected, the empirical variance both compression techniques small, and that, indeed, D outperforms D nat
limit
0.08
Varlence 1CNood
0.07
0.06
0.05
DC
Figure 18: When p and is very large, the empirical variance of D be smaller than that of D However, in this case, the variance of DR. is already negligible. nat
nat
A.4.4 COMPRESSING GRADIENTS
We also performed identical to those reported above, but with a different generation technique the vectors In particular, instead of synthetic Gaussian generation, used gradients generated by our optimization procedure as applied to the problem of training several deep learning models. Our results essentially the same the reported above, and hence do not include them.
A.5 DIFFERENT COMPRESSION OPERATORS
We report additional experiments where we compare our compression operator to previously proposed ones. These results are based on Python implementation of our methods running in PyTorch this enabled a rapid direct comparisons against the prior methods. We compare against no compression, random sparsification, and random dithering methods. We compare MNIST and CIFAR 10 datasets. For MNIST, we use a two-layer fully connected neural network with RELU activation function. For CIFAR10 10, use VGG1T with fully connected layer the classifier. We these experiments

---

Under review as a conference paper at ICLR 2021
with 4 workers and batch size 32 for MNIST and 64 for CIFARIO. The results averages over runs.
We tune the step size for SGD for given "non-natural" compression. Then the same step size for the "natural" method. Step sizes and parameters are listed alongside the results.
Figures 19 and 20 illustrate the results. Each contains four plots that illustrate, left to right, (1) the test accuracy vs. the volume data transmitted from workers to master (measured in bits), (2) the test accuracy over training epochs, (3) the training loss the volume of data transmitted, and (4)
the training loss over training epochs.
One that in terms of epochs, obtain almost the result in terms of training loss and test accuracy, sometimes even better. On the other hand, our approach has a huge impact on the number of bits transmitted from workers master, which is the main speedup factor together with the speedup in aggregation if we use In-Network Aggregation (INA). Moreover, with INA we compress updates also from master nodes, hence we send also fewer bits. These factors together bring significant speedup improvements, as illustrated in Fig which strongly suggests similar speed-up in training time as observed for Cats see e.g. Section
18

---

Under review as a conference paper at ICLR 2021
80
80
training lona.
None
Cur Cat
Gra Guc
20
20 apactts
20
1d12
1e12
(a) No Additional compression, step size 0.1.
5t à None
SAL a Nane
2.0
1.5
treering
1.5
rest
5 Gue Our
F..0
1.
bits
1+12
spochs
bds
1e12
epachs
(b) Random sparsification, step size 0.04, sparsity 10%.
accommyy
g,00
500
+ None
traini tova
2.0
5e + None ge our
40
1.5
1.5
Nonw Gau Guu
None gos
Gut
20
40
20
40
opocho
opocts
(c) Random sparsification with non- non-uniform probabilities
Wangni et al. 2018), step size 0.04, sparsity 10%.
accorecy
1i Kone
2t?" Nome
62-
191
Gwt
20
02.5
1e1.
spacta
1615
spochs
(d) Random dithering, step size 0.08, 8, 27, second norm.
Figure 19: CIFARIO with VGGI1.
19

---

Under review as a conference paper at ICLR 2021
None None Our
None Nonc
300 A00.0EE
G4
Trairiin
training
None None
None None
32
Gat
15
15
spachu
bills
*pocts
(a) No Additional compression, step size 0.1.
None
gea
test acturncy
Gez
5 Gau
tninng
gel None
None
Gea + Coe
24
2011
(b) Random sparsification, step size 0.04, sparsity 10%.
5 None
5 None
1001 200.800
treitingg Iree
Gaa Gut
cattec less
5 Car Cut
3/1L + None 511
5 Norr
590
Dits
spochs
bibs
3el1
opocta
(c) Random sparsification with non-uniform probabilities WWangni et al. 2018), step size 0.04, sparsity 10%.
nat None mg G.
66
mát" n2 Cun
1055
Trannny
None
None
32
Cat
300
6.5
0.88
315
186
1.5
153
23 spachs
20
635
656
075
180
135
epachs
(d) Random dithering, step size 0.01, 8 8, 2
second norm.
Figure 20: MNIST with 2 fully conected layers.
B EXPERIMENTAL SETUP
Our experiments execute the standard CNN benchmark We summarize the hyperparameters setting in Appendix A.1.2 We further present results for two more variations of our implementation: one without compression (providing the baseline for In-Network Aggregation (Sapio et al. 2019)), ) and the other with deterministic rounding to the nearest power of 2 to emphasize that there exists a performance overhead of sampling in natural compression.
We implement the natural compression operator within the Gloo communication library as a drop-in replacement for the ring all-reduce routine. Our implementation is in C++. We integrate our communication library with Horovod and, in turn, with TensorFlow. We follow the same communication strategy introduced in SwitchML. (Sapio et al., 2019), which aggregates the deep learning model's I's gradients using In-Network Aggregation on programmable network switches. We choose this strategy because natural compression good fit for the capabilities of this class of modern hardware, which only supports basic integer arithmetic, simple logical operations and limited storage.
A worker applies the natural compression operator to quantize gradient values and sends them to the aggregator component, As in SwitchMI., an aggregator capable of aggregating fixed-length array of gradient values at a time. Thus, the worker sends stream of network packets, each carrying chunk of compressed values. For a given chunk, the aggregator awaits all values from every worker;
20

---

Under review as a conference paper at ICLR 2021
1c10
1e9
count
1.0
maximum
count
0.5
-50
-40
-30
-20
-10
10
exponent
Figure 21: Histogram of exponents of gradients exchanged during the entire training process for ResNetl 10 (left) and Alexnet (right). Red lines denote the minimum and maximum exponent values of all gradients.
then, it restores the compressed values as integers, aggregates them and applies compression to quantize the aggregated values. Finally, the aggregator multicasts back to the workers packet of aggregated values.
For implementation expedience, prototype the In-Network Aggregation as server-based program implemented atop DPDK for fast I/O performance. We leave to future work a complete P4 imple- mentation for programmable switches; however, note that all operations (bit shifting, masking, and random bits generation) needed for our compression operator are available on programmable switches.
Implementation optimization. We carefully optimize our implementation using modern x86 vector instructions (AVX2) to minimize the overheads doing compression. To fit the byte length and access memory more efficiently, we compress 32-bit floating point numbers to an 8-bit representation, where bit for the sign and bits are for the exponent. The aggregator uses 64-bit integers to store the intermediate results, and we choose to clip the exponents in the range of -50 ~ 10. As result, we only use bits for exponents. The remaining one bit is used to represent zeros. Note that is possible to implement 128-bit bit integers using two 64-bit integers, but we found that, in practice the exponent values never exceed the range -50 10 (Figure[]1 21).
Despite the optimization effort, identify non-negligible 10 15% overheads in doing random number generation used stochastic rounding, which was also reported in Hubara et al. (2017). We include the experimental results of our compression operator without stochastic rounding as a reference. There could be more efficient ways to deal with stochastic rounding, but we observe that doing deterministic rounding gives nearly the same training curve in practice meaning that computational speed up is neutralized by slower convergence due to biased compression operator.
Hardware setup. We run the workers 8 machines configured with I NVIDIA P100 GPU, dual CPU Intel Xeon ES-2630 v4 at 2.20GHz, and 128 GB of RAM. The machines run Ubuntu (Linux kernel 4.4.0- (22) and CUDA 9.0. Following Sapio al. 2019), balance the workers with aggregators (4 aggregators in the case of 4 workers) running on machines configured with dual Intel Xeon Silver 4108 CPU at 1.80 GHz. Each machine uses a 10 GbE network interface and has CPU frequency scaling disabled. The chunks of compressed gradients sent by workers are uniformly distributed across all aggregators. This setup ensures that workers can fully utilize their network bandwidth and match the performance of programmable switch. We leave the switch-based implementation for future work.
hhttps://wwr dpdk org
21

---

Under review as a conference paper at ICLR 2021
C DETAILS AND PROOFS FOR SECTIONS AND 3
C.I PROOF OF THEOREM
By linearity of expectation, the unbiasedness condition and the second moment condition the form
have
E [[((()) = Dis
VI E
Rd
Vi [d]
(6)
and
[(C())) S (1+1)
Σ
Vx E Rd.
(7)
i=1
Recall that Cust can be written in the form
Cuat (t) = stgn(t) 2 2ooRa Mnl + A(t)).
(8)
where the last step follows since p(t) 2louz 1811 -ldl Hence,
21lnez 14]1
[Cas (t)
E
sign(t) 2 1411
(1 + X(t)) = sign(t) 2l [+|] (1+ E [A(O))
sign(t) 2loggg |+|] (1 + p(t)) =
This establishes unbiasedness (
In order establish 7 suffices to show that E [x)) I (w 1)x² for all 24 R. Since by definition (Cuat (a)); Cunt (2:4 for all [d]. it suffices to show that
E (1)) s (w++1) 11)?,
VI E
f = or = sign(t)2" with a being an integer, then Cuat (t) = f. and holds as an identity with
0. and hence inequality (9) holds for 1/s. Otherwise t sign 2 where
|a <
[a] + 1. With this notation, we can write
22a 2
18
|4|
2a
E [CCaat ({))
+
2a++)
29 - 20+1).
2a
2a
So,
E [C (t))
23(3 22+1)
2n(3|t -a+1)
sup
2
f2
f2
2*<t<<2"11
(3 2n0
2a+1)
30 2
sup 1<8<2
sup 1<842
(2-0)2
0
The optimal solution of the last maximization problem is 4
with optimal objective value g g.
This
3
implies that (9) holds with w = g.
C.2 PROOF OF THEOREM 2
Let assume that there exists some w < oo for which Cint is the w quantization. Unbiased rounding to the nearest integer can be defined in the following way
[ [xr].
with probability p(x:);
(xi) =
with probability
1 p(xx),
where p(z;) [x,;] F.. Let's take 1-D example, where E (0, 1), then
E [Cme (13) (1 - =)0² + x12 S wr?
which implies w 2 1/2, thus taking r + 0+, one obtains w + oc, which contradicts the existence of finite
22

---

Under review as a conference paper at ICLR 2021
C.3 PROOF OF THEOREM!
3
The main building block of the proof is the tower property of mathematical expectation. The tower property says: If X and Y are random variables, then E [X] E [ [X Y]] Applying it to the composite compression operator C₁ o C2, we get
E [[[ - (+) = = E E(C C2(x)] [x)
I.
For the second moment, we have
E [I[[C e (2) = [B(IC) [c((
(w2 + 1)E ||c| (z))1
(wi + ()(22 1) |=||
which concludes the proof.
C.4 PROOF OF THEOREM 4
Unbiasedness of Dia is a direct consequence of unbiasedness of DC.p.
For the second part, first establish bound on the second moment of E:
9 | 2
| ||<
|z 21-a
E
1
2 1-s
+
21-
|
x p
8
|
1
pp
|
9
|2
[zg]
|z:||
11
< 2
2 2
|001|
p
|Ir11
|0e||
Using this bound, we have
d
27
[I mii [1) =
E
||0||]
[] Σ
E
E
Ii
||>l||
IVB
|
2
d
[r:]]
+
< 21-
|1zel 2 1
||
i=1
IN
|| 2 min {2'-0 ||=1||
|| ||| 22-2a 20 2d || [|x112]
||a|||
2 min (d1/22)- ||جl| || 22 25 dd || |1=11²]
9
d/ minlp.2) min { 1, d²/ minlp:21
||>||
where the second inequality follows from Σ minnfa;.b)) b,) S minfI ai bb,} and the last two inequalities follow from the following consequence Hölder's inequality ||жl|p S d/-p-1/2 || for 1 5 p < 2 and from the fact that || < || || for p 2 2. This concludes the proof.
C.5 PROOF OF THEOREM 5
The main building block of the proof is useful connection between DP.s and 2 which can be formally written
Dia (x:
D
| sign(x) Crat (E(x:))
(10)
where (E(x)); = ((2s/1x/1,) with levels 0, 1/2--1, 10pr-,, 2/2"-1,... 1. Graphical visualization can be found in Fig 22
23

---

Under review as a conference paper at ICLR 2021
0
1
3
5
6
7
1
8
4
8
2
8
8
8
Figure 22: ID visualization of the workings natural dithering D and standard dither- ing D with u 2=-1 with
4. Notice that the numbers standard dithering rounds to, i.., 0, 1/8 2/a..... 7/8, form a superser of the numbers natural dithering rounds to, i.e, 0,2 0,2-3,2 2,2 2 ,1 Importantly, while standard dithering uses 24 8 levels (i.e., inter- vals) to achieve a certain fixed variance, natural dithering only needs = levels to achieve the same variance. This is an exponential improvement in compression (see Theorem for the formal statement).
Equipped with this, we can proceed with
E
10
| sign(x) Cnar (Ex))
|
||=||]]] E [ICnac
Thm
F
||:|| sign(>>><(>))
F
D ||((())
8
sta
(w + 1),
which concludes the proof.
C.6 NATURAL COMPRESSION AND DITHERING ALLOW FOR FAST AGGREGATION
Besides communication savings, our new compression operators Cuat (natural compression) and nat (natural dithering) bring another advantage, which is ease of aggregation. Firstly, our updates allow in-network aggregation a primitive switch, which can speed up training by up to 300% (Sapio al. 2019) itself. Moreover, our updates are so simple that if one uses integer format on the master side for update aggregation, then our updates have just one non-zero bit, which leads to additional speed up. For this reason, one needs to operate with at least 64 bits during the aggregation step, which the reason why we also do Cunt compression on the master side; and hence we need to transmit just exponent to workers. Moreover, the translation from floats to integers and back is computation-fiet due structure of our updates. Lastly, for D compression respect to standard randomized dithering D as our levels are computationally less expensive due to their natural compatibility with floating points. addition, for effective communication one needs to communicate signs, nomn and levels as a tuple for both D and sta which needs to be then multiplied back on the master side. For D this is just the summation of exponents rather than actual multiplication as is the case for D
obtain additional speed up with
D DETAILS AND PROOFS FOR SECTION
D.1 ALGORITHM

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Distributed SGD with bidirectional compression
12' Input: learning rates { Jkmo > O, initial vector x
for 0. 0, I....... T do
Parallel: Worker side
for 1....... n do
compute stochastic gradient 9x(=*) (of Si at x*)
compress it A = Cw: (9.(5) end for
Master side aggregate A = ΣE A
compress of Cm (A*) and broadcast to each worker
Parallel: Worker side
for 1;.....,111 do
x x+1 w 2"
end for
end for
D.2 ASSUMPTIONS AND DEFINITIONS
Formal definitions of some concepts used in Section follows:
Definition 4. Let f; R + R be fixed function. A stochastic gradient for fü is random function (z( so that [g]()) = V fz)).
In order to obtain the rate, introduce additional assumptions (x(x) and ff())).
Assumption 1 (Bounded Variance). We say the stochastic gradient has variance at most of if [1)) [((())] $ o
for all x E TRd. Moreover, let Σ
Assumption 2 (Similarity). We say the variance of gradient among nodes is at most & if < S, for all Rd. Moreover, let <² Σ - C.
Moreover, we assume that f is L-smooth (gradient is L-Lipschitz). These are classical assumptions for non-convex SGD (Ghadimi & Lan 2013 Jiang & Agrawal 2018 Mishchenko al. 2019) and comparing to some previous works (Alistarh et al. 2017). our analysis does not require bounded iterates and bounded the second moment of the stochastic gradient. Assumption 2 is automatically satisfied with X = 0 if every worker has access the whole dataset. If one does not like Assumption one can use DIANA algorithm (Horváth et al. 2019) as base algorithm instead SGD, then there is no need for this assumption. For simplicity, we decide to pursue just SGD analysis and we keep Assumption
D.3 DESCRIPTION OF ALGORITHM I
Let describe Algorithm First, each worker computes its stochastic gradient gi (I**), this is then compressed using a compression operator Cw; (this can be different for every node, for simplicity, one can assume that they are all the same) and send to the master node. The master node then aggregates the updates from all the workers, compress with its own operator CM and broadcasts update back to the workers, which update their local copy of the solution parameter x.
Note that the communication of the updates can be also done in all-to-all fashion, which implicitly results in Cas being the identity operator. Another application, which is one of the key motivations of our natural compression and natural dithering operators, is in-nelwork aggregation (Sapio et al. 2019). this setup, the master node network switch. However, current network switches can only perform addition (not even average) of integers.
D.4 THREE LEMMAS NEEDED FOR THE PROOF OF THEOREM
Before we proceed with the theoretical guarantees for Algorithm in smooth non-convex setting, first state three lemmas which are used to bound the variance of g² stochastic estimator of
25

---

Under review as a conference paper at ICLR 2021
the true gradient f=²).. In this sense compression at the master-node has the effect of injecting additional variance into the gradient estimator. Unlike in SGD, where stochasticity is used to speed up computation, here use it to reduce communication.
Lemma' (Tower property + Compression). IfC E B(w) and is a random vector independent of C, then
[I((=) - = =|p S wE [|=1|]]
E [[((()))))
s (w + 1)B [1=1*]]
(11)
Proof. Recall from the discussion following Definition 2 that the variance of compression operator E (Bw) can be bounded as
[[(xx) xx| =01²] S w |
Vo E IR.
Using this with 2, this can be written in the form
E [I[C()) =|1² | =
w |==11
Var Rd
(12)
which we can use in our argument:
E [[[(()) =1(²]
E
[I(())
- 211
12
12
E w
||
wF ||
The second inequality can proved exactly same way.
Lemma 8 (Local compression variance). Suppose is fixed, C E B(w), and 9;(x)) is an unbiased estimator of V((x). Then
E - s (w +w
-
(13)
Proof.
E. [[(C()(())) V\()))
Det. 5
F. -(()) F. [1oa(() - V=(
WE [100( [ll((0) V
Def
S
(w + I)FE [1))(()) - V - [()
Assum
II
(w 1)07 + [VV
Lemma (Global compression variance). Suppose x is fixed, Cw: E B(ww,) all i, Car E B(was), and (2( is unbiased estimator of V fe(x)) for all Then
|1
E
1
CM
Cw.
Sa B1V
(14)
where ww = max;e(() ww: and
(WM + () + 1) 0² + (was + 1)w 2
B == + wM + (WM + 1)w
(15)
n
Proof. For added clarity, let us denote
A
Cw. (g((x))
1
26

---

Under review as a conference paper at ICLR 2021
Using this notation, the proof proceeds follows:
E
CM (A)
Det.
E
CM (A) vf(2))
| + |V{(2)]
Def
1
|ICM (A)
||3
+E
- - v((x)) 1/ + +[]([())]
n
Vf(a) | + +|[5(0)11
WM E ||A| 2 n²?
+
A
- f(x) 1
Def
(wM + 1)E
+ + + 1) [[
WM + 1 n
E [[C,, - - (we + 1V
n² f=1
(WM + ()( + 11) + (wM + +)w 1
|V}(()))1
+(WM + 1) [[)]1
(WM + 1)(ww + 1) 02 + (wi + 1)ww
Vf((z) v=)))
1=1
(1 + +w + (w> + 1)ww) |V((())
Assum
(WM + 1)(W + 1) 02 (WM + 1)wW g²
1 [+ (WM + 1)w
|[V[(x))
D.5 PROOF OF THEOREM 6
Using T-smoothness of and then applying Lemma
we get
[[](attt)] < [[[(a*)] + F. (V
k+1
- 24 + -/2 |
L
h+1
2 [1]]]]]]
2
|1
gh 27
E [f((a))] - n
||
+
L n
2
E [{f(a*)] - - n/
L tne E ||< |1
+ Lamk
2
2
Summing these inequalities for O...,, 1, we obtain
TLami
Bnk E ||V,<<>>)| s S5(x9)-((
1k
2
k=
Taking mh 7) and assuming
2
1 < L3
(16)
one obtains
E [IV][EN)]]
1 < E E [1
2(f(x)) - f(x)))
Lan
= 8(n,T))
Tn (2 (3m)
2 LBn
k=
is easy to check that we choose 77 = L(ate)) (which satisfies (16) for every E > 0), then for any
T > 2Lif(=") f(x=)((=)))))) (a==
have 8(1, T) 5 8, concluding the proof.
27

---

Under review as a conference paper at ICLR 2021
Master can aggregate real numbers (e.g., a workstation)
Master can aggregate
integers only
(e.g.. SwitchML (Sapio et al. 2019)
Same communication speed both ways Master communicates infinitely fast
MODEL 1 MODEL 2
MODEL
MODEL 4
Table 2: Four theoretical models.
D.6 A DIFFERENT STEPSIZE RULE FOR THEBRRE
Looking Theorem 6 that setting step size
V/h 17 2(f(x0) f(x*))
1.T
with
T (B²()(x))) ((x)))
a
(number of iterations), we have iteration complexity
(V (ww + 1)(WM +
Tn
which will be essentially same as doing no compression on master and using Cw o Cas or Cw o Cas the workers' side. Our rate generalizes the rate of Ghadimi & Lan (2033) without compression and dependency on the compression operator is better comparing to the linear one in Diang & Agrawal (2018 Moreover, our rate enjoys linear speed-up in the number of workers n. the same as Ghadimi & Lan (2013). In addition, if one introduces mini-batching on each worker of size b and assuming each worker has access the whole data, then σ² - o²/6 and ç² - which implies
(V
o
(aw
1) +1) Tn
(V
[ww + 1)(war + 1)
Thn
and hence one can also obtain linear speed-up in terms of mini-batch size, which matches with Jiang & Agrawal (018).
D.7 SGD WITH BIDIRECTIONAL COMPRESSION: FOUR MODELS
It is possible to consider several different regimes for our distributed optimization/traiinng setup, depending on factors such as:
The relative speed of communication (per bit) from workers the master and from the master to the workers,
The intelligence the master, i.e., its ability or the lack thereof of the master to perform aggregation of real numbers (e.g., a switch can only perform integer aggregation),
Variability of various resources (speed, memory, etc) among the workers.
For simplicity, we will consider four situations/regimms only, summarized in Table 2
Direct consequences of Theorem 6 Notice that (5) posits a O(I/T) convergence the gradient
aLa norm to the value 2- which depends linearly on a. In view of (4), the more compression we perform, the larger this value. More interestingly. assume now that the same compression operator used at each worker: Cw Cw,- Let Cw B(ww) and CM B(wwr) be the compression == 2L( f(x* 22 + EB) is its iteration complexity. of equal data all nodes, i.e., 0, get
on master side. Then, T(WM, In the special
(war+)) +1)o"/++)///// and B = (WM + 1) (1 + ww/n). If no compression is used, then ww = WM = and + eB = 0²/n
Jiang & Agrawal 2018 allows compression the worker side only.
28

---

Under review as a conference paper at ICLR 2021
So. the relative slowdown of Algorithm| without compression is given by
1
used with compression compared to Algorithm used
(1)*+ /n (1 + ww//)))
Thwar ww) 7(0.0)
(WM + 1) E (WM + 1, (wm + () + 1)] (17)
o o//n+e +
The upper bound achieved for n (or for any n and e + 0), and the lower bound is achieved co. So, the slowdown caused by compression worker side decreases with n. More importantly, the savings in communication due to compression can outweigh the iteration
in the limit
slowdown, which leads overall speedup!
D.7.1 MODEL.
First, we start with the comparison, where we assume that transmitting one bit from worker to node takes the same amount of time as from master to worker.
Compression
No. iterations
Bits per iteration
Speedup ((0)
C E B(w)
T(w)= O(( 1)
W M + M r> W;
Tw
None
2 32d
Cnat S4
1+0
2 9d
2.81x-3. 36x
(2)1+
2 (33 + loga d)g
0.06x 0.60x
8 o Cuas
19d 1-#
2 (10 + loga d)g
0.09x-0.98x
8q
DP.2"'3
(1 + v02" 1-2l~>))
149
(32 + d(s + 2))
1.67x-1.78x
140
D
81
2 (8 + d(log, 2))
3.19x-4.10x
Table 3: Our compression techniques can speed up the overall runtime (number of iterations T(w) times the bits sent per iteration) of distributed SGD, We assume binary32 floating point representation, bi-directional compression using and the same speed of communication from worker master (W; + M) and back (M ~> W.). The relative number of iterations (communications) sufficient to guarantee optimality (w) = (w + 1) where 0 E (1, (see Theorem 6). Note that big regime leads to better iteration bound T(w) since for big n we have 0 s 1, while for small have 9 x= 2. For dithering,
min 1, dd2 The 2.81x speedup for Cnat is obtained for 0 = 1, and the 3. 166 speedup for = 0. The speedup figures were calculated for d = 10 = (dithaa choice of (dithering), and g 0.1d (sparsification).
D.7.2 MODEL.
For the second model, assume that the master communicates much faster than workers thus com- munication from workers is the bottleneck and we don't 't need to compress updates after aggregation, thus Cм is identity operator with WM 0. This is the case mention in the main paper. For completeness, we provide the same table here.
D.7.3 MODEL.
Similarly to previous sections, we also do the comparison for methods that might be used for In- Network Aggregation. Note that for INA, is useful to do compression also from master back to workers as the master works just with integers, hence in order to be compatible with floats, it needs use bigger integers format. Moreover, Cuat compression guarantees free translation to floats. For the third model, we assume we have the same assumptions communication as for Model 1. As baseline, we take SGD with Crat as this the most simple analyzable method, which supports INA.
D.7.4 MODEL 4
Here, we do the same comparison as for Model 3. contrast, for communication we use the same assumptions for Model 2.

---

Under review as a conference paper at ICLR 2021
Approach
Cw;
No. iterations
Bits per iter.
Speedup
T (ww)
O(www + 1)
Wi + M
Factor
Baseline
identity
32d
New
Cuse
(9/s)
9d
3.2x-3.6x
Sparsification
54
(4/4)*
(33 + log2 d)q
0.6x-6.0x
New
Cuas o S
(9i//sa) 0
(10 + log2 d)4
100-110.xx
Dithering
D
kdd 20000
31 d(2 + 8)
1.8x-15.9x
New
D
(9/8 + nd 20
31 + d(2 log, 8)
4.1x-16.0x
Table 4: The overall speedup of distributed SGD with compression on nodes via Cw, over a Baseline variant without compression. Speed is measured by multiplying the # communication rounds (i.e., iterations T (www)) )) by the bits sent from worker to master (W; + M) per 1 iteration. We neglect in practice this is much faster. We assume binary32 representation. The
M + W; communication relative # iterations sufficient to guarantee optimality is ("(w)) = (ww + 1)", where 0 E (0, 1] (see Theorem 6). Note that in the big regime the iteration bound [(ww) is better due (however, this is not very practical as n is usually small), while for small we have 0 = 1. For dithering, r = min 2}, λ min 1, vd2²-= *}. The lower bound for the Speedup Factor is
obtained for = 1, and the upper bound for 0 = 0. The Speedup Factor (T(ww )-4 Bits
figures were
TO)-32d
calculated for d = 10,, 9 = 0.1d, p = 2 and optimal choice of 8 with respect to speedup.
Approach
C
Slowdown (iters/ baseline)
Bits per iter.
Speedup factor
W; m> M M W.
Baseline
Cast
2-
Sparsification
S o Cuat.
(d/4 1-
2 210 log, d)q
0.03x-0.30x
Dithering
(9/8 Rd 2 10
2 2- + d(2 + log, 8))
1.14x 1.30x
Table 5: Overall speedup (number of iterations T times the bits sent per iteration (W; + M + M H>
W;) of distributed SGD. We assume binary32 floating point representation, bi-directional compression using the same compression C. The relative number of iterations (communications) sufficient to guarantee ε optimality is displayed in the third column, where 0 E (0, 1] (see Theorem 6). Note that big regime leads to smaller slowdown since for big we have 0 = O, while for small n we have 0 2 1. For dithering, we chose = 2 and x min v Vd22-*3. The speedup factor figures were calculated for d 10% p = (dithering).opting choice of (dithering), and 0.1d (sparsification).
Approach
Cw:
Car
Slowdowa (iters baseline)
W M commun. (bits/ iteeattoon
Speedup factor
Baseline
Cuat
Cunt
9d
Sparsification
Sa Crat
Cunt
(%))
(10 + logg d)g
0.30x-3.009
Dithering
Dr
Guat
(9/8 + kd y
(8 d(2 log, *))
1.3x-1.5x
Table 6: Overall speedup (number of iterations T' times the bits sent per iteration (W; + M)) of distributed SGD. We assume binary32 floating point representation, bi-directional compression using Cw,, CM. The relative number of iterations (communications) sufficient to guarantee optimality displayed in the third column, where (0, 1] (see Theorem 6). Note that big n regime leads to smaller slowdown since for big we have 0 RJ O, while for small n we have 0 R 1. For dithering, we chose p 2 and min Vd21-*3. The speedup factor figures were calculated for d 10 p = 2 (dithering).optinge choice (dithering), and = 0.1d (sparsification).
D.7.5 COMMUNICATION STRATEGIES USED IN TABLES
5 6
No Compression or Crat. Each worker has to communicate a (possibly dense) d dimensional vector of scalars, each represented by 32 or 9 bits, respectively.
30

---

Under review as a conference paper at ICLR 2021
Sparsification S with without Cuat. Each worker has to communicate sparse vector of entries with full 32 or limited 9 bit precision. We assume that q is small, hence one would prefer to transmit positions of non-zeros which takes g(log2 (d) 1) additional bits for each worker.
Dithering (D or Da ). Each worker has communicate 31(8 D bits (sign is always positive, so does not need be communicated) for the norm, and log2(s) + 1 bits for every coordinate for level encoding (assuming uniform encoding) and bit for the sign.
D.8 SPARSIFICATION FORMAL DEFINITION
Here we give a formal definition of the sparsification operator used in Tables Definition 5 (Random sparsification). Let 1 S q S d be integer, and let denote the Hadamard (element-wise) product. The random sparsification operator Sa R + F is defined as follows:
d fox,
2
where ε E Rd is a random vector chosen uniformly from the collection of all binary vectors 3 {0, 13 with exactly nonzero entries (i.e., l1v/lo = 4)).
The next result describes the variance of S
Theorem 10. S E IB(// - 1).
Notice that in the special case y = reduces to the identity operator (i.e., no compression applied), and Theorem 10 yields tight variance estimate: d/a - 1 = 0.
Proof. See e.g. Stich et al. 2018 (Lemma A.I).
Let us now compute the variance of the composition Cuat St. Since Guat E B(1/s) (Theorem and S 1B(4/- 1) (Theorem 10), in view of the our composition result (Theorem 3 we have
WW ( (
d -
9d
Cw Cuat 8 B(ww),
where
1. (18)
q 8q
E LIMITATIONS AND EXTENSIONS
Quantization techniques can be divided into two categories: biased (Alistarh et al. 2018 Stich ct al. 2018) and unbiased (Alistarh et al. 2017 Wen et al.) 2017 Wangni et al. 2018). While the focus this paper was on unbiased quantizations, is possible to combine our natural quantization mechanisms in conjunction with biased techniques, such the TopK sparsifier proposed in Dryden jtt al.] (2016): Aji Heafield (2017) and recently analyzed in Alistarh et al. (2018); Stich et al. (2018) and still obtain convergence guarantees.


Reviews:
[{"review_id": "anoh47sWMIn", "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": "This paper proposes a novel unbiased bidirectional compressor for vanilla SGD to reduce the communication overhead. Both theoretical and empirical analysis are provided. In overall, the paper is technically sound.\n\nMy concerns are mainly about the the significance of the proposed method in practice and the comparison to the previous work:\n\n1. Dist-EF-SGD [1] and SignSGD [2] both achieve nearly 32x bidirectional compression, while natural compression only achieves roughly 8x in the experiments. Although this paper focuses on unbiased compressors and Dist-EF-SGD and SignSGD are biased compressors, the gap in the compression ratio is hard to ignore, which makes it hard to claim that this paper achieves SOTA in practice.\n\n2. For the CIFAR-10 experiments, all the models (the smallest is ResNet50) are heavily over-parameterized, which means that there is huge redundancy in the gradients and models themselves. As a result, it will be easy to converge to small training loss for any compressor. Furthermore, since the experiments lacks comparison to other works (the only baseline with compression is standard dithering), it's hard to justify the importance of the proposed compressor. It will be better if the authors could show results on simpler models such as resnet20.\n\n3. The paper lacks comparison to other methods. I still highly recommend to compare to dist-EF-SGD [1], since it achieves SOTA performance in communication-efficient distributed SGD. For other compressors, I understand that the other unbiased compressors may not have bidirectional compression. However, SignSGD [2] achieves bidirectional 32x compression without error feedback (error feedback improves the convergence of SignSGD, but not neccessary in some cases). Although SignSGD is biased compressor, it satisfies the requirement \"vanilla distributed SGD with bidirectional compression\" mentioned in Section 4, which makes it a good baseline. However, SignSGD is not compared or cited in this paper.\n\n4. Most of the experiments are relatively small. For the ImageNet experiments in the appendix, no comparison in training time is provided.\n\n\nReferences:\n[1] Zheng, Shuai, Ziyue Huang, and James Kwok. \"Communication-efficient distributed blockwise momentum SGD with error-feedback.\" Advances in Neural Information Processing Systems. 2019.\n[2] Bernstein, Jeremy, et al. \"signSGD: Compressed Optimisation for Non-Convex Problems.\" International Conference on Machine Learning. 2018.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Jn0-JW5uMZK", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a data compression method named natural compression. This method can be implemented very fast and could be added to other compression methods for additional compression. Then this is generalized to natural dithering for a more aggressive compression. In addition, it compares different compression methods for a bidirectional compressed SGD method. \n\nStrength:\n\n- This compression method is very fast and can be combined with other compression methods. This compression has a small relative variance. It also has advantages in hardware implementation. \n\nWeakness:\n\n- Except for the compression method, the optimization algorithms discussed in this paper is the standard parallel SGD. There are many advanced optimization algorithms in the literature, and it is more important to see its performance of this compression method on those advanced algorithms. Two examples are DoubleSqueeze (Parallel stochastic gradient descent with double-pass error-compensated compression) and DORE (A Double Residual Compression Algorithm for Efficient Distributed Learning), and both algorithms have bidirectional compression. \n- The compression rate is large comparing to other data compression methods such as p-quantization in the paper (Distributed Learning with Compressed Gradient Differences). Also, the comparison in A.4 may be unfair for the standard dithering. For standard dithering, the variance is bounded, while the variance for natural compression is relatively bounded. Therefore, for large values, the variance of natural compression is larger than standard ones (the same applies to Theorem 2), while small values favor natural compression. In the analysis, the relative variance is applied, so the result does not favor standard ones. It would be more interesting to compare different compression methods in solving various types of machine learning problems with different algorithms. \n- Table 1 may not reflect the speedup in real implementation. As mentioned above, the analysis is based on the relative variation, so it would be interesting to see the comparison in numerical experiments as well. \n- Line 4 in the caption of Table 1. The second sentence is not completed. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "BtC_NZhee7l", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed a new compression scheme called natural dithering, which uses powers of 2 as quantization levels in gradient compression. The variance of the scheme is studied and the compression scheme is tested in neural network training experiments.\n\nPros:\nThe proposed compression scheme is easy to implement in practice and the experiment results show it can reduce training time in practice. The study on different aspects of natural dithering is quite comprehensive, including the variance, comparison with standard dithering, and the limit regime when the number of bits goes to infinity (where standard dithering is better).  \n\nCons:\nMy main concern is the novelty of this paper. Although discussions in the paper are quite comprehensive, the proposed compression scheme is just changing the uniform quantization levels to powers of 2. The idea is quite trivial and standard especially given the current machine representation of floating-point numbers. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5nVVE2xq8EN", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper introduces a new, simple yet theoretically and practically effective compression technique: natural compression. Theoretically, the compression technique increases the second moment of the compressed vector by not more than the factor of 9/8. Empirically, the communications savings are substantial, leading to 3-4 times improvement in overall running time. \n\nOverall, I think the paper is theoretically solid and empirically validated. I tend to acceptance. \n\nPros: \n1.  Theoretically grounded and rigorous criterion for compressing the information. The authors also give the theoretical and geometric interpretation why the natural compression technique can reduce communication without sacrificing too much accuracy. \n2. It theoretically demonstrates that the savings in communication due to compression can outweigh the iteration slowdown, which leads to an overall speedup. This is not common in existing compression work. \n3. The simulation considers various distributed learning settings and several standard datasets. It also considers the compatibility of the proposed compression schemes to the current IEEE standard and current programmable network switches. This provides evidence on the practical impact of the proposed compression scheme.  \n\nCons: \n1.   The literature review seems outdated. Considering various compression techniques (quantization and sparsification) have been proposed during the last two years, more recent work needs to be discussed and compared, e.g.,\n\nQsparse-local-SGD: Distributed SGD with Quantization, Sparsification and Local Computations, NIPS 2019\nCommunication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradients, NIPS 2019\nOnline Learned Continual Compression with Adaptive Quantization Modules, ICML 2020\nMoniqua: Modulo Quantized Communication in Decentralized SGD, ICML 2020 \n \n2.  In the simulations, the baselines are lacking. Specifically, the proposed compression techniques only compare with non-compression schemes, which is not sufficient. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers provided negative reviews and the authors wrote detailed feedback. During the later discussion stages, the reviewers acknowledged that some concerns are alleviated (e.g. R1 raised score from 4 to 5), but two concerns still remain: i) the novelty is less clear to the reviewers; ii) the advantage over existing approaches is not strong enough. I personally think the first concern is somewhat subjective; for the second concern, the authors indeed added a few experiments on "comparison to Top-K, SignSGD, EF-SignSGD, and PowerSGD", but R1 still maintained that the comparison is "not well demonstrated", which I guess is because R1 views the two works mentioned in R1's review as "concurrent or later" while R1 pointed out in the discussion that those two works appear before Oct 2019.  
R2 pointed out that the paper could have shown the advantage in one of two aspects (see below) but did not. 
See the discussions of the three reviewers below.

R1
"The advantage of the proposed compression method over existing approaches is not well demonstrated."
R2:
"To justify the significance of the contribution, I think the paper should show at least 1 of the followings:
When approaching a very high compression ratio, the natural compressor has significantly better testing accuracy compared to the previous work, i.e., the proposed work could push the compression ratio higher than the previous work with nearly no accuracy loss. The authors could use the new compressor alone, or combine it with some other compressors such as top-k, as the authors mentioned in the answers. (However, according to the extra experiments, the testing accuracy is slightly better than top-k, and slightly worse than power-k. None of them makes a significant difference.)
The natural compressors can achieve similar accuracy compared to the previous work with the same compression ratio, but with much less computation overhead. (I think this one may work for this paper, as the authors mentioned in their answers. However, to justify such a contribution, we will need to check the training time compared to EF-SGD with top-k and power-k, which seems not included in the extra experiments.)"
R4: 
"I stand with my point that the novelty is limited."

Overall, I think the paper might have presented an interesting idea, but unfortunately can not be accepted in the current form. 

Decision: Reject