Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Error feedback (EF) is a technique for ensuring convergence of biased contractive compressor. However, it achieves suboptimal convergence rate when full gradient is used. Recently, EF21 was introduced to mitigate the theoretical deficiencies of EF. This paper studies several extensions of EF21 including EF21 with stochastic gradient, variance reduction, heavy momentum, partial participation, bidirectional compression, and proximal gradient. The paper establishes the convergence results for the six variants and conducts experiments on several small datasets.
main_review: I appreciate the authors' efforts for analyzing EF21 for various settings and provide their convergence results as well as the experimental results. However, it is not clear to me what challenge the paper addresses and novelty the paper presents. All the six variants including stochastic gradient, variance reduction, heavy momentum, partial participation, bidirectional compression, and proximal gradient have been extensively studied in the literature. Merely combining them with EF21 and providing theoretical analyses do not seems novel to me.

EF has worse error bound than the full-precision counterpart when the full gradient is used. However, it has the same asymptotic bound with stochastic gradient. How does EF21-SGD compare to EF-SGD? Does EF21 still yield better bound when stochastic gradient is adopted?

The aforementioned question is from theoretical side. From empirical side, Figure 7 in the appendix shows that both EF-SGD and EF-SGD-HB converge faster than EF21-SGD and EF21-SGD-HB, respectively. Only the hybrid method EF21+-SGD-HB obtains higher testing accuracy. These seems to contradict the claim that EF21 is better than EF for the stochastic setting. How do we explain these findings?

Some minor comments:
1. It is clearer to split the updates in Table 2 to worker's and server's, which I think are more friendly to the readers.
2. $L_j$ in Example 2 should be $L_{ij}$? 
summary_of_the_review: This paper provides solid theoretical analysis for several EF21 variants. But the novelty is limited.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose six practical extensions of EF21, with convergence analysis and good experiment results.
main_review: The paper is well-written. The convergence analysis and experiments shows that the proposed algorithms work well in both theory and practice. 
However, I have the following concerns:
1. All the proposed algorithms are extensions of EF21, the overall modification seems minor to me, which weakens the contribution of this paper.
2. Most importantly, I hardly find the experiment results convincing due to the experiment settings. Most of the datasets and models are small and simple, which typically does not require distributed training (even being trained on CPUs), not to mention communication compression. The results on such simple and small learning problems can barely show the significance of any distributed training algorithm with communication compression. 
3. Even for the largest problems: Resnet on cifar10, is usually considered the smallest one in the distributed scenarios.  On cifar10, although the proposed algorithms shows better test accuracy than the baselines, the baselines have better training loss. Thus, it is hard to justify which algorithm is actually better. Such phenomena is also not explained in the paper.  
4. A very important baseline is missing in the experiments: SGD without communication compression, which could be compared to the proposed algorithms in the number of epochs. Without such a baseline, it is hard to justify the performance of the proposed algorithms.
summary_of_the_review: The paper is well-written, and good in theory and practice. 
However, I have some concerns in the contribution and the experiment settings.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies communication efficient methods by extending EF21 to six more practical settings including momentum, variance reduction, etc. The main results are the convergence rates under these settings. 
main_review: While the authors definitely did a lot of works, as this is a 70 page paper, the novelty of this work seems to largely depend on EF21. And the main results are obtained by combining the key results in of EF21 with existing analytical techniques such as PAGE and momentum. It is not clear from the main context what are the new analytical breakthrough introduced specifically in this work.

More experiments are needed to support the theoretical findings. In particular,

a) Comparison with other benchmarks is needed since tighter bounds in theory does not necessarily imply better empirical performance.

b) More large-scale experiments should be added. Currently, many logistic regression problems have dimension less than 300.

c) In the ResNet18 experiment, have the authors decreased the step sizes? Typically it is not hard for resnet18 to get a test accuracy more than 90%.

d) One of the goals of communication efficient methods is to make training faster. Communication rounds does not necessarily mean fast in runtime since there are also implementation overhead for (de)compression. Hence, the runtime vs accuracy is also needed in numerical results.
summary_of_the_review: More discussions are needed to clarify the theoretical novelty, and numerical results should be extended.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the extended versions of a previously proposed algorithm called EF21. The paper includes several variants of EF21 such as stochastic optimization, partial participation, variance reduction, momentum, etc. The theoretical analysis for each extension is given and experiments on real world datasets are conducted.
main_review: This paper studies extended versions of an existing algorithm called EF21, and show its convergence complexity when combined with other techniques, such as momentum, variance reduction, etc. The theoretical analysis is detailed and given for each variant. The analysis on partial participation and proximal settings are new for error-feedback type algorithms.

Overall I have two concerns:

- The paper provides convergence proof for each variant, which is good, however, it's still unclear to me what role EF21 plays on these techniques. More specifically, to me this paper seems to focus on the fundamental question: how would the convergence rate of any existing algorithm adapt if an EF21 gradient oracle is used? For instance, if we want to use both stochastic approximation and momentum (which is usually the case in practice), can we obtain a rate from your analysis without additional proof? 

- The experiments seem a little thin. The main experiments are conducted on small scale linear regression problems (where communication is not really an issue). The appendix provides additional results for Resnet18 on CIFAR10. However, only the first few epochs are shown and it's unclear what hypothesis is verified there (Resnet18 should reach 93% test accuracy on CIFAR10). 

Some other minor concerns:

- In the abstract (and also in the paper), it's claimed that EF21-BC is better than a previous result from (Tang et al., 2020). But note that in (Tang et al., 2020), stochastic gradient is used while in  EF21-BC, full gradient is still used. So it's not clear whether EF21-BC can really improve the rate if they are compared in the same setting.

- In the comparison to ChocoSGD on page 8, the authors states $G$ usually depends on dimension while $\sigma^2$ and $\Delta$ are dimension free, which seems a little off to me. As they are all bounded on the norm, the statements on their orders are unjustified.
summary_of_the_review: Please refer to the main review for the details.

I recommend the authors to update the manuscript to make these points clearer.
review_title: null

Meta-review: This paper presents several variants and extensions (including stochastic and proximal) of the error-feedback method EF21 and provides convergence rates for each of them and shows that they improve upon previous state of the arts. Despite the much broadened application scenarios and SOTA  in convergence rates/complexity, the main and common concern from the reviewers is the novelty of the paper beyond the original EF21 work. There are also concerns on the empirical evaluations that do not fully support the theoretical promises. I agree with the reviewers and regrettably have to recommend rejection for ICLR.
Decision: Reject