Decentralized stochastic gradient descent (SGD), where parallel workers are connected to form a graph and communicate adjacently, has shown promising results both theoretically and empirically. In this paper we propose Moniqua, a technique that allows decentralized SGD to use quantized communication. We prove in theory that Moniqua communicates a provably bounded number of bits per iteration, while converging at the same asymptotic rate as the original algorithm does with full-precision communication. Moniqua improves upon prior works in that it (1) requires no additional memory, (2) applies to non-convex objectives, and (3) supports biased or linear quantizers. We demonstrate empirically that Moniqua converges faster with respect to wall clock time than other quantized decentralized algorithms. We also show that Moniqua is robust to very low bit-budgets, allowing less than 4-bits-per-parameter communication without affecting convergence when training VGG16 on CIFAR10.
This paper considers training of DL models in a decentralized setting. Previous work (Tang et al 2018b, Koloskova et al 2019, Tang et al 2019) introduced communication compression in order to reduce communication cost in decentralized SGD. This paper shows that the naive way to apply quantization to compress communication can fail (but, none of the previous works used this naive way). The paper proposes a novel decentralized SGD algorithm called MONIQUA which communicates only with compressed vectors. The paper theoretically proves that MONIQUA asymptotically converges with the same speed as D-PSGD (Decentralized SGD with full communications) for non-convex functions. 
The main benefit of the proposed algorithm is that in contrast to the baselines, MONIQUA doesn’t require any additional memory and computation overhead connected to that. 
The paper also allow to combine MONIQUA with asynchronous communications (AD-PSGD) and decentralized data (D^2), which is novel, previous baseline didn’t allow asynchronous communications. Paper experimentally validates MONIQUA and show that it converges faster than the baselines on early optimization stage, but omit comparison of final results.
My score is weak reject. The method is interesting and elegant, doesn’t require additional memory, theoretically convergent with a good speed and allows asynchronous communication. However, it looks a bit incremental. In contrast to the baselines, MONIQUA does not support arbitrary communication compression. Experimental comparison is shown only for the beginning of the optimization where the algorithm doesn’t achieve state of the art accuracy. 
Major concerns: 
1. Superior experimental results are shown only for (i) the constant stepsize schedule and (ii) only in the beginning of the optimization. The algorithm is unable to achieve s.o.t.a. test accuracy and has severe accuracy drop of 10-20%. It is unclear if MONIQUA is able to close the accuracy gap. 
To get good test accuracy the exponentially decaying learning rate schedules are usually used when training ResNet on Cifar10. However, that is unclear if this learning rate schedule could be supported by the algorithm. I see that theoretically the same result would be not possible. Once the learning rate dropped, ||x_i - x_j|| has to be smaller than the new theta, which is not true. 
2. In contrast to the baselines, MONIQUA doesn’t support arbitrary quantization. The quantization level is fixed. For example, for the ring 8 case (which was used in experiments), the number of bits required to converge is at least 5 (I calculated it using expression for B on page 5). This also questions if MONIQUA will be able to converge to good accuracy in extreme bit-budget. 
Other concerns that should be addressed: 
3. The spectral gap is usually not a constant: for example for the ring topology it decreases as 1/n^2. That should be clarified in the convergence rate and the number of bits required to communicate. 
4. In the experiments, to ensure fair comparison, the tuning details of the averaging rate for DeepSqueeze and Choco baselines, and theta parameter for MONIQUA were not given.
5. Reproducibility of the experiments: Many experimental details are omitted: 
   - What are the values of hyperparameters used in the plots?
   - How did you model asynchrony in experiments?
   - How did you choose the parameter \theta in experiments?
6. In (1), why x is \in [-1, 1]^d? What if this assumption doesn’t hold in (4)? The Theorem 1 is not clear then.
7. Why taking mod \theta is required? Cannot you assume that ||Q(x) - x|| <= theta delta? The whole analysis will stay true.
8. In Asynchronous communication section, why \tau_k are the same for all the workers? Cannot different workers have different delays? 
9. Why in experiments D-PSGD doesn’t converge when the data are decentralized? This is not consistent with the theory, D-PSGD should converge just slower. 
Questions: 
10. Is there a way to compute theta it in practice beforehand? 
Minor comments: 
- x mod y is not defined when x is a float number.
- Intuition behind Moniqua: do you assume that worker 1 has only one neighbour (worker 2)? does m_1 is one dimensional or high dimensional? 
- Algorithm 1, the notation \bar X_k might be confusing as in the proof big letters correspond to matrixes. Consider to change on \bar x_k.
- why some equations are numbered and some are not? 
- In Asynchronous communication section: what are the assumptions on W_k? 
- it would be helpful for the clarity to remind what is the stochastic rounding quantization in configuration of experiments section. 
- which are the other algorithms you talk about in footnote 6? 
- In wall-clock time evaluation section: how floored outputs could be represented as 16-bit integers? aren’t the vectors which you quantize always smaller than one? 
- wall-clock time evaluation section: the statement that “algorithms diverge” might be confusing.
- Aggressive quantization add  ”.”
- why the number of epochs differ in different experiments? Fig. 3(a) and Fig. 4(a) ?