Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors present ErrorCompensatedX, which compensates the compression error using the information from the previous 2 steps instead of 1 for distributed SGD with variance reduction. Theoretical analysis is provided. Empirical results show that the proposed algorithm outperforms the baseline with single compensation.

main_review: The paper is well-written. A novel method for improving the error compensation in variance-reduced SGD is proposed. Furthermore, a general theoretical analysis framework is provided for the proposed method. The experiment results also show good performance compared to the baseline. Overall, I think this is a good paper and I tend to accept it.
I have the following questions/concerns:
1. Compared to single compensation, how much extra computation and memory is cost by ErrorCompensatedX?
2. According to line 184-186, if alpha=1 (SGD case), single compensation and ErrorCompensatedX share the same error bound. Does that mean that in SGD case, single compensation is equivalent to ErrorCompensatedX? No matter if this is correct or not, could you give more explanation about such a special case?
3. I would recommend adding some more experiments. It could be either larger experiments like CIFAR-100/ImageNet, or applications other than CV, like NLP. Although I don’t think this is a big issue, using multiple datasets/applications in the experiments will be very helpful in showing the good performance of the proposed method.
limitations_and_societal_impact: 1. In some cases, such as momentum SGD, it seems that ErrorCompensatedX does not outperform single compensation.
2. Only 1 compressor (1-bit compressor) is tested in the experiments. Different compressors may have different behaviors. I also recommend to try top-k and random-k compressors.
3. Communication reduction is mostly for reducing the overall time for distributed training. However, no training time is provided in the experiments.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes and analyse a generic error compensated scheme for variance reduced optimization algorithm in a distributed setting.
main_review: The paper is well-written and pleasing to read. It is not excessively original, but the analysis is generic to several variance-reduced algorithms and very nicely carried out with a good balance between quantitative results and qualitative explanation. The contribution is also well-motivated with respect to previous work. The numerical experiments are also nicely presented without being excessively striking. It is the most appreciable paper in my batch of seven NeuRIPS papers this year.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces a new method for error compensation in distributed optimization algorithms, specifically compressed gradient descent-based (CGD) algorithms, with the ultimate goal of reducing communication cost. Compared to existing error compensation approaches, the proposed method, termed ErrorCompensatedX, utilizes the error from the previous two steps of compressed gradient descent to improve it’s convergence rate. Despite some promising theoretical results, the numerical experiments seem inadequate, and below average exposition makes parts of the paper difficult to fully comprehend.
main_review: While the idea presented seems promising and some theoretical results are provided, this paper does not clearly indicate whether the proposed scheme reduces communication cost. Exposition is suboptimal and quite dense in places, and as such makes judging the paper on its’ merits and identifying novelties difficult.

Some further comments are below:
1. Since this paper concerns communication efficient optimization, one would expect to see theoretical and empirical results regarding communication complexity, communication rounds and number of communicated bits. The empirical results presented in Sec. 5 focus only on training loss and testing accuracy versus the number of training epochs. 
2. Is $\xi^{(i)}$ in Eq. (1) different from $\xi_t$ in Eq. (2)?
3. Is $\alpha_t$ a positive scalar, or can it take any value?
4. Some additional intuition regarding the role of $\mathbf{e}_t$ in the equations after line 103, could facilitate better understanding of the proposed method. Also, how  does this equation describe a low-pass filter? 
5. In the beginning of Section 3.2 it is mentioned that $\mathscr{A}$ is transferred from worker nodes to the server, however the ensuing equations do not involve the workers. The note in line 126 that the discussion focused on the one worker case should be mentioned earlier, ideally in the beginning of the subsection.
6. The difference between $\mathbf{\delta}_s$ between the second and third equations in Sec. 3.2 can be confusing.
7. The innovation of ErrorCompensatedX compared to regular Error Compensation should be made more explicit in Sec. 3.2.
8. In line 122 it is mentioned that when $\alpha = 1$, the last term disappears. However, if $\alpha = 1$ all terms except $\mathbf{x}_0$ seem to disappear. 
9. In line 133 it is mentioned that "using just the compression error from the last step is not good enough". Not good enough with respect to what criterion? Also, where is this analysis shown?
10. In Assumption 2, the same inequality is written twice. 
11. What does the learning rate in Sec. 5 refer to?

limitations_and_societal_impact: Discussion regarding limitations of the proposed method seems lacking. 

Paper is mainly theoretical and societal impact depends on how the practitioner would deploy the proposed method.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an extension to the error compensation framework to reduce communication burden in distributed systems. The idea is to use previous two (instead of one) accumulated compression errors in the history together with low-pass filter update. The extension is applied for variance reduced methods and is analyzed for non-convex smooth objectives. The work provides general framework to analyze such methods, it shows that asymptotic convergence of such methods is the same as without compression and error compensation. Two numerical experiments are included with linear regression and neural networks to illustrate effectiveness of the proposed extension.
main_review: 1. It is mentioned in the abstract (lines 8,9) that your analysis standard Error Compansation (EC) does not fully compensate the compression error. Where this statement is justified in your theory ?

2. Then, you propose ErrorCompansatedX (ECX), which presumably compensate the compression error fully and achieves the same rate as without compression. But the same claim about the rate is true for EC methods (see [1,4,5]).

3. Are the statements on reducing half (line 19) or 3% (line 24) of the communication volume without degrading the speed of convergence accurate ? Are they theoretical results for general training or numerical results on some datasets ?

4. Are the references of Momentum SGD in line 28 and STORM in line 29 accurate ? For example, STORM method is not from (Cutkosky & Mehta, 2020).

5. In the introduction (lines 32-34), it is claimed that *the best* compression method for Variance Reduced (VR) methods is found and it is the proposed ECX. Where exactly do you prove that it is the best one ? If so, it is the best one in what sense ?

6. The first point of contribution (lines 36-38) claims that ECX admits *faster convergence rate* compared to previous methods. However, section 4 (lines 145-146) says it gives the same (asymptotic) rate as uncompressed methods; something that previous methods also achieved (see [1,4,5]).

7. Line 38 mentions that ECX fully compensates all error history. What does this mean ? If you are referring the fact that ECX uses previous two errors, then what about using previous three or more error terms. If this statement is empirical and is based on some experiments (e.g., Figure 1), it should made more precise.

8. The second point of contribution (lines 39-44) decomposes the rate into the terms affected by compression and terms that will remain even with full precision training. I think this is typical for most of the compressed algorithms. Minor: equation (2) in line 44 is defined much later after line 90.

9. Lines 73-78 are confusing. Why you highlight linear rate from (Mishchenko et al., 2019; Liu et al., 2020) and (Horva´th et al., 2019) in strongly convex setup, when you consider non-convex objectives only and all those three papers also include some theory for non-convex optimization (which is not mentioned there) ?

10. EC update rule described after line 99 is not exactly accurate because of the step-size $\gamma$ (it should be inside the compression operator; see e.g. equation (8) of (Stich et al., 2018b) ).

11. Related to the claim made in line 106, see [3,6,7].

12. Is the dependence of $\epsilon$ in the rate of Corollary 4 accurate ? It is in the denominator, meaning that less compression leads to worse upper bound. Also, the same leading term is achieved by Doublesqueeze method for non-convex losses.

13. In the section for experiments it is mentioned about four implementations, but plots contain three. Assumption two contains the same expression twice.

14. At least 10 references do not have journal/conference names (if not published then usually arXiv version is being referenced).

Out of curiosity, why the method is called ErrorCompansatedX ?

--------------------------- 


What can be done to improve the paper ?

I1. It is claimed that the paper provides general theoretical analysis framework for error compensated and variance reduced methods. One can use that framework to design a new method, which would outperform current VR methods both theoretically and numerically in some (at least one) settings. 

I2. By describing the improved behavior of some method, it is important to identify and highlight the aspect/compenent of the method which actually makes the improvement. For instance, the proposed Algorithm 1 adds two components on top of EC framework: low-pass filter and second previous compression error. Which component contributes to faster convergence in Figures 1 and 2 ? Are both of them needed ? Do we actually need second previous error, since as it was mentioned in lines 101-102, low-pass filter can be helpful for stabilizing the training and further improving the training speed.


I3. Avoid over-claimed or conflicting statements (see points 3,5,6 above)

I4. Fix the references and inaccuracies when citing prior work (see points 9,10,11,14)

--------------------------- 


[1] Hanlin Tang, Xiangru Lian, Chen Yu, Tong Zhang, Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. ICML 2019.

[2] Horva´th, S., Kovalev, D., Mishchenko, K., Stich, S., & Richtarik, P.. Stochastic distributed learning with gradient quantization and variance reduction. arXiv 1904.05115, 2019.

[3] Xun Qian, Hanze Dong, Peter Richtarik, Tong Zhang. Error Compensated Loopless SVRG for Distributed Optimization. OPT2020: 12th Annual Workshop on Optimization for Machine Learning, 2020.

[4] Sebastian U. Stich, Sai Praneeth Karimireddy. The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Updates. Journal of Machine Learning ResearchJMLR 21(237), 1–36, 2020.

[5] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, Martin Jaggi. Error Feedback Fixes SignSGD and other Gradient Compression Schemes, ICML 2019.

[6] Xun Qian, Peter Richtarik and Tong Zhang. Error Compensated Distributed SGD Can Be Accelerated, arXiv 2010.00091, 2020.

[7] Xun Qian, Hanze Dong, Peter Richtarik, Tong Zhang. Error Compensated Proximal SGD and RDA. OPT2020: 12th Annual Workshop on Optimization for Machine Learning, 2020.
limitations_and_societal_impact: It might be a good idea to write a small section on limitations.
review_title: null

Meta-review: I agree with the reviewers that this paper is well-written and has a nice analysis of several variance-reduced algorithms, balancing quantitative results and qualitative explanations. But I also agree with the reviewers that the exposition and notation could be improved, the effect of the low-pass filter could be better explained, and more extensive experiments could be carried out (especially for STORM, which has the best practical performance improvements, and for data sets where other values of alpha and beta are optimal). The reviewers give a large number of minor suggestions that can help you to significantly improve the paper.

I recommend that the paper should be accepted.
Decision: Accept (Poster)