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 aaadeeggaddeet 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 CA.. 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-noncomnee 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
fnl
- al,
for some a 2 and n > ", named a 2 0-interaction dominant condition [... Then, the saddle
grudient of J satisfies the fite----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,
| FF2122212
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 <
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 1
EAG-C and EAG-V. V, with same 3x
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 is 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 2k
< (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-422,, 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 for 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": "yayhmKtT3lN", "reviewer": "Reviewer_ukbE", "summary": "The authors focus on the problem of unconstrained min max optimization by finding approximate stationary points of non convex non concave landscapes. These landscapes are not arbitrary, they satisfy the \\rho- comonotonicity ( a notion that captures  cocoercivity and monotonicity, and many more classes of functions). They design an accelerated extra gradient method that gives an \\eps approximate stationary point (norm of gradient is at most \\eps) in time 1\\eps. Note this is optimal even in convex optimization for smooth functions (standard GD gives 1/eps^2, Nesterov's method gives 1/\\eps). Stochastic analysis of the method is also provided.", "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": "This is an interesting result and the iteration complexity of the provided method is optimal. I think it is a solid contribution for a non trivial class of functions that include well studied classes. My main comment is that the authors mention that they tackle structured non convex non concave landscapes (in the abstract and later). They should rephrase it because they focus on a specific class of non convex non concave functions and sounds like overselling. Technically the paper is okay (accelerated extra gradient has appeared in other paper which are cited, nothing of great novelty here) but the authors should put some work on explaining key technical differences between their paper and the literature (on monotone, mvi etc). Another comment is that the authors mention all their results in terms of the square of the norm of the gradient, i think the norm of the gradient would be more preferable.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is theoretical and the reviewer does not see any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "m6vlwTEvVOV", "reviewer": "Reviewer_GXGY", "summary": "This paper studied nonconvex-nonconcave minimax optimization with smooth and comonotonicity assumptions and proposed fast extragradient (FEG) algorithm which has O(1/k^2) convergence rate. The authors also proposed a line-search strategy to improve the algorithm in practice and extended FEG to stochastic case.", "questions": "", "limitations": "", "rating": 5, "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": "This paper studies nonconvex-nonconcave minimax optimization with smooth and comonotonicity assumptions. The authors combine the idea of EG+ and EAG which leads to a two-time-scale EG with anchoring, named fast extragradient (FEG), that has a fast $O(1/k^2)$ convergence rate on the norm of the gradient. The paper also propose a backtracking line-search variant the problem parameters are not available and extended the algorithm to stochastic case.\n\nThis paper improves the convergence rate of nonconvex-nonconcave minimax optimization under comonotonicity assumptions. My main consideration is why such setting is useful. Example 1 connects the assumption to $\\alpha$-interaction dominate condition, however, it is no clear which types of problem satisfies $\\alpha$-interaction. \n\nIt is also desired to see some numerical experiment to validate the effectiveness of the theory, since the extension of FEG are proposed for implementation in practice. The audience of NeurIPS are more interested in the optimization algorithm related to machine learning models. Hence, I hope the author need to provide more discussion for the applications of the proposed algorithms.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretical.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "dnTb1iAjXTJ", "reviewer": "Reviewer_h3Zc", "summary": "This paper develops the FEG method for solving smooth structured nonconvex-nonconcave minimax problems. It is proved that FEG has an accelerated convergence rate $O(1/k^2)$ on the squared gradient norm, which is the first accelerated method under the nonconvex-nonconcave setting. Moreover, it is shown that the FEG method has a rate faster than those of the EAG and the Halpern\niteration for smooth convex-concave problems. The authors further develop and study backtracking line-search and stochastic versions of FEG.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 very well written and developed sound results. The FEG method is the first accelerated algorithm for nonconvex-nonconcave problems with negative-monotonicity. Therefore, this paper makes a solid contribution to the existing literature. \nBelow are some questions.\n\n1. From the analysis in sec 7.1, it is not clear how the reused $Fz_k$ term in FEG help achieve an accelerated convergence rate? How substantial would the proof be different from that of EAG?\n\n2. I think it is important to numerically compare this algorithm with the competitive algorithms mentioned in the paper. Given that FEG only introduces a reuse of $Fz_k$, it is not clear if this can easily accelerate the convergence in practice. \n\n3. The result of stochastic FEG has a bad dependence on the stochastic variance $\\sigma_k^2$. There are existing accelerated SGD analysis under constant noise variance, e.g., Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, Saeed Ghadimi · Guanghui Lan. This might be an interesting reference.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "dJtf-oZ3Fex", "reviewer": "Reviewer_xDiD", "summary": "This work proposes an accelerated first-order method for nonconvex-nonconcave minimax optimization. Critically the convergence theory relies on the objective being L-smooth and having at most a modest level of nonconvexity/nonconcavity (based on the comonotonicity being at most a 1/2L). For such problems, the method converges in gradient norm squared at a rate of 1/T^2, improving on the typical 1/T rate of similar extragradient-type methods. Extensions of this framework to utilize backtracking and stochastic oracle evaluations are provided. As a tertiary result, a clever example is given showing a gradient oracle alone can be trapped in a subspace without any stationary points.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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 Example 1, the work of Grimmer et al. does not use $\\gamma$-smoothness, but rather a weaker condition (called weak convexity-weak concavity therein). The proof in the appendix does not rely on smoothness, so this difference is minor.\n\nAfter defining comonotonicity, the paper defines three cases (negative, zero, and positive) implying the resulting theory would cover all three, most impressively the negative \\rho setting. It was disappointing then in the theory to see the results only cover a very limited range of negative \\rho (between -1/2L and 0). The paper should weaken its language when claiming a rate for negative comonotone problems as only a very limited class of these are able to be addressed by the theory presented.\n\nSection 4 presents detailed comparisons between derived guarantees in the three settings (limited negative rho, rho=0, and \\rho>0) with existing bounds. Much of the improvements are in terms of small constants: (i) The limited negative \\rho range is larger by a factor of four for FEG than EG+, (ii) The FEG constant is smaller than EAG by 4/27. Numerically, are these improvements realized? They are small enough that I suspect these differences may come from proof technique differences rather than actual improvements in optimization power.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "AGDA (Alternating Gradient Descent Ascent) provides a common first-order method that violates the requirements in Lemma 8.1. It would be interesting if a modified example could show limitations for methods in the span of the x and y gradient components separately.\n\nThe stochastic version of the algorithm presented is fairly weak. Requiring both convexity/concavity and the level of stochasticity to decrease as the method converges effectively removes much of the interesting stochastic benefits. The paper already acknowledges itself the importance of handling constant noise as a future direction.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new algorithm that can get 1/k^2 convergence rate for a class of structured smooth nonconvex-nonconcave minimax optimization problems, in terms of the squared gradient norm, improving over the currently known 1/k rate algorithm for the same problem. While the paper does not provide any practical example that falls into the class being analyzed here, the reviewers felt that the paper makes an interesting theoretical progress on the hard and challenging problem of nonconvex-nonconcave minimax optimization. Furthermore, the techniques developed in this paper can potentially lead to further work in this area. Consequently, I am recommending the paper for acceptance.
Decision: Accept (Poster)