Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper has several contributions:
1. it derives $(\mathcal{O}\frac{1}{\sqrt{T}})$ convergence rate of the best iterate of an extension of Optimistic gradient (OG). The setup is weak minty VIs (MVI)---which is a setting that includes non-monotone VIs as well; Sec. $3$.
2. proposes an accelerated version of Reflected Gradient (RG) by combining it with anchoring as in Halpern iteration--- named *ARG* for short---and shows that it achieves the optimal $\mathcal{O}(\frac{1}{T})$ last iterate rate. The setup here is negatively comonotone problems, which are larger than monotone but smaller class than weak MVIs. 
3. shows that RG has $\mathcal{O}(\frac{1}{\sqrt{T}})$  last iterate rate for constrained convex-concave min-max optimization.  


The first two results are in terms of the decreasing rate of a quantity called *tangent residual* which the authors show that it upper bounds the natural residual in Diakonikolas, 2020. The third one is with respect to the standard gap function and also the tangent residual.

strength_and_weaknesses: **Strengths**.
- This paper focuses on some interesting and highly relevant VI problems and has several contributions.
- It is generally well-written, and easy to follow, with clear notation. I also like that the authors provide proof sketches when the full proof is deferred to the appendix.


**Weaknesses**
- Some of the presented aspects of the first two contributions exist in prior works (please see below). The third contribution does not exist if I am correct, but it is for the setting of a much smaller class of convex-concave zero-sum games.

- Missing motivation/relevance to focus on some of the considered methods and the little connection between the results and the considered setups and methods. In my opinion, it would have been clearer if the three results are separated and each is developed further with some more relevant questions such as parameter-free guarantees, stochastic case, etc, and discussing the insights from the theoretical results, e.g. better dependence on some constants relative to other methods, etc. 

- Structure. This may be a consequence of the above, but it is often difficult to follow the flow in terms of the motivation of what follows. For example, the introduction mostly motivates the first two contributions. Please also discuss therein the difference between those two non-monotone setups, for completeness. Then, Sec. 5 separately discusses the motivation for Thm. 3 after the result is presented.
clarity,_quality,_novelty_and_reproducibility: ### Missing related works
- the first contribution is as in [1] where a best-iterate rate is provided for a variant of OGDA (of the same order) for weak MVIs.
- a relevant work to the second contribution that achieves the same accelerated rate for OGDA-variant is [2] for monotone VIs.

These should be added in Table 1. 

[1] Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions, Böhm, 2022, https://arxiv.org/abs/2201.12247

[2]  Fast OGDA in continuous and discrete time, Bot et al., 2022, https://arxiv.org/abs/2203.10947

### Questions
1. Since you are addressing the general case of general A, could you comment on some examples when A is not the normal cone for a closed domain? And are there some examples when the inverse computation is computationally inexpensive? 
2. Could you comment on the range of convergent step sizes between OG and the two-projections methods that have the same rate on the setup of Thm 1? Did you explore trying to make Thm 1 parameter-free?
3. A similar technique of combining anchoring with EG was used by Lee & Kim, 2021. Could you comment on the technical differences (and challenges if applicable) when applying those techniques to OG?
4. Could you provide some examples in which cases one would use RG? Alternatively, could you provide some references to the relevant part in Sec. 5?
5. Could you provide some simulations of how ARG performs relative to accelerated variants of EG (or others) with guarantees for this setting?


### Writing / Minor / Typos
- Abstract: existing methods [...] require  (instead of *requires*)
- Abstract: missing quantifier, [...] in applications -> in some applications. 
- Abstract: the abs. is wrongfully alluding that the first contribution is for the last iterate, and for standard OG, be specific that it is an OG-variant
- Abstract: only the third contribution specifies that the result is for the last iterate; be specific for the first two as well
- Abstract: specify the used measure for those rates
- page 2, last paragraph: operators satisfy the [...] -> operators that satisfy
- page 3: variationally stability -> variational stability
- page 3: either move the resolvent definition above or move the related works section after you define resolvent
- include full stops after the equations if the corresponding sentence ends after it.
- be specific in Theorem 1 and 2 to which assumption you refer when referencing Definition 1 since the latter has two different definitions 
- Explain why you discuss Fact 1, instead of just listing it after the proof of the Theorem 1

summary_of_the_review: This paper provides three contributions, among which the first two go beyond standard monotonicity, and thus are key to understanding game optimization.
Prior work showed similar results for the first two contributions. The third contribution focuses on a much smaller problem class and it is not clear to me why it is relevant that we consider that method given that other methods have the same rate and guarantees for larger problem classes, but I may be missing something.
It focuses on three different setups and three different methods, making its coherence and writing structure less easy to follow. The paper could be significantly improved by adding motivations and discussions for the presented results, as well as some further more practically relevant questions such as parameter-free guarantees and stochastic settings.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper involves the study of constraint min-max optimization problems in the nonconvex-nonconcave setting with structure. Specifically, the more general framework of inclusion problems. Regarding the methods presented, they exclusively require single calls to the oracle and to the resolvent of an operator A; that is mainly the prominent goal of this work. 
The two main contributions involve an extension of the Optimistic Gradient (OG) for the inclusion problems whose operators satisfied the weak MVI and a new accelerated Reflected Gradient (ARG) method for the same class of problems but for the case of negatively comonotone operators. The convergence rate achieved in the latter improves over [1] with respect to the number of oracle and projection calls, and is also optimal matching the lower bound of any first-order methods even for monotone inclusion problems. Lastly, the authors show that RG achieves a last-iterate convergence rate for convex-concave min max optimization, an open problem mentioned in [2].


References
[1] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated Algorithms for Monotone Inclusions and Constrained Nonconvex-Nonconcave Min-Max Optimization.
[2] Yu-Guan Hsieh, Franck Iutzeler, JÂ´erË†ome Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods.
[3] Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.

Typos
	1	In the last expression of Theorem 1 there should \frac{2 \rho}{\eta}
strength_and_weaknesses: Overall, I believe it is above bar for acceptance. The paper provides a clear but quite technical analysis (Proposition 2) and does a significant contribution to the field of single-call methods. Additionally, although the presented techniques might not be novel (see [3]), the authors propose the first single call single-resolvent method (ARG) of optimal convergence rate in the general structured (negatively comonotone) constraint nonconvex-nonconcave setting that has received important attention lately.

References
[1] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated Algorithms for Monotone Inclusions and Constrained Nonconvex-Nonconcave Min-Max Optimization.
[2] Yu-Guan Hsieh, Franck Iutzeler, JÂ´erË†ome Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods.
[3] Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.
clarity,_quality,_novelty_and_reproducibility: The paper is written in a clear way and the work seems original.
summary_of_the_review: The authors show that RG achieves a last-iterate convergence rate for convex-concave min max optimization, answering an open question asked in "On the convergence of single-call stochastic extra-gradient methods". This makes the paper above the bar for acceptance I feel.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes three single-call algorithms for constrained min-max optimization and develops the following convergence guarantees. (i) The OG method achieves $O(1/\sqrt{T})$ convergence rate for weak MVI problems. (ii) The ARG method achieve the optimal $O(1/T)$ convergence rate in the negative comonotonicity regime. (iii) The RG method achieves an $O(1/\sqrt{T})$ last-iterate convergence guarantee for constrained convex-concave optimization. The weak MVI and negative comonotonicity regimes have been well studied. 
strength_and_weaknesses: Strength:

1. The algorithms establish the first convergence guarantee for nonconvex-nonconvex min-max optimization problems under weak MVI and negative monotonicity regimes. These results are new. 

Weaknesses: 

1. This paper studies the single-call scenario that restricts algorithms to conduct one oracle call per iteration. This seems to be restrictive and lacks motivation. The classical extra-gradient method only requires making two calls to obtain the gradients. Decreasing two calls to a single call does not seem to have a significant practical impact. These differences are often hidden in the big-O $O(\cdot)$ notation with many other constants, such as the $H^2$ and $\eta^2$ terms specified in Theorem 1. Meanwhile, if we consider  $z = [x, y]$ as one vector, EG approaches only require one projection instead of two.  It would be beneficial if the authors could provide more motivation for studying single-call algorithms. For instance, is there a scenario in which only single-call algorithms can be applied? 

2. In Theorem 1, the authors develop the convergence guarantees for weak MVI problems for a restrictive choice of $\rho \in ( - \frac{1}{12\sqrt{3}L}, 0]$. I wonder why it is necessary for the convergence claim. Is this choice of $\rho$ commonly accepted by EG methods for weak MVI problems? Similarly, Theorem 2 considers the case when $\rho \in ( -\frac{1}{100L}, 0 ]$, which also restricts its applicability. A comparison of choices of $\rho$ in existing works would be beneficial. 

3. Theorem 3 establishes an $O(1/\sqrt{T})$ convergence guarantee for convex-concave problems, which is suboptimal for EG methods. In this case, it seems suboptimal to consider single-call approaches because it requires a larger amount of iterations than the classical EG methods. 

4. This paper does not provide numerical experiments to test the practical performance of their algorithms. It would be beneficial if the authors could provide some numerical results to test their algorithm and compare the total required calls with classical EG approaches. 
clarity,_quality,_novelty_and_reproducibility: Clarity: The problem setting is easy to understand. 

Quality: The theoretical part establishes some new results and is clear. However, the single-call regime is not well-motivated and lacks numerical support. 

Novelty: This paper studies a novel single-call nonconvex-nonconcave min-max problem. 

Reproducibility: No numerical results are provided. 
summary_of_the_review: This paper proposes a class of single-call algorithms for solving nonconvex-nonconcave min-max problems and establishes the theoretical convergence guarantees. However, the single-call regime is not well-motivated. Theorems 1 and 2 rely on some restrictive choices of $\rho$, which weakens their applicability. Theorem 3 provides a suboptimal convergence rate. No numerical results are provided to test the practical performance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes new algorithms for structured non-convex non-concave min-max optimization that improve upon prior work by decreasing the number of gradient computations per iteration from two to one, by achieving last-iterate convergence, and by achieving improved convergence.

This paper generated significant discussion regarding the motivation for obtaining single-call methods and last iterate convergence, as well as the assumptions studied and the limitations of the analysis. After the discussion, the reviewers agreed that single call methods and last iterate convergence are meaningful contributions that are valuable to the community. The reviewers also agreed that the assumptions on the rho parameter are a significant weakness of the paper, but this limitation is shared to a large degree by the prior works as well.

Overall, the improvements over the prior work and the technical contributions are significant enough to warrant acceptance.
justification_for_why_not_higher_score: The paper's technical strength and improvements over prior work are significant, but the assumptions and limitations of the analysis restrict the applicability of the results. 
justification_for_why_not_lower_score: The paper improves on prior works on several relevant dimensions and it introduces new analysis techniques that may lead to further progress.
Decision: Accept: poster