Efficient Interpolation between Extragradient and Proximal Methods for Weak MVIs
Authors: Thomas Pethick
Ioannis Mavrothalassitis
Volkan Cevher
Venue: ICLR 2025 Poster (2025)
Keywords: Weak Minty variational inequalities
cohypomonotone
nonmonotone
first-order methods
extragradient method
proximal point algorithm
Primary area: optimization
TL;DR: We show the best known complexity for nonmontone games satisfying the weak Minty variational inequality using an adaptive scheme

Abstract: We study nonmonotone games satisfying the weak Minty variational inequality (MVI) with parameter $\rho \in (-\tfrac{1}{L}, \infty)$, where $L$ is the Lipschitz constant of the gradient operator. An error corrected version of the inexact proximal point algorithm is proposed, with which we establish the first $\mathcal O(1/\epsilon)$ rate for the entire range $\rho \in (-\tfrac{1}{L}, \infty)$, thus removing a logarithmic factor compared with the complexity of existing methods. The scheme automatically selects the needed accuracy for the proximal computation, and can recover the relaxed extragradient method when $\rho > -\tfrac{1}{2L}$ and the relaxed proximal point algorithm (rPPA) when $\rho > -\tfrac{1}{L}$. Due to the error correction, the scheme inherits the strong properties of the _exact_ rPPA. Specifically, we show that linear convergence is automatically achieved under appropriate conditions. Tightness for the range of $\rho$ is established through a lower bound for rPPA. Central to the algorithmic construction is a halfspace projection, where the key insight is that the allowed error tolerance can both be used to correct for the proximal approximation and to enlarge the problem class.

Published as a conference paper at ICLR 2025
EFFICIENT INTERPOLATION BETWEEN EXTRAGRADI- ENT AND PROXIMAL METHODS FOR WEAK MVIS
Thomas Pethick*
Ioannis Mavrothalassitis'
Volkan Cevher*
ABSTRACT
We study nonmonotone games satisfying the weak Minty variational inequality (MVI) with parameter P E (-1/z, x)). where L is the Lipschitz constant of the gradient operator. An error corrected version of the inexact proximal point algo- rithm is proposed, with which establish the first (11/e) rate for the entire range p E (0), thus removing a logarithmic factor compared with the complex- ity of existing methods. The scheme automatically selects the needed accuracy for the proximal computation, and can recover the relaxed extragradient method when p > 1/22L and the relaxed proximal point algorithm (rPPA) when p > -1/z. Due to the error correction, the scheme inherits the strong properties of the exact rPPA. Specifically, we show that linear convergence is automatically achieved under ap- propriate conditions. Tightness for the range of p is established through a lower bound for rPPA. Central the algorithmic construction is halfspace projection, where the key insight is that the allowed error tolerance can both be used to correct for the proximal approximation and to enlarge the problem class.
INTRODUCTION
Nonconvex-nonecnnce minimax problem-and more generally nonmonotone games-an are ubiq- uitous in machine learning applications but notoriously difficult to solve (Daskalakis et al., 2021; Hirsch & Vavasis, 1987; Papadimitriou, 1994; Hsich et al., 2021). A nonmonotone class that has attracted significant attention the class of problems satisfying the weak Minty variational inequal- ity (MVI) introduced in Diakonikolas et al. (2021). One reason for the increased interest is that the counterexamples constructed to demonstrate the failure of classical methods in Hsieh al. (2021) were shown to satisfy the weak MVI (Pethick et al., 2022).
The weak MVI is dictated by a parameter p, which determines the degree of allowed nonmonotonic- ity. A flurry of work has followed since Diakonikolas et al. (2021) focusing on extending the range of p (Pethick et al., 2022; Lee & Kim. 2024; Fan al., 2023; Alacaoglu et al., 2024; Pethick al., 2024). At the heart of all these methods is relaxed update rule. Interestingly. the relaxed extra- gradient method achieves (tight) & E (-1/2r, oo) (Pethick et al., 2022; 2024) while the relaxed proximal point algorithm (rPPA) permits the larger range of p E (-1/1, oo) (Alacaoglu et al., 2024; Pethick et al., 2024). In other words, moving beyond p > -1/22 seems to require an increasingly refined approximation of the proximal operator made precise by the logarithmic factor suffered in the complexity (Alacaoglu et al., 2024). This is in stark contrast with monotone problems where the extragradient method (Korpelevich, 1977) can approximate the proximal point algorithm without any tradcoff (Solodov Svaiter, 1999b; Mokhtari et al., 2020).
The paper addresses the following fundamental question:
Can we treat the weak MVI range p E (-1/L, -1/21] without suffering logarithmiccaactonn (*)
Very recently Fan et al. (2023) interestingly managed to show convergence for p - R3 0.632 in unconstrained problems without a logarithmic factor in the complexity. However, it is unclear if the approach can be generalized to the larger range of p and constrained settings.
"I Laboratory for Information and Inference Systems (L.ONSS) EPFL. (thomas.prthickk@epl...

---

Published as a conference paper at ICLR 2025
Table I: Comparison with existing literature. Algorithm 1 is the first method to treat weak MVT
with -1/4 without suffering a logarithmic factor in the complexity.
Method
Minimum
Complexity
Constraints
Linear convergence"
Diakonikolas et al. (2021)
OC)
81.
Pethick et al. (2022)
(
27.
Böhm (2022)
0
X
Fan al. (2023)
1-1/
(
X
Alacaoglu al. (2024)
O (n
This paper
(())
Number of operator evaluations for making squared tangent residual smaller than E,
Linear convergence is established under an enror bound condition (ef. Section 7).
We answer (+) in the affirmative. Our analysis generalizes the halfspace projection approaches in both Pethick et al. (2022) and Solodov & Svaiter (1999a). The key observation is that the allowed error tolerance in the halfspace projection can both used to expand the problem class and to cor- rect for the inexactness of the proximal operator estimation. Our construction provides intuitive geometric explanation for convergence results in weak MVIs.
Concretely we make the following contributions:
(i) Improved complexity We propose a hybrid proximal extragradient method (Algorithm 1) to achieve convergence for p >> -1/,, which automatically selects the required approxima- tion quality for the proximal operator through a computationally negligible error condition. The stopping criterion combined with the error correction step in Algorithm removes the logarithmic factor in the complexity, while generalizing to constrained and regularized settings. The tightness of the range of p is made precise through lower bound for the idealized case of exuct proximal computations.
(ii) Unification The error condition for the inner loop in Algorithm can pass immediately if p -1/2L, in which case the scheme exactly reduces to the AdaptiveEG+ method of Pethick et al. (2022). Algorithm is an instantiation of the implicit scheme (8) which recover the hybrid method of Solodov & Svaiter (1999a) and the celebrated forward- backward-forward algorithm (Tseng, 2000) when the problem is monotone (i.e. p 0).
The scheme thus unifies the analysis of the relaxed extragradient method, the relaxed proxi- mal point algorithm (rPPA) and classical methods for monotone problems, while providing a precise explanation for why the relaxed extragradient method only applies p 1/22..
(iii) Linear convergence Algorithm adopts strong properties of the exact rPPA due to етror correction. Specifically Algorithm automatically obtains linear convergence under appropriate conditions by exploiting the Fejér monotonicity the iterates. Additionally, Fejér monotonicity simplifies the proofs in general by saving us from meticulously arguing about boundedness of the iterates otherwise necessary in c.g. Alacaoglu et al. (2024); Pethick et al. (2024). The simplicity is apparent as the proof for the general case fits
half a page, even the adaptive case (cf. Appendix C) and lines in the nonadaptive case (cf. Theorem 5.5).
RELATED WORK
Variational inequalities (VIs) provide a unifying framework for studying optimization, equilibrium, and fixed point problems (Facchinei & Pang, 2003). Classical work has focused monotone VIs, where the operator satisfies a global monotonicity condition. For such problems, a wide range of ef- ficient algorithms have been developed, including the (inexact) proximal point method (Rockafellar, 1976), the extragradient method (Korpelevich, 1977), and the forward-backward -arrwrfd method (Tseng, 2000).
Recent works have begun to study nonmonotone VIs motivated by nomconvex-nomconncae minimax optimization. Diakonikolas al. (2021) introduced the weak Minty variational inequality (MVT)
2

---

Published as a conference paper at ICLR 2025
and showed convergence of the relaxed extragradient method for p -1/E.. Subsequent works have focused on pushing the allowable range of p using various algorithmic techniques. Pethick et al. (2022) extended the definition to constrained problems and proposed algorithm with convergence for the range p > -1/2... Fan et al. (2023) proposed an extension using multiple forward operator evaluation, H = id FyF, per iteration, extending the range p > -1-1/e/1. for unconstrained problems. Lee & Kim (2024) also extended the range of using a hyperplane projection, but at the cost of logarithmic factor in the complexity. turns that relaxed (inexact) proximal point methods (Pethick et al., 2024; Alacaoglu et al., 2024) can achieve the relaxed range p -1LL as first shown in Alacaoglu al. (2024). The same range can be obtained by applying the inexact proximal point method in e.g. Chen & Luo (2022) to the modified operator defined in Lee Kim (2021, App. A.1). Adaptive approaches has also been taken an attempt to increase the range of even further (Pethick et al., 2022; Böhm, 2022; Alacaoglu et al., 2023).
Whereas the previous schemes can be seen as instances of the Krasnosel skif-Mamm (KM) iteration from the fixed point literature (Pethick et al., 2024), there exists another line of work focusing on the Halpern iteration in the special case of cohypomonotone problems. In contrast with the KM iter- ation, Halpem iteration linearly interpolates with the initial point using time-varyine stepsize, i.e.
2h+ = (1 >₂)²²' Ag This construction has been used to show optimal O(1/k²) convergence rates for the squared fixed point residual. Sabach & Shtern (2017); Lieder (2021) originally showed convergence for nonexpansive operators, which implies convergence for p-comonotone problems with p > -1/2L using the (exact) proximal operator. By directly approximating the proximal operator, an explicit scheme was later proposed for monotone problems in Diakonikolas (2020), suffering a logarithmic factor in the rate. The logarithmic factor was removed for unconstrained problems by means of an extragradient variant in Yoon & Ryu (2021), which was later extended to p-cohypomonotone problems with p > -1/2L. in Lee & Kim (2021) and subsequently the con- strained case in Cai et al. (2022a) while only requiring a single projection. Recently, Alacaoglu et al. (2024) showed convergence for the range > 1/t1. using the inexact Halpern iteration by exploiting the weaker structure of nonic-nonexpamiivenes (Bauschke et al., 2021; Bartz et al., 2022).
PRELIMINARIES
We will formulate our problem as a (possibly nonmonotone) inclusion problem in which we seek to find z E Rdd such that
0 Sz Fz Az.
(1)
More compactly, we will write = E zer S. We will use the single-valued operator ; R2 + Rd
capture the smooth part of the problem and A _dd = Rd to capture (projectable) constraints as made precise in the following assumptions (cf. Appendix A for missing definitions).
Assumption 3.1. In problem (1),
(i) The operator F: Rd + Rdd is L-Lipschitz, i.e. for some L E 0o),
|F - Fz'll S L||= - z'1l Vz, Rd.
(ii) The operator A : Rdd = Rd is maximally monotone.
(iii) The operator S = F + A satisfies the weak Minty variational inequality (MVI), i.e. there
exists a nonempty solution set z S zer such that for all 2* E Z and some p e (- (0)
(u, 2 x²) 2 e|l111 V(2,0) E gghh
(3)
One prominent problem class that can be cast as the inclusion (1) is m-player games.
Example 3.2 (m-player games). Denote the decision variables := (2;;==) := (21, ....... 2m) Rd
with d = ""= d2 and let the loss incurred by the thh player be C,(2; 2-12)_1) = (p((2) + g((2,)
where P; is the payoff function and gi typically enforce constraints 2, A Nash equilibrium is any decision 2 E TR. which is unilaterally stable, ie.,
(a(=)==1)) S L((2632a) Wz E dRd: and i [m] (1....,m}
3

---

Published as a conference paper at ICLR 2025
D(**)
1
20)
11
P(z*) = (()) (z+)
Z
The scheme (8) proceeds by iteratively projecting onto the constructed halfspace D(=*), ), which is guaranteed to contain the solution set 2 C wer S. It turns that only relative error condition when computing ø* is sufficient to ensure that the sequence do not terminate prematurely.
Figure I:
The corresponding first order optimality conditions may be written the inclusion (1) with Fz (V., (i()...).... V V=n 9m (2)) and Az = (0g1(21). 00.........mm.m. The operator A will only be accessed through the resolvent
J=)(2) == (id (z) (prox.g1 (21)..... prox.ggm (2m))
with y > O. Maximal monotonicity of A is satisfied when gi is proper Ise convex all E [m]]
ALGORITHMIC CONSTRUCTION
Our starting point is the (inexact) proximal update on S + A, which given a a E Rd seeks:
(id (2-
= z ( and E 7
(5)
with inexactness Rd The above update can be applied iteratively, *+1 (id SS (2* -*) when the resolvent is singled-valuee as classically considered (Rockafellar, 1976), but establishing convergence would require the errors to be absolutely summable, i.e. Σ || oo, which translates into an increasing number of inner iterations used to approximate the proximal operator.
Instead will introduce halfspace projection to correct for the inexactness in the proximal evalu- ation, which we will refer to interchangeably as the error correction step. The construction is largely inspired by Solodov & Svaiter (1999a), which introduced the idea for monotone problems to relax the standard absolute summable еттоr criterion to only requiring what was coined as relative inex- actness. what follows, we will importantly construct a halfspace that can be used for the more general class of weak MVI.
Observe that, regardless of the inexactness, the proximal update (5) can be used to construct halfspace that contains the solution set in Assumption 3. 1iii)
D(2) = { w: (w. w:) 2 1
(6)
where 5 S p. The containment of the solution set is easily verified by taking w 2 If we can iteratively project onto this (changing) halfspace, then convergence immediately follows, provided that we can argue that there is fixed point other than the projection operator P. As we will see, it is fairly easy to derive the closed form solution to this halfspace projection, which effectively results using an extragradient computation 782;
S. For later convenience define
Φ D(z) z E D(z)
with (0.2- 2)+ 1011
P(z) :- (z) arg min ||u -=1|== wED(=)
A convergent sequence can readily be constructed by repeatedly applying the projection, ie. A++1 P.=*). This iterative scheme is known the Picard iterations in the fixed point itera- tion literature, and it converges for firmly nonexia--onexpaasivve operators- property which holds for the projection operator P as formally established in Proposition 5.1.
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 An explicit hybrid proximal extragradient method
Require: 2º E R A E 2), E [0,1+ + ;),, - P. (1-pl+,
Repeat for k 0, 0,..... until convergence
1:
+ 2t
2: repeat
3:
h
+- 2 - FF
4:
g6 (id -oyy)-lha
5: until (2 - zt, +t) 2 (1 o |5+|| where oh = 11th = +7F=*
6:
2k+1 z² o with or 1
(""
=n)
Return 2*+1
In order to later relate our adaptive scheme to existing fixed variants in the literature, it will prove useful to introduce an (over)relaxation parameter Å E (0, 2). The resulting scheme is known as the Krasnosel'skii. Mann (KM) iteration, which recovers the Picard iteration for X =
= -x)==*
Au. P(=*)
(KM)
with A It is worth highlighting that our use of the above relaxation different from the one used in Alacaoglu et al. (2024); Pethick et al. (2024). They apply the KM iteration directly to the (inexact) proximal operator, and rely on the (under)relaxation to establish convergence for weak MVIs with > I. We instead apply it to the halfspace projection operator P and only use the generalization to expand the algorithmic class. particular, we will still be able to show convergence for
+ even when A E 21)
By expanding the operator P in KM and including the sufficient error condition (12) from Proposi- tion 5.1 we obtain the following algorithm with y O, d E (0, 2), 8 and [0, 1 + G):
find
2 E Rdd and T E yS
s.t. = - -8* + and
(e tt S <ol
(8)
update =1 AROUo as
(0
# +
Remark 4.1. The scheme generalizes both Pethick et al. (2022, Alg. and the construction in
Solodov & Svaiter (1999a). To recover Pethick et al. (2022, Alg. 1) take ex 7(2x F2*)
for which the error condition can automatically pass for p > -7/2 (see Section 6). To recover Solodov & Svaiter (1999a), which applies to the monotone case (p = 0), we first choose 5 = 0. Furthermore, from the Cauchy-Schwarz inequality and the update rule we recover the more stringent error condition ||=*|| I max([]=*|) ||2* x from Solodov & Svaiter (1999a). For e* = 0 we obtain the relaxed proximal point algorithm (Eckstein & Bertsekas, 1992) with the relaxation parameter & = >yak A1 2). See Appendix B for an overview of the special cases.
Comparison Alacaoglu et al. (2024); Pethick al. (2024) also considers an inexact relaxed prox- imal point update. For any other choice than c = O, the algorithm (8) differs from the approach in Alacaoglu et al. (2024); Pethick al. (2024) by not using z² directly in the update of * but rather importantly the extragradient evaluation &² E yS== This will turn out to be crucial to estab- lishing Fejér monotonicity and thus avoiding the logarithmic factor in the complexity. Specifically, the update in Alacaoglu et al. (2024); Pethick et al. (2024) is the relaxed inexact proximal point algorithm
* = (id S7/5)
*+1 (1 - >x)=* * + Z
where Ag E (0,1). 1). In contrast, our proposed (8) uses an extragradient evaluation at z follows:
z ~ (id -
(10)
= k+l k+ =
x*) + Ax - o*)
where the extragradient evaluation &² E SS² is defined through (8). We further discuss the differ- ence with existing schemes in Section 6.3.
5

---

Published as a conference paper at ICLR 2025
Explicit scheme To derive an explicit scheme will define inner iteration approximating the resolvent (id +yS) Recall == A Given 2 E F we seek E IR such that
x (id+ = (id +- yFx)
Following Nemirovski (2004); Pethick et (2024) this can be approximated with fixed point iteration of
C2 : + (id +y (z-
(11)
which is a contraction for small enough y since F is Lipschitz continuous. follows from Banach's fixed-point point theorem Banach (1922) that the sequence converges linearly. Approximating s in (8)
with an inner iteration (11) leads Algorithm
ANALYSIS OF THE IMPLICIT SCHEME (8)
This section establishes convergence of the implicit scheme (8). The key to showing convergence is to guarantee that we always make progress towards zero of S when applying the halfspace
projection operator P (7). Specifically we will argue that the numerator (6, - =) 0 1 in the (adaptive) stepsize a remains positive even with the inaccuracy e (such that P C 2", which prevents the sequence from terminating prematurely). We now show crucial properties of this operator.
Proposition 5.1 (Properties of (7)). Suppose Assumption ((ii) holds, S p. and (5) satisfies the following error condition,
(e,, S <0100/2
(12)
where a E [0, 1 +1++0 3). Then,
(i) The projection operator P : IRd + [d (7) is firmly quasi-nonexpansive.
(ii) 2' C zer S.
(iii) The closed form solution to P is given as in (7) and the stepsize satisfies a 2 21+ 1
Remark 5.2. Notice how the approximation quality in (12) needs to be better (while still only rel- ative) for increasingly negative p through the requirement o < 1 11+ Trivially, when
0 we get the loose requirement of p > - - - where the last inequality follows from the requirement < 1/2 for the proximal operator to be single-valued (see Lemma C.2 and Remark 5.4).
Convergence of (8) follows from convergence of the KMM iteration (see Theorem C.I) applied to the firmly nonxpanone operator P and the fact that fix P S zerS. The following theorem is direct consequence of the previous Proposition 5.1 and Theorem C.1. The theorem establishes convergence rate for what referred to as the tangent residual (Cai et al., 2022b;a; Bot al., 2023).
Theorem 5.3. Suppose Assumption (iii) holds. Consider the sequence (2*) generated by (8) with As E (0, lim inf (2 Xx) O, S p. and a [0,1 4). Then, for all 2
||:0 2²
min kE(O.....K K
Ky 2 (1
K
Furthermore, if 2 zer then (z*) converges to some x" E Z"
Remark 5.4. It is important to ensure that the (inexact) proximal update is well-defined. The exact case holds under maximal monotonicity of the operator A and Lipschitz continuity of the operator F when 7 < f. (see Lemma C.2). We have assumed maximal monotonicity of A for simplicity. However, note that it trivially possible relax the condition on cohypomonotonicity when A is also cohypomonotonicity (with > -7) since well-definedness of Jy.s is preserved
S = F (Bauschke et al., 2021, Cor. 2.1 The inexact case will be treated for the particular choice of inexactness, since will importantly be able to relax the stepsize requirement 7 +
Convergence for variant of (8) with nonadaptive relaxation parameter λạ ā follows im- mediately, since the adaptive stepsize can be absorbed into 2g E (0, 2) as remarked in Section 6.3. However, include direct proof as it turns out to be particularly compact.

---

Published as a conference paper at ICLR 2025
Theorem 5.5. Suppose Assumption 3.1(iit) holds. Consider the sequence (2 keE generated by (8)
with the nonadaptive stepsize Xy. = E (0, 2(1 - o + 9)). Then, for all x² 2
1: 2 1=
min kE (U......KI
dist(0, S 27² - ā K)
Proof. We proceed by expanding the update for rule in (8) and establishing Fejér monotonicity:
|| 2²1 = || x + 1 (ā. 2² - -2")
|| 2 (ā 2t -2") -ā -2")
|| 2= - 1| - -2)0"" , 2²)
(Assumption 3.)( & || - 2" -2-- + 1)1l0= 20(
(error condition) 2 || 2" 26 -a- 9)
(13)
Rearranging, summing and telescoping completes the proof.
A few remarks are in place. First notice that there is almost no looseness in the proof we only apply an inequality once, which is the weak MVI that we work under-the error condition does not add any looseness we can control its tightness. Secondly, from (13), the interplay between the relaxation parameter o, the error tolorance a and the nonmonotonicity constant p becomes very apparent. Specifically, the parameter ā needs be taken smaller with increasingly negative p and large error tolerance Note that Theorem 5.5 also implies convergence of the explicit Algorithm when we force ag a.
ANALYSIS OF THE EXPLICIT SCHEME (ALGORITHM 1)
Al Algorithm is an instance of (8) with particular iterative approximation of = Thus, in order to obtain convergence suffice to show that the error condition will eventually pass. Due to Pethick et al. (2024, Lem. 5.1), which analyses the same inner iteration as Algorithm 1, the error ||=*]| can be made arbitrarily small, which would be sufficient for ensuring the error condition.
In this section we will show a stronger result by characterizing the number of inner iterations in Algorithm sufficient for convergence of a given p. and crucially show that the number inner iterations can be (1) instead of only O(In )) As warmup first show that a single inner iterations suffice when p 1. thus exactly recovering the result of Pethick al. (2022).
6.1 SINGLE-STEP APPROXIMATION
We will show that a single-step approximation of the resolvent suffice under the more stringent requirement p -
27 To obtain the direct extragradient type scheme in Pethick et al. (2022, Alg. 1) take the error in (8) to * = FFF=* - Fz*) such that the update rule defining the extrapolated point z can be explicitly computed with one forward-backward step
Jh H *
z (id +xd++ -
(14)
where H = id F is the forward operator and well-definedness of the resolvent follows from maximally monotonicity A. In turn the error condition in (8) reduces
-7 (Fz* Fz H²* H < a H HE*
We want to understand for what this condition is met. From 1 4-cocoercivity of H (Lemma A.4()) have the following when the operator F RRd Rd is Lipschitz continuous and 1
| 1 s (H=** H * - z²) {
H F=* P + H H
Consequently, the error condition holds with a E [ 1 + () in which case > 2/2 is sufficient for convergence.
Notice that the update (14) correspond to having one inner step of Algorithm 1. Thus, by the same
argument the error condition in Algorithm will immediately pass if o [2 1+ ?) and Algorithm exactly reduces Pethick et al. (2022, Alg. 1). The statement is made precise in Theorem 6.1
7

---

Published as a conference paper at ICLR 2025
6.2 MULTIPLE INNER STEPS
The key to extending the nonmonotonicity parameter p is observing that we can push the lower bound on the relative inexactness parameter (0,1+ 1 G), for which the error condition is guaran- teed to pass, closer zero by increasing the number of inner iterations. Consequently, the condition on becomes weaker. The following theorem makes this precise, where the main technical diffi- culty comes from having to establish lower bound on || I12 appearing the error condition. The convergence rate in the theorem is a direct consequence of Theorem 5.3.
Theorem 6.1. Suppose Assumption 3./ holds. Consider the sequence (2 (E") generated by Algo- rithm I and let == lim infx (2 2x) 0. Then, for all z" E 2
1 =1 KY (1+ -
min dist(0, dist(0,Sz*) kE K-1
Furthermore, if 2 zer S then REE comverges some 2" Z*. Moreover, let n denote the number of inner iterations in Algorithm Then,
(i) the error condition passes immediately (i.e. n even when only y i 12:1 which is feasible for > -
(ii) the error condition passes after at most n iterations for some 7y < 1/r 2-Infn)/n E 4+11-m(n)/n: 1 ()) which is feasible for - 11(11 In(n)
n-1
a+1 In(a)/n
Remark 6.2. For simplicity of exposition we assume maximally monotonicity of A Red = Rd. but the assumption can be relaxed to pa-comonotonicity with Pa > -7/2 without modifying the argument, since the resolvent A remains nonexpansive (Bauschke et al., 2021, Prop. 3.13(
We can immediately infer complexity bounds from Theorem 6.1 without logarithmic factor, due to the fact that the number of inner steps n is ((1). The characterization interestingly uncovers an additional dependency on p in the complexity in the interval p E (-1 2 which we conjecture is unavoidable considering the tightness of our construction.
Corollary 6.3. Suppose Assumption 3. holds. Consider the sequence (2 (EEN generated by Algo- rithm 1 and let K ;= lim inf A²(2 A&) > 0. Then, for all zt E Z* the sequence achieves (o..,, dist(0, S I after at most
(1 + n)]12 =12
# (oracle calls) <
27 -2E
to both the operator F and the resolvent (id+>A) where n bound on the number of inner iterations.
is an upper [ ItpL In (+pp.)
6
Remark 6.4. Corollary 6.3 removes the logarithmic factor in e that otherwise appears for approaches approximating the proximal operator (Pethick et al., 2024; Alacaoglu et al., 2024; Lee & Kim, 2024). Not only does Algorithm 1 improve the complexity from O In !) to ( for > -(1 a)y, but the method removes the need for hardcoding potentially pessimistic choice of the number of inner steps and the stepsize og by instead chosen them based on the local structure of each iteration.
6.3 NONADAPTIVE VARIANT
Although the adaptive stepsize or and error condition of Algorithm comes at essentially no addi- tional computational cost, it will prove instructive derive a scheme with fixed number of inner iterations and a nonadaptive stepsize. Specifically, the variant will illuminate differences and simi- larities with the relaxed approximate proximal point method (RAPP) of Pethick et al. (2024) which can similarly converge for p > -1/L. The method is defined by the following recursion
* = (id +> (2 FFZ/)
= n with
(RAPP)
.+1 = (1 x* 2
with dg E (0, In contrast, Algorithm reduces to the following when the error condition is assumed pass after iterations:
8

---

Published as a conference paper at ICLR 2025
Vi O,... with 20 *++ (id + +7 7
*
(15)
*+1 (1 xz)) * + ā 7 F -F=
where guarantee that org X E (0. 2(1 (1 o + p/T, oo) (from Proposition 5,1 by picking ó = p) can be absorbed into the relaxation parameter AR- (0,2). Consequently, the convergence guarantee of Theorem 6.1 carries over to (15).
p/>)) since the adaptive stepsize or
becomes apparent that for the fixed variant the only difference with RAPP is the additional term (( - F..) This difference is a consequence of using the extragradient evaluation 전 yS2* in (8) (and consequently Algorithm 1) instead of directly the iterate z used in RAPP, which is crucial for establishing Fejér monotonicity. Fejér monotonicity is central to avoiding the logarithmic factor in the complexity by circumventing requiring Ei= || oc.
For n = the fixed variant (15) exactly reduces to CEG+ of Pethick et al. (2022) from which the celebrated forward-backwant www.-aad-wwwwrrreeeeeewee forward (FBF) method of Tseng (2000) be recovered (Pethick et al., 2022, Rem. 3.3). This perspective provides a new interpretation of the FBF algorithm as a one-step application of the (contraction) map used to approximate the proximal operator in (8), akin to the original motivation for the MirrorProx algorithm in Nemirovski (2004). The connection is precise in the sense that we obtain convergence proof of FBF instance of Algorithm I (cf. Theorem 6.1).
LINEAR CONVERGENCE
Because of the enror correction Algorithm adopts the strong properties of the exact (relaxed) prox- imal point algorithm (rPPA), even when inexactness is present. Specifically, Fejér monotonicity holds, which we will use show that linear convergence is automatically obtained under appropri- ate structure. In contrast, Halpern based methods do not automatically adapt due to the anchoring mechanism and depends on stepsize modifications in order obtain linear convergence (Park & Ryu, 2022).
We will specifically work under the following assumption. Assumption 7.1 (Error bound), The operator F + satisfies for some 7 > that ||a|| 2 dist(z, zer S) V(z, v) E gph S.
(16)
Remark 7.2. The error bound captures two otherwise seemingly distinct problem classes:
(i) Strongly monotone problems for which is the strong monotonicity modulus.
iii) Affine operators for which is the minimum non-zero singular value of the linear operator. Nonmonontone affine operators are allowed under the weak MVI (cf. Bauschke et al. (2021, Sec. 5)).
The following theorem establishes linear convergence of Algorithm through the more general implicit scheme (8).
Theorem 7.3. Suppose Assumptions (ii() and 7.1 hold. Consider the sequence (EE) generated by (8) with À E (0. 2), p. [0,1 1 4)) Then, for all x² Z*
dist? zer 5) S (1 - <)x dist?(22) zer S)
with < X(2 -) 1--++///
(1) 1-
Remark 7.4. As a by-product, Theorem 7.3 establishes linear convergence for EG+ (Diakonikolas et al., 2021), AdaptiveEG+/CEG+ (Pethick et al., 2022) (when p > -2/2) and rPPA (Eckstein & Bertsekas, 1992) (when -7). For the reductions see Remark 4.1 and Section 6.1.
TIGHTNESS
In this section establish that the derived range of the weak MVI parameter p o0) in Theorems 5.3 and 6.1 is tight for the relaxed proximal point algorithm (rPPA)
A+1 -ax)²* (nd -
(rPPA)

---

Published as a conference paper at ICLR 2025
10
1.0
10a
10
0.8
10:5
0.7
RAPP 100)
10-12
RAPP 200)
0.6
10-16 16
RAPP (n- 300)
0.5
Algorithm
10-20
10"
10
10a
10
10
2
12
14
Itraaioon &
Inner steps
Figure 2: (left) For p -098/ even n. 200 inner iteration sufficient for RAPP to converge. while Algorithm converges rapidly with only 15 (adaptively picked). (right) Algorithm can achieve arbitrarily high accuracy for given p < -y using fixed number inner steps n.
where Ken is a predefined stepsize sequence. Note that rPPA can be seen as a special case of our implicit scheme (8) in the idealized case of exact access the proximal operator (i.e. e 0).
Theorem 8.1. Consider sequence (=*) keE generated according rPPA with 7 and for all N. Let S -(1 3% yy. Then, there exists an operator S R - R for any d > satisfying Assumption 3.1(ii)) which the sequence will not converge.
Remark 8.2. Theorem 8.1 prevents convergence in general when the weak MVI parameter p - -7, when the relaxation parameter ãą - 0. The lower bound Z -2/2 for the (unrelaxed) proximal point algorithm (Gorbunov et al., 2022, Thm. 3.3) is recovered by taking ag = 1.
In Appendix G we exploit that the range of is dictated by the stepsize y, by analysing Gauss- Seidel type update rule which permits stepsizes that are possibly larger than 1/r.
NUMERICAL EVALUATION
We test Algorithm and RAPP on Pethick et al. (2022, Ex. 5) which can be parameterized by and (see Example F.1). We 7 0.99/L for both methods and ãū 0.001 for RAPP and compared
0.98/s. Algorithm is additionally run multiple problem instances of varying p to determined the relationship with the (automatically selected) number of inner steps. The results shown in Figure 2, where Algorithm 1 is observed to converge using substantially fewer inner iterations than baseline.
10 CONCLUSION
We have introduced hybrid proximal extragradient method that interpolates between relaxed ex- tragradient method and the relaxed proximal point method. The algorithm achieves the first O(1) oracle complexity for the loose requirement mie factor. The algorithm mitigates the need for hyperparameter selection by both automatically determining the stepsize aş and the number of inner iterations n, while automatically enjoying lin- ear convergence under an error bound condition. The construction is obtained through an intuitive geometric interpretation that leads tight and simple analysis.
-1/r. in weak MVIs, thus removing the logarith-
In the special case of cohypomonotone problems our derived rates can be accelerated for > >>1/22. It is interesting to investigate integrating the halfspace projection method with Halpern iteration, which could permit an optimal method in the regime E (-1/L, -1/2z] without suffering a loga- rithmic factor in the complexity.
10

---

Published as a conference paper at ICLR 2025
11 ACKNOWLEDGEMENTS
This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 205011. This work was supported by Hasler Foundation Program: Hasler Responsible AI (project number 21043). Research was sponsored by the Army Research Office and was accom- plished under Grant Number 19--
REFERENCES
Ahmet Alacaoglu, Axel Böhm, and Yura Malitsky. Beyond the golden ratio for variational inequality algorithms. Journal Machine Learning Research, 24(172):1-33, 2023.
Ahmet Alacaoglu, Donghwan Kim, and Stephen Wright. Extending the reach of first- order algorithms for nonconvex min-max problems with cohypomonotonicity. arXiv preprint arXiv:2402.05077, 2024.
Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fund. math, 3(1):133-181 1922.
Sedi Bartz, Minh N Dao, and Hung M Phan. Conical averagedness and convergence analysis of fixed point algorithms. Journal of Global Optimization, 82(2):351-373, 2022.
Heinz H. Bauschke and Patrick L. Combettes. Corvex analysis and monotone operator theory in Hilbert spaces. CMS Books in Mathematics. Springer, 2017. ISBN 978---.19-48310-8
Heinz H Bauschke, Walaa M Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Mathematical Programming, 189(1):55-74, 2021.
Axel Böhm. Solving wwoncoonvex-nnncoome min-max problems exhibiting weak minty solutions. arXiv preprint arXiv:2201.12247, 2022.
Radu loan Bot, Dang-Khoa Nguyen, and Chunxiang Zong. Fast forward-backward splitting for monotone inclusions with convergence rate of the tangent residual of (1/k). arXiv preprint arXiv:231..1217.. 2023.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated algorithms for monotone inclusions and constrained nonconvex-nonconeavy min-max optimization. arXiv preprint DiXiv:2206.052488 2022a.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Tight last-iterate convergence of the extragra- dient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities. arXiv preprint arXiv:2204.0022 09228, 2022b.
Lesi Chen and Luo Luo. Near-optimal algorithms for making the gradient small in stochastic mini- max optimization. arXiv preprint arXiv:2208.0 05925, 2022.
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. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. In Conference on Learning Theory, pp. 1428-1451.
PMLR. 2020.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for struc- tured nonconvex-noncoocaaee min-max optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2746-2754. PMLR, 2021.
Jonathan Eckstein and Dimitri P Bertsekas. On the Douglas Douglas-Rachfordd splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming. 55(1): 293-318, 1992.
11

---

Published as a conference paper at ICLR 2025
Francisco Facchinei and long-Shi Pang. mentarity problems. Springer, 2003.
Finite-dimensional variational inequalities and comple-
Yifeng Fan, Yongqiang Li, and Bo Chen. Weaker mvi condition: Extragradient methods with multi- step exploration. The Twelfth International Conference on Learning Representations, 2023.
Eduard Gorbunov, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. Convergence of proximal point and xtragradienttbasee methods beyond monotonicity: the case of negative comonotonic- ity. arXiv preprint arXiv:2210. 13831, 2022.
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.
Ya-Ping Hsich, Panayotis Mertikopoulos, and Volkan Cevher. The limits of max optimization algorithms: Convergence to spurious non-critical sets. In International Conference on Machine Learning, pp. 4337 4348. PMLR, 2021.
GM Korpelevich. Extragradient method for finding saddle points and other problems. Matekon, 13 (4):35-49, 1977.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. Advances in Neural Information Processing Systems, 34:22588- 22600, 2021.
Sucheol Lee and Donghwan Kim. Semi-anchored gradient methods for monconvex-mnnnconcaee minimax problems, 2024. URL https::t//// http://pppneeeeeeeeeeeeotormmmma
Felix Lieder. On the convergence rate of the halper-iteration. Optimization letters, 15(2):405-413 2021.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pp. 1497-1507. PMLR, 2020.
Arkadi Nemirovski. Prox-method with rate of convergence (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-225 2512292221122 2004.
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.
Jisun Park and Ernest K Ryu. Exact optimal accelerated complexity for fixed-point iterations. In International Conference on Machine Learning, pp. 17420-17457 PMLR, 2022.
Thomas Pethick, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq, and Volkan Cevher. Escaping limit cycles: Global convergence for constrained noncomvex-noncooeee minimax problems. In International Conference on Learning Representations, 2022.
Thomas Pethick, Olivier Fercoq, Puya Latafat, Panagiotis Patrinos, and Volkan Cevher. Solving stochastic weak Minty variational inequalities without increasing batch size. In The Eleventh International Conference on Learning Representations, 2023a.
Thomas Pethick, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq, and Volkan Cevher. Escap- ing limit cycles: Global convergence for constrained nonconvex-nome nonconcave minimax problems. arXiv preprint arXiv:2302.0983 2023b.
Thomas Pethick, Wanyun Xie, and Volkan Cevher. Stable nonconvex-nomconccav training via linear interpolation. Advances in Neural Information Processing Systems, 36, 2024.
R Tyyrelll Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5).877-898, 1976.
Shoham Sabach and Shimrit Shtemn. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640 660, 2017.
12

---

Published as a conference paper at ICLR 2025
Mikhail V Solodov and Benar F Svaiter. A hybrid projection-proxteeee point algorithm. Journal of convex analysis, 6(1):59-70, 1999a.
Mikhail V Solodov and Benar F Svaiter. A hybrid approximate extragradient-proxina point algo- rithm using the enlargement of a maximal monotone operator. Set-Valued Analysis, 7(4):323-345, 1999b.
P. Tseng. A modified heward-backwant splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431-444 2000.
TaeHo Yoon and Ernest K Ryu. Accelerated algorithms for smooth convex mavex-cooncve minimax prob- lems with (1/K3 2) rate squared gradient norm. In International Conference Machine Learning, pp. 12098-12111 12109. PMLR, 2021.
13

---

Published as a conference paper at ICLR 2025
Appendix
TABLE OF CONTENTS
Preliminaries
15
Recovering existing schemes
16
C Proofs for Section (Amalysis of the implicit scheme (8))
17
D Proof's for Section (Amalysis of the explicit scheme (Algorithm 1))
18
Proofs for Section (Linear convergence)
24
F Proofs for Section 8 (Tightness)
25
G Relaxing p through coordinate-wise update
25
14

---

Published as a conference paper at ICLR 2025
A PRELIMINARIES
The distance from E Rd to set Z C Rd is defined as dist(z, 2) := ming'ez ||z z'1l-
The normal cone is defined as (=)=) == [ (0,z' I 2z' E 2 and the projection as (x) := arg minn.we || w| and the proximal operator of R + - as prox,g (z) arg we g(w) 2 | w||2.
We restate here some common definitions from monotone and nonexpansive operator for conve- nience (for further details see Bauschke & Combettes (2017)). An operator A R = R" maps each point 2 E Rdd to a subset Az C IR",, where the notation A()) and Az will be used interchangably. We denote the domain of A by domA1 == (= E IRd Az * (), its graph by gph A == ((2, v) Rd TR" e E Az]. The inverse of A defined through its graph,
gph A = [(VV (z, v) E gph A} and the set of its zeros by
zer A == {2 E Rd 0 Az).
The set of fixed points is defined as
fix A = {= RRdd
2 E Az].
Definition A.1. A single-valued operator T: Rd + Rd is said to be
(i) nonexpansive if T - TT''l < ||2 ='|l V2,2's E Rd..
(ii) quasi-nonexaansive if I[T 2" - || 211 (Vz E (2) E fix
(iii) firmly nonexpansive = [|'||= < ||= - 2 [( 21) (T= -22)11 V2, E Rd.
(iv) firmly nuass--nonexaansive if [['z - 2 2 $ ||a 2" 11 ||> - TT=l? (Vz E (V2* e T).
The resolvent operator JA = (id (id+A)-1 is firmly nonexpansive (with dom/A RR) iff A is maximally monotone.
Let S C IRd. A sequence (=E) is said to be
(i) Fejér monotone if || - =|| S || - =|| (V2 E S)(k EN
(ii) Quasi-Fejér monotone if ||= =112 < || - 21| + ek (V= S)kk E
where kEN) is summable sequence in (0, oo).
Definition A.2 (monotonicity Bauschke & Combettes (2017)). An operator A Rd Rdd is called monotone if.
(u v -'- --2= 0 V(2,e), (z', gph A,
The operator A is maximally monotone if no other monotone operator B exists for which gph A c
gph B.
Definition A.3 (Lipschitz continuity and cocoercivity). Let D C gd be nonempty set. A single- valued operator A: D + Rd is said be L-Lipschitz continuous for any 2, E D
||zz Az'l S L - =211--
and B-cocoercive if
(z (z= - Az 2 AI Az'11
Lemma A.4. Let A: 1dd R denote single valued operator. Then,
(i) A is 1-Lipschitz if and only ifT id - is 1/2-cocoercive.
(ii) If A is L-Lipschitz, then T id anl, 77 E (0, 1/2), is (1 - (LLmmmmmmootooo and in particular for all u, U E Rd.
[ Twll 2 TT v|]-
(17)
15

---

Published as a conference paper at ICLR 2025
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:
(Tu Tu, u) = ||u - u|I² () - Au, u) 2 (1 7T)1Iv ul|?.
In turn, the last claim follows from the Cauchy-Schwar inequality.
We will use the following closed form solution concerning hyperplane projections.
Fact A.5. The projection pp( = arg min ||= - x I1 onto the set = {= (a, 2) 2 b) of D is given as,
(x) = (a, σ)
||0|| a
(18)
B RECOVERING EXISTING SCHEMES
Let recall the proposed implicit scheme in (8), which for y > 0. d E (0,2), 8 s and
(0, + ) proceeds as follows:
find 2 E RRd and v E =
s.t. zk = -vv + + and
(o ot) S 0 1
(19)
update k+1 = 2 Agayo ag
1ot T+
The scheme can recover a range of existing methods.
The relaxed proximal point algorithm Take the error be g in which case on 1
and the error condition is satisfied for any a. By using that et 2 zt the update (19) reduces the relaxed proximal point update (Eckstein & Bertsekas, 1992)
z (id (id)
(20)
k+1 = (1 - Ax)=* * + Ag
where 7 > 0, A E (0,2(1+ )) and -
Solodov & Svaiter
In the monotone case (p 0) and with the more stringent enor conditioning ||=* - ==11), (19) reduces to the method Solodov Svaiter (1999a)
| S a max
find
z I and Th 7
s.t.
* = *h - -i +* and ||s*|| || S a max max(1 1| - **13
(21)
update k+1 = -Aaay
10011
f > d E (0 and E (0, 1).
AdaptiveEG+ Pick eh = F2 - Fz" Notice that the error is a natural choice as it replaces the implicit evaluation Fz in Th with the known Fz Define the forward operator as H id F such that ūt = H² H Then (19) reduces to the scheme of Pethick et al. (2023b):
オ = (id +> A
(22)
++ = t Au t - HH*)) 04k (H2 H
1 HEE
where 7 E (1-2p)+. 1/4), d (0,2) and 8 E (-1/2,p). A constant stepsize variant can be obtained by absorbing the adaptive og into da. Let À = Agais then the resulting scheme can be written
z = (id +>A) (Hz*)
(23)
A+1 = X(H 1z*1)
16

---

Published as a conference paper at ICLR 2025
where y (1-2p]+. À E (0,1+ + ?5) and d (-7/2, When in the unconstrained case (A = the scheme reduces to the extragradient+ method (Diakonikolas et al., 2021)
= zt =FFz z k+1 2² Fx
(EG+)
which we synonymously refer the relaxed extragradient method since EG+ be rewritten as z = = F 2+1 (1 (1- A(2
(24)
FF*)
forward-backward-foor In the monotone case (p 0) we can recover the celebrated (FBF) method of Tseng (Tseng, 2000). Pick ex F2 F and y < I/1. (strictly). This allows us to pick d as noted in Pethick et (2023b, Rem. 3.3) in which case the scheme simplifies to
z = (id +7.A) (s* 7F2
(FBF)
k+ = 2 (1= - Fzz")
with y E (0, 1/). When in the unconstrained case (A 0) the scheme reduces the extragradient method (Korpelevich, 1977)
zh x² F
(EG)
k+1 z² F=
C PROOFS FOR SECTION 5 (ANALYSIS OF THE IMPLICIT SCHEME (8))
Proposition 5.1 (Properties (7)). Suppose Assumption (iii) holds, p. and (5) satisfies the following error condition,
-(E, 0) S $.
(12)
where a E (0,1+ R). Then,
(i) The projection operator P .dd + Rdd in (7) is firmly quass-nonexpansive.
(ii) Z" C fix zer S.
(iii) The closed form solution to P given in (7) and the stepsize satisfies 2 1 11++
Proof. To find the closed form solution for the projection we invoke Fact A.5, concerning general hyperplane projections, with = - and b = (6, | For & D(z),
(0.u (a,u-1)+ F||2
(u)
(25)
||e|
Let us prove 2 C fix P. The set D2)) defined in (6) is constructed to contain the solution set. Let us verify this claim. From the definition E in (5) we have that E SS. By using Assumption 3. 1.iii, solution 2* E Z satisfies
(o, - x²) 2 31
which is contained in D(z) by assuming 8 < p. This proofs that 2 D (2) for all E Rd. which
is more general than 2 C fix P.
To prove fix P C zer S we need to show that the (adaptive) stepsize in (25) is positive and bounded away from zero. We have
( 2) + - (1 1 (1 (s, 2 (1 -
(26)
where the third last inequality follows from assuming -(e, 7) 0|| Thus, (26) is strictly
positive assuming 1 + (which proofs the last claim). Consequently, E fix P only if
0 E SE. This proves the second claim.
17

---

Published as a conference paper at ICLR 2025
Finally for the first claim, the projection onto convex set is firmly qussi-nonexpansive. That is, for
all 2 E IR" and xt E 2 C fix])
(w) ==1 S I|u = ==1
| (w))
where we can take u = 2 to establish the claim. This completes the proof.
For completeness we include well known convergence guarantee for the KM iterations applied to a firmly quasi-nonexpansive operator, which is used to establish convergence of (8).
Theorem C.I. Suppose T RRd + R.d is firmly quasi-nonexpunsive. Consider the sequence (=*) )EN
generated by KM with 0g (0, 2). Then, for all 2t E fix
11:0 2=12
1Tt - 1 S RE BE(O....KI))
min
2 Aa)
Proof. We have
|| z² 1|2 = (1 - > - 112 + As - =1
A1 (1 Ax] - -/1
(1 >x)l - =1- 2 + ds IT - -T=" de - Ac) - 211
< (1 >x][ =11 As 12 =1 Ax - -xx(1 T2 2/1
= || - =-1| - |T= -
(27)
where we have used firmly quasi-nonexpansivenes T.. Telescoping completes the proof.
Theorem 5.3. Suppose Assumption (ii() holds. Consider the sequence (z") generated by (8) with As E 20, lim inf (2 Ax) O, S P. and a [0, 4). Then, for all
11:0 -
11
min dist(O,
kE Koo,
2
o)2K
Furthermore, if 2 zer then (z )eeN converges to some 2t E z"
Proof. From Proposition 5.1 and Theorem C.1 have that
120 221
min Ax As)llaa=*112 AE(O....K-)
K
From Proposition 5.1 we have that as 2 (1 + o). Lower bounding ag in the convergence guarantee and rearranging obtains the claimed rate.
It follows from Fejér monotonicity with respect to fix P that (2*) is bounded. Using telescop- ing argument we have that (I(*")))EN converges to zero, implying that the limit points * belong to zer S when ser S 2 claimed.
Lemma C.2. Suppose Assumptions 3. 3i) and 3. 3ii( hold and the stepsize ? < 1. Then the resol- vent Jus single-valued and has fill domain.
Proof. The operator 7S is -yL-monotone due to Assumptions 3.) and 3.i Consequently (15) -1 _=--mmoonoonne since 7 < due to Bauschke et al. (2021, Lem. 2.8). Thus, the resolvent J,s is valued and has full domain due to Bauschke et al. (2021, Cor. 2. 2.14) which completes the proof.
D PROOFS FOR SECTION 6 (ANALYSIS OF THE EXPLICIT SCHEME (ALGORITHM 1))
Theorem 6.1. Suppose Assumption 3.1 holds. Consider the sequence (2²) keNN generated by Algo- rithm 1 and let lim inf A2 >x) 0. Then, for all z* E Z
1| - 101
min dist Szh dist(0,Szh)² k-10
89 21
18

---

Published as a conference paper at ICLR 2025
Furthermore, if 2' zer S then (2") converges some 2" Z*. Moreover, let n denote the number of inner iterations in Algorithm Then,
(i) the error condition passes immediately (i.e. n even when only S 1 ifa E 1++1 which is feasible for -
ii) the error condition passes after at most iterations for some < 1/1. if 2 2-In(n)/n
a *+1-Im(m)/n
()) which is feasible for [1
In(n) n+1 1ntln-n(n)/m
Proof. The convergence rate and convergence of (z LEN follows immediately from Theorem 5.3. The resolvent J is single-valued and has full domain due to maximally monotonicity of the oper- ator A. Theorem 6.1 follows from the argument in Section 6.1. Theorem 6.1 follows directly from Lemma D.7 due to Assumptions 3.1(1) and 3.1(i)).
Corollary 6.3. Suppose Assumption 3.1 holds. Consider the sequence (2 (eeN generated by Algo- rithm and let k = lim inf Aς(2 - Ax) >> O. Then, for all z" E 2* the sequence achieves min. (0,t S=* I after most
(1 + n) - =
# (oracle calls)
2 - -0)
to both the operator F and the resolvent (id+>A)~+ where n I+pL
In(
I+pL
an upper
bound on the number of inner iterations.
Proof. Due to Assumptions 3i) and 3ii, from Lemma D.8 we know that n inner iterations sufficient for satisfying the error condition. Note that one additional evaluation of carried out at each iteration, i.e. Fz* Combined with the rate in Theorem 6.1, the claim is obtained.
T+pT. In( T+pT.
3
D.1 ANALYSIS OF THE INNER ITERATIONS
In this section we provide formal proof for the lower bound on the value of p. We have that:
S p/7 +1 p -1 o)
So we can start by providing lower bound on the value of
We will index the inner iterations of Algorithm by j. meaning that we can rewrite the 7th iteration of the inner loop, as:
Notation:
h 2² - =-FFf
2/ (id +7-) 11
For the sake of exposition, let us rewrite the condition of line of Algorithm 1, using this notation:
(at S ott 2 (1- σ) || where 5 = h2j = + FFF
(28)
D.1.1 LOWER BOUND ON O
If
0. then (28) holds trivially for any for the rest of this section, will analyse the
case where | >
Lemma D.1. j inner iterations of Algorithm 1, we have that:
| - -ドド
1 + || - F
19

---

Published as a conference paper at ICLR 2025
Proof. We have that:
2 3
zk
-
+ -FEE)11
hg
2 + +
Let us now analyze the left hand side of (28).
2( - x/
||2* - 2
+ |
1/ - 11
|| =
1 - FEJ1
So from (28), we have the following bound for
2g
2
F
1F
2 1 1
||
?
1 1 2)
-
FF
2 1
2
We will now maximize the above lower bound a, which equivalen to maximizing for || we get from the triangular inequality, that: + F - F
Since 8 = 2
|| < || - +
1 31
So we get:
| 전 |1 -
1
1
2
(1|2 - 1 + || 1F
1
(1
|| | >F (1)
- -
||7 -
0
2
(|1* =
*
||
F - 1 F
0
2
2
F
FF
|
E||l
||
7 Fz
1
z
| Fzt F
FF
0
N
2
1 - ボ
+
FE x
|1 - -
0
||
+ 11 - F
D.1.2 CONTRACTION BOUNDS
Lemma D.2. Suppose Assumptions 31) and 3.1 For stepsize and inner iterations, we have:
|| - S (7 ||** -=tll
Proof. For the j inner iteration, we have that:
الاا [[ +y-4 2 - (id (id+>>)=
(Assumption 3.1 S ||b h
= 118-551-7-F33
(Assumption 3.1())
By doing this recursively, we get the lemma statement.
20

---

Published as a conference paper at ICLR 2025
Lemma D.3. Suppose Assumptions (i) and 3.1 For stepsize 7 and inner iterations, we have:
|| - - S (xL)+1 || -=1ll
Proof.
| - S (7L)
-
The statement follows from the previous lemma.
D.1.3 LOWER BOUND FOR || =2
Lemma D.4. Suppose Assumptions 3i) and 3.1(i). For j inner iterations, we have the following inequality:
|| zf+1l 2 2| =
1-(2))14
where B
1471
Proof. We will proceed by proof by contraction. Let us assume that for j inner iterations we have the following inequality
|| - s/+1l < <B I
(30)
1-(1 for 3 = 1476.
We have that:
|14 n = 1|*a - -F - 2/ + + = ||| 5+1 F=
Note that Algorithm we set z zt. Additionally, we have that: h1+1 + 7F 24
2t, for all
j 2 O.
Then we have that:
1 h34 (id ((d+>)))
(id A)} 1 j+1 + FF
|| 2
'nt (id A
(Assumption 3.1(i))
S 1 1
1|> - PP=
(Assumption 3.1())
S (xL) ||* -
The first inequality comes from (firmly) nonexpansiveness of the resolvent when the operator is maximally monotone, while the second comes from the Lipschitz of the operator F. Now applying the triangle incquality, we get:
|| h5+1 (id 47d)
(id Ay) + - FF2f
hi (id+ + +
| (id +y 14 + +
(1 B) -
Above we used the assumption of the proof (30). Combining the two previous inequality, we get:
- 3
||
|| - -
(31)
7L
From the triangle inequality, we have that:
| =/1
zk - ||
S || - =
||
=
||
2 ||
< (yL || z
1 - 3 7 ||2*
3
-
(T 1|= =
1 - (7L)++1
8
1 7
Where the second line comes from Lemma D.2. The third line comes from our assumption in the proof, (30) and (31). Thus our assumption (30) is violated which concludes the proof.
21

---

Published as a conference paper at ICLR 2025
1.1.4 PROOF OF LEMMA D.6
In this section we will provide the bounds on and p function of the product 7 and the inner iterations j of Algorithm 1.
Lemma D.5. Suppose Assumptions 3.1(i) and 3.1(ii. For j iterations of the inner loop of Algo- rithm I and stepsize < 1/L, we have that the enror condition of line 5 of Algorithm I has been satisfied, for
(TL) + (7L)+1
(32)
1+ (yL)+1
Proof. From Lemma D.I, we have that:
|| - P
o 2 2 - + || -
order to get the tighest lower bound on a we want to maximize the right hand side of this incquality. We can do this by minimizing the value of || - 2 and maximizing the value of
1/ - all-
From Lemma D.4, we get that:
- 2 2 3 311=* = ||*-
where 8 = 1-(y
1474
and from Lemma D.3
|/ - FF
S (y 1
combining the above, we get that:
(7L)² || - -
1-(x
| - * + (7 -|=
1t7l
(T
1-(x 147l + (TL)
(gL) + (2L)++1
1 (7L)5+1
Now using Lemma D.5, we can state our corresponding lemma, for p.
Lemma D.6. For j iterations of the inner loop of Algorithm 1 and stepsize < 1/L, we have that Algorithm 1 handles p. for p:
1 1- (7Ly
p - 1+ (T
(33)
Proof. We start our proof from Lemma D.5, from which we get the inequality:
(yL) + (ZL)++
1 1+ (yL)++
We know that for p it holds that: p 2 - + y o, substituting the incquality for completes the proof.
D.1.5 BOUNDING P BY THE NUMBER OF INNER STEPS
In this section we will convert the lower bound on that is presented as a function of y and L in Lemma D.6 to function of the inner iterations n.
Lemma D.7. For inner loop iterations and inner stepsize = (1 - Inn/n) L,, we get that the minimum value for P. supported by our algorithm is least:
1
In
1
(34)
7.
11
11
Inn
22

---

Published as a conference paper at ICLR 2025
Proof. Let restate Lemma D.6 for the sake of exposition.
- (7L)
p
(35)
1+ (2
By selecting 7 = x// L,, we have:
1
- xn
P
L xE(0,1))
max for
1 + xa+1
Now will lower bound the the right hand side.
1- x
In n
1 - (1 In ym
max {or 2E(0,1]
+ x
+ (1
1n y2+1
71
+
7 (1
In
n
n
1
Inn
12
Where in the first line we just choose In(n)/n
D.1.6 INFERRING ORACLE COMPLEXITY
Lemma D.8. Suppose Assumption 3.1 holds. Then Algorithm I needs to do
n
In( + p L 1
inner loop iterations.
Proof. We start from the inequality we gave for Lemma D.7, which states that with n inner loop iterations we can handle p. when:
In n
f1
(1
n +
In
Inn
1 n n+11 1
By multiplying both sides with -L, we get:
In
-p.L <
(1
(36)
n+
Decreasing the right hand side of 36, with respect n, yields worse requirements complexity wise, for n and æ. Given this observation, now let us set n = x e", for some x, in this case, we have that:
In In(2 x e*) = x + (n x) s 2r + In < 2x
Since 2x is the upperbound on In we have that: Inn >
2x
Also note that since
2xea
2re 2 e", we have that 2 11 So:
2xe
e=+1"
Inn n
2x
2
n n+1
2xe
ex +1
So we can upperbound the number of iterations n required for a certain p, I,, by calculating a solution to the following equation:
-p. L-
- +
We solve the above equation for ex > 1, since we require n > O. By solving for e", we get:
e" 2 2- / - LV8 L
L)
23

---

Published as a conference paper at ICLR 2025
We can simplify the above expression by taking the upperbound for the value of -p- L which is 1.
So we get:
e" = 3 1+ p. 1+p.
By solving for z, we get:
3
In(
1+p p.
So we get that for
3
11 1+ p.
IIn(
+ p
E PROOFS FOR SECTION 7 (LINEAR CONVERGENCEE)
Theorem 7.3. Suppose Assumptions 3. 3.i( and 7.1 hold. Consider the sequence (z generated
by (8) with À E (0, 2), d S P, [0, + 4) Then, for all z" 2*
ds zer 5) S (1 - 5)* dist ? (z" zer S)
with Ç = = ())
Proof. The error condition in (8) can equivalently be written as
(= - =² ,²a) 2 (1 - r) 001
Using || 1|=* - =b112 + || 2 (z* - - due to eh = z* _k we have
|| - 11 + || 1|2 || 2 2(1 11
follows that
(1 -1-20 20 | < (1 + M> 1012
(37)
for any > 0 where we have used Young's 's inequality through the inequality
-Ila- bl1 - _|bb1
which holds for any a, E IRd and 0. By optimizing a = - in (37) and rearranging we obtain
||a - 2 2 E||
(38)
with & = 1
The update (8) is constructed as the KM iteration on the projection operator P (7). Thus, from the Fejér monotonicity of the KM iteration established in (27) we have
||2
2"
1|2
< || - 12 A2 Ax) P 2
= ||= - =11 - Ax - du 1a)a"1l0**1
from which it follows that dist? (2 zer 8) S dist? (2* Using the triangle inequality
zer S) 1
- >x )z)a
(39)
dist(2 zer 5)= < 11 211 < 1 - 2011 + 11 - =
(38) | 211 + E||T*|
(Assumption 7.1) < -
(40)
with 2 = IIzer s s(at). Combining (40) and (39) we obtain
dist? k+1 zer S) < (1 (+) dist? dist? (2* zer S)
with C+ = (2 A (7, 2 A2 As) + - - o)² ("r++sj= which uses og 2 1+
from Proposition 5. Taking A À completes the proof.
24

---

Published as a conference paper at ICLR 2025
F PROOFS FOR SECTION 8 (TIGHTNESS)
To prove the lower bound we rely on the following operator based on Pethick et al. (2022, Ex. 5). Example F.1. Consider the following linear operator:
F2 (ay + bzx by az)
(41)
where 2 = (x, 3), b < and > 0. It is straightforward to verify that
(i) Assumption 3.)(i) is satisfied with L. v b2.
(ii) Assumption 3. (ii() satisfied with p
h
a=+82
Theorem 8.1. Consider sequence (=*) generated according to rPPA with y > 0 and ãg > 0 for all N. Let p S -(1- -11-))7
)7 Then, there exists an operator S Rd - Rd for any d >
satisfying Assumption 3. 3.I(iii) which the sequence will not converge.
Proof. We follow the argument in Pethick et al. (2022, Thm. 3.4) closely. The update rule rPPA is linear operator by linearity of the operator F. Specifically.
T (1 C 0z (I FF)
(x(1+1))-
+
05 82
(42)
a²y² +6 +2by+1
26
2 2by++ - 5g +
a²-² 62, +2by+1
A linear dynamical system is globally asymptotically stable iff the spectral radius of the linear map- ping is strictly less than Let X1, A2 be the eigenvalues of T. Then the spectral radius is the largest absolute value of the eigenvalues. For T we have,
max |&, v(a2g2 (by + 1)2) ((āx 1)7 ((āx 1)y (a² + b2) 2b) 1) 22 + 62) + 2by +
(E(1,2)
(43)
(āx - 1>>?(((x 11y - 2p) +1
712(7 + 2p) +
where have used that the requirement < -(1 2 ) for convergence of the discrete dynamical system. On the other hand, since (42) is linear system, we simultaneously learn that picking 7 any smaller would imply non-convergence through max; [Ar 2 1 (given 20 *f 0). Noting that problem (42) be embedded
- and L2P. Solving for max; Ayr 1, obtain
into a higher dimension completes the proof. We provide an accompanying Mathematica notebook for verifying the above steps.
G RELAXING P THROUGH COORDINATE UPDATE
In this section show that our implicit scheme (8) can also be used to capture similar construction to the primal dual extragradient algorithm in Pethick et al. (2023a). The coordinatewise update we will develop is important for relaxing the Lipschitz condition, which in term relax the condition on the weak MVI parameter through the weaker requirement on the stepsizes.
To allow for coordinate specific stepsizes will introduce the positive definite stepsize matrix E Rdxd Note that this generalization of (8) only affects the constants in the resulting convergence guarantee, but is not necessary for relaxing the condition on p. In other words, (8) can directly capture the Gauss-Seidel type method developed in this section for a particular choice of the error ck (2** M, (z*)) where M is defined in (48). For simplicity will consider nonadaptive variant with some > 0:
find
z Rdd and bh S
s.t.
r-1 (2* zt) = 8 + + and
I coloo
(44)
compute
A+1 = zk a.
25

---

Published as a conference paper at ICLR 2025
Theorem G.1. Suppose Assumptions (ii( and 3. 3.i( hold. Consider the sequence (2 TEEN gen- erated by (44) with a >> and > - - o - 2 where 7 is the smallest eigenvalue of T. Then, for all z" E 2
1| - - 1 distr (0, S= 20 (1 - 1 2 5)K
min R-1)
(45)
kE
Remark G.2. Note that well-definedness and vanlee-valuedness of the proximal update still needs to be ensured.
Proof. Recall that oh E Sa and the error condition
vhh -E",
S
(46)
The update in (44) yields
||2 ||? 1
|| 2*1 1 + a2110*11 2a 2* 2²)
= || k - z "I + a2|15=1}
2a 2 - - 2a(0 (0, z - =21)
= || - 2" ?|?
2a(1 1) =a(t",s"), 20 1t - 2²)
(46) I || R =" 2 2a(1 ") || -2 zt 2²)
(Assumption 3.1 I || & 2 - 2a(1- o "> 2apl1=*12
< k - z" 11 20 - o _ + +
(47)
where the last inequality uses that Rearranging, summing and telescoping completes the proof.
||a < || with 7 being the smallest eigenvalue of r.
Instead of making Lipschitz continuity assumptions on F F + directly, we consider the following operator,
= F()) -
(48)
where the operator Qu : Rd + Rdd is to be defined.
Assumption G.3. The operator M defined in (48) is L -ipschitzz with Las S 1 with respect to a positive definite matrix I' E gdxd, i.e.
[|M{()) M2(=')llr & T. ||= 2'Il-- V2, E Rd.
(49)
We will write the update in terms of Hz)2) == r-12 - Mz),,, which will be important in order to relax the Lipschitz conditions. With M,, defined, it is straightforward to establish that H, is 1/2- cocoercive and strongly monotone long as M, is Lar-Lipschitz continuous done in (Pethick et al., 2023a) (see Lemma G.4). This provides a strict generalization of Lemma A.4 concerning the forward operator H id F.
Lemma G.4 (Pethick al. (2023a, Lem. F2)). Suppose Assumption G.3 holds and let I' E gdxd be a positive definite matrix. Then, the mapping H=(=) = r-12 Ma(z) is 1/2-cocoercive, iee.
(H2(2') - H=(=), 2) (1H+(=>') H=(x))l? V2,z' RR.
(50)
Proof. By expanding using (48),
Hz(z) -
(2- (M2(=)) -M(()))
(51)
Using this we can show cocoercivity,
(H² - H2()), = (z') - ())) (51) = (3') - H.(=)) + 1l - (=)('')
- (AM()) -
- M2(2'))i
(Assumption G.3) 2 (s') - -H.())]l (1(1)) -211--
(52)
This establishes the claim.
26

---

Published as a conference paper at ICLR 2025
Specifically, pick the error ex = M2 (2*) M2 (2*) in (44) such that the update rule defining z4 reduces to a preconditioned update asking for 8t E IR" such that
H²+(2*) H (5*) rZ E S
(53)
Thus, the update (44) for the particular choice of ex reduces to the following with I E Rddd and 0:
find I E TR, TRL,"* v Sz
s.t. Hz*(=*) (3th n compute g = - aT (H2² (2 H²*(2*)
(54)
We obtain the following corollary by specializing Theorem G.1 to the update in (54).
Corollary G.5. Suppose Assumptions 3. (ii), 3. (iū)) and G.3 hold. Consider the sequence )=*) kEEN
generated by (54), 0 and p (1-0h where is the smallest eigenvalue of T. Then, for all 2" EEZ z
|1 - 2" 1
min (o(.....K-1)
(0,
(55)
a -)
Proof. Let us compute the error tolerance a for the particular choice of the error ex, From 1/2-
cocoercive due to Lemma G.4 we immediately have
[1H+a(=**) H.* (2* < (Ha+(z*) - H2*((")),,))) - -
(Ha+(2h)) - (x*),"), M,, (x+()*)) + +1 H22
(56)
which equivalent to - (6* E Theorem G.1 for the particular d.
S σ a| with a We obtain the result by specializing
Observe that the weak MVI parameter p in Corollary G.5 depends on the Lipschitz constant of op- erator M rather than Lipschitz operator F directly, through the smallest eigenvalue of the stepsize matrix r. This important because & can potentially be larger than 7 +. which is otherwise required if were relying on L-Lipschitz of F.
In the following, we will choose an asymmetric Q in M, that leads to a well-defined (Gauss-Seidel) update for =* and then subsequently show the implication for the Lipschitz condition. For simplic- ity, we first illustrate the idea for minimax problem resulting in a coordccoor update with only two blocks.
Minimax
Consider the following minimax problem
min max ((x.)) y). zEX' vEY
(57)
We will pick an asymmetric Q
(3) (0, - V y ( y))
(58)
with z = (xx and z = (H, g). in which case (53) is well-defined and becomes an alternating update
I (x+ I v Voo(a )² = 1 + V v (a ,t) y²))
* (H, + S H H
<>
(59)
where we have rescaled the iterates for convenience by defining 1* (It (gg))) We furthermore have that the desired Lipschitz assumption on the operator M (Assumption G.3) holds provided
V V= u) V. 2/)1 < 22 | - ='112 L Ily 1
| [V,o(x,)) Voo(z, 2/1l < 1 v112
Specifically, we have that LM = max M L2 |1 2 LE |222 + L3 [2]]]]] which can be smaller than the Lipschitz constant T. of the operator F.
27

---

Published as a conference paper at ICLR 2025
Coordinatewise More generally, F(z) = (Fi(2)..... Fm (2)). Consider the decomposition & = (æ1,..., 2m) E R' and define the shorthand notation 2g: (2) 22, ..... 2m and 22i = (2), ................................ 2m) for the truncated vector. More- over suppose that A decomposes into Az ( Am zmn) with A; Rd = IR maximally monotone and define
consider block-coordinatewise update for general
1.l.diagTT........ .m)) where r, E Rd xd, are positive definite matrices. We will pick an asymmetric Q
(2(2) = (0, (1 =22), (2 E2, 223), .... Pm (2,
(60)
in which case (53) is well-defined (see Pethick et al. (2023a, Lem. F.1)) and becomes a Gauss-Seidel update
(LT A -((())))))) (T; +.) (2 - F--1 2)
ii= if i = ......
zh (H,+
(61)
We furthermore have that the desired Lipschitz continuous assumption on the operator M (Assump- tion G.3) holds provided
[[((2)) F,(= =2011 S Σラ= L2,,, [|=; - =/]l Vi E [m]]
Specifically, have that L3s maxie(m] {Ezelt 2, [[]]] which can be smaller than the Lipschitz constant L of the operator F.
28


Reviews:
[{"review_id": "yp8rdeVuSF", "reviewer": "Reviewer_kMEF", "summary": "This paper investigates variational inequalities that satisfy the weak Minty variational inequality (MVI) condition and proposes a hybrid proximal extragradient method. The authors establish improved complexity bounds for both the implicit and computationally efficient explicit versions of this method, extending previous results to a broader range of the MVI parameter $\\rho$. The tightness of this range is confirmed through a lower bound analysis for the exact version of the method. Additionally, linear convergence is shown to be achievable under appropriate conditions.", "questions": "1. The authors refer to the halfspace projection as an *error correction* step. When comparing Eqs. 9 and 10, if we substitute the first equality condition from Eq. 8 into Eq. 9, we get $z^{k+1} = (1-\\lambda_k) z^k + \\lambda_k (z^k - \\bar{v}^k - \\epsilon^k)$. Can we interpret the error correction as eliminating the *explicit* error term $\\epsilon^k$ in Eq. 10 through an additional operator evaluation $\\bar{v}^k \\in \\gamma S \\bar{z}^k$? Consequently, although the calculation of $\\bar{z}^k$ involves this error term, it only appears *implicitly*, and with the error condition, it ensures Fejér monotonicity.\n\n2. Why is the parameter $\\lambda_{k}$ considered within $(0,2)$? The analysis suggests that $\\lambda_{k}$ primarily affects the step size $\\lambda_k \\alpha_k$, while the theoretical results indicate that $\\lambda_k=1$ yields the best convergence. What are the benefits of considering $\\lambda_k < 1$ or $\\lambda_k > 1$?\n\n3. Does $\\alpha_k$ have an upper bound?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. **Theoretical Results**: This paper achieves superior complexity and convergence over a broader range of $\\rho$. In particular, the authors establish an upper bound for the number of inner iterations that is independent of target accuracy. The theoretical results are further enriched by a lower bound analysis, thoroughly addressing the questions posed in the introduction.\n2. **Algorithm Design**: The authors construct the algorithm based on a halfspace projection operator, yielding a hybrid method that combines the inexact proximal point method with the extragradient method. This novel perspective offers a systematic approach to determining the step size and recovers several algorithms from prior work under specific conditions.\n3. **Presentation**: The paper is well-organized, easy to follow, and contains extensive content.", "weaknesses": "1. **Significance (major concern)**: While this paper addresses the questions raised in line 47, the practical significance may be limited. Previous work has achieved $O(1 / \\epsilon \\log (1 / \\epsilon) )$ complexity for $\\rho > -1/L$; the marginal gain from removing the logarithmic term (which is much smaller than $1/\\epsilon$) is unclear. Additionally, the $O(1/\\epsilon)$ complexity is already achievable for $\\rho > -1/(2L)$, so the practical value of studying $\\rho \\in (-1/L, -1/(2L)]$—a narrow range—seems limited.\n\n2. **Presentation Complexity**: The relationship between the proposed algorithm and existing methods is somewhat complex. A diagram could help clarify this relationship. Additionally, the placement of Algorithm 1 feels distant from Section 6.", "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": "o3R6VbXVZo", "reviewer": "Reviewer_Gq7N", "summary": "This paper introduces an inexact proximal point algorithm with an error correction mechanism, which guarantees convergence for minimax problems that satisfy the weak Minty variational inequality (MVI) with a parameter  $\\rho>-1/L$. The proposed method achieves a convergence rate of  $\\mathcal O(1/\\epsilon)$ without the logarithmic complexity factor found in previous approaches, making it a promising solution for weak MVIs in constrained settings.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The proposed algorithm achieves better iteration complexity by avoiding the logarithmic factor present in previous methods.\n\n* The performance results shown in Figure 2 are impressive and highlight the algorithm's effectiveness.\n\n* The scheme unifies the analysis of the relaxed extragradient method, the relaxed proximal point algorithm (rPPA), and classical methods for monotone problems.", "weaknesses": "* It would be helpful if the authors elaborated on the intuition behind the necessity of multiple inner loops when $\\rho<-1/2L$. Further insight into why these loops are essential could enhance understanding of the algorithm’s design choices.\n\n* In Section 8, the authors mention the possibility of extending the range of $\\rho$ beyond $1/L$. Including experimental results to illustrate this potential would strengthen the paper’s claims and provide evidence for the method’s flexibility under various settings of $\\rho$.\n\n*  The paper would benefit from additional empirical evaluation to demonstrate its applicability to complex real-world problems. Alternatively, a more explicit discussion on the practical relevance of these theoretical results could help clarify their significance for challenging problem settings.\n\n* The paper’s notation is somewhat confusing, as the authors sometimes use the range of $\\gamma$ to imply constraints on \n$\\rho$ and other times directly specify the range of $\\rho$. Since $\\rho$ and $\\gamma$ are related, a unified notation throughout would make the technical content easier to follow, especially given the paper’s density.", "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": "JOZrzBuAId", "reviewer": "Reviewer_bh4m", "summary": "Non monotone games, which are operators that are non convex and non concave appear in several applications and are proven to be hard to solve. One important class of problems within this is the class of problems satisfying the weak Minty Variational Inequality. Thiis was one of the counter examples proving the hardness of the broader family of problems. The weak minty condition is a relaxation of monotonicity, i.e., roughly for some $\\rho$, we require for all solutions $z^{\\star}$ of an operator S, \n$$ \\langle S(z) , z-z^{\\star}\\rangle \\geq \\rho \\|S(z)\\|_2^2.$$\n\nThere has been a flurry of work that has tried to give algorithms for different values of $\\rho$. When the operator is $L$-Lipschitz, the relaxed extragradient method allows $rho > -1/2L$ and the relaxed proximal point algorithm allows a larger range, $\\rho > -1/L$ but loses an additional $log 1/\\epsilon$ factor. This paper considers the range $-1/L<\\rho <-1/2L$ and gives an algorithm that gets rid of this extra $log 1/\\epsilon$ factor. Their method also unifies the two methods mentioned above. The additionally also obtain some kind of linear convergence under additional assumptions that I dont fully follow.\n\nTheir algorithm follows an inexact proximal point algorithm, where they require the errors of every prox step to be small in order to obtain convergence. Normally this would involve increasing the number of iterations, but the authors get away with this using “half-space projections” inspired by Solodov and Svaiter’99.", "questions": "Some suggestions to the authors:\n1. Please check the introduction, it has several grammatical errors.\n2. If possible please introduce the halfspace method. It seems to show up without introduction and it is not clear what it means in Section 4\n3. It is also not clear to me why the halfspace method works in getting better accuarcy? Also is it the same as the Ellipsoid method? I can imagine that the ellipsoid method would work the same way for convex functions.\n4. I dont follow what the linear convergence means. Is it for the inner loop?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is able to unify a few methods to get one coherent method for solving the Minty Variational Inequality problem to an optimal rate. They also improve a $\\log 1/\\epsilon$ factor for an important range of parameters. It is overall reasonable well written, though I would hope that the next version has background which is easier to parse for a newcomer in the field.", "weaknesses": "I think the paper would improve if there is a more detailed summary of what the previous methods do. I understand the space limitations in the main text but maybe something in the appendix would help. Currently there is a brief overview in the introduction but since the method unifies certain methods, it would be nice to know in somewhat more detail what the unification is.", "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": "pN7FjpdxYd", "reviewer": "Reviewer_F8GR", "summary": "This paper studies the nonmonotone games satisfying the weak Minty variational inequality (MVI). The authors propose an inexact hybrid proximal extragradient method. The method converges with the rate of $O(1/\\epsilon)$ in the maximal range of $\\rho$. Compared with Alacaoglu et al. (2024), the method in this work removes a $O(\\log(1/\\epsilon))$ factor. The authors also show that linear convergence is automatically achieved under their proposed inexact conditions.", "questions": "Most of my questions are about related works.\n1. Have the authors considered the stochastic case like [1,2]. Is it possible to remove the log factor using your framework?\n2. It seems that a similar idea (using proximal methods) also appears in [2]. Although the result in [2] writes the assumption $\\rho > - \\frac{1}{2L}$, it seems their proposed algorithm can also be used in the range $\\rho > - \\frac{1}{L}$ (due to the use the proximal methods) just by changing the constants in their algorithm. Also, [1] applies very a similar MLMC technique as used in [2]. Could the author please tell me if my understanding is correct and compare these related works for me?\n3. The method in this paper looks similar to [3]. What are the differences between the method in this paper and [3]?\n\n[1] Alacaoglu, Ahmet, Donghwan Kim, and Stephen J. Wright. \"Extending the Reach of First-Order Algorithms for Nonconvex Min-Max Problems with Cohypomonotonicity.\" arXiv preprint arXiv:2402.05071 (2024).\n\n[2] Chen, Lesi, and Luo Luo. \"Near-optimal algorithms for making the gradient small in stochastic minimax optimization.\" arXiv preprint arXiv:2208.05925 (2022).\n\n[3] Monteiro, Renato DC, and Benar F. Svaiter. \"Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems.\" SIAM Journal on Optimization 22.3 (2012): 914-935.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The contribution and improvement over previous methods are clear. The analysis in this paper also seems interesting to me. \n\nIf I understand correctly, using exact proximal point methods to extend the range of $\\rho$ to $(-1/L,\\infty)$ seems straightforward. \nAn additional $O(1/\\epsilon)$ naturally appears if using inexact proximal point methods. Therefore the result in Alacaoglu et al. (2024) seems not very surprising. \nBut the result without such a log factor seems much more challenging and interesting to me.", "weaknesses": "1. This paper only considers the deterministic case, which seems to be easier than the stochastic case considered by some other works such as [1,2].\n\n2.  Alacaoglu et al. (2024) also consider the cohypomonotone case, with an accelerated rate. The acceleration seems more interesting and challenging.\n\n[1] Alacaoglu, Ahmet, Donghwan Kim, and Stephen J. Wright. \"Extending the Reach of First-Order Algorithms for Nonconvex Min-Max Problems with Cohypomonotonicity.\" arXiv preprint arXiv:2402.05071 (2024).\n\n[2] Chen, Lesi, and Luo Luo. \"Near-optimal algorithms for making the gradient small in stochastic minimax optimization.\" arXiv preprint arXiv:2208.05925 (2022).", "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)