Venue: NeurIPS 2022 Conference

Reviews:

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: In this paper, the authors propose a decentralized nonconvex optimization algorithm with communication compression. With the gradient tracking technique, the convergence rate is improved over the existing ones.
strengths_and_weaknesses: Strengths:
1. In this paper, the authors propose a decentralized nonconvex optimization algorithm with communication compression. 
2. With the gradient tracking technique, the convergence rate is improved over the existing ones.
3. Overall, the writing is smooth, although there are some typos.

Weaknesses: 
1. There is another very relevant work that also considers decentralized optimization with communication compression:
Y. Liao, Z. Li, K. Huang, and S. Pu. Compressed gradient tracking methods for decentralized optimization with linear convergence. arXiv preprint arXiv:2103.13748, 2021.
Please clarify the differences (for example, strongly convex and nonconvex).
2. The comparison in Table 1 is unfair. The other algorithms are stochastic but BEER is deterministic.
3. The numerical experiments could be strengthened if the authors consider training a deeper neural network, and show the evolution of accuracy with respect to runtime.

questions: 1. There is another very relevant work that also considers decentralized optimization with communication compression:
Y. Liao, Z. Li, K. Huang, and S. Pu. Compressed gradient tracking methods for decentralized optimization with linear convergence. arXiv preprint arXiv:2103.13748, 2021.
Please clarify the differences (for example, strongly convex and nonconvex).
2. The comparison in Table 1 is unfair. The other algorithms are stochastic but BEER is deterministic.

limitations: N/A.
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 paper presents a new decentralized nonconvex optimization algorithm, termed BEER, with communication compression to reduce the number of communication rounds in networked systems. Specifically, the authors introduced two auxiliary variables to track the parameter and global gradient updates. They theoretically showed that the convergence rate was improved over the state-of-the-art and matched the uncompressed counterpart. Additionally, they also analyzed the convergence when the objective satisfies the PL condition. They claimed that the strong bounded gradient assumption can be relaxed using the proposed algorithm. To validate BEER, the authors used two simple benchmark datasets and two simple models to show that the proposed algorithm is comparable to the uncompressed algorithm and better than the best available compressed decentralized algorithm.
strengths_and_weaknesses: I think overall the investigated topic in this paper is quite interesting, as communication overhead is a critical issue that needs to be resolved in order to achieve scalability in multi-agent systems. This paper is well written and easy to follow. While I still have a few concerns here that the authors should address to make the current paper more technically solid and sound.

1. The algorithmic framework has to be agent-wise. Though the authors have defined the terminologies well and explain the algorithm clearly. Since the focus of this paper is a decentralized optimization algorithm, it will be clear and straightforward to understand how the parameters are updated. That way, an agent-wise algorithm is better than the current algorithmic framework.

2. The authors defined the Lyapunov function, $\Phi_t$ , to measure the convergence progress. For Theorem 1 and Theorem 2, the error bounds are actually determined by $\Phi_T$, which might be with respect to $T$. Hence, it will cancel out the $T$ in the denominator. I wonder if the authors could get something like $\Phi_0-\Phi_T\leq \Phi_0-\Phi^{*}$, which will turn the error bound being independent of $\Phi_T$. This is typically in theoretical analysis. Otherwise, the authors need to make a guarantee that $\Phi_T$ won’t be with respect to $T$ in the paper. Additionally, by inspecting Theorem 3 and Theorem 4, the authors use $\Phi_t$ as the measure. Since you have used $f$ in the previous two theorems, why didn’t you follow the same idea?

3. The experimental results are not promising. Though the theoretical analysis looks interesting and decent, to me, the experimental results are not that convincing, due to the only usage of very simple datasets and models. Given the results by baseline methods, BEER actually performs comparably. I think the authors should be presenting more quantitatively to tell how much of gain BEER can achieve. The current discussion is too qualitative. It should be noted that these experiments were conducted by only using simple datasets and models. Then how about with more complicated datasets, such as CIFAR 10, CIFAR 100, ImageNet, and models, such as VGG and ResNet? Moreover, the authors have mentioned different other decentralized optimization algorithms with communication compression in the paper? Then why not compare BEER with them? The authors should present more experimental results to validate the proposed algorithm.

4. Regarding the coefficients for $c_1, c_2, c_3, c_4$ in the Lyapunov function, the authors mentioned in the paper that they depend on different theorems, can the authors give specific values at least for one scenario?

5. Minor comment: The authors have used $\alpha$ as the compression constant. Then for the nonconvex regularization, they should have used another different character.

***********************************************
Overall, the responses from the authors clarified my confusion and addressed most of my concerns. While I think this work delivers some useful insights to the community in theory, which is not a reason to just have simple evaluations for validating the proposed method. The authors have claimed that they will have additional experimental results, which can add values to the paper. So I raised my score. However, the authors should take all comments from other reviewers into account to make the draft more technically solid and sound.
questions: 1. Is $\Phi_T$ with respect to $T$? Can the authors show it is a constant in the error bound in both Theorem 1 and Theorem 2?
2. How is the performance of the proposed algorithm when it is applied to larger benchmark datasets and more complex models?
limitations: I don't think the authors have adequately addressed the limitations of their proposed approach. It would be better and great to see some discussion regarding this aspect, particularly in terms of the perspective of applications and the comparison with other existing methods.
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 paper proposes a decentralized algorithm with communication compression named BEER. In the deterministic non-convex setting, BEER improves the convergence rate of existing algorithms to O(1/T), which is a state-of-the-art result. The author also establish the convergence rate of BEER in the stochastic setting or with PL conditions. Numerical experiments have been conducted to validate the results.
strengths_and_weaknesses: ### Strength

- BEER works under weaker assumptions. It removes the assumption on bounded gradients and gradient dissimilarity;


- In the deterministic setting, BEER achieves the state-of-the art convergence rate in terms of T.

### Weakness

- The convergence rate in the stochastic and non-convex setting is not satisfactory; it is worse than existing algorithms such as SQuARM-SGD

- The dependence on the network topology is not satisfactory; it is worse than existing state-of-the-art algorithms

In general, the reviewer values the strengths more and hence rates the paper positively. 
questions: While the convergence rate established in the deterministic scenario is SOTA, the rate for stochastic settings is not. 

1. According to the established rate, BEER cannot converge to the stationary solution even with decaying learning rate. In contrast, other decentralized compression algorithms such as CHOCO-SGD and SQuARM-SGD can converge to the stationary solution with decaying rate. It is a major drawback;

2. The authors argue that by utilizing large enough mini-batches, BEER can converge to the stationary solution. In this setting, its convergence rate is still worse than CHOCO-SGD and SQuARM-SGD if they also utilize large enough mini-batches.

3. Another major drawback is that, under the stochastic setting, BEER does not show a linear speedup rate. In contrast, SQuARM-SGD shows a clear linear speedup term $O(\sigma^2/\sqrt{nT})$. In contrast, BEER cannot even have a diminishing term associated with $\sigma^2$. 

4. Also, even in the deterministic non-convex setting, the dependence on the network topology established in existing works (without communication compression) is far better than $O(1/\rho^3)$. For example, in the following reference, the network topology dependence of the GT algorithm is $O(1/\rho)$.

[Ref] A.  Koloskova, T. Lin, and S. Stich, An Improved Analysis of Gradient Tracking for Decentralized Machine Learning, NeruIPS 2021.

Can the authors please have a few comments on the above points. Are these drawbacks valid? Can these drawbacks be improved? If not, can the authors provide the reason or insight why these drawbacks are difficult to overcome?

limitations: Yes
review_title: null

Meta-review: metareview: The paper has been considered by two ACs--the following is the (adapted) meta-review after the discussions between the two ACs and the senior AC.

The paper focuses on designing communication-compressed algorithms for decentralized nonconvex optimization, where the clients are only allowed to communicate a small amount of quantized information with their neighbors over a predefined graph topology. With quantization, the best known achievable convergence rate for this scenario (i.e. consensus converge to a ) was O(T^{-2/3}). This paper improves this rate to O(T^(-1)) via a novel algorithm called BEER. The main idea behind BEER is to track the model estimate as well as the overall gradient through the message-passing rounds that helps to reduce the effect of the errors due to compression. It is noteworthy that BEEr does not need any extra assumption on the objective (e.g. bounded gradients, etc). Also, BEER is matching the rate without compression even under arbitrary data heterogeneity. Hence, the paper provides a set of interesting and notable results in the field of decentralized learning.

Overall, all the reviewers were in favor of (weakly) accepting the paper. Most of the concerns that the authors had were alleviated in the discussion phase. The main weakness that was discussed among the reviewers was the lack of thorough experimental results. However, we believe that the paper should be judged by its theoretical merits. Even though the paper's main contribution is theoretical, I strongly recommend to the authors to show thew superiority of their proposed method on practical models/settings/data compared to SOTA methods such as Seep Squeeze, CHOCO-SGD, or SQuARM-SGD (please see the reviews for more details). Such experiments would showcase the applicability of BEER in practical settings.

Finally, I would also like to point out that the idea of gradient tracking has been used in Federated learning to improve the rates (in the presence of quantized messages). E.g. see FedLin by Mitra et al (2021), or SCAFFOLD by Karimireddy et all (2020). These papers show for example that gradient tracking can help to get similar rates when the functions are strongly convex (which is analogous to the Polyak condition considered in this submission). I recommend that the authors add a discussion in the final version about the relevant to these works. 

confidence: Certain
Decision: Accept