Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper develops a decentralized algorithm for solving variational inequalities with a certain structure motivated by machine learning applications. The key innovation is the utilization of compression (i.e., quantization) for communicating loss functions and their aggregates between a set of devices and a centralized server node, towards solving the inequalities using extragradient methods. The paper provides theoretical convergence guarantees that account for the quantization errors, and report the trade-off between the communication complexity    and the convergence.  
main_review: The authors study a well motivated problem. The algorithm developed has a solid theoretical framework from an optimization theory viewpoint. The convergence results seem non-trivial and thorough. However, some concerns exist.

- A critical question that remains unanswered - from the viewpoint of theory - is whether there exist compressors that indeed lead to improved communication complexity over the uncompressed methods. In particular, the authors report that it is needed that $\beta q^{(1+q/M)} < 1$ is required. However, for the randK compressor where $\beta = (M+1)/Mq$ - assuming that the same compressor everywhere -  this relation is not satisfied. To complete the arguments purported in the paper, it seems necessary to provide this analysis for the randK compressor, or some other compressor that performs well. 

- The experimental section appears somewhat weak, I would have liked to see more.. Although the paper is motivated via GANs and adversarial training, results are only provided for the latter. Perhaps more importantly, the influence of various parameters (compressors, compression ratio, tau) on the performance is not studied. In effect, the experiments do not appear to be a sufficiently thorough validation of the theory. 

- The presentation can be improved by presenting and explaining the idea behind the basic centralized solution in the appendix, or before presenting the solution with the decentralized, compressed version.

- From the communication complextity reported below Corollary 1, it is surprising that the compression-factor of the devices influences the total number of bits much more than the compression factor at the  server, essentially the communication complexity appears to be 2^{(1+q1)*log(q2)} bits, where q1,q2 respectively represent the variances of the quantizers of the devices and the servers respectively. It is also not transparent that this disparity in behaviour exists looking at Theorem 1, where the dependence on q1,q2 appears more symmetric (at least in an order sense). Please explain.
 

summary_of_the_review: Overall, non-trivial theoretical analysis has been conducted to study the effect of compression on convergence. However, some concerns exist in terms of both theoretical justification need to be addressed. The experimental analysis could have been more thorough, though I consider this a relatively minor weakness given the extent of theoretical contribution in terms of convergence analyses.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper studies the communication needed in order for a group of distributed players to collectively solve a variational inequality problem. The paper provides two algorithms MASHA1, MASHA2 to do this that solve both the deterministic and stochastic cases.  They also provide experimental results on applying their techniques to Bilinear saddle point problem and adversarial training of transformers. 


main_review: Main techniques used and the good points about the paper 
Both the algorithms basically extend the extragradient/extrastep method of solving variational inequalities to the distributed setting. So in particular they specify how this method can be modified to fit in a distributed regime and prove the convergence and give upper bounds on the total communication. 

Main drawbacks and technical issues with the paper 
I think this is an interesting modification of the prior known work but I do not believe that this is a significant research contribution and is an incremental adaptation of the extragradient/extrastep method. Also the convergence or upper bounds on communication while cumbersome are not non trivial and straightforward adaptations of the classical centralized setting proofs. I think a worthwhile theoretical contribution would be to prove lower bounds on how much communication overhead would be needed to solve variational inequalities in the distributed setting.  Or at the bare minimum have some kind of restriction assumptions on the algorithm and then prove lower bounds that could explain why this adaptation of the extragradient method is near optimal or non trivial.   

Presentation of the paper. 
I think it would help the reader to first understand the classical solution to the variational inequality problem before jumping into the distributed solution. Section 4 is really abrupt and it would help to ease the reader into the distributed solution. Otherwise the paper looks okay.
summary_of_the_review: The paper studies the communication needed in order for a group of distributed players to collectively solve a variational inequality problem. In particular they provide two algorithms MASHA1, MASHA2 to do this that solve both the deterministic and stochastic cases. 
They also provide experimental results on applying their techniques to Bilinear saddle point problem and adversarial training of transformers. 
Both the algorithms basically extend the extragradient/extrastep method of solving variational inequalities to the distributed setting. I think this is an interesting modification of the prior known work but I do not believe that this is a significant research contribution and is an incremental adaptation of the extragradient/extrastep method.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the compression methods for solving variational inequalities (or saddle point problems in particular) in the distributed setting. Both unbiased (i.e., MASHA1) and contractive (i.e., MASHA2) compression methods have been proposed. Theoretical analysis is provided to show that the proposed method can converge. 

main_review: This paper proposes compression methods for solving variational inequalities. It is good to cover various settings such as unbiased vs. contractive, deterministic vs. stochastic. Detailed convergence analysis is also provided. However, I also have the following concerns. 

1. For practical problems such as GAN or adversarial training, the objective of min-max optimization is nonconvex-nonconcave, which results in a non-monotonic operator in variational inequalities. This more practical assumption has been considered in existing work with sound theoretical analysis (see reference [1] as below). The authors are encouraged to extend the analysis to the more practical nonconvex-nonconcave regime. 

2. In the paragraph right above Figure 2, the authors mentioned that “the learning curves on Figure 1(upper) follow a predictable pattern, with more extreme compression techniques demonstrating slower per-iteration convergence”. First, is Figure 1(upper) a typo? Should it be Figure 2(upper). Second, the learning curves in Figure 2(upper) are overlapping with each other (except for pure 8-bit in the upper-left figure). I am not sure how the authors get the observation that  “more extreme compression techniques demonstrating slower per-iteration convergence”. Besides, some discussion is needed to compare the compression ratio between 8-bit quantization and power compression with rank r=8. This is because power compression with rank r would decompose the dense matrix of size m\*n into two matrices of size 
m\*r and n\*r. The exact compression ratio would depend on the values of m and n. 

3. In Figure 2(lower), it’s customary to also list average scores across different tasks in GLUE benchmark. It’s easier to compare different methods by checking their corresponding average scores. 

4. In Figure 1, it looks like that extra-step method also diverges (i.e., accuracy decreases as training goes). Since the extra-step method is specific for solving saddle point problems, it’s counter-intuitive when it diverges. 

5. It looks like there is no conclusion section at the end of this paper.

Reference:   
[1] Diakonikolas, Jelena, Constantinos Daskalakis, and Michael Jordan. "Efficient methods for structured nonconvex-nonconcave min-max optimization." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.


summary_of_the_review: I have been working on related areas and have read this paper carefully.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors have considered general distributed variational inequalities problems and proposed two methods using unbiased and contractive compressors.They have evaluated their methods on saddle point problems including large-scale adversarial training of transformers. 


main_review: The main weakness of this paper is regarding the theoretical results. 

- The authors consider a general notion of unbiased compression schemes in (1). Parameter $q$ is in general dimension-dependent (Alistarh 2017). The authors establish the bounds by treating $q$ as a constant term. However, this parameter can be very large in overparameterized settings, which motivate this paper as stated in the abstract. When $q$ is large, $C_q$ in Theorem 1 will be large too, which leads to very small learning rate. Similar issue happens when $\tau$ is close to one. As authors mentioned $\tau$ should be close to one to control communication costs. When $\tau$ is close to one, the learning rate becomes very small, which does not lead to interesting results in terms of convergence. A similar issue happens in Corollaries 1 and 2.

- I think the discussion after Corollary 1 is not accurate. In particular, the condition under which Algorithm 1 outperforms the standard uncompressed extragradient method is restrictive. It is more likely that the standard uncompressed extragradient method outperforms Algorithm 1 in terms of communication complexity. 

-  It will be nice if the authors provide concrete examples of interesting VI problems beyond saddle point problems in machine learning. It is also important to show that Assumptions 1 and 2 hold for such problems. Indeed, the experiments are also based on saddle point problems. 

- It is unclear how all nodes have access to $F(w^{k+1})$ at the beginning of the iteration $k+1$ while only some nodes with $b_k=1$ compute $F_m(w^{k+1})$?

- In Table 1, the authors mentioned that ``(Deng & Mahdavi 2021) does not have strong theory since it cannot improve on non-compressed methods without assuming data homogeneity.'' I my view, a similar criticism applies to this work too. 

- "we introduce the notion of expected density, defined ..." This is not new. A similar notion based on the expected number of required bits has been proposed in the literature e.g., QSGD, NUQSGD, signSGD ...

- The paper is not well-written. There are many typos that require a substantial revision. Some examples include: abstract, Section 1.4, footnotes in Table 1, first paragraph of Section 4.1, first paragraph of Section 5.2, ...

Minor comment: 
- Section 4.2: "We now establish convergence of MASHA1 in both regimes": please specify "both regimes". 

- Some terms such as $\tau$ and $b_k$ are defined only in Algorithm 1. It will be easier for readers if those terms are defined in the main text too.  
summary_of_the_review: The paper has some interesting aspects for example large-scale adversarial training of transformers. However, given the issues regarding theoretical results, connection with related work, and clarify and presentation of the paper, I recommend rejection.
review_title: null

Meta-review: In this paper, the authors consider two algorithms for solving (strongly) monotone variational inequalities with compressed communication guarantees, MASHA1 and MASHA2. MASHA1 is a variant of a recent algorithm proposed by Alacaoglu and Malitsky, while MASHA2 is a variant of MASHA1 that relies on contractive compressors (by contrast, MASHA1 only involves unbiased compressors). The authors then show that
- MASHA1 converges at a linear rate (in terms of distance to a solution squared), and at a $1/k$ rate when taking its ergodic averge (in terms of the standard VI gap function).
- MASHA2 converges at a linear rate (in terms of distance to a solution squared).

Even though the paper's premise is interesting, the reviewers raised several concerns which were only partially addressed by the authors' rebuttal. One such concern is that the improvement over existing methods is a multiplicative factor of the order of $\mathcal{O}(\sqrt{1/q + 1/M})$ in terms of communication complexity (number of transmitted bits) for the RandK compressor, which was not deemed sufficiently substantive in a VI setting (relative to e.g., wall-clock time, which is not discussed).

After the discussion with the reviewers during the rebuttal phase, the paper was not championed and it was decided to make a borderline "reject" recommendation. At the same time, I would strongly urge the authors to resubmit a properly revised version of their paper at the next opportunity (describing in more detail the innovations from the template method of Alacaoglu and Malitsky, as well as including a more comprehensive cost-benefit discussion of the stated improvements for the RandK/TopK compressors).
Decision: Reject