Understanding Top-k Sparsification in Distributed Deep Learning
Authors: Shaohuai Shi
Xiaowen Chu
Ka Chun Cheung
Simon See
Venue:  (2020)
Keywords: Distributed Deep Learning
SGD
Gradient Sparsification
Communication-efficient SGD
Top-k

Abstract: Distributed stochastic gradient descent (SGD) algorithms are widely deployed in training large-scale deep learning models, while the communication overhead among workers becomes the new system bottleneck. Recently proposed gradient sparsification techniques, especially Top-$k$ sparsification with error compensation (TopK-SGD), can significantly reduce the communication traffic without obvious impact on the model accuracy. Some theoretical studies have been carried out to analyze the convergence property of TopK-SGD. However, existing studies do not dive into the details of Top-$k$ operator in gradient sparsification and use relaxed bounds (e.g., exact bound of Random-$k$) for analysis; hence the derived results cannot well describe the real convergence performance of TopK-SGD. To this end, we first study the gradient distributions of TopK-SGD during training process through extensive experiments. We then theoretically derive a tighter bound for the Top-$k$ operator. Finally, we exploit the property of gradient distribution to propose an approximate top-$k$ selection algorithm, which is computing-efficient for GPUs, to improve the scaling efficiency of TopK-SGD by significantly reducing the computing overhead.

Under review as a conference paper at ICLR 2020
UNDERSTANDING TOP-K SPARSIFICATION IN DIS- TRIBUTED DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Distributed stochastic gradient descent (SGD) algorithms are widely deployed in training large-scale deep learning models, while the communication overhead among workers becomes the new system bottleneck. Recently proposed gradient spursification techniques, especially Top-k sparsification with error compensation (TopK-SGD), can significantly reduce the communication traffic without obvious impact on the model accuracy. Some theoretical studies have been carried out analyze the convergence property of TopK-SGD, However, existing studies do not dive into the details of Top-k operator in gradient sparsification and use relaxed bounds (e.g., exact bound of Random-k) for analysis; hence the derived results cannot well describe the real convergence performance of TopK-SGD. To this end, first study the gradient distributions of TopK-SGD during training pro- cess through extensive experiments. We then theoretically derive a tighter bound for the Top-k operator. Finally, we exploit the property of gradient distribution propose an approximate top-k selection algorithm, which is computing-effice for GPUs, to improve the scaling efficiency of TopK-SGD by significantly reduc- ing the computing overhead.
INTRODUCTION
Training large-scale deep neural networks (DNNs) generally exploits distributed synchronous stochastic gradient descent (SGD) optimization algorithms to reduce the overall training time. Let P be the number of workers distributed setting, and æ E IRd denotes the model parameters with d dimensions. At the (-th iteration, distributed synchronous SGD updates the model parameters by
Ø++1 = P
L.
(1)
where of E Rd the stochastic gradient with its locally selected data for the loss function f2 Rd - and 7/ is the learning rate. The aggregation of d-dimension gradients from P workers requires a communication complexity of (d)) in terms of communication traffics which generally limits the system scalability. Gradient sparsification (Strom) 2015 Dryden al., 2016 Aji & Heafield 2017 Chen et al., 2018 Lin et al.) 2018) is a promising technique for distributed SGD, which can significanlly reduce the communication traffic while reserving the model convergence. In gradient sparsification, compressor Comp& is applied on each worker to locally select k. k < d, gradients for aggregation and Comp: (Top,, Randæ (Stich al. 2018). Compp zeros out (d - k) elements of ge and keeps & elements unchanged. The zeroed-out d - k elements are stored as residual Ee for the next iteration. Formally, the model parameters are updated by
E Rd
P
D1+1 = Iz - 17 p
1
Σ
Comps (g + <)) and E. = ge + - -Compp (g) + c.),
(2)
where Ee E _d and eg In theory, distributed SGD with gradient sparsification (c.g., Top. Rand, and any other k-contraction operators) with error compensation has been proved to have the
'The ring- AllReduce collective can achieve the bandwidth optimal performance that is not related to the number of workers, but there exist latency that will increase with increased number of workers.

---

Under review as a conference paper at ICLR 2020
same order of convergence rate vanilla SGD for both convex and non-convex problems if the number iterations is large (Wangni et al. 2018; Stich et al. 2018 Alistarh et al. 2018 Jiang & Agrawal 2018 Karimireddy et al., 2019; Tang et al. 2019: Zheng al. 2019). The convergence rates are derived with a key contraction property of the sparsification operator Comps (Top,, or 2018), that is
Randę) (Stich et al. 2018 Alistarh et al.
(3) where Eg is the expectation taking on the compressor and || is the fz-norm. For any æ E RR Top;(2)) E [dd selects the top largest elements (in terms of the absolute value) of with corresponding indices and sets other d - k elements zeros; while Randy, (x) E R randomly (in uniform distribution) selects k elements from x with corresponding indices and other - elements zeros. It is obvious that
Rcll= Comps (x))) (1 (1--k/dl k/d)[|=]l Va E RR..
(4) Existing studies use the same error estimate for both Top,, and Rand, in distributed SGD by ex- ploiting the properties of (4), which cannot differentiate the convergence behavior of operators. In practice, however, TopK-SGD has much faster convergence speed (in term of iterations) than SGD with Rand, (RandK-SGD) empirically shown in (Stich et al. 2018). We also compare the convergence performance between TopK- -SD and RandK- -GD on 16-worker distributed set- ting with three popular convolutional neural networks (VGG-16 (Simonyan Zisserman [014), ResNet-20 and ResNet-50 (He et al.) 2016)). Our results are shown in Fig. []] We observe that TopK-SGD achieves very similar performance the original distributed SGD (hense-SGDD, while RandK-SGD has much slower convergence than TopK-SGD, RandK-SGD even cannot converge on ImageNet. Therefore, though existing studies show that TopK-SGD and RandK-SGi have the same convergence bound, their theoretical results cannot explain the performance gap between TopK-SGD and RandK-SGD Even some work (Karimireddy et al., 2019. Tang et al., 2019) exploits g < 1 to replace k/d in 3 they also fail to identify exact ò to distinguish Top; and Randg-
a Top, (==) S | - Rand, (z>)] and En [| Randy (2) [ (1 - k/ 1/
70
80-
80
60
60-
60
50
Dense-SGD Topk-5GD
40
Danse-SGD
TGD
40
TopK-SGD
Dense-SGD
vol
20
RandK-5GD
20
RDD
20
RandK-
56D
10
20
40
60
80
100
120
20
40
60
80
100
120
0
10
20
30
40
50
60
70
epechs
epochs
(a) VGG-16 on CIFARIO
(b) ResNet-20 on CIFARIO
(c) ResNet-50 on ImageNett
Figure Convergence comparison between original distributed SGD (Dense-SGD), Top, spar- sification (TopK-SGD) and Rand, sparsification (RandK-SGi -SDD at 16 distributed workers the CIFAR1O (Krizhevsky et al. 2010) and ImageNet (Deng et al. 2009) data sets. = 0.001d for TopK-SGD and RandK-SGD.
In this paper, dive into the details of the Top, operator in distributed SGD when training DNNs and provide a tighter bound than inequality (3) to explain the good convergence performance of TopK-SGD. The observation of gradients with Top; sparsification further enables propose new computational--ffiiies selection algorithm for gradient which preserves the convergence prop- erty. Our contributions are summarized as follows.
Contributions. (1) We empirically study the details of local stochastic gradients and observe that the coordinates of gradient follow bell shaped distributions through extensive experiments. (2) The bell shaped distribution enables us to intuitively explain that Top, should have much tighter bound than Rand,, and we exploit the distribution property to formulate how Top, outperforms Randg- (3) We design and implement an approximate top-k selection algorithm?] which much more efficient than existing top-k selection algorithms on GPUs. As compared with the existing sampling-basse based approximate top-k selection algorithm, we improve the scaling efficiency by 12-50% on our 16-GPU cluster.
Our system implementation will be made open-source after the review process.
2

---

Under review as a conference paper at ICLR 2020
2 RELATED WORK
Gradient Quantization. In distributed training of neural networks, the communicated gradients can be quantized to low-bit precision (e.g.. 16-bit (Micikevicius et al. 2018 Jia et al. 2018), 3-bit
(Wen et al. 2017). 2.8-bit (Alistarh et al. 2017 Karimireddy et al. 2019) and even 1-bit (Seide al., 2014 Strom 2015)) while preserving nearly consistent convergence performance with the
full precision (32-bit) counterpart. Recently general frameworks of gradient quantization with error compensation are proposed to generalize the theoretical results of low-bit communication (Wu et al.) 2018 Diang & Agrawal 2018 Karimireddy et al.) 2019 Tang et al. 2019: Haddadpour et al.. 2019). However, the quantization method can only reduce the communication traffic in 32x (i.c., 1-bit vs. 32-bit), and it could not be enough for large-scale models or low-bandwidth network connections.
Gradient Sparsification, Compared to gradient quantization, gradient sparsification is a much more promising communication traffic reduction technique it can sparsify up to three orders of magnitude gradients be zero with little impact on the model convergence (Strom 2015 Dryden 2016 Aji & Heafield 2017] Chen al. 2018 Lin al. 2018 Shi al. 2019ap. Due al. to the much success of gradient sparsification (e.g.. Top-k sparsification) in significantly reducing
the communication traffic (Lin et al.) 2018 Sun al. 2019). much recent work tries to build
thcoretical guarantees for SGD with gradient specification Wangni et al. [0188) Stich et al. 20188] Alistarh et al. 2018 Jiang& & Agrawal 2018 Shi et al., | Karimireddy al. [019 Tang al. 2019). These theoretical frameworks try to generalize the sparsification operator with the bound of inequality (3) to derive the convergence results for SGD with gradient sparsification. However, the existing analysis fails to go insight into the details of gradient sparsification of Top,, which could have better convergence than other compression operators (e.g., Rands).
Gradient Distribution Glorot & Bengio (010) study the distribution of activation values of DNNs and also their corresponding gradients. They empirically showed that back-propagated gra- dients have Gaussian-lik, distributions, which helps understand the difficulty of training deep neural networks. A similar plot is shown in (Micikevicius et al.) 2018), where the distribution of gradients helps analyze if the 16-bit representation of gradients would be overflow underflow. These work has demonstrated that the gradients during training are likely located near zeros. We extend the similar studies the gradient distribution for TopK-SGD.
STUDY ON STOCHASTIC GRADIENTS
3.1 GRADIENT DISTRIBUTION
In previous gradient sparsification studies Strom 2015 Dryden et al. 2016 Aji & Heafield 2017] Chen et al. 2018 Lin et al. 2018), the basic rule of sparsification is to select "significant" elements of the gradients because they contribute more to the updates. The Top, operator selects the exact local top-k elements of gradients so that it achieves nearly consistent convergence performance with would like to understand what is the difference between "significant" elements of the gradients and randomly selected ones. We conduct extensive experiments to study the gradient distributions on three areas of deep learning applications, including image classification, language modeling, and speech recogmition. The selected models are: 1) Feed-forward Neural Networks (FNNs). An FNN with three hidden fully connected layers (FNN-3) on the MNIST (LeCun) 1998) data set. 2) Convolutional Neural Networks (CNNs). LcNet-5 (LeCun et al. 2015) on MNIST, ResNett-0 (He et al. 2016) and VGG-16 (Simonyan & Zisserman 2014) on CIFARIO (Krizhevsky et al., 2010). And 3) Recurrent Neural Networks (RNNs). Long Short Term Memory networks (LSTMs) on the Penn Treebank (PTB) (Mareus et al. 1993) and the AN4 (Acero) 1990) data sets. For PTB, we adopt 2-layer LSTM model (LSTM-PTB) with 1500 hidden units per layer, and for AN4, we use a 5-layer LSTM model (LSTM-AN4) with 800 hidden units per layer.
Dense-SGD. Therefore,
The details of the experimental settings are shown in Table I As the compression operator is ap- plied on the gradients, we first measure the distributions of the gradient's ' elements (histograms) on Dense-SGD. The results demonstrate the similar shapes as (Glorot & Bengio 2010), while ours covers various applications (refer to Appendix A.2 Our interest is on TopK-SGD to check
"hhe distribution we discussed in this paper is over coordinates particular vector (e.g., activation out-
puts, full gradients).
3

---

Under review as a conference paper at ICLR 2020
Table I: Experimental settings. All models are trained by SGD with 0.9 momentum. "BS" is the
mini-batch size at each worker. "LR" is the initial learning rate which is decayed during training.
The hyper-parameters are set to cover various weight initialization methods, activation functtions, batch sizes and learning rates with proper convergence performance.
Type
Model
# Params
Weight Init.
Activation
BS
LR
Data Set
FNN
FNN-3
199,210
Xavier
ReLU
128
0.01
MNIST
LeNet-5
61,706
Xavier
ReLU
128
0.01
CNN
ResNet-20
269,722
Xavier, Kaiming
ReLU
32
0.1
CIFARIO
VGG-16
14,728,266
Kaiming
ReLU
128
0.1
LSTM-PTB
66,034,000
Uniform
Tanh
20
22
PTB
RNN
LST
27,569,568
Xavier
Tanh
4
0.0002
AN4
gradients distributions perverse the same properties as Dense-SGD, During the training process of TopK-SGD (k 0.001d for d-dimension model), we measure the histograms of local gradients accumulated with the residuals (i.e., up ge + E(). The histograms of u with different on different models are shown Fig. 2 where we only show the gradients from the first worker as different workers have very close gradient distributions. The corresponding cumulative distributions are presented in Appendix A.I is seen that different models have different shapes on the accumu-
04
5.2
0. 02.02-00 0.--- 00--0.55-..22 30-0.22
0.25 0.75
-2.0
-15 -1.0
-0.5
0. 0.5 10
-15 -1.0
-5.5 0.0
1.0
gradient value
gracient value
gradentvalle
1e-1
(a) FFN-3
(b) LeNet-5
(c) ResNet-20
1000
Iee 300
1.0
Ite 800
1020
1.6
Ber-1000
ken 000
120
0.8
1420
1220
12-
Ben-7700
Fer 1002
0.6
Iur- 2820
ken-2000
0.6
1-
02
15
gradent
16-2
value
16-3
gradlent
(d) VGG-16
(c) LSTM-PTBB
(f)
LSTM-AN4
Figure 2: The histograms of ut of TopK-SGD. For each model, the gradient histograms are plotted every 200 iterations from iteration 200 to 1600 (other iterations have similar shapes).
lated gradients, but one common feature is that most coordinates of u, are close to zero. Compared to the full gradient SGD (Appendix A.2)) TopK-SGID shows wider distributions, which could be mainly caused by residual accumulation. When selecting top-k largest values (in terms of absolute values) from u, the selected values should be located the left and right sides on the histograms. Therefore, performing Top, on should generate a vector whose by-norm is very close to that of
ur that is Top (u,) ||2 & ||uul|? 2 The intuitive result inspires us to formulate how much close of Top,, (u+) |2 to |uall Specifically, we would like to derive a variable y S (1 k/d) such that
[u, Top, (u.) < 7/|,,112 holds.
3.2 THEORETICAL ANALYSIS AND RESULTS
We investigate the Top, operator on up 9e + + (for ease of presentation, we use to denote u(). Error estimation of Top.. Let ग denote sorted vector of |u| |||] in a descending order. That ()) 2 (i+1)) 2 for 1,2, .... d 1, where (T)) is the 1th element of π E Rd. Then we have
w Top (u) 12
|/u Top, (w) (1)l///11l/
| Top, (2)
Σi=4t T.
(5)
u
| uIB
d Σ
4

---

Under review as a conference paper at ICLR 2020
where ä u/ [u/l|u////0 Assume that (()) follows bell shaped distribution (e.g.. Fig. a()), and X²
a decreasing function w.r.t. i as shown in Fig. b). In order to evaluate Eq. ( It is essential empinially prove that
to calculate the area under the curve of x². As illustrated in Fig. 2 one π is convex and it is always less than the reference line (y = -i/d + 1) if u follows bell shaped
distributions. Considering the areas of A1, A2, A3; and A4 shown in Fig. 3c), have
Eizk+1
A1 4 As
A + A4
(6)
Σ (1)
A1
+ A2 + A
Due to the space limit, the proof of the inequality is put in Appendix A.4 Then we have
A
+
Area of MDB Area of EBD
[1 k
A + A2 + A3 <
=
(7)
A2+
Area of OCB
Area of OAB
where the second equality can be obtained from the similarity of triangle AMDB ~ ACOB and AEDB AAOB, ie..
Area of MDB
MD
DB
ED
Area of EBD
(8)
Area of OCB
CO OB
AO
Area of OAB
Putting altogether, we have
1u -
|u=Top;(u)) (u)p /|/||| $ (1 (1-k)) k/d)) =:7
(9)
and eventually
1| - (u) < >|/u|| < (1 - k/d) ||ee|2
(10)
where 7 = (1 k/d)2. The last inequality always true as k ddl S
Our results can be
140
0.5
1.29
rermalaee veluu
1.00
0.5.
0.75
0.4
0.2
-200-0075-- 30-0225
030
150
20000 40000 60000 80600 100000
20000 40000 cobco n0000 100000
(a) Bell shaped distribution
(b) Sorted shape
(c) Illustrated areas
Figure The shape of (e) with different i with d 100, 000 and a 1.
summarized as the following theorem. Theorem 1. Assume that IRd follows a bell shaped distribution and π² is convex and less than the line = -i/d + 1, then we have
1ue - Top (2)) < (1- (1=k///"\/u
(11)
Furthermore, can be rearranged into the form that
||u (w)) < 111-6) 6) |/ul12 where 5 = (2kd k32/
(12)
Convergence Bound of TopK-SGD We use the same assumptions on the objective function f Rd + IR as (Karimireddy al. 2019). The assumptions are: 1) f is L-smooth and 2) has moment bound (i.e., Elgl = Vf(x) and | < G2 for some G O, where g is a stochastic gradient and æ is the model parameter). Therefore, can directly use the the bound formulation of convergence rate with 5 from (Karimireddy et al.) 2019) in Remark 4.
Theorem 2. If we set t/ vI4I for running TopK-S -SD and under the assumptions of J, we have
4(f(xo) fr) + LG2
min E| EEIT
(13)
2/T +1
(T +1)
where 8 is the optimal solution.
5

---

Under review as a conference paper at ICLR 2020
The theorem indicates that after T 2 0 iterations, the first term of the right-hand side of inequality [13) will dominate the bound that the convergence rate becomes O(1 O(1/V7 /V) which matches the rate of vanilla SGD. Note that our derived bound of 5 = (2kd //2 is much tighter
than k/d in previous studies (Stich et al., 2018; Alistarh et al., 2018, Jiang & Agrawal 2018 Shi
et al. 2019b Karimireddy et al. 2019). Let c d/k denote the compression ratio of gradients.
Previous results (ō I/c) indicate that RandK-SGD or TopK-SGD should run after T 2 O(c²) iterations to make it catch up the convergence rate of Dense SGD. Using inequality (TO) for TopK- SGD, just requires 2 (cd²/ (2c- iterations to have the full gradient convergence rate. The result gives the explanation to why TopK-SGD can easily achieve nearly consistent convergence performance to Dense-SGD, while RandK-SGD could not (as shown in Fig. D.
3.3 GAUSSIANE: AN APPROXIMATE TOP; OPERATOR
Though TopK-SGD has a good convergence property with significantly reduced communication size in distributed SGD, the exact top-k selection is not friendly to many-core processors like GPUs (Shanbhag et al., 2018). Inefficient Top, could make the overall wall-clock time worse. For exam- ple, training a ResNet-50 (He et al.) 2016) model on ImageNet (Deng et al. 2009) on an Nvidia Tesla V100 GPU with a mini-batch size of 128 requires around 0.46 seconds per iteration When we distribute the training to 16 Tesla V100 GPUs connected with 10 Gbps Ethernet (10GbH), the communication time of full gradients (d = 25, 557, 032) is around 0.2 seconds. However, the Top, operator with k 0.001d on ResNet-50 with the Tesla V100 GPU consumes 0.4 seconds. The 0.2- second communication overhead is saved, but it introduces another 0.4 seconds, which makes the training efficiency even worse. In DGC-SGD (Lin et al. 2018), the authors proposed to sample only 0.1% to 1% of the gradients to estimate the threshold hierarchically, which requires to invoke top-k selection twice on the subsets of the original vector. For ease of reference, we DGC; denote the hierarchical sampling method in selecting the largest top-k gradients. In RedSyne-SGD (Fang) al. 2019), the authors proposed trimmed top-k selection algorithm (Trimmedg) gradients for CNNs by heuristically searching the threshold with moving the ratio between the max- imum value and the average value. However, Trimmed; could use a threshold that is much smaller than the exact top-k threshold so that the number of selected gradients is much higher than k.
select top
Algorithm 1 Gaussian;
Input: Stochastic gradients with residuals u.
computation time @
Top-k
Input: & and dimension d
DGC-k
I: Initialize
a zero vector with d dimensions;
4
Gausslan-k
μ.o mean and std of vector ui:
3
3: p= = - k/d;
4: Uhres = upf(u,. 11, o);
2
5: for = 0 + 3 do
6: masks |u/| > thres;
1
7: estimatedy= # of True values in masks;
8: if eestimateds < 2k/3 then
2
9: thres = 1.5++ thres;
of parameters
1e6
10: else if estimated, > 4k/3 then
11: thres = 1.5 thres;
12: else
Figure 4: The GPU computation time (lower is better) of Top,, DGC; and Gaussian;- We use the PyTorch tensor API, "tensor.topk"", for the Top, operator.
13:
break:
14:
à imaasss] = uf maakks];
15:
Return i;;
We propose an approximate Top, operator named Gaussiang by exploiting the Gaussian-like dis- tribution property of gradients. The key ideas of Gaussiang are: 1) We regard the d-dimensional gradients (i.e., u&) at each iteration as normal distribution with the mean (μ1) and standard vari- ance (ar) which can be directly calculated in an (dd) complexity and the caleulations are friendly to GPUs. 2) We estimate the threshold by exploiting the percent point function (ppf) of uf with three parameters: p
k/dd, i and a. 3) As the distribution is not exactly normal, the ppf estimation could result in a threshold that could be slightly smaller or larger than the true threshold. We move
*The model is trained with the 32-hit floating point without using Tensor Cores of the Tesla V100 GPU.

---

Under review as a conference paper at ICLR 2020
to the estimated threshold to the left right side several times such that have very close top-k largest absolute values. The algorithm of Gaussian; is shown in Algorithm T
4 EXPERIMENTS
As we mainly focus on gradient sparsification, we use the fp32 operations instead of exploiting lower precision for training models. The related software libraries are CUDA-10.1, cuDNN-7.5.0 NCCL-223.7, PyTorch-I.1.O, OpenMPI-4.0.1, and Horovod-0.16 16.4 (Sergeev & Balso 2018), which are kept the same for all evaluated algorithms.
4.1 NUMERICAL RESULTS OF THE TOP; OPERATOR
To validate the bound of inequality 10). we randomly (in Gaussian distribution) generate a 100, 000 dimension vector and compare the exact value of u ( (1)///// and 1 k/d with ours derived (1 - k/d)². We also compare the three bounds in the real-world model training process. The results are shown in Fig. side of the exact value, which indicates the derived bounds hold. With increased k, ours becomes better and better than the previous result. However, the exact value is still much lower than ours. The reason is that our bound is derived by the reference line (Fig. 3b)) but not the original function. Therefore, if the shape of (()) can be exactly formulated, one can derive tighter bound for the Top;
is seen that both ours and the previous result are in the upper
operator than (1 k/d)² and we will leave this as our future work.
exact value presious stulles
TWNN Noarg
0.0
0.0
0.8
0.0
0.c.
ours
0.6
0.6
0.6
02-
6.-
0.0
0.0
0.0
2.00
0.0
0.1
0.2
0.3
0.4
0.5
0.2
0.1
0.2
03
0.4
0.5
9.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.4
0.5
(a) Random
(b) FNN-3
(c) CNN (ResNet-20)
(d) RNN (LSTM-PTB) -TB)
Figure 5: The comparison of bounds with a range of
4.2 GPU COMPUTATION EFFICIENCY OF SPARSIFICATION
To evaluate the computing efficiency of different top-k selection algorithms on GPUs, we conduct experiments on an Nvidia Tesla V100 GPU with d ranging from 20 million to 400 million and k 0.001d. The GPU computation speed comparison between Top DGC, and Gaussian, operators shown in Fig. For DGC&, we use 1 1% as suggested in (Lin et al. 2018) to estimate the threshold. Note that tensor operations (e.g., top-k selection, mean and std calculations etc.) are from Py PyTorch's 's tensor API The experimental results show that the Top; operator becomes very slow with large number of parameters, while Gaussiang only generates slight overheads. DGC, also becomes inefficient if d is large. It is crucial for the end-to-ent training to have computing-effichee efficient operator on GPUs such that the extra computation overhead would not limit the system scalability.
4.3 CONVERGENCE PERFORMANCE OF GAUSSIANK-SCHI
To demonstrate the convergence performance of Gaussiank-SGII we run 120 epochs on CIFARIO and 70 epochs on ImageNet with 16 workers. On CIFARIO, the hyper-paramen parameters are listed in Table I and on ImageNet, we use a mini-batch size of 32 per GPU and a initial learning rate 0.01. The top-1 validation accuracy of the evaluated models is shown in Fig. 6 Note that for each model, we use the same hyper-parameter for the three SGD algorithms. We can see that our GaussianK- SGD has nearly consistent validation accuracy with TopK-SGD, which indicates that our proposed Gaussian; operator can select close elements with Top;- The gradient distributions in GaussianK- SGD are similar to TopK-SGD (Appendix A.2). In the evaluated three models, GaussianK-Se TopK-SGD have slight accuracy loss (around 0.6%-0.8% compared to Dense-SGI. As suggested in (Lin et al. 2018). the small residuals could have staleness compared to the current gradients
and
html

---

runs much Under review as a conference paper at ICLR 2020
so that it could cause the slight accuracy loss. Some optimization tricks in momentum correction would address this problem.
Lin et al.
2018 like
70
80-
60
VS5 scourecy
50
60-
40-
Dense-SGD
20
30
TopK-SGD
Topk-GGD
Top
GaUsstank-SGD
Go05siank:SG0
Gaussiank-Son
20
40
60
80
100
120
40
60
80
100
120
10
20
30
40
5o
60
70
epochs
epachs
spachs
(a) VGG- 16 on CIFARIO
(b) ResNet-20 on CIFAR1O
(c) ResNet-50 on ImageNet
Figure 6: The convergence performance (top-1 validation accuracy) of distributed SGD with GaussianK-SCO using 0.001d compared TopK-SGD and Dense-SGD on workers.
4.4 END-TO-END TRAINING SCALING EFFICIENCY OF GAUSSIANK-SGD.
the ImageNet (Deng et al. 2009) data set with four popular models (AlexNet (Krizhevsky et al. 2012). VGG- 16 (Simonyan & Zisser- man 2014). ResNet-50 (He al. 2016) and Inception- V4 (Szegedy et al. 2017))
We evaluate the average iteration time of GaussianK-SGii
16-GPU cluster compared to Dense-SGD with full gradients, (opK-SGDD with the original top- selection, DGC-SGD (Lin et al. 2018) with hierarchical sampling and RedSync-SGD (Fang al. (019) with trimmed top-k selection. The cluster has four nodes connected with 10GbE, and each node contains four Nvidia Tesla V100 GPUs (the PCIe version with 32GB memory). k 0.001d for all the sparsi- fied algorithms. The results are shown in Table which shows that TopK-SGD and RedSync-SCG SGDD are even slower than Dense-SGD on the 16-GPU cluster, while our GaussianK faster than other algorithms. Specifically, GaussianK-Soe is 1.19x -2.33x faster than Dense-SGD, 1.36x -3.63 faster than TopK-SGD, and 1.11x-1.514 faster than DGC-SGD, respectively. Even on the VGG-16 model, which has several large-size fully connected layers, GaussianK-SoC can achieve 85.5% scaling efficiency on the 16-GPU cluster with low now-bandwidth Ethernet.
Table 2: Wall-clock time of end-to-end training with ImageNet on 16 Tesla V100 GPUs. The batch size for each GPU is 128, and the input image resolution is 224x224. Scaling efficiency is defined The, where T1 the throughput of single GPU training, and Tio is the overall system throughput by 167,
of distributed training on 16 GPUs with weak-scaling.
Iteration Time (s)
Scaling Efficiency (%)
Model
Dense
TopK
DGC RedSync GaussianK
Dense
TopK
DGC
RedSync GaussianK
AlexNet
0.571
0.891
0.369
7.203
0.245
14.1
9.0
21.8
1.11
32.8
VGG-16
2.068
3.010
1.540
14.670
1.311
54.2
37.2
72.8
7.6
85.5
ResNet-50
0.699
0.810
0.655
2.588
0.586
65.8
56.8
70.2
17.9
78.5
Inception- V4
1.022
1.268
0.916
3.953
0.787
67.5
54.4
75.3
17.4
87.7
5 CONCLUSION
In this paper, we first identified that existing theoretical results fail to explain the convergence per- formance of distributed SGD algorithms with Top-k gradient sparsification (TopK-SGD). Then empirically studied gradient distributions during training with TopK-SGD through extensive experi- ments, and observe that the elements of stochastic gradients are mostly located near zero (Gaussian- like distribution). The observation enables us to build tighter bound for the Top; operator based on the empirical assumption of bell shaped distributions of gradients, which makes the convergence property of TopK-SGD explainable. According to the distribution of gradients, we propose ap- proximate top-k selection algorithm named Gaussiang which is much efficient than the existing top-k selection algorithms GPUs. We finally conduct extensive experiments verify our derived bound for the Top, operator and the convergence performance of distributed SGD with Gaussian, (GaussianK-SGri) SGD). In terms of the scaling efficiency, GaussianK-SGD achieves up 2.33 3 and 1.51x x faster training speed than full gradient SGD, TopK-SGD and DGC-SGD on a 16-GPU cluster connected with 10 Gbps Ethernet, respectively.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alejandro Acero. Acoustical and environmental robustness in automatic speech recognition. In Proc. of ICASSP, 1990.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proceedings of the 2017 Conference Empirical Methods in Natural Language Processing, pp- 440 445, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication--fficin SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, pp. 5977-5987, 2018.
Chia-Yu Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, and Kailash Gopalakr- ishnan. AdaComp: Adaptive residual gradient compression for data- mata-parallel distributed training. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, pp. 248-255. IEEF, 2009.
Nikoli Dryden, Tim Moon, Sam Ade Jacobs, and Brian Van Essen. Communication quantization for data-paralle, training of deep neural networks. In 2016 2nd Workshop on Machine Learning in HPC Environments (MLHPC), pp. 1-8. IEEE, 2016.
Jiarui Fang, Haohuan Fu, Guangwen Yang, and Cho-Jui Hsich. RedSync: Reducing synchronization bandwidth for distributed deep learning training system. Journal of Parallel and Distributed Computing, 133:30-39, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding up distributed SGD for non-convex optimization. In International Conference on Machine Learning, pp. 2545-2554, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Xianyan Jia, Shutao Song, Wei He, Yangzihao Wang, Haidong Rong. Feihu Zhou, Liqiang Xie, Zhenyu Guo, Yuanzhou Yang, Liwei Yu, et al. Highly scalable deep learning training system with mixed-precision: Training ImageNet in four minutes. arXiv preprint arXiv:1807.11205. 2018.
2018.
Peng Jiang and Gagan Agrawal. linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances in Neural Information Processing Systems, pp. 2530- 2541, 2018.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. International Conference on Machine Learning, pp. 3252-3261, 2019.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 10 (canadian institute for advanced search). URL http://wwww.cs.oorootto edu/kriz/cifar ott.eei/t.oooo.onccuciiiiiiiinre html, 2010.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.

---

Under review as a conference paper at ICLR 2020
Yann LeCun. The mnist database of handwritten digits. http://yam.lecun.cmm//zai 1998.
Yann LeCun et al. Lenet-5, convolutional neural networks. URL: 20:5, 2015.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Reprexentations, 2018.
Mitchell P Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building large annotated corpus of English: The Penn Treebank. Computational linguistics, 19(2):313330, 1993.
Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory
Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, al. Mixed precision training. International Conference on Learning Representations, 2018.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in Ten- sorFlow. arXiv preprini arXiv: 1802.0099, 2018.
Anil Shanbhag, Holger Pirk, and Samuel Madden. Efficient top-k query processing massively parallel hardware. In Proceedings of the 2018 International Conference on Management of Data, pp. 1557-1570. ACM, 2018.
Shaohuai Shi, Qiang Wang, Kaiyong Zhao, Zhenheng Tang, Yuxin Wang, Xiang Huang, and Xi- aowen Chu. A distributed synchronous SGD algorithm with global Top-k sparsification for low bandwidth networks. In The 39th IEEE International Conference on Distributed Computing Sys- tems (ICDCS 2019), pp. 2238-2247, 2019a.
Shaohuai Shi, Kaiyong Zhao, Qiang Wang, Zhenheng Tang, and Xiaowen Chu. A convergence analysis of distributed SGD with communication-efficii gradient sparsification. In Proceed- ings of the Enventy-Eightt International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 3411-3417, 2019b.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogmition. arXiv preprint 1rXiv:1409.1556, 2014.
Sebastian U Stich, Jean- SaantBapiitte Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In 2018. Advances in Neural Information Processing Systems, pp. 4452-4463, 2018.
Nikko Strom. Scalable distributed DNN training using commodity GPU cloud computing. In Six- teenth Annual Conference of the International Speech Communication Association, 2015.
Peng Sun, Wansen Feng, Ruobing Han, Shengen Yan, and Yonggang Wen. Optimizing network performance for distributed DNN training GPU clusters: ImageNet/AlexNet training in 1.5 minutes. arXiv preprint arXiv:1902.06855. 2019.
Christian Szegedy, Sergey loffe, Vincent Vanhoucke, and Alexander A Alemi. Inception-v4, inception-resnet and the impact of residual connections on learning. In Thirty-Firsi AAAI Confer- ence on Artificial Intelligence, 2017.
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. In International Conference on Machine Learning, pp. 6155-6165, 2019.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. In Advances in Neural Information Processing Systems, pp- 1306-1316, 2018.
Wei Wen, Cong Xu, Feng Yan, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication distributed deep learning. In Advances in neural information processing systems, pp. 1509-1519, 2017.
10

---

Under review as a conference paper at ICLR 2020
Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. Error compensated quantized SGD and its applications to large-scale distributed optimization. International Conference on Machine Learming. 2018.
Shuai Zheng, Ziyue Huang, and James T Kwok. Communication--fficcienn distributed blockwise momentum SGD with error-feedbac.. In Advances in neural information processing systems, 2019.

---

Under review as a conference paper at ICLR 2020
A
APPENDIX
A.1 CUMULATIVE DISTRIBUTION OF GRADIENTS IN TOPK-SGD
Itrdd00
1.0
Per-800
1.0
be-400
100
K2r 1000
bor 1000
0.8
Iar-1200
Aer-2200
D.
2200
0ur-1400
ker-3400
Ear 1400
0.6-
Itr=1100
0.6
Per-1600
0.5
-.00
0.2
0.2
0.2
0.0
28-1
(a) FFN-3
(b) LeNet-5
(c) ResNet-20
0.5
1200
Ier
kar-1520
Ber-1502
0.4
0.4
0.4
-15
-1.0
-0.5
0.0
5.5
1.0
1.5
-2.0
-1.5 -1.0
-2.5
0.0
0.5
1.0
1.5
2.0
-1
gradient value
gradient
grad
(d) VGG-16
(c) L.ST-PTBB
(f) LSTM-AN4
Figure 7: The cumulative distribution of u during the TopK-SGD training process.
A.2 GRADIENT DISTRIBUTION ON DENSE-SGD
100
144
1.4
120
0.5
ner-1200
0.6-
1400
1600
Iter 1600
1400
0.6
hor 1000
Por 1400
0.4
0.2
02-
0.0
75.00-0.75-0000
0.25-.25000 0.50 0.25 0.50 0.75 Loc
0.0
3
-2
0.0
-2
2
grodlent value
godientvaus
gradient volue
(a) FFN-3
(b) LcNet-5
(c) ResNet-20
Ior 800
kzr 800
hor 800
1t0:
ker 1000
1.0-
her 1000
Ber-1200
Iee- 400
3.0
Fen-1400
kar-1200
0.8
Iee-1400
Bar 1200
hor
10
gradent
leva
10-4
gradlent value
(d) VGG-16
LSTM-PTB
(I) LSTM-AN4
Figure 8: The histograms of u during the Dense-Se SGD training process.
12

---

Under review as a conference paper at ICLR 2020
A.3
GRADIENT DISTRIBUTION ON HAUSSIANK-SGI
0.8
ie-000
Ite-00d
Hen-1000
0.5
1200
Iten1200
ner-1200
0.6-
for 1400
Rer-1409
0.5
7er 2ar-1400
Ioor 1600
Ior 1500
7or 1900
0.4
0.4
0.2
0.4
02
0.2
0.8
11.00-0..0 2.75--255--- 75-0.30-0.25
0.20--05.00000 0.50 0:25 0.50 0.75 1.0
0.0
-15
-1.0
-0.5
0.
1.0
1.5
0.0
-0.75 -0.30
-0.25
0.00 0.55 0.50 0.75
gradient value
gradient valu
gradient value
(a) FFN-3
(b) LeNet-5
(c) ResNet-20
3.5
Ner 810
K2r 500
bar 800
Ien-1 D00
ter-1000
Iee-100
3.0
Ian-1200
Ken-22 200
1.50
1200
2.5
Ite-11 1.00
1400
2.0-
0.5
815
2.00
(d) VGG-16
L.SM-PTBB
(f) LSTM-AN4
Figure 9: The histograms of un during the Gaussiank-SGG training process.
A.4 PROOF OF INEQUALITY (6
A
A + A4
A + A2 + A3
A + A2 As
A1 + A2 + AA) S (A1 + A.)(AA1 As As)
# + A1A2 A1A4 A + A1Aa + A4A1 A4A2 + A4Aa
+0 < A, + A4A2 + A4A3.
A.5 SENSITIVITY STUDY OF GAUSSIANK-SGD
60-
eccuracy
40
40
Gaussiank-SGD
GaussianK: SGD
DGC-SGD
30-
DGC-SGD
Topk
20
TopK-SGD
0.0
0.2
0.4
0.6
0.8
1.0
gradients
1e8
of gradients
le6
(a) VGG-16 CIFARIO
(b) ResNet-20 CIFARIO
Figure 10: Number of communicated gradients vs. accuracy. 0.001d
Our proposed Gaussianı operator could under- or over- sparsify the gradients, which makes the num- ber of selected gradients is larger smaller than k. To demonstrate the sensitivity of GaussianK- SGD to the configured k. we first evaluate the accumulated number of communicated gradients over the training process, which is shown in Fig. TO It that at the first several epochs,
13

---

Under review as a conference paper at ICLR 2020
Cauussank-SGDD under-sparsifies the gradients (requires higher communication overheads), and after that, Gaussiank over-sparsifies the gradients (requires lower communication overheads) with little loss of accuracy.
To study the impact of different on the convergence, we further evaluate the accuracy of GaDD by setting k 0.01d and h 0.005d on VGG-16 and ResNet-20 models with the same hyper-parameters as Fig. [6] The validation accuracy with different shown in Fig. 11 can be seen that Gaussiang would under- over- sparsify the gradients, GaussianK-SGD performs well on the convergence.
90
80
80
val accuracy
60
100
110
120
90
100
110
220
40
50
GaussianK SGD 0.00dd))
Gaussiane anc Sn-
0.001d)
SaU 0.005))
40
Caussiank-SCC 0.005d)
20
Gaussiank SGD 0k0000)
30
Laussiank SGD 0.010d)
20
40
60
80
100
120
20
40
60 epochs
80
100
120
epochs
(a) VGG-16 CIFARIO
(b) ResNet-20 CIFARIO
Figure 11: Sensitivity of GaussianK-Se -SGD using k 0.001d, 0.005d and le 0.01d compared to Dense-SGD on 16 workers.
14


Reviews:
[{"review_id": "rke_w79jFr", "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": "Top-k algorithm is a gradient sparsification method which gains its popularity to train deep networks due to its high compression ratio. However due to its computation overhead, it is not efficient on GPUs. This paper performs empirical study on the distribution of the gradients when training various deep networks, and provides a Gaussian approximation analysis to improve the convergence of the top-k algorithm. Further, the paper proposes to use a Gaussian-k algorithm to perform similar gradient sparsification with a much lower computational cost without losing much convergence accuracy compared to Dense-SGD. \n \nHowever, the theoretical result seems to me overstated in the sense that it lacks mathematical rigor in the proof and is not clear how much insights it brings to understand better why top-k sparsification algorithms work well in deep learning (Figure 5 shows that the bound is still too tight). It is written after Equation (6) that “One can easily prove that π is convex and it is always less than the reference line (y = −i/d + 1) if u follows bell shaped distributions as illustrated”, however it is not clear me in what sense this is true.  The u are random variables, therefore π is a curve which depends their realizations, hence it is a random curve. Or maybe it holds when d goes to infinity?\n\nThe numerical results are specific with k = 0.001d, which makes it hard to see if the Gaussian-k algorithm would still work using different k/d ratio. As shown in Figure 2,  some of the histograms of u^1_t are quite sparse (these plots are hard to read for different iterations, maybe use cdf instead and perform statistical test to check how close to Gaussian distributions), therefore in some of these cases the Gaussian approximation may be poor. It is worth further investigation of the robustness of this algorithm as a replacement of the top-k algorithm. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SkeyfEe1cH", "reviewer": "AnonReviewer3", "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": "This paper makes two contributions to gradient sparsification to reduce the communication bottleneck in distributed SGD.\n1) Based on an assumption on the distribution of gradient coordinate values that are backed by an empirical study, the paper derives a tighter bound on the approximation quality of top-k gradient sparsification. This result induces better convergence bounds.\n2) The authors note that the top-k cannot benefit from the highly parallel architectures popular in ML, and propose an approximate top-k sparsification operator. This operator tries up to three thresholds and checks how many entries are larger than this value. The initial guess is based on approximating the distribution of gradient coordinates with a normal distribution again.\n\nMy score is weak reject. I believe that both observations are valid, and that their solutions might be practically meaningful. However, I would like to see the comparison to another baselines [1]. I would also urge the authors to make it more clear that their theoretical results are based on a strong assumption on the distribution of gradients. The top-k approximation algorithm is practical but I find 3-step threshold search inelegant.\n\nComments: \n1) [1] is another baseline -- compare your method with it too. \n\n2) 4.3 Convergence performance \"operator can select close elements with Top_k\" --- It seems obvious that it can select similar elements. The question is whether the number of elements chosen is accurate. I would like to see this evaluated. It is unclear if this scheme is biased. As far as I can see, it might be over- or under-sparsifying. \n\n3) 3.1 Gradient Distribution \"One can easily prove\" --- please do so (in the appendix)\n\n4) Theorem 1 - Looks like this can't be true in general. I think it assumes d -> infinity. \n\n5) 3.1 Gradient Distribution \"then pi is a decreasing function\" --- should this be pi^2. Also in figure 3, the result of Eqn 7 is only correct if the curve if pi^2.\n\n6) Figure 2: I am not convinced that these distributions are 'gaussian'. In fact, they seem peakier. It seems to me that this should improve the results (i.e. make the descending pi^2 curve more convex). If this is true, I would encourage the authors to discuss this. BTW, the distribution is in terms of the whole model, or just one randomly picked layer?\n\n7) Conclusion \"theoretically tighter bound\" --- because the assumption on the distribution empirical, I find it slightly misleading to call this a 'theoretical bound'. I would urge the authors to make this very clear. (This does not mean I find the bound meaningless)\n\n8) Introduction: \"O(d), which generally limits the system scalability\" --- The O(d) does not explain scalability in terms of number of workers as is suggested. Note that even though bandwidth scales with O(d) in all reduce, the latency does scale with n. This should not be ignored.\n\n9) Related work/Gradient Sparsification --- Please add a reference for empirical success of top-k. I am not aware of much use outside of academia.\n\n10) Quite a few language errors (some paragraphs/sentences don't make sense at all and there are many cases with missing 'a's etc.)\n\n11) Some of the experimental details are missing\n    - what are the learning rates/batch sizes used in experiments.\n    - How topK is performed? Layer-wise or for the full gradient.\n    - Table 1 \"experimental settings\": how these values were chosen.\n    - Table 2 --- please define how scaling efficiency is computed.\n    - Table 2 --- Do these algorithms achieve the same validation accuracy during the training?\n    - Figure 1: which k was used in these plots? \n\n12) Figure 6: in VGG-16, the gap of 1 percentage point is quite large. This seems expected as the compression ratio is very high (1000x). \n\n13) Figure 6: Imagenet training scheme is not standard. SOTA validation accuracy for the Imagenet benchmark with Resnet50 is around 76%. Would it also have similar quality loss on later stages as in training VGG or ResNet20 on cifar? \n\n14) Eqn. 8 - I couldn't follow the first inequality.\n\n15) Introdcution: The first few times \"distribution of gradients\" is mentioned, it was unclear to me if this was over 'coordinates' (as it seems to be), or over 'data points', or 'training time'. Please clarify.\n\n\n[1] Jiarui Fang, Cho-Jui Hsieh. Accelerating Distributed Deep Learning Training with Gradient Compression.\n", "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": "HygKNsO9Kr", "reviewer": "AnonReviewer1", "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": "This paper  empirically investigates the distribution of the gradient magnitude in the training of DNNs, based on which a tighter bound is derived over the conventional bound on top-K gradient sparsification.  The authors also propose a so-call GaussianK-SGD to approximate the top-K selection which is shown to be more efficient on GPUs.  Experiments are carried out on various datasets with various network architectures and the results seem to be supportive.  Overall, I find the work interesting and may have real value for communication-efficient distributed training.  On the other hand, I also have following concerns. \n\n1.  The theory part of the work is basically based on empirical observations.  My sense is that it can be more rigorous than its current form.  For instance, the authors may give a concrete form (e.g. Gaussian) of the $\\pi$ and derive the area under the curve of  $\\pi$ and so on.  Right now, a major part of the derivation is given in a rough sketch. \n\n2. $||\\mu||_{\\infty}$ should be $||\\mu||^{2}_{\\infty}$ in Eq. 5. \n\n3. It is not clear to me why the inequality holds in Eq.8.   Could you elaborate on it a bit?  Again, it would be helpful if a concrete function of $\\pi$ can be given for derivation.\n\n4. I notice that different distributed training packages are used in experiments, e.g. NCCL and OpenMPI.  It is not clear to me why the experiments are not conducted using a consistent distributed setting.  I don't see authors compare the performance of them.  Also, when comparing the wall-clock time in end-to-end training, are the models trained using the same all-reduce setting?  The authors need to explain. Otherwise, the numbers in Table 2 are not directly comparable.  \n\nP.S. rebuttal read.  I will stay with my score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "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_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates gradient sparsification using top-k for distributed training. Starting with empirical studies, the authors propose a distribution for the gradient values, which is used to derive bounds on the top-k sparsification. The top-k approach is further improved using a procedure that is easier to parallelize.

The reviewers and AC agree that the problem studied is timely and interesting. However, this manuscript also received quite divergent reviews, resulting from differences in opinion about the rigor and novelty of the results, and perhaps issues with unstated assumptions. In reviews and discussion, the reviewers also noted issues with clarity of the presentation, some of which were corrected after rebuttal. In the opinion of the AC, the manuscript is not appropriate for publication in its current state. 
Decision: Reject