Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The authors present an algorithm CHOCO-SGD to make use of communication compression in a decentralized setting. This is an interesting problem and the results are promising. Firstly they prove the convergence rate of the algorithm on non-convex smooth functions, which shows a nearly linear speedup. 

Second, on the practical part, there have 3 main results:
	1. They compare CHOCO-SGD under various compression schemes with the baseline. The results show the algorithm generally outperforms the baseline.
	2. They implement it over a realistic peer-to-peer social network and show a great communication performance under such a network with limited bandwidth.
	3. In a datacenter setting, they compare the algorithm with all-reduce, which is a centralized communication method. The results show a strong training reduction for CHOCO-SGD.

Also, the paper is mostly nicely written.

However, there have several issues:

	1. In the introduction, they introduce their experiments with the order from "datacenter experiment" to "peer-to-peer experiment", which is different from the actual presenting order.
	2. In the description of Algorithm 1, the representation of initial values should be x{(-1/2)}_{i} instead of x{(0)}_{i} since line 2 using the term x^{t-1/2}_{i} with the range of t from 0 to T-1.
	3. About "datacenter setting" experiment, it seems not an apple to apple comparison between CHOCO-SGD and all-reduce method since CHOCO-SGD stands for the decentralized algorithm with compression and all-reduce stands for a centralized algorithm without compression. It's better to compare with at least one centralized algorithm with a compression scheme (like QSGD[1], signSGD[2], DGC[3]).
	4. Although they compare with the baseline (DCD and ECD) on Cifar-10 dataset,  it's worth to compare with them on the ImageNet since the result may be different under large-scale training.

Overall, this could be a great paper if fixing the issues above.


[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] Bernstein J, Zhao J, Azizzadenesheli K, Anandkumar A. signSGD with majority vote is communication efficient and fault tolerant. arXiv. 2018 Oct 11.

[3] 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.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper studies non-convex decentralized optimization with arbitrary communication compression. It is well motivated and well written. The authors consider CHOCO-SGD for non-convex decentralized optimization and establish the convergence result based on the compression ratio. This result does not rely on specific quantized method and main term in the upper bound matches with the centralized baseline. The authors also show CHOCO-SGD with momentum is effectiveness in practical. The experimental results on several benchmark datasets validate the algorithm achieves better performance than baselines

Both of the theoretical and empirical results are convincing. I believe this paper is ready for publication.

Minor comments:

1. It is prefer to present Algorithm 2 and 3 in the main text, since they are mentioned by the statement of Theorem 4.1 and used in experiments respectively.

2. Can you provide some theoretical guarantee of CHOCO-SGD with momentum?

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper studies the convergence of CHOCO-SGD for nonconvex objectives and shows its linear speedup while the original paper of CHOCO-SGD only provides analysis for convex objectives. The momemtum version of CHOCO-SGD is also provided although no theoretical analysis is presented.

Extensive empirical results are presented in this paper and the two use cases highlight some potential usage of the algorithm. However, there some concerns which could be addressed.

First, the authors only provide analysis on CHOCO-SGD but the comparison with baselines are based on their momemtum versions. Moreover, some highly relevant baseline like DeepSqueeze are not cited and compared. Thus, the advantage of vanilla CHOCO-SGD over other alternatives is not convincing. 

Second, the cores of decentralized optimization include minimization of objective and consensus of the solution. However, no evaluation of the consensus is presented and this leads to the following point.

Third, it seems the authors report the average performance over all nodes using their individual model. If this is the case, the reported perfromance and comparison are not convincing. Without consensus, different nodes can have individual minimizer. In this case, the obtained average loss can be even smaller than the optimal loss. Under current measurement, if we run SGD on each worker individually without any communication, we will still get pretty good performance but this does not achieve the goal of decentralized optimization. Further clarification on this is needed.

Overall, I think the technical contribution of this paper is unclear and the evaluation is not convincing. 

review_title: Official Blind Review #1

Meta-review: The authors present an algorithm CHOCO-SGD to make use of communication compression in a decentralized setting. This is an interesting problem, and the paper is well-motivated and well-written. On the theoretical side, the authors prove the convergence rate of the algorithm on non-convex smooth functions, which shows a nearly linear speedup. The experimental results on several benchmark datasets validate the algorithm achieves better performance than baselines. These can be made more convincing by comparing with more baselines (including DeepSqueeze and other centralized algorithms with a compression scheme), and on larger datasets. The authors should also clarify results on consensus.
Decision: Accept (Poster)