Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems
Authors: Thomas Pethick
Puya Latafat
Panos Patrinos
Olivier Fercoq
Volkan Cevher
Venue: ICLR 2022 Spotlight (2022)
Keywords: Minimax
Nonconvex-Nonconcave
Variational inequilities
Saddle point problem
First-order methods
Limit cycles

Abstract: This paper introduces a new extragradient-type algorithm for a class of nonconvex-nonconcave minimax problems. It is well-known that finding a local solution for general minimax problems is computationally intractable. This observation has recently motivated the study of structures sufficient for convergence of first order methods in the more general setting of variational inequalities when the so-called weak Minty variational inequality (MVI) holds. This problem class captures non-trivial structures as we demonstrate with examples, for which a large family of existing algorithms provably converge to limit cycles. Our results require a less restrictive parameter range in the weak MVI compared to what is previously known, thus extending the applicability of our scheme. The proposed algorithm is applicable to constrained and regularized problems, and involves an adaptive stepsize allowing for potentially larger stepsizes. Our scheme also converges globally even in settings where the underlying operator exhibits limit cycles.

Published as a conference paper at ICLR 2022
ESCAPING LIMIT CYCLES: GLOBAL CONVERGENCE FOR CON- STRAINED NONCONVEX-NOONONCGVE MINIMAX PROBLEMS
Thomas Pethick* Puya Latafat
Panagiotis Patrinos
Olivier Fercoq*
Volkan Cevher*
ABSTRACT
This paper introduces new extragradient-type algorithm for a class of nonconvex-noncoocar minimax problems. well-known that finding a local solution for general minimax problems is computationally intractable. This ob- servation has recently motivated the study of structures sufficient for convergence of first order methods in the more general setting of variational inequalities when the so-called weak Minty variational inequality (MVI) holds. This problem class captures non-trivial structures we demonstrate with examples, for which a large family of existing algorithms provably converge to limit cycles. Our results require less restrictive parameter range in the weak MVI compared what is previously known, thus extending the applicability of our scheme. The proposed algorithm is applicable to constrained and regularized problems, and involves an adaptive step- size allowing for potentially larger stepsizes. Our scheme also converges globally even in settings where the underlying operator exhibits limit cycles.
INTRODUCTION
Many machine learning applications, from generative adversarial networks (GANs) to robust re- inforcement learning, result notorious difficulties to the scalable first order methods. Indeed, there is no shortage of results illus- trating divergent or cycling behavior when going beyond minimization problems (Benam & Hirsch, 1999; Hommes & Ochea, 2012; Mertikopoulos et al., 2018b; Hsieh et al., 2021).
constrained minimax problems, which pose
Traditionally, minimax problems have been studied for more than half a century under the umbrella of the variational inequalities (VIs). The extragradient-type algorithms from the VI literature was recently brought to the awareness of the machine learning community (Mertikopoulas et al., 201 8a; Gidel al., 2018: Böhm et al., 2020), and have provided principled way of stabilizing training and avoiding Poincaré recursions. However, these results mostly concern the convex-concave setting.
In eenconev minimax problems, or more generally nonmonotone variational inequali- ties (VIs), even finding local solution is in general intractable. This has been made precise through exponential lower bound of the classical optimization type (Hirsch & Vavasis, 1987) and computa- tional complexity results (Papadimitriou, 1994; Daskalakis et al., 2021b). This is in sharp contrast to minimization problems, where only finding a global solution intractable. The recent result of (Hsieh et al., 2021) provides some intuition behind this difference by showing that the asymptotic limits of most schemes, including extragradient, can converge to attracting limit cycles.
To make progress in lieu of these negative results, Diakonikolas et al. (2021) proposes a simple generalization of extragradient, called (EG+), that can converge to stationary point even for a class of nonmonotone problems provided that the weak Minty variational inequality (MVI) holds. This problem class is parametrized by a constant p. which controls the degree of nonconvexity. However, given the range of p in Diakonikolas et al. (2021), the class is still too small include the simplest counterexample of Hsieh et al. (2021) for the general Robbins-Mon schemes.
* Laborraoryy for Information and Inference Systems (L.OOSS) EPFL (thomas.pethick @epfl.ch)
I Department of Electrical Engineering (ESAT-STADIEE KU Leuven fI Laboratoire Traitement Communication d' I'Inorration, Télécom Paris, Institut Polytechnique de Paris

---

Published as a conference paper at ICLR 2022
CungummE
-05
-25
-10
-1.0
-10
-1.0
Figure Forsaken (Hsieh al., 2021, Example 5.2) provides an example where the weak MVI constant p does not satisfy algorithmic requirements of (EG+) and (EG+) does not converge to a stationary point but rather the attracting limit cycle (left). In contrast, adaptively choosing the extrapolation stepsize large enough with our method, called (CurvatureEG+), The repellant limit cycle indicated in black and the stream plot shows the vectorfield Fz. The blue and curves indicate multiple trajectories of the algorithms starting from initializations indicated black. See Appendix C.4 for properties of Forsaken.
sufficient for avoiding the limit cycles (right).
Contributions Building on the analysis in Diakonikolas et al. (2021), we propose a new adaptive scheme, called (CurvatureEG++) that converges even in the difficult counter example of Hsieh al. (2021) as illustrated in Fig. 1. Our main contributions are summarized below.
1. We propose an adaptive extragradient-type algorithm that converges for a larger range of p, the parameter in the weak MVI assumption (ef. Assumption I(iii) than previously known.
2. More importantly, tion stepsize. This is crucial since by selecting ys through a backtracking procedure larger stepsizes allowed, which in turn implies convergence for more negative values of p. thus capturing larger class of problems. In addition, we show that the linesearch eventually passes without triggering any backtrack if initialized based on the Jacobian of F (ef. Section 4).
show that convergence is ensured if 2p y: O, where ys is the extrapola-
3. We present non-adaptive variant of our algorithm (CEG+), and show that for particular pa- rameter choices (EG+) Diakonikolas et al. (2021), and when p the celebrated forward- backward- -owwwrdd (FBF) algorithm of Tseng (2000) recovered, thus unifying and generalizing both methods. We improve upon Diakonikolas et al. (2021) by not only relaxing the problem class but also the stepsize range. We show that our results are tight by providing matching lower bound, thus providing complete picture of (EG+) under weak MVI.
Related work The community has resorted to various approaches make progress for nonconvex-nonccocaae minimax problems. One line of work focuses on deriving local convergence results (Mazumdar al., 2019; Fiez & Ratliff, 2020; Heusel et al., 2017). For global results, the two primary approaches have been to either assume global oracle for the inner problem (Jin et al., 2019; Davis & Drusvyatskiy, 2018) or assume particular problem structure such the Polyak- Lojasiewicz condition (Nouiched et al., 2019; Yang et al., 2020) or concavity for the inner problem (Rafique al., 2019).
We follow the same tradition of assuming structure, but from the general perspective of operator theory. The idea of studying minimax and related problems through the lens of variational inequality has long history (Minty, 1962; Rockafellar, 1976; Polyak, 1987; Bertsekas, 1997), with recent renewed interest due to its relevance for minimax formulations (Mertikopoulos et al., 2018a; Gidel et al., 2018; Azizian et al., 2020).
One relaxation the monotone case for which we have positive results that of Minty varia- tional inequalities (MVI) (Mertikopoulos et al., 201 8a; Song et al., 2021; Zhou et al., 2017; Liu et al., 2021), which includes all waassiconvex-concaan and starconvex-conect las et al. (2021) introduced the relaxed condition of weak MVL. In the unconstrained setting they showed non -o-masymptoiic convergence results under a restricted problem constant p. Similarly to us, Lee & Kim (2021a) extends the regime but under the stronger condition of cohypomonotonicity.
problems. Diakoniko-
2

---

Published as a conference paper at ICLR 2022
They do by studying more evolved variant of extragradient building anchoring techniques. We instead directly improve upon (EG+) and generalize it to new settings.
In the stochastic setting, usually the stepsize for the extrapolation step is diminishing. This is the case in Böhm ct al. (2020) where they consider a wwwaardbbacwardd--oo they remain in the monotone setting, where the limit cycles non-attracting, exemplified by bilinear game. Hsieh et al. (2021) recently showed that a large family of algorithms, which includes the extragradient method with diminishing stepsize, can converge to attracting limit cycles. Going beyond this restriction, prior to Diakonikolas et al. (2021), Hsieh et al. (2020) interestingly considers two separate and diminishing stepsizes under the stronger assumption of MVI.
type scheme. However,
2 PROBLEM FORMULATION AND PRELIMINARIES
In this paper we are interested in finding zeros of an operator (or set-valued mapping) T: R" 3 R" that is written as the sum of a Lipschitz continuous (but possibly nonmonotone) operator F and maximally monotone operator A. That is, we wish to find E R" such that the general inclusion
0 Tz Az Fz
(2.1)
holds. The set of all such points is denoted by zer T == fz R" 1 Tz). Throughout the paper problem (2.1) is studied under the following assumptions (definitions can be found in Appendix A).
Assumption I. In problem (2.1),
(i) Operator A R" 3 R" is a maximally monotone operator.
(i) Operator F R² - R" is L-Lipschitz continuous.
(iii) Weak Minty variational inequality (MVI) holds, i.e., there exists a nonempty set S* S zer T such that for all z" E S* and some p E (- $,00)
<v,I-z²> > plvl?, for all (z, E gph
(2.2)
Generally, we do not require the weak Minty assumption to hold at every z" E zer zer In fact, as shown in Theorem 3.1 nonemptiness of S* is sufficient for ensuring that the limit points belong to zer T. Interestingly, despite nonmonotonicity of F, global (as opposed to subsequential) convergence can be established when S* zer T, assumption that is still weaker than cohypomonotonicity.
VIs provide a convenient abstraction for a range of problems. We mention some central examples below but otherwise defer the overview in Facchinei & Pang (2007). Subsequently, we provide examples where the weak MVI holds.
Example 1: (minimax optimization). A comprehensive way capture wide range of applications in machine learning is to consider structured minimax problems of the form
minimize maximize L(x.)) y) ypxx,y g(x) h(y).
(2.3)
xx Rd
where is not necessarily convex in x or concave in y. Functions and h are proper extended real-valued lower semicontinuous and convex, with easy to compute proximal maps. Common ex- amples for and h involve regularizers such as l,, l2 norms, or indicator functions of sets al- lowing us to capture constrained minimax problems. The first order optimality condition asso- ciated with this problem may be written in the form of the structured inclusion (2.1) by letting Fz (V.4(x.)). Vx,4(x. Az = (Ōg(x), Ōh(y)).
As it will become clear in the next section (cf. Algorithm 1), the main computations involved in the proposed scheme are evaluations of F and resolvent JA (id + A) Recall that the resolvent of maximally monotone operator is firmly nonexpansive with full domain (cf. (Bauschke & Combettes, 2017, Sect. 23)). If ôf is the subdifferential operator of convex function f. then its resolvent the proximal mapping. For instance when A is as Example 1, then its resolvent is given by Jx(x,y) (prox, (x), (y)).
Example 2: (N (N-player games). More generally, we can consider a continuous game N players in normal form. Denote the decision variables z z-)) (zi.... ZN) and let the loss incurred by
3

---

Published as a conference paper at ICLR 2022
the 1th player be Z((zzz-1) = (i(z)) gi(2i) where oi is the payoff function and & typically enforce constraints on Z4. Then we seek a Nash equilibrium, which is any decision which is unilaterally stable, i...
=() < ((8e2))) Vz, and e [M] = (I.....NN.
(2.4)
The corresponding first order optimality conditions may be written as Az (fg.(2))....,, (gN((Z)) and F2 (V), (x)(()))
solution to (2.1) thus returns a candidate for which the first order condition of the above problems is satisfied. In the monotone case these two solution concepts coincide, while in the more general case of weak MVI, we provide examples where this still holds. In particular, we introduce in Sec- tion 5 nonconvex-noncoonaae minimax game which additionally exhibits limit cycles for Fz. As a consequence most schemes including gradient descent ascent, extragradient and optimistic gradi- ent descent ascent do not converge stationary point globally (Hsich et al., 2021). However, the global Nash equilibrium satisfies Assumption I(iii) with p - 1/2,, which we show is sufficient for global convergence of (CEG+).
The weak MVI condition is satisfied in certain reinforcement learning settings. Specifically, Di- akonikolas al. (2021); Daskalakis al. (2021a) considers a two-player zero-sum game where the weak MVI holds, while neither MVI nor cohypomonotonicity holds. Interestingly, the formulation requires constraint condition they do not handle. We thus provide the first provable algorithm for this setting. Weak MVI also contains all quasiconvex-conett For further examples, the literature on cohypomonotonicity (Bauschke et al., 2020) is relevant since it implies weak MVI, see for instance Lee & Kim (2021b, Example 1).
and starconvex-concat
problems.
3 GENERALIZING EXTRAGRADIENT+
Our starting point is the Extragradient+ (EG+) algorithm of Diakonikolas et al. (2021) which is identical to extragradient (Korpelevich, 1976) except for the second stepsize being smaller. They only treat the inclusion (2.1) when = 0, and in our notation require p E (-1/st, 0]. Specifically, (EG+)
전 = ć Fz. t+1 + - F
where they choose = 1/2 and ā₁ = 1/2 (Diakonikolas et al., 2021, Thm. 3.2).
We generalize (EG+) in Algorithm to take the operator into account- consequently we capture constraint and regularized problems as well. In addition, the scheme is adaptive in ây. We will show that the weaker requirement of p e (-1/22, o0) suffices even for the more general inclusion (2.1).
The main convergence results of Algorithm 1 are established in the next theorem. The proof is largely inspired by recent developments in operator splitting techniques in the framework of mono- tone inclusions (Latafat & Patrinos, 2017; Giselsson, 2021). The key idea lies in interpreting each iteration of the algorithm as a projection onto a certain hyperplane, an interpretation that dates back to Solodov & Tseng (1996); Solodov & Svaiter (1999).
Theorem 3.1. Suppose that Assumption I holds, and let d (0,2), y: (1-2p)+ 1/1] where [x]+ == max 5x E (-n/2.p), lim inf,- de(2 - Ax) > O, and lim inf (6, + 7/22) > O. Consider the sequences (z)) "EEN ( KEEN generated by Algorithm Then for all E S*
min k-0,
| H2-112 - - 12
(3.1)
where lim inf: inf: 12 - (o) + n//)2. Moreover, the following holds
(i) KEN is bounded and its limit points belong zer T';
(i) if in addition lim sup: < 1/2 and S* = zer T, then (2 (e)) (et both converge to some z zer
Note that whenever lim supe-co 7x- < T. Lemma A.3(ii) may be used to derive a similar inequality in terms of E - 2²|l by lower bounding HE H || in (3.1). We also remark that tighter rates may be obtained in the regime p O, however, this will not be pursued in this work.
4

---

Published as a conference paper at ICLR 2022
Algorithm 1 (AdaptiveEG+) Deterministic algorithm for problem (2.1)
INITIALIZE: 20 .ini E R", d E (0, 2), y E (1-2pl+.1/1- 6x E (-1/2,
REPEAT for k 0, ..... until convergence
L. Let ह (id + +xA) (+' FF
1.2:
Compute stepsize
( H Hzt
de +
H H2t
where 11 id y.F.
Update the vector 2+1 2 + (H Hzt) RETURN 2+1
1.3:
3.1 NON-ADAPTIVE STEPSIZE VARIANT
Although we do not incur additional costs for evaluating the adaptive stepsize in step 1.2, it proves instructive to present variant with constant stepsize. As a result we compare the range of our stepsizes against Diakonikolas et al. (2021) showing improvement by factor of 9/2. Moreover, in the monotone case (p- = O), with certain choice of stepsizes the algorithm reduces the celebrated wawpaadd-bbwwrrddd-a forward (FBF) algorithm of Tseng (2000). We remark that the relation of FBF to projection-tyy -ype algorithms was noted in Tseng (2000), (Giselsson, 2021, Sect. 6.2.1).
To this end, in this subsection consider the following non-adaptive variant of Algorithm 1 that gen- eralizes (EG+). Letting ã e (0, 1 26//s):
(id + AA) (+' - xFF). ト+ ج az Hz²).
(CEG+)
The convergence of this algorithm is an immediate byproduct of Theorem 3.1. I. To see this, note that the I update in step 1.3 may be written z 전 + 2 HHt),, for m (0, 1). Therefore, convergence is still ensured for any ã₂ < 20r as the difference may be absorbed by the relaxation parameter 7)2- Note that by //2-cocoercivity of (cf. Lemma A.3(i))
2 H )
8:
26 Y6
28c Y
201
(3.2)
IE 1=
establishing the validity of the prescribed stepsize range. The convergence of the non-adaptive vari- ant is summarized in the next corollary that for simplicity is stated with constant parameters (drop- ping subscripts k).
Corollary 3.2 (Constant stepsize). Suppose that Assumption I holds, and let (1-2p]+, 1/4], E p-1/2,pl, and à e (0, 1 + 26/7). Consider the sequences (z) (#t generated according to the update rule (CEG+). Then,
120 =212
|H 22- k=
min
(3.3)
k(m 1)*
where x= ā(1 + 28 ā). Moreover, the claims of Theorems 3. (i) and 3. ((i) hold true.
The setting of Diakonikolas et al. (2021) in (EG+) involves the stepsizes Y = 1/2, 02 = 1/2. Note that when restricting to = 0, the iterates (CEG+) simplify to this form owing to the fact that - 전 - - Hz -y In comparison, in our setting ō p 1/8r. (the smallest P permitted in Diakonikolas et al. (2021)) selected, then based on our analysis in Corollary 3.2 we may select y 1/2, and ãμ E (0, 3/4), thus the upper bound for the second stepsize is 3/2 times that of Diakonikolas et al. (2021).
Remark 3.3 (relation to FBF). In Corollary 3.2 the range of stepsizes y, ā may alternatively be set y E (/))) E (0, [2/)]. This is due to the fact that if < 1/2 (strictly), then H is strictly /a-cocoercive. Therefore, in (3.2). 1 + 28 < 2a; holds, and thus the stepsize à = 1+ 28 is permitted. Although this may appear be of little practical significance, by setting and à = 1 in (CEG+), we obtain ++1 = z² # yF2 yFZ², which is the forward- backward-forweer (FBF) algorithm of Tseng (2000), (Bauschke & Combettes, 2017, Thm. 16)1
10)1,,,, 5 P 0,
5

---

Published as a conference paper at ICLR 2022
02
0.0
Figure 2: The grey region indicates where convergence provably cannot be guaranteed by Theorem 3.4. The dashed line indicates where p -/sr. This the condition under which (Diakonikolas al., 2021, Thm. 3.2) shows the first convergence result (+). Covollary 3.2 improves their result by matching the lower bound for any i. in particular for ā 3/4 The adaptive scheme in Theorem 3.1 mutches the smallest
pussible p for any (EG+) scheme with fixed stepsize
3.2 LOWER BOUNDS
We show that the result Corollary 3.2 is tight by providing matching lower bound when O. We do by fixing åg and showing stepsize dependent lower bound. In particular, note that if ar = 1/2 as in Diakonikolas et al. (2021, Thm. 3.2), then Theorem 3.4 implies a lower bound of p 1/4r. for the (EG+) scheme. The lower bound is contextualized in Fig. 2 by relating it to our convergence results and existing results in the literature.
Theorem 3.4. Consider sequence (eN generated according to (EG+) fixing Yk = 1/2 and āg ā E (0, 1). Let -pL B ..ا Then, there exists F R" R", n > 1, satisfying Assumption I(ii) and Assumption ((iiiforr which the sequence will not converge.
4 ADAPTIVELY TAKING LARGER STEPSIZES USING LOCAL CURVATURE
As made apparent in the analysis in Section 3 (cf. Appendix B.I) the bound the smallest weak MVI constant p in Assumption I(iūi) may be replaced with the requirement that p > -w//2 for all k E N. Therefore, larger stepsizes ys would guarantee global convergence for even larger class of problems. Since a global Lipschitz constant is inherently pessimistic the natural question then becomes how to locally choose maximal stepsize without diverging.
The proposed scheme involves a backtracking linesearch that uses the local curvature for its initial guess. The reason being that this will immediately pass, close enough the solution z", by argu- ment of continuity. More precisely, we will set the initial guess to something slightly smaller than |JF(=)]] where Jz(z) denotes the Jacobian of F at and ||- is the spectral norm. Note that, de- spite the use of second order information, the scheme remains efficient since [F((z)] only requires one eigenvalue computation performed through Jacobian- vector product (Pearlmutter, 1994).
Given an initial point 2" = _innt and E (0, 1), the final scheme which we denote (CurvatureEG+) proceeds for k 0, l.... as follows:
Obtain yt and according to Algorithm with yii v|)sF(E()
(CurvatureEG++)
2. Compute 2++1 according to steps 1.2 and 1.3 of Algorithm
The above intuitive reasoning is made precise in the next lemma where is shown that backtracking linesearch will terminate in finite time and that yiii will be immediately accepted asymptotically.
Algorithm Lipschitz constant backtracking
INITIALIZE 2t IR" (0, 1), (0. 1) 2.1: Set initial guess y iit and let Gy(tt) = (id + yA) ((t yFz)) while (G, - Felll > G(+)( 2 do y Ty
RETURN Y: = y and 전 (z')

---

Published as a conference paper at ICLR 2022
Lemma 4.1 (Lipschitz constant backtracking). Suppose that F R" R² is L-Lipschitz contin- uous operator. Consider the linesearch procedure in Algorithm 2. Then,
(i) The linesearch terminates in finite time with y 2 min(y/ v5/1]; (5///)
(i) Suppose that (2t) KEN converges to z" E zer If F is continuously differentiable, and yim (0.v) (..])F((211-) with v E (0, 1), then eventually the backtrack will never be invoked (yinit would be accepted).
The convergence results for (CurvatureEG+) are deduced based of the above lemma and The- orem 3.1 and are provided in Corollary B.1 Appendix B.2. We illustrate the behavior of (CurvatureEG++ in Fig. and in Section 6.
CONSTRUCTING TOY EXAMPLES
When Assumption I(iii) holds for negative p. limit cycles of the underlying operator Fz can emerge. We illustrate this with simple polynomial examples for which all the properties of interest can be computed in closed form.
Definition (PolarGame). A PolarGame denotes two-player game whose associated operator F has limit cycles at |z|2 = c; for all E [K] where c / 0.
This turns out to be particularly easy to construct in polar coordinates as the name suggests (see Appendix C.I). Apart from introducing arbitrary number of limit cycles it also gives control over This is illustrated in the following instantiations capturing three important cases.
Example 3: (PolarGame). Consider Fz (b(x, y, x(,,x) x) where I & 1/110 and
(xx a - x2 + + 16x² + 16y²). We have the following three cases:
(i) then p (- + (ii) i then p (-
(ii) then p (- 8T.
where I. denotes the Lipschitz constant of restricted to the constraint set. For all cases exhibits limit cycles |||| and |z|| 3/4. Proof deferred to Appendix C.2.
Example 4: (minimax). In the particular case of constrained minimax problem we introduce the following polynomial game:
minimize maximize ((x,)) == xy ((x) -b(),
(GlobalForsaken)
19//
where (()) =
21 -
We provide proof of the following properties in Appendix C.3:
(i) There exists a repellant limit cycle and an attracting limit cycle of
(ii) (0.0) a global Nash equilibrium for which Assumption I(iii) holds inside the constraint with p 1/22,, where L denotes the Lipschitz constant of F restricted to the constraint set.
EXPERIMENTS
The algorithms considered in the experiments include the adaptive Algorithm 1, (CurvatureEG+) and constant stepsize methods that can be seen as instances of (CEG+) for various choices of y: we recover constrained variant extragradient, which we
and 0g.. When 7/ 1/1. and a; denote CEG. When & 1/2 we denote the scheme CEG+, which is the direct generalization to the constraint setting of the (EG+) scheme studied in Diakonikolas al. (2021, Thm. 3.2). Note that this choice of â₂ restricts the problem class for which otherwise can have guaranteed convergence according to Corollary 3.2. When ăe is chosen adaptively according to Algorithm we refer to it as AdaptiveEG+. Finally, when y is additionally chosen adaptively use the name (CurvatureEG+).
In the stochastic setting, when Yt 1/4 and a; = 1, effectively both stepsizes diminish, and we recover constrained variant of the popular stochastic extragradient scheme (see e.g. Hsieh et al.

---

Published as a conference paper at ICLR 2022
(a) Example 3 (a 1)
(b) Example (p- -1/s)
00
00
08
05
-10 -25 0.
1.2
-1.0
-2.5 0.0
1.0
AdapiveEG+
Figure 3: Deterministic setting. In (a) we have an instance of Example with p < -/22, for which Theorem 3.4 provides lower bound for extrapolation stepsize Y/ = 1/2 However, adaptively choosing Ys larger can converge as illustrated with (CurvatureEG+)) In addition, (b) confirms with Example 5, that (CEG+) for 1/2 and CEG may indeed converge AdaptiveEG+ and (CurvatureEG+) converges the stationary point. Note that picking lead to convergence of (CEG+) by Comollary 3.2. See Fig. and Fig. 7 for supplementary experiments.
when p -1/21. In contrast, both
1/s would
Example
Example (p -1/L)
1.2
8111
107
SEG SEG+
Figure 4: Stochastic setting. In (a) test the stochastic algorithms strained minimax example. The eycling behavior SEG is inline with Hsieh et al. (2021). who shows that sequence generated by SEG can converge to limit cycles of the underlying operator F. On other hand, we observe that SEG+ escapes the attracting limit cycle. In (b) we also provide a more challenging example motivated by our lower bound.
nonconvEx-RunCORCEE
(2021, Algorithm 3)), which we refer to SEG. We also consider heuristic variant where yx 1/z. and only da is decreasing, which we refer to SEG+.
test the algorithms on the constructed examples and confirm their convergence guarantees. Specifically, we apply the algorithms to the minimax problem in Example 4, the PolarGames in Example 3, and worst case construction, Example 5, from the proof of the lower bound (cf. Ap- pendix B.3). For Example we choose the problem parameters such that p -1/3u according to (B.,3), and additionally add an -bal constraint to keep the iterates bounded. To simulate the stochastic setting add Gaussian noise calls of F. Results for the deterministic setting and stochastic setting can be found in Fig. 3 and Fig. respectively.
CONCLUSION
This paper introduced an EG-type algorithm for a class camconvex-nonconecee minimax prob- lems that satisfy the weak Minty variational inequality (MVT). The range of parameter in the weak
8

---

Published as a conference paper at ICLR 2022
MVI was extended compared to EG+ of Diakonikolas al. (2021), and tightness of our results were demonstrated through construction of a counter example. In addition, EG+ (Diakonikolas et al,, 2021), as well as the forward-back www.baaad-ooowaaaaa algorithm (Tseng, 2000) were all shown to be spe- cial cases of our scheme. Furthermore, (CurvatureF:Gi+) was proposed that performs a backtracking linesearch the extrapolation stepsize y allowing for larger stepsizes and relaxes the condition II 10 > -2y/ which is often a much weaker condition. More importantly it is shown that asymptotically the linesearch always passes with Y x|]JF(z>)]|- for any v é (0, 1), thus rat- ifying the name (CurvatureEGG+). Future direction include exploring applications of the proposed algorithm in particular in the setting of GANs. It is also interesting to develope a variance reduced variant the algorithm for finite sum minimax problems.
8 ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
We would like to especially thank Yu-Guan Hsich for providing valuable feedback and discussion. This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement n 725594 time-data). This work supported by the Swiss National Science Foundation (SNSF) under grant number 200021_20501 The work of the second and third author was supported by the Research Founda- tion Flanders (FWO) postdoctoral grant 12Y7622N and research projects GO8 1222N, GOA0920N, G086518N, and GO863 I8N; Research Council KU Leuven C1 project No. C14/18/068; Fonds de Recherche Scientifique FNRS and the Fonds Wetenschappelijk Onderzoek Vlaanderen un- der EOS project no 304681 60 (SeLMA); European Union's 's Horizon 2020 research and innovation programme under the Marie Sklodowska-Cure grant agreement No. 953348. The work of Olivier Fercoq was supported by the Agence National de la Recherche grant ANR-20-CE40-0027. Optimal Primal-Dual Algorithms (APDO).
REFERENCES
Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of gradient-based methods for whole spectrum of differentiable games. In International Conference on Artificial Intelligence and Statistics, pp. 2863-2873. PMLR, 2020.
Heinz H. Bauschke and Patrick L. Combettes. Convex analysis and monotone operator theory in Hilbert spaces. CMS Books in Mathematics. Springer, 2017. ISBN 978-3-319-48310-8;
Heinz H Bauschke, Walaa M Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Mathematical Programming, pp. 1-20, 2020.
Michel Benam and Morris Hirsch. Mixed equilibria and dynamical systems arising from ficti- tious play in perturbed games. Games and Economic Behavior, 29(1-2):36 1999.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 134-334, 1997.
Axel Böhm, Michael Sedlmayer, Ernö Robert Csetnek, and Radu Ioan Bot. Two steps time- taking gan training in stride with tseng's 's method. arXiv preprint M0Xiv:2006.090333 2020.
Constantinos Daskalakis, Dylan J Foster. and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. arXiv preprint arXiv:2 004333, 2021a
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp. 1466-1478, 2021b.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges the rate $O(k}- 1/4])$ on weakly convex functions. arXiv:1802.022 02988 (cs, math], February 2018.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for struc- tured nonconvex-oo noncooccvee min-max optimization. In International Conference on Artificial Intelligence and Statistics, pp. 7756-2754. PMLR, 2021.

---

Published as a conference paper at ICLR 2022
Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and comple- mentarity problems. Springer Science Business Media, 2007.
Tanner Fiez and Lillian Ratliff. Gradient descent-ascent provably converges to strict local minmax equilibria with finite timescale separation. arXiv preprint arXiv:2009. 14820, 2020.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. arXiv preprint arXiv:/8022 10551, 2018.
Pontus Giselsson. Nonlinear forward-backward splitting with projection correction. SIAM Journal on Optimization, 31(3):2199 2226, 2021. doi: 10.1 10.1137/20M/345022
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge local nash equilibrium. Advances in neural information processing systems, 30, 2017.
M Hirsch and Vavasis. Exponential lower bounds for finding Brouwer fixed points. In Proceedings of the 28th Symposium Foundations of Computer Science, pp. 401-410, 1987.
Cars H Hommes and Marius I Ochea. Multiple equilibria and limit cycles in evolutionary games with logit dynamics. Games and Economic Behavior, (4(1):4344441 2012.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits min-max optimization algorithms: Convergence spurious non-critical sets. In International Conference Machine Learning. pp. 4337-4345 PMLR, 2021.
Yu-Guan Hsich, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggres- sively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. arXiv preprint arXiv:2003. 2020.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? arXiv:/902.0065 [cs, math, stat), June 2019.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Puya Latafat and Panagiotis Patrinos. Asymmetric forward-backward- splitting for solving
monotone inclusions involving three operators. Computational Optimization and Applications, 68(1))57-92 Sep 2017.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. arXiv preprint 1xX.:2206.002266 202
Sucheol Lee and Donghwan Kim. Semi-anchored multi-step gradient descent ascent method for structured nonconvex- nonconcave composite minimax problems. arXiv preprint arXiv:2/05. 15042, 2021b.
Mingrui Liu, Hassan Rafique, Qihang Lin, and Tianbao Yang. First-order convergence theory for (169):1-34, 2021. 2021.
min-max problems. Journal of Machine Learning Research, 22
Eric V. Mazumdar, Michael I. Jordan, and S. Shankar Sastry. On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games. arXiv:1901.0083. [cs, math, stat]. January 2019.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv: (07.02987..0222, .2.22, 2018a
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms, pp. 2703-2717. SIAM, 2018b.
George Minty. Monotone (nonlinear) operators in hilbert space. Duke Mathematical Journal, 29 (3)34413346, 1962.
10

---

Published as a conference paper at ICLR 2022
Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solv- ing a class non-convex min-max games using iterative first order methods. arXiv preprint arXiv:1902.08297, 2019.
Christos H Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and system Sciences, 48(3):498-532, 1994.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
Boris T Polyak. Introduction to optimization. Optimization Software New York, 1987.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv:1810.02060 [cs, math), January 2019.
R. T. Rockafellar and R. J.-.. Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-895, 1976.
Ralph Tyrell Rockafellar. Convex analysis. Princeton University Press, 1970.
M. Solodov and P. Tseng. Modified projection-type methods for monotone variational inequali- ties. SIAM Journal on Control and Optimization, 34(5):1814-1830 1996.
Mikhail V Solodov and Benar F Svaiter. A hybrid projection-proximal point algorithm. Journal of convex analysis, 6(1):59-70, 1999.
Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrap- olation for coherent non-monotone variational inequalities. arXiv preprint 1rXiv:2103.04410, 2021.
Gerald Teschl. Ordinary differential equations and dynamical systems, volume 140. American Mathematical Soc., 2012.
Tseng. A modified
splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431-446 2000.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for a class nonconvex-nonccomaas minimax problems. arXiv preprint arXiv:2002.0966 2020.
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W Glynn. Stochastic mirror descent variationally coherent optimization problems. In Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.

---

Published as a conference paper at ICLR 2022
A PRELIMINARY DEFINITIONS
Notationally we will use + max(0, x) throughout. We additionally recall some standard defini- tions and results and refer to Bauschke & Combettes (2017); Rockafellar (1970)) for further details.
An operator set-valued mapping A R Rd maps each point R" subset Ax of R We will use the notation Axx) and Ax interchangably. We denote the domain of A by
dom A fre R"
Ax Ø)
its graph by
gphA = (xx,y) E R x Rd ye ye Ax),
and the of its zeros A {x R" 0 Ax). The inverse of A is defined through its graph: gph == x6,x) (x,y) E gphA}. The resolvent of A is defined by JA == (id + A) where id
denotes the identity operator.
Definition A.I ((conooonty Bauschke et (2020)). An Operator R 3 R" is said to be p-monotone for some E IR for all (x.y), (x.y)) g
plx- x < x
and it is said to be p-comonotone for all (x, (x' E gphA
plly - < (x (x- x x
The operator A is said to be maximally moontooe if its graph is not strictly contained in the graph of another (co monootone operator.
We say that A is monotone if is O-monotone. When p p-comonotonicity also referred as /--ooyypomooooniiciyy.
Definition A.2 (Lipschitz continuity and cocoercivity). Let D s R" be a nonempty subset of R". A single-valued operator D R" is said to L-Lipschitz continuous if for any x, e D
|Ax Ax
& L x
x'|].
and B-cocoercive if
B|Ax- AX|I & (x AxAx- Ax)
Moreover, A is said to be nonexpansive if is I-Lipschitz continuous, and firmly nonexpansive if it I-cocoercive.
The resolvent operator JA is firmly nonexpansive (with dom JA R") if and only if is (maximally) monotone.
The following lemma plays an important role in our convergence analysis. Lemma A.3. Let A R" denote a single valued operator. Then,
(i) 1-Lipschitz if and only T
1/2-cocoercive.
(ii) If A is L-Lipschitz then T id nA, n E 1/)), - 1--LL)-monntom and in particular for all u. R".
Tuu Tvll
Proof. The first claim follows directly from (Bauschke Combettes, 2017, Prop.4.11) That T is strongly monotone is consequence of the Cauchy Schwarz inequality and Lipschitz continuity of A:
(Tv Tu, u) || u|2 Ay Au, u) > (1 nL]ll u||
In turn, the last claim follows from the Cauchy- Schwwrr inequality.
B PROOFS AND FURTHER RESULTS
B.I PROOFS OF SECTION 3
12

---

Published as a conference paper at ICLR 2022
Proof of Theorem 3.1. Let H = id - F.F. By Step 1.1 He* Et + MAZ Therefore,
(H2² - -H AZ + F
(B.1)
In what follows we will show that Algorithm 1 is equivalent to taking forward-backwart step followed by correction step. Consider the updates
き² = (id + 72A) (+ >)FE",,
(B.2)
g+ = -1- (1) + 4 (x'), where Dj == {W (H) - HE, Et w) H H
1241
Note that
H - H +
& 111 He* (2 (x) H 12 y
(B.3)
where in the inequality Lemma A.3(i) used. Hence, by (B.3) the stepsize ag is positive and bounded away from zero. Moreover, if E Dr, then from (B.3) we may conclude that [ - & O which implies that the generated sequence remains constant and 5x zer (cf. (B.1)).
The projection onto D3 for any v Dz is given by
( H.
H |H HE22
1 (v) +
(H H2²)
|H - 1
Moreover, 1) together with Assumption I(iii) at 전ス yields
2 (HE H2 -²) - H H
H Hz²1
(B.4)
thus ensuring 2" E S" = Dt. The projection onto D2 is then given by 11 (+*) 2. + + ( -HE*) where og is as in step 1.2.
Finally, since the projection Hy is firmly nonexpansive, it follows from (Bauschke & Combettes, 2017, Cor. 4.41) that the mapping (1 -4)id + d H, 4/2-averaged. Consequently, we may con- clude that (zt) KeN is Fejér monotone relative to S* (Bauschke & Combettes, 2017, Prop. 4.35(
That is for all 2" E S*
1 2²1 < || - 2-1 1/2 - a HE* 12a
(B.3) < || - 1-
* HH 12
(B.5)
where e, = (2) + The convergence rate in (3.1) is obtained by telescoping (B.5). Since lim inf; 8 > 0, ( HE* HH=*12)en converges to zero. Moreover, (Il=* - 2²1²) converges {E*) and the sequence (z*) JEN is bounded. Since yı is bounded, and F and the resolvents (id + are Lipschitz continuous (cf. (Bauschke Combettes, 2017, Cor. 23.9)). so their composition. Hence, (EN) is also bounded. Let (z*)EE be subsequence converging to some 2 E R" Combined with the fact that H Hz2 keN converges to zero, we may conclude from (B.1) along with (Bauschke & Combettes, 2017, Prop. 20.38) and Lipschitz continuity of F that 2 E zer Finally, if in addition y= lim sup Yt < I/L. then (1 (1- yLy I < |H Hæ*ll (invoke Lemma Aii().). There- fore, (1|E* 2f1 kNN converges to zero, which in turn implies that a subsequence (z*) (=*)e< converges to point z' iff so does the subsequence (2*), JEK" Hence, (2+) )ex also converges to Ž E zer Conse-
7/
quently, Assumption I(iii) holds at all of the zeros of T, i.e., S = zer T, then the second claim follows by invoking (Bauschke & Combettes, 2017, Thm. 5.5).
Proof of Corollary 3.2 (Constant stepsize). The proof of convergence already given prior to the statement of the corollary. It remains to derive (3.3). By Assumption I(āū)) and owing to 1/2- cocoercivity of H (cf. Lemma A.3(i))
( -HE H&²) = -(²- 11, - H + ( - #, HE -HE²)
(B.4) v - + [ H2*
(B.6)
Therefore, provided that ă > 0 we have
1 zz 2 || 2-112 a² 222
H2-'| 1|| + 2ā(e" 2²' .HH H²²) (B.6) < ||z - 2-' a
H) - H22
Telescoping the above inequality yields the claimed inequality.
13

---

Published as a conference paper at ICLR 2022
B.2 CONVERGENCE RESULTS AND SECTION
The convergence results for (CurvatureBGG+) are provided in the next corollary where in Assump- tion I(i))) is allowed to take potentially larger values provided that p -2/2.. Note that owing the lower bound on (cf. Lemma 4. (i)), the weak MVI assumption in the corollary is always satisfied pf (-V7/2L, 20), however, in practice yk may take larger values.
Corollary B.I. Suppose that Assumptions I(i) and I(ii) hold, and consider the sequences (2)) KEN
(2) N generated by (CurvatureEG+t). Suppose that Assumption I(iii) holds for some p E R
satisfying Ys + 2p > and let òg E (-1/2.p), de (0,2), lim inf 12 1x) 0, and lim inf (6g + 7/22) 0. Then,
(i) The sequence (1 - - LEN vanishes;
(i) (#') (ET) are bounded, and have the same limit points belonging zer
(ii) in addition S = zer T, then (#") (z) both converge to some =" E zer T.
Moreover, t -" zer T (as is the case in B.l(iii),, and F is continuously differentiable, then eventually the backtrack will never be invoked.
Proof. Observe that in the proof of Theorem 3.1 1-Lipschitz continuity of F is only used at the generated points zt and z (see (B.3)), and is thus ensured by the linesearch Algorithm 2. Therefore, it is easy to see that ag is positive and bounded away from zero provided that -1// see (B.3). Moreover, since y FF F2 & vl|E* - 2²1, arguing as Lemma A.3(ii) we obtain HE 122
(1 1-- r) |. Hence, it follows from (B.5) that
|| 1² | 2-11² -11-" I
By telescoping the inequality and noting that yx bounded, we obtain Eee | 21 0., implying B.1(i). Noting this and arguing as in the last part of the proof of Theorem 3.1 establishes B.i( (ii The last claim the direct consequence of Lemma 4.1
Proof of Lemma 4.1 (Lipsehitz constant backtracking). 4.1(i): Since F L--Lipschitz continuous the linesearch would terminate in finite steps. Either yimil satisfies the condition, or clse the back- track procedure is invoked, which in turn implies the previous candidate y/r should have violated the condition leading the the claimed lower bound.
4ff(;;): Since the resolvent -A)+ and F are Lipschitz continous, so is their composition. Hence, yF2 Gy(z*) + yA(G,(z")), Consequently, using monotonicity of at Gz(z") and z", and that - Fz E Az" yields & (z" yF'z' Gy((") + Fz", ",,(")(())))) 2*) - ||z" - (2)2)) Thus Gy(2") = z- Using the fact that both (Gy (z+) ieN and
(=fr - Gz(z"). Furthermore. by definition
(2+) KeN converges z E zer T:
lim (2)) Fz
F Fz -
lim =f
lip F(z')(()))))) []F((")]
G,((**) =+
where (Rockafellar & Wets, 2009, Thm. 9.7) was used. The claim follows from continuity of JF and the fact that (z*) converges to z
L
B.3 PROOFS SECTION 3.2
To prove the lower bound we introduce the following unconstrained bilinear minimax problem with an unstable critical point.
Example Consider the following minimax problem:
minimize maximize f(xyy == axy b _ - -2))
(B.7)
xER
yek
where b < 0 and a 0.
14

---

Published as a conference paper at ICLR 2022
Proof of Theorem 3.4. The associated operator of Example can easily be computed,
Fz= (ay + bx, by ax),
(B.8)
where = (x,y). In this particular case, both L and turn out to be constants. By simple calculation have,
[JF(2)] v + b
(B.9)
d
b
where || is the spectral norm. Since the norm of the Jacobian constant equates the global Lipschitz constant, L [JF(z)]
By linearity of F, one step of (EG+) is conveniently also a linear operator. Specifically,
+ -6 +ob++++b+))
ot Vo++
++1 = Tz with T :
6¹ b (1 (1-7)a - y +ab+b)
(B.10)
+0 26)
We know that linear dynamical system globally asymptotically stable if and only if the spectral radius of the linear mapping is strictly less than 1.
Let dq. be the eigenvalues of T. Then the spectral radius is the largest absolute value of the eigenvalues. For T this becomes,
max [2/ = (2( l)ā 1)a² 2ā + 1)b( Va² 62 b) + (1.2)
(B.11)
a² + b2
So we can ask what p = - needs be the sequence )eN to converge. Solving for in this equality with max; bi 1, obtain,
1 1-
(B.12)
2
provided that we pick
V1 c²
(B.13)
b'
Equation (B.13) provides specification for Example As long as (B.12) is satisfied, (EG+) is guaranteed to converge for y 1/2. On the other hand, since (B.10) is a linear system, simulta- neously learn that picking any larger would imply non-convergence through max; [4] (given 2" 0). We can trivially embed problem (B. into higher dimension generalize the result. Noting that -p. completes the proof.
We provide Mathematica code to verify each step of the above proof.
C TOY EXAMPLES
In the following appendix, denotes the Lipschitz constant of F restricted to the constraint set and P is the parameter of the weak MVI (Assumption I(iū)) when restricted to the constraint set. This restriction the definitions warranted, since z remains within the constraint in all simulations, while 5 is guaranteed to stay within by definition of Step 1.1 in Algorithm (and likewise for all other considered method treating problem (2.1)).
All computer-assisted calculations can be found in the supplementary code.
C.1 CONSTRUCTING POLARGAME (DEFINITION 1)
Recall Definition which considers a vectorfield F R - Rd with limit cycles at E (cI,... Ci) where a * for all i e [K]. Such vectorfield can be constructed for n = by departing from the
Thee supplementary code be found http::://ggtttooo.ooooo/ssssssts
15

---

Published as a conference paper at ICLR 2022
Figure 5: We can construct the desired properties in polar coordinates (r. 0) and subsequently transform into vectorfield in cartesian coordinates yx This is illustrated by PolarGame with attracting limit cycles radius [|z] and repellant limit cycle [z]] 3/4 for the associated operator Fz indicated red blue respectively.
(a) a =1
(b) = 3/4
(c) = 1/3
Figure 6: Example 3 for different values of a (and thereby different values p). Note that even extragra- dient may escape the limit cycles even though p This not in conflict with the negative results of Hsieh et (2021) since the stepsize is not diminishing, However, in general case even extragradient with fixed stepsize will not converge as shown by the lower bound Theorem 3.4.
following dynamics in polar coordinates,
aa ...r(()
(T00 + c.) (x() c;)
1-1
(C.1)
20 r(t).
ōr
with b * 0. Transforming this dynamics into cartesian coordinates yields the desired vectorfield, F, while subsequently integrating with respect x and yields the two potentials associated with the two players. Note that the roots {-c for the polynomial defining are not strictly necessary for showing existence of limit cycles, but leads to simpler form for Fz. We illustrate the construction in Fig. 5.
Proposition 1. Fzt (ž. y) be the evolution in cartesian coordinates of the associated vectorfield in polar coordinates defined by (C.I). Then the only stationary point of the origin (0, 0) and there exists limit cycle c; for all i [k].
Proof. Let r = +2. It is easy to see from (C.1) that the only stationary point is at r 0. By construction, ? polynomial with roots e; for all E [k]. so any trajectory starting the circle defined by c; remains in that However, is strictly nonzero. As consequence Fz nonzero, so r must define a limit cycle, which proofs the claim.
16

---

Published as a conference paper at ICLR 2022
(a) Example
(b) Example 5 (p = =/3r)
455
40
-10
-1.0 -0.5 0.0 0.5 1.0 -10 -25 D0
0.5
1.0
CEGe
CBG- 1/9
Figure 7: In (a) observe that all algorithms converge, despite F having attracting limit cycle in Example However, note that in the stochastic setting, where diminishing stepsize is required, SEG does not converge to the critical point (see Fig. 4a). (b) we demonstrate that when p -V/L,, picking & < for (CEG+) is necessary for convergence in general. See Section 6 for the experimental setup.
C.2 PROOF FOR PROPERTIES OF EXAMPLE
The operator F R2 - R²2 defined in Example 3 obtained by constructing the associated dynamics in polar coordinates,
Òr Ōt
a r(t) (r(1) + 1) (r(1) - 1) (r(1) + 3/4) (r(1) - 3/4)
(C.2)
00
Ōr = -r(i).
This can easily verified by a change of variables. From Proposition then follows, that there must exist limit cycle |z] 1 and | = 3/4. To verify the conditions on & compute the closed form solution to and L in Mathematica:
(i) For a we have p = 1050977
50176
and L 2538096 7044424999 70244999677
20000
(ii) For 3/4 have p
6021 12
and 7614288 V6381574361 635022906555
1679882
80000
(iii) For 1/3 we have
LS0528
and
2538096
7344249224
94339585
60000
It can easily be verified that the stated conditions for in Example 3 are met for the values above. This completes the proof.
We provide Mathematica code verifying the construction of F and the closed form solutions to and p.
C.3
PROOF FOR PROPERTIES EXAMPLE
Under the definitions of p and L in Appendix C, we claim that the origin (0,0) in (GlobalForsaken) a global Nash equilibrium and satisfies Assumption I(īii) with p > >-12/1.
To verify that (0.0) 0) is indeed global Nash equilibrium need check that the solution cannot be unilaterally improved. In other words, the solution should coincide with (x".y*) where
arg min (xx, 0)
(C.3)
arg max di d(0.y).
17

---

Published as a conference paper at ICLR 2022
We can easily verify this with Minimize in Mathematica, since the functions polynomial for which a closed form solutions to the global optimization problem will be returned.
To find p for 2" (0, 0) we solve the global minimization problem,
(F2,z 12.2-222 2²>
minimize
(C.44
F2
for which a closed form solution can be found with Mathematica, which when numerically evaluated is approximately -
We need compute L ensure p -1/24. In our case of convex constraints, C, we have that = sEc [JF(Z)] where denotes the spectral norm (Rockafellar & Wets, 2009, Thm. 9.2 and 9.7). Under our constraint [2]|o0 a < 4/s, this can similarly be computed closed form, yielding
L = v (9409 /5922115 //57210011 (19721001+741155511 2/2835 So 2L - 0.165332 which satisfy the condition p 21'
This completes the proof.
Proposition 2. Let F be the associated operator of & in (GlobalForsaken) defined Fzz v), v)) Define the radius as = ||=] Then, Fz has stable critical point at the origin (0. 0), at least one attracting limit cycle in the region defined by / < << 2 and at least one repellant limit cycle within < 1/2.
Proof. We follow a similar argument as in Hsieh et al. (2021, D.2). We can compute the associated operator F.
4x
4x
(C.5)
-//
With a change of variables into polar coordinates (r. we get that r= V x2 + evolves as,
22 (9)/* cos( (40) 14,² cos(40) 15 -22 28).
1
(C.6)
When / this reduces to i 3 +55 and we observe that i 0 for any 0. Likewise for 56
= 2, we have that i = 21 (22 cos + 25) which implies i < 0. Since there is no stationary point
4
in the region S { (r:00) 1/2 </> 2] it then follows from the -endaar--enndxxonn theorem (Teschl, 2012, Thm. 7.16) that there must exist at least one attracting limit cycle in S. Further, it easy see that (0. critical point and that
stable by inspection of the Jacobian JF(z). Since S is trapping, it follows from Poincaré Chincaé--Hopf index theorem, that there must exist repellant limit cycles in the region defined by r< 3 This completes the proof.
C.4 PROOr OF PROPERTIES FOR (HSIEn ET AL., 2021, EXAMPLE 5.2)
This section considers (Hsieh et al., 2021, Example 5.2) on the constraint domain = (2 E R" | & 3/2). We show that the unique critical point z" does not satisfies the weak MVI for p > - 1/21. even when restricted to the constraint set E D. We restate the example with the additional constraint for convenience.
Example 6: (Hsieh et al., 2021, Example 5.2)
minimize maximize obx := x(y- + x(x) - ((y).
(Forsaken)
x//$
where (z) = 222
By using Mathematica, we can obtain a closed form solution of the Lipschitz constant L of F re- stricted to the constraint set, which we find to be L = a V 1 {10889 /801761 + 993841). Math- ematica solve approximately for the critical point, yielding z (0.0780267, 0.41 1934). To find we want to globally minimize p(z) := (Fac-z") for 2 E D. Mathematica finds the candi- PF
date /' 1.01236. 0..144799) for which p(z') = -0.477761. So p must be at least this small, ie. p < 0..477761. Since -1/21 x -0.04, this implies that p < -1/2u. See Forsaken. nb for Mathematica--asissed computations.
18

---

Published as a conference paper at ICLR 2022
-10
-15
0.5
CEG
CEG+
AdaptiveEG-
CurvatureEG+
Figure 8: Demonstration of algorithms on (Hsieh et al., 2021. Example 5.2). Only (CurvatureBG con- verges to the criticul point, while the remaining methods. CEG, (CEG+) with ûj 1/2, and Ed converges attracting limit cycle. See Section for further specification the algorithms.
This rules out convergence guarantees for both (CEG+) and AdaptiveEG+ (Algorithm 1), which is supported by the simulation in Figure 8. However, as observed, (CurvaturcEG++ converges in the simulations.
19


Reviews:
[{"review_id": "hn0Bm3AJnnw", "reviewer": "Reviewer_DVU2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 focuses on general minimax problems, which is a very important problem (even though with the special Weak MVI structure). The paper is clearly written and easy to read. \n\nThe results of curvature-based adaptive stepsize and lower bound look interesting, which can reveal a significant difference compared to EG+, and rationalize the extension of the regime of $\\rho$.\n\nMy main concern is that:\n1. The lower bound requires EG+ to have a fixed stepsize $\\gamma$, but as far as I know, lower bound analysis generally has no requirement on the stepsize (in fact they are using linear-span algorithms, so it can be arbitrary stepsize). So to some extent, now I view the lower bound result too specified and therefore a little restrictive, can the author comment more about it?\n2. Even though with the craft stepsize strategy, the final complexity result is still similar to those in existing literature, will the parameter choice of proposed algorithm bring any benefits in terms of the complexity (even in the constant)? Or do you think the lower bound for the whole class of weak MVI problems is already achieved? Can the author comment more about it? Thank you.\n\nGenerally I view the results in the paper pretty interesting.", "summary_of_the_paper": "This paper proposed CEG+ and CurvatureEG+, which extend extragradient method to a proximal variant (regarding the operator $A$), and apply it in nonconvex-nonconcave minimax optimization with Weak MVI condition in both deterministic and stochastic cases, and proved their complexities, which has the same order as those in literature (e.g., Diaonikolas et al., 2021). The authors also studied the lower bound in the simpler case when $A\\equiv 0$, showing a difference compared to EG+ in (Diaonikolas et al., 2021).\n\nIn the deterministic case, it proposed an adaptive stepsize strategy to allow larger range of the MVI parameter $\\rho$, and further a curvature-based strategy to avoid the lower bound requirement of $\\rho$. The authors also executes several experiments, showing that CurvatureEG+ can avoid cycling in the experiments.", "summary_of_the_review": "This paper provides approach to avoid lower bound of Weak MVI parameter and provide a lower bound perspective on the fundamental difference compared with existing literature.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NHw5iVEeX-", "reviewer": "Reviewer_4TM5", "summary": "", "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": "**Strengths**\n- A larger range of $\\rho$ of the weak MVI: The Adaptive EG+ and (a line-search-version) CurvatureEG+ work for a wider range of $\\rho$, $\\rho>-\\frac{1}{2}$ or $\\rho>-\\frac{\\gamma_k}{2}$ respectively, compared to that of EG+, $\\rho>-\\frac{1}{8}$. (This bound of EG+ could be weakened, but the authors show that this cannot be better than $\\rho>-\\frac{1}{4}$.) One might be view this improvement negligible (which I did when I glanced through the paper), but the wider region includes, e.g., the difficult \"forsaken\" example in [Hsieh et al., 2021] and the corresponding experimental results are interesting to read. For the stochastic case, the proposed SEG+ works for a same range of $\\rho$, while a stochastic version of EG+ in [Diakonikolas et al., 2021] is shown to work for a more restrictive setting.\n- Unified analysis of a larger class of algorithms: This work first used a projection onto a certain hyperplane technique with an adaptive step size. Then, the authors show that it includes a non-adaptive variant, named CEG+, which covers both EG+ and FBF [Tseng, 2000]. (This also allows a larger step size for EG+.) Although the projection on to a hyperplane is not new (while probably new to the machine learning community), such unifying analysis seems theoretically inspiring.\n- Stochastic variant: A constant step size for the exploration step (while requiring diminishing step size for the other step) seems new and worth further investigation.\n- Experiments: At a first glance, the weak MVI condition looked artificial, but the examples (while toyish) well complemented the importance of such new condition introduced recently.\n\n**Weaknesses**\n- One might view the convergence guarantee improvement of CurvatureEG+ over that of EG+ not significant.\n- To be precise, none of the examples satisfy Assumption 1 (specifically the Lipschitz continuity) globally. \n- The authors claim that they have less tuning parameters, compared to the method in [Lee & Kim, 2021a], but Algorithm 1 seems to have relatively many tuning parameters. I think this can be resolved, for example, by providing standard choices such as $\\lambda_k=1$, $\\gamma_k = \\frac{1}{L}$, $\\delta_k = \\rho$, requiring the knowledge of $\\rho$ and $L$. This however still does not seem to have less tuning parameters than that in [Lee & Kim, 2021a].\n\n**Other comments**\n- Although readers can check the appendix to see an explicit interpretation of the projection onto a certain hyperplane in Algorithm 1, I personally suggest at least further introduce it in the main page if there is a space.\n- I think it is worth mentioning related convergence results on the projection onto a certain hyperplane. What is new in that perspective seems missing in this paper. \n- The names of the proposed methods are given in the experiment section, but I suggest mentioning them in the main sections where they first appear for the readers who do not have time to read from the beginning to the end in details.\n- After (.2): $\\sigma_k$ -> $\\delta_k$\n- Before (.4): $\\bar{z}$ -> $\\bar{z}^k$", "summary_of_the_paper": "This paper constructs methods named CurvatureEG+ (and Adaptive EG+ and CEG+), built upon a recently proposed EG+ [Diakonikolas et al., 2021], a variant of EG, that works under the weak MVI condition. Most importantly, the CurvatureEG+ (and Adaptive EG+/CEG+) works for a range (of the weak MVI) larger than that of EG+. The corresponding nonconvex-nonconcave setting includes non-trivial problems illustrated in the paper, where the proposed method converges, while other existing methods reach limit cycles. Unlike EG+, the CurvatureEG+ can handle both constrained and composite cases. A stochastic variant is also studied. Although the experiments consider toyish problems, they seem interesting.", "summary_of_the_review": "Built upon a recent study on generalizing EG for nonconvex-nonconcave setting, this paper provides a nice unified framework of EG using the projection onto a hyperplane. Although the improvement in terms of the convergence guarantee is not significant, this paper is theoretically inspiring, and the toyish experiments are informative, which I believe has potential for further research both theoretically and practically.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AOun3sOPiE", "reviewer": "Reviewer_crvQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Pros:\n\n(1) This paper studies the constrained/regularized nonconvex-nonconcave minimax optimization and its generalization called weak MVI problem, which are popular, important, general and hard problems. \n\n(2) There are abundant extensions of the original extragradient algorithm. \n\n(3) Both theorems and experiments convincingly demonstrate that there are inclusion problems where the original extragradient algorithm diverges while the proposed algorithm with adaptive stepsizes converges. \n\nConcerns: \n\n(1) In the introduction, you said \"However, given the range of $\\rho$ in Diakonikolas et al. (2021), the new class is still too small to include even the simplest counterexample of Hsieh et al. (2021) for the general Robbins-Monro schemes.\" Does your setting contain this simplest counterexample? If yes, I think it better to elaborate this counterexample and demonstrate that it belongs to your setting but not that in Diakonikolas et al. (2021), possibly in the appendix. If not, then I think it better not to mention this counterexample. \n\n(2) In Section 3.1, your maximum stepsize $\\overline{\\alpha}_k$ is $3/2$ of Diakonikolas et al. (2021). Is your convergence rate also faster than or comparable with that paper? A similar comparison of convergence rate might also be made between your Theorem 3.5 and Theorem 4.5(i) in Diakonikolas et al., 2021.  \n\n(3) To my understanding, $\\|\\overline{z}^k-z^k\\|$ is a generalization of proximal gradient, a popular measure for nonsmooth nonconvex minimization problems. Why do you use the convergence measure $\\|H\\overline{z}^k-Hz^k\\|$ instead of $\\|\\overline{z}^k-z^k\\|$?\n\n(4) In Figure 2, should the region below the dashed line indicates where $\\rho>-1/8L$ and the dashed line indicates where $\\rho=-1/8L$? What does \"positive result\" mean? Diakonikolas et al. 2021 only obtains convergence results at the black square point while you obtain convergence results at the blue round point, right? \n\n(5) In Theorem 3.4, is it better to derive a lower bound of Algorithm 1 instead of EG+, i.e., the lower bound where Algorithm 1 may diverge? \n\n(6) What is the definition of \"origin\" in Example 4? \n\n(7) In the left subfigure of Figure 3, Adaptive EG+ seems to converge to the limit cycle instead of a stationary point. How do you explain? \n\n(8) In Figures 3 and 4, does \"lower bound example\" mean Example 5? Example 5 seems to have the maximally monotone operator $A\\ne 0$. In this case, does $\\|H\\overline{z}^k-Hz^k\\|= \\|F\\overline{z}^k\\|$ still hold? If not, I think the y label should perhaps be $\\|H\\overline{z}^k-Hz^k\\|$ instead of $\\|F\\overline{z}^k\\|$. \n\n(9) In the experiment, for the algorithms with adaptive stepsizes, I think it better to give the specific stepsize values, such as $\\gamma_k=1/k$, etc. \n\n(10) In the experiment, you said \"this is the direct generalization to the constraint setting of the EG+ scheme studied Diakonikolas et al. (2021).\" Does \"this\" mean CEG+ only, or both CEG and CEG+? \n\n(11) The convergence of CurvatureEG+ is assumed not proved in Lemma 4.1. Is it feasible to prove?\n\nMinor comments:\n(1) You might cite the following paper about nonconvex-nonconcave minimax optimization, and discuss about your advantage over it. \n\n[1] Yang, J., Kiyavash, N., \\& He, N. (2020). Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems. ArXiv:2002.09621.\n\n(2) In Theorem 3.1 and 3.4, is it feasible to recommend adaptive stepsizes that lead to the fastest possible convergence rate? \n\n(3) In Figure 1, I think it is better to explain the blue and red curves in either legend or caption. They are multiple trajectories from different initial points, right? Why do some red curves on the right subfigure have small black ends?\n\n(4) I think it better to define \"maximally monotone\" and \"cohypomonotonicity\" or cite the papers that have the definition, as some readers like me see these concepts for the first time. \n\n(5) You might add \"(MVI)\" right after \"Weak Minty inequality\" in Assumption 1.\n\n(6) There's a typo in \"VIs provides a convenient abstraction for a range of problems\", you could use \"provide\". \n\n(7) There's a typo in \"Recal that the resolvent of a maximally monotone operator\", you could use \"Recall\".\n\n(8) In \"by making the extrapolation step adaptive as well\" in Section 3, you might explain which of equation (EG+) is \"extrapolation step\", or maybe use \"making $\\gamma_k$ adaptive as well\"?\n\n(9) Right below Corollary 3.2, should $\\overline{z}^k-F\\overline{z}^k-Hz^k$ be $\\overline{z}^k-\\gamma F\\overline{z}^k-Hz^k$? \n\n(10) In the experiment, I think it better to add \"(cf. Appendix A.1)\" right after \"Example 5\". ", "summary_of_the_paper": "This work extends the extragradient algorithm in Diakonikolas et al. (2021) from unconstrainted and unregularized inclusion problems that satisfy weak Minty inequality (MVI) to their constrained and regularized counterparts. Compared with the original extragradient algorithm, the extended algorithm is proved to converge with a larger range of stepsize choices and MVI-related constant $\\rho$ (implying a larger set of applicable problems) in both deterministic and stochastic inclusion problems. The range of $\\rho$ is also proved tight by providing a lower bound of $\\rho$. The extended algorithm also generalizes the celebrated forward-backward-forward (FBF) algorithm in Tseng (2000). Finally, an improvement of this extended algorithm is proposed using Lipschitz constant backtracking. ", "summary_of_the_review": "Due to the aforementioned pros, I think this is an excellent paper and would like to see it accepted. Some points need to be clarified as aforementioned in the concerns and minor comments. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "89WEs3A_ZBY", "reviewer": "Reviewer_wk1L", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "# Strengths\n- The paper has several theoretical contributions referring to different options for the two step-sizes of EG (see summary above), and importantly, it relaxes the setup of prior work--in particular of (Diakonikolas et al. 2021).\n- The technical contributions are relevant for the community, given past negative results and the current state of existing provable convergence results. \n----\n# Weaknesses\n- Inconsistency of methods the authors provide theoretical/empirical results for.  This paper mixes several different options for the step sizes, and the convergence for the stochastic counterparts of the considered full-batch methods is not shown. In particular, the stochastic method requires one of the step sizes to be diminishing, and the considered full-batch methods require different assumptions on the step sizes. \n- Lack of empirical evaluation to verify if the results are helpful for challenging real-world problems, or alternatively a discussion of the importance of the provided results in practice. \n- In terms of novelty, the paper largely builds on (Diakonikolas et al. 2021), and combines it with recent developments of operator splitting techniques (Latafat & Patrinos, 2017; Giselsson, 2021) to provide the relaxation of the problem.\n- Due to shifting between the different options, the writing is somewhat confusing and hard to follow (see examples below). \n\n----\n# Minor Comments and Suggestions\n- While the writeup seems technically precise, it is not self-contained. In particular, there are missing definitions. As these are the basis for understanding the presented results the definitions should be provided. Examples of non-defined terms: monotone operators, maximally monotone, cohypomonotonicity, etc., and even defining L-Lipschitz is common. \n- Some typos: \n   - in contribution 3: our result are $\\rightarrow$ is\n   - related works: approaches has been $\\rightarrow$  have been\n   - Hsieh et al .. considers  $\\rightarrow$ consider\n   - last sentence Sec. 1: they only considering $\\rightarrow$ consider\n- Consider naming Alg.1 \n- In my opinion, the title could be misleading, it could be interpreted as a novel technique to escape limit cycles for general non-convex contained problems. It does not emphasize that this work specifically focuses on (variants of) extragradient and that the global convergence holds solely for the weak MVI setup. \n- It is hard to follow which proposed method the listed contributions refer to. It might be helpful to define the method in a general form before this listing so that you can be more precise about which step size is adaptive/constant/diminishing etc for each of the contributions.\n- adding more detailed related work section (if lack of space in Appendix) to list relevant works on convergence results (e.g. the reference below)\n\n----\n# Questions\n- Is it possible to provide a separate convergence theorem for CurvatureEG+ on weak MVI, ideally for a larger set of problems than Thm 3.1. as the results indicate?\n- How does CEG+ perform on Forsaken (Fig.1)?\n- Does CurvatureEG+ escape unstable critical points? In particular, how does it perform on the almost bilinear toy example of Hsieh et al '21? \n- Since CurvatureEG+ uses an iterative way to find the step size, it is important that the  authors provide a comparison with EG on a problem where EG converges with the x-axis being the computation time\n- Could you comment on the convergence rate you get relative to existing results of EG on monotone variational inequalities, e.g. [1]\n\n[1] Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems, Golowich et. al, 2020", "summary_of_the_paper": "This paper focuses on variants of ExtraGradient (EG) by considering different options for the two step-sizes of the method: one for the extrapolation step and the second for the iterate update. \nBuilding on the analysis of (Diakonikolas et al. 2021),  the paper relaxes the setup therein by allowing a larger range of values for the $\\rho$ parameter (see Fig. 2) of weak Minty Variational Inequality (MVI) which parameter controls the degree of nonconvexity.\n\nIn particular, it provides the following contributions:\n*(i)* Primarily it defines Alg.1 where the step size for the iterate update is adaptive and shows the main convergence result (Thm  3.1.) that under some assumptions (Asm 1), Alg. 1 converges on weak MVI problem.\n*(ii)* It then considers a non-adaptive variant of Alg. 1, dubbed CEG+, which can be seen as a generalization of the EG+ method of (Diakonikolas et al. 2021), and complements the result of the latter by showing that the convergence result is tight on weak MVI;\n*(iii)* extends CEG+ by using an adaptive scheme for the first step size (for the extrapolation) which uses Lipschitz constant backtracking, and Alg.1 for the latter step size (for the iterate update), dubbed CurvatureEG+, which method is shown to empirically converge on some toy-examples on which CEG+ does not;\n*(iv)* finally, for the stochastic setup the authors consider one of the step-sizes to be diminishing and the other can be constant, and show that this variant converges on weak MVI problems.\n", "summary_of_the_review": "The paper provides several contributions for different variants of the extragradient method, which in general are of interest to the community. \nIt lacks stochastic counterpart convergence guarantees of the full-batch results, and it considers several variants of the method rather than focusing mainly on the method with best convergence properties and to consistently discuss its convergence in full-batch setting, then stochastic, and finally verifying these results and ideally discussing/showing if these are relevant for challenging real-world setups.\nIn summary, the paper is somewhat rushed, and although it is in a good and valuable direction, at this stage, it requires major modifications (see comments above) and additional stochastic counterpart results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

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