Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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. 
 
However, 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?

The 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. 
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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. 

1.  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. 

2. $||\mu||_{\infty}$ should be $||\mu||^{2}_{\infty}$ in Eq. 5. 

3. 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.

4. 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.  

P.S. rebuttal read.  I will stay with my score.
review_title: Official Blind Review #1

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