Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes MCM ~ algorithm to perform bidirectional compression in distributed setting. The authors claim similar convergence guarantees as vanilla setting. 
They introduce the notion of sending different models to different clients while keeping the global model preserved. 

main_review: Overall, the presentation has cyclomatic complexity. Its hard to read and the main idea is not clear at a fast glance. I would strongly encourage improving the presentation and writing.

For example, using algorithmic blocks would greatly help. 

Novelty:
I have concerns regarding the novelty of the algorithm. The idea of error feedback is leveraged in both client and server to deal with bidirectional compression degradation. While client EF is common, server EF is less common but not new [1] 

Also, using EF at both end seems like a natural approach and not very novel or insightful .

The main contribution of the paper is thus the analysis. However, I find the analysis straightforward extensions of EF-SGD [2] proof technique. 

Experiments :
The experiments are tiny. MNIST , using simple toy like datasets 
I would strongly encourage performing experiments on sufficiently large models and more sophisticated datasets. 

The deep learning exp in appendix show S11(a) slower convergence.

Time Complexity:
Note that computing the server memory etc has computational overhead and it would be great to run experiments wrt wall clock time. 
Also, a precise asymptotic complexity analysis might be useful 

[1] https://arxiv.org/pdf/2106.08882.pdf
[2] https://arxiv.org/abs/1901.09847
limitations_and_societal_impact: See Above
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a bidirectional compression algorithm for parameter-server-based distributed training.
Two variants, MCM and Rand-MCM, are proposed to achieve the same improvement as the uplink-compression-only compression algorithm, where the downlink-compression-only impacts local models while the global model is preserved.
The Rand-MCM also introduces the concept of (simulated) random smoothing via model compression.
main_review: ### Advantages
* The paper has been written well and is theoretically sound.
* The use case for introducing downlink and uplink compression is critical and could have significant consequences.
* The concept of using different compressed worker models to perform random smoothing is intriguing.


### Disadvantages
1. The paper's convergence analysis results were not fully validated (through some numerical results).
    1.  The memory mechanism is crucial for controlling the variance of the local model, but I cannot find a detailed (empirical) discussion related to $\alpha_{\text{dwn}}$. Figure 1 is insufficient to justify the trade-off of the different hyper-parameter choices; some numerical results are required here to justify the tightness of the convergence rate.
    2. Similar issues appeared in the $\omega_{\text{up}}$. Hyper-parameters associated with different levels of $\omega_{\text{up}}$ should be included, and studied, for example, in terms of complexity.
    3. It is a good idea to use a constant learning rate to observe the bias and variance independently. However, the current results in Figures 2 & 3 are hard to tell the difference, e.g., (1) it is difficult to determine whether all curves enter the saturation level or not due to the log-scale visualization, (2) why the Rand-MCM results are omitted in Figure 2c & d, and (3) for MCM results in Figures 2d & 3d, the reached training loss values are far behind other baselines and I am not sure if prolonging the training period can close this gap or not. It is necessary to provide a more detailed illustration.
    4. The numerical evaluations only take into account a fixed number of workers and a fixed level of compression/quantization. Because of the limited experimental setups, understanding the empirical behavior of the proposed algorithms, as well as the alignment between numerical results and convergence analysis, is difficult.
2. The concept of using the perturbed model in distributed training to perform random smoothing is not novel; the authors should at the very least include a brief discussion with [1, 2, 3, 4]. It would be great if the authors could use the insights of improved gradient Lipschitz in [5] to further justify the gain of their proposed Rand-MCM algorithm.

### Reference
1. SmoothOut: Smoothing Out Sharp Minima to Improve Generalization in Deep Learning, https://arxiv.org/abs/1805.07898
2. Gradient Noise Convolution (GNC): Smoothing Loss Function for Distributed Large-Batch SGD, https://arxiv.org/abs/1906.10822
3. Extrapolation for Large-batch Training in Deep Learning, https://arxiv.org/abs/2006.05720, ICML 2020
4. Sharpness-Aware Minimization for Efficiently Improving Generalization, https://arxiv.org/abs/2010.01412, ICLR 2021
5. Randomized smoothing for stochastic optimization, https://arxiv.org/abs/1103.4296, SIAM Journal on Optimization.


=== review update ===
I am happy with the responses and I will raise my score to 6.


limitations_and_societal_impact: Please check the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed to compress model different for improving downlink compression. The theoretical analysis on convex problems shows that the dominant term does not depend on the compression error of the downlink, thus improving upon on the existing results on two-way compression.
main_review: Overall, the idea is interesting and the paper is well written. However, I have a few concerns:

1. One motivation of the paper is that the downlink communication is cheaper than the uplink one. This depends on the actual network topology. If we consider a mesh topology, recursive doubling allows us to perform broadcasting faster.  But if we consider a general server-worker bipartite graph (Jiang, Yimin, et al., 2020), the uplink and downlink communication can be overlapped and the downlink one is not more efficient than the uplink one.

2. The theories of  Zheng et al. [41] and Tang et al. [36] are for nonconvex problems. What is the convergence result of the proposed method for nonconvex objective? Can we still remove \omega_{dwn} from the dominant term? And, Corollary 2 in Tang et al. [36] also shows that \omega_{up/dwn} is in a higher order term 1/T^{2/3}.

3. Bound (5) has a quadratic dependency on \omega_{dwn}, which is worse than the bound for two-way compression.

4. Given a fixed communication budget, how do we distribute it over uplink and downlink to optimize the convergence rate?

5. How does the distribution of the difference of gradient differ from the one of model? And, how does this difference affect the choice of the uplink and downlink compressors?

6. What does d=20 mean in Figure 2?

7. The experimental setup is weak, i.e., synthetic dataset and small image classification problems. 

Jiang, Yimin, et al. "A Unified Architecture for Accelerating Distributed {DNN} Training in Heterogeneous GPU/CPU Clusters." OSDI. 2020.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors propose MCM, a new algorithm achieves bidirectional compression with better convergence rate. Theoretical analysis is provided. The empirical results show good performance.

main_review: The paper is well-written. The theorems give detailed analysis in strongly convex, convex, and non-convex cases. The experimental results show that MCM can achieve better convergence when using the same communication overhead as the baselines.
Also, I like the idea of calculating the carbon footprint in the appendix.
limitations_and_societal_impact: The experiments are still not large enough. In distributed training, we usually focus on large-scale problems like imagenet. Cifar100 or some NLP tasks are also recommended. However, since I believe that this paper focuses mostly on the theoretical analysis, I don’t think this is a big issue.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed a new method: MCM for bidirectional compression in federated learning. Convergence analysis showed that linear convergence can be achieved with the proposed method. Empirical results also show the method could achieve non-trivial performance with high compression rate.
main_review: I'm a bit concerned with the novelty of this work. Compression with memory method has been previously proposed, but only in the uplink case. This paper seems simply applying it during downlink and analyze the convergence behavior. Hence, I wonder that the contribution is a bit incremental here.

In terms of the experiment section, the compression operator being used is specifically s-quantization. However, there are other naive unbiased compression methods like random masking. To show the generality of this method, multiple compression operators for C_up and C_down should also be presented in the main experiment section. Other than that, biased compression methods like top-k masking without using MCM are also interesting to compare with.

In practice, people would also care about generalizability as well as convergence. Hence, I suggest adding test metrics(loss/accuracy) for cifar and mnist to compare the performance of MCM with baselines.
limitations_and_societal_impact: Limitations and suggestions are listed in the main review.
review_title: null

Meta-review: This work proposes MCM, a method that performs bidirectional (i.e., both uplink and downlink) compression in distributed learning. A benefit of the approach is that it is able to match convergence rates of methods that use compression in only a single direction. The reviewers were generally in agreement that the work was well-written and motivated. However, many of the reviewers were unclear about the novelty of the approach, and there were a significant number of additional experiments included as part of the discussion period (e.g., relating to test metrics, new datasets). I believe the paper will be significantly strengthened if the authors carefully incorporate the discussed changes (specifically, more clearly outlining the main contributions/novelty and including the additional experiments that have been run since the time of submission). Although one reviewer finds the results unsurprising, this view was not shared by others, and I agree with the remainder of the reviewers that this work provides a solid contribution in communication-efficient learning.
Decision: Accept (Poster)