Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper unifies the two distinct compress techniques: DIANA and EF21, into a single framework. This new algorithm, which is named EF-BV, has advantages over the combined two techniques. First, EF-BV allows biased compression, which is not allowed by DIANA. Second, EF-BV introduces randomness, which improves the performance compared to EF21. EF-BV's convergence is provided.
strengths_and_weaknesses: Strengths
+ The new framework allows more compression techniques than previous algorithms.
+ The convergence results improve the existing one for EF21. 

Weakness
- Removing the biasedness for DIANA has been done in recent work: Zhang, J., You, K., & Xie, L. (2021). Innovation compression for communication-efficient distributed optimization with linear convergence. _arXiv preprint arXiv:2105.06697_. This result is for decentralized optimization, which is more difficult than the centralized one considered in this paper. 
- EF-BV is only compared with EF21 for the biased compression. It would be interesting to see the comparison with DIANA as well.  
- Even the benefit of EF-BV over EF21 is not too much in the numerical experiment. 
questions: + The data in the distributed nodes are homogeneous because they are split after the random shuffle. It would be interesting to see the results for heterogeneous as well.  
limitations: + The result is only for functions satisfying the PL or KL conditions. Though these conditions are weaker than strongly convex, many problems do not satisfy these conditions.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work addresses the problem of compressing the information exchanged between the workers and the parameter-server for distributed optimization. There have been several works in the recent literature that consider this, and subsequently propose various compression mechanisms (eg. top-K, rand-K, quantization, etc.) to reduce the communication demand for various iterative algorithms. 

In this work, firstly, the authors propose a slightly different perspective towards the characterization of such compressors. Existing works characterize a compressor $C(\cdot)$ using the *expected compression error* defined as $\mathbb{E}\lVert C(x) - x \rVert^2$, where $x \in \mathbb{R}^d$ is the compressor input and $d$ is the dimension. Consequently, the *expected compression error* is upper bounded in different ways, depending on whether the compressor is *unbiased* or *biased but contractive*. In this work, the authors propose an alternative and finer characterization of any compressor by decomposing the *expected compression error* into two terms: The **bias** of the compressor, and the **variance** of the compressor, as follows: 

$\mathbb{E}\lVert C(x) - x \rVert^2 = \lVert \mathbb{E}[C(x)] - x \rVert^2+ \mathbb{E}[\lVert C(x) - \mathbb{E}[C(x)] \rVert^2]$,

where the first and second terms on the R.H.S. are the **bias** and **variance** respectively. Consequently, they propose a new class of compressors, $C(\eta, \omega)$, where $\eta$ characterizes the bias, whereas $\omega$ characterizes the variance of the compressor. They show that for appropriate values of $\eta$ and $\omega$, the class $C(\eta, \omega)$ boils down to known classes of compressors, such as *unbiased compressors* or *biased contractive compressors*, implying that $C(\eta, \omega)$ is a more general characterization of compressors.

Following this, they propose the notion of **average relative variance** that characterizes the variance when compressed outputs from different workers are averaged at the parameter server. Furthermore, they also show that the bias and variance of any compressor $C(\cdot) \in C(\eta, \omega)$ can be traded-off by appropriately scaling the output of $C(\cdot)$, i.e. using $\lambda C(\cdot)$ instead of $C(\cdot)$, for some $\lambda \in (0,1]$. They subsequently show that with an appropriate choice of the scaling $\lambda$, the *scaled compressor*, $\lambda C$ can be made contractive with minimal bias (which is desirable).

After this, the authors use this alternative characterization to propose a unified framework to generalize two existing works: **DIANA** *(Mishchenko et al.)* and **EF21** *(Richtarik et al.)*. DIANA studies the utility of unbiased compressors for distributed optimization. At every iteration, DIANA maintains a control variate **h** and predicts the (approximate) gradient from the control variate by doing a first-order predictive coding from compressed gradient differences. To do this prediction, it utilizes a parameter $\lambda$ that controls the variance of the descent direction -- this is also referred to as **Variance Reduction**. On the other hand, EF21 studies biased contractive compressors, and shows that the idea of predictive first-order coding of DIANA can also be extended to mitigate the bias of contractive compressors, as long as the control variates converges to a point, implying that the sequence being compressed goes to 0. EF21 shows that compressing gradient differences (or, first-order predictive coding) implicitly does error-feedback to ensure convergence. However, it does not explicitly do anything to control the variance of the descent steps.

In the context of both of these works, EF-BV (short for **Error-Feedback with Bias-Variance Decomposition**) uses the *bias-variance decomposition* of the class $C(\eta, \omega)$ of compressors, that uses appropriate scaling to do both -- $\rm (i)$ Updating the control variate from compressed gradient difference, and $\rm (ii)$ Obtaining the descent direction from the control variate. To do $\rm (i)$, the scaling is chosen so that the individual compression error at each worker is small, whereas to do to $\rm (ii)$, the scaling is chosen so that the error in the (globally averaged) descent direction at the parameter server is small (this is where the characterization of **average relative variance** comes into picture). To do $\rm (i)$ and $\rm (ii)$, the optimal scaling makes use of the bias-variance decomposition parameters $\eta$ and $\omega$. EF-BV does separate scaling for both, allowing the algorithm designer a finer control on the compression error.

Finally, the authors show how this approach subsumes DIANA and EF-21, while giving analytic convergence results. They prove linear convergence for objective functions that satisfy the Kurdyka-Lojasiewicz (KL) condition, which is a generalization of Polyak-Lojasiewicz (PL) condition for regularized objective functions. To do this, they choose appropriate values of the scaling parameters for $\rm (i)$ and $\rm (ii)$ as mentioned above. Subsequently, they also show how their approach has new implications for DIANA and EF-21.




strengths_and_weaknesses: **Originality**: The work is mostly original, although it builds heavily on the works of Mishchenko et al. (DIANA) and Richtarik et al. (EF21). The authors have placed their work appropriately in the context of both these works and also discussed implications of their proposed framework for these existing works. The idea of characterizing estimators using the bias-variance decomposition is a common trick in Estimation & Detection Theory and Signal Processing. However, their application in the context of distributed optimization and its implications in tuning hyper-parameters as done in this work is non-trivial.

**Quality**: The quality of this paper is good. The authors have put in appreciable effort in placing their work in the context of existing works and spent a considerable portion of the paper discussing prior works and how this work improves on top of them. The bibliography is mostly adequate -- however they have missed some recent relevant references that I am aware of and have mentioned in pts. 5-(a), 5-(b), and 5-(c) of **Questions** in the next section of the review. 

**Clarity**: For a major portion of the paper, the clarity is good and everything is well-explained. It is well-placed in the context of two of the most related works -- DIANA and EF21, and heavily builds on top of them. However, there were some places that confused me a little when I was reading the paper. Some of them might have gotten clear later in the paper (or over multiple reads, i.e. I had to read a couple of paragraphs multiple times to grasp its significance). I have mentioned them as follows:

1. In line 91, the authors write "... DIANA with independent random compressors has a $\frac{1}{n}$ factor in the increase of iteration complexity due to the use of compression. That is, when n is very large, as is typically the case in practice, the iteration complexity does not suffer from the use of compression. EF21 does not have this property: its convergence rate does not depend on the number n of workers." -- It is not clear how DIANA and EF21 are being compared here. The authors say that in both of them, the iteration complexity does not suffer from increasing number of workers (n) -- why the use of "however" then? Are the authors saying -- DIANA performs better if there are more workers, i.e. as 'n' increases, whereas EF21 does not? If that is the case, perhaps this paragraph needs some rephrasing.

2.   In lines 101-106, the authors make some claims regarding the desiderata of a distributed optimization algorithm. under communication constraints. A suggestion -- The authors should explicitly specify how EF-BV addresses them by reverting back to these points later in the paper after EF-BV is introduced.

**Significance**: The contributions of this work are significant. Specifically, I imagine the bias-variance characterization of compressors to have an impact on guiding the design of distributed algorithms for other settings, beyond EF-BV such as fully decentralized or peer-to-peer settings or federated learning with local averaging. In particular, the bias-variance can be traded-off differently beyond just a simple scaling as done in this work.
questions: The paper is well-written. However, I have some questions and suggestions and I would be grateful if the authors address them. I would be happy to change my rating if these concerns are adequately addressed:

1. The authors propose a general class of compressors $C(\eta, \omega)$, and mention in line 103: "... It deals with unbiased compressors, biased contractive compressors, and possibly even more ..." When I read this line, "possibly even more" made me wonder if it's really that obvious? Does the class $C(\eta, \omega)$ actually include compressors that are not obtained from a simple re-scaling of existing compressors in $\mathbb{B}(\alpha)$ or $\mathbb{U}(\omega)$? The authors do mention **mix-(k,k')** and **comp-(k,k')** -- however, they also note that similar compression errors can be obtained for appropriately designed **top-K** or **rand-K** compressors too. Is it not clear why one would prefer using **mix-(k,k')** or **comp-(k,k')** over these. In other words, the answer of the following question is not obvious to me, "Are there compressors in the new proposed class $C(\eta, \omega)$ that perform better than existing compressors in any sense?" A possible answer to this question might be: Even if the total compression error is the same, does the distinction of bias and variance for these compressors enable EF-BV to achieve a better convergence rate than with simply **top-(k + k')** or **scaled rand-(k + k')**? If what I mention here holds true, the authors should explicitly discuss this somewhere in the paper. Another possible answer to this question might be the concatenated use of compression and quantization operators that provide a different way of trading-off the bias and variance (some relevant references are mentioned in pts. 5-(b) and 5-(c) below).

2. The authors define the **relative average variance** in order to characterize the variance of the compressed outputs averaged at the parameter server. But they make no mention of the **relative average bias** -- is it because for independent and identical compressors at the workers, global averaging at the parameter server makes no difference to the bias? If that is the case, I would request the authors to explicitly mention it somewhere (perhaps a footnote). If average variance is considered, it is only natural to discuss about the average bias, since a primary hinging idea of this work is the bias-variance decomposition of the compressors.

3. The authors should reference the proofs for Propositions 4 and 5 in Appendices. A.1 and A.2, for the bias and variance of **mix-(k,k')** and **comp-(k,k')** to relevant sections App. D and App. E.

4. Since the authors emphasize that the **average relative variance** can be *much smaller* than the individual variances of compressors at the workers due to large number of workers (n), they are requested to add an explicit discussion regarding how the communication / iteration complexity of EF-BV varies with the number of workers (n). Is the improvement only because of appearance of $\omega_{av}$ in place of $\omega$ or are there other expressions too through which "n" affects the convergence rate?

5. The authors have missed several relevant references:

      (a) The authors claim in line 508 that they *"propose"* **comp-(k,k')**: However, a concatenated application of top-k and rand-k has already been studied in the following: ***Leighton Pate Barnes, Huseyin A. Inan, Berivan Isik, Ayfer Ozgur, "rTop-k: A Statistical Estimation Approach to Distributed SGD", https://arxiv.org/abs/2005.10761***.

      (b) More recent works using error-feedback wherein the convergence rate (at least for smooth and strongly convex functions) go beyond just *linear convergence* to *linear convergence with rates approaching uncompressed gradient descent*. In particular, ***Chung-Yi Lin, Victoria Kostina, Babak Hassibi, "Differentially Quantized Gradient Methods", http://128.84.4.18/abs/2002.02508*** studies quantization methods, and uses error feedback to ensure that gradients are *always evaluated* on the unquantized trajectory. Another work: ***Rajarshi Saha, Mert Pilanci, Andrea J. Goldsmith, "Democratic Source Coding: An Optimal Fixed-Length Quantization Scheme for Distributed Optimization Under Communication Constraints", https://arxiv.org/abs/2103.07578*** builds on top of this strategy to achieve dimension independent linear convergence rates close to the unquantized linear convergence rates.

      (c) Some other recent relevant works on quantization for distributed optimization: ***Venkata Gandikota, Daniel Kane, Raj Kumar Maity, Arya Mazumdar, "vqSGD: Vector Quantized Stochastic Gradient Descent", https://arxiv.org/abs/1911.07971*** and ***Prathamesh Mayekar, Himanshu Tyagi, "RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization", https://arxiv.org/abs/1908.08200*** -- It is important to mention them because quantization is inevitable in the system implementation of any distributed optimization algorithm. So, the bias-variance tradeoffs for concatenated application of various compression and quantization strategies (in order to show that they lie in $C(\eta, \omega)$) is relevant to further justify and substantiate the importance of the new general class of compressors $C(\eta, \omega)$.

limitations: The work does not have any major limitations or potential negative impact. Some minor suggestions for clarification/improvement have been mentioned in the previous sections **Questions** and **Limitations** of the review.

One thing that I would appreciate if the authors cleared it up for me, "How extensively does the framework proposed in this paper require the independence of the compressors across different workers?" I understand it is not necessary as the authors mention *m-nice sampling* -- however, even for this scheme, the set $\Omega$ of participating workers is selected uniformly at random which simplifies the analysis. Do the authors have any comments on if $\omega_{av}$ is a sufficient way to characterize the average relative variance, and how to derive expressions for $\omega_{av}$ in settings where the compressors across different workers are different? For example, different number of bits used to quantize the updates of each worker? In other words, "Is $\omega_{av}$ still much smaller than $\omega$ in such under a worst-case scenario where the individual compressors at workers are heterogeneous?" *Clarification -- This is not a major limitation of the work, just a suggestion to consider since it is a more practical scenario.* The authors should add a brief discussion on it because communication compression is a relevant aspect of federated learning and the assumptions of i.i.d. compressors or i.i.d. client selection rarely hold in such settings. Discussing this will perhaps broadens the impact of the paper.

Another suggestion I would have for the authors is to have some numerical experiments in the main body of the paper. An application-oriented theoretical research like this work is better appreciated with substantive numerical experiments, especially since the analyses solely can often not be tight. I understand the page limitations, but just a suggestion to put the experiments in the main body of the paper instead of the supplementary, in case the work is accepted and they get an additional page.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper introduced a new communication-efficient distributed training method called EF-BV, which can be treated as a combination of previous method EF21 and DIANA.  The paper gives its linear convergence analysis under certain  conditions in the main part and experiments on relatively small dataset is provided in the appendix. This paper is well written  and easy to follow.
strengths_and_weaknesses: Strengths: This paper proposed EF-BV which includes unbiased and biased compressors as its particular cases. The linear convergence analyses are detailed and technically sound. Assumptions underlying the proposed method are simpler compared to previous methods.

Weaknesses: 

1.The main part can be more concise (especially for the introduction part)and including empirical results.

2.Given the new introduced hyper-parameters, it is still not clear whether this new proposed method is empirically useful. How to choose  hyper-parameters in a more practical training setting?

3.The empirical evaluations can not well supported their theoretical analysis. As the authors claim running experiments with 24 A100 GPUs, all methods should be compared in a relatively large scaled training task. Only small linear regression experiment results are reported, where communication is not really an issue.


questions: See Weaknesses.
limitations: The paper discusses a new variant on a technique in distributed training. As far as I’m concerned, there is no serious issue or limitation that would impact society.
review_title: null

Meta-review: metareview: It is strongly suggested by the reviewers that the authors explicitly mention the limitations in their paper -- essentially everything that came out of the discussion period, and not exaggerate the results. It has been noted that the advantage of EF BV over existing EF21 scheme is marginal. Further, authors seem to be oblivious of some relevant works on gradient quantization. However, the generalization framework of error-feedback is an interesting contribution and the community will be benefited from this knowledge.
confidence: Less certain
Decision: Accept