Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper extends the theory of MARINA to support potentially correlated compressors and refines the original analysis of MARINA based on a new quantity called Hessian variance. They show their proposed compressors, random permutations, have improvements in theoretical communication complexity in the low Hessian variance regime.
main_review: ### Strength
1. The paper proposes some new techniques (e.g. AB inequality and input variance compressors) to relax the original assumption of independent compressors.
2. The paper proposes a new quantity called Hessian variance to refine the analysis of communication complexity.


### Concerns
1. The advantages of the new theoretical results are based on the regime Hessian variance is 0 or small. To illustrate, the paper gives some examples of Hessian variance equal 0, i.e. identical functions and linear perturbation. But these seem to be very simple cases. For more complicated models, it is not clear if and when the Hessian variance is small.
2. In the big data case ($d \leq n$), when $d \ll n$, there is no improvement.
3. In Figure 1, PermK does not outperform other algorithms, although the paper claims the theoretical improvement of $\sqrt{n}$. In Figure 2, the difference between PermK and TopK is very small, which does not show the theoretical improvements.
summary_of_the_review: Although not perfect and build upon existing works, the paper proposes some new techniques and quantity to refine the analysis of distributed non-convex optimization algorithm. The theoretical novelty is sufficient.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied MARINA method (proposed in a previous work) in distributed nonconvex optimization problems. With a new assumption on the Hessian variance, the paper extend the original analysis of MARINA to accomodate correlated compressor, which avoid the independent compressor setting and can lead to improvement to the communcation complexity in a case when the number of dimension is larger than that of component.
main_review: Improving communication complexity is an important topic in distributed optimization. The paper tried to extend the analysis of the SOTA algorithms in a more detailed case to refine the complexities. The paper is clearly written and easy to read.

My main concern are as follow:
1. The analysis (Theorem 4) here seems to be heavily relied on the AB inequality and correspondently Hessian variance assumption, but I am not sure whether the Hessian variance is motivated enough. Now authors verify the assumption holds on only identical functions and quadratic functions, I am not sure whether it is applicable to more general problems. 

2. For the experiments, does the autoencoder example satisfy the extra assumptions?

3. For the proof, the difference seems to lie in the Lemma 5 here and derivation above Eq (21) in MARINA paper, where AB inequality and Hessian variance work to bring some difference in the coefficients in my opinion, and the claimed difference of using correlated compressor is incorporated into the coefficient computation of AB inequality, the remaining things are similar, e.g., the Lyapunov function $\Phi$. Can the authors kindly provide more intuition on the benefits of the new analysis, with the additional assumption?  

Some minor thoughts:
1. Even though closely related to MARINA paper, but as a separate independent submission, to make it self-contained, I may suggest that at least authors can consider to add a formal description (e.g., an \algorithmic environment or the main update rule) of the algorithm into the main content (rather than mentioning it in Appendix B), I think, at least now, readers should not be required to be familiar with MARINA as they are with SGD before reading the submission.

All in all, now I view the contributions here are a little marginal, and skeptical on whether it is suitable as a separate work. I hope to have more insights from authors on the importance and practicality of the additional assumptions. Please definitely indicate here if I misunderstand any point. I will appreciate the authors to address my confusions, and definitely reconsider my decision. Thank you very much.
summary_of_the_review: The paper improves the analysis of MARINA algorithm, but the introduced new assumptions need to be further justified.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper extends the analysis to an existing algorithm called MARINA, and proposes two results: 1) Correlated compressors among the workers, and one realization called PermK; In the analysis, an inequality called AB inequality is used to study the compression variance. 2) A new metric called Hessian variance to refine the results of MARINA.
main_review: The proposition of studying correlated compressors in a distributed environment is good, but I'm a little confused on the motivation -- why is the hypothesis limited on MARINA but not on other algorithms? To me the hypothesis is fairly simple and interesting: in a distributed setting, workers follow parameter server architecture and communicate via compressed gradients, how will the correlation in the compressors affect the convergence? This should be independent to the algorithm itself. Actually, some analysis have already been done in the literature, for instance (Acharya et al., 2019)(Acharya et al., 2020), which are analyzed in more general cases. Same question for the Hessian variance part: could you elaborate why this is specific for MARINA? Understanding a newly proposed algorithm is great, but the contribution of a paper seems limited if the results only hold on one algorithm.

The idea of PermK, where unbiased sparsifier is constructed via some random state and selected coordinates are enlarged, seems to be overlapped with (Jianqiao et al., 2017). In that paper, unbiased gradient sparsification is guaranteed in a similar manner. The similar idea can also be found in (Wang et al., 2018). It's unclear to me about the novelty on this method.

The experiments are done on linear tasks, but it's unclear what hypothesis they are verifying. In the main paper, a new complexity bound on the iteration is shown, but in the experiments all the X-axis are number of bits. They only match when the same compressors are used in each run and number of bits in each case grow linearly with the iteration at the same rate.


- Reference

Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. *Gradient Sparsification for Communication-Efficient Distributed Optimization* https://arxiv.org/pdf/1710.09854.pdf

Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi. *Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction* https://arxiv.org/pdf/1812.11476.pdf

Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi. *Communication-Constrained Inference and the Role of Shared Randomness* http://proceedings.mlr.press/v97/acharya19a/acharya19a.pdf

Hongyi Wang, Scott Sievert, Zachary Charles, Shengchao Liu, Stephen Wright, Dimitris Papailiopoulos *ATOMO: Communication-efficient Learning via Atomic Sparsification* https://arxiv.org/pdf/1806.04090.pdf
summary_of_the_review: Could you take a look at my main review and address the concerns on motivation, PermK and experiments?
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper investigates a permutation based sparsification technique for distributed optimization, and prove that, under a mildly tighter condition than L-smoothness, it can achieve better communication complexity than the existing random sparsification technique. The method is largely under the larger construct of MARINA, a distributed optimization scheme by Gorbunov. A (1+d/sqrt(n)) factor improvement is shown with the permutation vs randomization technique when the Hessian variance is small, and several promising numerical results are given. 
main_review: Overall, the paper is interesting, and the analysis in the  main paper is careful and clear. The assumptions are not too outlandish, and it makes sense that sparsification should be easier when data / Hessians are more uniform. (I suspect that is what is happening in the MNIST example, for example.) The paper seems strong, but I am not familiar enough with this specific area to comment on its novelty or impact.

Weaknesses: Since the paper seems mainly to put forward the theoretical advantages of different schemes, I question if the proposed methods are better because of better proof techniques, or if they are really always like that in practice. For example, I suspect a fully correlated scheme where every worker uses the *same* sparsification (but randomly regenerated at each iteration) should achieve good performance as well. It is unclear to me, at least intuitively, why a permutation approach would be better than random sampling. (For this, a few toy examples would be illuminating.) I also think (and this is less easy to address, so it's not really factoring to my decision of the review) that the few experiments given may not be exhaustive enough to provide general conclusions as to the superiority of each method. 

Also, since the appendix is about 40 pages long, I did not have time to read it. If the authors feel there is one specific proof that they are particularly proud of, I'd be happy to take a look and give a less lukewarm review.
summary_of_the_review: See above.
review_title: null

Meta-review: The reviewers have agreed that the paper is in borderline. Although the reviewers are not really convinced about the authors’ responses, they still acknowledge that the paper is interesting and developed some new techniques for the analysis of distributed optimization. 

The following concerns are raised by the reviewers from their discussions: 

1) The paper is heavily based on existing work. 
2) The theoretical advantages are based on the regime Hessian variance is 0 or small, but it is not clear if and when the Hessian variance is small for more complicated models, which means we will not know if the theory will be helpful in practice. Although the authors provide some experimental results in the rebuttal showing that $(L_+)^2 / (L_{\pm})^2$ can be large at initial iterations, it is still not clear how long will this advantage keep during training and how much the advantage is.
3) Reviewer wjjy increased the score from 5 to 6, considering that the additional result truly suggests that the implicit setting can hold in some case at the beginning of iteration, which makes the submission a complete story for him/her now, to some extent. But if we are more strict on the evaluation, the experiment result also suggests that the implicit assumption will not hold anymore over iterations, because the ratio is approaching 1 quickly, i.e., $ L_\pm$ is about the same order as $ L_+$, so there is a mismatch between theory and practice, which even brings out the risk that the paper will fail from the beginning because Sec 4.1 will not make sense anymore.
4) On the theory side, two main contributions of this paper is relaxation on the compressors used in MARINA and a new assumption to refine the analysis. These two contributions seem rather limited if only used to analyze this specific algorithm -- it's unclear what the authors mean in practice or how they correlated to the MARINA. For example, it is still hard for us to compare or understand MARINA with another algorithm as we wouldn't know if the improvement from MARINA is due to a better design, or this additional assumption. The reviewer also finds the authors statement that "their analysis focuses on MARINA because it is SOTA" confusing. Different from NLP and vision community where standard benchmarks are usually used to evaluate new models, He/she is confused by what it means for a newly proposed optimization algorithm to be SOTA.
5) Since the paper proposes a specific algorithm named PermK, it's quite reasonable to question how it relates to some previously proposed sparsification methods with similar design such as (Jianqiao et al., 2017). However, the authors insist their main contribution is in theory, and the small-scale experiments comparing with TopK and RandK are sufficient. The reviewer disagrees about this. As communication compression is usually need in larger scales (at least beyond MNIST), and TopK/RandK are not SOTA baselines of sparsification.

The authors are expected to address them for the clarifications in the final version.
Decision: Accept (Poster)