Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on co-coercive variational inequalities and proposes a quantized generalized extra-gradient (Q-GenX) for solving these problems in multi-GPU settings where multiple processors/workers/clients have access to local stochastic dual vectors. In terms of theory, the paper proves $O(1/T)$ convergence of Q-GenX under relative noise and $O(1/\sqrt{T})$ under absolute noise. 
strength_and_weaknesses: The paper has interesting results, however, it has several issues in terms of presentation that do not allow me to suggest acceptance at this stage. Let me provide more details below. 

1. The paper claims that it solves general monotone problems while truly focusing on a much smaller class of VIPs for which the analysis is typically much easier. This is the class of co-coercive VIPs. 

2. On top of the co-coercivity condition, the authors mentioned "Moreover, in order to avoid trivialities, we make the following mild assumption" to refer to assumption 1. However, Assumption 1 assumes that the problem has a unique solution as well. Thus it is far from general monotone or even general co-coercive. 

3. In the expression of the co-coercive condition the dual norm is used without further explanation. Note that the standard co-coercivity holds for euclidean norms. 

4. For co-coercive problems assuming bounded variance, bounded noise or relative noise (growth condition) are unnecessary and quite strong assumptions. Please check the results of paper [1] where these conditions have not been used. 
The authors spend half a page providing examples where Ass. 2 and 3 are satisfied which is good for pedagogical reasons but the examples are standard for anyone familiar with noise assumptions in stochastic algorithms. This space could have been used for the numerical experiment (which is not part of the main paper)

5. Proposition 1 is a well-known result. As presented now it gives the impression that this is a contribution of the authors. The authors mention: "Mathematically speaking, we have the following proposition:" 

6. Presentation of Section 3 is confusing as it involves quantities that appear later in the paper. What is $Q_{\ell_t}$ what is $V_{k,t}$, etc. A good idea for clarity will be to introduce a notation paragraph at the beginning of that section 3. Note that definition 1 only appears in section 3.2 while it should have been presented before section 3.1

7. In section 4 a proof sketch is provided in the main paper which takes half a page. This space could have been used for the experiments which as it is mentioned in several parts of this work is one of its main contributions. At the moment there are no experiments in the main paper. 

8. Main Issue: 
Even if one checks the experiments in the appendix (not a requirement for the reviewer) the paper has no comparison with closely related works that use compression on top of distributed algorithms for solving VIPs. The authors mentioned the works of Beznosikov et al. (2021); Kovalev et al. (2022) and say that they are concurrent works. This is not true. Beznosikov et al. (2021) for example, is 1-year-old paper. 

In the numerical evaluation, a proper comparison with algorithms from the above papers should be presented. 

A highly related paper, that also focuses on co-coercive VIPs, and to the best of my knowledge has state-of-the-art performance in terms of distributed methods with compressors for VIPs is paper [2]. This is also non-concurrent work as it appears some time ago. A formal comparison with the distributed methods with compressed communications presented in that work is highly recommended.  

Missing references:

[1] Loizou, Nicolas, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. "Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity." Advances in Neural Information Processing Systems 34 (2021): 19095-19108.

[2] Beznosikov, Aleksandr, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. "Stochastic gradient descent-ascent: Unified theory and new efficient methods." arXiv preprint arXiv:2202.07262 (2022).
clarity,_quality,_novelty_and_reproducibility: Please see the above review for further details.
summary_of_the_review: As I mentioned in my review the idea of the paper is interesting. However, there are many issues in terms of presentation and numerical evaluation. 

In my opinion, a fair score for the current version of the paper is "3: reject, not good enough" or "5: marginally below the acceptance threshold". 

At this point, I give a score of 5 to this work.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers a monotone variational inequality to be solved in a Federated learning setup, with a central server and multiple clients. They develop a version of the extra gradient (EG) algorithm in this setting where the bottleneck is the communication: In their algorithm, communications between the central server and the clients are compressed.

The resulting algorithm is a version of EG with compression and they show convergence rates in terms of the restricted gap function under different assumptions on the noise in the stochastic "gradient". The stronger assumption on the noise ensures zero noise at the optimum and therefore recover the deterministic rate of EG. Besides, the authors compute the communication cost and show reduction in number of bits communicated at each round.
strength_and_weaknesses: Strength

- The compression part of the paper is precise and specific. The compression operators are described and the number of bits communicating is computed. I am not sure, but these calculations seem to be new. So there is also a contribution here, additional to the optimization part (analysis of EG) 

- The optimization part (EG algo) seems equally solid. Convergence is in restricted gap and recover the deterministic result as a special case.

-The assumptions on the noise cover several types of stochastic gradients

-The meta algorithm actually covers several algorithms for monotone VI


Weaknesses

-In many applications of ML, monotonicity does not hold (Monotonicity is like convexity). This paper deals only with the monotone case
clarity,_quality,_novelty_and_reproducibility: Clarity and quality:

Overall the paper is clearly written. The paper is technical and it is possible that I misunderstood part of it. However, the authors did a good job explaining all the material.

Section 3.3. (optimization of the quantization levels) could be clearer, as well as the difference between encoding and quantization.

Novelty:

This papers seems to be the first to consider communication efficient variant of EG. The rates are reasonable and recover known results as special case. 

No reproducibility issues.
summary_of_the_review: A solid work that considers an idealized setting (monotonicity) but provides precise and competitive guarantees for both the computation complexity and the communication complexity of the proposed algorithm.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work studies distributed (synchronous) algorithms for monotone variational
inequality (VI) optimization, generalizing convex minimization, saddle-point
problems, and games. Specifically, it proposes a quantized, general
extra-gradient framework called "Q-GenX" that unifies previous methods.  This
approach uses unbiased and adaptive compression techniques for communicating
local stochastic gradients, and it uses an adaptive learning rate rule for
which the authors prove convergence guarantees: $O(1/T)$ under relative nosie
and $O(1/\sqrt{T})$ in the presence of absolute noise. For this VI problem,
they show that increasing the number of processes can accelerate convergence.
Lastly, they train GANs on multiple GPUs in the appendix to support their
theoretical results.


strength_and_weaknesses: **Strengths:**
- This paper is very well written and provides a comprehensive survey of
  related works.
- The Q-GenX algorithm is indeed practical, and the authors provide strong
  theoretical guarantees about its performance.

**Weaknesses:**
- The exact contributions of this work over previous methods (aside from the
  unification aspect) should be made more clear. The discussion after Theorem 5
  talks about more processors leading to faster convergence, but how does this
  convergence rate compare to existing methods for different slices of the VI
  problem (e.g., convex, saddle-points)?
- Given the nature of this paper, there should be some experiments in the main
  body. Some GAN experiments are discussed in Appendix H, but it seems
  incomplete.
clarity,_quality,_novelty_and_reproducibility: The writing is extremely clear, but the contributions of this work relative to
others could be more explicit. The experiments in the appendix are minimal but
appear to be reproducible.
summary_of_the_review: This work is polished and well-organized, but the comparison to prior works and
experiments to support the Q-GenX algorithm seem to be lacking. The algorithm
is clean and practical, and come with strong theoretical guarantees. This paper
could be accepted to ICLR, but it would benefit from addressing the weaknesses
pointed out above.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The three reviews are generally positive about the paper, but they also point out some weaknesses and areas for improvement. The main strengths of the paper are:

- It proposes a quantized, general extra-gradient framework (Q-GenX) that unifies previous methods for monotone variational inequality (VI) optimization, a general class of problems that includes convex minimization, saddle-point problems, and games.
- It provides strong theoretical guarantees for the convergence of Q-GenX under different assumptions on the noise in the stochastic gradients, and shows that increasing the number of processors can accelerate convergence.
- It uses unbiased and adaptive compression techniques for communicating local stochastic gradients, and an adaptive learning rate rule, which are practical and efficient.
- It is very well written and provides a comprehensive survey of related works.

The main weaknesses of the paper are:

- It only considers the monotone case, which is a restrictive assumption that does not hold for many applications of machine learning.
- It does not make clear how its contributions compare to existing methods for different slices of the VI problem, and what are the advantages and limitations of Q-GenX.
- It does not include any experiments in the main body, and the experiments in the appendix are minimal and incomplete.
- It does not discuss or compare with some closely related works that use compression on top of distributed algorithms for solving VI problems.



Conclusion:

Based on the reviews, the paper can be accepted for poster, as it meets the minimum criteria for acceptance, but it also has some room for improvement. The paper should address the reviewers' comments and suggestions in the final version, and provide more evidence and clarity for its contributions and comparisons.

References:

[1] Beznosikov, Aleksandr, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. "Stochastic gradient descent-ascent: Unified theory and new efficient methods." arXiv preprint arXiv:2202.07262 (2022).

[2] Beznosikov, Aleksandr, Dmitry Kovalev, Egor Shulgin, and Peter Richtarik. "Communication-efficient distributed optimization with quantized extra-gradient methods." arXiv preprint arXiv:2102.06171 (2021).
justification_for_why_not_higher_score: Why it can not have a higher score:

A higher score would require the paper to address the weaknesses mentioned above, and to demonstrate more clearly the novelty and significance of its contributions. Specifically, the paper could:

- Relax the monotonicity assumption or discuss how Q-GenX can be extended or adapted to non-monotone cases, or provide more motivation and examples for the monotone setting.
- Provide a more detailed and rigorous comparison with existing methods for different slices of the VI problem, and highlight the trade-offs and benefits of Q-GenX in terms of convergence rate, communication cost, and robustness to noise.
- Include some experiments in the main body that showcase the performance and scalability of Q-GenX on realistic and challenging VI problems, such as GANs, and compare with state-of-the-art methods.
- Discuss or compare with some closely related works that use compression on top of distributed algorithms for solving VI problems, such as [1,2], and explain how Q-GenX differs or improves upon them.

justification_for_why_not_lower_score: 
Why it can not have a lower score:

A lower score would not be justified, as the paper still presents a solid and well-organized work that proposes a practical and unified framework for monotone VI optimization, and provides strong theoretical guarantees for its convergence. The paper also surveys a large body of related works, and uses unbiased and adaptive compression techniques that are novel and efficient. The paper has potential to make an impact on the field of distributed optimization, and to stimulate further research on VI problems.
Decision: Accept: poster