Weaker MVI Condition: Extragradient Methods with Multi-Step Exploration
Authors: Yifeng Fan
Yongqiang Li
Bo Chen
Venue: ICLR 2024 poster (2024)
Keywords: extragradient
minimax
nonconvex-nonconcave
variational inequilities
saddle point problem
Primary area: optimization
TL;DR: We show that extragradient with multistep extrapolation solve more problems and propose a new algorithm that tackles cycling behaviors

Abstract: This paper proposes a new framework of algorithms that is extended from the celebrated extragradient algorithm. The min-max problem has attracted increasing attention because of its applications in machine learning tasks such as generative adversarial networks (GANs) training. While there has been exhaustive research on convex-concave setting, problem of nonconvex-nonconcave setting faces many challenges, such as convergence to limit cycles. Given that general min-max optimization has been found to be intractable, recent research efforts have shifted towards tackling structured problems. One of these follows the weak Minty variational inequality (weak MVI), which is motivated by relaxing Minty variational inequality (mvi) without compromising convergence guarantee of extragradient algorithm. Existing extragradient-type algorithms involve one exploration step and one update step per iteration. We analyze the algorithms with multiple exploration steps and show that current assumption can be further relaxed when more exploration is introduced. Furthermore, we design an adaptive algorithm that explores until the optimal improvement is achieved. This process exploits information from the whole trajectory and effectively tackles cyclic behaviors.

Published as a conference paper at ICLR 2024
WEAKER MVI CONDITION: EXTRAGRADIENT METH- ODS WITH MULTI-STEP EXPLORATION
Yifeng Fan Yonggiang Li
Bo Chen
Zhejiang University of Technology ( fengfan, ygl i, behen) @z jut edu.cn
ABSTRACT
This paper proposes a new framework of algorithms that is extended from the celebrated extragradient algorithm. The min-max problem has attracted increasing attention because of its applications in machine learning tasks such as generative adversarial networks (GANs) training. While there has been exhaustive research convex-concave setting, problem of noncomvee-nnncoonaae setting faces many challenges, such as convergence to limit cycles. Given that general min-max op- timization has been found to be intractable, recent research efforts have shifted towards tackling structured problems. One of these follows the weak Minty vari- ational inequality (weak MVT), which is motivated by relaxing Minty variational inequality (MV1) without compromising convergence guarantee of extragradient algorithm. Existing extragradient-type algorithms involve one exploration step and one update step per iteration. We analyze the algorithms with multiple exploration steps and show that current assumption can be further relaxed when more explo- ration is introduced. Furthermore, we design an adaptive algorithm that explores until the optimal improvement achieved. This process exploits information from the whole trajectory and effectively tackles cyclic behaviors.
INTRODUCTION
Min-max optimization has aroused recent interest due to its significant applications in machine learning tasks, such as generative adversarial networks, adversarial training, robust learning and sharpness-aware minimization (Goodfellow et al., 2014; Madry et al., 2018; Levy et al., 2020; Foret et al., 2020).
Min-max optimization aims to find saddle point of a objective function. Theories and methods have been extensively studied for decades, usually through the prospective of variational inequalities. There has been a plethora of literature focusing on convex-concave (Tseng, 2008; Nesterov, 2007; Nemirovski, 2004) nonconvex-concave (Xu al., 2023; Bog & Böhm, 2023; Lin et al., 2020) objectives. However, problem with nonconvex-noncoocaae objective remains relatively obscure. Finding local solution general nonconvex-noncconene problems has been proved intractable (Daskalakis et al., 2021).
One powerful tool that has been revisited is the celebrated extragradient (Korpelevich, 1976), which has been found effective in solving a class of nonconvex cowereexxnononccveee problems (Daskalakis et al., 2020). Diakonikolas et al. (2021) first introduce this new structure as weak Minty variational inequality, featuring weaker assumption than monotonicity. They make a slight modification on extragradient (named EG+) and establish convergence guarantee on this structure. Pethick al. (2022) elucidate the mechanism of EG+ and prove tight parameter range of p > -1/21, where represents the weak Minty parameter that describes the degree of non-monotonicity and L is the Lipschitz constant, which is the known best range to have convergence guarantee for this class of problems.
Our contributions Building the works of Pethick al. (2022) and Diakonikolas et al. (2021), we generalize the extragradient algorithm to multi-step cases which adapt to a larger range of problems. Furthermore, propose algorithm that exploits more than local information by

---

Published as a conference paper at ICLR 2024
introducing adaptive exploration.
1. We analyze the algorithms with two and more exploration steps. We discover that the range of p in weak MV1 assumption can be relaxed when more exploration steps are introduced. Especially, when the sum of exploration stepsizes in one iteration is still bounded by !/t., a similar type of convergence guarantee can be established. Under this restriction, the assumption parameter can be relaxed to p > -2--////1. Additionally, for n are unrestricted by these constraints.
establish the range of p where the stepsizes
2. Building on the established convergence results, introduce novel algorithm that adaptively increases the number of exploration steps. This is inspired by the idea of interpreting each update as projection onto certain hyperplane, defined by the weak Minty inequality. Every exploration point provides information and helps narrow down the target range. This algorithm effectively tackles cyclic behaviors.
Related work Recent application in GAN training has motivated research on min-max optimization and revisit to classic algorithms. line of pioneering works introduces the traditional perspective of variational inequality and resorts to optimistic methods (Daskalakis et al., 2018; Gidel et al., 2018; Mertikopoulos et al., 2018). Simple algorithm such as gradient descent ascent is also examined under the
condition (Yang al., 2020). Hsieh et al. (2021) revisit list of algorithms including extragradient and demonstrate that current methods still have trouble avoiding limit cycles.
Weak Minty variational inequality, also known star-negative comonotonicity, has received recent attention from community and has become a common structure setting. Diakonikolas et al. (2021) first introduced weak MVT important assumption, under which their EG+ algorithm enjoys
OLLVkk) convergence rate. Pethick et al. (2022) provide full picture of the algorithm with an adaptive stepsize selection technique. They also propose an algorithm with backtracking line search incorporated, which effectively escape limit cycles and outperforms existing methods. Böhm (2022) propose another variant of EG+ with adaptive stepsize, not requiring knowledge of problem parameter P and L. While most literature provide best-iterate convergence results, last-iterate convergence of EG+ under weak MVT has also been established (Gorbunov et al., 2023; Tran-Dinh, 2023), but under more restrictive parameter p > 1/881.
Another line of work resorts to anchoring techniques. Lee & Kim (2021) combine anchored ex- tragradient with separate stepsizes and obtain a fast (11/k) rate on gradient norm. Alcala et al. (2023) introduce new moving anchor technique generalizing current algorithms and attain optimal convergence rate. These works are under a more restrictive (unstarred) negative comonotonicity assumption.
When it comes to stochastic methods, similar thought to EG+ can be found in Hsich et al. (2020), where they show that doubled exploration stepsize in stochastic extragradient is effective on avoiding cycles. Diakonikolas et al. (2021) extend their deterministic result to stochastic setting with unbiased oracle of gradient and bounded variance by increasing oracle queries. Pethick et al. (2023) establish almost sure convergence with single query per iteration, involving one fixed and one diminishing stepsize. Their method works under the same assumption of > -1/2t. Aside from separate stepsizes, other variants such as stochastic past extragradient (SPEG) have been shown effective under weak MV1 assumption, along with new expected residual condition (Choudhury et al., 2023).
PRELIMINARIES
We consider two real vectors, æ E Rdd, y R&d and minimax problems of the form:
min max f(x, v)
(2.1)
#ER yeR
where f Re R.d R. is smooth (possibly nonconvex-noncooeaav function and d, + dy d.
To study the stationary point, we consider the saddle gradient operator F Rd Rd defined via V Vnf(x, y) where z = y
x
Fz =
(2,
2

---

Published as a conference paper at ICLR 2024
We want to find zeros of this operator, the set of which denoted by zerF = fz E R Fz 0}.
This is first-order necessary condition being the saddle point satisfying (2.1).
In this paper, study problems in which operator F satisfies the following assumptions.
Assumption 1. (L-Lipschitz continuity). Operator is L-Lipschitz continuous. For any u, v R4,
[ Full I L|(u - v|l
(2.2)
Assumption 2. (Weak MVI). There exists x" E zerF such that for any 2 E R
(Fz, 2²) 2 Fz||
(2.3)
for some p E (po, oo).
In this paper, the proposed methods provide convergence guarantee for problems where (-(1-Vo/L,, oo), where e is Euler's s number.
2.1 PRELIMINARY ALGORITHMS
EG (Korpelevich, 1976):
z² 2 0g. Fz
(EG)
k+1 z² FrFF
where is the stepsize.
Extragradient classical algorithm for saddle point problems. Often regarded explicit approximation of the proximal point method, EG employs the same stepsize for both extrapolation and update phases.
EG+ (Diakonikolas et al., 2021):
z x - - Fi Fz
(EG+)
k+1 z² 1 z
where I/L and 0g 1/2L are the stepsizes.
EG+ a generalization EG, allowing an aggressive extrapolation step. This slight modification makes it effective for weak MVI problems under p > -1/St.
AdaptiveEG+ (Pethick et al., 2022):
= x² 7/ Fz
FF k: zk 2/
Ok 0k
|F
(AdaptiveEG+)
2 k+1 2² DEaa F d E (0.2)
where " E (1-2pl+, 1/4,, are the stepsizes and E (-71/2,p) pl. A E (0,2) are relaxation
parameters.
This algorithm provides tight range of ay for convergence of (EG+). Diving into the conception of projection, (AdaptiveEGG+) broadens the problem range to p > -1/21, which has been the best known result for weak MVI problems.
2.2 PRELIMINARY DEFINITIONS
Definition 2.1. (Weak MVI halfspace). Given Rdd, Define weak MVT halfspace at u as the set restricted by (2.3) at u,
D(u) (w Rdd (Fu, w) Fr The boundary of D(u) is hyperplane with Fu normal vector,
(2.4)
0D(u) (w E Rd (Fu, w) pl F2
(2.5)

---

Published as a conference paper at ICLR 2024
Under Assumption 2, we have Vu E R D(u). As access gradient at any point, we get the information that zero x" must be inside the corresponding halfspace.
The signed distance from Definition 2.2. (Signed distance). Given u e R² and convex set S c RR. u to S is defined by
OS),
iu S
d(u, S) = [-d(u, US), if s
(2.6)
where üS denotes the boundary S d(u, OS) = inf aeas d(u, v)-
S and S denotes the complement S. d(u, 0S) is defined by
The signed distance d(u,S) S) is positive when u is out of S and negative when u is inside S.
In this paper, focus on the signed distance between point and weak MVT halfspace, which is linear and therefore convex. More specifically, the iteration point z and weak MVI halfspace at exploration point z/.
Lemma 2.3. Given u, E Rd the signed distance from to D(u) is
d(v,D(u)) Ful (Fu, v) |Fu|
(2.7)
GENERALIZED FRAMEWORK OF PROJECTION ALGORITTMSS
Projection-type algorithms have been extensively utilized in variational inequality problems (Solodov Tseng, 1996; Solodov & Svaiter, 1999). Recent work of Pethick et al. (2022) employs projection technique in generalizing extragradient algorithm.
Notice that in (AdaptiveEG+), the update stepsize ag = 03 (FS* |F
d(= (===)((=)))
|F
The main idea lies in perceiving each update as projection onto the hyperplane @D () Due to Assumption 2, z² E D(**), while z & D(z²) since the algorithm is designed to make a₁ > 0. As a result, the hyperplane naturally separates =* and z". The parameters of o S p and À E (0, 2) bear no effect on convergence, given the fact that scaling the projection distance no more than twice still takes you closer to the hyperplane.
It is interesting to notice that in this process. there is restriction on the selection of z² Literally any g generates a halfspace that xt E D(=*). Therefore the same mechanism still applies as long as = is chosen such that x D(z*), as at every iteration point, we can find another point such that the iteration point is out its weak MVI halfspace. The border hyperplane consequently separates the iteration point z² and the desired zero z². Therefore intuitively, a projection onto the hyperplane get closer to z" This point does not necessarily have be attained by a single forward operator evaluation z =² Fz
equivalently d(z", D)=*)) )) > 0. In other words,
long
Given the foregoing discussion, it is straightforward to propose the following framework for solving the weak MVI type saddle point problems.
G
FF gk x/
as = akk
FF*112 1|2
> 0, Sp
(3.1)
b+ = zb Ae
Fzz du E (0,2)
where for all k G5 : Rd + Rdd is a map such that Vz E IRd, d(z, D(G+2)) > and σ S is selected such that a > 0.
In other words. if for every = we are able to find 2µ so that x² Φ D(z)), then the gradient Fž, can be used for extragradient update. Our objective is to find such maps that guarantee this property. One example is G3 = id 7/ F with -- + < 7kk & l/r. used in EG+, where id denotes identity operator and [x] m0 x).
Such algorithms enjoy similar convergence guarantee to (AdaptiveEG+))(Pcthiik et al., 2022), Thm. 3.1), with an O(//R) best-iterate convergence rate.
4

---

Published as a conference paper at ICLR 2024
Theorem 3.1. Let F be L-Lipschitz and satisfy weak Minty condition with Let X Tk I p. Assume that lim x- 1 and lim inf k- ag > 0. Assume that for all d(zg,Di D))))) Assume that dg is selected such that ag >> O. Consider the sequences (z") and (z*) kEN generated by (3.1). Then,
(0, 2),
min
| k(m + 1) 11= 201
(3.2)
k=
where x lim in (2 )a)a Moreover, (ž* kEE converges to z".
Note that no limitation on p is mentioned in this framework. Actually, the range of manageable depends on the selection of σk and the map Gg. which will be covered in the next section. More
supg* (F -======" =x=)
specifically, >
where the right-hand side is related to the settings of Gg.
(a) GDA
(b) AdaptiveEG++
(c) (Algorithun 1)
Figure 1: Intuition of projection algorithms
From another perspective, every operator evaluation Fz provides new information about z". x" D(z) rules out the possibility that x' is in another halfspacce This explains why increasing exploration plays a crucial role. Gradient descent ascent fails in < weak MVI problems since both z* and z" is in (2=*) and the hyperplane cannot separate them. (AdaptiveEG+)) manages to find suitable g* with larger extrapolation stepsize to separate them and update (project) with a smaller stepsize.
It then natural increase exploration by taking further steps in the subroutine Gk, pursuing larger projection distance. See Fig. for intuition. This naturally leads to question: what kind of convergence guarantee can be provided for aforementioned multi-step algorithms? We address this problem in Section and introduce the "max distance" algorithm in Section 5.
4 MULTI-STEP EXTRAGRADIENT
We start from the (AdaptiveEG+) algorithm and generalize it to multi-step cases.
Pethick et al. (2022) obtained a range of p E (- = 0o) for the algorithm to converge and demon- strated its tightness. Moreover, they restated the condition p 77//2, where the stepsize satisfies T Σ L.L We recxamine the claim and articulate our understanding.
The key is to assure positive projection distance. Taking σμ
(F z 2²
|F p (F Fz*)
0g p-
|
p
+
7
L
(4.1)
The inequality follows from rearranging | Fz*11 S 7h F F> into |F
I- Fzk|
<
L
|F and applying Cauchy-Schwarz inequality on it.
Rather than the stated > -7n/2 which only applics when " S 1/2, a more precise condition should be p 1 Increasing extrapolation stepsize 7k does not extend the lower bound of p infinitely,

---

Published as a conference paper at ICLR 2024
but push it closer -1/L. Actually, objective functions with p -1/L are knotty for first order methods. For example, both Fz = Lz and Fz = L falls into the structure. Particularly, when 3 ك -1, 3-cohypomonotone operator F may fail have at most single-valued resolvent Jr, making it problematic in finding fixed points of Jr (Table 1, (Bauschke et al., 2021)).
4.1 2-STEP EXTRAGRADIENT
Consider the n-step extragradient.
Vi [n]] x =xi-1 = P
z² z
(F z# 2²
(n-step EG)
0Kk Ok
FF >0,0
k+1 2² Fz A E (0,2)
where zt== 2 is the current point, 2 i [n]] are intermediate steps, and z x++ is the adopted update. The extrapolation point = is attained by n steps of gradient descent.
In this subsection we focus on the where 2. Recall that selection of stepsizes and os plays crucial rule in the algorithm and determines the range of problem parameter p that the algorithm can address. We elaborate in the subsequent theorem how choose parameters that ensures convergence.
Theorem 4.1. Let F be L-Lipschitz and satisfy weak Minty condition with p. Let n 2. Assume that for all `ik1 6/L,, 7k.2 = L1/L, and 81, 82 (0, 1). Assume that lim inf )x A₂) and lim kn > 0. for all k, a% S p and
(++))))60))
1
0k
1
221-69((1-63)
5 51-1
+
1482
62
+
(4.2)
Then the sequence (** KEN generated by (n-step EG) satisfies min mm R(m+TJ ||20 112 where k = lim inf 2a - (2)))
F
Selecting the parameters according to (4.2) guarantees best-iterate convergence. In the following theorem, present the specific parameter selection that maximize the range of p in both cases.
Theorem 4.2. Let F be L-Lipschitz and satisfy weak Minty condition with p. Let n = 2. Assume that for all 7k.1 5./T,, 7x.2 = 62/1., and 61, 82 (0, 1). Assume that lim inf x-f (2 Aτ) 0 4 and lim inf t00 ag 0. Let K lim & (2 Ax)a
(i) for all k 81 = 2 82 2 and ax p
71 then the sequence )EEN generated by
5
(n-step EG) satisfies min I F v a(m+1) 2| =1"
(ii) for all k, 51 = ò1 52 = 82 and o = = L. where on R 0.52212, & R 0.644793 is the unique solution of following equations.
83 (1 55) = (1 87)
80 (1+ 52)4
(4.3)
81 62 1,01, 82 <1
and Ç=
8 11-18-83) 8
Re 0.5834, then the sequence kEN) generated by (n-step
2(1-3)(1-3))
1+02
EG) satisfies min:=o.1.....
|F* 1|2
< m(m+1 || 1²1
The theorem presents quite interesting results. When the sum sub-iteration stepsizes is bounded by I/L, a familiar stepsize choice in preliminary algorithms, the optimal range is attained under succinct invariant stepsize setting. However in otherwise situation, suggested parameters are highly complicated varying stepsizes. Note that invariant and varying both refer to sub-iteration stepsizes Th. " here and in the subsequent discussion. See Fig. in Appendix C. 1 for a contour of (4.2) that incorporates the results in Theorem 4.1 and 4.2.

---

Published as a conference paper at ICLR 2024
4.2 n-STEP EXTRAGRADIENT
While the case of Ei=1 nhi L > 1 is convoluted even when n = 2, we are able to generalize the results when Σi=1 NkiL S to 2 3 cases:
Theorem 4.3. Let F be L-Lipschitz and satisfy weak Minty condition with p. Assume that for all k and i E [n], Th.s = 6/1,, 6g E (0, 1) and Ei=1 6g S 1. Assume that lim inf&->c 2x A1) > 0
and lim inf soc ag 0. for all oh S pand
L (
(4.4)
1+8,
Then the sequence (EE) generated by (n-step EG)
satisfies min s
M(++TJ ||=0 - 2=1 where k = lim inf AR(2 As)o
Given the positive result extended, this next theorem expands our understanding of parameter selection from point to line, thus broadening the algorithm's adaptability.
Theorem 4.4. Let F be L-Lipschitz and satisfy weak Minty condition with p. Assume that for all k and E [n]. Thei = 7 =811. Assume that lim inf )x - Ax) > O and lim inf info-00 Cr. > O.
(i) 1ʃō E (L - 11+ 1.. as E (-m
(1+ 7, and > - 11
where |x|+ = max (0, x), then the sequence )eeN generated by (n-step EG) satisfies
0...........l. 1 k(m+1) || 2013 where lim inf \x 2 )a
(ii) Given any p > - (1 - 2), ler n 242log 1. then >>> - (1+
Theorem 4.4 (i) provides the ranges for y and a% under invariant stepsize. When n the algorithm recovers the parameter range E (1- 1 1/, 1/2. and dº E (-7/2, p) from (AdaptiveEG+). Selecting d% near its lower bound is the common practice when p is unknown. Theorem 4.4 (ii) establishes the global range of p E (-(1-1/)/z, 20) in this paper.
We remark that the range of p in Theorem 4.4 (i) not the global optimal result. can be improved if there restriction on 7 L, just in the case of 2. Yet it is interesting to figure out whether the global optimum of -pp converges to 1 1/c as n + co. Our answer In numerical experiments, 3-step EG with 8n 0.272899, 52 0.512753, &g as 0.515522 demonstrates a range - -p I, 2 0.632242, which already exceeds 1 - 1/e, and 4-step EG improves it least LpoL 0.657724. Refer to Appendix C.4 for more details. This leaves room for further enhancements.
5 ADAPTIVE EXPLORATION BY PURSUING MAX DISTANCE
is discussed Section 4 that increasing extrapolation stepsize push the lower bound of p towards the threshold of l/t.. Inspired by this we propose algorithm that explores aggressively. In the following scheme, extrapolation process will not stop until projection distance stops increasing.
The algorithm aims find projection distance large possible. Thanks to the convergence results in Section 4.2, choosing early stepsizes in accordance with (n-step EG) guarantees a positive distance for problems with p - 2) and subsequent explorations will only increase it.
Note that the distances may converge and thus be monotonic, when the GDA sub-iteration of zt directly converges. Therefore very small tolerance > 0 is introduced to preclude the sub- iterations from endless loop. The algorithm may have worse complexity in such scenarios when F more structured than monotone, reflecting a trade-off between complexity in casier problems and convergence in a broader class. $2 recovers GDA when the algorithm potentially stagnates due to intractable local environment, thereby circumvents thorny areas (see Example 3 and Appendix D.3).
Parameter choice and knowledge of By setting o = p. Algorithm exploit the information of p to the largest extent. A smaller d S still guarantees convergence long as og > since
7

---

Published as a conference paper at ICLR 2024
Algorithm Max Distance Extragradient
initialize:
= E _k" p; A E (0,2), n E (0, 1/1], on S p and tolerance E1, 62 > 0 repeat for k k= 0.1....
Let z = x d -00
repeat for i = ....
Let - = - -1 ?/ F2
Compute estimated distance
|| 1 Th F2
(F
25
x
d
until de - d <11
Let g² 2, d d
Compute stepsize
d
(F #
2/)
||
0k
Update
ak 2 E2 then 2 *+1 1 else 2++1 = z
2²
FzaFFz
until convergence return *++
projection onto larger halfspace still proceed toward the goal. safe parameter range can be found in Theorem 4.4 (i). More aggressive candidates such as o = -1/2 may apply to harder problems.
EXAMPLES AND EXPERIMENTS
We consider three classic examples corresponding to respectively.
- p (- < -
Example 1. (bilinear)
b
min max (x, = azy 2 11² y2) RER vER
(Bilinear)
where a > 0, b b<0 O. Example 2. ((Pethick et al., 2022), Example 3)
Fz (v)(x, y) <b x) - xr)
(PolarGame)
where (Ix y) = ar (-1 2 + ()) (-9 + 16x² + y²) and a =
Example 3. ((Hsieh et al., 2021), Example 5.2)
min max [(x, y) = x - 0.45) + 6(x) 6(v) ØEk BER
(Forsaken)
where 6(2) 122 2
Tested algorithms include (n-step EG), (MDEG) in this paper. (AdaptiveEG++) (CurvaturelGG+) from (Pethick et al., 2022) and (EG+ Adaptive) from (Böhm, 2022). All experiments are implemented without the knowledge of p. In Example we choose the parameters make pL E (-0.6, 0.5) and verify the convergence result of (n-step EG) in Theorem 4.4(i). Example 2 exhibits two limit cycles, one attracting and one repellent. (Algorithm 1) excels at handling such cyclic problems and evades the limit cycle in the first iteration. Example further exceeds the manageable threshold of -1/r, posing challenges for the algorithms. The basic version (Algorithm 1) erroneously stagnates in the problematic area, echoing the discussion on intractability. Introducing the tolerance s2 prevents the algorithms from incorrect convergence and helps to recover GDA when in a predicament. The modified algorithm cireumvents the thorny as shown in Fig. 4. Among all tested algorithms, (Algorithm 1) and (CurvatureEG+) converge in Example and 3, where our method relies solely on global information.
8

---

Published as a conference paper at ICLR 2024
(a) pL -
(b) pL -V3/3
and and Figure 2: Example 1. p 1/2L examples which are beyond the lower bound of (AdaptiveEG+)
(n-step EG) converges with guarantee.
0/0
AdagtiveEG+
2-stop
Adaptive
Figure 3: Example with pL = 00888552 in the box ||=||00 S cycle and converges to the stationary point. The first iterations of (MDEG) are attained after 30, 23, 23, 23, exploration steps respectively.
3/2. (MDEG) break out of the limit
6:00
18"
184
AdaptiveE++
2-step
MDEG
CurvatureEG+
EG+ Adaptive
Figure 4: Example 3 has highly nonmonotonic regions with local pL. 3.04076 which go beyond convergence guarantee of all shown algorithms. (MDEG) bypasses the thorny areas and converges to the stationary point, oulperforming counterparts on operator evaluations.
7 CONCLUSION
This paper opens up new dimension for extragradient-type algorithms and demonstrates how expanding extrapolation could help address more problems. We provide bound analysis on our framework of multi-step extrapolation EG+ algorithms, relax the condition > -1/22 to > -(1-1/)/z and capture past algorithms as special cases. Furthermore, the adaptive method we propose effectively resolves problems with limit cycles. While method utilizes repeated GDA steps in its subroutine, investigating alternative subroutines that offer better approximation of the proximal point operator could represent valuable research direction.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work has been supported by National Natural Science Foundation of China (NSFC) Grant No. 62073294, No. U2341216. We would like to thank the anonymous reviewers for spending time and efforts and bringing in many insightful comments and suggestions, which greatly contributed the improvement of this work.
REFERENCES
James K Alcala, Yat Tin Chow, and Mahesh Sunkula. Moving anchor extragradient methods for smooth structured minimax problems. arXiv preprint arXiv:2308. 12359, 2023.
Heinz H Bauschke, Walaa M Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Mathematical Programming. 189:55-74, 2021.
Axel Böhm. Solving nonnoneee- min-max problems exhibiting weak minty solutions. Transactions on Machine Learning Research, 2022.
Radu loan Bot and Axel Böhm. Alternating proximal-grann gradient steps for (stochastic) nonconvex- concave minimax problems. SIAM Journal on Optimization, 33(3):1884-133) 2023.
Sayantan Choudhury, Eduard Gorbunov, and Nicolas Loizou. Single-call stochastic extragradient methods for structured monotone variational incqualities: Improved analysis under weaker conditions. Advances in Neural Information Processing Systems (NeurlPS), 36, 2023.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis. and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations (ICLR). 2018.
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 33:5527-55400 5540, 2020.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I Jordan. Efficient methods for struc- tured nonconvex-nonconeaay min-max optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2746-2754. PMLR, 2021.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-awart minimization for efficiently improving generalization. In International Conference on Learning Representations (ICLR), 2020.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien variational inequality perspective on generative adversarial networks. In International Conference on Learning Representations (ICLR), 2018
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems (NeurIPS), 27, 2014.
Eduard Gorbunov, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. Convergence of proximal point and extragradient-based methods beyond monotonicity: the case of negative comonotonicity. In International Conference on Machine Learning (ICML), pp. 11614-11641. PMLR, 2023.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min optimization algorithms: Convergence to spurious non-critical sets. In International Conference on Machine Learning (ICML), pp. 4337-4348. PMLR, 2021.
Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Advances in Neural Information Processing Systems (NeurIPS), 33:16223-16223 16234, 2020.
10

---

Published as a conference paper at ICLR 2024
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. Advances in Neural Information Processing Systems (NeurIPS), 34:22588-226101 2021.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems (NeurIPS), 33:8847- 8860, 2020.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concat minimax problems. In International Conference on Machine Learning (ICML). pp. 6083-6093. PMLR, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations (ICLR), 2018.
Arkadi Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-25) 2004.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2-3):319-344, 2007.
Thomas Pethick, Panagiotis Patrinos, Olivier Fercoq, Volkan Cevherå, et al. Escaping limit cycles: Global convergence for constrained conconvex--onconeee minimax problems. In International Conference Learning Representations (ICLR), 2022.
Thomas Pethick, Olivier Fercoq, Puya Latafat, Panagiotis Patrinos, and Volkan Cevher. Solving stochastic weak minty variational inequalities without increasing batch size. International Conference on Learning Representations (ICLR), 2023.
Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845-848, 1980.
Michael V Solodov and Paul Tseng. Modified projection-type methods for monotone variational inequalities. SIAM Journal on Control and Optimization, 34(5):1814-1830, 1996.
Mikhail V Solodov and Benar F Svaiter. A hybrid poojection-proxingg point algorithm. Journal of convex analysis, 6(1):59-70, 1999.
Quoe Tran-Dinh. Sublinear convergence rates of extragradient- methods: A survey on classical and recent developments. arXiv preprint arXiv:2303. 2023.
Paul Tseng, On accelerated proximal gradient methods for convex-concave optimization. SIAM Journal on Optimization, 2(3), 2008
Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. unified single-loop alternating gradient projec- tion algorithm for cancoovexx-ooncane and convex-nonconee minimax problems. Mathematical Programming, pp. 1-72, 2023.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconvex-noncoocant minimax problems. Advances in Neural Information Processing Systems (NeurIPS), 33:1153-1166 2020.
11

---

Published as a conference paper at ICLR 2024
A TECHNICAL LEMMAS
Lemma A.1. Let F be L-Lipschitz and satisfy weak Minty condition with p. Assume that for any 2/ E
Rd there is zh I2d such that d(z*, ))=*)) O. Let 0% S p. d O. Let ag o%
(F 2² =²
1F
xkt 2 AzaFFE* Assume that for all k, ar 0. Then,
x+1 z² 2111
==1 (2 2 21 )4)a 2 F
(A.1)
Proof. From the expression of Ork we know that
(F - = (or: 11*12
(A.2)
S (p- - -x))
(A.3)
Together with Assumption 2
(F 2 - -2") 2 F=
(A.4)
Therefore,
1|2 1
=1
11 2" F
(A.5)
1| 211 2Ax (# -/ -2) 1
(A.6)
I 11 211 - 22xa Xag
(A.7)
11 x= >x(2 Au 1
(A.8)
L
Remark 1. It is worth mentioning that Lemma A.1 is highly related to (Solodov & Svaiter, 1999).
Lemma 2.1.
Notice that when A = 1,
(F z² = as F=* || > 0
(A.9)
(F - = (ox F>
(A.10)
and |+| PH[2*]] 2² Fz# where PM|=** is the projection of x² onto the hyperplane H = (w E I (FZ*, = + oz F = 0}. which is evident from (A.9).
According to (Solodov & Svaiter, 1999), Lemma 2.1,
||* - 2=1 2 x k- - x 11 || k x*
(A.11)
k- _ x ==1 ax F
(A.12)
which is in accordance with Lemma A.1.
Lemma A.2. Let F be L-Liscchitz and satisfy weak Minty condition with p. Let n = 2. Assume that
for all k, 7k,1 81/L. 7k.2 = $2/L, and ò1, 82 E (0, 1). Define function g (0, x (0, 1) IR
+
0(81,82) =
(146)))+0)) 1-89 02 2(1-6)(1-63)
(A.13)
if + 82
Initialize z and generate the sequence (z )s((o) by (n-step EG). The following inequality holds and is light:
FZ Fzk) 2 g()),82)
(A.14)
|
Proof. In this proof we treat Fzt as an axis. Define following as coordinates with respect FzJ.
FF
Fz
(A.15)
F2
12

---

Published as a conference paper at ICLR 2024
21 == (F'zf, Fxb)
(A.16)
||22||
From (n-step EG) and Lipschitz continuity (Assumption 1), it is clear that
|| |x k - Fz'll S 7 F= || 8, F=
(A.17)
|F - Fzžll 7R.2 F Fx1 8211F221
(A.18)
Changing the perspective to fixed Fz2 and Fz we expand and recomplete the square
1
51
||
P'z
||
-
|=
(A.19)
1 89
1
1
1-
67
1
82
||
Fz1ll
F2'll
(A.20)
02
1 82
where Fot is in a ball whose center and radius proportional to FzJ. and F2* is in a ball whose center and radius is proportional to Fzf. The boundary of such area is called a Cartesian oval in two dimension, or a Cartesian surface in three or more dimensions.
Apply Gauchy-Schward inequality on (A.20)
52
82
||
<
FF
Fzz
Fz2)
S
=11
(A.21)
1
82
52
1
02
1
1
|F 1|
- (Fzt
Fz1)
||
(A.22)
1 82
82
1
S
(A.23)
1+ 82
1- 82
Apply Cauchy-Schwarz Schwarz incquality on (A.19)
(F**
Fzt k
F Fz
2
- FF
Fz
F251
F2
(A.24)
1-
1- 89
81
2
F ||||
Fz
(A.25)
1 57
81
(22,F222 2
(Fz Fz2)
(A.26)
87
Divide both sides with || 1| we have
1
61
|2
1-
57
21
1-
F211
(A.27)
From || - F < Fz || it straightforward to see
| S
122 Fzb))
1-53 |F deriving that
|| |
<
201-1 1 1-83
Therefore,
1
25
1 87
21
81
82
(A.28)
Define function p: 1 1-82] + Ik as p(x1)=
(21 51 v
201-1 1-62
= 1-57
1
51
f'(1) 1 1-87 87 1 v(1 - -8) 1)
(A.29)
which is monotonically increasing. Let (z(1 0, the solution is 20
1+ 82
Whether this
21- 62)
1+87 and 1+5, since it is 2(1-
82
extremum point fall into the domain hinge upon the relation between
easy to examine that 1+67 62 1
2(1
1
13

---

Published as a conference paper at ICLR 2024
1+57-62 2(1 2(1-6;)
S 1705
equivalently 8f s - 82)2, 82 S
x 2 p(
)
(A.30)
+ 82
(1+ + (1 + +62
1+82 2(1-4f) T4.5* equivalently 8f > (1 -
If
+ +02 >1
x x pl 1+ 09 83
1 87 63
(A.31)
2(1 - 03)
2(1 - 61)
establishing the lemma.
Lemma A.3. Let F be L-Lipschitz and satisfy weak Minty condition with Assume that for all Vhe 61/1, ò, (0, 1), in and Σi=1 6, S 1. Initialize zh and generate the sequence (z Migao by (n-step EG). The following inequality holds and tight:
F FF
Fzb F 1
(A.32)
1+
Proof. Similar Lemma A.2, what want prove that the minimum value is attained when Fzk is scalar multiple of Fzb We make the following key proposition and prove it using mathematical induction:
Σ im
6
|
Fz 5
F
(A.33)
(1
Σ 8.)
(1 8,)
(1
Σ 6.) II
(1
+ 8.)
E1
1=1
For = 1, it is mentioned in (A.19) that |F
I-8 Fz
-
Assume that the proposition holds for 1. Apply the result the m extrapolations from
z to ak
Σ 6:
Fz
F * |1
5
2
F 2m
(A.34)
(1 Σ 6,)
(1 5.)
(1 -
Σ 8,) (1 5.)
Square both sides and rearrange the equation,
m
61
1 Σ d;
(F F2t 2
| +
| ||2
(A.35)
2
11 1=2
(1 + 5,)
To prove the n vn occasion, we examine the correctness of following inequality.
Σ 6
1
82
Fz
Fzz || 5
1=1
| k
|=
1 87
87
(1
Σ 84) 11 (1
0.)
(1
2 8,)
11
(1
8.)
(A.36)
14

---

Published as a conference paper at ICLR 2024
2
Σ 8G 1=1
61
Fzi
F k
2
F/ ||
F
=
09
12
172
m
1 09
(1- Σ 54) 11 (1 + 0z)
Σ
0:)
1I (1 + 6z)
1=1
1
Σ 8
261 Σ 8,
|F 1
+
|F +
i=1
FF 17*1111
1
1 - 87
m Σ
m
m
(1
5.)
(1 + 6:)2
-1-68 (1-8)((1
Σ
6:)
1
(1 + 6s)
i=1
2
(F Fz
(1 (1-
Σ
6,)
II
[1 + 6,)
1=1
1=1
1
Σ 6;
28 Σ 6;
<
1 +
1=1
|F 11
i=1
|F ||||
1 - 87
m
m73
Σ 6,) m7
(1
Σ 64)
II
(1 + 62)²
(1 81-8))(11
[1 6))
1-1
Σ 5i
1 +
Σ 65
|F
F =mmm! 11
m Σ
m
172
(1 + 6.) m
(1 (1-89) 61)
8.)(1 + 81)
(1 (1-8))(1-))))) - Σ
6.)
II
[1 F= k 1
[=1
1
m
81 Σ
8,
81 + 81)
Σ 8
1=1
12
m (1 - (1) - >
TR
(1) + 61)
(1- (1 - > 6.)
11 (1 + -.)²
1=1
11
m
26 Σ 8,
+
1=1
(1 -1-68 (1( - Σ 6.)
(1 + 6z)
1=1
1=1
81 Σ 5,
r=1
|| +
1
| 1
2
| |||| F 2
(1- (1-88) 81)
Σ 6.)(1 + 81)
II
(1 + 8,)2
II
(1 6,)
81 m
Σ 8,
1
|F
| mm2ml
S 0
m
(1- 01 -
Σ 6,) 61)
51)
(A.37)
It is rather easy to examine the positiveness of the right-hand side
Σ 8
Σ 6
1=1
| 2/! |1
1=1
| *
xm 11
m
VIL
(1 - Σ 6.)
(1 +
8.)
(1- -
Σ 8.)
II (1 + ++))
=1
11
(A.38)
m
Σ 8,
||
(1 - Σ 5,) + +1)
1=1
81
8
2 11 8,) + +,,
|2
|21
1
8
15

---

Published as a conference paper at ICLR 2024
The above two formulae complete the proof of (A.36), and the n case follows from triangle The proposition (A.33) is then proved by
inequality and || 1-07 F2fll
- F=fll-
induction. Using Sauchy-Schwarz inequality we obtain
Σ 6
(F Fz*
Fz
|x
(A.39)
(1- Σ 6.) 1=1 1=1
I1 + 6:)
(1
Σ
63)
II (1 + 6:)
1=1
1=1
(F Fz*)
||
(A.40)
12
11
(1 + 6;)
establishing the lemma.
B PROOFS
Proof of Lemma 2.3. Let w be any point on the hyperplane @D(u). According the definition,
(Fu, u w) - Fu]
(B.1)
Fu is perpendicular to the hyperplane, and the distance from v to @D(u) equal to the length of the orthogonal projection of on Fu.
d(v (D()))
|| will
(B.2)
(Fuu, v0 w/)
(B.3)
|Full
(F',, w)
(Fuu v)
(B.4)
|
Ful
(Fue
w)
(B.5)
|Fuu|
To convert this into signed distance, we remove the absolute value according to Definition If E 8 d(v. (D(u)) > 0. Thus,
E S, d(v, OD(u)) d((,)(((u)) <
d(v) Fu| (Fu, 1)
(B.6)
[Fu||
Proof of Theorem 3.1. Telescoping (A.1) from k 0 to k m.
||20 =112 m+ 201
F
(B.7)
k=
Let Ck = Ax - )z) and i lim inf k- Ek
|| - x 2 2
F
K
1F
(B.8)
k=1
Therefore,
min | <
F
-
(B.9)
171
m + 1)
Since x = lim x-o Ek > 0, F1
} ker converges to zero. Combined with Lipschitzness, KEN converges z².
=| z" =*I]kken converges zero and (=
16

---

Published as a conference paper at ICLR 2024
Proof of Theorem 4.1. Expand the formula for calculating the stepsize otk.
(F 2 =²)
oh Yk. 7k,1 (Fz Fz#))
7k FZZ Fzf))
0k 0k
F 12
F 12
|
(B.10)
The lower bounds of the last two terms are established in Lemma A.2 and (A.22),
7
Og 2 σk + 76,1(611,2))
1 + 82
(B.11)
82
0h + 019(01, 52) +
+ 82
Hence, if (4.2) holds, og 0. is also straightforward that d(z*, D(**)) 0 since p ok- With the assumptions met, we can refer to Theorem 3.1 for the convergence result.
Proof of Theorem 4.2. (i) When d1 + 82 S 1,
1
p σk
1
(B.12)
(1 61) + 62)
2
1
(
2
)²
(B.13)
2 + 81 - 82
5
(B.14)
9T.
The equality in (B.13) holds when 61 = 1/22.
(ii) Define function q {(x,y) 9) x + 1, < 1, 1/ < 1)
R
61 07 82)
(2)
+
(B.15)
2(1 07) 82)
1 1 02
Try to find its critical point,
0g
(1- 87)² 63 + o
(B.16)
08
2(1 81) 83)
0q
1
0/
(1- 87) 82)2 0
(B.17)
08,
(1 (1+8
Equivalently,
(1(1+ = (1(1+))=((100)) (1-)881 87)2 81 + 62) -1 23)
(B.18)
(B.19)
(4.3) follows by rearranging the equations,
86 1 82) (1 61))
(B.20)
=5g(1 + 67) - 62)4
(B,21)
(1(+8))² = (1 + 67) 62)1
(B.22)
We compute the solution Mathematica,
82 (z; 132 + 24=² - -0 + 162
(B.23)
81 54003 + -32233
351d, + 243
(B.24)
189
where 8g- = (2; 132 + 24 20 + 1624) is the adopted notation for the second root of the
polynomial - 132 + 24x² 30 + 1624 in Mathematica's ordering, which is the larger one of its 2 real roots.
17

---

Published as a conference paper at ICLR 2024
The closed form solution of 82 can be solved from the quadratic equation:
5
82
=
16
+
16
V
39 +
3
(576
7V6771)
1
39
(576
7V6771)
2
32
8 8-33
8(3(576 + 7 6777))
(B.25)
61
+
32
39
+
8
(576 + 777711
33
3(57647/6771))
Proof of Theorem 4.3. Notice that Lemma A.3 can applied on parts of the steps,
F FF T2. Fz Fz
(B.26)
F
1 + 6n
[ k Fzh-22
2
(B.27)
F |
(1 + 11+6 1n 66)
(B.28)
(F F ||
1
(B.29)
+ ... (1.(1+)))
Expand Ork.
(F 2 2²
ak ok
| |
(B.30)
711 (F2% Fzt)
+ 72( (F Fet)
+ In (n( Fzti
ok +
(B.31)
| 112
|| 112
8n-
8n
2 0k +
+
(B.32)
L
(1 + 81)... ... (1
8n)
(1+ (1 6m)
1 6n
ok + L
(B.33)
(1+ 81) (1 + 8m)
The incquality tight since equality holds when Fx 1 Fz = Thus, the sufficient and necessary condition of og > 0 is:
Fz
1481
(1+61)...(1+6,)
1 - σk -
(B.34)
(1+6)).... (1 8n)
Similarly, the convergence result follows from Theorem 3.1.
Proof of Theorem 4.4. (i) According to AM-GM inequality,
Σ 5k)a s (1 + 1 ym
(1 (1. 5m) < (1+ n k=1
(B.35)
The equality holds when 81 =...
= Sn 1. Therefore.
1
1
(B.36)
L
(1 + 81) (1 6,)
L
(1
m
8 < and a% p directly come from the theorem assumption.
18

---

Published as a conference paper at ICLR 2024
> Vi+pL 1[+ follows from p o2
1
-
[1+61m
Moreover,
1 1 0k L (1 5)
2 -
1
2 n
(B.37)
)mm
(1+
1
establishing the parameter ranges in Theorem 4.4 (i).
(ii) Given >> (1 1), let = 242 (1+pL)
1 ) n n log (1
(B.38)
n
n
2n
2n
[1 +og (1 + +LL]]
log (1 + PL)
(B.39)
1 (1+ -
(B.40)
1 + PL
p
(1 1 m
(B.41)
establishing Theorem 4.4 (ii).
C FIGURES AND INTUITIONS
C.1 ADDITIONAL FIGURES
vector
range
p=0
p=
-=
P=
Figure 5: This figure illustrates the permissible range of the vector Fz under Assumption 2. and 2.2. Originating from the circle's center z, the vector extends into the shaded area, which is delineated by these assumptions. Notably, the extent of the allowable region is influenced by the relationship between the weak Minty parameter and the Lipschitz constant L. Enumerated are several representative problem settings.
The presented problem settings in Fig. appear in various classic algorithms. variational inequality, also known as star-monotonicity. The MVI ensures that the negative gradient does not point outward from the solution z". (EG+) extends from (EG) and allows for slight extent non-monotinicity with > -1/8L. (AdaptiveEG+)) further relaxes the problem parameter to p 1/2L. These efforts make it permissible for the direction of gradient descent to move away from solution limited extent.
recovers Minty
Our methods introduced in the main paper provide convergence guarantee for problems under > (1-%/)//. Furthermore, > -1/2 marks the boundary tractability. As discussed in Section 4, increasing the exploration stepsize could potentially solve more problems within this range.
Fig. visually encapsulates the findings regarding 2-step EG in Section 4.1. The plot is a contour of the following function, in the box [0, 0.8] [0, 0.8).
if + 82 $
61 (1-10 (1++))
h(6,, 02) =
(C.I)
62
66 >
2(1 2(1 (1 11-83)
I+52
19

---

Published as a conference paper at ICLR 2024
Figure 6: This contour shows the relation between 8,, 82 and the lower bound of -ox presented in (Section 1) The dashed line (---) shows the border line of the two cases ò1 82 1. (+) denotes
(0.5, 0.5). (*) denotes global optimum at (d1. 82) se (0.52212, 0.644793).
The function is continuous on the dashed line 6 + 82 However, its properties change noticeably the dashed line. Notably, the lower left side of the dashed line, the contour lines exhibit symmetry, which vanishes on the upper right side. Moreover, when either dj or d2 approaches 1, the function value tends plummet towards negative infinity.
C.2 WEAK MVI HALESPACE AND (MDEG)
In Fig. we give intuitive explanations for projection algorithms involved in this paper. The blue regions represent the weak halfspace generated from the latest iteration point. Fig. la explains why GDA fails at star-negative conomonotonic problems, as the hyperplane cannot separate z² and Fig. lb shows the principle of (AdaptiveEG+). A larger extrapolation stepsize helps separating z and z=, and a smaller update stepsize complete the projection. Fig. Ic demonstrates how (MDEG) works. Instead increasing stepsize, consecutive extrapolations exploit the structure efficiently.
The example used in the figures is Example with 5, b = 1, and 20 (0, 11), 11/2r.
σ = 1.2 p.
Figure Projection onto convex hull
We mention another perspective that the max distance projection in Algorithm can be considered as an approximation of the projection onto convex hull. Consider òR for convenience. Instead of computing dh d(z D(z+)), construct a convex hull n, D(= and compute the distance d: = d( Ni=1 D(z On obtaining the maximum distance, similarly project onto this convex hull, a = Pn. ))=))) ) This approach, while computationally more expensive, utilizes all the information available throughout the entire exploration process.
As shown in Fig. 7, hyperplane projection performs good approximation of the convex hull scheme. This idea could be helpful in exploring other subroutines. For example, it feasible to choose 2 using Monte Carlo method. When employing such desultory and inconsecutive approach, the convex
20

---

Published as a conference paper at ICLR 2024
hull scheme brings considerable improvement over hyperplane projection. See Fig. 8 for example where the exploration points are randomly selected.
(a) Projection onto the farthest separating hyperplane
(b) Projection onto the convex hull
Figure 8: Comparison when randomly choosing exploration points. The orange arrow denotes the adopted projection.
C.3 RELATION TO PAST EXTRAGRADIENT
Past Extragradient ((Popov, 1980)) is recently proved converge for weak MVI problems with > 1/2t (CChoudhury et al., 2023; Gorbunov et al., 2023; Böhm, 2022)).
Past Extragradient has the following form:
zk th
7/k Fz*
(C.2)
k+ 2 w/. Fz
Since the three points == 2 2 are collinear, it can be viewed PEG derives z directly from ==1 and retraces a step back to get = Despite the differences in extrapolation, both AdaptiveEG+ and PEG perform updates in the form of zk+1 z wy. Fz*, suggesting projection from z onto a hyperplane perpendicular to Fz
(a) Ad The blue point indicates z and the livid point indicotes g
(b) PEG. The green point indi- cates z k-1 The blue point indi-
cales The livid point indicates z
Figure 9: Comparison of AdaptiveEG and PEG
Moreover, the underlying principles for convergence similar:
In AdaptiveEG+, perform extrapolation step from z g² 2² -xx Fz,, and the weak MVI hyperplane 0D( z*) separates * and =".
In PEG, perform an extrapolation step from k-1, gh k (7 + Wk- 1) F& and the weak MVT hyperplane 0D( z*) separates =-1 and z².
21

---

Published as a conference paper at ICLR 2024
Note that in AdaptiveEG+ the extrapolation step follows the form of gradient descent, while it is not the case with PEG.
C.4 72STEP EG AND CARTESIAN OVALS
When we consider n-step extrapolation, we often perceive the last gradient Fz benchmark and measure anterior extrapolations with it. This perspective naturally results from the update rule of og.
When there is extrapolation step, Fz is distributed over circle (ball).
1 F211l
51
F
- T Fz''l
(C.3)
1 57
When there are extrapolation steps, Fz is distributed inside Cartesian oval (surface).
1
81
F2
Fz
F
(C.4)
09
0
1
82
|/
F2
F
(C.5)
02
1
82
(a) 61 = 62 = 0.3
(b) 61 62 = 0.5
(c) 81 = 62 0.65
Figure 10: Cartesian ovals.
(1
2
5 T- + 82 v2, where Fz (1,
1 1-
When there are extrapolation steps, Fz* is distributed inside the envelope of circles (balls) whose center is inside Cartesian oval (surface).
51
F2 k
Fz
k|
<
Fx
(C.6)
87
1
87
1
82
|F
Fzz
S
(C.7)
82
82
1
83
Fz5
<
F2
(C.8)
03
83
We have conducted numerical calculations on 3-step and 4-step cases. The results are presented below along with
1, cases.
n
8,
82
83
84
1
0.5
2
0.52212
0.644793
0.583456
3
0.272899
0.512753
0.515522
0.632242
4
0.22
0.31
0.39
0.44
0.657724
The 3 result is (nearly) tight, obtained from numerical optimization method in Mathematica.
The n = 4 result achieved by manual tests and serves as a lower bound. anticipate that larger will continue to yield an improved range for p.
22

---

Published as a conference paper at ICLR 2024
(a) 82 83 0.2
(b) 61 62 0.3, 6z = 0.4
(c) 82, 82, 03) (0.27, 0.50, 0.53)
Figure 11: 3-step EG. Zero curvature is observed again when ô1 + 82 83
D ADDITIONAL STATEMENTS
D.I EXPERIMENT PARAMETERS
For Example 1, two experiments are conducted.
In the first experiment, 3v2, b = - v7. Mk, 2L In the second experiment, v2, b 1. Thtt TZ,"% Tk
10 0.99 is used in 2-step EG.
1176
625 7N 0.99 is used in 4-step EG.
For Example and Example 3, both experiment Ykis 1, and 0% 21. is used in (MDEG).
Recommended tolerance for (MDEG) is E1 10 E2 10-3
D.2 PROPERTIES OF EXAMPLEE
Lemma D.1. The saddle gradient operator F of f(z,y) = ary + )x² - y²), where > 0, b <<
0,
satisfies Assumption 1 with L va² 122 and Assumption 2 with a²487
V (xr y) yf (x,
Lay + bx by az
b a
Proof. The operator Fz
= Az, where the matrix A
-a b
Fu Fbll = A| Avll 2 ||A|||||u - w/l
(D.1)
Therefore, the Lipschitz constant L = ||A||2 a R
Recall the weak Minty condition, where f(z, y) has the only stationary point x" = (0,
(Fz,z =²) 2 F2|1 (Az) (= =²) 2 ((Az)TAz
(D.2)
(D.3)
I" AT 2 p2 AT Az
(D.4)
6(x² + y²) 2 p(a² (z) + x²)
(D.5)
Therefore, the weak Minty parameter p a²+12
We provide interesting result that (Algorithm 1) converges on Example 1 for p - -7, if the stepsizes are selected infinitely small.
Theorem D.2. Consider Example 1, f(x.y) ary (x² )² where 0, b 0. Apply
(Algorithm 1) on Example with infinitely small stepsize 7ik - 0. Assume that σ = p. 2 1,
20 (No, 3o), then the algorithm converges the the stationary point after one iteration, i.e.
=1 = (0.0).
V Vaf(2,)) (I,()
Tay + bx by at
Proof. Recall that Fz
=
Az, where the matrix A =
-a
Try to normalize A:
23

---

Published as a conference paper at ICLR 2024
A
ta a
(D.6)
Va² + b²
V02
COS
sin 4p
(D.7)
sin 4
c.08 yp
where şp = arctan 5. COS
48 sin Va"+5?
When " O, the discrete process of gradient descent 2 - 7/h F2 evolves into
continuous gradient flow
dz F=
(D.8)
dt
which corresponds linear system & Az. The solution to the ODEs is
(t) At =0))
(D.9)
ccos al sin al
sin at cos at x(0)
c bt
(D.10)
where z00) = (Ira vo) To (cos Pg. sin 0p).
Calculate the gradient vector Fz((t),
Ft(()= = Ae x()))=(0))
(D.11)
e -b
cos at + sin at
a cos at - ssin ot
bcos + a sin at =(0)
(D.12)
aa + bsin at
cos (at + sp sin (at sp)
sin (at + p) -oos (at + (p) z(0)
Le bt
(D.13)
Since the matrix a rotation matrix.
[| = Le Le-bi [=(0]
Irge bt
(D.14)
Furthermore,
(xx(t)xx(t)) =t) Fz(t)
(D.15)
Le 2ht =(0))
cos at
sin at cos
cos (at 10) sin (at + ())
sin (at (p) cos (at + sp) z(0)
(D.16)
sin at
Cos yp sin
sin gp)
Le 2ht z00)
cos z(0)
(D.17)
Le 2ht (z) + vo) cos P
(D.18)
Lige 2hr cos yp
(D.19)
The matrix multiplication is straightforward since they rotation matrices.
(Fz(t),z(0)) =(0)
(D.20)
Le x00"" cos (at 10) sin (at + s)
sin (at :p) cos (at + (p) z(0)
(D.21)
Le Le- (~) v cos (al s)
(D.22)
Lrge cos (at + up)
(D.23)
Note that pL = Vo*48"
cos s. Now we can calculate the projection distance,
d(z(0),D(z(1))
(D.24)
24

---

Published as a conference paper at ICLR 2024
=p]|Fz(t||| (Fz(t), x(t) z(0))
(D.25)
['x(tt]]
=pLmie bt + rue bl cos ro cos (at + yp)
(D.26)
--ree cos + roe bb cos ro cos (at + sp)
(D.27)
To cos (at + +p)
(D.28)
Let us simplify the notation with d(t) ((zz(0))((z(()))) The derivative d' d'()) arg sin (at + 4p).
At the starting point, d(0) - To cos & < 0, d' (0) ary sin y > 0. The signed distance is initially negative and within a increasing interval.
Algorithm 1 adopts the projection when the distance function reaches its first local maximum value. Given the nature of the cosine function, becomes apparent that the final distance will be d0 d( d("=))== ro- Consequently,
F = Fz
(D.29)
u(a v
L
1 0
0 z(0)
=
66n
T,2
(D.30)
The stepsize og
p |2
Mn L-1 Therefore,
z 2 0g Fz =0 -0
(D.31)
establishing the theorem.
D.3 PROPERTIES EXAMPLE 3
-15
Figure 12: Contour of local pL in Example 3
is introduced by Pethick et al. (2022) that in the box || S 3/2, the object function has
Lipschitz constant L so V (1089 801761 + 993841) ~ 12.4026. The critical point is z" (0.0780267, 0.4119344111 According to our calculation, global weak MVT parameter records -1.22057 at the point z' = (-0.258079, 0.79 0.791652). Recall that 1 ~ 00.0806285.
However, this astonishing value of pL As 118.8889 does not reflect much of its nature. Looking into the local value of p and L in Fig. 12 we find that most areas remain tractable parameter of - while a minimum value of pL = -3. 3.04477 is recorded at the point (1.03889, 1.35309). Furthermore in the outer areas colored in white, PL rises dramatically very large positive value. It is plausible that these anomalies prevent convergence, and convergent algorithms actually circumvent such thorny area and make progress in tractable area.
25

---

Published as a conference paper at ICLR 2024
-1
(a)
(b) 0 1/L
(c) -
1980
13
(d) 10/L
(e) 15/z
Figure 13: Parameter adaptability of (MDEG).
As shown in Fig. 13, wide range of choice of σg leads convergence. From σ 0 o (MDEG) withstands the limit cycles. Convergence to limit cycle is observed under the parameter of 0% L. While the glohal I. Rs 12.4026 reflects a spike of local Lipschitz constant near the border, even considering L, 2 1.97703 in smaller box of || I 1, the algorithm makes good coverage of σ from + to
26


Reviews:
[{"review_id": "elvXEIYyOj", "reviewer": "Reviewer_xJXM", "summary": "The paper focuses on solving structured, non-monotone variational inequality problems that satisfy the weak Minty inequality (eq. 2.3). The proposed approach is based on multi-step methods (per iteration), where multiple evaluations of the operator are computed at consecutive points extrapolated through an iterative subroutine at each parameter update. \nIt is demonstrated that an extragradient method with two or finite extrapolation steps can solve this problem, provided that the problem's parameters are known. Additionally, a variant is proposed that adaptively determines the number of extrapolation steps required, relying on knowledge of a parameter of the assumed problem structure.", "questions": "1. On page 4, you mentioned that the lower bound can be represented by parameters in $G_k$. However, I am unsure how convergence can be proven if $\\rho$ is estimated as commented therein. Could you please elaborate on this?  \n2. In Thm. 2.5 what is the assumption on $\\rho_0$?\n3. Could you describe in more detail how Fig. 2 was obtained? (are $L,\\rho$ from a specific problem?)", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper addresses a challenging problem, establishes convergence guarantees in a unifying way, and provides some intuition. The first method slightly modifies existing ones, whereas the second one (Alg. 1) builds on the theoretical results.", "weaknesses": "*The guarantee requires knowing $\\rho$*. \nTo ensure convergence, it is necessary to know the $\\rho$ problem parameter. However, this presents a challenge as the convergence guarantee depends on it. Although the authors suggest ways to estimate it, it remains uncertain if the proposed approach will converge when using a noisy estimate. This limitation also applies to Alg. 1, which also requires knowledge of $\\rho$ to function correctly.\n\n\n\n*The presentation of the theorems*. \nThe theorems in the second part are presented in a very convoluted manner, making it difficult to interpret the added parameters. Some of the included assumptions are not evident from the statements, which further adds to the confusion. After carefully re-reading the second part, it is still unclear what the precise assumptions, convergence rate, and convergence measure are.\n\n\n*Writing.*\nThe writeup needs further refinement. See the non-exhaustive examples below (listed as Minor).\n\n\n*Additional practical concerns.*\nThe studied methods involve a variable number of inner steps, which makes it more complex than the methods discussed in this paper. As a result, I am uncertain whether it can be applied to a wider range of problem classes. However, it is reassuring that it offers guarantees for the specific problem class addressed in this paper.\n\n\n\n# Other\n\n- Many of the figures are not referenced, making it unclear when the reader should consult them. Moreover, these are not explained, for example, it would be helpful to describe how Fig. 2 helps understand the theorems.\n- I wouldn't classify it as a *more than local* method (page 1) because the information is still very much local, but it's applied to multiple points, which has obvious computational disadvantages.\n- $\\rho$ should be listed as input to Alg. 1.\n\n\n# Minor \n\n\n\n- The abstract has numerous typos, for example:\n   - Min-max problem -> The min-max problem\n   -  application in ML ->  applications in ML\n   - exhaustive researches -> exhaustive research\n   - problem on nonconvex-nonconcave setting -> problem of nonconvex-nonconcave setting \n   -  is proved -> has proved\n   - process exploit  [...] tackle -> process exploits [...] tackles\n\n- Introduction:\n   - $\\rho, L$ are mentioned without introducing them. It would be helpful if at least (2.3) is moved in the introduction and if it is mentioned that $L$ is the Lipschitz constant\n   - typo: algorithm that exploit -> exploits\n   - similarly, it was unclear what is $e$ at the beginning of page 2\n   - In the first paragraph of page 2, since the comment *this lower bound (on $\\rho$) is not necessarily tight* is for two cases (1) when the sum of the step sizes at one update step is smaller than $1/L$ and (2) when that is not the case, it remains very unclear if it is tight for the case (1), because that comment states *that does not meet the step size restriction*. In other words, this statement is problematic because two different cases are being compared while claiming that the bound for one case is not satisfied.\n    - The second paragraph on page 2 also assumes that the reader is familiar with the mentioned idea; otherwise, it is unclear why *this algorithm tackles cyclic behaviors*. Moreover, that is also the case for standard extragradient, so it is unclear what the point is here.\n- In Fig. 1, it would be helpful to annotate $L$ constant.\n- page 3: instead of the *objective function* $F$, it is better to use *vector field* or *operator*\n- page 3: our methods [...] is -> are\n- page 3: described next section, missing *in*\n- ...", "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": "", "extra_scores": {}}, {"review_id": "mUugfpvufJ", "reviewer": "Reviewer_mxmH", "summary": "The paper focuses on the weak MVI condition and proposes algorithms that allow the condition to be weaker than what was analyzed before. In particular, the main idea is that by using algorithms with multiple exploration steps, one can further relax prior used assumptions. In addition, the authors design an adaptive algorithm that explores until the optimal improvement is achieved. This process exploits information from the whole trajectory and effectively tackles cyclic behaviors.", "questions": "See Weaknesses section above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The paper is well-written, and the idea is easy to follow. The authors did a great job in the introduction of motivating the problem, explaining their approach, and clearly stating their main contributions.", "weaknesses": "However, I believe the paper has several issues regarding the presentation of the sections after the Introduction that make the reader's life more challenging.  The narrative around the statements of the theorems and the figures in the experiments section is not clear. In general i find that the main part of the paper has several holes and requires an effort from the reader to connect the dots.\n\nLet me provide some details below:\n\n### Some Basic Issues: \n\n1)  Figure 1 is included in the paper without reference to it at any part of the paper. What is its purpose? Can the authors elaborate more? The figure mentions \"range of gradient: while the definitions are related to operators. Does this hold only for the specific operator at the end of page 2 (saddle gradient operator)? Why is this figure helpful for the reader?  In several parts of the paper, the authors refer to the \"gradient\". If the results hold for general operators, it would be beneficial to be mentioned. \n\n2)  What is the $S^c$ in equation 2.6? \n\n3) Proof of Lemma 2.3 is missing (even if it is trivial the authors should include it for completeness).\n\n4) The presentation of Lemma 2.4, its importance, and the discussion after the results should be improved as this is a vital part of the understanding of the paper. I would suggest the authors include more information and explain the motivation behind it.  For example, what is the purpose of parameter $\\lambda_k$ here (why is not simply equal to 1)? Also, how does algorithm 2.9 satisfy the assumptions of Lemma 2.4? More explanation is needed.\n\n5) in section 3 the authors mentioned, \"The key is to calculate stepsize from projection and assure its positiveness.\" I get the statement but then how is that related to what they have as equation (3.1)? important connections are missing. Why is that projection? \n\n### More Serious Presentation Issues in the main part of the paper : \n\n6)  Sections 3.1 and 3.2 are focused on the algorithms and statements of the theorems. However, there is no explanation of what the results mean and how they are positioned in the literature. What are the benefits of the final statements? As a reader, I find it impossible to understand why for example, Theorem 3.2 is useful and what it means. The whole section 3 and in particular, pages 5 and 6 include several theorems one behind the other without a proper presentation and paragraphs explaining in more detail the main outcome. \n\n7) Section 4 is devoted to the Max Distance Extragradient where the extrapolation process will not stop until the projection distance stops increasing. This is interesting, but an intuitive understanding of what this means is missing from the main paper. The Discussion from Appendix B.1 and Figure 6 should have been part of the main paper. \n\n8) Important: An indication of the lack of proper presentation is the following. There is no clear explanation in the main paper of why by taking multiple extrapolation steps, one can have a weaker MVI. This is the main selling point of the work, but all the discussion of this is in the appendix. By simply reading the main paper, this is not clear.\n\n9) Unfortunately, the same pattern happening in the experiments section as well. The problems are presented, but an in-depth comparison of the results and paragraphs focusing on the output of the proposed methods and how they are compared to other algorithms is missing. How do the experiments correspond to the main theorems? A full page is devoted only to the plots (Figures 3-5) but without proper presentation and connection to the theoretical results.\n \n### On related work\n\n9) Finally, I believe the cited work of Choudhury et al. 2023 includes convergence of the deterministic optimistic methods for solving weak Minty inequalities with $\\rho>-1/2L$. It might be worth comparing with the Optimistic method as well in experiments and in the comparison of theory in the main paper.", "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": "", "extra_scores": {}}, {"review_id": "OEq3sH3owf", "reviewer": "Reviewer_xeFY", "summary": "This paper extends the AdaptiveEG+ proposed in [1] and studies the extragradient-type algorithms that take multiple intermediate steps for the unconstrained weak MVI problem, aiming to relax the weak MVI condition. Their analysis essentially relies on the condition that the iteration point and the solution point can be separated by the border hyperplane defined by the weak MVI condition w.r.t. the iteration point. In detail, for the iterate $z_k$, the authors defines the adaptive stepsize for computing $z_{k + 1}$ to be $\\lambda_k(\\rho \\|F(z_k)\\|^2 - \\langle F(z_k), z_k - \\bar z_k\\rangle)/\\|F(\\bar z_k)\\|^2$ with $\\lambda_k \\in (0, 2)$ and certain intermediate iterate $\\bar z_{k}$ (not necessarily obtained by one GD step), which requires $\\bar z_k$ to satisfy the condition that $\\rho \\|F(z_k)\\|^2 > \\langle F(z_k), z_k - \\bar z_k\\rangle$, assuming that the operator $F$ satisfies weak MVI condition with (negative) parameter $\\rho$. To guarantee this, the authors derives certain conditions on the stepsizes of intermediate step for multi-step extragradient, which leads to wider range on weak MVI condition parameter, roughly $\\rho > -\\frac{1 - 1/e}{L}$ (not tight), and improves upon the previously best known range $\\rho > -1/2L$. Their findings are further supported by preliminary numerical results. \n\n\n[1] Thomas Pethick, Panagiotis Patrinos, Olivier Fercoq, Volkan Cevhera, et al. Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems. In International Conference on Learning Representations, 2022.", "questions": "1. Could the authors further explain the derivation for the inequality in (3.1)?\n2. Besides the adaptive exploration proposed in Algorithm 1, I am curious for $n$-step EG whether it is expected to get better range on $\\rho$ with larger $n$, or it is sufficient to only take $n = 3$ with proper intermediate stepsizes for better range on $\\rho$? Based on the current (non-tight for $n \\geq 3$) analysis in the paper, one can get better range on $\\rho$ with 3 steps than taking $n$ steps with $n$ tends to infinity (in which case we get $\\rho > -(1 - 1/e)/L$).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors provides an intuitive generalization of AdaptiveEG+ from the perspective of weak MVI halfspaces. As long as one can find some intermediate iterate $\\bar z_k$ such that $\\rho \\|F(z_k)\\|^2 > \\langle F(z_k), z_k - \\bar z_k\\rangle$, the algorithm framework (2.9) are proved to converge with rate $O(1/k)$ for the average guarantee. An adaptive exploration scheme to find such $\\bar z_k$ is also given in Algorithm 1.\n2. This paper gives a quite comprehensive analysis and discussion on the stepsize requirements for intermediate steps with connection to the restriction on the parameter of the weak MVI condition, relaxing the previous contraints $\\rho > -1/2L$ to roughly $\\rho > -(1 - 1/e)/ L$.", "weaknesses": "I do appreciate the discussion and analysis for the more general multi-step extragradient. However, I note that the convergence rate remains the same (see Thm 2.5 in the paper) as AdaptiveEG+[1] in prior works, and the wider range of $\\rho$ only provides slight (constant) improvements. One may argue that although the rate is the same, MDEG and multi-step EG can solve for problems in more nonmonotonic regions. However, the numerical experiment as in Figure 4 shows that CurvatureEG+[1] can actually perform similarly as MDEG proposed in this paper. All of these limit the contribution of the paper.", "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": "", "extra_scores": {}}, {"review_id": "ZS9EZnaXfF", "reviewer": "Reviewer_ii6f", "summary": "The paper considers the weak Minty variational inequality for unconstrained problems and shows that the range for the problem constant $\\rho \\in (-1/(2L), \\infty)$ can be increase to $\\rho \\in (-(1-1/e)/L, \\infty)$ for an explicit scheme. They achieve this by modifying an extragradient method to compute the extrapolated point using _repeated_ applications of the forward operator. They first generalizing the hyperplane projection approached used in Pethick et al. 2022 to an abstract condition on the extrapolated point. They then show tight conditions on $\\rho$ when the extrapolated point is generated by two steps of GDA with time-invariant stepsize. To extending to $\\rho < -(1-1/e)/L$ they consider $n>2$ inner steps under the restriction that the sum of stepsizes $\\sum_i \\gamma_i < 1/L$. They finally propose a method which heuristically attempt to maximize the projection distance in order to relax the requirement on $\\rho$.", "questions": "- Eq. 3.6 (and consequently Thm 3.2) is tight for time invariant stepsize? Since this would be a stronger claim I would state it explicitly, and contrast it with e.g. Thm. 3.4.\n- Why define $z^0 = z^{init}$?\n- Is it possible to prove anything for Algorithm 1?\n- After Algorithm 1 it is suggested to use the stepsize choice of n-step EG, but how do you guarantee $\\sum_i \\gamma_i < 1/L$ in Algorithm 1 if the horizon is not known? (since the horizon is adaptively chosen by the max distance stopping criterion)", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper introduces a very nice idea and does so in an approachable way. It is interesting that an explicit scheme can extend the range of $\\rho$ and that this is achievable by such a simple and elegant approach. The work opens up exploration of other subroutines.", "weaknesses": "I definitely recommend accept. I only have one concern regarding Algorithm 1 and otherwise some suggestions for improving the content/writing.\n\n- It seems problematic that the max distance algorithm (Algorithm 1) has worse complexity when the operator $F$ has _more_ structure (e.g. when cocoercive such that the subroutine itself is sufficient for convergence). In other words, it seems that the scheme is trading off complexity in easier problem for a convergence in a larger class. What is the observed oracle complexity if you run the algorithm on a strongly monotone problem or cocoercive (for which the subroutine convergence) in comparison with e.g. EG+? (e.g. take $f(x,y)=x^2 - y^2 + xy$)\n\nSome suggestions:\n\n- I would state the minimal $n$ that achieves the $\\rho_0$ in Thm. 3.4. This way you can also specify the oracle complexity.\n- Lemma 2.4 is very related to [Solodov and Svaiter 1999](https://www.emis.de/journals/JCA/vol.6_no.1/j149.pdf) Lemma 2.1 which might be worth mentioning\n- Maybe make it explicit that the multiple steps for the extrapolation steps are not \"anchored\" to approximate a prox ala [Nemirovski 2004, page 3](https://www2.isye.gatech.edu/~nemirovs/SIOPT_042562-1.pdf)\n- Concerning $\\rho < -1/L$ threshold maybe mention [Bauschke et al. 2019, e.g. Table 1](https://arxiv.org/pdf/1902.09827.pdf) characterization for cohypomonotone problems.\n- Page 2 (first paragraph): It is stated that a better bound is derived in the 2-step case, but this seems not to be the case $\\rho > -(1-1/e)/L$ is looser than $\\rho > -0.5834/L$.\n- \"common practice is to choose $\\sigma_k$ near its lower bound\": There is a trade-off (lower bound yields weaker conditions on $\\rho$, but higher complexity, so only recommended if guaranteed convergence for the largest class possible is important)\n- The discussion after Thm. 3.4 is confusing to me:\n    - The lower bound could still be tight for time-invariant stepsize (as Thm. 3.4 is concerned with)\n    - The numerical evaluation only _suggests_ that improving the lower bound is possible if time varying stepsize is allowed. Stating that a counterexample proofs something in this setting can be misleading (especially in the context of the word \"lower bound\" being used in a slightly unconventional way).\n- Maybe use \"range of $\\rho$\" instead of lower bound where possible to avoid conflation with negative results (e.g. after Thm. 3.4)\n\nConcerning the writing:\n\n- A lot of whitespace\n    - To compress page 6 you could consider writing the inner loop of (n-step EG) with $\\forall i \\in [n]$ in one line.\n- Unspecified in places (e.g. section 2.1 should define $\\alpha_k$ and $\\gamma_k$, \"recommended parameter\" requires specification, etc)\n- Before section 2 (Preliminaries) the $\\rho > -1/L$ should only be a $\\rho > -1/(2L)$.\n- Assumption 2 is missing $z \\in \\mathbb R^d$\n- page 4 \"[...] does not necessarily have to be attained by a _single_ forward operator evaluation\"\n- $\\bar \\alpha_k$ is sometimes used for a pre-defined (nonadaptive) stepsize in the literature, but it is up to you what convention you stick to.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)