Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the problem of minimizing the objective, defined as a  finite sum of smooth and possibly non-convex functions in a Federated learning setting.
This paper aims to tackle the problem of expensive communications that appeared in the distributed scenario between one central server and multiple nodes\workers.
In particular, this work considers unidirectional and bidirectional communication compression as the approach to tackle the problem of communication bottleneck.
Looking into details authors establish the following list of contributions:

1) They establish convergence lower bounds for distributed algorithms with communication compression in the stochastic non-convex regime. This lower bound is applicable to any algorithm performing unidirectional or bidirectional compression and using unbiased or contractive compressors. They clearly compare the established lower bounds and convergence rates of the existing methods.

2) They propose a novel, nearly optimal algorithm with compression called NEOLITHIC that provably matches the established lower bound. Moreover, NEOLITHIC can adopt either unidirectional or bidirectional compression and is compatible with both unbiased and contractive compressors. 

3) In particular, the convergence result of NEOLITHIC shows that algorithms using biased contractive compressors bidirectionally can theoretically converge as fast as those with unbiased compressors used unidirectionally.

4) In addition, they provided a set of numerical experiments comparing their novel method with existing baselines.

strengths_and_weaknesses: Strengths:

1) The paper is very well written and easily read; the main claims are outlined. The paper adequately mentions related works, including other papers establishing lower bounds. In addition, it clearly explains 
their relationship to this one. All notations that is being used in the theoretical claims are rigorously defined. 

2) To the best of my knowledge, this is the first work establishing lower bounds for stochastic methods involving unidirectional and bidirectional compressions in a Federated learning setting. It closes an essential gap in such a relevant area.

3) Being a solid theoretical paper, it provides an extensive amount of experiments. Firstly, they confirm that NEOLITIC has a similar convergence rate as parallel-SGD, MEM-SGD, and Double Squeeze on least squares and logistic regression problems. Secondly, On the CIFAR10 classification problem via ResNet, train loss of NEOLITHIC converges slightly better than Double Squeeze and EF21-SGD, and it is compatible with MEM-SGD. However, the Top1 accuracy metric of NEOLITHIC outperforms all considered baselines in experiments on ResNet18 and ResNet20 with 1% and 5% compression ratios.

Weaknesses:

1)
The main theoretical flaw is that the analysis of NEOLITHIC relies on a restrictive Assumption 5 (bounded dissimilarity):

$$\frac{1}{n} \sum_{i=1}^{n} \lVert \nabla f_{i}(x)-\nabla f(x) \rVert^{2} \leq b^{2}, \quad \forall x \in \mathbb R^{d}$$

One can easily come up with an example for which this assumption does not generally hold.
For example, let us consider $f_{i}(x)=x^{\top} \mathbf A_{i} x$, where $\mathbf A_{i} \in \mathbb R^{d \times d}$. Since $\nabla f_{i}(x)=\mathbf B_{i} x$, where $\mathbf B_{i}=\mathbf A_{i}+\mathbf A_{i}^{\top}$.  The bounded dissimilarity assumption (Assumption 5), which can be written in the form $\frac{1}{n} \sum_{i=1}^{n}\left\|\left(\mathbf B_{i}-\frac{1}{n} \sum_{j=1}^{n} \mathbf B_{j}\right) x\right\|^{2} \leq b^{2}$, also does not hold, unless $\mathbf B_{i}=\mathbf B_{j}$ for all $i, j$, which reduces to the identical data regime, which is of limited interest.

2) Some details on the experimental setting are missing. See Question 1) in the next section.

3) Literature review ignores several papers that are seemed to be relevant [1], [2]. It seems VR-MARINA for online problems from [1] and DASHA-MVR from [2] both satisfy Assumption 2 and have a better rate than QSGD in the stochastic regime.  See Question 2) in the next section. 

4) Table 1 contains possible typos: 
- 1) It mentions a paper on MEM-SGD that does not have a non-convex rate. Their rate is applicable to strongly convex functions. I would recommend here to mention another, more relevant work [3].  See Question 3) in the next section. 
- 2) Similar problems with CSER, Double Squeeze, and QSGD.  See corresponding Questions 4), 5) and 6) in the next section.

References:

[1] Gorbunov, Eduard, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. 2021. “MARINA: Faster Non-Convex Distributed Learning with Compression.” arXiv [cs.LG]. arXiv. http://arxiv.org/abs/2102.07845.

[2] Tyurin, Alexander, and Peter Richtárik. 2022. “DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization.” arXiv [cs.LG]. arXiv. http://arxiv.org/abs/2202.01268.

[3] Koloskova, A., Lin, T., Stich, S. U., \& Jaggi, M.. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXiv:1907.09356, 2019


questions: 1) Experiments on least squares and logistic regression:
Regarding compression properties, it is only said that the rand-1 compressor is utilized. 
- 1) Could you please clarify whether you are using scaled rank-1% in all methods? Do you use unidirectional or bidirectional compression for NEOLITHIC?
- 2) Is there any reason why you exclude EF21-SGD from the comparison?
- 3) What stepsizes did you use? Were they constant or decreasing?

2) Could you please compare rates of VR-MARINA and DAHSA with QSGD that was mentioned in Table 1?

3) Could you please clarify where did you get the following rate for MEM-SGD (mentioned in Table 1):

$\mathcal O\left(\frac{\sigma}{\sqrt{n T}}+\frac{G^{2 / 3}}{\delta^{2 / 3} T^{2 / 3}}+\frac{1}{T}\right)$

I checked the original work [4] and does not have any results on non-convex losses. In fact, it deals only with convex losses.

4) The same question about method CSER [5].
I checked the original work, and it shows (Corollary 1 on page 20) that the rate of CSER does not have a term with 1/T dependence. Could you please clarify this inconsistency with Table 1?
 
5) I checked the original paper on Double Sqeeze, and their rate is 

$\frac{1}{T} \sum_{t=0}^{T-1} \mathbb E \lVert\nabla f\left(\boldsymbol{x}_{t}\right)\rVert^{2} \lesssim \frac{\sigma}{\sqrt{n T}}+\frac{\epsilon^{\frac{2}{3}}}{T^{\frac{2}{3}}}+\frac{1}{T}$ 
where $\epsilon$ is the noise bound, such that

$ \mathbb E_{\omega} \lVert {\delta}_{t}^{(i)} \rVert \leq \frac{\epsilon}{2},  \forall t, \forall i $

$ \mathbb E_{\omega} \lVert {\delta}_{t} \rVert \leq \frac{\epsilon}{2},  \forall t$. 

However, Table 1 says that Double Squeeze has a rate 

$\mathcal O\left(\frac{1}{\sqrt{n T}}+\frac{G^{2 / 3}}{\delta^{4 / 3} T^{2 / 3}}+\frac{1}{T}\right)$

(the second term differs compared to the original work).

Could you please clarify this inconsistency?

6) Regarding QSGD, using the notation of Paper8019, Corollary 3 in [6] states the rate 

$\mathcal O\left(\frac{(1 + \omega)\sigma^2 + \omega b^2}{\sqrt{MT} } \right)$, where M is minibatch size (not a number of workers $n$). 

At the same time, Table 1 claims 

$\mathcal O\left(\frac{(1+\omega) \sigma+\omega b^{2} / \sigma}{\sqrt{n T}}\right)$.

Could you please clarify this inconsistency in the QSGD rate from Table 1 and the original result from [6]?

References:

[4] S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified sgd with memory. In Advances in Neural 445
Information Processing Systems, 2018.

[5] C. Xie, S. Zheng, O. Koyejo, I. Gupta, M. Li, and H. Lin. Cser: Communication-efficient sgd 464
with error reset. In Advances in Neural Information Processing Systems, 2020.

[6] Jiang, Peng, and Gagan Agrawal. "A linear speedup analysis of distributed deep learning with sparse and quantized communication." Advances in Neural Information Processing Systems 31 (2018).
limitations: 1) I would recommend making the y-axis in the right subfigure of Figure 1 logarithmic scale. Otherwise, it is hard to distinguish plots corresponding to different methods.

2) One more possibly relevant and missing citation is [7]. The Algorithm 3PCv3 (Appendix C.6, page 26) already employs a similar nested structure as proposed in Paper8019 by FCC.

3) I would recommend running least squares and logistic regression experiments for a longer period. It looks like the methods on the left subfigure of Figure 1 and Figure 2 were stopped quite early and did not reach the SGD-specific oscillation region.

4) Some minor notes:
- 1) (line 685): instead of Cauchy-Schwarz, one needs to refer to Young's inequality for product;
- 2) (line 693): instead of Cauchy-Schwarz, one needs to refer to Jensen's inequality

FINAL REMARKS: 

I would be happy to rate this paper an 8 for its solid theoretical contributions and reliable experiments. 

However, at this moment, I can not do so since the paper still contains several crucial issues that are needed to be clarified or fixed. 

I am ready to reconsider my current rate during rebuttals once you respond to me on Weaknesses 2-4 and Questions 1 - 6.

UPDATE: After the Authors-Reviewers discussion, I decided to increase the score since my concerns were resolved.

References:
[7] Richtárik, Peter, Igor Sokolov, Ilyas Fatkhullin, Elnur Gasanov, Zhize Li, and Eduard Gorbunov. 2022. “3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation.” arXiv [cs.LG]. arXiv. http://arxiv.org/abs/2202.00998.
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 paper is focused on the compression technique of distributed ML. It considers two well-studied types of compressors, i.e., the unbiased compressor and the contractive compressor. The paper provides lower bounds for those compression algorithms in the context of both unidirectional and bidirectional communication. Based on this theory, the authors come up with a new distributed training algorithm called NEOLITHIC. According to the experiment results, NEOLITHIC can achieve better training accuracy compared with the existing compressed algorithm.
strengths_and_weaknesses: - Strength
    - This paper takes unbiased and contractive compressors, unidirectional and bidirectional communication patterns all into a unified analysis, which can be quite helpful to better understand this field from a new perspective.
    - The theoretical analysis is solid and clear.
    - The proposed algorithm NEOLITHIC is quite creative in the sense that it involves multiple communication rounds to send a vector once.
- weakness
    - In the experiment, the authors only use contractive compressors, like random-1, top-k, but not unbiased compressors. So the effectiveness of quantization is not clear
questions: - As mentioned in the appendix, it seems that 2 is the best value for communication round R. Can you explain why?
- Assuming R=2, then NEOLITHIC has 2 times more communication overhead than other methods, therefore it only has T/2 iterations for training. But with half number of iterations, how can you guarantee the best accuracy? In other words, in order to achieve the best accuracy, do you still need to train with NEOLITHIC for the same iterations as other methods? 
- Given your theory, can you give compression guidelines for a distributed task? For example, for a given task (optimization problem), how can you decide the following: 1) which compressor can achieve the best accuracy 2) how much is the compression ratio 3) unidirectional or bidirectional?
limitations: Please refer to the weakness.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work considers smooth and non-convex distributed learning problem under communication compression schemes to reduce communication costs between the server and devices. It discusses widely adopted classes of unbiased and contractive compression operators, unidirectional (device to server) and bidirectional (device to server and server to device) communication compression schemes. The paper proposes lower bounds on the number of stochastic gradient evaluations (or communication rounds) for all these regimes and designs a method, called NEOLITHIC, that achieves those lower bounds for the mentioned regimes up to log factors.
strengths_and_weaknesses: **(1: Lower bounds).** There are 4 lower bounds discussed in the paper: two classes of compression operators (unbiased or contractive) and two types of communication reduction schemes (unidirectional or bidirectional). The first result (Theorem 1) shows the lower bound for unidirectional unbiased compression and the other three lower bounds are corollaries from Theorem 1 following standard arguments (unidirectional compression is a special case of bidirectional one and unbiased compression can be treated as a special case of contractive compression). ***However, the lower bound (3) of Theorem 1 does not seem consistent with existing upper bounds.*** As you mention in lines 64-65, algorithms with unidirectional and unbiased compressors enjoy better convergence rates. Specifically, convergence rates with unbiased compressions typically depends on $\frac{\omega}{n}$. For example, the method MARINA from [27](Gorbunov et. al. 2021 - Marina: faster non-convex distributed learning with compression) has $(1+\frac{\omega}{n})\frac{1}{T}$ rate with full gradients (i.e., $\sigma=0$). On the other hand, the lower bound (3) claims $(1+\omega)\frac{1}{T}$ rate when $\sigma=0$. In other words, the upper bound from [27] is better than the proposed lower bound (3). As the other lower bounds are special cases of (3), ***the correctness of the lower bounds are questionable.***


**(2: Upper bound).** ***The proof of the convergence rate of the proposed NEOLITHIC algorithm has an issue.*** The proof of Theorem 3 goes quite neat and clean up to equation (45). To get to the issue, consider (44) showing the following rate for the method (ignoring constants):
$$
\mathbf{E} [ || \nabla f(\hat{x}) ||^2 ] \lesssim \frac{1}{\gamma K} + \frac{\gamma \sigma^2}{n R} + \gamma^2\theta.
$$

Then, choosing the stepsize as in (45), it continues (before equation (46))
$$
\mathbf{E} [ || \nabla f(\hat{x}) ||^2 ] \lesssim \frac{1}{\gamma K} + \frac{\gamma \sigma^2}{n R} + \gamma^2\theta  {\color{red} \lesssim \frac{\sigma}{\sqrt{n R K}} + \frac{\theta^{1/3}}{K^{2/3}} + \frac{1}{K}}.
$$

***I do not think that this upper bound in red holds.*** In particular, $\frac{1}{\gamma K}$ term ($\frac{8\Delta}{\gamma(K+1)}$ exact expression) in (44) is upper bounded by $\frac{1}{K}$ (exact expression is $\frac{88L\Delta}{K+1}$) using the upper bound $\gamma \le \frac{1}{11L}$ from (45). However, since $\gamma$ is in the denominator of $\frac{1}{\gamma K}$ term, we have the ***reverse inequality***, namely $\frac{8\Delta}{\gamma(K+1)} {\color{red}\ge} \frac{88L\Delta}{K+1}$. In order to upper bound $\frac{1}{\gamma K}$ by $\frac{1}{K}$, one need to have a lower bound for $\gamma$. But, the choice (45) for $\gamma$ does not allow a lower bound, namely $\gamma\to0$ as $T\to\infty$.


Moreover, ***I do not think this issue can be fixed and the same rate of Theorem 3 be proven***. In order to minimize the sum of first two terms $\frac{1}{\gamma K} + \frac{\gamma \sigma^2}{n R}$, one needs to choose $\gamma$ such that $\frac{1}{\gamma K} = \frac{\gamma \sigma^2}{n R}$, which implies that $\gamma = \frac{1}{\sigma}\sqrt{\frac{nR}{K}}$. With this choice of $\gamma$, the first two terms recover the desired term in the rate, namely $\frac{1}{\gamma K} + \frac{\gamma \sigma^2}{n R} \lesssim \frac{\sigma}{\sqrt{nT}}$. However, the third term $\gamma^2\theta$ becomes $\frac{nR}{K\sigma^2}\frac{1}{\delta T} \lesssim \frac{n}{\sigma^2} \frac{1}{\delta^3 T^2}$, which blows up when $\sigma\approx 0$.

--------

**(3: References on Table 1).** Does the reference [32] really showed the mentioned rate, which blows up for $\sigma\approx 0$ ? MEM-SGD paper [53] seems to be on convex problems, could you point the place in [53] where the non-convex rate is mentioned ? There are some typos in the rate of DoubleSqueeze, I think the rate is $\mathcal{O}(\frac{\sigma}{\sqrt{nT}} + \frac{G^{2/3}}{\delta^{1/3}T^{2/3}} + \frac{1}{T})$.

**(4: On FCC).** I understand why FCC (with $R>1$) is introduced and used in the proof. However, FCC sends $R$ times more bits and I think this cost outweighs the exponential decay of the error shown in Lemma 2. For example, applying Top-$2$ is (slightly) better applying Top-$1$ twice (namely FCC with Top-$1$ and $R=2$). The reason is that theoretical contraction factor of Top-$2$ is smaller than of FCC with $R=2$, i.e., $1-\frac{2}{d} < (1-\frac{1}{d})^2$.

**(5: On Remark 2).** Check the MCM algorithm of (Philippenko and Dieuleveut 2021 - Preserved central model for faster bidirectional compression in distributed settings) related to bidirectional/unidirectional communication compression.

questions: Please see the comments under Strengths And Weaknesses section. The critical points are detailed comments (1) and (2).
limitations: IMO, no need.
review_title: null

Meta-review: metareview: The authors have addressed many if not most of the issues raised, as evidenced by the increase in scores. All reviewers agree that the paper is worthy of acceptance. The analysis is insightful. The authors are suggested to contextualized with other gradient quantization schemes such as Gandikota et al, 2021, or lower bounds Mayekar et al., 2020; and also to motivate the "sup over compressors" measure.
confidence: Certain
Decision: Accept