Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: Brief summary of the paper:
This paper studies data-parallel SGD that K processors work together to minimize an objective function. Each processor computes a stochastic gradient and broadcasts to other peers. In this distributed system, there is a trade-off between the *communication cost* from sharing the stochastic gradient and the *variance* from gradient quantization. This paper is a follow-up of Alistarh et al. (2017). It proposes a non-uniform (logarithmic) quantization scheme (NUQSGD). This paper provides theoretical analysis of the variance and communication cost of NUQSGD. Then the paper analyzes the convergence rate of NUQSGD for convex and smooth objective function. At the end, this paper empirically evaluates NUQSGD for image classification problem. 


Originality and significance:
This paper follows up on the parallel SGD framework proposed by Alistarh et al. (2017), where the authors proposed QSGD using a uniform quantization. This paper proposes NUQSGD using a non-uniform quantization method. The quantization of the stochastic gradient amplifies the stochastic variance, which influences the rate of convergence of SGD. Thus, on one hand, it is important to design a quantization method to improve the variance, for the sake of convergence rate. On the other hand, it is also important to decrease the communication cost. NUQSGD does not provide significant improvements in terms of the variance and communication cost. 

Theorem 2 and Theorem 3: QSGD has a variance of min {d/s^2, \sqrt{d}/s} and NUQSGD has a variance of min{O(d/2^{-2s}), O(\sqrt{d/2^{-2s}})}. QSGD has communication cost of \tilde O(s(s+\sqrt{d})) and NUQSGD has communication cost of \tilde O(2^{2s}\sqrt{d} ). Compared to QSGD, we can see that NUQSGD improves the dependence on s for the variance term, but it has a worse (exponential) dependence on s for the communication cost. Usually s is a small number and it serves as a hyper-parameter to be tuned. We would expect NUQSGD to improve the dependence on the dimension d, which is more significant. However, NUQSGD has the same dependence on d as QSGD in terms of both variance and communication cost. 

Experiments: Figure 3 compares NUQSGD with other parallel SGD algorithms and vanilla SGD. Figure 3 shows how fast the training loss decreases with respect to iterations. It would be great to add learning curves with the ‘time’ being the x-axis as well. Also, I would suggest the authors to record the time needed to proceed one iteration for each parallel algorithm to compare the communication cost. 

Quality and clarity:
This paper is well-written. 



review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The authors propose a new scheme for quantizing gradients which are followed by the previous work QSGD [1]. They show that it yields stronger theoretical guarantees than QSGD while showing a great empirical performance. 
The main difference between their scheme NUQSGD and QSGD is that they use nonuniform quantization (0, 1/2^{s},  …., 2^{s-1}/2^{s}, 1) instead of uniform quantization (0, 1/s, …, (s-1)/s,1).  Intuitively, by the way, it could reduce quantization error and variance by better matching the properties of normalized vectors.
The results are in 2 parts. First comparing with QSGD, they establish stronger convergence guarantees for NUQSGD, under standard assumptions. They also establish theoretical results for the variance upper bound and expected communication cost of their scheme. Second, they show strong empirical performance on deep models and a large dataset, with an efficient implementation in PyTorch.

However, there are several issues and questions that if fixed or illustrated could be a great paper.

	1) The author claim NUQSGD achieves stronger convergence guarantees comparing with QSGD but hasn't illustrated the point in detail. On page 6, the paragraph named 'NUQSGD vs QSGD' mainly claims that variance upper bound controls the guarantee on the convergence speed by empirically showing the results of variance upper bound. It would be great to include more theoretical analysis which demonstrates the importance of variance upper bound for convergence speed guarantee.
	2) In the experimental part, they control the hyperparameters including batch-size, base learning rate, momentum, and weight decay to be identical with each method. This may cause tuning biases (the setting may favor one method but hurt others' performance).
	3) Although the paper mainly focuses on comparing with QSGD, there are several relative communication efficient training algorithms which I think are worth to compare empirically (at least one of them). For example:
		a. Deep Gradient compression [2]
		b. signSGD [3]
		c. TernGrad [4]
	4) In figure 4, the encoding cost is significantly increased from 4-bit to 8-bit NUQSGD. Any reason why it happens? Is it due to inefficient encoding implementation? 

I agree with the authors' point that it's worth to explore the interaction between NUQSGD with more complex reduction patterns like ring-based. Since the ring-based algorithm like all-reduce is more popular in practice nowadays, interacting with it would have a better practical meaning. 

[1] D. Alistarh, D. Grubic, J. Z. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication-efﬁcient SGD via gradient quantization and encoding. In Proc. Advances in Neural Information Processing Systems (NIPS), 2017.

[2] Lin Y, Han S, Mao H, Wang Y, Dally WJ. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.01887. 2017 Dec 5.

[3] Bernstein J, Zhao J, Azizzadenesheli K, Anandkumar A. signSGD with majority vote is communication efficient and fault-tolerant. arXiv. 2018 Oct 11.

[4] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li. TernGrad: Ternary gradients to reduce communication in distributed deep learning. In Proc. Advances in Neural Information Processing Systems (NIPS), 2017.
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors propose a new gradient compression method, which is called nonuniform quantization. The algorithm is a reasonable variant of SGD with uniform quantization. The paper is well written. The experiments show good performance.

However, there are several weakness in this paper:

1. In this paper, a very important reference and baseline is missing, which is call error-feedback SGD [1]. Although the title of [1] focuses on SignSGD, it provides a general algorithm for arbitrary compressor with a error/variance bound similar to Theorem 2 in this paper, no matter the compressor is unbiased or not. Since [1] provides the SOTA results for quantized SGD, the proposed algorithm should be compared to it in the experiments.

2. This paper claims to have strong theoretical guarantees. However, the theoretical analysis only works for convex functions. Note that the theoretical analysis in [1] also works for non-convex functions.

3. Regardless of the convergence guarantees (which is weak considering the existing theorems in [1]). the proposed algorithm, NUQSGD, does not show improvement on the convergence, compared to the baseline QSGDinf.

4. In Figure 3, the experiments only show loss vs. # of iterations, which does not show the actual training time. In Figure 4, training time is only shown for NUQSGD, which ignores the other baselines including QSGD and QSGDinf. What I really what to see is training loss (or testing accuracy) vs. training time (or communication overhead, such as number of bits), so that we can evaluate the trade-off between communication overhead and the convergence, compared to the baselines.



Minor issue (I hope the authors can consider the following suggestions in a revised version. However, since the issue is minor, it doesn't affect the score):

!. In Definition 1, in some cases $s$ is c constant integer, and in some other case $s$ become a function, which is very confusing and not friendly to the readers. I also hope the authors can highlight the definition of $r$ and $p$, which are essential for understanding the nonuniform quantization mechanism. 




--------------
Reference

[1] Karimireddy, Sai Praneeth et al. “Error Feedback Fixes SignSGD and other Gradient Compression Schemes.” ICML (2019).
review_title: Official Blind Review #1

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

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

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