Title: UNDERSTANDING TOP-K SPARSIFICATION IN DIS-TRIBUTED DEEP LEARNING

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.

1. 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 in a distributed setting, and x ∈ R d denotes the model parameters with d dimensions. At the t-th iteration, distributed synchronous SGD updates the model parameters by

EQUATION

where g p t ∈ R d is the stochastic gradient with its locally selected data for the loss function f p (x) : R d → R and η t is the learning rate. The aggregation of d-dimension gradients from P workers requires a communication complexity of O(d) in terms of communication traffics1 , which generally limits the system scalability. Gradient sparsification (Strom, 2015; Dryden et al., 2016; Aji & Heafield, 2017; Chen et al., 2018; Lin et al., 2018 ) is a promising technique for distributed SGD, which can significantly reduce the communication traffic while reserving the model convergence. In gradient sparsification, a compressor Comp k is applied on each worker to locally select k, k ≤ d, gradients for aggregation and Comp k ∈ {Top k , Rand k } (Stich et al., 2018) . Comp k (g p t ) ∈ R d zeros out (d -k) elements of g p t and keeps k elements unchanged. The zeroed-out d -k elements are stored as residual p t for the next iteration. Formally, the model parameters are updated by

x t+1 = x t -η t 1 P P p=1

Comp k (g p t + p t ) and p t+1 = g p t + p t -Comp k (g p t + p t ),

where p t ∈ R d and p 0 = 0. In theory, distributed SGD with gradient sparsification (e.g., Top k , Rand k and any other k-contraction operators) with error compensation has been proved to have the same order of convergence rate as vanilla SGD for both convex and non-convex problems if the number of 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 et al., 2019) . The convergence rates are derived with a key contraction property of the sparsification operator Comp k (Top k or Rand k ) (Stich et al., 2018; Alistarh et al., 2018) , that is

EQUATION

where E C is the expectation taking on the compressor and • is the 2 -norm. For any x ∈ R d , Top k (x) ∈ R d selects the top k largest elements (in terms of the absolute value) of x with corresponding indices and sets other d -k elements to zeros; while Rand k (x) ∈ R d randomly (in a uniform distribution) selects k elements from x with corresponding indices and other d-k elements are zeros. It is obvious that

EQUATION

)

Existing studies use the same error estimate for both Top k and Rand k in distributed SGD by exploiting the properties of (4), which cannot differentiate the convergence behavior of two operators.

In practice, however, TopK-SGD has a much faster convergence speed (in term of iterations) than SGD with Rand k (RandK-SGD) as empirically shown in (Stich et al., 2018) . We also compare the convergence performance between TopK-SGD and RandK-SGD on a 16-worker distributed setting with three popular convolutional neural networks (VGG-16 (Simonyan & Zisserman, 2014) , ResNet-20 and ResNet-50 (He et al., 2016) ). Our results are shown in Fig. 1 . We observe that TopK-SGD achieves very similar performance to the original distributed SGD (Dense-SGD), 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-SGD 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) (Krizhevsky et al., 2010) and ImageNet (Deng et al., 2009) data sets. k = 0.001d for TopK-SGD and RandK-SGD.

In this paper, we dive into the details of the Top k 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 k sparsification further enables us to propose a new computational-efficient selection algorithm for gradient which preserves the convergence property. 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 k should have a much tighter bound than Rand k , and we exploit the distribution property to formulate how Top k outperforms Rand k . (3) We design and implement an approximate top-k selection algorithm2 , which is much more efficient than existing top-k selection algorithms on GPUs. As compared with the existing sampling-based approximate top-k selection algorithm, we improve the scaling efficiency by 12-50% on our 16-GPU cluster.

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 et 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; Jiang & 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 32× (i.e., 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 as it can sparsify up to three orders of magnitude gradients be zero with little impact on the model convergence (Strom, 2015; Dryden et al., 2016; Aji & Heafield, 2017; Chen et al., 2018; Lin et al., 2018; Shi et al., 2019a) . Due to the much success of gradient sparsification (e.g., Top-k sparsification) in significantly reducing the communication traffic (Lin et al., 2018; Sun et al., 2019) , much recent work tries to build theoretical guarantees for SGD with gradient specification (Wangni et al., 2018; Stich et al., 2018; Alistarh et al., 2018; Jiang & Agrawal, 2018; Shi et al., 2019b; Karimireddy et al., 2019; Tang et 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 k which could have better convergence than other compression operators (e.g., Rand k ).

Gradient Distribution3 . Glorot & Bengio (2010) study the distribution of activation values of DNNs and also their corresponding gradients. They empirically showed that back-propagated gradients have Gaussian-like 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 or underflow. These work has demonstrated that the gradients during training are likely located near zeros. We extend the similar studies on the gradient distribution for TopK-SGD.

3. 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 k operator selects the exact local top-k elements of gradients so that it achieves nearly consistent convergence performance with Dense-SGD. Therefore, we 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 recognition. 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). LeNet-5 (LeCun et al., 2015) on MNIST, ResNet-20 (He et al., 2016) and VGG-16 (Simonyan & Zisserman, 2014) on CIFAR10 (Krizhevsky et al., 2010) . And 3) Recurrent Neural Networks (RNNs). Long Short Term Memory networks (LSTMs) on the Penn Treebank (PTB) (Marcus et al., 1993) and the AN4 (Acero, 1990) data sets. For PTB, we adopt a 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.

The details of the experimental settings are shown in Table 1 . As the compression operator is applied 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 if lated gradients, but one common feature is that most coordinates of u t are close to zero. Compared to the full gradient SGD (Appendix A.2), TopK-SGD shows wider distributions, which could be mainly caused by residual accumulation. When selecting top-k largest values (in terms of absolute values) from u t , the selected values should be located at the left and right sides on the histograms. Therefore, performing Top k on u t should generate a vector whose 2 -norm is very close to that of u t , that is Top k (u t ) 2 u t 2 . The intuitive result inspires us to formulate how much close of Top k (u t ) 2 to u t 2 . Specifically, we would like to derive a variable γ ≤ (1

-k/d) such that u t -Top k (u t ) 2 ≤ γ u t 2 holds.

3.2. THEORETICAL ANALYSIS AND RESULTS:

We investigate the Top k operator on u p t = g p t + p t (for ease of presentation, we use u to denote u p t ). Error estimation of Top k . Let π denote a sorted vector of |u|/ u ∞ in a descending order. That is

EQUATION

)

where ũ = u/ u ∞ . Assume that u (i) follows a bell shaped distribution (e.g., Fig. 3 (a)), and π 2 is a decreasing function w.r.t. i as shown in Fig. 3(b ). In order to evaluate Eq. ( 5), it is essential to calculate the area under the curve of π 2 . As illustrated in Fig. 2 , one can empirically prove that π 2 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 A 1 , A 2 , A 3 , and A 4 shown in Fig. 3 (c), we have

EQUATION

)

Due to the space limit, the proof of the inequality is put in Appendix A.4. Then we have

EQUATION

where the second equality can be obtained from the similarity of triangle M DB ∼ COB and EDB ∼ AOB, i.e.,

EQUATION

)

Putting altogether, we have

u -Top k (u) 2 / u 2 ≤ (1 -k/d) 2 =: γ (9)

and eventually summarized as the following theorem. Theorem 1. Assume that u ∈ R d follows a bell shaped distribution and π 2 is convex and less than the line y = -i/d + 1, then we have

EQUATION

EQUATION

)

Furthermore, it can be rearranged into the form that

EQUATION

)

Convergence Bound of TopK-SGD. We use the same assumptions on the objective function f : R d → R as (Karimireddy et al., 2019) . The assumptions are: 1) f is L-smooth and 2) f has a moment bound (i.e., E[g] = ∇f (x) and E[ g 2 ] ≤ G 2 for some G > 0, where g is a stochastic gradient and x is the model parameter). Therefore, we can directly use the the bound formulation of convergence rate with δ from (Karimireddy et al., 2019) in Remark 4.

Theorem 2. If we set η t = 1 √ T +1 for running TopK-SGD and under the assumptions of f , we have

EQUATION

)

where f * is the optimal solution.

The theorem indicates that after T ≥ O(1/δ 2 ) iterations, the first term of the right-hand side of inequality (13) will dominate the bound so that the convergence rate becomes O(1/ √ T ) which matches the rate of vanilla SGD. Note that our derived bound of δ = (2kd -k 2 )/d 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 (δ = 1/c) indicate that RandK-SGD or TopK-SGD should run after T ≥ O(c 2 ) iterations to make it catch up the convergence rate of Dense-SGD. Using inequality (10) for TopK-SGD, it just requires T ≥ O(c4 /(2c -1) 2 ) 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. 1 ).

3.3. GAUSSIAN k : AN APPROXIMATE TOP k OPERATOR:

Though TopK-SGD has a good convergence property with a 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 k could make the overall wall-clock time worse. For example, 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 4 . When we distribute the training to 16 Tesla V100 GPUs connected with 10 Gbps Ethernet (10GbE), the communication time of full gradients (d = 25, 557, 032) is around 0.2 seconds. However, the Top k operator with k = 0.001d on ResNet-50 with the Tesla V100 GPU consumes 0.4 seconds. The 0.2second 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 use DGC k to denote the hierarchical sampling method in selecting the largest top-k gradients. In RedSync-SGD (Fang et al., 2019) , the authors proposed a trimmed top-k selection algorithm (Trimmed k ) to select top gradients for CNNs by heuristically searching the threshold with moving the ratio between the maximum value and the average value. However, Trimmed k 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. We propose an approximate Top k operator named Gaussian k by exploiting the Gaussian-like distribution property of gradients. The key ideas of Gaussian k are: 1) We regard the d-dimensional gradients (i.e., u p t ) at each iteration as a normal distribution with the mean (µ) and standard variance (σ) which can be directly calculated in an O(d) complexity and the calculations are friendly to GPUs. 2) We estimate the threshold by exploiting the percent point function (ppf) of u p t with three parameters: p = 1 -k/d, µ and σ. 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 to the estimated threshold to the left or right side several times such that we can have very close top-k largest absolute values. The algorithm of Gaussian k is shown in Algorithm 1.

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-2.3.7, PyTorch-1.1.0, OpenMPI-4.0.1, and Horovod-0.16.4 (Sergeev & Balso, 2018) , which are kept the same for all evaluated algorithms.

4.1. NUMERICAL RESULTS OF THE TOP k 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 -Top k (u) 2 / u 2 and 1 -k/d with ours derived (1 -k/d) 2 . We also compare the three bounds in the real-world model training process. The results are shown in Fig. 5 . It is seen that both ours and the previous result are in the upper 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. 3(b) ) but not the original function. Therefore, if the shape of π 2 (i) can be exactly formulated, one can derive a tighter bound for the Top k operator than (1 -k/d) 2 and we will leave this as our future work. 

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 k , DGC k and Gaussian k operators is shown in Fig. 4 . For DGC k , we use 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 PyTorch's tensor APIs5 . The experimental results show that the Top k operator becomes very slow with a large number of parameters, while Gaussian k only generates slight overheads. DGC k also becomes inefficient if d is large. It is crucial for the end-to-end training to have a computing-efficient operator on GPUs such that the extra computation overhead would not limit the system scalability.

4.3. CONVERGENCE PERFORMANCE OF GAUSSIANK-SGD.:

To demonstrate the convergence performance of GaussianK-SGD, we run 120 epochs on CIFAR10 and 70 epochs on ImageNet with 16 workers. On CIFAR10, the hyper-parameters are listed in Table 1 , 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-parameters 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 k operator can select close elements with Top k . The gradient distributions in GaussianK-SGD are similar to TopK-SGD (Appendix A.2). In the evaluated three models, GaussianK-SGD and TopK-SGD have slight accuracy loss (around 0.6%-0.8%) compared to Dense-SGD. As suggested in (Lin et al., 2018) , the small residuals could have staleness compared to the current gradients so that it could cause the slight accuracy loss. Some optimization tricks in (Lin et al., 2018) like momentum correction would address this problem. We evaluate the average iteration time of GaussianK-SGD on the ImageNet (Deng et al., 2009) data set with four popular models (AlexNet (Krizhevsky et al., 2012) , VGG-16 (Simonyan & Zisserman, 2014) , ResNet-50 (He et al., 2016) and Inception-V4 (Szegedy et al., 2017) ) on a 16-GPU cluster compared to Dense-SGD with full gradients, TopK-SGD with the original top-k selection, DGC-SGD (Lin et al., 2018) with hierarchical sampling and RedSync-SGD (Fang et al., 2019) 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 sparsified algorithms. The results are shown in Table 2 , which shows that TopK-SGD and RedSync-SGD are even slower than Dense-SGD on the 16-GPU cluster, while our GaussianK-SGD runs much faster than other algorithms. Specifically, GaussianK-SGD is 1.19×-2.33× faster than Dense-SGD, 1.36×-3.63× faster than TopK-SGD, and 1.11×-1.51× faster than DGC-SGD, respectively. Even on the VGG-16 model, which has several large-size fully connected layers, GaussianK-SGD can achieve 85.5% scaling efficiency on the 16-GPU cluster with low-bandwidth Ethernet. 

5. CONCLUSION:

In this paper, we first identified that existing theoretical results fail to explain the convergence performance of distributed SGD algorithms with Top-k gradient sparsification (TopK-SGD). Then we empirically studied gradient distributions during training with TopK-SGD through extensive experiments, and observe that the elements of stochastic gradients are mostly located near zero (Gaussianlike distribution). The observation enables us to build a tighter bound for the Top k 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 an approximate top-k selection algorithm named Gaussian k which is much efficient than the existing top-k selection algorithms on GPUs. We finally conduct extensive experiments to verify our derived bound for the Top k operator and the convergence performance of distributed SGD with Gaussian k (GaussianK-SGD). In terms of the scaling efficiency, GaussianK-SGD achieves up to 2.33×, 3.63× and 1.51× faster training speed than full gradient SGD, TopK-SGD and DGC-SGD on a 16-GPU cluster connected with 10 Gbps Ethernet, respectively. A.4 PROOF OF INEQUALITY (6)

A 1 A 1 + A 2 + A 3 ≤ A 1 + A 4 A 1 + A 2 + A 4 ⇔A 1 (A 1 + A 2 + A 4 ) ≤ (A 1 + A 4 )(A 1 + A 2 + A 3 ) ⇔A 2 1 + A 1 A 2 + A 1 A 4 ≤ A 2 1 + A 1 A 2 + A 1 A 3 + A 4 A 1 + A 4 A 2 + A 4 A 3 ⇔0 ≤ A 1 A 3 + A 4 A 2 + A 4 A 3 .

A.5 SENSITIVITY STUDY OF GAUSSIANK-SGD Our proposed Gaussian k operator could under-or over-sparsify the gradients, which makes the number of selected gradients is larger or 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. 10 . It is seen that at the first several epochs, our GaussianK-SGD under-sparsifies the gradients (requires higher communication overheads), and after that, GaussianK-SGD over-sparsifies the gradients (requires lower communication overheads) with little loss of accuracy.

To study the impact of different k on the convergence, we further evaluate the accuracy of GaussianK-SGD by setting k = 0.01d and k = 0.005d on VGG-16 and ResNet-20 models with the same hyper-parameters as Fig. 6 . The validation accuracy with different k is shown in Fig. 11 .

It can be seen that even Gaussian k would under-or over-sparsify the gradients, GaussianK-SGD performs well on the convergence. 

:

The ring-based AllReduce collective can achieve the bandwidth optimal performance that is not related to the number of workers, but there exist latency terms that will increase with increased number of workers.

Our system implementation will be made open-source after the review process.

The distribution we discussed in this paper is over coordinates on a particular vector (e.g., activation outputs, full gradients).

The model is trained with the 32-bit floating point without using Tensor Cores of the Tesla V100 GPU.

https://pytorch.org/docs/stable/tensors.html

Figures and Tables:

Figure1: Convergence comparison between original distributed SGD (Dense-SGD), Top k sparsification (TopK-SGD) and Rand k sparsification (RandK-SGD) at 16 distributed workers on the CIFAR10(Krizhevsky et al., 2010) and ImageNet(Deng et al., 2009) data sets. k = 0.001d for TopK-SGD and RandK-SGD.

Figure 2: The histograms of u 1 t of TopK-SGD. For each model, the gradient histograms are plotted every 200 iterations from iteration 200 to 1600 (other iterations have similar shapes).

Figure 3: The shape of π 2 (i) with different i with d = 100, 000 and σ = 1.

Figure 4: The GPU computation time (lower is better) of Top k , DGC k and Gaussian k . We use the PyTorch tensor API, "tensor.topk()", for the Top k operator.

Figure 5: The comparison of bounds with a range of k.

Figure 6: The convergence performance (top-1 validation accuracy) of distributed SGD with GaussianK-SGD using k = 0.001d compared to TopK-SGD and Dense-SGD on 16 workers.

Figure 7: The cumulative distribution of u 1 t during the TopK-SGD training process.

Figure 10: Number of communicated gradients vs. accuracy. k = 0.001d

Figure 11: Sensitivity of GaussianK-SGD using k = 0.001d, k = 0.005d and k = 0.01d compared to Dense-SGD on 16 workers.

Experimental settings. All models are trained by SGD with a 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 functions, batch sizes and learning rates with proper convergence performance. the same properties as Dense-SGD. During the training process of TopK-SGD (k = 0.001d for a d-dimension model), we measure the histograms of local gradients accumulated with the residuals (i.e., u p t = g p t + p t ). The histograms of u 1 t with different t on different models are shown in 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.1. It is seen that different models have different shapes on the accumu-

Table content: <table><tr><td>Type</td><td>Model</td><td># Params</td><td>Weight Init.</td><td colspan="2">Activation BS</td><td>LR</td><td>Data Set</td></tr><tr><td>FNN</td><td>FNN-3 LeNet-5</td><td>199,210 61,706</td><td>Xavier Xavier</td><td>ReLU ReLU</td><td>128 128</td><td>0.01 0.01</td><td>MNIST</td></tr><tr><td>CNN</td><td>ResNet-20 VGG-16</td><td>269,722 14,728,266</td><td>Xavier, Kaiming Kaiming</td><td>ReLU ReLU</td><td>32 128</td><td>0.1 0.1</td><td>CIFAR10</td></tr><tr><td>RNN</td><td colspan="2">LSTM-PTB 66,034,000 LSTM-AN4 27,569,568</td><td>Uniform Xavier</td><td>Tanh Tanh</td><td>20 4</td><td>22 0.0002</td><td>PTB AN4</td></tr><tr><td colspan="3">gradient value gradients distributions perverse 1.00 0.75 0.50 0.25 0.00 0.25 0.50 0.75 1.00 1e 1 0.0 0.2 1e3 0.4 0.6 0.8 1.0 frequency iter-800 iter-1000 iter-1200 iter-1400 iter-1600</td><td/><td/><td/><td/><td/></tr></table>

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 224×224. Scaling efficiency is defined by T1616T1 , where T 1 is the throughput of single GPU training, and T 16 is the overall system throughput of distributed training on 16 GPUs with weak-scaling.

Table content: <table><tr><td>Model</td><td colspan="5">Iteration Time (s) Dense TopK DGC RedSync GaussianK Dense TopK DGC RedSync GaussianK Scaling Efficiency (%)</td></tr><tr><td>AlexNet</td><td>0.571 0.891 0.369 7.203</td><td>0.245</td><td>14.1 9.0 21.8</td><td>1.11</td><td>32.8</td></tr><tr><td colspan="2">VGG-16 2.068 3.010 1.540 14.670</td><td>1.311</td><td>54.2 37.2 72.8</td><td>7.6</td><td>85.5</td></tr><tr><td colspan="2">ResNet-50 0.699 0.810 0.655 2.588</td><td>0.586</td><td>65.8 56.8 70.2</td><td>17.9</td><td>78.5</td></tr><tr><td colspan="2">Inception-V4 1.022 1.268 0.916 3.953</td><td>0.787</td><td>67.5 54.4 75.3</td><td>17.4</td><td>87.7</td></tr></table>

Peer review (iclr2020):
This paper makes two contributions to gradient sparsification to reduce the communication bottleneck in distributed SGD. 1) 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. 2) 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. My 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. Comments: 1) [1] is another baseline -- compare your method with it too. 2) 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. 3) 3.1 Gradient Distribution *One can easily prove* --- please do so (in the appendix) 4) Theorem 1 - Looks like this can*t be true in general. I think it assumes d -> infinity. 5) 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. 6) 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? 7) 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) 8) 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. 9) Related work/Gradient Sparsification --- Please add a reference for empirical success of top-k. I am not aware of much use outside of academia. 10) Quite a few language errors (some paragraphs/sentences don*t make sense at all and there are many cases with missing *a*s etc.) 11) Some of the experimental details are missing - what are the learning rates/batch sizes used in experiments. - How topK is performed? Layer-wise or for the full gradient. - Table 1 *experimental settings*: how these values were chosen. - Table 2 --- please define how scaling efficiency is computed. - Table 2 --- Do these algorithms achieve the same validation accuracy during the training? - Figure 1: which k was used in these plots? 12) 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). 13) 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? 14) Eqn. 8 - I couldn*t follow the first inequality. 15) 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. [1] Jiarui Fang, Cho-Jui Hsieh. Accelerating Distributed Deep Learning Training with Gradient Compression.