Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new EF mechanism to solve nonconvex distributed optimization problem. The new proposed algorithm has the following advantages：1）Theoretical analysis relies on standard assumptions only as compared to others assumptions used in previous works, and leads to better an more meaningful rates. In specific, the convergence rate is improved from O(1/T^{2/3}) to O(1/T). 2) This paper provides the first linear convergence result for an error feedback method not relying on unbiased compressors. The successful results relies on the proposed recursive Markov compressor. Experimental results are provided to verify their theoretical observations.
main_review: This paper is well-written, and the idea is well-presented. As mentioned in this paper, the core idea of the paper is to use the propose recursive Markov compressor. In the theoretically sides, the recursive Markov compressor actually reduces the gradient approximation error, and thus provides better theoretically  results. This idea may share the same spirit of the stochastic variance reduction method in classical nonconvex optimization that reducing the approximation error by  using the previous gradient.  Although I do not go through the proof in details, I believe the proposed method works in theory. Correct me if I am wrong.

The drawback of the proposed method is about  practical usage. First, the nonconvex distributed optimization setting used in this paper is simple Synchronous SGD with distributed data.  Synchronous setting is time-consuming, and not that popular in practice. 
The more interesting setting should give to the asynchronous setting.  It will be interesting to extend this idea to asynchronous setting.  

Overall, I think the authors in this paper propose a interesting idea by using recursive  trick to solve the  nonconvex distributed optimization problem. In specific, the convergence rate is improved from O(1/T^{2/3}) to O(1/T) ). Moreover, This paper provides the first linear convergence result for an error feedback method not relying on unbiased compressors.  Therefore, I tend to accept this paper at this point for its theoretical contribution.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a new simple method for error feedback (or error compensation) for enhancing distributed compressed gradient descent-based (CGD) algorithms. The paper is well written, and theoretical and experimental results are convincing.  Some minor clarifications on the methods and related works could improve the understanding of this work. 
main_review: Strengths: 
- The paper is well written, reads easily, and most central ideas are communicated clearly. 
- Theoretical and empirical results showcase good performance gains.
- Assumptions underlying the proposed method are simpler compared to competing alternatives. 

Weaknesses:
- Some parts of the paper could benefit from further clarification: 
1. Why is $\Psi$ used as a metric for Polyak-Lojasiewicz functions? 
1. Do Figs. 1, 2, and the experiments in the appendix indicate both uplink (from workers to server) and downlink (from server to workers) communication cost?

-  There is some related work on quantizing gradient differences or innovations for federated learning, referenced below. How is this work different from the referenced ones? 

  - K. Mishchenko, E. Gorbunov, M. Takác, and P. Richtárik,“Distributed learning with compressed gradient differ-ences,”arXiv preprint:1901.09269, Jan 2019.

  - S. Magnússon, H. Shokri-Ghadikolaei and N. Li, "On Maintaining Linear Convergence of Distributed Learning and Optimization Under Limited Communication," in IEEE Transactions on Signal Processing, vol. 68, pp. 6101-6116, 2020, doi: 10.1109/TSP.2020.3031073.

  - J. Sun, T. Chen, G. B. Giannakis, Q. Yang and Z. Yang, "Lazily Aggregated Quantized Gradient Innovation for Communication-Efficient Federated Learning," in IEEE Transactions on Pattern Analysis and Machine Intelligence, doi: 10.1109/TPAMI.2020.3033286.


Other comments: 
1. In line 24 of the abstract, there is a word missing in “can a large impact”
1. In line 198 “If we new” should be “If we knew”.

limitations_and_societal_impact: This is mainly theoretical work. The Societal impact depends on how the proposed method is applied to solve real problems.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the Error Feedback (EF) technique in distributed optimization. The paper proposes a new version called EF21 and claims this is theoretically and practically better. A new scheme for EF compression named Markov compressor is proposed. The writing quality is great and the paper is easy to follow. However, some of the statements are flawed which substantially compromise the quality of this paper.
main_review: 1. For starters, one of the main contributions of EF21 is to converge at a rate of $1/T$ instead of $1/T^{2/3}$. Here the author makes a mistake in line 133, saying Koloskova et al. [2020, Theorem 4.1] assumes a bound on the full gradient on worker i. However, the actual assumption in that paper was a bound on the *stochastic* gradient on worker i. These two are notably different as the latter incorporates the sampling noise. If the sample complexity is not considered (which seems to be the case of EF21), it's not surprising that a $1/T$ rate is achieved (this is like saying GD improves upon SGD). In fact, if we remove the sampling noise in Koloskova et al. [2020, Theorem 4.1], a $1/T$ rate is straightforward to obtain. The paper claims in the abstract EF21 "beats" the previous bound of $1/T^{2/3}$, which is confusing. Also Koloskova et al. [2020] works in the decentralized case, which is more challenging than the setting in this paper.

2. Could you provide a data-parallel setting where we need communication compression but no sampling? I cannot think of any since communication overhead is usually observed in deep learning tasks and sampling is a must rather than an option. Having said that, the application of EF21 is very limited. The authors provide empirical results on deep learning tasks in the appendix, but mini-batching is used there, which is not aligned with the theory or logistic regression task. Also the data heterogeneity issue is confusing: In data center training where we are able to shuffle the dataset, we can usually reduce the intra-worker variance. Heterogeneous data usually takes place in the federated learning, where the execution of EF21 shown in the paper clearly does not cover.

3. Based on 1 and 2, the main improvement of Markov compressor upon EF is data heterogeneity where $||\nabla f_i||$ can be large when the algorithm converges. However, the only case the Markov compressor can address this seems to be in non-stochastic case. If we use stochastic gradient in the Markov compressor, the error bound does not approach zero either. How EF21 handles this issue remains unclear. 

4. The authors conduct different experiments  but the results are not convincing. First, # Gbits/n is used as X-axis for all figures. However, for compression algorithms the convergence speed with respect to iterations or time are also important since when communication is reduced, the compression can become a new overhead. If the paper claims EF21 is practically better, other X-axis should be provided. Second, some of the plots for baselines are omitted for no reason, which is serious. Specifically, in the Resnet18 on CIFAR-10 experiment, EF and EF21 seems to perform similar under 128X, however only EF21 is shown under 512X while EF at 512X is not shown. Note that validation performance is not informative here, since the design of EF21 does not consider generalization.

Clarification on my review after reading the author response
===
While I appreciate the author answering my questions, but it appears some of my concerns were misunderstood. Specifically:

**On the problem with improved rates**

I did not state anywhere in my review that $G=0$, as author claimed. Let me rephrase: this is the problem with the baseline comparison. Take Koloskova et al. [2020] as example (other baselines such as Tang et al. [2020] has similar issue), in their Theorem 4.1, the convergence bound is shown as
$O\left(\frac{\bar{\sigma}}{\sqrt{T}} + \frac{G^{2/3}}{T^{2/3}} + \frac{1}{T}\right)$, where $\bar{\sigma}^2$ and $G$ are assumed to be the bound on the variance and magnitude of the *stochastic* gradients, respectively. Now, since EF21's rate is shown in non-stochastic case, for comparison, the authors convert the baseline bound as follows: drop the first term (which makes sense since $\bar{\sigma}=0$); and keep the second term. That's where my confusion comes from, as $G$ is clearly correlated with the stochastic gradient in their analysis, so how do you justify the removal of term $\frac{1}{T^{2/3}}$ in EF21 is due to EF21 being better algorithm/analysis, but not because the fact that two settings are different so that the conversion of baseline results is loosen? This happens because the authors converted a result from a more general setting to a special case, which could implicitly worsen the baseline result. In fact, there is no obvious way to detach the stochastic noise from $\frac{G^{2/3}}{T^{2/3}}$ term without reproving the baselines in the non-stochastic case, so I don't fully understand how is it an improved rate.

To make this even clearer, consider this example (not relevant to the paper, just for illustration): suppose we prove algorithm A having rate $O(1/T)$ on smooth functions while algorithm B having rate $O(\rho^T)$ on smooth and strongly convex functions. Clearly, algorithm A is analyzed in a more general setting (analogous to Koloskova et al. [2020]). Can we say B is better than A by directly converting these bound in any way? Apparently not. In fact, the only way to make conclusion on rate comparison is to reprove A or B in the other setting.

(**In response to author's follow-up question on why Gower et al (2019) can do the conversion correctly**): I thank the authors for bringing up this paper as it is a perfect example for illustrating the problem. In a nutshell, you can convert a result from a general case to a special case by setting zero to variables, but not in every case. It depends on how the baseline result is shown. Gower et al (2019) does an analysis for SGD, take their Theorem 3.1 as example, they show the convergence rate by $\mathbb{E}||x^k-x^*||^2 \leq (1-\gamma\mu)^k\mathbb{E}||x^0-x^*||^2 + 2\gamma\sigma^2/\mu$ in their Equation (10). Now this result can be converted to GD with valid conversion since the term relates to stochastic sampling is the second one, and they can easily convert by setting $\sigma=0$. However, in this paper the conversion is problematic (I acknowledge setting $\sigma=0$ is correct in my review, it's the $G$ term that has problem) because you cannot detach the effect of stochastic gradient from $G$. Put it another way, if the baseline result looks like $O(\sigma/\sqrt{T}+{1}/{T^{2/3}} + 1/T)$, then your conversion would be correct since now only the first term relates to the sampling and you can easily convert the result by setting $\sigma=0$ but that's not the case here.

**On the problem with application**

In my original review, I raised the question of naming an application setting where we need communication compression but no sampling, to which EF21 can be applicable. The author states in their response that one application of EF21 is federated learning, which seems a little off to me. As we know, federated learning usually involves a large number of nodes, so a typical algorithm (such as FedAvg, SCAFFOLD) requires client sampling. However, in the multiple node version of EF21, it requires all the nodes to participate in each iteration and need to be synchronized at the end of each iteration. So if I understand it correctly, EF21 can be used in federated learning only under the following two conditions:

(1) The number of nodes cannot be too large so that global synchronization is possible and negligible.

(2) The number of data samples on each node (client) cannot be too large so that full gradient computation is not an overhead. 

I don't really understand how this is applicable, please correct me if anything in my statement is incorrect.

**On the problem of extension to stochastic case**

Maybe I did not state it well in the original review. My claim is that stochastic gradient actually breaks the intuition of EF21 which makes it not easy to extend. Here's why: the intuition of EF21 is illustrated in line 271: $\mathbb{E}||\mathcal{M}(v^t)-v^t||^2\rightarrow 0$, while this is true for full gradient because as the algorithm converges, the magnitude of full gradient will approach zero. However, it's not clear to me why it still holds for stochastic gradient, especially the case where all the data samples have different local minimas (not quite the heterogeneity as mentioned in the paper). Specifically, could you explain why such quantity still approaches zero if $v^t$ contains sampling noise? 

The authors state in their response that error feedback is orthogonal to stochastic approximation, and the latter should be handled by other variance reduction algorithms like SVRG, I'm confused. Because the baseline algorithms like DoubleSqueeze, Q-local-Sparse clearly works with stochastic approximation without involving variance reduction parts.

The author pointed out a stochastic analysis is included in the appendix I, however, no rate is shown in that analysis and that analysis ends with "It is straightforward...to establish complexity results for our stochastic variant of EF21 ." If the authors believe the statement of my original review "$O(1/T)$ rate is straightforward to obtain in baseline" is unjustified because "such a rate is not included in their paper", I politely ask the authors to apply the same standard to the paper, and avoid using such statement to justify your results. Because, the rate of EF21+ too, is not shown in the paper or appendix. As pointed out by authors in their response: "Simply claiming this does not make it true". Please correct me if I'm wrong.

**Summary**

I believe all my concerns are specific on the technical issues. The idea of Markov compressor is interesting, so I've decided to raise my score slightly to give some more credit. However, at this point, I still don't think this paper meets the acceptance bar of NeurIPS as the issues I raised are serious and closely related to the main contribution of this paper, unless the authors can prove I misunderstood them all.




limitations_and_societal_impact: The paper discusses a new variant on a technique in distributed training. There is, from my perspective, no serious issue or limitation that would impact society.
review_title: null

Meta-review: The paper's strength and appeal is in proposing a simple modification to the Error Feedback mechanism that has both theoretical and empirical benefits.  The idea and mechanism proposed in the paper could have significant implications in important problems include distributed optimization and in optimization under various constraints (communication restricted, memory restricted, privacy restricted, etc).  The proposed EF21 mechanism is also nicely and clearly motivated and presented.  For these reason, I think the paper can make for an interesting oral presentation. 

The ACs and myself were disappointed by the the authors choosing to restrict the scope of the paper to presenting the core idea only, without much applications and extensions.  It is much more useful to the community and makes for a much stronger paper to include these in the paper, so as to justify importance of the core idea.  While the paper is certainly "acceptable" without them, in order to be a milestone paper and a foundational reference, these further applications and extensions are appropriate.  This is certainly much preferred to splitting the contribution into multiple papers each with 1 MPU (minimum publishable unit) worth of content.  In a sense the recommendation for an oral presentation is on credit, and based on the expectation that this will urge the authors to make the paper more comprehensive and complete.

I should also say that I found the comment regarding reviewer scores at a workshop entirely inappropriate.  While I appreciate the author's frustration with scores they disagree with, the author response is meant to point out factual issues with the reviews and address reviewer questions, and the authors also have the option of commenting on review quality.  But the paper should speak for it's own merit, and including recommendation letters for the paper, let alone vague and anonymous scores without justification, is not part of the reviewing process.  Furthermore, the criteria in a broad conference such as NeurIPS and in a technical workshop are different.  In particular, for a broad conference, it would be appropriate to include a better discussion and examples of applications and extensions so as to help show the significance of the results to the reviewers, as representatives of the general audience.
Decision: Accept (Oral)