Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper constructs methods named CurvatureEG+ (and Adaptive EG+ and CEG+), built upon a recently proposed EG+ [Diakonikolas et al., 2021], a variant of EG, that works under the weak MVI condition. Most importantly, the CurvatureEG+ (and Adaptive EG+/CEG+) works for a range (of the weak MVI) larger than that of EG+. The corresponding nonconvex-nonconcave setting includes non-trivial problems illustrated in the paper, where the proposed method converges, while other existing methods reach limit cycles. Unlike EG+, the CurvatureEG+ can handle both constrained and composite cases. A stochastic variant is also studied. Although the experiments consider toyish problems, they seem interesting.
main_review: **Strengths**
- A larger range of $\rho$ of the weak MVI: The Adaptive EG+ and (a line-search-version) CurvatureEG+ work for a wider range of $\rho$, $\rho>-\frac{1}{2}$ or $\rho>-\frac{\gamma_k}{2}$ respectively, compared to that of EG+, $\rho>-\frac{1}{8}$. (This bound of EG+ could be weakened, but the authors show that this cannot be better than $\rho>-\frac{1}{4}$.) One might be view this improvement negligible (which I did when I glanced through the paper), but the wider region includes, e.g., the difficult "forsaken" example in [Hsieh et al., 2021] and the corresponding experimental results are interesting to read. For the stochastic case, the proposed SEG+ works for a same range of $\rho$, while a stochastic version of EG+ in [Diakonikolas et al., 2021] is shown to work for a more restrictive setting.
- Unified analysis of a larger class of algorithms: This work first used a projection onto a certain hyperplane technique with an adaptive step size. Then, the authors show that it includes a non-adaptive variant, named CEG+, which covers both EG+ and FBF [Tseng, 2000]. (This also allows a larger step size for EG+.) Although the projection on to a hyperplane is not new (while probably new to the machine learning community), such unifying analysis seems theoretically inspiring.
- Stochastic variant: A constant step size for the exploration step (while requiring diminishing step size for the other step) seems new and worth further investigation.
- Experiments: At a first glance, the weak MVI condition looked artificial, but the examples (while toyish) well complemented the importance of such new condition introduced recently.

**Weaknesses**
- One might view the convergence guarantee improvement of CurvatureEG+ over that of EG+ not significant.
- To be precise, none of the examples satisfy Assumption 1 (specifically the Lipschitz continuity) globally. 
- The authors claim that they have less tuning parameters, compared to the method in [Lee & Kim, 2021a], but Algorithm 1 seems to have relatively many tuning parameters. I think this can be resolved, for example, by providing standard choices such as $\lambda_k=1$, $\gamma_k = \frac{1}{L}$, $\delta_k = \rho$, requiring the knowledge of $\rho$ and $L$. This however still does not seem to have less tuning parameters than that in [Lee & Kim, 2021a].

**Other comments**
- Although readers can check the appendix to see an explicit interpretation of the projection onto a certain hyperplane in Algorithm 1, I personally suggest at least further introduce it in the main page if there is a space.
- I think it is worth mentioning related convergence results on the projection onto a certain hyperplane. What is new in that perspective seems missing in this paper. 
- The names of the proposed methods are given in the experiment section, but I suggest mentioning them in the main sections where they first appear for the readers who do not have time to read from the beginning to the end in details.
- After (.2): $\sigma_k$ -> $\delta_k$
- Before (.4): $\bar{z}$ -> $\bar{z}^k$
summary_of_the_review: Built upon a recent study on generalizing EG for nonconvex-nonconcave setting, this paper provides a nice unified framework of EG using the projection onto a hyperplane. Although the improvement in terms of the convergence guarantee is not significant, this paper is theoretically inspiring, and the toyish experiments are informative, which I believe has potential for further research both theoretically and practically.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on variants of ExtraGradient (EG) by considering different options for the two step-sizes of the method: one for the extrapolation step and the second for the iterate update. 
Building on the analysis of (Diakonikolas et al. 2021),  the paper relaxes the setup therein by allowing a larger range of values for the $\rho$ parameter (see Fig. 2) of weak Minty Variational Inequality (MVI) which parameter controls the degree of nonconvexity.

In particular, it provides the following contributions:
*(i)* Primarily it defines Alg.1 where the step size for the iterate update is adaptive and shows the main convergence result (Thm  3.1.) that under some assumptions (Asm 1), Alg. 1 converges on weak MVI problem.
*(ii)* It then considers a non-adaptive variant of Alg. 1, dubbed CEG+, which can be seen as a generalization of the EG+ method of (Diakonikolas et al. 2021), and complements the result of the latter by showing that the convergence result is tight on weak MVI;
*(iii)* extends CEG+ by using an adaptive scheme for the first step size (for the extrapolation) which uses Lipschitz constant backtracking, and Alg.1 for the latter step size (for the iterate update), dubbed CurvatureEG+, which method is shown to empirically converge on some toy-examples on which CEG+ does not;
*(iv)* finally, for the stochastic setup the authors consider one of the step-sizes to be diminishing and the other can be constant, and show that this variant converges on weak MVI problems.

main_review: # Strengths
- The paper has several theoretical contributions referring to different options for the two step-sizes of EG (see summary above), and importantly, it relaxes the setup of prior work--in particular of (Diakonikolas et al. 2021).
- The technical contributions are relevant for the community, given past negative results and the current state of existing provable convergence results. 
----
# Weaknesses
- Inconsistency of methods the authors provide theoretical/empirical results for.  This paper mixes several different options for the step sizes, and the convergence for the stochastic counterparts of the considered full-batch methods is not shown. In particular, the stochastic method requires one of the step sizes to be diminishing, and the considered full-batch methods require different assumptions on the step sizes. 
- Lack of empirical evaluation to verify if the results are helpful for challenging real-world problems, or alternatively a discussion of the importance of the provided results in practice. 
- In terms of novelty, the paper largely builds on (Diakonikolas et al. 2021), and combines it with recent developments of operator splitting techniques (Latafat & Patrinos, 2017; Giselsson, 2021) to provide the relaxation of the problem.
- Due to shifting between the different options, the writing is somewhat confusing and hard to follow (see examples below). 

----
# Minor Comments and Suggestions
- While the writeup seems technically precise, it is not self-contained. In particular, there are missing definitions. As these are the basis for understanding the presented results the definitions should be provided. Examples of non-defined terms: monotone operators, maximally monotone, cohypomonotonicity, etc., and even defining L-Lipschitz is common. 
- Some typos: 
   - in contribution 3: our result are $\rightarrow$ is
   - related works: approaches has been $\rightarrow$  have been
   - Hsieh et al .. considers  $\rightarrow$ consider
   - last sentence Sec. 1: they only considering $\rightarrow$ consider
- Consider naming Alg.1 
- In my opinion, the title could be misleading, it could be interpreted as a novel technique to escape limit cycles for general non-convex contained problems. It does not emphasize that this work specifically focuses on (variants of) extragradient and that the global convergence holds solely for the weak MVI setup. 
- It is hard to follow which proposed method the listed contributions refer to. It might be helpful to define the method in a general form before this listing so that you can be more precise about which step size is adaptive/constant/diminishing etc for each of the contributions.
- adding more detailed related work section (if lack of space in Appendix) to list relevant works on convergence results (e.g. the reference below)

----
# Questions
- Is it possible to provide a separate convergence theorem for CurvatureEG+ on weak MVI, ideally for a larger set of problems than Thm 3.1. as the results indicate?
- How does CEG+ perform on Forsaken (Fig.1)?
- Does CurvatureEG+ escape unstable critical points? In particular, how does it perform on the almost bilinear toy example of Hsieh et al '21? 
- Since CurvatureEG+ uses an iterative way to find the step size, it is important that the  authors provide a comparison with EG on a problem where EG converges with the x-axis being the computation time
- Could you comment on the convergence rate you get relative to existing results of EG on monotone variational inequalities, e.g. [1]

[1] Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems, Golowich et. al, 2020
summary_of_the_review: The paper provides several contributions for different variants of the extragradient method, which in general are of interest to the community. 
It lacks stochastic counterpart convergence guarantees of the full-batch results, and it considers several variants of the method rather than focusing mainly on the method with best convergence properties and to consistently discuss its convergence in full-batch setting, then stochastic, and finally verifying these results and ideally discussing/showing if these are relevant for challenging real-world setups.
In summary, the paper is somewhat rushed, and although it is in a good and valuable direction, at this stage, it requires major modifications (see comments above) and additional stochastic counterpart results.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed CEG+ and CurvatureEG+, which extend extragradient method to a proximal variant (regarding the operator $A$), and apply it in nonconvex-nonconcave minimax optimization with Weak MVI condition in both deterministic and stochastic cases, and proved their complexities, which has the same order as those in literature (e.g., Diaonikolas et al., 2021). The authors also studied the lower bound in the simpler case when $A\equiv 0$, showing a difference compared to EG+ in (Diaonikolas et al., 2021).

In the deterministic case, it proposed an adaptive stepsize strategy to allow larger range of the MVI parameter $\rho$, and further a curvature-based strategy to avoid the lower bound requirement of $\rho$. The authors also executes several experiments, showing that CurvatureEG+ can avoid cycling in the experiments.
main_review: The paper focuses on general minimax problems, which is a very important problem (even though with the special Weak MVI structure). The paper is clearly written and easy to read. 

The results of curvature-based adaptive stepsize and lower bound look interesting, which can reveal a significant difference compared to EG+, and rationalize the extension of the regime of $\rho$.

My main concern is that:
1. The lower bound requires EG+ to have a fixed stepsize $\gamma$, but as far as I know, lower bound analysis generally has no requirement on the stepsize (in fact they are using linear-span algorithms, so it can be arbitrary stepsize). So to some extent, now I view the lower bound result too specified and therefore a little restrictive, can the author comment more about it?
2. Even though with the craft stepsize strategy, the final complexity result is still similar to those in existing literature, will the parameter choice of proposed algorithm bring any benefits in terms of the complexity (even in the constant)? Or do you think the lower bound for the whole class of weak MVI problems is already achieved? Can the author comment more about it? Thank you.

Generally I view the results in the paper pretty interesting.
summary_of_the_review: This paper provides approach to avoid lower bound of Weak MVI parameter and provide a lower bound perspective on the fundamental difference compared with existing literature.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work extends the extragradient algorithm in Diakonikolas et al. (2021) from unconstrainted and unregularized inclusion problems that satisfy weak Minty inequality (MVI) to their constrained and regularized counterparts. Compared with the original extragradient algorithm, the extended algorithm is proved to converge with a larger range of stepsize choices and MVI-related constant $\rho$ (implying a larger set of applicable problems) in both deterministic and stochastic inclusion problems. The range of $\rho$ is also proved tight by providing a lower bound of $\rho$. The extended algorithm also generalizes the celebrated forward-backward-forward (FBF) algorithm in Tseng (2000). Finally, an improvement of this extended algorithm is proposed using Lipschitz constant backtracking. 
main_review: Pros:

(1) This paper studies the constrained/regularized nonconvex-nonconcave minimax optimization and its generalization called weak MVI problem, which are popular, important, general and hard problems. 

(2) There are abundant extensions of the original extragradient algorithm. 

(3) Both theorems and experiments convincingly demonstrate that there are inclusion problems where the original extragradient algorithm diverges while the proposed algorithm with adaptive stepsizes converges. 

Concerns: 

(1) In the introduction, you said "However, given the range of $\rho$ in Diakonikolas et al. (2021), the new class is still too small to include even the simplest counterexample of Hsieh et al. (2021) for the general Robbins-Monro schemes." Does your setting contain this simplest counterexample? If yes, I think it better to elaborate this counterexample and demonstrate that it belongs to your setting but not that in Diakonikolas et al. (2021), possibly in the appendix. If not, then I think it better not to mention this counterexample. 

(2) In Section 3.1, your maximum stepsize $\overline{\alpha}_k$ is $3/2$ of Diakonikolas et al. (2021). Is your convergence rate also faster than or comparable with that paper? A similar comparison of convergence rate might also be made between your Theorem 3.5 and Theorem 4.5(i) in Diakonikolas et al., 2021.  

(3) To my understanding, $\|\overline{z}^k-z^k\|$ is a generalization of proximal gradient, a popular measure for nonsmooth nonconvex minimization problems. Why do you use the convergence measure $\|H\overline{z}^k-Hz^k\|$ instead of $\|\overline{z}^k-z^k\|$?

(4) In Figure 2, should the region below the dashed line indicates where $\rho>-1/8L$ and the dashed line indicates where $\rho=-1/8L$? What does "positive result" mean? Diakonikolas et al. 2021 only obtains convergence results at the black square point while you obtain convergence results at the blue round point, right? 

(5) In Theorem 3.4, is it better to derive a lower bound of Algorithm 1 instead of EG+, i.e., the lower bound where Algorithm 1 may diverge? 

(6) What is the definition of "origin" in Example 4? 

(7) In the left subfigure of Figure 3, Adaptive EG+ seems to converge to the limit cycle instead of a stationary point. How do you explain? 

(8) In Figures 3 and 4, does "lower bound example" mean Example 5? Example 5 seems to have the maximally monotone operator $A\ne 0$. In this case, does $\|H\overline{z}^k-Hz^k\|= \|F\overline{z}^k\|$ still hold? If not, I think the y label should perhaps be $\|H\overline{z}^k-Hz^k\|$ instead of $\|F\overline{z}^k\|$. 

(9) In the experiment, for the algorithms with adaptive stepsizes, I think it better to give the specific stepsize values, such as $\gamma_k=1/k$, etc. 

(10) In the experiment, you said "this is the direct generalization to the constraint setting of the EG+ scheme studied Diakonikolas et al. (2021)." Does "this" mean CEG+ only, or both CEG and CEG+? 

(11) The convergence of CurvatureEG+ is assumed not proved in Lemma 4.1. Is it feasible to prove?

Minor comments:
(1) You might cite the following paper about nonconvex-nonconcave minimax optimization, and discuss about your advantage over it. 

[1] Yang, J., Kiyavash, N., \& He, N. (2020). Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems. ArXiv:2002.09621.

(2) In Theorem 3.1 and 3.4, is it feasible to recommend adaptive stepsizes that lead to the fastest possible convergence rate? 

(3) In Figure 1, I think it is better to explain the blue and red curves in either legend or caption. They are multiple trajectories from different initial points, right? Why do some red curves on the right subfigure have small black ends?

(4) I think it better to define "maximally monotone" and "cohypomonotonicity" or cite the papers that have the definition, as some readers like me see these concepts for the first time. 

(5) You might add "(MVI)" right after "Weak Minty inequality" in Assumption 1.

(6) There's a typo in "VIs provides a convenient abstraction for a range of problems", you could use "provide". 

(7) There's a typo in "Recal that the resolvent of a maximally monotone operator", you could use "Recall".

(8) In "by making the extrapolation step adaptive as well" in Section 3, you might explain which of equation (EG+) is "extrapolation step", or maybe use "making $\gamma_k$ adaptive as well"?

(9) Right below Corollary 3.2, should $\overline{z}^k-F\overline{z}^k-Hz^k$ be $\overline{z}^k-\gamma F\overline{z}^k-Hz^k$? 

(10) In the experiment, I think it better to add "(cf. Appendix A.1)" right after "Example 5". 
summary_of_the_review: Due to the aforementioned pros, I think this is an excellent paper and would like to see it accepted. Some points need to be clarified as aforementioned in the concerns and minor comments.
review_title: null

Meta-review: The paper considers the saddle point problem of finding non-convex/non-concave minimax solutions. Building onEG+ of Diakonikolas et al., 2021 that works under weak MVI conditions, the work presents a new algorithm CurvatureEG+ that works for a larger range of weak MVI condition compared to previous work and also works for the constrained and composite cases. The authors show cases where this algorithm converges while the previous algorithms can be shown to reach limit cycles. Overall, this theoretical work seems strong. Most reviewers seem to agree that the contribution is good enough for publication. Compared to EG+ the additional contribution is to expand the range of weak MVI condition. While this seems like a slight improvement, looking beyond just the final convergence rate, the paper has some nice insights that provides a unifying view that captures past algorithms (like EG+ as special case). I recommend acceptance.
Decision: Accept (Spotlight)