Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This papers proposed an interesting idea for distributed decentralized training with quantized communication. The authors show that naively compressing the exchanged model can fail to converge, and introduce to compress the model difference with modulo operation. The idea is further applied to decentralized data and asynchronous optimization settings. Convergence analyses are provided for non-convex problems. 

Though I found this paper interesting and novel, I have several concerns:

1. There is no convincing explanation why modulo operation makes the algorithm better. In particular, the equation $((m_2)_j - (m_1)_j) \text{mod} \theta = (m_2)_j - (m_1)_j$ does not hold. For example, let $(m_2)_j = 5$, $(m_1)_j = 3$ and $\theta=2$, then $((m_2)_j - (m_1)_j) \text{mod} \theta = (5 - 3) \text{mod} 2 = 0$ and $(m_2)_j - (m_1)_j = 5- 3 = 2$.

2. The proposed algorithm requires knowledge of $\theta$, which depends on the upper bound of gradient. If $\theta$ is underestimated, the algorithm will suffer from large errors. For instance, suppose that true $\theta$ is $5$ while we use $4.5$, then an identity quantizer cannot even recover the original value, e.g., $(5/4.5) \text{mod} 1*4.5 = 0.5 << 5$. On the other hand, if $\theta$ is overestimated, the convergence is dramatically slowed down. I checked authors' response to Reviewer 3 regarding this issue. However, they are not efficient and can still provide wrong estimates.

3. The upper bound of staleness is missing in the main text and convergence bound. I found that bounded delay is assumed in the supplementary. However, the constant for bounded delay is missing in Theorem 4.

4. The experiments are not convincing. In particular, Figure 2 shows that all the quantization methods perform very bad with low bits format. The centralized method DoubleSqueeze uses error feedback and supports arbitrary compression. Based on my experience, even with the 1-bit quantizer introduced in (Karimireddy et al., 2019), DoubleSqueeze converges as fast as full precision SGD. Also, it seems that final test accuracy of D-PSGD on ResNet110 is just 80+, which is much lower than its official 93.6% test accuracy. This indicates that experiments are not appropriately done.

5. CIFAR-10 is a very small scale dataset. For distributed training, it is more convincing to conduct experiments on larger datasets such as ImageNet.

They are a lot of typos. The authors need to double check.

Karimireddy et al., Error Feedback Fixes SignSGD and other Gradient Compression Schemes. ICML 2019.

review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: This work is about the use of quantized communication in decentralized stochastic gradient descent. The general advantage of using quantized communication is that is has the potential to reduce the amount of data exchanged, thereby leading to faster convergence -- and the main focus of this work is to include ideas that stem from quantized communication into decentralized training approaches. Competing methods of this kind suffer from potentially severe problems like memory overhead, limited applicability to convex problems, or the need for nonlinear quatizers.

The proposed Moniqua algorithm is an attempt to overcome these shortcomings. A central technical contribution is the analysis of direct quantization strategies in decentralized SGD in Theorem 1, which basically states that local models can fail to converge even for simple objective functions. The motivation for the Moniqua algorithm -- which is designed to solve this problem of local models -- is rather intuitive, and the algorithm can be implemented quite easily in practice. Some theoretic insight is provided, such as the asymptotic convergence rate (which is the same as in D-PSGD) and the loglog(n)-bound on the number of bits per parameter communicated as a function of the number of parallel workers.

Moniqua is empirically evaluated on a large number of different network configurations, and it seems that it indeed converges faster than other related algorithms, while being highly robust to aggressive quantization and strict bit-budgets. In summary, this work addresses a highly relevant problem and it nicely combines formal asymptotic analysis with experimental validation. I think, this work has indeed a great potential to advance this field of research. 
review_title: Official Blind Review #2

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

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper studies an important problem in the decentralized optimization, i.e., communication compression. Unlike gradient compression, the model compression in decentralized optimization is more challenging because the model parameters will not vanish like gradient. To solve this problem, the authors proposed Moniqua, where only lower-order bits of model are communicated since their higher-order bits are getting close. A hyperparameter $\theta$ is used as a “criterion” to separate the higher-order bits and lower-order bits of the model parameter via a modular arithmetic. The authors also apply Moniqua on D^2 and AD-PSGD.

There are several major concerns:
1.	It is not clear how the performance is measured in this paper. If the authors simply take the average of training loss over all nodes, this is not a good evaluation unless consensus is achieved. Unless clarifying this, it is hard to judge the performance. 
2.	It is better to provide evaluation on the consensus error which meansures the model consistency.
3.	The modular hyperparameter $\theta$ is not easy to choose and seems cannot help achieve consensus. On the one hand, the theory suggests its value to be proportional to the gradient magnitude bound, which could be very large in practice. But if $\theta$ is large, we cannot achieve even approximate consensus because of the quantization error. On the other hand, a small $\theta$ cannot ensure sufficient model average since higher-order bits are ignored by the modular arithmetic but actually they should be communicated. Either way, it doesn’t seem to be good for achieving consensus. 

Overall, the idea of Moniqua is interesting and the authors provide useful extensions based on it. But the evaluation is not convincing and whether the proposed Moniqua can achieve consensus is unclear.



review_title: Official Blind Review #1

Meta-review: This papers proposed an interesting idea for distributed decentralized training with quantized communication. The method is interesting and elegant. However, it is incremental, does not support arbitrary communication compression, and does not have a convincing explanation why modulo operation makes the algorithm better. The experiments are not convincing. Comparison is shown only for the beginning of the optimization where the algorithm does not achieve state of the art accuracy. Moreover, the modular hyperparameter is not easy to choose and seems cannot help achieve consensus.
Decision: Reject