Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyzes the hard-threshold sparsifier in distributed SGD with convergence analysis and extensive experiments. Main contributions include: 1. Provides upper bounds of the optimization errors for the hard-threshold sparsified distributed SGD, which improves from top-k compressor with linear speedup and compressor operator parameter dependence. 2. Conducts extensive experiments to demonstrate the benefits of hard-threshold sparsifier, achieving much better performance given the same average compression density (# of used coordinates / # of coordinates of DNN weights). 
main_review: 1. I am trying to understand why the proposed communication-complexity model is new, it seems to me it is an adaptive compression operator allowing different # of coordinates to be sent for each iteration. And the section 4.4 and Lemma 3 seems incorrect to me, since the optimization over B is sequential, the choice of first block will change the second block of A, so I didn’t quite follow why the proposed sparisfier is optimal for this communication-complexity model. 
2. On the confusion of total error minimization. In the paragraph starting from line 44, it seems to the authors are trying to present a new perspective that is not minimizing per iteration compression error but total compression errors, but the last sentence seems to me conveying the message of considering fixed total communication budget, which is exactly what I think other papers have discussed, how to tradeoff optimization error with total communication budgets. So there may be some confusion in this paragraph.
3. The authors provide upper bounds of optimization errors for the proposed spasifier, in strongly convex, convex, and nonconvex settings respectively. Those upper bounds improve from the results using top-k sparsifier in terms of linear speedup and compressor parameter dependence. 
4. The provided upper bounds, however, seem to me not clearly they are more communication-efficient than the top-k sparsifier, since there is no characterization of the total number of coordinates being used in theory. Ideally, if we set the threshold be very small, most coordinates will be used. In experiments, the authors provide solid results showing that the hard-threshold sparsifier does use less coordinates in total than the top-k. 
5. The total error minimization perspective seems to me more like an observation of the consequence using a hard-threshold sparsifier, it may need further arguments to show it is the reason for better performance. 
6. The paper is in general well written and very clear, the extensive experiments are helpful for the understanding of the practical benefits of the hard-threshold sparsifier. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the role of compression operators on the convergence of Distributed SGD with Error Feedback. In particular, via simple observations, the authors conclude that a hard-threshold sparsifier with a carefully tuned threshold parameter minimizes the total error appearing in the analysis because of the presence of compression. Moreover, they show empirically the connection between poor behavior of EF-SGD with Top-k compression and the severe error accumulation.

Motivated by these observations, the authors derive new convergence guarantees for EF-SGD with absolute compressors. This class of compressors covers hard-threshold sparsifier. The derived bounds show that the compression does not affect the slowest terms in the bound. Moreover, the authors derived the first complexity result in the non-convex case for EF-SGD with $\delta$-cnotraction operators without bounded gradient assumption and $n > 1$ (though, under bounded data dissimilarity). Finally, the paper contains a good empirical study of the performance of EF-SGD with the hard-threshold sparsifier. The authors also provide an insight on how to tune the threshold parameter in order to outperform EF-SGD with the Top-k operator.
main_review: ## Strengths

1. **Simple but important observations about total error minimization.** The paper provides a closer look at the convergence of EF-SGD and identifies what quantity should be minimized in order to get better results. That is, via the sequence of simple observations, authors show that a hard-thresholding sparsifier (with fine-tuned threshold parameter) is the optimal choice in terms of the total error minimization. Moreover, the authors properly explain all the details and support their theoretical observations with empirical findings (e.g., see Figures 1 and 3).

2. **Clarity and proofs.** The paper is clearly written. The proofs are easy to follow and contain only a couple of typos.

3. **New results for EF-SGD.** The authors derived new results for the convergence of EF-SGD with absolute compression for strongly convex, convex, and non-convex objectives. The slowest terms in the derived bounds have a linear speedup and are not affected by compression-dependent parameters. This is a good property since the derived bounds match the ones for SGD without compression if the target accuracy is small enough / the number of communication rounds is large enough. Moreover, the authors derived the first convergence result for EF-SGD for $\delta$-contraction operators without assuming boundedness of the gradients, but under Assumption 4, that bounds dissimilarity between local loss functions. Although the proofs substantially rely on the known techniques, the obtained results are quite good.

4. **Numerical experiments** show a connection between the behavior of EF-SGD with Top-k and hard-thresholding sparsifier and "error buildup". Therefore, these numerical results justify the insights provided in Section 4.

## Weaknesses

1. **No analysis for the arbitrary heterogeneous case for non-convex objectives (minor).** The derived bounds in the non-convex case substantially rely on Assumption 4 that bounds the dissimilarity between local loss functions. Although this is a significant limitation, previous works on EF-SGD rely on even stronger assumptions. Therefore, this is a minor drawback.

## Questions and Comments

1. **Rates for EF-SGD with $\delta$-contraction operator.** The rates shown in Remarks 5 and 7 can be significantly improved via the results from [19]. Although, in [19], Assumption 3 is not considered it can be easily cast in the general framework from [19] via the following derivation: $\frac{M}{n}\sum_{i=1}^n\|\nabla f_i(x^k)\|^2 + \sigma^2 \leq 2LM(f(x^k) - f(x^*)) + \frac{M}{n}\sum_{i=1}^n \|\nabla f_i(x^*)\|^2 + \sigma^2$. Using the results from [19] one can actually show the linear speedup even for $\delta$-contraction operators in the $\mathcal{O}(1/T)$ and $\mathcal{O}(1/\sqrt{T})$ decaying terms for $\mu > 0$ and $\mu = 0$ respectively. Therefore, the conclusion from lines 270-272 is not correct.

2. **equation after line 654:** the enumerator in the second term should be $\mu L^2(1+M/n)^2R_0 + L\kappa^2 \ln(T)$.

3. **line 247, $\nu = \gamma_t \kappa$:** It is better not to use $\kappa$ in the definition of $\nu$ because $\kappa$ usually denotes the condition number of the problem in the optimization literature.

4. **lines 283-284:** This is done for $\delta$-contraction operators in [19] and in Qian, X., Dong, H., Richtárik, P., & Zhang, T. Error Compensated Loopless SVRG for Distributed Optimization, Qian, X., Richtárik, P., & Zhang, T. (2020). Error compensated distributed SGD can be accelerated. arXiv preprint arXiv:2010.00091.

5. **Lemmas 6 and 7.** First of all, one should add that $\gamma = \min\left(\frac{1}{d}, \sqrt{\frac{r_0}{cT}}\right)$. Next, Lemma 7 can be tightened when $c$ is small, see Lemma D.3 from [19].

6. **Lemma 9.** When $c = 0$ this result is incorrect since the logarithmic factor becomes infinity. See Lemma D.2 from [19] for the correct version.

7. **Lemma 11.** It is better to cite the assumptions of the lemma in the statement (or at the beginning of the subsection).

8. **lines 623-627:** The discussion in these lines should be rewritten after applying the corrections suggested in comment 1. Moreover, one should also say that $\lambda$ can be large.

## Comment after rebuttal
I thank the authors for their response. I have read other reviews as well. Overall, my evaluation of the work remains the same. Therefore, I recommend the paper for acceptance and hope that the authors will apply all necessary corrections mentioned in the reviews.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors demonstrate that, in the context of distributed optimization problems with $n$ workers, the hard-threshold sparsifier is the optimal sparsifier for a proposed communication complexity model which where the goal is to minimize the total error for a sequence of responses. This allows the authors to compare the sum of compression errors for various algorithms and to demonstrate that while for the per-iteration $k$-element budget the Top-$k$ sparsifier is optimal, when it comes to total error the hard threshold sparsifier is better. 

The authors also compare the convergence rates of the top-$k$ sparsifier vs the hard threshold sparsifer for image classification, language modeling, and recommendation tasks. 
main_review: I find this paper interesting and vote to accept it. I think it is an interesting result but unfortunately I am not an expert in the field and so am not sure about it's significance in the context of the field. I do like the communication complexity model. 
limitations_and_societal_impact: This is a theoretical paper and has limited societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers gradient sparsification for learning in distributed setup, and advocates using a hard-threshold sparsifier combined with error-feedback mechanism. The paper shows that such algorithm is _optimal_ in a certain sense, and give several convergence guarantees for the error-feedback algorithms using absolute compressors and relative compressors. The empirical performance of HT and top-k compressors are also compared.
main_review: Post-rebuttal: Thank you for the reply. My concerns have been addressed well. Raising the score to 7.

---

__TL;DR.__ I think this paper presents several meaningful theoretical results as a contribution. However, I think some of the paper's claims are being quite oversold.

__Strengths.__ Some of the theoretical results are definitely very cool to have. I believe that the convergence results in Section 5 (Theorems 2--5) is a nice contribution, and would be of interest to the distributed learning society, especially to those who study error-feedback mechanisms. Also, the proof technique going through the perturbed iteration analysis (via Lemma 10) is quite neat. Finally, the manuscript seems to discuss the related work relatively well.

__Claims on optimality.__ I am very worried about the paper's claims about the optimality. The word "optimal" is a very bold, and should be used with a great care (in my opinion), as they could be quite misleading without delivering the assumptions and conditions it relies on. For instance, the abstract states that top-k is "communication-optimal given a per-iteration $k$-element budget." But, what exactly does the word "communication-optimal" here mean? It is very easy to understand the statement as saying that such algorithm gives the hypothesis with a smallest loss---either in expected or high-probability sense. If I understood correctly, I think the paper is pointing to lemma 2, where authors state that Top-k gives the sparsified version of the error-feedback (or actually any signal) that has the smallest squared distortion from the original gradient signal. This also relies on the assumption that the choice of sparsification does not affect the subsequent gradient signals. This discrepancy gets more significant for the claims on the optimality of hard-threshold methods, where this "independency assumption" is critical for the proof. I believe that these ill-specified claims on the (possibly vacuous notions of) optimality should either be toned down to a certain degree to help readers better understand what the paper is contributing. Also, I think presenting the optimality claims in a form of lemmata without proofs is unnatural, no matter how straightforward the proofs are. I recommend either stating the claims in plain words without a formalization, or provide the result-specific assumptions clearly in the lemma statement---so that it is self-contained---and give at least a formal proof.

__Stating the limitations.___ If I understood correctly, such hard-threshold sparsifiers may need a very high communication throughput at some epochs (mostly earlier). However, there are many setups such high peak communication rate is undesirable, due to the limited capacity of the communication channel (but when the delay is crucial). In such cases, having a constant communication rate could be beneficial. I think authors should discuss such scenarios to appropriately deliver the cases where the considered hard-threshold methods are desirable, and the cases they are not (sorry if I missed these parts).

__Clarity: Why error-feedback?__ I am not entirely sure what is the big motivation behind considering the error-feedback mechanisms for this paper. Line 51 says: "Consequently, we consider sparsification using the error-feedback mechanism, ..." but I couldn't really locate the part that necessitates considering error-feedback. Could you please further clarify?

__Clarity: $\gamma_t$.__ The quantity $\gamma_t$ appears at line 133, but I do not think this quantity is defined or introduced properly in the text.

__Clarity: Assumption 2.__ I do not think Assumption 2 is explicitly assumed in any theorem appearing in the main text. But if I am correct, it is implicitly used for every theorems that use $R_0 := \lVert x_T - x^\star \rVert$ in its bounds.

__Question: $v$-dependency__ It was unexpected to me that the convergence guarantees for the absolute compressors $C_v ( \cdot ) $ does not depend explicitly on the compression factor $v$, especially considering the fact that the guarantees for the $\delta$-contraction operators contain a term that is inversely proportional to $\delta$ (see Theorem 2 & Remark 5, for instance). Any further discussion explaining why such discrepancy happens (especially for the case $\delta \to 0, v \to \infty$) would be very nice to have; does this suggest the existence of a tighter bound for $\delta$-contraction operators under additional assumptions the size of $p_{i,t}$?

__Suggestion: Discussing $P_T$.__ While the quantity $P_T$ appears in many optimization literature, the meaning of the quantity may not be very straightforward for the readers who are relatively new to the field (like myself), especially because it gives the performance bound for $\bar{x}_T$ generated by some weights $w_t$. Giving more ideas about the quantity may help the readers a lot, including whether one can choose $w_t$ arbitrarily or not, whether it implies that we should use an averaging scheme...
limitations_and_societal_impact: I think authors should additionally mention when can such variable-communication-load methods may not useful or usable.
review_title: null

Meta-review: This paper reformulates an existing problem (how to sparsify gradients in distributed training) and proposes to minimize a new objective (the total compression error subject to communication constraint as opposed to per-iteration compression error). This change of viewpoint leads to a new algorithm (hard threshold algorithm with variable sparsity). The authors show the effectiveness of the proposed algorithm through theoretical bounds and experiments. All reviewers agree that this is a valuable contribution. Comments from previous submission to ICML are adequately addressed.
Decision: Accept (Spotlight)