Year: 2018

Abstract:
In distributed training, the communication cost due to the transmission of gradients or the parameters of the deep model is a major bottleneck in scaling up the number of processing nodes. To address this issue, we propose dithered quantization for the transmission of the stochastic gradients and show that training with Dithered Quantized Stochastic Gradients (DQSG) is similar to the training with unquantized SGs perturbed by an independent bounded uniform noise, in contrast to the other quantization methods where the perturbation depends on the gradients and hence, complicating the convergence analysis. We study the convergence of training algorithms using DQSG and the trade off between the number of quantization levels and the training time. Next, we observe that there is a correlation among the SGs computed by workers that can be utilized to further reduce the communication overhead without any performance loss. Hence, we develop a simple yet effective quantization scheme, nested dithered quantized SG (NDQSG), that can reduce the communication significantly without requiring the workers communicating extra information to each other. We prove that although NDQSG requires significantly less bits, it can achieve the same quantization variance bound as DQSG. Our simulation results confirm the effectiveness of training using DQSG and NDQSG in reducing the communication bits or the convergence time compared to the existing methods without sacrificing the accuracy of the trained model.

text: In distributed training, the communication cost due to the transmission of gradients or the parameters of the deep model is a major bottleneck in scaling up the number of processing nodes. To address this issue, we propose dithered quantization for the transmission of the stochastic gradients and show that training with Dithered Quantized Stochastic Gradients (DQSG) is similar to the training with unquantized SGs perturbed by an independent bounded uniform noise, in contrast to the other quantization methods where the perturbation depends on the gradients and hence, complicating the convergence analysis. We study the convergence of training algorithms using DQSG and the trade off between the number of quantization levels and the training time. Next, we observe that there is a correlation among the SGs computed by workers that can be utilized to further reduce the communication overhead without any performance loss. Hence, we develop a simple yet effective quantization scheme, nested dithered quantized SG (NDQSG), that can reduce the communication significantly without requiring the workers communicating extra information to each other. We prove that although NDQSG requires significantly less bits, it can achieve the same quantization variance bound as DQSG. Our simulation results confirm the effectiveness of training using DQSG and NDQSG in reducing the communication bits or the convergence time compared to the existing methods without sacrificing the accuracy of the trained model.

heading: 1 INTRODUCTION
text: In recent years, the size of deep learning problems has increased significantly both in terms of the number of available training samples as well as the complexity of the model. Hence, training deep models on a single processing node is unappealing or nearly impossible. As such, large-scale distributed machine learning in which the training samples are distributed among different repository or processing units (referred to as workers) has started to be a viable approach for tackling the memory, storage and computational constraints.
The requirement to exchange the gradients or the parameters of the model incurs significant communication overhead which is a major bottleneck in distributed training algorithms. In recent years, there has been a great amount of effort on reducing the communication overhead. The majority of existing methods can be categorized into two groups: The first group mitigates the communication bottleneck by reducing the overall transmission rate via sparsification, quantization and/or compression of the gradients. For example, Seide et al. (2014) reduces the communication overhead significantly by one-bit quantization of the stochastic gradients (SG). However, the reduced accuracy of gradient may impair the convergence rate. Using different quantization levels or adaptive quantizers, one can alleviate such issues by decreasing the error in the quantized gradients in the expense of increased communication bits Dryden et al. (2016). Moreover, applying entropy coding algorithms such as Huffman coding on the quantized values can further reduce the communication bit-rate Øland & Raj (2015); Strom (2015). Alistarh et al. (2017) introduced QSGD which uses probabilistic (stochastic) quantization of SGs instead of ordinary fixed (deterministic) quantization methods. They investigated its convergence guarantee and the trade-off between the quantization precision and variance of QSG. Terngrad Wen et al. (2017) probabilistically quantizes the gradients into {−1, 0,+1} and it is shown that the convergence rate can be improved by layer-wise quantization and gradient clipping.
The second group of works attempts to attenuate the communication bottleneck by relaxing the synchronization between workers. Each worker may continue its own computations while some others are still communicating and exchanging parameters. Carefully scheduling and managing the asynchronous parameter exchange can lead to a better utilization of both the communication bandwidth and the computational power of the distributed system. Examples of such approaches include DownpourSGD Dean et al. (2012), Hogwild! Niu et al. (2011), Hogwild++ Zhang et al. (2016) and Stale Synchronous Parallel model of computation Ho et al. (2013).
Our Contributions. Our work in this paper falls within the first line of research, i.e. reducing the communication overhead by quantizing and compressing the gradients. We first introduce using dithered quantization in the distributed computations of the stochastic gradient and show that stochastic quantizer of Alistarh et al. (2017) and ternarization of Wen et al. (2017) can be considered as special cases of our proposed method, although the reconstruction algorithms are slightly different. The convergence of dithered quantized stochastic gradient descent algorithm is analyzed and its convergence speed w.r.t. the number of workers and quantization precision is investigated. Next, we observe that in a typical distributed system, the stochastic gradients computed by the workers are correlated. However, the existing communication methods ignore that correlation. We tap into the question of how that correlation can be exploited to further reduce the communication without sacrificing the precision or convergence of the learning algorithm. We model the correlation between the stochastic gradients computed by each worker and propose a nested quantization scheme to reduce the communication bits without increasing the variance of the quantization error or reducing the convergence speed of the distributed training algorithm.

heading: 1.1 NOTATIONS
text: Throughout the paper, bold lowercase letters represent vectors and the i-th element of the vector x is denoted as xi. Matrices are denoted by bold capital letters such asX , with the (i, j)-th element represented by Xi,j or [X]i,j . Given a real number x ∈ R, bxe is the nearest integer to x. For a random variable u, u ∼ U [a, b] if its probability distribution is uniform over interval [a, b] and u ∼ N (µ, σ2) if it follows a Gaussian distribution with mean µ and variance σ2.

heading: 2 PRELIMINARIES

heading: 2.1 DITHERED QUANTIZATION
text: It is well-known that the error in ordinary quantization especially when the number of quantization levels is low, depends on the input signal and is not necessarily uniformly distributed. In Dithered Quantization, a (pseudo-)random signal called dither is added to the input signal prior to quantization. Adding this controlled perturbation can cause the statistical behavior of the quantization error to be more desirable Schuchman (1964); Gray & Stockham (1993); Gray & Neuhoff (1998).
Let Q(·) be an M-level uniform quantizer with quantization step size of ∆, i.e., Q(v) = ∆ bv/∆e where bαe is the nearest integer to α. The dithered quantizer is defined as follows;1
Definition (Dithered Quantization). For an input signal x, let u be a dither signal, independent of x. The dithered quantization of x is defined as x̃ = Q(x+ u)− u. Remark 1. To transmit the dithered quantization of x, it is sufficient to send the index of the quantization bin that x + u resides in, i.e., b(x+ u)/∆e. The receiver reproduces the (pseudo)random sequence u using the same random number generator algorithm and seed number as the sender. It is then subtracted from Q(x+ u) to form the dithered quantized value, x̃.
Theorem 1 (Schuchman (1964)). If 1) the quantizer does not overload, i.e., |x + u| ≤ M∆2 for all input signals x and dither u, and 2) The characteristic function of the dither signal, defined as Mu(jν) = Eu [ ejνu ] , satisfies Mu(j 2πl∆ ) = 0 for all l 6= 0, then the quantization error e = x− x̃ is uniform over [−∆/2,∆/2] and it is independent of the signal x.
It is common to consider U [∆/2,∆/2] as the distribution of the random dither signal. It can be easily verified that this choice of the dither signal satisfies the conditions of Thm. 1, and it does not increase
1Throughout the paper, we assume that all quantizers are centered around 0. This is the case also for ternary Wen et al. (2017) and stochastic quantizations Alistarh et al. (2017).
the bound of the quantization error, i.e, |x̃− x| ≤ ∆/2 which is the same as the traditional uniform quantization with the same step size.
In some cases, the receiver may not be able to reproduce the dither signal to subtract from Q(x+ u). Hence, quantization is simply defined as as x̃h = Q(x + u). We refer to this approach as the half-dithered quantization as the dither signal is applied only to the quantizer, not the reconstruction of x. In this case, the quantization error is not necessarily independent of the signal, however by an appropriate choice of the dither signal, the moments of the quantization error will be independent Gray & Stockham (1993). For example, if the dither signal u is the sum of k independent random variables, each having uniform distribution U [−∆/2,∆/2], then the k-th moment of the quantization error, = x− x̃h, would be independent of the signal, given by E [ k|x ] = E [ k ] = (k + 1)∆ 2
12 .

heading: 2.1.1 RELATIONSHIP WITH TERNARY AND STOCHASTIC QUANTIZATIONS
text: Here, we examine the relation between the dithered quantization, Ternary quantization of Wen et al. (2017) and the stochastic quantization in Alistarh et al. (2017). Without loss of generality, assume that the vector x is normalized such that |xi| ≤ 1. Although the reconstruction of quantized values in our method is different from those in TernGrad and QSGD, we show that these quantizers can be considered as a special case of the half-dithered quantizer.
M -level Stochastic Quantization in Alistarh et al. (2017) is defined as
Q(s)(xi) = { sign(xi) l/M with probability l + 1−M |xi| sign(xi) (l + 1)/M with probability M |xi| − l , (1)
where |xi| ∈ [l/M, (l + 1)/M ]. The ternary quantizer of Wen et al. (2017) can be considered as a special case of stochastic quantizer with M = 1. Lemma 2. Stochastic quantization is the same as (2M + 1)-level half-dithered quantizer with step-size ∆ = 1M and uniform dither u ∼ U [− 1 2M , 1 2M ].
In other words, stochastic quantizer adds a uniformly distributed dither to the input signal before quantization, but at the receiver, it does not subtract the dither from the quantized value. Therefore, the quantization error is not independent of the signal Gray & Stockham (1993). It can be easily verified that although the quantization is unbiased, E [ x−Q(s)(x) ] = 0, its variance depends on the value of the input signal:
E [ ([Q(s)(x)− x]i)2 ] = (|xi| − l/M)((l + 1)/M − |xi|), if |xi| ∈ [l/M, (l + 1)/M ].
It can be easily verified that the variance of the quantization error varies in the interval [0, 14M2 ] depending on the value of x. If x is uniformly distributed over [−1, 1], the average quantization variance would be 16M2 , twice the variance of the dithered quantization.

heading: 2.2 NESTED QUANTIZATION
text: Here, we briefly overview the definition and some properties of the nested quantization. Especially we focus on the one dimensional case as our algorithm is based on scalar quantization. Definition (Nested Quantizers). The pair (Q1, Q2) of two quantizers are nested if and only if ∀x, Q1(Q2(x)) = Q2(x), but the opposite does not necessarily hold. Q1(·) and Q2(·) are called the fine and coarse quantizers, respectively.
As a result, the centers of the quantization bins in the coarse quantizer is a subset of those of the fine quantizer. In the one dimensional case, if Q1 and Q2 have quantization step sizes equal to ∆1 and ∆2, respectively, it can be easily verified that they are nested if and only if there exists a constant integer k > 1 such that ∆2 = k∆1. For the definition and properties of higher di-
mensional nested quantization using lattices please refer to Zamir et al. (2002); Zamir (2009) and references therein.

heading: 3 DISTRIBUTED TRAINING USING DITHERED QUANTIZATION
text: LetW ⊂ Rn be a known set of possible parametersw and L :W → R be a differentiable objective function to be minimized. A stochastic gradient g of L(w) is an unbiased random estimator of the gradient, i.e., g is a random function such that E[g] = ∇wL. Specifically, ifL(w) = Ex∈X [f(x;w)], whereX is the set of training data samples and f(x;w) is a smooth differentiable parametric function, then given a mini-batch {x1, . . . ,xL} of training samples, the stochastic gradient of L(w) can be computed as g = 1L ∑ l∇wf(xl;w).
We consider the distributed training scenario shown in Fig. 2. There are P separate workers (processing nodes) which have their own copy of the model to be trained. At each iteration of the training, each worker computes a stochastic gradient of the parameters gk, or the update in the parameters δWk, based on its own available data. It is then transmitted to a server (in the centralized training) or communicated with other workers (in the decentralized topology) to compute the average. The average of all gradients or the updates (ḡ or ¯δW ) is then broadcasted back to all workers. In the following, we focus on the distributed training using stochastic gradients with a centralized ag-
gregation node. First, we consider the use of dithered quantization in training and analyze the convergence of the learning algorithm in both single worker and distributed (multiple workers) training scenarios. Next, we observe that the stochastic gradients computed at the workers are correlated. We define a correlation model to capture the dependency between SGs of the workers and show that how nested dithered quantization can help further reducing the communication bits at each iteration of training without sacrificing the accuracy or the number of iterations to converge.

heading: 3.1 DITHERED QUANTIZED STOCHASTIC GRADIENT
text: We consider the dithered quantization of SG (DQSG) as follows: Let Q(·) be a uniform quantizer with quantization step size ∆, and u ∼ U [−∆/2,∆/2] be the random dither signal. The dithered quantized SG is given by
g̃ = κ ( Q ( g/κ+ u ) − u ) , (2)
where the scale factor κ = ‖g‖∞ = maxi |gi| maps the gradient into the range [−1, 1]. By Thm. 1, the scaled quantization noise e = (g − g̃)/κ will be independent from g and uniformly distributed over [−∆/2,∆/2]. Note that by setting ∆ = 1/M , we will have a 2M + 1 level quantizer with quantization bins’ indexes in {−M, . . . ,−1, 0, 1, . . . ,M}. Lemma 3. Let g be a stochastic gradient of L(w). Then, the DQSG, g̃, has the following properties:
P1. g̃ is unbiased, i.e., E[g̃] = ∇wL, P2. Its variance is bounded as E [ ‖g̃ −∇wL‖22 ] ≤ n∆ 2 12 E [ ‖g‖22 ] + E [ ‖g −∇wL‖22 ] .
Especially, if we assume that the difference between the stochastic gradients and the true ones behaves like a Gaussian noise, i.e., g −∇wL = ν where ν ∼ N (0, σ2)2, then
E [ ‖g̃ −∇wL‖22 ] − E [ ‖g −∇wL‖22 ] ≤ ∆ 2 3 ln( √ 2n) E [ ‖g −∇wL‖22 ] + n∆2 6 ‖∇wL‖2∞. (3)
As a result of Lemma 3, we observe that the excess variance caused by quantization is proportional to ∆2. Hence by adding 1 bit, i.e., doubling the number of quantization levels, it is reduced by a factor of 4. Further, we notice that how partitioning the stochastic gradient into K sub-vectors can reduce the variance of DQSG at the expense of extra communication bits. Let g̃K be the DQSG resulted from partitioning g into K sub-vectors and quantizing them separately. For the simplicity of analysis assume that the partitions are of equal length, n/K. Simple calculations reveal that
E [ ‖g̃K −∇wL‖22 ] −E [ ‖g −∇wL‖22 ] ≤ ∆ 2
6
[ 2 ln( √ 2 n K )E [ ‖g −∇wL‖22 ] + n‖∇wL‖2∞ ] (4)
2Usually, the SG is computed as g = 1 L ∑ l∇wf(xl;w) and for large enough L, due to the central limit
theorem, g −∇wL d→ N (0,Σ/ √ L) for an appropriate fixed covariance matrix Σ.
The first term decreases logarithmically w.r.t. the number of partitions. On the other hand, each partition requires transmitting an additional scale factor (κ in (2), see Alg. 1), incurring extra Kb bits in total, where b is the number of bits for each scale factor. Hence, the excess communication bits due to partitioning increases linearly, while the first term in the excess variance decreases logarithmically.
Convergence Analysis. We now analyze the convergence of the gradient descent algorithm with the dithered quantized stochastic gradients. At the t-th iteration, the parameters are updated as
wt+1 = wt − ηtg̃t, (DQSGD) where ηt is the learning rate and g̃t is the DQSG.
Recall that g̃ = g + ‖g‖∞ , where ∼ U [−∆/2,∆/2] is the quantization noise, independent of g. Hence, training with dithered quantized SG is the same as training with non-quantized SG corrupted by an independent bounded uniform noise. If the quantization step size and hence the noise is controlled appropriately, the quantization noise can improve the training of very deep models Neelakantan et al. (2015); Noh et al. (2017)
Moreover, analyzing the convergence of (DQSGD) is almost the same as the ordinary SGD. For example, since E [ ‖g̃‖22 ] ≤ ( 1 + n∆ 2
12
) E [ ‖g‖22 ] , under the same assumptions as of Bottou (1998),
the convergence of DQSGD can be proven, which is replicated here for the sake of completeness. Theorem 4. Assume that i) L(w) has a single minimum, w∗, ii) ∀ > 0, inf‖w−w∗‖2> (w − w∗)T∇wL > 0, iii) ∑ t ηt = +∞ and ∑ t η 2 t < +∞, and iv) for some constants A and B,
stochastic gradients satisfy E [ ‖g(w)‖22 ] ≤ A+B‖w −w∗‖22. Then for any quantization step size ∆ ≤ 1, training with DQSGD converges to the solution almost surely.
Next, we investigate how the number of workers and quantization step size affects the training time in the proposed distributed training scheme.
Distributed Training with DQSGD. Algorithm 1 summarizes the proposed distributed training with P workers using dithered quantization of SG (DQSG). The p-th worker, first computes the stochastic gradient gp and then using the scale parameter κp = ‖gp‖∞, computes the quantization index qp (see Remark 1). Hence, the DQSG is given by g̃p = κp(∆.qp − up). To be able to reproduce the (pseudo-)random sequences at the server, the same random number generator algorithm and seed number, sp, is used at both the worker and the server. At each iteration of training, the seed numbers are updated according to a predetermined algorithm at all workers and the server, to prevent generating the same random sequences repeatedly.
Using the above distributed training algorithm, the following result on the convergence time of distributed (DQSGD) algorithm can be proved. Theorem 5. LetW ⊂ Rn be a convex set and L(w) be a convex, Lipschitz-smooth function with constant `3. Further, assume that L achieves its minimum at w∗ and has bounded gradients almost everywhere, i.e., for a constant B > 0, ‖∇L‖2 ≤ B. Let the initial point for the learning algorithm be w0 and R = supw∈W ‖w − w0‖2. Consider distributed training algorithm (Alg. 1) on P workers using (DQSGD) with quantization step size ∆. Suppose that the workers can compute stochastic gradients with variance bound V , i.e,. E [ ‖gp −∇wL‖22 ] ≤ V . Define σ2 = V (1 + n∆2/12) + nB∆2/12. Then for sufficiently small > 0, after T steps of training with constant step size ηt, where
T = 2.5 R2 2 σ2 P , and ηt = /( `+ 1.1σ2/P ),
we have
E [ L ( 1
T T∑ t=1 wt
)] − L(w∗) ≤ .
Let Tc be the training time without any quantization in the above setup. Then, it can be easily verified that the training time of the dithered quantization is increased by
T − Tc Tc = n∆2 12
( 1 + B
V
) . (5)
3i.e., ‖∇L(w1)−∇L(w2)‖2 ≤ `‖w1 −w2‖2
Algorithm 1: Distributed Training Using Dithered Quantization of SG Initialization
- Assign a random seed sp to the p-th worker and initialize the parameters with w0, p = 1, 2 . . . , P . - Keep a copy of sp’s at the server. - Set ∆, the quantization step-size, and the associated uniform quantizer, Q(·).
for each iteration of training do Workers p = 1, 2, . . . , P :
- Get a batch of training data and compute the stochastic gradients gp. - Generate a pseudo-random sequence up, uniformly distributed over [−∆/2,∆/2] using seed sp. - Compute the quantization index: qp = bt/∆e where t = gp/κp + up and κp = ‖g‖∞. - Update the seed number sp. - Send κp and qp (or the corresponding quantization bin).
Server : - Reproduce the pseudo-random sequence up using the seed number sp. - Reconstruct the gradient of the p-th worker as g̃p = κp (∆.qp − up). - Update the seed number sp. - Compute the average SG, ¯̃g = 1
P ∑ p g̃p, and broadcast it to the workers.
Workers p = 1, 2, . . . , P : - Receive average SG, ¯̃g. - Update parameters according to the the preset training algorithm (SGD, ADAM, ...).

heading: 3.2 REDUCING COMMUNICATION OVERHEAD BY NESTED QUANTIZATION
text: It is well-known that correlated signals can be communicated more efficiently via distributed compression than the traditional entropy based coding Slepian & Wolf (1973). Nested Quantization has been proven to be a viable tool in communicating correlated data Zamir et al. (2002). Here, we propose to use nested quantization in distributed learning.
Let (Q1, Q2) be a pair of nested quantizers with quantization step sizes ∆1 and ∆2, respectively and 0 < α ≤ 1 be a shrinkage factor whose value to be determined later. To quantize and transmit x, the worker first generates a random dither u ∼ U [−∆1/2,∆1/2] and computes t = αx + u. Then it quantizes and encodes it as s = Q1(t)−Q2(t), (6) i.e., it transmits the position of the fine quantization bin relative to the coarse one (shown by indexes −1, 0, 1 in Fig. 3). At the receiver, by knowing s alone, x cannot be estimated reliably as multiple values can produce the same s. To resolve that ambiguity, it is required to know which coarse quantization bin x belongs to. This is achieved by the help of the information provided by y, available at the receiver. x is reconstructed from the received s and using y as follows:
r = s− u− αy, x̂ = y + α(r −Q2(r)). (7)
Note that quantizing x does not require y, however estimating x at the server depends on the information provided by y.
Figure 3 shows an example of using nested quantization, where ∆1 = 1 and ∆2 = 3. Let x = −4.2 and u = 0.3 be the generated dither. Assume α = 1, hence s = Q1(−3.9) − Q2(−3.9) = −4 − (−3) = −1 is the signal to be transmitted. Note that multiple points can produce the same s with that dither signal, some are shown by in the figure, e.g., −4.3.,−1.3, 2.7, . . . all leads to the same s. However, having access to y = −3.4 at the receiver can resolve the ambiguity. The value which resides in the same coarse quantization bin as y is chosen, resulting in x̂ = −4.3. Note that in this nested quantization scheme, the output of quantizer is in
{−1, 0,+1}. If we wanted to achieve the same accuracy with a single quantizer, we had to transmit
s = −4 instead of s = −1, increasing the number of bits depending on the range of x. For example, in Fig. 3, nested quantization reduces the range of quantization indexes from {−4,−3, . . . , 4} to {−1, 0, 1}, reduction by a factor of 3.
Algorithm 2: Distributed Training Using Nested Dithered Quantization of SG Workers p = 1, 2, . . . , P
if p ∈ P1 then - Generate random dither up ∼ U [−∆1/2,∆1/2] - Transmit sp = Q1(gp + up) else if p ∈ P2 then - Generate random dither up ∼ U [−∆(p)1 /2,∆ (p) 1 /2]
- Use nested dithered quantizer; transmit sp = Qp1(αpgp + up)−Qp2(αpgp + up) Server
- Compute g̃ = 1|P1| ∑
p∈P1 g̃p using received quantized gradients of workers in P1 for p ∈ P2 do
- Reproduce random dither up ∼ U [−∆(p)1 /2,∆ (p) 1 /2] - Compute r = sp − up − αpg̃ - Decode the SG of worker p as g̃p = g̃ + αp(r −Qp2(r)) - Update g̃ using g̃p.
Our proposed distributed training using nested dithered quantization is summarized in Alg. 2 for one iteration of training 4. The stochastic gradient, computed by the p-th worker in a distributed training system, can be considered as a noisy estimate of the true gradient, i.e., gp = ∇wL+ νp where νp is a zero-mean noise. However, as opposed to Zamir et al. (2002) and other similar works, the exact gradient ∇wL is not available in distributed training. To overcome this issue, we propose to divide the workers into two groups. Set P1 of workers use DQSG with quantization step size ∆1, to provide an initial estimate for the true gradient. The parameter of the quantization and the number of workers in P1 are chosen such that the variance of averaged DQSG (see Lemma 3) becomes in an acceptable range, determined by Thm. 6. The workers in P2 use nested quantizer with step-sizes (∆(p)1 ,∆ (p) 2 ) and scale αp. To decode the received Nested Dithered Quantized SG (NDQSG), the receiver uses the average of all SGs already received and decoded from other workers, denoted by g̃. We assume that the SG of the p-th worker can be modeled as gp = g̃ + zp, where zp is an independent random noise. Hence, the nested quantization uses g̃ at the receiver as the side information to compute g̃p. To find the quantization parameters, we can use the following result;
Theorem 6. If the SG at a worker is modeled by g = ¯̃g+z, E [ z2i ]
= σ2z , and the worker uses nested quantizer with parameters ∆1, ∆2 and α, then with probability at least 1− p, g̃i will be estimated correctly (i.e., gi and g̃i are in the same coarse quantization bin), where
p = Pr ( |αz + u| > ∆2
2
) ≤ ∆ 2 1
3∆22 + 4α2 σ2z ∆22 , u ∼ U [−∆1/2,∆1/2]. (8)
Specially if |z| < ∆2−∆12α , then p = 0. In this case,
E [ ‖g̃ − g‖22 ] = α2
∆21 12 + (1− α2)2σ2z . (9)
Note that setting α = 1 or α = √
1−∆21/12σ2z results in the same quantization variance as dithered quantization with step-size ∆1. However, nested quantization requires log2(∆p2/∆p1) bits to transmit each value, i.e., less than the ordinary quantization methods which requires almost log2(2/∆p1) bits.
4Note that we have ignored details on reproducing the pseudo-random sequences uk’s and updating seed numbers which are the same as in Alg. 1.

heading: 4 EXPERIMENTS
text: We examine the convergence and and the number of communication bits used by different learning algorithms based on DQSG and nested dithered quantized SG (NDQSG) for various number of workers, and compare them against the baseline (no quantization of gradients), one-bit quantization Seide et al. (2014), TernGrad Wen et al. (2017), and QSGD Alistarh et al. (2017). Although it is possible to evaluate the performance of the quantization and compression schemes in both synchronous and asynchronous settings, here we assume that the workers and server are synchronous. The main reason for such a setting is to cancel-out the performance degradation (in terms of training accuracy or speed) that may be caused by the stale gradients in asynchronous updates, and to solely investigate the effect of the quantization/compression algorithms.
We have considered three different models, a fully connected neural network with two hidden layers of sizes 300 and 100 over MNIST dataset (herein, referred to as FC-300-100), a Lenet-5 like convolutional network LeCun et al. (1998) over MNIST and a convolutional network Krizhevsky (2014) on Cifar10 (referred to as CifarNet), with SGD and Adam training algorithms. The initial learning rates for SGD and Adam are 0.01 and 0.001, respectively with decay rate 0.98 per training epoch. The batch size is fixed at 256 and divided evenly among the workers.
First, we observe that using entropy coding algorithms such as Adaptive Arithmetic Coding (ACC) can further reduce the communication bits for all schemes close to the entropy limit (within 5% range). Therefore, it suffices to report both the number of raw communication bits from quantization as well as the resulting entropy of the bit-stream for comparison. Tables 1 and 2 show the raw (uncompressed) communication bits and the entropy per worker at each iteration of training, respectively. The communication bits of DQSGD and QSGD are close to each other. Although One-bit quantization requires less raw bits to transmit, it is less compressible, e.g., using entropy coding for Lenet, DQSGD would use 6 times less number of bits per iteration compared to one-bit quantization.
Figure 4 shows the accuracy of the final trained model vs different number of workers for FC-300-100 and Lenet models. Table 3 shows the results for CifarNet model after 50 epochs ot training. From the simulations, it is seen that our proposed algorithm performs much better than the one-bit quantization method and is close to the baseline performance (non-quantized communication).
Moreover, in Fig. 5, we have compared the convergence rate of our dithered quantization scheme w.r.t. baseline (no quantization), one-bit quantization Seide et al. (2014) and QSGD Alistarh et al. (2017) for 4 and 8 workers. It is interesting to note that the dithered quantization improves the convergence of the training algorithm even when compared to the baseline (no quantization) in terms of number of training iterations. Although we do not have any analytic proof that using dithered quantization would always improve the convergence speed w.r.t. no quantization, because of the independency of the noise from the SGs in our proposed method, our method is likely to result in a better convergence property than the aforementioned techniques for complex training data Neelakantan et al. (2015);
Noh et al. (2017). On the other hand, as the number of workers increases, due to the averaging performed on the received quantized SGs, the noise would decrease proportionately and we expect the performance gap between different quantization methods eventually vanishes.
Next, we compare our nested dithered quantizer with the dithered quantization scheme. To have fair comparison, we chose the same expected accuracy for both quantization schemes. For DQSG, we chose M = 2, hence ∆ = 0.5 and the output of quantizer would be in {−2, . . . ,−2}. In NDQSG, for half of the workers, we divided the workers to two groups, half of the workers use DQSG with the same ∆ and the other half, uses NDQSG with ∆1 = 1/3 and ∆2 = 1. Hence, the output of NDQSG quantizer is in {−1, 0, 1}. In Fig. 6 we compared the accuracy of NDQSG with DQSG and baseline training during training. As seen, the learning curve of NDQSG is almost the same as DQSG and the baseline. However, the communication bits are much less. For example, in training FC-300-100, with 2 level quantizers, QSG and DQSG requires 619.2 Kbits per worker to communicate, while NDQSG
reduces that to 422.8 Kbits, more than 30% reduction in number of bits to communicate. The Same is true for the other considered neural networks.

heading: 5 CONCLUSION
text: In this paper, first, we introduced DQSG, dithered quantized stochastic gradient, and showed that how it can reduce communication bits per training iteration both theoretically and via simulations, without affecting the accuracy of the trained model. Next, we explored the correlation that exists among the SGs computed by workers in a distributed system and proposed NDQSG, a nested quantization method for the SGs. Using theoretical analysis as well as simulations, we showed that NDSQG performs almost the same as DQSG in terms of accuracy and training speed, but with much fewer number of communication bits.
Finally, we would like to mention that although the simulations and analysis of the proposed distributed training method is done in synchronous training setup, it is applicable to the asynchronous training as well. Further, our nested quantization scheme can be easily extended to hierarchical distributed structures.

heading: A PROOF OF LEMMA 2
text: Let Q(·) be a 2M + 1-level quantizer with step size ∆ = 1/M . Let u ∼ U [−∆/2,∆/2] be the dither signal. Let 0 ≤ x ≤ 1 be an arbitrary number. Assume that l/M ≤ x < (l+ 1)/M and define d = x− l/M . Note that 0 ≤ d < ∆ and
P ( Q(x+ u) = l
M
) = P ( |x+ u− l/M | ≤ ∆
2
) = P ( u ≤ ∆ 2 − d ) = 1− d ∆ = 1−Md.
Similarly, P (Q(x + u) = (l + 1)/M) = Md. Comparing with stochastic quantizer, we see that they both assign the quantization points with the same probability. The case x < 0 can be verified similarly.

heading: B PROOF OF LEMMA 3
text: To prove the unbiasedness, note that by Thm. 1, e = Q(g/κ+ u)− (g/κ+ u) is independent from g/κ and uniformly distributed over [−∆/2,∆/2]. On the other hand, g̃ = g + κe. Hence,
E[g̃] = E[g + κe] (a)= E[g] + E[κ]E[e] (b)= ∇L, where (a) is due to the fact that κ = ‖g‖∞ is independent of e and (b) because of unbiasedness of stochastic gradient and e having mean zero.
For the variance, E [ ‖g̃ −∇L‖22 ] = E [ ‖g −∇L‖22 ] + E [ ‖g‖2∞ ] Var[e] (c) ≤ Var[g] + E [ ‖g‖22 ]n∆2 12 ,
where (c) follows from E [ ‖e‖22 ] = ∑n i=1 E [ (ei) 2 ]
= n∆2/12, and ‖g‖∞ ≤ ‖g‖2. To prove (3), note that for a given g,
E [ ‖g̃ − g‖22 ∣∣g] = ‖g‖2∞n∆212 ⇒ E[‖g̃ − g‖22] = E[‖g‖2∞]n∆212 . Let µ = ∇wL. The assumed model for g implies that g ∼ N (µ, σ2) and E [ ‖g −∇wL‖22 ] = nσ2. For an arbitrary t > 0,
etE[‖g‖ 2 ∞]
(d) ≤ E [ etmaxi |gi| 2 ] = E [ max i et|gi| 2 ] ≤ ∑ i E [ et|gi| 2 ] ,
where (d) follows from Jensen’s inequality and definition of ‖ · ‖∞. Since gi ∼ N (µi, σ2), E [ et|gi| 2 ] = 1√
1− 2tσ2 exp
( µ2i t
1− 2tσ2
) , for 0 ≤ t ≤ 1
2σ2 .
Therefore,
etE[‖g‖ 2 ∞] ≤ n∑ i=1 E [ et|gi| 2 ] = 1√ 1− 2tσ2 ∑ i exp ( tµ2i 1− 2tσ2 ) ≤ n√ 1− 2tσ2 exp ( t‖µ‖2∞ 1− 2tσ2 ) E [ ‖g‖2∞ ] ≤ 1 t ln ( n√ 1− 2tσ2 ) + ‖µ‖2∞ 1− 2tσ2 .
Setting t = 1/4σ2 gives the desired bound in (3).

heading: C A NOTE ON THM. 4
text: Because of the nature of quantization noise in our approach, the majority of convergence results with stochastic gradients can be readily applied to the DQSG. As an example, in this paper, we considered a result by Bottou (1998). To prove the convergence of (DQSGD), it suffices to show that there exists constants A′ and B′ such that E [ ‖g̃(w)‖22 ] ≤ A′ +B′‖w −w∗‖22;
E [ ‖g̃(w)‖22 ] (e) = E [ ‖g̃ − g‖22 ] + E [ ‖g‖22 ] = n∆2 12 E [ ‖g‖2∞ ] + E [ ‖g‖22 ] ≤ (1 + n∆ 2 12 )E [ ‖g‖22 ] .
Therefore, for A′ = (1 + n∆ 2 12 )A and B ′ = (1 + n∆ 2
12 )B, the DQSG is bounded and the theorem is proved following the same argument as in Bottou (1998).

heading: D A NOTE ON THM. 5
text: This is a direct result of (Bubeck, 2015, §6). Note that E [ ‖g̃ −∇wL‖22 ] ≤ V + n∆ 2 12 E [ ‖g‖22 ] ≤ V (1 + n∆ 2 /12) + nB∆ 2 /12 = σ2 and since there are P workers, the variance bound on g̃ would be
σ2/P . Then after T iterations of (DQSGD) with step size ηt = 1/(`+ 1/γ) for γ = Rσ/√P √ 2/T ,
E [ L ( 1
T T∑ t=1 wt
)] − L(w∗) ≤ R √ 2σ2
PT + `R2 T .
For < 0.2σ2/PL, set
T = 2.5 R2σ2
P 2 .
Then, it can be easily verified that for the given step-size, the results hold.

heading: E PROOF OF THM. 6
text: Let e = αg + u−Q1(αg + u) and r = s− u− α¯̃g. Then,
ĝi = ¯̃gi + α(ri −Q2(ri)).
Since ¯̃gi = gi + zi, it can be shown that
ri −Q2(ri) = αzi − ei −Q2(αzi − ei).
Therefore, ĝi = ¯̃gi + α(αzi − ei)− αQ2(αzi − ei).
The correct decoding occurs when Q2(αzi − ei) = 0. Hence, the probability of correct recovery would be 1− p where
p = Pr ( |αz + u| >
∆2 2
) , u ∼ U [−∆1/2,∆1/2].
In that case, ĝi = gi − (αei + (1− α2)zi).
Since ei ∼ U [−∆1/2,∆1/2] and zi are independent from each other and from gi, simple calculations show that
E [ (g̃i − gi)2 ] = α2
∆21 12 + (1− α2)2σ2z .

Review summaries:
In this paper, the authors propose to apply dithered quantization (DQ) to the stochastic gradients computed through the training process. Though an extra noise is added to the gradient, it improves the quantization error. Hence after the noise is removed at the update server, it achieves superior results when compared against unquantized baseline.

Authors establish a connection between communication reduction in distributed optimization and dithered quantization. This allows us to understand prior approaches in a new perspective, and also motivates authors to develop two new distributed training algorithms which communication overhead is significantly reduced. The first algorithm, DQSG, uses dithered quantization to reduce the communication bits. The second algorithm, NDQSG, uses nested dithered quantization to further reduce the amount of needed communication. The usefulness of these algorithms are empirically validated by computing the raw communication bits and average entropy of them. Therefore, dithered communication seems to provide both theory and algorithm which are useful.