Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Consider unconstrained, possible non-convex-non-concave min-max problems where the saddle gradient operator is Lipschitz and comonotone. Suppose our aim is to minimize the squared norm of the saddle gradient. Inspired by the Halpern iteration and generalized extragradient method, this paper proposes a method called Fast Extragradient (FEG). This paper shows that both FEG and a backtracking variant of it converge at a $O(1/t^2)$ rate, whereas in literature, this rate is only achieved assuming the problem is convex-concave. This paper also proposes a stochastic method called Stochastic FEG (S-FEG); if the variances of the noisy gradients is $O(1/t)$, then S-FEG also converges at a $O(1/k^2)$ rate in expectation. 
main_review: Overall, I think the paper is solid and novel enough. I like the examples and the discussion in Section 8; they are non-trivial and informative. Regarding novelty, the proposed FEG method does not look like a direct combination of the Halpern iteration and extragradient method. Indeed, it is curious to me how the authors found the form of FEG, though I feel it should be possible given, e.g., [6,7,38]. It would be good if the authors can elaborate on how they came up with the idea. 

[38], which proposes an FEG-like method for smooth convex-concave problems, is perhaps the most similar work to the submission. Since the convergence guarantees in this submission require a lower bound on the comonotonicity parameter in terms of the smoothness parameter, I would like the authors clarify if the algorithm and analyses in the submission can be directly obtained given [38] or not and, if possible, address the possibility of getting rid of the lower bound on the comonotonicity parameter. 

The significance of this work seems to be theoretical. I wonder if there is any practical problem that is not convex-concave and satisfies the comonotonicity condition in the paper. 

The S-FEG part seems isolated. The algorithm is not exactly an instance of FEG. It would be good if the authors can explain why. It seems that the authors want to pursue a $O(1/t^2)$ convergence rate. As the stochastic setup includes several learning and statistical problems, I feel it more reasonable to argue that it is in general impossible to have a rate faster than $1/t$. 

I do not get the second last line in the equation following Line 239. Please explain. 

The presentation is clear. I suggest the authors indicate where the reader can find the proof of Theorem 4.1 after presenting the theorem. 

I do not check all proofs in the supplementary material. 

Typos: 
- Line 104: The lower bound should not be expressed in big-O. 
- Line 228: *the* potential function

limitations_and_societal_impact: Please address the issues I raised in the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper develops a new extra gradient algorithm for solving minimax problems with negative comonotonicity condition. This condition allows nonmonotonicity and therefore covers a class of nonconvex nonconcave minimax problems. This method gets 1/k^2 rate on the squared gradient norm. The algorithm builds on the recent anchored extra gradient algorithm by Yoon, Ryu [39] which focused on monotone case. For handling nonmonotone case, the authors use the recent development by Diakonilas et al [7] that focused on weakly Minty VI (MVI) problems which is a more general template than negative comonotone. This paper also includes extensions with line search and stochastic oracles. For the monotone case, the bounds in this paper are tighter than [39] and the analysis is simpler.
main_review: In terms of techniques, this paper mostly builds on [39]. When \rho = 0, FEG is slightly different from EAG of [39]. The change is that the step size for the first update is (1-\beta_k)\alpha_k instead of \alpha_k. To handle negative comonotonicity, FEG incorporates additional terms depending on \rho_k and Fz_k. This modification is used in the analysis to remove the additional error terms coming from lack of monotonicity (as in line 447, first line: -\rho_k\|Fz_{k+1} - Fz_k \|^2.

From what I understand, the authors cannot handle weak MVI assumption since the proof of [39] uses monotonicity with z_{k+1} and z_k, which corresponds here to the first line in line 447. Therefore, this drawback is inherited from the analysis of [39]. Is this correct? On this front, I am concerned with the novelty because of this. The analysis seems to be slightly tighter and giving better bound, but there is no advantage on flexibility: the paper cannot handle MVI or weak MVI assumptions.

The extensions for line search and stochastic oracle seem straightforward but these are not claimed to be the main contributions, so it is fine. More interesting for me is that the authors managed to derive a tight rate compared to [39]. On the other hand, I am curious how this translates to practice. Can the authors run a toy example and compare with EAG-V?

Presentation: I think the paper highlights nonconvex-nonconcave problems too much that it can be misleading. The paper can only handle a small class of nonconvex-nonconcave problems, whereas the abstract and the intro are written too much highlighting this aspect, using GANs, adversarial learning etc. However in the sequel, the authors do not mention at all if the negative comononicity holds for any of the problems. Moreover, the paper cannot handle weak MVI or MVI problems which are themselves restrictive in terms of applications.

Examples: The authors only use Example 1 to give example problems for Assumption 2. Is there any interesting concrete examples that satisfy this assumption? Otherwise, I recommend authors to decrease the focus of introduction on nonconvexity. If there are no interesting applications of the assumption, I doubt it has much value.

I might increase my score if the authors can highlight novelties in their analysis on top of [39] and clarify whether any concrete applications exist for negative comonotonicity.
limitations_and_societal_impact: The work does not have potential negative societal impacts. In the other hand, I suggest the authors to highlights the limits in the paper in terms of existence/lack of problems satisfying negative comonotonicity, or flexibility of the analysis: why does MVI and weak MVI assumptions not sufficient?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a two-time-scale and anchored extragradient method for smooth structured nonconvex-nonconcave problems. The proposed FEG method with the Lipschitz continuous and negative comonotone operators has an accelerated convergence rate, O(1/k^2), with respect to the squared gradient norm.. Moreover, the authors further study the backtracking line-search version of FEG, named FEG-A, for smooth structured nonconvex-nonconcave problems, and also propose its stochastic version, named S-FEG, for smooth convex-concave problems.
main_review: The paper is nicely written and overall easy to follow. The rigorous convergence analysis of the proposed algorithms has been provided in this paper.

There are several major issues in this paper:
1.	In Theorem 4.1, the condition \rho>-1/2L needs to be modified, because when \rho=1/sqrt(k)-1/2L, the convergence rate is O(1/k) instead of O(1/k^2).
2.	The update rules in Algorithm 1 depends on the parameter \rho.  In a practical min-max problem, how to determine the parameter \rho?
3.	Although the paper is theoretically sound, there is a lack of experiments to verify the proposed algorithms.

limitations_and_societal_impact: 1.	In Theorem 4.1, the condition \rho>-1/2L needs to be modified, because when \rho=1/sqrt(k)-1/2L, the convergence rate is O(1/k) instead of O(1/k^2).
2.	The update rules in Algorithm 1 depends on the parameter \rho, for a practical min-max problem. How to determine the parameter \rho?
3.	Although the paper is theoretically sound, there is a lack of experiments to verify the proposed algorithms.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes and analyses a variant of Extragradient with anchoring and reuse of past gradients that they call Class FEG. They analyze this method in the context of Lipschitz and comonotone operators (that is a subclass of non-monotone operators). They also propose a version of their algorithm with backtracking line-search and propose an analysis in the stochastic setting (with vanishing noise!). They show accelerated (with respect to the normal EG rates) convergence rates in the comonotone setting when the comonotonicity is small enough with respect to the Lipschitness of the operator.  
main_review: ### Main Points:
- Significance: This paper proposes a new method with accelerated rates in a non-monotone setting. It is very relevant to the ML community since it deals with the comonotone setting, which is a first step to understand the general non-monotone setting that has application to GANs and, more generally, any game with non-convex payoffs. 
Quality: This paper provides high-quality results. I have a question about Lemma 8.1 that I would like the authors to address: First of all, I would like to know how the authors address the previous works that proposed worst-case scenarios for smooth operators ([Hsieh et al. 2021] and [Letcher et al. 2021]). Second of all, I am a bit confused because Lemma 8.1 seems to provide a counterexample for Theorem 4.1. Since what only matters are what happens in the line {x=y} and that on that line, F is constant (hence Lipschitz and comonotone). Even if the example provided in Lemma 8.1 is not comonotone (which is currently not proven in the paper), it is not clear to me why it is impossible to extend a vector field F such that $F(x,x) = (-\sqrt{LR},-\sqrt{LR}), \forall x$ into a Lipschitz and comonotone vector field. 

- Clarity: The paper is very clear and well written
- Originality: The proposed method is novel, and the analysis with accelerated rates is new and very relevant to the community. 
The main weakness of the paper is that there is no experiment to illustrate the performance of their algorithm in such a \rho-comonote case. The consequence of this lack of experiment is two-fold: first, the authors do not propose any concrete example of realistic or synthetic comonontone games for which their assumptions hold (namely $\rho > -\frac1{2L}$). Secondly, it would illustrate the practical improvement over Extragrdient in such a setting and the additive value of the proposed backtracking line search. 

### Conclusion:
Besides the weakness mentioned above, I think this paper is a strong contribution to the community and should be accepted to NeurIPS. However, if the authors could provide some experimental results and answer my question about Lemma 7.1, I would consider increasing my grade.

### Minor comments: 
L239: $V_1$ is not equal to 0! I checked your proof, and thanks to the fact that $\alpha \leq 1/L$ we have $V_0 \leq 0$. 

### Reference:
Hsieh, Ya-Ping, Panayotis Mertikopoulos, and Volkan Cevher. "The limits of min-max optimization algorithms: Convergence to spurious non-critical sets." International Conference on Machine Learning. PMLR, 2021.
Letcher, Alistair. "On the impossibility of global convergence in multi-loss optimization." ICLR 2021.

### After Rebuttal
After the discussion with the authors, I decided to maintain my score.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: The authors propose an extension of [Yoon and Ryu] along the function class of [Diakonikolas et al], which technically considers a bigger function class than [Mertikopoulos et al; extra mile]. The authors' provide a clean algorithm (FEG) and then try to make it practical via line-search. Finally, they provide a stylized example. On the theoretical side, the success of line-search is guaranteed provided that the parameters fall within an unknown threshold, which is a weakness. The authors are recommended to explain this weakness in their final version. Overall, it is a solid paper with some technical contributions over the existing optimization literature on weak MVIs.
Decision: Accept (Poster)