Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors propose communication-compressed methods for solving a particular class of problems that they refer to as "variational inequalities". The authors prevent theoretical guarantees for their method, claim that a naive compressed-gradient based approach will fail in general, and present experiments demonstrating benefit to their technique over a naive compressed-gradient based.
strengths_and_weaknesses: ### Major caveat to review
- I have not had time to go deeply through the mathematical content of this paper, therefore my review will not be able to address this aspect
- I apologise that my review thus addresses superficial aspects of the paper.

### Strengths
- the authors address a potentially practically useful problem, and produce both theoretical and experimental results on this topic.

### Weaknesses
- style violations. The authors greatly reduce the font-size of their figure captions, which as far as I am aware breaks the style rules, allowing them to fit more content into the 9 pages. This may sound a bit harsh, but I think that this is unfair to other authors who follow the rules and I would advocate for rejecting the paper for this reason.
- the paper has not been properly proof-read. Basic aspects of the technical introduction contain errors. For instance, the saddle point problem is introduced as min-min on line 158 when as far as I am aware it should be min-max. Also on line 221, the symbol q^serv is used twice instead of the proper notation.
- exposition. The exposition could be much clearer. For instance at line 154, no supporting intuition is offered about the mathematical form of the VI inequality, making it hard for an unfamiliar reader to build a working understanding of this topic.

### Overall
I want to apologise to the authors that my review is superficial. However, I am being clear about the fact that it is superficial. I want to add that I had a limited amount of time to review the work and ultimately needing to comment on things like style violations reduced the amount of time available to deal with the content.
questions: I do not have any questions for the authors
limitations: Negative societal impact is not an issue here.
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: In this work the authors develop distributed communication-efficient methods for solving i)variational inequalities and ii)saddle point problems. The proposed algorithms (MASHA1 and MASHA2) utilize bidirectionally existing compression operators ( i) unbiased compression operator and ii) contractive compression operator) in order to reduce their communication cost in strongly monotone, monotone and non-monotone regimes. Convergence results are derived and presented for MASHA1 & 2 in all three regimes and numerical experiments showcase the merits suggested by the theory as well as the superior performance of the proposed methods compare to Extra Gradient. Stochastic variants (VR-MASHA1 and VR-MASHA2) with variance reduction are studied as well as connections to Federated Learning.  
strengths_and_weaknesses: Strengths: This paper studies an interesting problem. Reducing the communication cost for distributed variational inequalities and saddle point problems is relevant in the area of machine learning. The paper provides convergence results for the proposed methods in many different regimes (strongly monotone, monotone and non-monotone operator regimes, deterministic, stochastic etc.). The theoretical results are also supported by illustrative experiments. 

Weaknesses: In my perspective the paper has two main weaknesses.
1. Firstly, the writing of the paper requires a major revision. There are many typos, syntactic errors and sentences that do not make sense throughout the main body and the appendix. As a result many important points of the paper are not clearly conveyed such as the description of Algorithm 1. Further, the appendix needs also to be rewritten more carefully to make it easier to follow. Below I state a few examples that could be revised :  

The sentence in lines 39-42 needs to be rephrased so that it has a clear meaning.
line 53 : In 'implementations it often advantageous' there is an 'is' missing.
line 56: Remove 'the' from 'lead to the comparable test error'.
line 60: Remove 'Since' from the beginning of the sentence.
line 79: Replace 'due to' with 'since'.
line 87: Remove ''provably
lines 130-131: Rephrase 'Moreover, devices can not only have a bad connection, in which one needs to compress data heavily, they can simply disconnect from the learning process'.
lines 140-143: Need rephrasing.
lines 209-221: The paragraph explaining MASHA1 needs to be rewritten. There are many typos and syntactic mistakes which make it hard to decipher the description of the algorithm.
line 228 : Replace 'listing' with 'description'.
line 230: 'an' is missing in 'Let us find optimal way to choose it'
line 247 : Rephrase 'Then once can note that MASHA1 O(􏰖1/M + 1/β · L/μ) better than the uncompressed extragradient method. We think that the factor O(􏰖1/M + 1/β · L/μ) is unimprovable and optimal – see Section A.'

2. While the theoretical results are extensive the originality and technical contribution appears to be limited. Similar results have been obtained with the same compression operators in optimization problems and certain techniques are repetitive.
questions: The paper could certainly be improved substantially by more carefully revising the writing and the points mentioned in the 'Weaknesses section'.  Specifically the technical contributions and the description of algorithm 1 need to be more carefully rewritten. 

Also as mentioned above the following parts need revising:
The sentence in lines 39-42 needs to be rephrased so that it has a clear meaning.
line 53 : In 'implementations it often advantageous' there is an 'is' missing.
line 56: Remove 'the' from 'lead to the comparable test error'.
line 60: Remove 'Since' from the beginning of the sentence.
line 79: Replace 'due to' with 'since'.
line 87: Remove ''provably
lines 130-131: Rephrase 'Moreover, devices can not only have a bad connection, in which one needs to compress data heavily, they can simply disconnect from the learning process'.
lines 140-143: Need rephrasing.
lines 209-221: The paragraph explaining MASHA1 needs to be rewritten. There are many typos and syntactic mistakes which make it hard to decipher the description of the algorithm.
line 228 : Replace 'listing' with 'description'.
line 230: 'an' is missing in 'Let us find optimal way to choose it'
line 247 : Rephrase 'Then once can note that MASHA1 O(􏰖1/M + 1/β · L/μ) better than the uncompressed extragradient method. We think that the factor O(􏰖1/M + 1/β · L/μ) is unimprovable and optimal – see Section A.'
limitations: The authors addressed the limitations of the paper.
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: The paper proposes approaches to add compression to the communication steps involved in solving variational inequalities in a distributed fashion. The authors propose approaches for both unbiased and contractive compression along with theoretical analysis and two experiments to validate their approaches.
strengths_and_weaknesses: Strengths:

1. This appears to be the first work to address the issue of compressed communication in distributed methods for solving variaitional inequalities. Moreover it proposes and analyzes separate schemes for both unbiased and contractive compressors.

2. Results on the synthetic experiment of solving a bilinear saddle point problem clearly show that the proposed approaches require significantly fewer iterations than baselines for convergence.

Weaknesses:

1. The experiment on Adversarial Training of Transformers is not clear at all. Specifically it is unclear if any of the MASHA approaches have been implemented for this since the plots appear to contain only the baselines. Moreover  the size of the plots, and the font size of the text in them is extremely small and thus it is very hard to tell what is going on in them.

2. It is not clear if MASHA1 will always reduce the communication cost. Corollary 1 appears to show that MASHA1 will have fewer iterations than the uncompressed case, but each round of iteration can involve upto 2 rounds (each way) of communication between the server and the clients. As the authors state in line 235, the average communication cost per round is ($1/\beta + 1 - \tau$) times the communication cost in the uncompressed case. It is not clearly stated if $1/\beta + 1 - \tau$ is smaller or larger than 1. If it is larger, then the communication cost would be higher than that of the uncompressed case from what I can tell.

2. The paper appears to be incomplete with no conclusion sections and no discussion of limitations/future work.
questions: 1. Please address points 1 and 2 under Weaknesses above.

2. Please include a conclusion section in the paper.

3. The notation for local operators $F_m$ is used in Section 2.3 before it has been defined. Please define notation before using it.
limitations: N/A
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: In this paper, the authors consider solving distributed variational inequalities (VIs) with compressed communication. For unbiased compressors, they use the variance reduction (VR) technique to control the variance; while for contractive compressors, they further incorporate the error compensation mechanism to handle the bias. They prove convergence rates for the cases where the operator is strongly-monotone, monotone, or non-monotone with Minty's condition, and demonstrate the speedup compared with the uncompressed counterparts. They further show how to extend their methods to the stochastic setting and the federated learning setting with partial participation.
strengths_and_weaknesses: ## Strengths

- This is the first work to study communication compression techniques in the setting of distributed VIs. Given the increasing importance of saddle point problems and the necessity of designing communication-efficient algorithms, I think this work should be of interest to the community.
- The presentation is mostly clear and easy to follow.
- The results are comprehensive and seem technically sound.

## Weaknesses

- I don't see any serious problem, but as a mostly theoretical paper I feel its algorithmic novelty is somehow limited. For instance, the idea of combining VR techniques and gradient compression seems not new; it has appeared in [1]. Also, the algorithm MASHA1 as well as its analysis resemble those in [2], with the stochastic oracle replaced by the compressed operator.

[1] Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed sgd can be accelerated. arXiv preprint arXiv:2010.00091, 2020.

[2] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. arXiv preprint arXiv:2102.08352, 2021.
questions: - Could you please articulate the connections between the proposed methods and the existing ones? In particular, both MASHA1 and MASHA2 seem similar to the FBF method with variance reduction in [2]. Also, the proof starting at line 786 in the Appendix also seems to be related to Lemma 2.4 in the mentioned paper.  
- Minor issues: 
    - The sentence from 39-42 is grammatically incorrect. 
    - Line 53: "it often" -> "it is often"
    - Line 106: "second norm" -> "Euclidean norm"?
    - The fourth line from last in Algorithm 1: "$w^{k+1}=z^k$" -> "$w^{k+1}=z^{k+1}$"
    - Line 226: It should be $\mathcal{O}(1/\epsilon)$ instead of $\mathcal{O}(1/\epsilon^2)$?
    - The reference number in the appendix seems to be off by one. 
limitations: Yes, the authors have mentioned the limitations in the paper.
review_title: null

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: This paper designs and analyzes compression algorithms for solving three families of distributed VI/SPP problems. 
strengths_and_weaknesses: The strengths of the work include extensive theoretical and experimental results highlighting that its designed algorithms outperform existing algorithms for solving VI/SPP. In particular, the results for strongly-monotone, monotone and non-monotone problems are provided.  

I don't see any major weaknesses from this paper. However, I would like to point out to typo errors in the paper: 

- Line 117-118: "But often ..." It is a run-on sentence. 
- Line 125: "fro details" -> "for details"
- Line 241: "in str-monotone case" -> "in strongly-monotone case"
questions: N/A 
limitations: N/A
review_title: null

Meta-review: metareview: Dear Authors,

We had a long discussion about this paper. Overall, the reviews are positive. Several reviewers raised their scores after the rebuttal phase, and they found the response by the authors satisfactory. 

However, there were some concerns about the novelty of the paper that I summarize here:

This paper combines some standard techniques and ideas from decentralized optimization and minimax optimization to obtain the presented results. Hence, the algorithmic novelty of the paper is limited. Perhaps the major contribution of the paper is in the vector that they decide to quantize, but still, the main idea of the paper is very similar to the single-loop variance reduction techniques that were first proposed in stochastic optimization and later used for distributed optimization. The main theoretical challenge that the authors had to face was combining quantization with the Extra Gradient method as highlighted in the first paragraphs of section 4.1. Indeed, similar quantization ideas have been extensively studied in the distributed optimization literature and thus the algorithmic novelty seems to be very limited. Similarly, excluding the aforementioned challenge (Extra Gradient + compression) the derivation of the theoretical results appears to be tedious but based on standard techniques. 

Considering the above points, the AC and one of the reviewers found the paper below the bar as its novelty is limited. However, four reviewers voted in favor of accepting this paper, as they believe the technical novelty of the paper and its proof techniques are significant enough. 

I respect the majority vote and hence recommend this paper to be accepted. 
confidence: Certain
Decision: Accept