Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization
Authors: Ali Ramezani-Kebrya
Fartash Faghri
Ilya Markov
Vitalii Aksenov
Dan Alistarh
Daniel M. Roy
Venue:  (2020)

Abstract: As the size and complexity of models and datasets grow, so does the need for communication-efficient variants of stochastic gradient descent that can be deployed on clusters to perform model fitting in parallel. Alistarh et al. (2017) describe two variants of data-parallel SGD that quantize and encode gradients to lessen communication costs. For the first variant, QSGD, they provide strong theoretical guarantees. For the second variant, which we call QSGDinf, they demonstrate impressive empirical gains for distributed training of large neural networks. Building on their work, we propose an alternative scheme for quantizing gradients and show that it yields stronger theoretical guarantees than exist for QSGD while matching the empirical performance of QSGDinf.

Under review as a conference paper at ICLR 2020
NUQSGD: PROVABLY COMMUNICATION-EEFICIENY DATA-PARALIE PARALLEL SGD VIA NONUNIFORM QUANTIZA- TION
ABSTRACT
As the size and complexity of models and datasets grow, so does the need for communication-efficcant variants of stochastic gradient descent that can be de- ployed on clusters to perform parallel model training. Alistarh et al. (2017) describe two variants of data-parallel SGD that quantize and encode gradients lessen communication costs. For the first variant, QSGD, they provide strong theoretical guarantees. For the second variant, which we call QSGDinf, they demonstrate im- pressive empirical gains for distributed training of large neural networks. Building on their work, we propose an alternative scheme for quantizing gradients and show that it yields stronger theoretical guarantees than exist for QSGD while matching the empirical performance of QSGDinf.
INTRODUCTION
Deep learning is booming thanks enormous datasets and very large models, leading the fact that the largest datasets and models can no longer be trained on a single machine. One common solution to this problem is to use distributed systems for training. The most common algorithms underlying deep learning are stochastic gradient descent (SGD) and its variants, which led to significant amount of research on building and understanding distributed versions of SGD.
Implementations of SGD on distributed systems and data-parallel versions of SGD are scalable and take advantage of multi-GPU systems. Data Pata-parallel SGD, in particular, has received significant attention due to its excellent scalability properties (Zinkevich et al., 2010; Bekkerman et al., 201 I; Recht et al., 2011; Dean et al., 2012; Coates al., 2013; Chilimbi al., 2014: Li et al., 2014: Duchi et al., 2015; Xing et al., 2015; Zhang et al., 2015; Alistarh et al., 2017). In data-parallel SGD, large dataset is partitioned among processors. These processors work together to minimize an objective function. Each processor has access to the current parameter vector of the model. At each SGD iteration, each processor computes an updated stochastic gradient using its own local data. It then shares the gradient update with its peers. The processors collect and aggregate stochastic gradients to compute the updated parameter vector.
Increasing the number of processing machines reduces the computational costs significantly. However, the communication costs to share and synchronize huge gradient vectors and parameters increases dramatically as the size of the distributed systems grows. Communication costs may thwart the anticipated benefits of reducing computational costs. Indeed, in practical scenarios, the communica- tion time required to share stochastic gradients and parameters the main performance bottleneck (Recht et al., 2011: Li et al., 2014; Seide et al., 2014; Strom, 2015; Alistarh et al., 2017). Reducing communication costs in mata-parallel SGD is an important problem.
One promising solution to the problem of reducing communication costs of data nata-parallel SGD is gradient compression, e.g., through gradient quantization (Dean et al.. 2012: Seide et al., 2014: Sa et al., 2015; Gupta et al., 2015; Abadi et al., 2016; Zhou et al., 2016; Alistarh et al., 2017; Wen et al., 2017; Bernstein et al., 2018). (This should not be confused with weight quantivation/sparsffccall studied by Wen al. (2016); Hubara et al. (2016); Park al. (2017); Wen et al. (2017), which do not discuss here.) Unlike full-precision Kata-parallel SGD, where each processor is required to broadcast its local gradient in full-precision, i.e., transmit and receive huge full-precision vectors at each iteration, guantization requires each processor to transmit only a few communication bits per iteration for each component of the stochastic gradient.
One popular such proposal for communication compptisoonoompmssiiionnoooo is quantized SGD (QSGD), due to Alistarh et al. (2017). In QSGD, stochastic gradient vectors are normalized to have unit 1.2 norm,

---

Under review as a conference paper at ICLR 2020
and then compressed by quantizing each element uniform grid of quantization levels using randomized method. While most lossy compression schemes do not provide convergence guarantees, QSGD's quantization scheme, is designed to be unbiased, which implies that the quantized stochastic gradient is itself a stochastic gradient, only with higher variance determined by the dimension and number of quantization levels. As result, Alistarh et al. (2017) are able to establish number of theoretical guarantees for QSGD, including that it converges under standard assumptions. By changing the number of quantization levels, QSGD allows the user to trade-off communication bandwidth and convergence time.
Despite their theoretical guarantees based on quantizing after L normalization, Alistarh et opt to present empirical results using L normalization. We call this variation QSGDinf. While the empirical performance of QSGDinf is strong, their theoretical guarantees on the number of bits transmitted no longer apply. Indeed, in our own empirical evaluation of QSGD, we find the variance induced by quantization is substantial, and the performance is far from that of SGD and QSGDinf.
Given the popularity of this scheme, it is natural to ask one can obtain guarantees as strong as those of QSGD while matching the practical performance the QSGDinf heuristic. this work, we answer this question in the affirmative by providing new quantization scheme which fits into QSGD in a way that allows us to establish stronger theoretical guarantees on the variance, bandwidth, and cost to achieve a prescribed gap. Instead of QSGD's uniform quantization scheme, we an unbiased nonuniform logarithmic scheme, similar to those introduced in telephony systems for audio compression (Cattermole, 1969). We call the resulting algorithm nonuniformly quantized stochastic gradient descent (NUQSGD). Like QSGD, NUQSGD is quantized data-parallel SGD algorithm with strong theoretical guarantees that allows the user trade off communication costs with convergence speed. Unlike QSGD, NUQSGD has strong empirical performance on deep models and large datasets, matching that of QSGDinf. In particular, we provide a new efficient implementation for these schemes using a modern computational framework (Pytorch), and benchmark it on classic large-scale image classification tasks.
The intuition behind the nonuniform quantization scheme underlying NUQSGD is that, after L2 nor- malization, many elements of the normalized stochastic gradient will near-zero. By concentrating quantization levels near zero, are able to establish stronger bounds on the excess variance. In the overparametrized regime interest, these bounds decrease rapidly as the number of quantization levels increases. Combined with a bound on the expected code-length, we obtain a bound on the total communication costs of achieving an expected suboptimality gap. The resulting bound is slightly stronger than the one provided by QSGD.
To study how quantization affects convergence on state-of-the-aar deep models, we compare NUQSGD, QSGD, and QSGDinf, focusing training loss, variance, and test accuracy on standard deep models and large datasets. Using the same number bits per iteration, experimental results show that NUQSGD has smaller variance than QSGD, as expected by our theoretical results. This smaller variance also translates to improved optimization performance, in terms of both training loss and test accuracy. We also observe that NUQSGD matches the performance of QSGDinf in terms of variance and loss/accuracy. Further, our distributed implementation shows that the resulting algo- rithm considerably reduces communication cost of distributed training, without adversely impacting accuracy. Our empirical results show that NUQSGD can provide faster end-to-end parallel training relative to data-parallel SGD, QSGD, and Freo-Feedbbck SignSGD (Karimireddy et al., 2019) on the ImageNet dataset.
Summary of Contributions.
We establish stronger theoretical guarantees for the excess variance and communication costs of our gradient quantization method than those available for QSGD's s uniform quantization method.
We then establish stronger convergence guarantees for the resulting algorithm, NUQSGD, under standard assumptions.
We demonstrate that NUQSGD has strong empirical performance deep models and large datasets, both in terms of accuracy and scalability. Thus, NUQSGD closes the gap between the theoretical guarantees of QSGD and the empirical performance of QSGDinf.
2

---

Under review as a conference paper at ICLR 2020
1.1 RELATED WORK
Seide et al. (2014) proposed signSGD, an efficient heuristic scheme to reduce communication costs drastically by quantizing each gradient component to twO values. Bernstein et al. (2018) later provided convergence guarantees for signSGD. Note that the quantization employed by signSGD is not unbiased, and so new analysis was required. As the number of levels is fixed. SignSGD does not provide any trade-off between communication costs and convergence speed.
Sa al. (2015) introduced Buckwild!, lossy compressed SGD with convergence guarantees. The authors provided bounds on the error probability of SGD, assuming convexity and gradient sparsity.
Wen et al. (2017) proposed TemGrad, a stochastic quantization scheme with three levels. Temnradd also significantly reduces communication costs and obtains reasonable accuracy with small degra- dation to performance compared to full-precision SGD. Convergence guarantees for TernGrad rely on nonstandard gradient norm assumption. As discussed, Alistarh et al. (2017) proposed QSGD, more general stochastic quantization scheme, for which they provide both theoretical guarantces and experimental validation (although for different variants of the same algorithm). We note that their implementation was only provided in Microsoft CNTK; by contrast, here we provide a more generic implementation in Horovod (Sergeev and Del Balso, 2018), communication back-end and which can support a range modern frameworks such as Tensorflow, Keras, Pytorch, and MXNet.
NUQSGD uses logarithmic quantization scheme. Such schemes have long been used in telephony systems for audio compression (Cattermole, 1969). Logarithmic quantization schemes have appeared in other contexts recently: Hou and Kwok (2018) studied weight distributions of long short-term memory networks and proposed to use logarithm quantization for network compression. Zhang et al. (2017) proposed gradient compression scheme and introduced an optimal quantization scheme, but for the setting where the points to be quantized are known in advance. As result, their scheme is not applicable to the communication setting of quantized data aata-parallel SGD.
2 PRELIMINARIES: DATA- SGD AND CONVERGENCE
We consider a high- sitbddimensioaal machine learning model, parametrized by a vector w E Rd Let Ω C Rd denote a closed and convex set. Our objective minimize f Ω + E. which is an unknown, differentiable, convex, and B-smooth function. The following summary is based on (Alistarh et al., 2017).
Recall that function f is ß-smooth if, for all u. v.V. Q, we have [V - Vf(v) S B Bluu vll- where ||-1| denotes the Euclidean norm. Let (5// E. be probability space (and let denote expectation). Assume we have access to stochastic gradients of f. i.e. we have access = V((w) for all w E Q. In the rest of the paper, we let g(w) denote the stochastic gradient for notational simplicity. The update rule for conventional full-precision projected SGD is W/+1 = Pa(w,- 0tg (w))), where w, is the current parameter input, is the learning rate, and Pa is the Euclidean projection onto Ω
function
g: Q -- Rdd such that, v μ. then (lg((,,)) (,,
We say the stochastic gradient has a second-moment upper bound when E F[llg(w)13 S B for all w E Ω. Similarly, the stochastic gradient has variance upper bound σ² when [[]lo() ff(w) Il o² for all w E Ω. Note that a second-moment upper bound implies variance upper bound, because the stochastic gradient is unbiased.
We have classical convergence guarantees for conventional full-precision SGD given access to stochastic gradients at each iteration:
Theorem (Bubeck 2015, Theorem 6.3). Let f R denote a convex and B-smooth function and let R² A supwea ww 2o Suppose that the projected SGD update is executed for 'I' iterations with a 1/(B 1/r) where /= / o. Given repeated and independent access to stochastic gradients with variance upper bound σ², projected SGD satisfies
2
BR
E
min f(w) WEQ
< R
(1)
T
T
Minibatched (with larger batch sizes) and data aata-parallel SGD are two common SGD variants used in practice to reduce variance and improve computational efficiency of conventional SGD.
3

---

Under review as a conference paper at ICLR 2020
Input:
local data, local copy of the parameter vector w,, learning rate a, and K
f = 1 to do
for
// each transmi processor (in parallel)
Compute gi( (w):: stochastic gradient
Encode çi2 ENCODE(g((W))
Broadcast to all processors;
for
do each receiver processor (in parallel)
for i= to K do // each transmitted processor
Receive ç₁2 from processor i for cach i;
Decode (i(w;, < (EC)DE(<;:):
10
Aggregate W/+1 + Po(w; Algorithm 1: Data- parallel (synchronized) SGD.
* - (:(w)));
Following (Alistarh et al., 2017), we consider data-parallel SGD, synchronous distributed framework consisting of K processors that partition large dataset among themselves. This framework models real-world systems with multiple GPU resources. Each processor keeps local copy of the parameter vector and has access to independent and private stochastic gradients of f.
At each iteration, each processor computes its stochastic gradient based its local data and then broadcasts it to all peers. Each processor receives and aggregates the stochastic gradients from all peers to obtain the updated parameter vector. In detail, the update rule for full-precision data- parallel SGD is w = Pa(w, (w, R -"=18: 87 (w;)) where 87 (,,w) is the stochastic gradient computed and broadcasted by processor I. Provided that gi (w,) is stochastic gradient with variance upper bound 6² for all I, then & Σ (w,) is stochastic gradient with variance upper bound g² Thus, aggregation improves convergence of SGD by reducing the first term of the upper bound in (1). Assume each processor computes minibatch gradient of size B. Then, this update rule is essentially a minibatched update with size BK.
Data-parally SGD is described in Algorithm 1. Full- puel-preciiion data mata-parallel SGD is special case of Algorithm with identity encoding and decoding mappings. Otherwise, the decoded stochastic gradient (ww,, is likely to be different from the original local stochastic gradient g:( (w,).
By Theorem 1, we have the following convergence guarantees for full full-precision data-parallel SGD:
Corollary 1 (Alistarh et al. 2017, Corollary 2.2). Let R. and be defined in Theorem 1 and let e >> O. Suppose that the projected SGD update is executed for iterations with a I/(B + /K/r) on K processors, each with access to independent stochastic gradients of f with a second-moment bound B. The smallest T for the full-precision data-pate paral-pallllll SGD that guarantees [[f( E w:)] mfn (w) S Te OR max( 2B B
Ke
NONUNIFORMLY QUANTIZED STOCHASTIC GRADIENT DESCENT
Data-parallel SGD reduces computational costs significantly. However, the communication costs of broadcasting stochastic gradients is the main performance bottleneck in large-scale distributed systems. In order reduce communication costs and accelerate training, Alistarh al. (2017) introduced a compression scheme that produces a compressed and unbiased stochastic gradient, suitable for use in SGD.
At each iteration of QSGD, each processor broadcasts an encoding of its own compressed stochastic gradient, decodes the stochastic gradients received from other processors, and sums all the quantized vectors to produce a stochastic gradient. In order to compress the gradients, every coordinate (with respect to the standard basis) of the stochastic gradient normalized by the Fuclidean norm the gradient and then stochastically quantized to one of small number quantization levels distributed uniformly in the unit interval. The stochasticity of the quantization is necessary to not introduce bias.
Alistarh et al. (2017) give simple argument that provides a lower bound the number of coordinates that are quantized to zero in expectation. Encoding these zeros efficiently provides communication savings each iteration. However, the cost of their scheme is greatly increased variance in the gradient, and thus slower overall convergence. In order to optimize overall performance, we must balance communication savings with variance.
4

---

Under review as a conference paper at ICLR 2020
060
1-0000
Figure 1: An example of nonuniform stochastic quantization with The point between the arrows represents the value of the normalized coordinate.
438
Figure Variance upper bounds.
By simple counting arguments, the distribution of the (normalized) coordinates cannot be uniform. Indeed, this is the basis of the lower bound on the number of zeros. These arguments make no assumptions on the data distribution, and rely entirely on the fact that the quantities being quantized are the coordinates of unit-norm vector. Uniform quantization does not capture the properties of such vectors, leading to substantial gradient variance.
3.1 NONUNIFORM QUANTIZATION
In this paper, we propose and study a new scheme to quantize normalized gradient vectors. Instead of uniformly distributed quantization levels, as proposed by Alistarh et al. (2017), we consider quantization levels that are nonuniformly distributed the unit interval, as depicted Figure 1. In order to obtain quantized gradient that is suitable for SGD, need the quantized gradient to remain unbiased. Alistarh et al. (2017) achieve this via a randomized quantization scheme, which can be easily generalized the case of nonuniform quantization levels.
Using a carefully parametrized generalization of the unbiased quantization scheme introduced by control both the cost of communication and the variance of the gradient.
Alistarh et al., Compared to a uniform quantization scheme, our scheme reduces quantization error and variance by better matching the properties of normalized vectors. In particular, by increasing the number of quantization levels near zero, we obtain stronger variance bound. Empirically, our scheme also better matches the distribution of normalized coordinates observed on real datasets and networks.
We now describe the nonuniform quantization scheme: Let s [1,2,-...} be the number of internal quantization levels, and let L 11,,4,,- .b+1) denote the sequence of quantization levels, where to = 0 11 ... < 4+1 1. For E [0, 1]. let 3(r) and p(r) satisfy (av)) S S 1str3-1 and (1 p(r)) + +( respectively. Define v(r) la (pp)- Note that 5(r) {0, 1,.1,,.. s...
Definition 1. The nonuniform quantization of vector E IRd is
e.(v) (.. .2((va) where Qs(vi) = signn()) (v,))));(vv))
(2)
where, letting = |w/////// the h,(v,))ss are independent random variables such that (v with probability 1 p(ri) and hy(v.s) 1s(n)+1 otherwise.
(5(rr)
We note that the distribution of h:(v,s) satisfies [v,ssv s)]= = and achieves the minimum variance over all distributions that satisfy E[h, (v,s)) = f with support L. In the following, we focus on special case nonuniform quantization with & = (0, 1/2", .........111/1 12-, as the quantization levels.
The intuition behind this quantization scheme is that it is very unlikely observe large values of ry in the stochastic gradient vectors of machine learning models. Stochastic gradients are observed to be dense vectors (Bersttei et al., 2018). 8). Hence, it is natural to use fine intervals for small r; values to reduce quantization error and control the variance.
After quantizing the stochastic gradient with small number of discrete levels, each processor must encode its local gradient into a binary string for broadcasting. We describe this encoding in Appendix A.
5

---

Under review as a conference paper at ICLR 2020
4 THEORETICAL GUARANTEES
In this section, we provide theoretical guarantees for NUQSGD, giving variance and code-length bounds, and using these in turn to compare NUQSGD and QSGD. Please note that the proof's of Theorems 2, 3, 4, and 5 are provided in Appendices B, C, D, and E respectively.
Theorem 2 (Variance bound). Let v E Rd. The nonuniform quantization of satisfies E[Q,(v)) = Furthermore, provided that s S log(d) /2, we have
(v) - s
(3)
where EQ min (d
va 32 +1)]
The result in Theorem 2 implies that if g(w) is a stochastic gradient with a recond-momen bound 17, then Qs (gw)) is stochastic gradient with variance upper bound EQT In the range of interest where d is sufficiently large, i.e., = o (I))())), the variance upper bound decreases with the number of quantization levels. To obtain this data- iata-independent bound, we establish upper bounds the number of coordinates of falling into intervals defined by L.
Theorem 3 (Code-length bound). Let v E Rd. Provided d is large enough to ensure 2 + vd2' S ddje, the expectation E|JENCODE(()) of the number of communication bits needed to transmit Q.(v) is bounded above by
No= -C=C+300 C+33,, + (1+ (1+o(1)) log (12 nz,d
d ) (1 (1+o
8(225 ()))++))
(4)
Bz,d
where C b- (1+( and psd = 2 + /d.
Theorem 3 provides bound on the expected number of communication bits encode the quantized stochastic gradient. Note that 2 + Vd2 <. d//e is a mild assumption in practice. As one would expect, the bound, (4), increases monotonically d and s. In the sparse case, if we choose s ologd) levels, then the upper bound on the expected code-length is 0(2 (2 (vd))
Combining the upper bounds above on the variance and code-length, Corollary implies the following guarantees for NUQSGD:
Theorem 4 (NUQSGD for smooth convex optimization). Let f and R be defined as in Theorem 1, let Eo be defined as in Theorem 2, let E > 0, B = BB) and let y > 0 be given by y² = 2R² (BT). With ENCODE and DECODE defined as in Appendix A, suppose that Algorithm is executed for T iterations with a learning rate a = l/(B + /K/r) on K processors, each with access to independent stochastic gradients of f with second-momen bound B. Then Te = 0 max ( Kez
2B B R²) iterations
suffice to guarantee E [f (+ Σ w;)] minwea.((w) S E. In addition, NUQSGD requires at most No communication bits per iteration expectation.
On nonconvex problems, (weaker) convergence guarantees can be established along the lines of, e.g.. (Ghadimi and Lan, 2013, Theorem 2.1).
NUQSGD QSGD. How do QSGD and NUQSGD compare in terms of bounds the expected number of communication bits required to achieve a given suboptimality gap E? The quantity that controls our guarantee on the convergence speed in both algorithms is the variance upper bound, which in turn is controlled by the quantization schemes. Note that the number of quantization levels, s, is usually a small number in practice. On the other hand, the dimension, d, can be very large, especially in overparameterizeed networks. In Figure 2, we show that the quantization scheme underlying NUQSGD results in substantially smaller variance upper bounds for plausible ranges of s and d. Note that these bounds do not make any assumptions the dataset or the structure of the network.
For any (nonrandom) number of iterations T, an upper bound, NA. holding uniformly over iterations k < T on the expected number bits used by an algorithm to communicate the gradient on iteration k, yields upper bound TN on the expected number of bits communicated over T iterations by algorithm A. Taking T TAe to be the (minimum) number of iterations needed to guarantee an expected suboptimality gap of e based on the properties of A. we obtain an upper bound, SA.e = NA on the expected number of bits of communicated on a run expected to achieve a suboptimality gap of at most

---

Under review as a conference paper at ICLR 2020
2.00
NUO55O
Moan hormatzed
SuperStD
22100
0.75
10-3
0,50
10
10a
Training
Trarring fteation
Figure 3: Training loss on CIFARIO (left) and ImageNet (middle) for ResNet models. QSGD, QSGDinf, and NUQSGD are trained by simulating the quantization and dequantizing of the gradients from 8-GPUs. On CI,ARIO, SGD refers to the single-GPU training versus on Imagenet it refers to 2-GPU setup in the original ResNet paper. SGD is shown to highlight the significance of the gap between QSGD and QSGDinf. SuperSGID refers to simulating full-precision distributed training without quantization. SuperSGiD is impractical in scenarios with limited bandwidth. (Right) Estimated normalized variance on CIFARIO on the trajectory of singlc-GPU SGD. Variance is measured for fixed model snapshots during training. Notice that the variance for NUQSGD and QSGDinf is lower than SGD for almost all the training and it decreases after the learning rate drops.
Theorem 5 (Expected number of communication bits). Provided that = o(log(d)) and 28 Ke
> B
ŚNUQSGD. = 0 /d(d - 200d-22))loo log
- 2F
and foSGD.E 0 d vd).
Focusing on the dominant terms in the expressions of overall number of communication bits required to guarantee a suboptimality gap of e, we observe that NUQSGD provides slightly stronger guarantees. Note that our stronger guarantees come without any assumption about the data. 5 EXPERIMENTAL EVALUATION
In this section, examine the practical performance of NUQSGD in terms of both convergence (accuracy) and speedup. The goal is to empirically show that NUQSGD can provide the same performance and accuracy compared to the QSGDInf heuristic, which has no theoretical compression guarantees. For this, we implement and test these three methods (NUQSGD, QSGD, and QSGDInf), together with the distributed full-precision SGD baseline, which we call SuperSGD. We split our study across two axes: first, we examine the convergence of the methods and their induced variance. Second, we provide an efficient implementation of all four methods in Pytorch using the Horovod communication back-end (Sergeev and Del Balso, 2018), adapted to efficiently support quantization, and examine speedup relative to the full full-precision baseline. We investigate the impact of quantization on training performance by measuring loss, variance, accuracy, and speedup for ResNet models (He al., 2016) applied to ImageNet (Deng et al., 2009) and CIFARIO (Krizhevsky).
We evaluate these methods on two image classification datasets: ImageNet and CIFARIO. We train ResNetl 10 on CIFARIO and ResNet18 on ImageNet with mini-batch size 128 and base learning rate 0. In all experiments, momentum and weight decay are set to 0.9 and 10-4 respectively. The bucket size and the number of quantization bits are set to 8192 and 4, respectively. We observe similar results in experiments with various bucket sizes and number of bits. We simulate scenario with k GPUs for all three quantization methods by estimating the gradient from k independent mini-batches and aggregating them after quantization and dequantization.
In Figure 3 (left and middle), we show the training loss with 8 GPUs. We observe that NUQSGD and QSGDinf improve training loss compared to QSGD on ImageNet. We observe significant gap in training loss on CIFAR 10 where the gap grows as training proceeds. We also observe similar performance gaps in test accuracy (provided in Appendix F). In particular, unlike NUQSGD, QSGD does not achieve test accuracy of full- preciiiin SGD. Figure 3 (right) shows the mean normalized variance of the gradient (defined in Appendix F) versus training iteration on the trajectory of single- GPU SGD on 1.. These observations validate our theoretical results that NUQSGD has smaller variance for large models with small number of quantization bits.
Efficient Implementation and Speedup. To examine speedup behavior, we implemented all quanti- zation methods in Horovod (Sergeev and Del Balso. 2018), a communication back-end supporting Pytorch, Tensorflow and MXNet. Doing so efficiently requires non-trie trivial refactoring of this frame- work, since it does support communication compression- our framework will be open-sourced
7

---

Under review as a conference paper at ICLR 2020
CAITLAR LOND
TashsiCo, tudih 50a-256. manter
24
Sur0oo NUDDOD-MM
300+
20ki solat sodos m6do sooks co000 L0000
Figure Scalability behavior for NUQSGD versus the full-precision baseline when training ResNer34 and ResNet50 on ImageNet. The ResNet34 graph examines strong scaling (left), splitting a global batch of size 256 onto the available GPUs, whereas the ResNet50 graph examines strong scaling (middle) keeping a fixed per- batch size of 16. Each time bar is split into computation (bottom), encoding cost (middle), and transmission cost (top). Notice the significant negative scalability of the SGD baseline in both scenarios. By contrast, the 4-bit communication-compress achieves positive scaling, while the 8-bit variant stops scaling between 4 and 8 nodes due to the higher communication and encoding costs. End-to-end training time for ResNet50/ImageNe for NUQSGD and EF-SignSGD versus the SuperSGD baseline (right).
implementation
upon publication. Our implementation diverges slightly from the theoretical analysis. First, Horovod applies "tensor fusion" to multiple layers, by merging the resulting gradient tensors for more efficient transmission. This causes the gradients for different layers to be quantized together, which can lead to loss of accuracy (due to e.g. different normalization factors across the layers). We addressed this by tuning the way in which tensor fusion is applied to the layers such that it minimizes the accuracy loss. Second, we noticed that quantizing the gradients corresponding to the biases has a significant adverse effect on accuracy; since the communication impact of biases is negligible, we transmit them at full precision. We apply this for all methods considered. Finally, for efficiency reasons, we directly pack the quantized values into 32-bit numbers, without additional encoding. We implemented compression and de-compression via efficient CUDA kernels.
Our baselines are full-precision SGD (SuperSGD), Error-Feedback SignSGD (Karimireddy et al., 2019), and the QSGDinf heuristic, which we compare against the 4-bit and 8-bit NUQSGD variants executing the same pattern. The implementation of the QSGDinf heuristic provides almost identical convergence numbers, and is sometimes omitted for visibility. (QSGD yields inferior convergence on this dataset and is therefore omitted.) All variants are implemented using a standard all-to-all reduction pattern. Figures 4 (left), (middle) show the execution time per epoch for ResNet34 and ResNet50 models on ImageNet, on a cluster machine with 8 NVIDIA 2080 Ti GPUs, for the hyper- parameter values quoted above. The results confirm the efficiency and scalability of the compressed variant, mainly due to the reduced communication volume. We note that the overhead of compression and decompression is less than 1% of the batch computation time for NUQSGD.
Figure 4 (right) presents end-to-end speedup numbers (time versus accuracy) for ResNeet50/lmaeeett, executed on 4 GPUs, under the same hyperparameter settings as the full-precision baseline, with bucket size 512. First, notice that NUQSGD variants match the target accuracy of the 32-bit model, with non-trivial speedup over the standard data-parallel variant, directly proportional to the per- epoch speedup. The QSGDinf heuristic yields similar accuracy and performance, and is therefore omitted. Second, we found that unfortunately EF-SignSGD does not converge under these standard hyperparameter settings. To address this issue, we performed non-trivial amount of hyperparameter tuning for this algorithm: in particular, we found that the scaling factors and the bucket size must be carefully adjusted for convergence on ImageNet. We were able to recover full accuracy with FF-SignSGDD on ResNet50, but that the cost of quantizing into buckets of size 64. Unfortunately, in this setting the algorithm transmits non-trivial amount of scaling data, and the GPU implementation becomes less efficient due to error computation and reduced parallelism. The end-to-end speedup of this tuned variant is inferior NUQSGD-4bil and only slightly superior to that of NUQSGD-S3 Please see Figure in the Appendix and the accompanying text for details.
6 CONCLUSIONS We study data- parallel and communication--fficie ing QSGD (Alistarh et al., 2017), we study a nonuniform quantization scheme. We establish
version of stochastic gradient descent. Build-
8

---

Under review as a conference paper at ICLR 2020
upper bounds the variance of nonuniform quantization and the expected code-length. In the overparametrized regime of interest, the former decreases as the number of quantization levels increases, while the latter increases with the number of quantization levels. Thus, this scheme provides a trade-off between the communication efficiency and the convergence speed. We compare NUQSGD and QSGD in terms of their variance bounds and the expected number of communication bits required to meet a certain convergence error, and show that NUQSGD provides stronger guar- antees. Experimental results are consistent with our theoretical results and confirm that NUQSGD matches the performance of QSGDinf when applied to practical deep models and datasets including ImageNet. Thus. NUQSGD closes the gap between the theoretical guarantees of QSGD and empirical performance of QSGDinf. One limitation of our study which we aim to address in future work is that we focus on all-to-all reduction patterns, which interact easily with communication compression. In particular, we aim to examine the interaction between more complex reduction patterns, such as ring-basce reductions (Hannun et al., 2014), which may yield superior performance in bandwidth- bottlenecked settings, but which interact with catpuuuiiaatioooompesett in non-trivial ways, since they may lead a gradient to be quantized at each reduction step.
REFERENCES
D. Alistarh, D. Grubic, J. Z. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication-effciiene SGD via gradient quantization and encoding. In Proc. Advances in Neurul Information Processing Systems (NIPS), 2017.
M. Zinkevich, M. Weimer, L. Li, and A. J. Smola. Parallelized stochastic gradient descent. In Proc. Advances in Neural Information Processing Systems (NIPS), 2010.
R. Bekkerman, M. Bilenko, and J. Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011.
B. Recht, C. Ré, S. Wright, and F. Niu, Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Proc. Advances in Neural Information Processing Systems (NIPS), 2011.
Dean, G. Corrado, R. Monga K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, Q. V. Le, and A. Y. Ng. Large scale distributed deep networks. In Proc. Advances in Neural Information Processing Systems (NIPS), 2012.
A. Coates, B. Huval, T. Wang, D. Wu, B. Catanzaro, and A. Ng. Deep learning with cots hpc systems. In Proc. International Conference on Machine Learning (ICML), 2013.
T. Chilimbi, Y. Suzue J. Apacible, and K. Kalyanaraman. Project adam: Building efficient and scalable deep learning training system. In Proc. USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2014.
M. Li, D. G. Andersen, W. Park, A. J. Smola, A. Ahmed, V. Josifovski, Long, E. J. Shekita, and B.-Y. Su. Scaling distributed machine learning with the parameter server. In Proc. USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2014.
J. C. Duchi, S. Chaturapruck, and C. Ré. Asynchronous stochastic convex optimization. In Proc. Advances in Neural Information Processing Systems (NIPS), 2015.
E. P. Xing, Q. Ho, W. Dai, J. K. Kim, J. Wei, S. Lee, X. Zheng, P. Xie, A. Kumar, and Y. Y. Petuum. Petuum: A new platform for distributed machine learning on big data. IEEE transactions on Big Data, (22):99-77, 2015.
S. Zhang, A. F. Choromanska, and Y. LeCun. Deep learning with elastic averaging SGD. In Proc. Advances in Neural Information Processing Systems (NIPS), 2015.
Seide, H. Fu, J. Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In Proc. INTERSPEECH, 2014.
N. Strom. Scalable distributed DNN training using commodity GPU cloud computing. Proc. INTERSPEECH, 2015.

---

Under review as a conference paper at ICLR 2020
C. M. D. Sa, Ce. Zhang, K. Olukotun, and C. Ré. Taming the wild: A unified analysis of hogwild-style algorithms. In Proc. Advances in Neural Information Processing Systems (NIPS), 2015.
S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan. Deep learning with limited numerical precision. In Proc. International Conference on Machine Learning (ICML), 2015.
M. Abadi, A. Agarwal, Barham, E. Brevdo, Z. Chen, C. Citro, G. Corrado, A. Davis, J. Dean, and M. Devin. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv:1603.04467, 2016.
S. Zhou, Y. Wu, Z. Ni, X. Zhou, H. Wen, and Y. Zou. Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients. AxXiv:660606611 2016.
W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang. Y. Chen, and H. Li. TernGrad: Ternary gradients to reduce communication distributed deep learning. Proc. Advances Neural Information Processing Systems (NIPS), 2017.
Bernstein, Y.-. Wang, K. Azizzadenesheli, and A. Anandkumar. signSGD: Compressed optimisa- tion for non-convex problems. In Proc. International Conference Machine Learning (ICML), 2018.
W. Wen, C. Wu, Y. Wang, Y. Chen, and H. Li. Learning structured sparsity in deep neural networks. In Proc. Advances in Neural Information Processing Systems (NIPS), 2016.
I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio. Binarized neural networks. In Proc. Advances in Neural Information Processing Systems (NIPS), 2016.
Park, S. Li, W. Wen, P. Tang. H. Li, Y. Chen, and P. Dubey, Faster CNNs with direct sparse convolutions and guided pruning. In Proc. International Conference on Learning Representations (ICLR), 2017.
K. W. Cattermole. Principles of pulse code modulation. Iliffe, 1969.
Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in tensorflow. arXiv preprint
2018.
L. Hou and J. T. Kwok. Loss-aware weight quantization deep networks. In Proc. International Conference Learning Representations (ICLR), 2018
H. Zhang, Li, K. Kara, D. Alistarh, J. Liu, and C. Zhang. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In Proc. International Conference Machine Learning (ICML), 2017.
S. Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-358, 2015.
Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341 12662288811288, 2013.
K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Deng. W. Dong, R. Socher, L.-J. Li, Li, and L. Fei-Fei. ImageNet: A large-scale hierarchical image database. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In Proc. International Conference on Machine Learning (ICML), 2019.
10

---

Under review as a conference paper at ICLR 2020
Awni Hannun, Carl Case, Jared Casper, Bryan Catanzaro, Greg Diamos. Erich Elsen, Ryan Prenger, Sanjeev Satheesh, Shubho Sengupta, Adam Coates, et al. Deep speech: Scaling up end-to-end speech recognition. arXiv preprint arXiv:1412.5550 2014.
P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2):194 203, 1975.
S. Boyd and I., Vandenberghe. Convex Optimization. Cambridge Univ. Press, 2004.
A ENCODING
Encoding:
Place a O at the end of the string; if N == 1 then
Stop;
else
Prepend bin to the beginning;
Let N' denote bits prepended minus 1;
Encode N' recursively;
Decoding:
Start with N 1:
then Stop and return N: 11 else
the next bit
Read that bit plus N following bits; Update N; Algorithm 2: Elias recursive coding produces bit string encoding positive integers.
13
By inspection, the quantized gradient Q+(v) determined by the tuple (I]v]], h)),, where ||v|] is the norm of the gradient, p e [sign(v1), .ag......iin....... (vg)()>)]" is the vector of signs of the coordinates vy's, and A [h (v,s),.... ... (v))) are the quantizations the normalized coordinates. We can describe the ENCODE function (for Algorithm in terms of the tuple (Ilv]I.p.l p.)) h) and an encoding/decoding scheme ERC: (1,2,....) {0,1) and ERC {0, 13' + (1,2....) for encoding/decoding positive integers.
The encoding, ENCODE(V), of stochastic gradient is as follows: We first encode the norm ||v|] using b bits where, in practice. we use standard 32-bit floating point encoding. We then proceed rounds, r 0, I..... On round r, having transmitted all nonzero coordinates up and including f, we transmit ERC(i,) where f 1, + i, is either (i) the index of the first nonzero coordinate of after f, (with to 0) (ii) the index of the last nonzero coordinate. In the former case, we then transmit one bit encoding the sign P., transmit ERC(log(2"** h )), and proceed to the next round. In the latter case, the encoding is complete after transmitting P.,, and ERC(logg22 (2--1),,.))) h),,)))
The DECODE function (for Algorithm 1) simply reads b bits reconstruct /v/ Using ERC-I, decodes the index of the first nonzero coordinate, reads the bit indicating the sign, and then uses ERC again determines the quantization level of this first nonzero coordinate. The process proceeds in rounds, mimicking the encoding process, finishing when all coordinates have been decoded.
Like Alistarh et al. (2017), we use Elias recursive coding (Elias, 1975, ERC) encode positive integers. ERC simple and has several desirable properties, including the property that the coding scheme assigns shorter codes to smaller values, which makes sense in our scheme they are more likely to occur. Elias coding is a universal lossless integer coding scheme with a recursive encoding and decoding structure.
The Elias recursive coding scheme is summarized in Algorithm 2. For any positive integer N, the following results are known for ERC (Alistarh et al., 2017):
1. ERC(N) < (I (1+)( IogN
2. ERC(N) can be encoded and decoded in time O[ERCC(N]))
11

---

Under review as a conference paper at ICLR 2020
3. Decoding be done without knowledge of an upper bound on N.
B PROOF OF THEOREM 2 (VARIANCE BOUND)
We first find simple expression of the variance of Q,(v) for every arbitrary quantization scheme in the following lemma:
Lemma 1. Let E Rd, L- 1...4.... ..+1). and fix 2 The variance of Qs(v) for general
sequence of quantization levels is given by
Bl)l.((v) - =1 Σ (())p(n)(1-p(n)))
(5)
where r; = lv:l/llvlll and p(r), t(r) are defined in Section 3.1.
Proof. Noting the random quantization i.i over elements of stochastic gradient, can decom-
pose [v]l2.(v) v| as:
E B - v = Σ o2)
(6)
where d²(r)) -E(((v,))))) r2) Computing the variance of (v,vs)), we can show that (2 (nn)p(n) p(ri)..
In the following, we consider NUQSGD algorithm with & = zation levels. Then, h (v,,s))ss are defined in two cases based which quantization interval r; falls into:
122,1) as the quanti-
rf 00, -) then
h((ys) {
{ 0 2- otherwise
with probability pi (ri,s);
where Pı (r:s) 2'r.
2) rf si-tt, for j 0,.., ,s- then
- { 2
with probability p2(ri,);;
h((v,s) - 2/+1-
otherwise
where p2 (r.s) ---11--1 Note that (.)
Let , denote the coordinates of vector v whose elements fall into the (j+ 1)-th bin, iee. A 2 {i:
|0,2-]] and SJ+1 {i: ri E 1 2/++- for j = 0,,.., s- 1. Let dj [5Sl) Applying the result of Lemma 1, we have
Elle.(v) =1|]=1|<[|? 1|v112
Σ (0(r:s)(1-pi(rr..)))
+||
Σ
7
Σ
(1-pas)((-p((ms))))) p2(n..))
0
15.7
where r, 11+1 -1, for (0..... .s..........
Substituting to - and T 2/-1-5 1-s for E (1,.., ,s} into (9), have
12

---

Under review as a conference paper at ICLR 2020
-+) - -1|]=111112 2x E
-
iEv0
+
+|11/|
Σ 22(
Σ
-1((::)(1-P2(mm))))
167
< <|111/2
E
(i(ris))
(10)
+||v||
Σ
22 s)
Σ p2(ri,s)
1=0
iE//41
We first note that Lie (r),,)) 2 d and 5m (2(ri,)) d for all i.e., upper bound on the variance (v(v) is given by E[| (v(v) - v & [ 2++1 + 1). Furthermore, we have
E PI (+. S min (do, do) 15
(11)
Dio |w] [ S
since
Vdg. Similarly, we have
E p2(n.s) S min(d 11- vd iE7
(12)
Substituting the upper bounds in (11) and (12) into (10), an upper bound on the variance of (v(v) is given by
Bllle.(v) -vl <
(13)
Σ min (2 (2)1 2
/dj+i
The upper bound in (13) cannot be used directly as it depends on {do, J.). Note that dj's depend on quantization intervals. In the following, we obtain an upper bound on []]l[,(v) v/13], which depends only d and s. To do so, we need use this lemma inspired by (Alistarh al., 2017, Lemma A.5): Let || Ilo count the number of nonzero components.
Lemma 2, Let v E Rd. The expected number of nonzeros in Qs(v) is bounded above by
Bille, < 2 ddo2".
Proof. Note that --de do < 2nd since
2 < (d do)
Σ 7 1
(14)
ig.7
For each i E .o. (v:)) becomes zero with probability - 2"r which results in
(vlle((v) < d- 1d do Σ r;2
iE9
2² + v ''2'.
(15)
Using similar argument in the proof of Lemma 2, have
d- do - dj dj (5-
(16)
for j 1, 1. Define b, A 2 2/-- for O.....5 1. Then
bn < do
bi + do
:
byt do + ..... d,-1-
(17)
13

---

Under review as a conference paper at ICLR 2020
Note that d, - do
dz-1-
We define
do è bo d 225
di _ lj bo = 3 221111
dz A b5- - b 12
d, _ dg
d=-1=4
(18)
Note that do S do. d1 + do s d1 + do. dy +..... do-
d, do S ds 1 +.... ... do. and d, + +.. do =
Noting that the coefficients of the additive terms in the upper bound in (13) are monotonically increasing with j. we can find an upper bound on (.) v|| (do, (do....d,) .d. in (13), which gives (3) and completes the proof.
by replacing (do, .d,) with
C PROOF OF THEOREM 3 (CODE-LENGTH BOUND)
Let |-1 denote the length of a binary string. In this section, we find an upper bound on B[JENCODE(V)] i.e., the expected number of communication bits per iteration. Recall from Appendix A that the quantized gradient Qv(v) determined by the tuple (l))). Write ilbilo for the indices of the h nonzero entries of h. Let io = 0.
The encoding produced by ENCODE(v) can be partitioned into two parts, R and E, such that, for =
hh/o-
R contains the codewords ERC(iJ- ii--) encoding the runs of zeros; and
E contains the sign bits and codewords ERC(log(2*t)h,) encoding the normalized quan- tized coordinates.
Note that ||[i,, i,, ... /lbi/ - i/n -- I|ll S d. Thus, by (Alistarh et al., 2017, Lemma A.3), the properties Elias encoding imply that
d
R| < [bloo (1 (1+o()))bblll
(19)
|
We now turn to bounding [E]. The following result in inspired by (Alistarh et al., 2017, Lemma A.3).
Lemma 3. Fix a vector q such that || S P, let i < <... <i.ll be the indices of its ||qllo nonzero entries, and assume each nonzero entry is form 28 for some positive integer k. Then
Igllo
) + ll
((L(
+ +[++o([))lglloogglg))
||
14

---

Under review as a conference paper at ICLR 2020
Proof. Applying property (1) for ERC (end of Appendix A), we have
ollo
alo
(RC((og(4;))) s +0(1))
log log + +////o
$ (1+o
+ || lo
Iallo log log og
+(++0(1))
{1+0(1)) + 1/
P |lallo
+ +1)+
where the last bound is obtained by Jensen's inequality.
Taking q = 2=2+th, h, note that |///2
2 h |
and
)
h
+
|
d
Σ
+
2221111111
(20)
|
2
22x
By Lemma applied and the upper bound (20),
| (1+++(1))) + 2
22 ||b||
(21)
+ (1 + (1+ (L)lol)))lllllloll
|
Combining (19) and (21), we obtain an upper bound on the expected code-length:
E|JENCODE(M)] <((ll)))
(22)
where
d
N(Joh]lo) = = +
(23)
8(22) +d) }]
-(++o))==(+(()))(
h
is not difficult to show that, for all k > 0, g: (x) A xlog (+) is concave. Note that gi is an increasing function up to x == k/e.
Defining 8x(x) A xloglo log (f) and taking the second derivative, we have
(x) (a00)=(xxxn0000) (IIn))) (1((//())))
(24)
Hence 82 is also concave on x < C. Furthermore, 82 increasing up to some C/5 <xx' < <C/4.
We note that E| bblo]] < 2 + /d2" following Lemma 2. By assumption 2 + Vd2 < d/e, and so, Jensen's inequality and (22) lead us (4).
D PROOF OF THEOREM 4 (NUQSGD FOR SMOOTH CONVEX OPTIMIZATION)
Let g(w) and ((w) denote the full-precision and decoded stochastic gradients, respectively. Then [[ll((w) - -VW [8]] (w) Vf(w) [13] + [ g(w))
(25)
By Theorem 2, = w) [)] By assumption, Eillg(w) ( [w] < B. Noting g(w) unbiased, Elll@(w) = The result follows by Corollary 1.
15

---

Under review as a conference paper at ICLR 2020
1e-6
2.5
mmma
SGD
Normalized Variance
1.25
QSGD
Mean variance
2.0
QSGDinf
1.5
NUQSGD
SuperSGD
1.0
0.50
0.5
0.0
Training Iteration
1e4
Training Iteration
1e4
Figure 5: Estimated variance (left) and normalized variance (right) CIFARIO the trajectory of single-GPU SGD. Variance is measured for fixed model snapshots during training. Notice that the variance for NUQSGD and QSGDinf lower than SGD for almost all the training and it decreases after the learning rate drops. All methods except SGD simulate training using 8 GPUs. SuperSGD applies no quantization to the gradients and represents the lowest variance we could hope to achieve.
E PROOF OF THEOREM 5 (EXPECTED NUMBER OF COMMUNICATION BITS)
Assuming 28 B then Te 0 28 Kea
Kez R²). Ignoring all but terms depending d and have TE = (B/e²). Following Theorems 2 and 3 for NUQSGD, GNUOSGD. = O(NeegB/e"). For QSGD, following the results of Alistarh et al. (2017), ŞQSGD.E = =N(ooegB/e /E²) where No = 3(s² +sdd) b and & min vdd
2 +o(1)) svdd (2(2+d) 2avd
In overparameterized networks, where d 2 2 have Eo 2 2 2'v VVd-2 O(s) and Èg vd/s. Furthermore, for sufficiently large d, No and No are given by 0(2'vdlog () and O(s/dlog(Vdd) respectively.
F ADDITIONAL EXPERIMENTS
Test Accuracy (%)
80
60
Test Test Accuracy
SGD
50
QSGD
QSGDinf
NUQSGD
30
40
SuperSGD
Training Iteration
1e4
Training Iteration
1e5
Figure 6: Accuracy the hold-out set CIFAR1O (left) and on ImageNet (right) for training ResNet models from random initialization until convergence. For CIFAR 10, the hold-out set the test and for ImageNet, the hold-out set is the validation set.
In this section, we present further experimental results in a similar setting to Section
In Figure 6, we show the test accuracy for training ResNetl 10 on CIFAR 10 and validation accuracy for training ResNet34 on ImageNet from random initialization until convergence (discussed in Section 5). Similar to the training loss performance, we observe that NUQSGD and QSGDinf outperform QSGD in terms of test accuracy in both experiments. In both experiments, unlike NUQSGD, QSGD does not recover the test accuracy of SGD. The gap between NUQSGD and QSGD ImageNet is significant. We argue that this achieved because NUQSGD and QSGDinf have lower variance relative to QSGD, It turns both training loss and generalization enror benefit from the reduced variance.
16

---

Under review as a conference paper at ICLR 2020
1.25
Mean Normalized Variance
Mean Normalizer Variance
1.1
1.00
1.0
0.75
SGD
0.9
0.50
QSGD
QSGDinf
0.8
0.25
NUQSGD
Super5GD
0.7
0.00
8 1e4
Training Iteration
Training Iteration
1e5
Figure 7: Estimated normalized variance CIFARIO (left) and ImageNet (right). For different methods, the variance is measured on their own trajectories. Note that the normalized variance of NUQSGD and QSGDinf is lower than SGD for almost the entire training. It decreases CIFARIO after the learning rate drops and does not grow as much as SGD on ImageNet. Since the variance depends on the optimization trajectory, these curves are not directly comparable. Rather the general trend should be studied.
We also measure the variance and normalized variance at fixed snapshots during training by evaluating multiple gradient estimates using each quantization method. All methods are evaluated on the same trajectory traversed by the single-GPU SGD. These plots answer this specific question: What would variance of the first gradient estimate be if one were to train using SGD for any number of iterations then continue the optimization using another method? The entire future trajectory may change by taking single good or bad step. We can study the variance along any trajectory. However, the trajectory of SGD is particularly interesting because it covers subset of points in the parameter space that is likely to be traversed by any first-order optimizer. For multi-dimensional parameter space, average the variance of each dimension.
Figure (left), shows the variance of the gradient estimates on the trajectory of single-Git GPU SGD on CIFAR10. We observe that QSGD has particularly high variance, while QSGDinf and NUQSGD have lower variance than single-GPU SGD.
We also propose another measure of stochasticity, normalized variance, that is the variance normalized by the norm of the gradient. The mean normalized variance can be expressed as
[ [))((:)))wv
(
where ((w:z) denotes the loss of the model parametrized by w sample and subscript A refers to randomness in the algorithm, e.g., randomness in sampling and quantization. Normalized variance can be interpreted as the inverse of Signal to Noise Ratio (SNR) for each dimension. We argue that the noise optimization is more troubling when it significantly larger than the gradient. For sources of noise such as quantization that stay constant during training, their negative impact might only observed when the norm of the gradient becomes small.
Figure 5 (right) shows the mean normalized variance of the gradient versus training iteration. Observe that the normalized variance for QSGD stays relatively constant while the unnormalized variance of QSGD drops after the learning rate drops. It shows that the quantization noise of QSGD can cause slower convergence at the end of the training than the beginning.
In Figure 7, show the mean normalized variance of the gradient versus training iteration CIFARIO and ImageNet. For different methods, the variance is measured on their own trajectories. Since the variance depends the optimization trajectory, these curves not directly comparable. Rather the general trend should be studied.
ResNet152 Weak Scaling. In Figure 8, we present the weak scaling results for ResNet152//magee Each of the GPUs receives batch of size 8, and we therefore scale up the global batch size by the number of nodes. The results exhibit the same superior scaling behavior for NUQSGD relative to the uncompressed baseline.
EF -iggSggDGD Convergence. Figure 9, we present a performance comparison for NUQSGD variants (bucket size 512) and convergent variant of EFSiSnSDGD with significant levels of parameter
17

---

Under review as a conference paper at ICLR 2020
4-bit NUSGO
25000
8-bxt NUSCD
550
20000
Time per epoch, seconds
15000
10000
5000
2 GPUs
GPUs
8 GPUs
ResNet152, weak scaling
Figure 8: Scalability behavior for NUQSGD versus the full-precision baseline when training ResNet152 on ImageNet.
80
70
Test accuracy (%)
60
50
40
32bit
30
EF-SIGNSGD (d=64)
20
NUQSGD 4bit
10
NUQSGD 8bit
0
50000
100000
150000 200000 250000
Time (sec)
Figure 9: End-to-end training time for ResNet550/mageNet for NUQSGD and EF-SignSGID versus the SGD baseline.
tuning for convergence. We believe this to be the first experiment to show convergence of the latter method at ImageNet scale, as the original paper only considers the CIFAR dataset. For convergence, we have tuned the choice of scaling factor and the granularity at which quantization is applied (bucket size). We have also considered learning rate tuning, but that not appear to prevent divergence in the early stages of training for this model. We did not attempt warm start, since that would significantly decrease the practicality of the algorithm. We have found that bucket size 64 is the highest at which the algorithm will still converge this model and dataset, and found 1-bit SGD scaling (Seide et al., 2014), which consists of taking sums over positives and over negatives for each bucket, to yield good results. The experiments executed machine with NVIDIA Titan X
18

---

Under review as a conference paper at ICLR 2020
GPUs, and batch size 256, and can be found in Figure 9. Under these hyperparameter values the SF-SigDSGD algorithm sends 128 bits per each bucket of 64 values (32 for each scaling factor, and 64 for the signs), doubling its baseline communication cost. Moreover, the GPU implementation not as efficient, as error feedback must be computed and updated at every step, and there less parallelism to leverage inside each bucket. This explains the fact that the end-to-end performance is in fact close to that of the 8-bit NUQSGD variant, and inferior to 4-bit NUQSGD.
G VARIANCE LOWER BOUND
In the following theorem, we show that for any given set of levels, there exists distribution of points with dimension d such that the variance is in ((Vd), and so our bound is tight in d.
Theorem 6 (Lower bound). Let d 7 and let (0,4,,"" ,4,, 1) denote arbitrary sequence of quantization levels. Provided d 2 (2/1)², there exists vector v IRd such that the variance of unbiased quantizatiion of V lower bounded by [[v]]lvvd/2 i.e., the variance in D(
Proof. The variance of (v) for general sequence of quantization levels is given by
Bll - -1| = |Iv1 Σ o² (ni)
I (440) 41)+ I. the variance o² (r) can be expressed as
(r = (()))((()())11-)))))))))))))))))
p(r)) (1-
(r
(26)
We consider vo = [15,,.... , _ for o 0. The normalized coordinates is 9o
Using (26) and noting 1/Vd 41, we have
- 1 22/222))
(27)
Summing variance of all coordinates and applying (27), the variance of Qs (voo) is lower bounded by
(v)) voll /lvo (r) 1/ 1/10ol//1v///
(28)
H WORST-CASE VARIANCE ANALYSIS
In this section, we first derive the optimal worst-case variance upper bound by optimizing over the distribution of normalized coordinates for arbitrary sequence of levels, expressed solution to an integer program with quadratic constraints. We then relax the program to obtain a quadratically constrained quadratic program (QCQP). A coarser analysis yields upper bound expressed solution to linear program (LP), which is more amenable to analysis. We solve this LP analytically for the special case of s and show the optimal level is 1/2.
Then, for an exponentially spaced collection of levels of the form and an integer number of levels, s, we write the expression of QCQP and solve efficiently using standard solvers. We have numerical method for finding the optimal value of p that minimizes the worst-case variance, for any given s and d. Through the worst-case analysis. we gain insight into the behaviour of the variance upper bound. We show that our current scheme is nearly optimal (in the worst-case sense) in some cases. Using these techniques we can obtain slightly tighter bounds numerically.
.p".pp for p [0, I]
H. GENERALLY SPACED LEVELS
Let L = (1. 1+)1) denote an arbitrary sequence of quantization levels where 4o 0 < h <
< 4+1 = 1. Recall that, for r E J0, 1], we define s(r) and p(r) such that they satisfy lar) S <r5
1ap=11 and (()) p(r)( respectively. Define t(r) 4 -[ar)- Note that
19

---

Under review as a conference paper at ICLR 2020
s(r) (0,1,.. .s). Then, (y,sss)ss are defined in two cases based on which quantization interval ri falls into:
If [0,11] then
hi(y,s) (1:)))/ {
with probability 1 Pi ();
(29)
otherwise
where Pı (F: = =1/4.
2) If E [4-1,1] for j == 1,..., , 3++1. 1, then
n;(v,s) = { 1
with probability 1 - p2(r1,
(30)
otherwise
where p2
Let y, denote the coordinates of vector whose elements fall into the (j+ bin, i.e.,  _ {i:
r; [[1//+1]] for j= 0, .....,, ,. Let dj- _ |-
Following Lemma 1 and steps in Theorem 2, we can show that
v Σ min tjd,,
(31)
Theorem (QCQP bound). Let E IRd. An upper bound on the nonuniform quantization of is given by Eop v|2 where EoP is the optimal value of the following QCQP:
2
max
Σ 2j
(dg em 50
2s) 1-0
subject to d do
-...-dd (1/1)t)), --.,...,,
Σ d, sd,
1=0
7/ 2) S (/dg. j= -,
d,20, j= 0 ......
Proof. Following Lemma 2, we have
d dl 5 (1/lj+1)²
(32)
for j 0.....5-11
The problem of optimizing (do, ... .d,),) to maximize the variance upper bound (31) subject to (32) is given by
min tjd [/Vdj/
(d de)
F=
subject to (32), = 0.... , 1,
Σ dj sd
(33)
1
dj E -0 j j= 0, 0.......
(34)
2e [Tdd), denote an auxiliary variable for j = -,.... ,. Problem Ei can be rewritten
as
Σ Zj
max
subject to 2j r7djj 2) < tidj, j 0,...
(35)
(32), (33), and (34).
20

---

Under review as a conference paper at ICLR 2020
The variance optimization problem 2 is an integer nonconvex problem. We obtain upper bound on the optimal objective of problem A2 by relaxing the integer constraint as follows. The resulting QSQP is shown as follows:
21
max (do. To
Σ 2j
(s) j=0
subject to dj 2 0, j= 0, ,,,
(36)
(32), (33), and (35).
Note that problem 21 can be solved efficiently using standard standard interior point-based solvers, e,g, CVX (Boyd and Vandenberghe, 2004).
In the following, we develop a coarser analysis that yields upper bound expressed the optimal value to an LP.
Theorem 8 (LP bound). Let v Rd. An upper bound on the nonuniform quantization of v is given by |/ where Epr the optimal value of the following LPP
max Σ tjds
(do: de) f=0
subject to d - do -...- S :=0,
Σ Sd,
j=
Proof. The proof follows the steps the proof of Theorem 7 for the problem of optimizing (do, dd) to maximize the following upper bound
(v)le. - v1f = |M] Σ e7dj
(37)
1=0
Corollary 2 (Optimal level). For the special case with s 1, the optimal level to minimize the worst-case bound obtained from problem P is given by I 1/2.
Proof. For 1, problem 9 is given by
Po max (dg4)
di + tid1
subject to d do S (1/1122
dy + d < d,
do 2 0, d,20
Note that the objective of Po is monotonically increasing in (do,di) ). It is not difficult to verify that the optimal (di di) is corner point on the boundary line of the feasibility region of Po. Geometrical representation shows that that candidates for an optimal solution are (1/4) (1/4))) and (d,0). Substituting into the objective of Po the optimal value of P is given by
E max 2,d, 2ed +/
(38)
Finally, note that to ti 1/2 minimizes the optimal value of Po (38).
21

---

Under review as a conference paper at ICLR 2020
lc6,
10a
le6,
0000 Opettall Valoe
109
lcf,
10
QCtP Optimal Valne
167,
10"
100
100
Figure 10: Optimal value of problem 21 versus p E [0, for exponentially spaced collection of levels of the form (O,p', "",,","""""",,..
H.2 EXPONENTIALLY SPACED LEVELS
In this section, we focus on the special case of exponentially spaced collection of levels of the form L, (0, p", ... . ... p. for p E [0, and an integer number of levels, In this case, have 50 = p" and Fj =
p)p" / for = 1.......
For any given and d. we can solve the corresponding quadratic and linear programs efficiently to find the worst-case variance bound. As a bonus, we can find the optimal value of that minimizes the worst-case variance bound. In Figure 10, we show the numerical results obtained by solving QCQP 21 with Lp versus p using CVX (Boyd and Vandenberghe, 2004). In Figure 10 (left), we fix d and vary while in Figure 10 (right), we fix and vary d. As expected, we note that the variance upper bound increases as increases and the variance upper bound decreases as s increases. We observe that our current scheme is nearly optimal (in the worst-case sense) in some cases. Further, the optimal value shifts to the right as increases and shifts to the left as s increases.
I NONCONVEX OPTIMIZATION
We can obtain convergence guarantees to various learning problems where we have convergence guarantees for SGD under standard assumptions. On nonconvex problems, (weaker) convergence guarantees can be established along the lines of, e.g., (Ghadimi and Lan, 2013, Theorem 2. 1). In particular, NUQSGI guaranteed converge a local minima for smooth general loss functions.
denote a possibly nonconvex and B-smooth function. Let Wo Q denote an initial point, Eq be defined as in Theorem infweg, f fww). Suppose that Algorithm I is executed for T iterations with
Theorem 9 (NUQSGD for smooth nonconvex optimization). Let f
T E 7270 and learning rate a = (1)B) on processors, each with access to independent stochastic gradients of with second-moment bound B. Then there exists a random stopping time E {O.... ,T} such that NUQSGD guarantees (f < where e O(B(f(w)) f" (1++))))++
22


Reviews:
[{"review_id": "r1xsybtTFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 authors propose a new scheme for quantizing gradients which are followed by the previous work QSGD [1]. They show that it yields stronger theoretical guarantees than QSGD while showing a great empirical performance. \nThe main difference between their scheme NUQSGD and QSGD is that they use nonuniform quantization (0, 1/2^{s},  …., 2^{s-1}/2^{s}, 1) instead of uniform quantization (0, 1/s, …, (s-1)/s,1).  Intuitively, by the way, it could reduce quantization error and variance by better matching the properties of normalized vectors.\nThe results are in 2 parts. First comparing with QSGD, they establish stronger convergence guarantees for NUQSGD, under standard assumptions. They also establish theoretical results for the variance upper bound and expected communication cost of their scheme. Second, they show strong empirical performance on deep models and a large dataset, with an efficient implementation in PyTorch.\n\nHowever, there are several issues and questions that if fixed or illustrated could be a great paper.\n\n\t1) The author claim NUQSGD achieves stronger convergence guarantees comparing with QSGD but hasn't illustrated the point in detail. On page 6, the paragraph named 'NUQSGD vs QSGD' mainly claims that variance upper bound controls the guarantee on the convergence speed by empirically showing the results of variance upper bound. It would be great to include more theoretical analysis which demonstrates the importance of variance upper bound for convergence speed guarantee.\n\t2) In the experimental part, they control the hyperparameters including batch-size, base learning rate, momentum, and weight decay to be identical with each method. This may cause tuning biases (the setting may favor one method but hurt others' performance).\n\t3) Although the paper mainly focuses on comparing with QSGD, there are several relative communication efficient training algorithms which I think are worth to compare empirically (at least one of them). For example:\n\t\ta. Deep Gradient compression [2]\n\t\tb. signSGD [3]\n\t\tc. TernGrad [4]\n\t4) In figure 4, the encoding cost is significantly increased from 4-bit to 8-bit NUQSGD. Any reason why it happens? Is it due to inefficient encoding implementation? \n\nI agree with the authors' point that it's worth to explore the interaction between NUQSGD with more complex reduction patterns like ring-based. Since the ring-based algorithm like all-reduce is more popular in practice nowadays, interacting with it would have a better practical meaning. \n\n[1] D. Alistarh, D. Grubic, J. Z. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication-efﬁcient SGD via gradient quantization and encoding. In Proc. Advances in Neural Information Processing Systems (NIPS), 2017.\n\n[2] Lin Y, Han S, Mao H, Wang Y, Dally WJ. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.01887. 2017 Dec 5.\n\n[3] Bernstein J, Zhao J, Azizzadenesheli K, Anandkumar A. signSGD with majority vote is communication efficient and fault-tolerant. arXiv. 2018 Oct 11.\n\n[4] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li. TernGrad: Ternary gradients to reduce communication in distributed deep learning. In Proc. Advances in Neural Information Processing Systems (NIPS), 2017.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJxLkbwatH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "In this paper, the authors propose a new gradient compression method, which is called nonuniform quantization. The algorithm is a reasonable variant of SGD with uniform quantization. The paper is well written. The experiments show good performance.\n\nHowever, there are several weakness in this paper:\n\n1. In this paper, a very important reference and baseline is missing, which is call error-feedback SGD [1]. Although the title of [1] focuses on SignSGD, it provides a general algorithm for arbitrary compressor with a error/variance bound similar to Theorem 2 in this paper, no matter the compressor is unbiased or not. Since [1] provides the SOTA results for quantized SGD, the proposed algorithm should be compared to it in the experiments.\n\n2. This paper claims to have strong theoretical guarantees. However, the theoretical analysis only works for convex functions. Note that the theoretical analysis in [1] also works for non-convex functions.\n\n3. Regardless of the convergence guarantees (which is weak considering the existing theorems in [1]). the proposed algorithm, NUQSGD, does not show improvement on the convergence, compared to the baseline QSGDinf.\n\n4. In Figure 3, the experiments only show loss vs. # of iterations, which does not show the actual training time. In Figure 4, training time is only shown for NUQSGD, which ignores the other baselines including QSGD and QSGDinf. What I really what to see is training loss (or testing accuracy) vs. training time (or communication overhead, such as number of bits), so that we can evaluate the trade-off between communication overhead and the convergence, compared to the baselines.\n\n\n\nMinor issue (I hope the authors can consider the following suggestions in a revised version. However, since the issue is minor, it doesn't affect the score):\n\n!. In Definition 1, in some cases $s$ is c constant integer, and in some other case $s$ become a function, which is very confusing and not friendly to the readers. I also hope the authors can highlight the definition of $r$ and $p$, which are essential for understanding the nonuniform quantization mechanism. \n\n\n\n\n--------------\nReference\n\n[1] Karimireddy, Sai Praneeth et al. “Error Feedback Fixes SignSGD and other Gradient Compression Schemes.” ICML (2019).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkxbah715H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Brief summary of the paper:\nThis paper studies data-parallel SGD that K processors work together to minimize an objective function. Each processor computes a stochastic gradient and broadcasts to other peers. In this distributed system, there is a trade-off between the *communication cost* from sharing the stochastic gradient and the *variance* from gradient quantization. This paper is a follow-up of Alistarh et al. (2017). It proposes a non-uniform (logarithmic) quantization scheme (NUQSGD). This paper provides theoretical analysis of the variance and communication cost of NUQSGD. Then the paper analyzes the convergence rate of NUQSGD for convex and smooth objective function. At the end, this paper empirically evaluates NUQSGD for image classification problem. \n\n\nOriginality and significance:\nThis paper follows up on the parallel SGD framework proposed by Alistarh et al. (2017), where the authors proposed QSGD using a uniform quantization. This paper proposes NUQSGD using a non-uniform quantization method. The quantization of the stochastic gradient amplifies the stochastic variance, which influences the rate of convergence of SGD. Thus, on one hand, it is important to design a quantization method to improve the variance, for the sake of convergence rate. On the other hand, it is also important to decrease the communication cost. NUQSGD does not provide significant improvements in terms of the variance and communication cost. \n\nTheorem 2 and Theorem 3: QSGD has a variance of min {d/s^2, \\sqrt{d}/s} and NUQSGD has a variance of min{O(d/2^{-2s}), O(\\sqrt{d/2^{-2s}})}. QSGD has communication cost of \\tilde O(s(s+\\sqrt{d})) and NUQSGD has communication cost of \\tilde O(2^{2s}\\sqrt{d} ). Compared to QSGD, we can see that NUQSGD improves the dependence on s for the variance term, but it has a worse (exponential) dependence on s for the communication cost. Usually s is a small number and it serves as a hyper-parameter to be tuned. We would expect NUQSGD to improve the dependence on the dimension d, which is more significant. However, NUQSGD has the same dependence on d as QSGD in terms of both variance and communication cost. \n\nExperiments: Figure 3 compares NUQSGD with other parallel SGD algorithms and vanilla SGD. Figure 3 shows how fast the training loss decreases with respect to iterations. It would be great to add learning curves with the ‘time’ being the x-axis as well. Also, I would suggest the authors to record the time needed to proceed one iteration for each parallel algorithm to compare the communication cost. \n\nQuality and clarity:\nThis paper is well-written. \n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a communication-efficient data-parallel SGD with quantization. The method bridges the gap between theory and practice. The QSGD method has theoretical guarantees while QSGDinf doesn't, but the latter gives better result. This paper proves stronger results for QSGD using a different quantization scheme which matches the performance of QSGDinf.

The reviewers find issues with the approach and have pointed some of them out. During the discussion period, we did discuss if reviewers would like to raise their scores. Unfortunately, they still have unresolved issues (see R1's comment). 
R1 made another comment recently that they were unable to add to their review:
"The proposed algorithm and the theoretical analysis does not include momentum. However, in the experiments, it is clearly stated that momentum (with a factor of 0.9) is used. Thus, it is unclear whether the experiments really validate the theoretical guarantees. And, it is also unclear how momentum is added for both NUQSGD and EF-SGD, since momentum is not mentioned in Algorithm 1 in this paper, or the paper of QSGD, or the paper of EF-SignSGD. (There is a version of SignSGD with momentum *without* error feedback, called SIGNUM)."

With the current score, the paper does not make the cut for ICLR, but I encourage the authors to revise the paper based on reviewers' feedback. For now, I recommend to reject this paper.
Decision: Reject