Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new error-feedback based gradient compression algorithm for distributed machine learning. The key difference with prior work is that the compression is bidirectional i.e. data sent by both the workers and the server is compressed unlike most prior works which only focus on compressing data sent by the workers. The authors show that a novel application of error feedback at both the server and the workers enables them to improve over the communication complexity of several prior methods and converge at the same rate as gradient descent despite sending significantly lesser data in each direction at each communication round.
strength_and_weaknesses: Strengths:

1. To the best of my understanding, this is a novel application of error feedback for server-to-worker compression in distributed machine learning. The fact that it can be used to augment any unbiased worker-to-server compression method also broadens its scope.

2. The theoretical and empirical results presented show improvements over prior work.

Weaknesses:

1. My main concern with the paper is that the overall gain with this approach is not entirely clear. As the authors themselves acknowledge, the received wisdom in this space is that downloading data is faster/cheaper than uploading it which reduces the need for compressing data being sent by the server. Moreover, the proposed approach appears to require the workers to a) maintain local state/memory and b) use an unbiased compressor. While the requirement of maintaining local state is a bit restrictive, that is not a big issue since there are scenarios where such state can be maintained. However, as far as I know, if a worker maintains state, it can use a biased compressor with error feedback to improve significantly over unbiased compressors. As the authors don't compare against any such method, it is unclear if their approach leads to any significant improvement over these approaches, especially when the need for server-side compression may not be that acute to begin with.

2. A second minor concern is the limited empirical evaluation. The authors only consider logistic regression on a few datasets. I would like to see evaluation on some other machine learning models to see if the gains are as apparent in other models as well. Also please clarify why results with the baseline approaches (DIANA, MCM, DASHA) are not presented for all datasets (some have DIANA as the baseline, some have DASHA, some have MCM).
clarity,_quality,_novelty_and_reproducibility: The overall idea is novel and clearly presented but the writing is very heavy on notation. I would suggest adding a table of symbols and their meanings in the appendix to help readers keep track. It might also be beneficial to provide a brief primer on gradient compression with error-feedback to enable to paper to reach a broader audience. Specifically, the steps in Algorithm 1 may not be self-explantaory to readers unfamiliar with the intuition behind error feedback.
summary_of_the_review: The paper proposes a new application of error feedback to bidirectional gradient compression. The application is novel and the theoretical results show improvement over prior work. However the evaluation is somewhat limited and the overall gains of the approach for different machine learning models and as compared to methods using error feedback and biased gradient compression at workers aren't clear yet.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper suggests a new compression method based on the recent EF21 scheme and then used this compression method in the bidirectional distributed SGD method. Authors provide convergence rates for strongly convex, convex, and non-convex objectives. The theory is verified using logistic regression experiments.

strength_and_weaknesses: Strength:

I think the most interesting part of this paper is the proposed compression technique and the section “Unified SGD analysis framework with EF21-P mechanism” which is placed in appendix. 

Weakness:

While there is theoretical value in bidirectional distributed SGD, I  do not think there is much practical gain in using bidirectional compression as there is a number of references that claim that Broadcasting one message to n users is much cheaper than n poin-to-point communication. Therefore, my main criticism is the motivation for bidirectional compression.

Another question is how do you compare the additional storage cost of distributed algorithm?

Additionally, I do not think the Assumption on $\hat{L}$ is standard. Can author provide any justification for that?

clarity,_quality,_novelty_and_reproducibility: Paper is easy to follow.

summary_of_the_review: Please see the comments above!
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The authors propose EF21-P in eq(3), which is an interesting and novel variant of error feedback. Theoretical analysis is comprehensive and solid. Empirical results on logistic regression task show the benefits of EF21-P.
strength_and_weaknesses: Strength:
1. The proposed EF21-P is an interesting way to look at error feedback. The compression error seem to be modeled as the difference between $x$ and $w$, so the optimization objective seem to be make $x$ and $w$ more coherent, which is novel.
2. The theoretical results are comprehensive, including both the convex and non-convex cases, and the combination with DIANA/DCGD to achieve the best results.

Weaknesses:
1. The experimental settings are small-scale. #features is 20k and #samples is 72k. A single worker should be sufficient to train logistic regression on this dataset.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and well-organized, and the method is new.
Codes are provided, so it should not be difficult to reproduce the experimental results.

[update] during discussion, reviewers find that EF=EF21-P, which is also acknowledged by the authors and severely damages the novelty. Therefore I decided to lower all my scores.
summary_of_the_review: The author proposes a novel variant of error feedback, and it seems very interesting compared with most of the existing error feedback variants. The theoretical analysis looks comprehensive and solid. The only concern is how this method works in practice with larger-scale datasets and more complicated models.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper proposes a simple error-feedback mechanism called EF21-P, and some variants such as EF21-P + DCGD and EF21-P + DIANA. This paper focuses on the theoretical analysis of EF21-P. The empirical shows good performance.
strength_and_weaknesses: Strength:
1. This paper focuses on the theoretical analysis of EF21-P, which provides thorough theories for both convex and non-convex cases.
2. The empirical shows good performance.

Weakness:
1. For the empirical analysis, the model (logistic regression) and the datasets (libsvm datasets and cifar-10) are both too small and simple for distributed training. Typically, for such simple and small tasks, a single computer is enough for fast training.
2. I believe that the main algorithm proposed in this paper, EF21-P, is actually not novel and is equivalent to the original error feedback. See my discussion below for more details. However, I'm not 100% sure about this. So please make clarification and correct me if I'm wrong about this.
clarity,_quality,_novelty_and_reproducibility: I believe that the main algorithm proposed in this paper, EF21-P, is actually not novel and is equivalent to the original error feedback (or EF, or error compensation).
Here is some simple derivation:

First, recall that the formula in Equation (3) for EF21-P is (I ignore the step "t" for the compressor):

$x^{t+1} = x^t - \gamma \nabla f(w^t)$ 

$w^{t+1} = w^t + C(x^{t+1} - w^t)$

$w^0 = x^0$

Now, we add an auxiliary variable $a^t$, which is actually the message before compression, defined as follows:

$a^t $
$= x^{t+1} - w^t $
$= x^{t+1} - x^t + x^t - w^t $
$ = - \gamma \nabla f(w^t) + x^t - w^t $
$= - \gamma \nabla f(w^t) + x^t - w^{t-1} + w^{t-1} - w^t $
$= - \gamma \nabla f(w^t) + a^{t-1} + w^{t-1} - w^t $
$= - \gamma \nabla f(w^t) + a^{t-1} - C(x^t - w^{t-1}) $
$= - \gamma \nabla f(w^t) + a^{t-1} - C(a^{t-1}) $

$a^0 = x^{1} - w^0 = x^{1} - x^0 =  - \gamma \nabla f(w^0) = - \gamma \nabla f(x^0)$

By using $a^t$, we can totally get rid of $x^t$ and re-write the algorithm as follows:

$w^{t+1} = w^t + C(a^t)$

$a^t = - \gamma \nabla f(w^t) + a^{t-1} - C(a^{t-1}) $

Now, if you are familiar with error feedback, you would find that the algorithm above is exactly the original error feedback, and the term $a^{t-1} - C(a^{t-1})$ is exactly the "residual error" in error feedback (please refer to the EF-SignSGD paper: http://proceedings.mlr.press/v97/karimireddy19a/karimireddy19a.pdf).

Given that my derivations above are correct, i.e., EF21-P is equivalent to EF, then we would have even more issues in this paper:
1. EF21-P + DCGD is just EF-SGD using quantization as the compressor, which is not novel
2. EF21-P + DIANA is just EF + DIANA. There is already an algorithm called EC-SGD-DIANA (error compensation + DIANA, and error compensation is the same as error feedback) proposed in the following paper:
Gorbunov, Eduard, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. "Linearly converging error compensated SGD." NeurIPS 2020. (https://proceedings.neurips.cc//paper/2020/file/ef9280fbc5317f17d480e4d4f61b3751-Paper.pdf)
I'm not exactly sure whether EF + DIANA is equivalent to EC-SGD-DIANA, or maybe EF + DIANA is just another variant of DIANA that combines error feedback with DIANA. So I would recommend the authors to make a comparison and give some clarification.
3. The experiment results actually show that EF-SGD ( or EF21-P + DCGD) works better than DIANA and EC-SGD-DIANA (maybe EF21-P + DIANA), while DIANA and its variants are supposed to be newer algorithms with state-of-the-art performance in practice. So, the experiment results in this paper seem to contradict the results from the previous works. Now I wonder whether DIANA is really better than simple EF-SGD.
summary_of_the_review: Although this paper may provide some new insights in the theoretical analysis of distributed SGD with error feedback, the experiments are too simple, and more importantly there are some issues in the novelty of EF21-P.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents a simple error-feedback mechanism, referred to as EF21-P, to address errors introduced by a contractive compressor. EF21-P operates in the primal space of models, and is used as a key building block for communication-efficient distributed optimization methods. The authors provide theoretical bounds on communication complexity for convex and nonconvex problems, and the results are corroborated by experiments.

Summarized Strengths:
-  Unified SGD analysis framework with EF21-P mechanism 
- Comprehensive theoretical results including convex and non-convex cases
- Results easily reproducible as codes are provided
- Theoretical and empirical results show improvements over prior work
- Can be used to augment any unbiased worker-to-server compression method

Summarized Weaknesses:
- Main algorithm proposed in paper is not novel and is equivalent to original error feedback (EF) method. The authors allege that they were not aware of that during the submission of the paper, yet at the same time explain how they are extremely well versed in the EF scheme. I personally give benefit of a doubt to the authors, but at the very least the discussion during the rebuttal phase would demand that the paper is significantly rewritten to address this (arguably major) issue.
- Overall gain is unclear due to need for workers to maintain local state and use an unbiased compressor
- Limited empirical evaluation on only logistic regression with few datasets
- Little practical gain from bidirectional compression 
- Some nonstandard assumptions (eg on \hat{L})

There was extensive engagement with the most critical of the reviewers, during which the authors realized that one of the claims (eg novelty of proposes EF21-P scheme) is not present, as it is equivalent with another method (EF). This of course can happen, and is not a major sign of concern, especially in the presence of novelty at other parts of the paper. However, given the present way that the results, and contributions are presented, the authors would have to significantly overhaul their manuscript to a point that would significantly deviate from the current version, that would require a complete and separate review phase.

The authors should take thorough steps to address the significant concerns of novelty raised by the reviewers, and if wish to resubmit the current paper to a future venue explain in detail how EF21-P is not a novel algorithm, and the main points of novelty are the theoretical results, and experimental findings, that many of the reviewers are in agreement that are novel.

justification_for_why_not_higher_score: The paper received significant criticisms regarding novelty, which required a big overhaul of the presentation of current results and algorithms, especially in comparison to current literature.
Decision: Reject