Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems
Authors: Sucheol Lee
Donghwan Kim
Venue: NeurIPS 2021 Poster (2021)
Keywords: Minimax problems
Nonconvex-nonconcave Problems
Extragradient Method
Acceleration

Abstract: Modern minimax problems, such as generative adversarial network and adversarial training, are often under a nonconvex-nonconcave setting, and developing an efficient method for such setting is of interest. Recently, two variants of the extragradient (EG) method are studied in that direction. First, a two-time-scale variant of the EG, named EG+, was proposed under a smooth structured nonconvex-nonconcave setting, with a slow $\mathcal{O}(1/k)$ rate on the squared gradient norm, where $k$ denotes the number of iterations. Second, another variant of EG with an anchoring technique, named extra anchored gradient (EAG), was studied under a smooth convex-concave setting, yielding a fast $\mathcal{O}(1/k^2)$ rate on the squared gradient norm. Built upon EG+ and EAG, this paper proposes a two-time-scale EG with anchoring, named fast extragradient (FEG), that has a fast $\mathcal{O}(1/k^2)$ rate on the squared gradient norm for smooth structured nonconvex-nonconcave problems; the corresponding saddle-gradient operator satisfies the negative comonotonicity condition. This paper further develops its backtracking line-search version, named FEG-A, for the case where the problem parameters are not available. The stochastic analysis of FEG is also provided.

Fast Extra Gradient Methods for Smooth Structured Nonconvex-Noncooccvv Minimax Problems
Sucheol Lee
Donghwan Kim Department of Mathematical Sciences KAIST
Department of Mathematical Sciences KAIST
Daejeon, Republic of Korea csfh13790kaist.
Daejeon, Republic of Korea donghwankkimkaiist. ac
Abstract
Modern minimax problems, such as generative adversarial network and adversarial training, are often under a nonconvex nonconvex-noncoonaay nonconocae setting, and developing an efficient method for such setting of interest. Recently. two variants of the extragradient (EG) method are studied in that direction. First, two-time-scale variant of the EG, named EG+, was proposed under a smooth structured nonconvex- nonconcave setting, with slow (11/k) rate on the squared gradient norm, where k denotes the number of iterations. Second, another variant of EG with an anchoring technique, named extra anchored gradient (EAG), was studied under smooth convex-concave setting, yielding a fast O(1/k²) rate on the squared gradient norm. Built upon EG+ and EAG, this paper proposes two-time-scale EG with anchoring, named fast extragradient (FEG), that has a fast Ol1/k²) rate on the squared gradient norm for smooth structured nonconvex noncooecannccccvveeee problems; the corresponding saddle-grading condition. This paper further develops its backtracking line-search version, named FEG-A, for the case where the problem parameters are not available. The stochastic analysis of FEG is also provided.
operator satisfics the negative comonotonicity
Introduction
Recently, nonconvex-noneoneee minimax problems have received an increased attention in the optimization community and the machine learning community due to their applications to generative adversarial network [10] and adversarial training [27]. this paper, we consider a smooth structured nonconvex-noncooccve minimax problem:
max f(x, # vEn*y
min
(1)
where f Rd R -> IR smooth and is possibly nonconvex in for fixed y, and possibly nonconcave in for fixed æ; the saddle-gre aaadeeggaddent operator F : (V.f. - -,f) satisfies the negative comonotonicity []. We construct an efficient (first-order) method, using saddle gradient operator F for finding first-order stationary point of the problem (
So far little known under the nonconvex-nonconeee setting. Recent works 4. 7
setting, compared the convex-concave 42 44 studied extragradient-typr methods [19 39 for
22
24
26
settings. other words, they consider various non-monotone conditions on F, such as the Minty variational inequality (MVI) condition the weak MVI condition 77, and the negative comonotonicity Among them, this
minimax problems under various structured conconvex-nonconeee
35th Conference on Neural Information Processing Systems (NcurIPS 2021).
Rellations between the conditions F considered in this paper summarized in Figure

---

paper focuses on the negative comonotonicity condition for Lipschitz continuous F. To the best of our knowledge, the following two-time-scale variant of the extragradient method, named EG+:
OK F
2k+ Zk B
(EG+)
2 = 2k C2p. cg 1+11/2
is the only known (explicit method, using F, that converges under the considered setting where z == (Øt, yt)). The EG+, however, has a slow ( (1//k) rate on the squared gradient norm. Note that a similar two-time-scall approach has been found stabilize the stochastic extragradient method with unbounded noise variance [14].
Meanwhile, under the smooth convex-concane setting, recent works 66
suggest that 40
Halpern-type [2] (or anchoring) methods, performing a convex combination of an initial point zo and the last updated point 23; each iteration, has fast (11/k²) rate in terms of the squared gradient norm. In particular, [43] developed the following anchoring variant of the extragradient method, named extra anchored gradient (EAG):
2/+ = 2k + BBxZ00 2/:) FzE;
(EAG)
Æh++ = 2/ + Bx
2%,)
F2 11+1/2
This is the first (explicit) method with a fast O(1/k²) rate on the squared gradient norm, when F satisfies both the Lipschitz continuity and the monotonicity. [43] also showed that such ( rate is optimal for first-order methods using Lipschitz continuous and monotone F.
Built upon both EG+ and EAG, this paper studies the following class of two-time-scale anchored extragradient methods, named fast extragradient (FEG):
k//1/2 = 2/z + 3x (=o- - =x) (1 - -Bx) + +22x)
(Class FEG)
1 Z/ + 3a (=0 - 2n.) Org 12 (1 - 3x)2pp Fzz-
Note that Class PEG reuses the Fzx term the 24+11 update, unlike the standard extragradient- type methods, which found essential for handling the negative comonotonicity condition. We leave further understanding the use of F Fzz and the formulation of (Class FEG) as future work. The proposed FEG method (with appropriately chosen step coefficients Cgg. Bg and Ps. discussed later) has an (1/k2²) rate on the squared gradient norm, under the Lipschitz continuity and the negative comonotonicity conditions
F. To the best of our knowledge, this is the first accelerated method under the nonconvex-noncooean setting. The FEG also has value under the smooth convex-concave setting. First, when F is Lipschitz continuous and monotone, the rate bound of FEG about 27/4 times smaller than that of EAG. Also note that the rate bound of FEG is only about four times larger than the (L/k²² lower complexity bound of first-order methods under such setting [3], further closing the gap between the lower and upper complexity bounds. Second, when F is cocoercive, FEG has a rate faster than that of version of Halpern iteration 12 in (
We also develop an adaptive variant of FEG, named FEG-A, which updates its parameters, ag and Pk in (Class FEGG, adaptively using backtracking line-search 2 25 31). FEG requires the knowledge of the two problem parameters for the Lipschitz continuity and the comonotonicity of F. However, those global parameters can be conservative, and in practice, they are even usually unknown. For such cases, the FEG-A adaptively and locally estimates the problem parameters, while preserving the fast rate (1/k²² on the squared gradient norm for smooth structured minimax problems,
Lastly, study stochastic version of FEG, named S-FEG, which uses unbiased stochastic estimate of Fz, i..., Fz Fz + instead of Fz in FEG, where & denotes stochastic noise. For Lipschitz continuous and monotone F, we provide a convergence analysis in terms of the expected squared gradient norm. In specific, we show that the S-FEG is stable with rate (11/k²) O(c), when the noise variance decreases in the order of (c/kk), while heing unstable otherwise due to
A proximal point method converges under the negative comonotonieity [ 18 but such implicit method not preferable over explicit methods 'The EG+ was originally shown to work under the weak MVI condition of F. which is weaker than the negative comonotonicity.
in practice due to its implicit nature.

---

error accumulation. This is similar to the convergence behavior of a stochastic version of Nesterov's 's fast gradient method [35 36], observed in [5], for smooth convex minimization.
Our main contributions are summarized as follows.
We propose the FEG method that has an accelerated convergence rate (11/k²) on the squared gradient norm for smooth structured nonconvex- -onoooocveeee minimax problems.
We present that the FEG method has a rate faster than those of the EAG and the Halpern iteration for smooth convex-coneave problems.
We construct a backtracking line-search version of FEG, named FEG-A, for the case where the Lipschitz constant and comonotonicity parameters of unavailable.
We analyze stochastic version FEG, named S-FEG, for smooth convex-coneave prob- lems.
2 Related work
2.1 Methods for convex-concave minimax problems
The extragradient method [19 is one of the widely used methods for solving smooth convex-concave
minimax problems (see, e.g., 7 22 24 26
44 for its extensions and applications). In terms
of the duality gap, maxy'ey [ the ergodic iterate of the extragradient-type methods [32 37 have an O (1) rate. Such (1//k)
min ex f(x', y), where X' and y are compac domains,
rate on the duality gap order-optimal for the first-order methods 34 38 leaving no room for improvement. On the other hand, the last iterate of the extragradient method has a slower (L)vV) rate on the duality gap, under an additional assumption that F has Lipschitz derivative [9]. In terms of the squared gradient norm, Fxll?. the best iterate of the extragradient type methods [19 39 have an (11/k) rate [40] 41 43 The last iterate of the extragradient method also has a rate O(1/k) when further assumed have a Lipschitz derivative
9 Unlike the duality gap, the (11 (1)/)) rate on the squared gradient norm is not optimal 45 From now throughout this paper, we mainly study and compare the convergence rates on the squared gradient norm, which still has room for improvement in problems, unlike the duality gap.
problems, and has meaning for nonconvex-nonconean minimax
Recently, 17 21 40
found that Halpern-type 12 (or anchoring) methods yield fast O(1/k²)
rate in terms the squared gradient norm for minimax problems. [7 showed that the (implicit) Halpern iteration [1] with appropriately chosen step coefficients has an ((1/k²) rate on the squared norm of a monotone F. Then, for a cocoercive F, an (explicit) version of the Halpern iteration was studied in 17 that has the same fast rate. In addition, 6 constructed a double-loop version of the Halpern iteration for Lipschitz continuous and monotone F, which has rate (11/k²) on the squared gradient norm, slower than the rate (l1 While this is promising compared to the O(1/k) rate of the extragradient methods on the squared gradient norm 40 41 43 the computational complexity due to its double-loop nature and a relatively slow rate remained a problem. Very recently, 43 proposed the extra anchored gradient (EAG) method, which is the first (explicit) method with fast (1/k²) rate for smooth convex-cones conccvve minimax problems, i.e., for Lipschitz continuous and monotone operators. In addition. 43 proved that the EAG is order-optimal by showing that the lower complexity bound of first-order methods (11k2²)
Cocoercive
Monotone
C
Negative comonotone IN
In MVI
S
Weak MVI
Figure 1: Relations between the conditions F.
"The convergence analysis on the duality gap of the extragradient type methods are generalized under the
unbounded domain assumption [28 29 30

---

2.2 Methods for nonconvex-noncomnce minimax problems
Some recent literature considered relaxing the monotonicity condition of the saddle gradient operator to tackle modern nonconvex-nonccocave minimax problems. For example, the Minty variational inequality (MVI) condition, i.e., there exists 2, E Z, (F)) satisfying (Fz,
2.) 2 for all
24 This condition is also studied under the name, the coherence, in [26] 42 44]. Moreover, 7 considered weaker condition, named the weak MVI condition, i.e., for some p < O, there exists 2, E (F)) satisfying
RR where (F) {z, E R Fz, 0). studied in 4 23
2F 2.) 2 p|| Fx| for all R The weak MVI condition is implied by the negative comonotonicity [ or, equivalently, the (positive) cohypomonotonicity 3 The comonotonicity will be further discussed in the upcoming section.
showed that the extragradient-type methods have an (11/k) rate on the squared gradient norm under the MVI condition, and 7 developed the (EG+) method under the weak MVI condition (and thus under the negative comonotonicty), which also has an OL1/k) rate the squared gradient norm. To the best of our knowledge, there is no known accelerated method for the nonconvex- nonconvex-nonconeaay nonconcave setting: our proposed FEG method is the first method to have fast (1/k²) rate under the of the existing methods and the FEG on the squared gradient norm are summarized in Table
For T--Lipschitz continuous
setting. The convergence rates
Table 1: Comparison of the convergence rates of the existing extragradient-type methods and the FEG, with respect to the squared gradient norm, for smooth structured minimax problems, under various assumptions on the Lipschitz continuous saddle gradient operator F.
Convex-concave
Nonconvex-nonconcavy
Method
Cocoercive Monotone Negative comonotone MVI
Weak MVI
EG
O(1/k)
((/kk)
(1/kk
Normal
EG+
((1/k)
(1/kk)
O(1/k)
(11/k) O(1/k)
Halpern 12 6
O(1/k²)
((1/k2)
Accelerated
EAG
((1)12)
O(1/k2)
FEG (this paper)
O(1/1²)
O(1/k²)
0(1/k2)
3 Preliminaries
The followings are the two main assumptions for the saddle gradient operator of the smooth structured nonconvex-noncoocaav problem ( Under such assumptions, we develop efficient
methods that find first-order stationary point z. E Z. (F) where ZF( == {z. Rd Fz, 0}.
Assumption 1 (L-Lipschitz continuity). For some L (0, oo), F satisfies
Fz - Fz'll S T.I| - z'11, Vz, z' ER.
Assumption 2 (p-Comonotonicity) For some p ( EL o0), F satisfies
FFz z x²) 2 F F2' v',z'e
The p-comonotonicity consists of three cases depending on the choice of yt the negative comono- tonicity when م < 0, the monotonicity when O, and the cocoercivity when p >> 0. The negative comonotonicity is weaker than the other two, and is the main focus of this paper. The following an
examplary nonconvex nonconcave condition that is stronger than the negative comonotonicity 3
Example 1. Let f be twice contimuously differentiable and w-w.aaly-comeeewwwllyyyoe ther assume that satisfies
Fur-
V2
f(n 1) ye 2 al, V2
(2)
xy
V2 Ny
2
f
fn
- al,
for some a 2 and n > ", named a 2 0-interaction dominant condition [... Then, the saddle
grudient of J satisfies the fhte----negaee ---negutive comonotonicity. (See Appendix A. For any y-weakly- conver-weakly-comcuyy function, the condition 2 holds with -y < O. Its extreme case is

---

f(z -- 3.y where there is no interaction between a and y. On the other hand, when the
the second terms in the left-hand side of 2 are sufficently positive definite, nonconvex-nonconar function satisfies the condition (2) with nonnegative a. In specific, the 2 O-interaction dominant condition is satisfied when the interaction term of Hessian V2 wy is dominating any negative curvature in Hessians Ff and gy ATTV.
We next present proposed FEG, and illustrate that the FEG outperforms existing methods such as EG+, EAG, and the Halpern iteration, for each three comonoticity case, respectively.
4 Fast extragradient (FEG) method for Lipschitz continuous and comonotone operators
This section considers instance of Class FEG) with ag = 7,, 3. R and PV: p for all k
-
The resulting method, named FEG, is illustrated in Algorithm [ which has an (1/k²) fast rate with respect to the squared gradient norm, in Theorem 4.1 The proof of Theorem 4.1 is provided in Section
Algorithm 1 Fast extragradient (FEG) method
Input: 2n E R L E (0, xo), P E
ZL. 00)
for =0, 1,., do
Ek+1/2 = 2k +
(20 - 2x.) - -(1
k + -1-)-(1-k++ (
1
+ +2p) Fzz.
k +
T
Zk+1 = 24 +
(20 - 2x.) - FZ
(1- k: +
1
2p zn.
++
T.
end for
Theorem 4.1. For the L-Lipschitz continuous and p-comonotone operator F with p p> 21. and for
any 2, E (F), the sequence {2 k20 generated by FEG satisfies, for all k 2 1,
4 20
z. 12
|
(3)
2p)
2.2
The following example shows that the bound (3) of the FEG exact for p and k: 4/ + 2. The bound (3) is not known to be exact in general, and we leave finding the exact bound as future work.
Example 2. Let f R x R + R be f(x y) = Lay- Its saddle gradient operator and solution F(r,V) v) (Ly, - Lx)) and z. (0,0), respectively. For the initial point 2o (Io, yo) O). the sequence { Zz 12z0 generated by FEG satisfies 2u122 (0, 2/211 for all 1 0. Hence,
| FF2222212
1a 412 22 for all 2 (See Appendix B.1
(2++1)=
(4++2)²
We next compare the rate bound with existing analyses for the three cases 1 < 0,
and > 0.
4.1 Comparison to EG+ under the negative comonotonicity (p < 0)
Under the negative comonotonicity with < p < O. the (EG+) method with ag 27. and , has an ( /k) rate on the squared gradient norm. To the best of our knowledge, this is the best known rate, and the FEG has faster (1/kk² rate with wider region of convergence
2L < p < 0.
4.2 Comparison to EAG under the monotonicity (p
For an L-Lipschitz continuous and monotone operator F. 43 proposed two EAG methods, named EAG-C and EAG-V. V, with same 3x 1
k but with different choices ag. EAG-C sets &s to
be constant 8Z
for all A 2 0 in (EA)). and has large constant 260 in its convergence rate,
5

---

10
EG-
EAG-C
EAG-V
10
Halpem
FEG
[[Fa 1
10
10
10
10
Iterations
Figure 2: Numerical result with fax y) - 2 xy J.y2 The dashed line represents the theoretical bound of FEG.
|2 <
360L"||z0=2.11 for all 1: 2 0. On the other hand, while EAG-V requires a complicated (K+1)2
recursive update for {a a++1 T-a (1
(E+1)(+33) (#+ L. for all l: 2 with og 0.618
(K42))
its rate has a smaller constant 27.
The FEG takes a constant Or I. unlike EAG-V, but has an even smaller constant 4 in its 4L -1-11=0-=-11"" for 0. Therefore, the FEG with 0 has about 260/4-times and 27 27/4-times faster convergence rate compared to those of EAG-C and EAG-W V, respectively. Furthermore, the rate bound of FEG with lower complexity bound of first-order methods under the considered setting 43) reducing the gap between the lower and upper complexity bounds from 27 to 4.
convergence rate ||
is only about 4-times larger than the
4.3 Comparison to the Halpern iteration under the cocoercivity (p
For p-cocoercive operator F, an (explicit) version of Halpern iteration 12 studied in 6). has fast rate, Fz ||2 < -=11= there case where the p-cocoercive (and thus Lipschitz continuous) operator has a Lipschitz constant 11 that L smaller than 1 Since L < J. the FEG has rate 1 < 41. (1/L+20)*'E 41 9p-
5"k Note that while the p-cocoercivity implies the L-Lipschitz continuity,
is faster than that of Halpern iteration. However, if take into account that the FEG requires computing the saddle gradient twice per iteration, unlike Halpern iteration studied in [6] the FEG method has slower rate in terms of the number of gradient computations. If we narrow down to
the case L < 2p the FEG has faster rate, |2 < 41|zo
|==1 For such case, 4p
(T/L+2p)ag2
the FEG has a rate faster than that of the Halpern iteration, even in terms of the number of gradient computations.
4.4 Toy example
We performed toy experiment on a simple quadratic function, f(x,
eL² - p2
2 y² which has an L-Lipschitz continuous and p-comonotone saddle gradient. For the case 3I and L 1, Figure illustrates that the FEG converges with an accelerated rate whereas EG+, EAG-C, EAG-V, and the (explicit) version of Halpern iteration [6] diverge. This example presents that the existing guarantees convergence and acceleration of the aforementioned methods setting.
eL.²
under the convex-concave setting do not generalize to the
FEG with backtracking line-search
The FEG requires the knowledge of the two global parameters T. and p for Lipschitz continuity and comonotonicity, respectively. Those global parameters often difficult to compute in practice

---

and can be locally conservative. To handle these two disadvantages, we employ the backtracking line-search technique [ 25 3T] in FEG. We adaptively decrease the two step size parameters, and 17. satisfy the both conditions, the local L-Lipschitz continuity and the "- comonotonicitt A pseudocode of the resulting method, named FEG-A, is illustrated in Algorithm 2 For detailed description of the FEG-A, see Algorithm in Appendix C.T
Algorithm Fast extragradient method with adaptive step size (FEG-A)
Input: 2g E R T-1 E (max (0, -2p}, oo), ?/ E (0, 00), 8 (0, 1)
Find the smallest nonnegative integer in such that & = Zo - T-1(1 6)¹0 Fzo satisfies F
Fzol S 71- | zull.
To T-1 T-1 5)0 21 20 F2.
for = 1.2....d do
i ju 0.
Increase each in and ja one by one until
(20 ((x) (1 1: 1ik 11- 873h Fzu
1
2k+1/2 = 2か + +
and
1
Ek+1 zi + +
(20- =zx) -T- -8)² F26+11/2
(mk-1 8) -T- - F
+
satisfy both conditions,
1
F F2 F22+1/211
8)1x || 2x+1/21l
and
-
(F Fzk, 2k+1 -2k) 1/k-1 111 8)5e -k--1(1 - 8)th F F
The = Th 1h-1(11 - 8) 7E = 1Tk-1(11 5)0h, 2k-1 = Ek+1-
end for
The following lemma shows that each of the nonincreasing sequences {Tu and { of the FEG-A has a positive lower bound, and thus FEG-A well-defined under the condition p > - - 1 of FEG, since the local Lipschitz This condition for & can be weaker than the condition > 21. parameter 1 can be smaller than L. This is another benefit of using backtracking line-search in FEG, over the standard FEG.
Lemma 5.1. For the L-Lipschitz and p-comonotone operator F and given constant ō E (0, 1), the step size Tyy of FEG-A is lower bounded by positive value I == min {T-1 1 for all k 2 and
if p > k 121 1.
Tv. the step size Ti lower bounded by positive value min No. (1 6) : + 2p) } for all
2
The FEG-A method also has the following O(1/k²) rate with respect to the squared gradient norm in Theorem 5.I. when p > - -7. The proof provided in Section 7 Iaand Appendix C.3
Theorem 5.1. For the L-Lipschitz and p-comonotone operator F and for any 2. E (F).). the sequence (22 generated by FEG-A satisfies
4||20 - 1=
|2 <
((I: 1)9) Tk 2p)²
for all k 2 1, Tk
This rate bound of FEG-A reduces to that of FEG in Theorem 71 = + + 2p for FEG-A.
when we choose T-1 1, and
'In specific, 7 and n) locally estimate 1 and 1 + 2p. respectively. One could have directly estimate instead
of + + 2p. but this complicates line-search process to handle both positive and negative values p. unlike our choice r in FEG-A.
"This requires
chooses T-1 strictly greater than the unknown value -2p when p 0.
7

---

FEG under stochastic setting
When exactly computing Fz is expensive in practice, usually instead consider its stochastic
estimate for computational efficiency (see, e.g., 13
16 26
42 44)). This section also
considers using stochastic oracle in FEG for smooth convex-coneane problems. In specific, this section assumes that we only have access noisy saddle gradient oracle, F #k F2/2/2 Ek/2- where (Ex/2 /:20 are independent random variables satisfying [B[x//2 = and B[]ls//2l| = 0 for all 0. Under this setting. we study a stochastic first-order method, named stochastic fast extragradient (S-FEG) method, illustrated in Algorithm
Algorithm 3 Stochastic fast extragradient (S-FEG) method Input: 20 R L (0, oo).
for 0, ",......0 do
1k-1/2 21: +
k (Zo 2xk)
(1
1
Fzz
k k+1 L
1
2k+1
2
k (#0
2x)
L
F2
end for
The following theorem provides an upper bound of the expected squared gradient norm for the S-FEG. (See Appendix[D.3) 3 for the proof.)
Theorem 6.1. Let Fzu/2 Fz + Ex/2, where (Ex/2)k20 are independent random variables satisfying E[Sx/2] = and /E|lEx/2ll o k/2 for all O. Then, for the L-Lipschitz continuous
and monotone operator F and for any z E (F).), the sequence {z generated by S-FEG satisfies
F2
4L2 20
2.
k-1
(P of + +
1:2
122
for all k 2 1. Furthermore, of 4 reduces to
0
<
and k+1/2
S 8iKtス for all k 2 1, then the bound
6k
4L
20
2. 1|
E|| Fz
+
122
for all k 2
Here, we needed the noise variance //2 to decrease in the order of O(1/k) so that the stochastic error of the S-FEG does not accumulate. Otherwise, if 2 constant for all k,, the error accumulates with rate O(k). In short, the S-FEG will suffer from error accumulation, unless the stochastic error decreases with rate (11/k). Such error accumulation behavior also appears in stochastic version of Nesterov's s fast gradient method [35] 36) for smooth convex minimization [5 []. Similar to (5),
we believe that adjusting the step coefficients of the S-FEG can make the S-FEG become relatively
stable even with a constant noise, which we leave as future work.
7 Convergence analysis with nonincreasing potential lemma
We analyze FEG and FEG-A by finding nonincreasing potential function in form Vi a 1 by F zk. Zu 2x) in the lemma below. We provide a similar potential lemma for S-FEG in Appendix D.2 The convergence analyses of EAG and Halpem iteration also based on such potential function 43].
Lemma 7.1. Let {#u J be the sequence generated by CCass FEG with {au {8x Ja20 (La (0, oo) and {pu)as Ja2o C IR satisfying ox E (0, x)), an E (0, +. 30 = 1, (Bx)221 C
(0, for all l 2 1, and
(1 Bk+1)
1
(a0+1 + 2px41) Pk++1 5
(ax + 2px) Pk
28p+1
2,h
8

---

for all k 2 0. Assume that the following conditions are satisfied.
1| F2 F Fo
< Lo 2 - zoll
F
F
1/21 L Zx+1 2k+1/2ll for all k 2 1,
FFZt+1
Fzk: 2x+1
2k) 2 Pk: Fzk+1 Fzx 112
for all t: 2 1.
Then the potential function
V& 0k F2z by (Fzk. 20 2k)
co(Li 1)
with ag
2 bo 0, bn = 1,
by Bk)
by
(ar + 2pk) bkPk and bx+1 - Bx
23x
for all k 2 1 satisfies V22 S for all 2 1.
Based on the above potential lemma, we next provide a convergence analysis of FEG. The analyses for the convergence rate of FEG-A and S-FEG, i.e., the proofs of Theorem 5.] and Theorem 6.1 are similar to that of FEG and are provided in Appendix C.3 and Appendix D.3
7.1 Convergence analysis for FEG
Proof of Theorem 4.1 Recall that FEG is equivalent to (Class FEG with on 1. 3 E+I and Pk p. It is straightforward to verify that the given fax k20 and {8k satisfy the conditions in Lemma with L2 for all & 2 O. Since
by( B&)
h22
0g
2B3
(a:: + 2pk) - bkPk
2
L
+ 2p) - kp
and
k-1
bk 1 - Bx-1
bk-1
b k,
- B
Lemma
7.1
implies that
2
Vo
2
V/2 =
+ +2p) - -kp)
| (FZz: 20 - 2x)
2 I
Therefore,
k2
+ 2p)
F2 2/
< (Fzk, 20
2σ) +kipl (/
T
k (Fzi, 20
2.)
*k (FZz; z. 2x) +kpl| Fzxl
< (Fz 20 2.)
(: comonotoniiii of F))
< Fz 20 2=
The desired result follows directly by dividing both sides by 1² (t + +p) Fzull.
Discussion: first-order methods for Lipschitz continuous operators
Throughout this paper, we studied and constructed efficient methods in class of first-order methods:
E + span Fzo. ..... FFz)
denoted by A. for smooth structured nonconvex-nonccocavve problems. We observed that all existing first-order methods, including the FEG, required an additional condition, such the negative comonoticity, on a Lipschitz continuous F to guarantee convergence. One would then be curious whether or not there exists (efficient) method in class A that guarantees convergence without any additional condition on Lipschitz continuous F. Unfortunately, the following lemma states that there exists a worst-case" smooth example that none of the methods in A can find its stationary point. The corresponding smooth function is illustrated in Figure 3
[15 20 also introduce worst-case minimax examples that existing methods cannot find a stationary point. A key difference from our example is that their saddle-gradien operators are not Lipschitz continuous. In addition, the considered classes of methods in [15 20 exclude EG+ and FEG, unlike the class A.

---

0.5
f(a, M)
-0.
0
0.5
-0.5
Figure 3: smooth worst-case example f(x y) 5 with I. R 1 for first-order methods. any sequence {= generated by first-order method in class A starting from (0, 0) is contained in the line x y-
Lemma 8.1. Let us consider the following function f : IR² - foror some L, R > 0:
R
for V R
2 (xr - y) VLR(x - 1) for / S <
f(x, v) =
(5)
(xx y) - VLR(z for S Z < + V
R
for + v E <r.
Its saddle- gradient operator F is L-Lipschitz continuous but not comonotone R Then, the sequence (2x)u20 ):20 generated by any first-order method class A with zq = (0,0) satisfies F2 = 2LR for all k 2 O.
Proof. F satisfies F(x, y) = (-VLR, LVRR whenever y. Hence, for all sequences { J22
satisfying 2g (0, 0) and 25 E 2g + $ ... zz } for all 2 we have that {* J220 S === (x. E R2 J y): thus, F2 12 2LR for all k 2 0.
The lemma implies that one should consider class methods, other than the class A, to guarantee finding stationary point of any smooth problem, which we leave as future work. We also leave finding additional conditions for a Lipschitz continuous F, weaker than the weak MVI condition and the negative comonotonicity (with p 2T.). which guarantee convergence its accelerated rate, respectively, as future work.
Conclusion
This paper proposed wwo-time-seut and anchored extragradient method, named FEG, for smooth structured nonconvex -onconcave problems. The proposed FEG has an accelerated (11/k²) rate, with respect the squared gradient norm, for the Lipschitz continuous and negative comonotone operators for the first time. The FEG also has value for smooth concave problems, compared to existing works. We further studied its backtracking line-search version, named FEG-A, for the problems and studied its stochastic version, named S-FEG,
smooth structured munconvex-nonconeee for smooth convex-concave problems. We leave extending this work stochastic, composite, or more general nonconvex-nonconee setting and applying to more realistic problems as future work.
B) and (0,0). Since Fz (0,0) and Fw (-VLR, get (Fx Fw, - w) LVL + R and Fx Fwol2 2LR, which implies that p -00 in the comonotonicity condition
'Let
10

---

Acknowledgments and Disclosure of Funding
This work was supported part by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2019RIASA (122022)4,) the POSCO Science Fellowship of POSCO Park Foundation, and the Samsung Science and Technology Foundation (No. SSTF- BA2101-02).
References
[1] H. H. Bauschke, W. M. Moursi, and X. Wang. Generalized monotone operators and their averaged resolvents. Matematical Programming, 189(1):55-74, 2021.
[2] A. Beck and M. Teboulle. A fast iterative shrinkage-threshollnng algorithm for linear inverse problems. SIAM Imaging Sci., 2(1):183-2044 2009.
[3] P. L. Combettes and T. Pennanen. Proximal methods for cohypomonotone operators. SIAM J. Control Optim., 43(2):331 2004.
[4] C. D. Dang and G. Lan. On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators. Computational Optimization and Applications, 60(2):277-310, 2015.
[5] O. Devolder. Stochastic first order methods in smooth convex optimization, 2011.
[6] J. Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions variational inequalities. Conference on Learning Theory, pages 1428-1451. PMLR, 2020.
[7] Diakonikolas, C. Daskalakis, and M. Jordan. Efficient methods for structured nonconvex- nonconcave min-max optimization. In International Conference on Artificial Intelligence and Statistics, pages 2746-2754. PMLR, 2021.
[8] S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59- March 2016.
[9] N. Golowich, S. Pattathil, C. Daskalakis, and A. Ozdaglar. Last iterate slower than averaged iterate in smooth convex-concave saddle point problems. In Conference Learning Theory (COLT), 2020.
[10] J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial networks. Neural Info. Proc. Sys., 2014.
[11] B. Grimmer, H. Lu, P. Worah, and V. Mirrokni. The landscape of the proximal point method for nonconvex-nooncomaaee minimax optimization, 2020.
[12] B. Halpemn Fixed points of nonexpanding maps. Bull. Amer. Math. Soc, 73:957-961, 1967.
[13] Y.-G. Hsich, F. lutzeler, Malick, and Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In Neural Info. Proc. Sys., 2019.
[14] Y.GG. Hsieh, F. Tutzeler, J. Malick, and P. Mertikopoulos. Explore aggressively, update conser- vatively: Stochastic extragradient methods with variable stepsize scaling. Neural Info. Proc. Sys., 2020.
[15] Y.P. Hsieh, Mertikopoulos, and V. Cevher. The limits min-max optimization algorithms: convergence spurious non-critical sets. In Proc. Intl. Conf. Mach. Learn, 2021.
[16] A. Juditsky, A. Nemirovski, and C. Tauvel. Solving variational inequalitics with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[17] D. Kim. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, 190(1):57-87, 2021.

---

[18] U. Kohlenbach. On the proximal point algorithm and its Halpern-typa variant for generalized monotone operators in Hilbert space. Optimization Letters, 2021.
[19] G. M. Korpelevich. An extragradient method for finding saddle points and other problems. Ekonomika i Mateaticheskie Metody, 12(4):747-56, 1976.
[20] A. Letcher. On the impossibility of global convergence in multi-loss optimization. In Proc. Inll. Conf. on Learning Representations, 2021.
[21] Lieder. On the convergence rate of the Halpern-iteratinn Optimization Letters, 15(2):405-418, 2021.
[22] M. Liu, Y. Mroueh, J. Ross, W. Zhang, X. Cui, P. Das, and T. Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. In International Conference on Learning Representations, 2020.
[23] M. Liu, H. Rafique, Q. Lin, and T. Yang. First-order convergence theory for weakly-convex- weakly-concave min-max problems. J. Mach. Learning Res., 22(169):1-34, 2021.
[24] Y. Malitsky. Golden ratio algorithms for variational inequalities. Mathematical Programming, 184(1):383-410, 2020.
[25] Y. Malitsky and T. Pock. A first-order primal-dual algorithm with linesearch. SIAM Journal on Optimization, 28(1):41 1-432,, 2018
[26] P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Opti- mistic mirror descent in saddle-point problems: going the extra (gradient) mile. In Proc. Intl. Conf. on Learning Representations, 2019.
[27] A. Mądry, A. Makelov, L. Schmdit, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In Proc. Intl. Conf. on Learning Representations, 2018
[28] A. Mokhtari, Ozdaglar, and S. Pattathil, A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In Proc. Intl. Conf. Artificial Intelligence and Stat. (AISTATS), 2020.
[29] R. D. C. Monteiro and B. Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM J. Optim., 20(6):2755-87. 2010.
[30] R. D. C. Monteiro and B. F. Svaiter. Complexity of variants of Tseng's modified FB splitting and Korpelevich's ' methods for hemivariational inequalities with applications to saddle- saddle-point and convex optimization problems. SIAM Journal on Optimization, 21(4):1688-1720 2011.
[31] M. C. Mukkamala, P. Ochs, T. Pock, and S. Sabach. Convex-concave backtracking for in- ertial bregman proximal gradient algorithms in nonconvex optimization. SIAM Journal on Mathematics of Data Science, 2(3):658 682, 2020.
[32] A. Nemirovski. Prox-method with rate of convergence (11/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Optim., 15(1):229-51, 2004.
[33] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19(4):15746609, 2009.
[34] A. Nemirovski and D. Yudin. Problem complexity and method efficiency in optimization. wiley, 1983.
[35] Y. Nesterov. method for unconstrained convex minimization problem with the rate of convergence O(1/k²). Dokl. Akad. Nauk. USSR, 269(3):543-7,, 1983.
[36] Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127-52 May 2005.
[37] Y. Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming. 109(2-3)3319444 March 2007.
12

---

[38] Y. Ouyang and Y. Xu. Lower complexity bounds of first-order methods for convex conve--concaee bilinear auddle-point problems. Mathematical Programming. 185(1):1-35, 2021.
[39] L. D. Popov. A modification the Arrow-Hurwicz method for search of saddle points. Mathemalical notes of the Academy of Sciences of the USSR, 28(5):845-8, November 1980.
[40] E. K. Ryu, K. Yuan, and W. Yin. ODE analysis of stochastic gradient methods with optimism and anchoring for minimax problems and GANs, 2019. arxiv 1905.10899.
[41] M. V. Solodov and B. F. Svaiter. A hybrid approximate extragradient-proximal point algorithm using the enlargement of maximal monotone operator. Set-Valued Analysis, 7(4):323-345, 1999.
[42] C. Song, Z. Zhou. Y. Zhou, Y. Jiang, and Y. Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. Neural Info. Proc. Sys., 2020.
[43] Yoon and E. K. Ryu. Accelerated algorithms smooth convex-conean minimax problems with (1/kk² rate squared gradient norm. In Proc. Intl. Conf. Mach. Learn, 2021.
[44] Z. Zhou, P. Mertikopoulos, N. Bambos, S. Boyd, and P. Glymn. Stochastic mirror descent in variationally coherent optimization problems. Neural Info. Proc. Sys., 2017.
13


Reviews:
[{"review_id": "vX6ySz6FPI", "reviewer": "Reviewer_VnM6", "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.  ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Main Points:\n- 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. \nQuality: 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. \n\n- Clarity: The paper is very clear and well written\n- Originality: The proposed method is novel, and the analysis with accelerated rates is new and very relevant to the community. \nThe 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. \n\n### Conclusion:\nBesides 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.\n\n### Minor comments: \nL239: $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$. \n\n### Reference:\nHsieh, 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.\nLetcher, Alistair. \"On the impossibility of global convergence in multi-loss optimization.\" ICLR 2021.\n\n### After Rebuttal\nAfter the discussion with the authors, I decided to maintain my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "r3zsTgcEFzf", "reviewer": "Reviewer_ifPf", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThere are several major issues in this paper:\n1.\tIn 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).\n2.\tThe update rules in Algorithm 1 depends on the parameter \\rho.  In a practical min-max problem, how to determine the parameter \\rho?\n3.\tAlthough the paper is theoretically sound, there is a lack of experiments to verify the proposed algorithms.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1.\tIn 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).\n2.\tThe update rules in Algorithm 1 depends on the parameter \\rho, for a practical min-max problem. How to determine the parameter \\rho?\n3.\tAlthough the paper is theoretically sound, there is a lack of experiments to verify the proposed algorithms.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "72"}, "extra_text": {}}, {"review_id": "i7iJRCkAOHw", "reviewer": "Reviewer_KwBn", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\n[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. \n\nThe 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. \n\nThe 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$. \n\nI do not get the second last line in the equation following Line 239. Please explain. \n\nThe presentation is clear. I suggest the authors indicate where the reader can find the proof of Theorem 4.1 after presenting the theorem. \n\nI do not check all proofs in the supplementary material. \n\nTypos: \n- Line 104: The lower bound should not be expressed in big-O. \n- Line 228: *the* potential function\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please address the issues I raised in the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "CRmRJoYuCq-", "reviewer": "Reviewer_NehK", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nFrom 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.\n\nThe 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?\n\nPresentation: 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.\n\nExamples: 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.\n\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)