Extragradient Method for $(L_0, L_1)$-Lipschitz Root-finding Problems
Authors: Sayantan Choudhury
Nicolas Loizou
Venue: NeurIPS 2025 poster ()
Keywords: optimization
extragradient
min-max
variational inequality problem
Primary area: optimization
TL;DR: We propose a novel step size strategy for the extragradient method to solve root-finding and min-max optimization problems under relaxed Lipschitz assumptions

Abstract: Introduced by Korpelevich in 1976, the extragradient method (EG) has become a cornerstone technique for solving min-max optimization, root-finding problems, and variational inequalities (VIs). Despite its longstanding presence and significant attention within the optimization community, most works focusing on understanding its convergence guarantees assume the strong $L$-Lipschitz condition. In this work, building on the proposed assumptions by Zhang et al. [2019] for minimization and  Vankov et al. [2024a] for VIs, we focus on the more relaxed $\alpha$-symmetric $(L_0, L_1)$-Lipschitz condition. This condition generalizes the standard Lipschitz assumption by allowing the Lipschitz constant to scale with the operator norm, providing a more refined characterization of problem structures in modern machine learning. Under the $\alpha$-symmetric $(L_0, L_1)$-Lipschitz condition, we propose a novel step size strategy for EG to solve root-finding problems and establish sublinear convergence rates for monotone operators and linear convergence rates for strongly monotone operators. Additionally, we prove local convergence guarantees for weak Minty operators. We supplement our analysis with experiments validating our theory and demonstrating the effectiveness and robustness of the proposed step sizes for EG.

Extragradient Method for (Lo, Li)-Lipschitz Root-finding Problems
Sayantan Choudhury AMS & MINDS
Nicolas Loizou AMS & MINDS Johns Hopkins University nloizoul juu edu
Johns Hopkins University schoudh8@jhu edu
Abstract
Introduced by Korpelevich in 1976, the extragradient method (EG) has become a cornerstone technique for solving min-max optimization, root-finding problems, and variational inequalities (VIs). Despite its longstanding presence and significant attention within the optimization community, most works focusing on understand- ing its convergence guarantees assume the strong L-Lipschitz condition. In this work, building on the proposed assumptions by Zhang et al. [2020b] for minimiza- tion and Vankov et [2024] for VIs, we focus on the more relaxed a-symmetric (Lo, --)-Lipschitz condition. This condition generalizes the standard Lipschitz assumption by allowing the Lipschitz constant to scale with the operator norm, providing more refined characterization of problem structures in modern machine learning. Under the a-symmetric (Lo, L1 --ipschhiz condition, we propose novel step size strategy for EG to solve root-finding problems and establish sublinear convergence rates for monotone operators and linear convergence rates for strongly monotone operators. Additionally, we prove local convergence guarantees for weak Minty operators. We supplement our analysis with experiments validating our theory and demonstrating the effectiveness and robustness of the proposed step sizes for EG.
Introduction
Min-max optimization problems have recently attracted significant interest due to their widespread applications in machine learning, such as reinforcement learning [Brown et al., 2020, Sokota et al., 2023], distributionally robust optimization [Namkoong and Duchi, 2016]. and generative adversarial network training [Goodfellow et al., 2020]. These problems are often formulated as variational inequalities (VIs) [Ryu and Yin, 2022, Gidel al., 2019, Sokota et al., 2023]. In the unconstrained case, the VI problem simplifies to the root-finding problem [Luo and Tran-Dinh, 2022, Tran-Dini 2024], defined as follows [Gorbunov al., 2022b]:
Find x. Rd such that F(x.) 0,
(1)
where F I2d + Rd is an operator. Root finding problems of the form (1) encompass variety of problems special cases, such as: (i) Unconstrained minimization: finding a stationary point of minzer" f(xx,, is equivalent solving (1) with F(x) f=))), (ii) Min-max optimization: Let min E max L(w,, W2) where L: Bdi Rd2 - IR. In this scenario, if in (I), the operator
is selected as follows:
F(x) (V w, L(wi, T
L(w1, w2) T)T
then solving (1) amounts to finding a stationary point x., = (w TT) E Rdi+da of the min- max problem, which for convex-concave functions L is a global solution (Nash equilibrium), i.e..
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

[(wi, w2) I [(w1., w2+) I L(w1, W2+) [Luo and O'Neill, 2025, Choudhury et al.. 2024], and (iii) Multiplayer games: A Nash equilibrium I, = (wi+...., w ).)" of an N-player game in which each player minimizes their own convex objective (, w-1) with respect to wy (here w-; denotes the actions of all players except i) is also captured by (I), with an operator F())
(Va (wi,, w-1)", ...., Vay L (WN, w= [Yoon al., 2025].
Problem (1) and algorithms for solving it have been studied extensively in recent years under different conditions on the operator J' [Loizou et al., 2021, 2020, Gorbunov et al., 2022a, Diakonikolas et al., 2021, Choudhury el al., 2024]. One of the well-known algorithms for solving VIs and root-finding problems of the form (1) is the extragradient (EG) method [Korpelevich, 1977] due to its superior convergence guarantees [Gorbunov et al., 2022b]. The algorithm is defined as follows
J% 7/k: F(TR),
2k++1 J%k w/ F(rx)
where 7 0 and Wi 0 are the extrapolation step size and update step size, respectively. Since its original inception by Korpelevich, the EG method was revisited and extended in various ways, e.g., non-monotone operators [Diakonikolas et al., 2021, Fan et al., 2023] stochastic [Mishchenko et al., 2020, Gorbunov et al., 2022a, Choudhury et al., 2024, Li et al., 2022], distributed [Beznosikov al., 2022]. Despite rich literature for analysing EG and its variants, most of the existing convergence guarantees heavily rely on the I.-Lipschitz assumption of the operator F' [Korpelevich, 1977, Diakonikolas al., 2021], i.e.
F((x) - F(vIl S D| yll
(4)
for all x. y E R.d However, this assumption can be restrictive; for instance, the operator F(x) x for x E IR does not satisfy (4) for any finite L [Zhang et al., 2020b]. The primary goal of this work is to relax this assumption and establish convergence guarantees under a more general framework.
Relaxing the L-Lipschitz Assumption. Recently, Zhang et al. [2020b] introduced the (Lo, Ln )-smoothness assumption for the minimization problems. Specifically, for mingeR f(x),, Zhang et al. [2020b] assume 2 fx)]] s Lo + L fx)]l (when f is twice diffcrentiable) and later [Chen et al., 2023] proved that this equivalent to:
[V VV(x))V\((] < (Lo + LI vll-
(5)
Zhang et al. [2020b] demonstrated that modern neural networks, such as LSTMs (Long Short-Term Memorys) [Hochreiter and Schmidhuber, 1997], align with (Ln, Ls)-smoothness assumption rather than the traditional L-smoothness assumption (i.e. [Vv ff(iil S L|[= yl). Moreover, they used this assumption to justify why gradient clipping speeds up neural network training. Later, Ahn et al. [2024] showed that similar trends hold for the transformer [Vaswani et al., 2017] architecture.
In Figure we present an example demonstrating the validity of the (Lo, L.)-smoothness condition (5) for the iterates of the EG. Similar plots have been presented for gradient descent methods [Zhang et al., 2020b, Gorbunov al., 2025], but to the best of our knowledge, this lin- ear connection between [ and fxx)]] for EG iterates was never reported before. Following Gor- bunov et al. [2025], we consider the minimization problem mingeR f(x) := log (1 [1+ exp(aaa x)), and plot the val-
Hessian Spectral Norm
Iteration Number
ues of f(x)) on the y-axis against |/V [ fzx))l on the
rraxis. Each point is colored according to the iteration index kt as indicated by the accompanying colorbar. The
resulting plot reveals approximately linear relationship between f || and [[V thereby supporting the modeling of this function within the [[[2 framework.
Gradient Norm
Figure 1: Scatter plot of [x=)( axis and [[V](xx)] r-axis.
| on
Lo + V f [z) or
Now, let us consider the min-max optimization problem min ER'; m L(wi, ((w,, which captured by (1) with the operator (2). If the operator F is T--Lipschitz, then its Jacobian matrix J (x)) defined in (11), satisfies [[])]] < L for all (w] w. (follows from Theorem 2.1

---

with L1 = 0). For example, consider the quadratic min-max objective ming, max,, [ww1, w2) [ wi we 2 w In this case, implementing the EG method and plotting the Jacobian norm [Ix)]] (on the y-axis) against the operator norm |[(()))] (on the z-axis) yields a horizontal line parallel to x-axis (see Appendix B).
However, this behaviour does not persist for more complex problems. For instance, for the cubic objective
mingy maX [(wi, w2) = juo + ww - 3
(6)
[xx)]] increases with the [[ This observation suggests that the standard Lipschitz assumption may be overly restrictive for capturing the structure of such problems (check Figure 2).
To better model this relationship, investigate relaxed condition of the form [[(())]] S Lo + L1 [ [(x) l with (0, 1] which generalizes the standard Lipschitz bound (for I. = 0, this boils down to [x]]))] < Too which the Lipschitz property). Note that, instead of a 1, our formulation permits a to lie in the broader interval
Jacobian Spectral Norm
-23
literation Number
(0, 1]. This condition motivated by the plot in Figure 2, which suggests sublinear relationship. resembling the form h(r) La + Lir" for some (0, 1). rather than a linear trend.
As we will prove later (in Theorem 2.1). for any doubly differentiable min-max optimization problem mingy max [(w,; W2), the condition [I]())] S To [x]] is equivalent to the operator F satisfying the a-symmetric L1) Liipschtit condition (see Assump-
Gradient Norm
Figure Scatter plot of [xxx) )l on y-axis and || [[ on x-axis.
tion 1.1). The equivalent a-symmetric (Lo, -LL-iicchitzz condition does not rely on second-order in- formation and applies to broader class of problems (no need for double differentiability), Therefore, in the remainder of this work, we focus on analyzing the convergence of EG under the a-symmetric (Lo, L Lipschit assumption [Vankov al., 2024] on the operator F, defined below.
Assumption 1.1. F is called a-symmetric (To, L Lipschitt operator if for some Lo, Ln 2 0 and a E 1).
[F(z) - ((x)) < (Lo + L1 maXoe[o.1] F((rr + (1 - -1)))ll)) || vll Vx,y
Rd. (7)
Instead of fixed Lipschitz constant in (4), Assumption 1.1 allows the Lipschitz- like quantity to depend on the norm of the operator itself along the path from to y. This assumption generalizes the standard T-1 E-Lipschitz condition (4), corresponding to the special case where T-g T. and 7,, = 0. Liipshittt condition provides more refined characterisation of Moreover, the a-symmetric (To, L1) operators whose Lipschitz constant depends on their norm, offering tighter bound by balancing Lo < L and L1 < L. Additionally, (7) provides more relaxed bound compared to (5) with a 1.
Classes Root-finding Problems. Apart from the condition (7), we will also assume ad- ditional structure the operator F to prove convergence. We say the operator F is monotone or strongly monotone it satisfies the following assumption.
Assumption 1.2. F is called monotone if
(F(z) F F x v\ 2
Vx, y E Rd
(8)
and strongly monotone if there is some μ > 0 such that
(F(x) Fly) v) 2 م y/ Vr,
Rd
(9)
This captures convex minimization and convex-concate min-max optimization problems special case. Apart from the monotone operators, we are also interested in some non-monotone operators, weak Minty operators [Diakonikolas al., 2021], which satisfy the following assumption.
3

---

Table I: Summary of step size selection for EG under the L-Lipschitz and a-symmetric (Lo, J-Lischhizz assumptions. Our proposed step size strategy is of general form " cot problems involving Q a-symmetric (Lo, -iisschtt operators.
[P [1 tailored for solving
Setup
Assumption
[Mokhturi ul., 2020]
L-Lipsehitz 14
0.25
74
a-symmetric (La, L.) L:)-Lipschitz
Strongly
(Vankov al., 2024]
min
2y/cto [F
Monotone
a-symmetric (La, LiJ-piccchizz (Theorem 3.2)
0.21 La Lu [F(ae]]
76
a-symmetric (Lu L, -Lipschitzz (Theorem 3.4)
(0,
(2 +2 Kg "[a""""""""
76
L-Lipschitz [Gorbunov et al., 2022b]
Monotone (1)
a-symmetrie LL. L. L-Lpschhtttz
(Theorem 3.5)
1
0.45 Ly 2, [F
76
a-symmetric LLg L, L-iischhizz (Theorem 3.7)
(0, 1)
IV2R, (2v2K, 12 "1Ptaa)
76
ippicccitz [Diakonikolas al., 2021]
T- L-Lipschitz [Pethick et al., 2022]
( [P()]]
p+
Weak Minty
o-symmetric (Lg Lipppicccitzz (Theorem 3.8)
Lot [
0.56
?
a-symmetric LL. L.)-Lipschitz (Theorem 3.9)
(0, 1] 2v/K: (av2K) -0-001p "]
Convergence measure strongly monotonc: ||æ x. monotone: minos+s F [[xx)) )ll
weak minty: millSAss | (&x))
For Ko, K1, Kg. check Proposition 3.1. Note that, for L = 0 we have K2 K2 O.
Assumption 1.3, Operator F is called weak Minty if for some 2 0, (F(x), x.) 2 (1)
Vo E Rdd
(10)
1.1 Main Contributions
We summarize the main contributions of our work below.
Tighter analysis for strongly monotone: We establish linear convergence guarantees for strongly monotone (9) a-symmetric (Lu, L problems (see Theorem 3.2, 3.4). In contrast to the results in Vankov et al. [2024] for a 1, our analysis shows that linear convergence can be achieved without incurring exponential dependence on the initial distance to the solution | x. (see Corollary 3.3).
First analysis for monotone and weak Minty: We provide the first convergence analysis EG for solving monotone (8) and weak Minty (10) problems under a-symmetric (Zu, L Lip-hiictiizz assumption. We establish global sublinear convergence for monotone problems (see Theorem 3.5, 3.7) and local sublinear convergence for weak Minty problems (see Theorem 3.8, 3.9).
Novel step size for EG: We propose novel adaptive step size strategy for the EG method designed to handle a-symmetric (Lo, L, -Lipschitzz operators. Specifically, all our step size schemes adopt the general form 7 to [[F(())) = where co, 01 > O are constants determined by the problem- dependent parameters Lo. L1. and a. In Table 1, we included a detailed summary of our proposed step size selection for different classes of operators and compared it with closely related works.
present experiments validating different aspects of our theoretical results. We compare our proposed step size selections with existing alternatives, demonstrating the effectiveness and robustness of our approach.
Numerical experiments: Finally, in Section
2 On the a-Symmetric (Lo, -ip-Lipchhitz Assumption
We divide this section into two parts. In the first subsection, we present an equivalent reformulation of the a-symmetric (Lo, Lippschtt condition (7) in the context of min-max optimization. In

---

the second subsection, we provide some examples of operators that satisfy (7) and highlight its significance.
2.1 Equivalent Formulation of a-Symmetrii (Lo, -iipsshht Assumption
In this subsection, we consider the min-max optimization problem min maX [(wi, w2). The corresponding operator F and Jacobian J are defined as
Vw, L(wi, w2) F(x)= = - -ww wy [(wi, w2)
V V
wi L(wi, w2) wi wy f(wi, W2)
V2
w w(w,,w2)
]
and (z)
(11)
((wi, w2)
W2 w2
where = [w] W Assuming that F a-symmetric (Lo, Li JLipschitz we obtain the following theorem.
Theorem 2.1. Suppose F is the differentiable operator associated with the problem ming; max,, [(w1, w2). Then F satisfies the a-symmetric (Lo, Lii-sshct condition (7) if and only if
[J S Lo + 1 (z))l"
(12)
Here (2x is the Jacobian defined in (11) and |](x)] = max (ar) i.e. maximum singular value of (zr). In particular, we have [I( S L. when operator F is T--Lipschitz
This result provides an equivalent characterization of the a-symmetric (Lo, L-ipschhtitz condi- tion (7) for min-max optimization problems. In practice, it is often easier verify (12) than to directly check (7), In Appendix E, we provide an example where we use Theorem 2.1 to verify an operator satisfics (7).
2.2 Examples of a-Symmetric (Lo, Lii-sissciitzz Operators
To motivate the significance of this relaxed assumption (7), we present a few instances of a-symmetric (Lo, Li)-Lipschitz operators that highlight its advantages over the conventional L-Lipschitz assumption.
Example 1[Gorbunov et al., 2025]: We start with an example from the minimization set- ting. Consider the logistic regression loss function f(x) log (1 + exp (-a x)). Then the Vf satisfies the L-Lipschitz assumption with L ||a] and a-symmetric (Lo, L1 L-iischhtt assumption with Lo 0, Li ||a]], 1. Therefore, when ||a|| >> the bound provided by I-symmetric (Lo, LiL-ppschhizzz can be significantly tighter than the one imposed by the L-Lipschitz condition. This example emphasizes the benefit of the a-symmetric (Lo, L1 Lipschhizz framework in scenarios where standard Lipschitz constants are overly pessimistic.
corresponding gradient operator
Example 2: Consider the operator F(x) = (uf. uz) for æ = (u1, u2) E R2 with x. = (0, 0). Then can show that
[[ F(v)l |I < 2 2 ( |x vll - ma F (0x + (1 0)n) | y/1-
This establishes that F is 1/2-symmetric (0, 2) 2i-Lisschhtz operator. However, this operator F does not satisfy the standard L-Lipschitz assumption for any finite choice of L. We add the related details to Appendix C. Therefore, this example highlights the need for relaxed assumptions on operators beyond standard L--Lipschitz (4).
Example Consider the following min-max optimization problem, for any p > 1,
min,y maXa2 L(wi, w2) = -+ || ||+11 + wi Bwz
p+I || ||,t1
2Tm + |M]], 2 2 Ti
The corresponding operator F(x) defined in (2) is 1-symmetric
Lippschitz
0
B 0
for any choice of > 0 and To
M
Moreover, F is not L-Lipschitz
-B
for any finite L. We have added the proof in Appendix C.
In Appendix C, we also provide additional examples that illustrate cases where the operator associated with general bilinearly coupled min-max optimization problem or an N-player game satisfies the a-symmetric (Lo, L1 Lippchitz condition.
5

---

Convergence Analysis
In this section, we present the convergence guarantees of EG for solving monotone, strongly tone, and weakly Minty operators. For strongly monotone operators, we have linear convergence, while for monotone and weak Minty operators, provide sublinear convergence guarantees. To prove these results, we rely on the similar expression presented in Chen et al. [2023] for the (Ln, L1)- smooth minimization problem. For completeness, include the proof for a-symmetric (La, L1)- Lipschitz operators in the Appendix.
Proposition 3.1. Suppose F is a-symmetric (Lo, Li)--ischiit operator. Then, for
[F(z)) F())ll = (Lo La (=)) (L1||z vlDI[æ vll.
(13)
and for E (0,1) we have
[IF(x)) F(y)ll & (Ko (1))F())]1 K2 y11 -) 1| yll
(14)
where Ko L2 n- 1), K1 L 2n / and K₂ 1/1 2n 30 a))/-a
Proposition 3.1 eliminates the maximum over E [0, in (7) and provides a simpler upper bound on the [=) F()))l We divide the rest of the section into three subsections based on the structure of operators. Moreover, each of these subsections is divided into two parts depending on the value of a, i.e. and (0,
3.1 Convergence Guarantees for Strongly Monotone Operators
In case of strongly monotone operators (9), we achieve linear convergence rates, analogous those obtained under standard L-Lipschitz assumptions [Tseng, 1995, Mokhtari et al., 2020]. For a = 1, operator F satisfies the condition
(13). To guarantee convergence for this class of operators, we use v/(Lo+ L1 (+=x)]) and >> O. Gorbunov et al. [2025] used similar
the EG with step size */A step sizes for the Gradient Descent algorithm solve convex minimization problems.
Theorem 3.2. Suppose F is μ-strongly monotone and 1-symmetric (Lo, 4 Lip-hipshhizz operator. Then EG with step size " = wis Lothi satisfy
k+1
|T441 11 S (1- To (1 + I.1 exp (Tn x. 1))[ - x.
vp
| F. 1|
where v > 0 satisfy 2v v² exp 2v = 0.
The equation 1 1-2 - 1² exp (2v) 0 admits positive solution, approximately 0.363. Specif- ically, to ensure ||* x. 12 S we require K= = K (( + LoLi exp (Li 1==0-==11)) log iterations. When L, O, we recover the best-known results for the strongly monotone L-Lipschitz setting [Tseng, 1995, Mokhtari et al., 2020]. Vankov al. [2024] also studied constrained strongly monotone problems and obtained similar guarantees with an alternative step size scheme.
However, using refined proof technique, we can eliminate the exp(Li I|=o- x= term from the convergence rate and establish tighter bound. One of the intermediate steps of Theorem 3.2 is proving a lower bound on the step size "ik which can be very loose for large k. We now show that after a certain number of iterations K' (51), the operator norm satisfies [[(())) < La/L, for all k > K", which implies
Wk 2 7/21.o for all k K".
Corollary 3.3. Suppose F is u-sttonglyy monotone and 1-symmetric (Lu, L, L1)-LLLLL. Lipschitz operator. Then, EG with step sizes 7h we L.+,, guarantees || x. 11 after at most
2L0 K
|200 12112
1
[2L 1| Ix
log
log
(15)
E
Tern
Term
iterations, where we have Ç == 1/Lo(1+ exp(L, I 1|] xx.1). and 1/ > satisfies 4v 202 exp(2v) = 0.

---

This result shows that to reach an accuracy of >> O, we need (15) iterations. Importantly. Term II in (15) independent of E, and the Term of (15) no longer depends on exp(Li ||00 x, ee.l)) Technically, Term II corresponds to the number of iterations required for the step sizes > and exceed 1/2no. while Term captures the iteration complexity of EG with a fixed step size 1/27.0.
Now, we investigate the behavior of a-symmetric (Lo, Li)-Lipschitz operators for 0 < < 1. In this regime, we adopt step size of the order O [(x))* and prove the following result.
Theorem 3.4. Suppose F is j-Stroongy monotone and a-symmetric (Lo, L1 Lipsshit operator satisfy
with a E (0,1). Then EG with 7kk = Wk 2Ko 2 +21 K2 ")][F(=))]|"
(2
h+1
|,0+1 x.112
200 x.
(2K1 "K; -M ) Ko K2 10000 2.11 27-1120-2211
where V E (0, 1) is a constant such that 1 - 1/ 0.
This result establishes linear convergence. In particular, to ensure || x.112 S E, it suffices to run K O Ko + (K,K2 (aakkKKKllll-222 1"0000 1*7-=) log 2) iterations. Compared the L--Lipschitz setting,
the bound here includes an additional dependence on ||ll x=I |1"/-,, which grows larger as a -
3.2 Convergence Guarantees for Monotone Operators
In this subsection, we focus on the monotone operators (8). Here provide the first analysis for the monotone I-symmetric (Lo, Li)-Liischitz operators.
Theorem 3.5. Suppose F is monotone and 1-symmetric (Lo, Li)-Lipschitz operator. Then EG with step size W/ = Lo [o satisfy
minoSAsK [Fx)) 24 exp 1100- 1xo- 11000
(16)
(<K+1)
where v expv v = 1/V2.
Note that the solution of μexp 1/v2 is approximately 0.45. Hence, this result proves sublinear convergence of EG when F is monotone. Moreover, (16) implies, EG will need K K= - 1 exp (2L, - -0.000)0-==.11 =.."") iterations get [ < E for some
k K. Therefore the convergence rate exponentially depends || xx||| when L1 0. This shows that 1-symmetric (Lu, Lipshhhtt operators potentially require more iterations of EG com- pared to L-Lipschitz operators when initialization To is far from 2.. However, (16) recovers the best known dependence on 20 - x=ll as a special case when L = 0, i.. a standard Lipschitz operator [Gorbunov et al., 2022b].
Theorem 3.5 shows that the EG's convergence rate has an extra term exp (L1 - x= compared to the results of the Lipschitz setting. One of the intermediate steps in this proof involves upper (see (56) in Appendix D). Then the simple approach is to get lower bound on F for all and derive (16). This lower bound on 7 involves the exp (Li 1 =2+ll) term (see (55) in Appendix D) and can be potentially very small. However, is possible to eliminate this exponential dependence using refined proof technique.
bound on Σ k== Tkl [( F 2
K
Theorem 3.6. Suppose F is monotone and 1-symmetric (Lo, Li Lipsschtt operator. Then EG with step size " Wh [(+]] satisfy
minogksk [[()))) PVK+ + 1- /2L, 1 xx.l
/2Lg 1000 x.
21 =1.11
where v expv 1/V2 and K + +1>
Note that obtain this convergence guarantee, a sufficiently large number of iterations is required, specifically K + > (247)]=0 -2.19)/p². Gorbunov al. [2025] employed similar proof technique
7

---

to eliminate the exponential dependence on the initial distance exp(L1]1zg z,Il) in the context of the Adaptive Gradient method.
Next we state our result for a-symmetric (Lo, -ippsshtt monotone operator with a E 1).
Theorem 3.7. Suppose F is monotone and a-symmetric (Lo. L1 ) -ipsschitz operator with a e (0, 1). Then EG with wk 2/2Kkt (2V2K) +2
2 2 (=())))) satisfy
minosAsk [((x))] 16 Ko // ")(oot K la-- aa-aya l x. 11)) 1
R+1
This theorem establishes a sublinear convergence rate for a E (0, 1). In the special case where Li 0 (i.e., the standard L-Lipschitz setting), have K₁ K2 by Proposition 3.1. Thus, our result recovers the best-known rate O (-
/K+1) (46/1)0=..1///x)) from Gorbunov et al. [2022b]. On the other
/K+1) Furthermore, as a O-which corresponds again to the L-Lipschitz setting our step sizes "Is and wh. become constant, and we recover the standard convergence rate O result for monotone L--Lipschitz operators up to constants, emphasizing the tightness of our analysis.
hand, when L > 0, we obtain a convergence rate of O |
This matches the classical
3.3 Local Convergence Guarantees for Weak Minty Operators
Beyond the monotone operators, it is also possible to provide convergence for weak Minty opera- tors (10) under some restrictions p 0. In contrast to the monotone problems where used the same extrapolation and update step 7Kk Wk, here we use smaller update step size wy. Specifically, employ wi n2/2, similar to Diakonikolas al. [2021] for handling weak Minty L--Lipschitz operators.
Theorem 3.8. Suppose F weak Minty and I-symmetric (Lo, Lip-schtt assumption. More- over we assume
D
Lo Lo limo lle (ra-s=l) 4p 0.
(17)
Then EG with step size 7 T [ and wi 7x/2 satisfies
4Lo (1 + L exp (L, 120 x.ll) I|20 - x.ll) ||ao x.
min 0gkgk
[[((+))
(18)
vλ, + 1)
where v expv = 1.
To the best of our knowledge, this is the first result establishing convergence guarantees for weak Minty, a-symmetric (Lo, - operators. Similar to the monotone case, we obtain sublinear convergence rate for weak Minty operators. However, the condition in (17) indicates that the initialization point zo must be sufficiently close the solution r. in order to ensure convergence. Consequently, Theorem 3.8 only provides a local convergence guarantee.
In the special case where In 0, i.e., the standard I.-L.pschitz setting, condition (17) reduces to 4/4Ta- Similar assumptions on have been made in prior works such as Diakonikolas al. [2021] and Pethick et al. [2022] for the T.-Lipschitz weak Minty setting. Finally, we extend our analysis to the case a E (0, 1). and present corresponding theorem establishing sublinear convergence under analogous restrictions on p.
the simpler requirement
Theorem 3.9. Suppose F is weak Minty and a-symmetric (Lo, Lipsshhttttzz operator with a E (0, 1). Moreover we assume
10 4p >
(19)
- ")
Then EG with step size 7 2/2Ko+ (20ko+(22336) (2 +2 -1/2 " [(
and We 74/2 satisfy
1 (KK+ (kot(K+22) 3/3 -) ")
(oo -/1-0 1.0- 12.0-
minosksk 12 [
A. (K+1)

---

Numerical Experiments
In this section, conduct experiments validate the efficiency of proposed step size strategy Tkk cu+ [[]g]]] with a = 1. In the first experiment, we compare our step size choice with that of Vankov et al. [2024] on a strongly monotone problem, and in the second experiment, we make comparison with the constant step size strategy solving a monotone problem. Finally, we evaluate our scheme for solving the GlobalForsaken problem from Pethick et al. [2022]. All experiments in this work were conducted using a personal MacBook with an Apple M3 chip and 16GB RAM. provide the code for all of our experiments http::/giihub..om/isaaaaaaa I
10
0.012
Relative Error
Stepsize
0.028
10-1
0.025
EG [Vankov et al. 2024]
EG [This work]
10
0.024
0.022
[Vankovv 2024]
[This work]
10
0.016
25
50
75
10c
125
15c
200
25
50
100
125
150
175
Iteration
lteration
(a)
(b)
Figure 3: In Figures 3a and 3b, compare proposed adaptive step size strategy with that of Vankov al. [2024]. We report the relative and the magnitude of the step size iterations.
L-100000
LO-10, L1-0.1
LO-10, L1-0.1
L1=1
L0=10, L1=1
LG-10, 11-10
LO-10, L1-10
Relative Error
L0=100;
Step Size
L0=100. L1=0..
LG=100, L1-1
L0=100, L1=1
L0=100, L1=10
L0=100, L1=10
L0-1000, L1-0.1
L0-1000, L1-0.1
L0=1000,
L0=1000,
LG- 000. L1=10
L0-1000. 11=10
Iteration
Iteration
(a)
(b)
Figure 4: In Figures 4a and 4b, we evaluate the performance of the EG method on the problem in (20), using both constant step size and the (To, I.1) -adaptiive step size. We report the relative error and the magnitude of the step size iterations.
Performance on Strongly Monotone Problem. In this experiment, compare theoretical step sizes with those from Vankov et al. [2024]. Here, we implement EG for solving the operator
F(x) (sign (u,) |uz| + u2, sign (u2) [2g w1). This problem has constants Lg = + 2 and L = 2/2.. For our method, we use 7 = Wk To F(ax]] while for EG [Vankov et al., 2024]
stepsize 7 wi min 4 2V2eLo 1 In Figure 3a, we plot the relative
| error I2 12. on the y-axis while number of iterations on the --axis. We find that our proposed step size outperforms that of Vankov et [2024]. Moreover, Figure 3b, we compare the magnitude of the step size and how it evolves over the iterations. We find that the step size of Vankov et al. [2024] remains constant approximately 0.02, whereas our proposed step size increases to value larger than 0.032. These experiments highlight the efficiency of our proposed step size.

---

Performance on a Monotone Problem. Here we consider the following min-max optimization problem
min ERd maX L(w1, w2) = [w Aws) w Bwy 3/ (w)) Cw2) "
(20)
where A, B. C E Rdxd are positive definite matrices. Note that, when d = 1. and A, B, C are just scalars equal to this problem reduces (6). The corresponding operator of this problem given by
V V un L(w1, W2) ((wi, (am = [w] Awi) 1/2 Aw
+ Bu2
F(x)= =
(w2 Cw2) 1/2 Cw B w1
Furthermore, show that L is convex-concave and has an equilibrium only w1, 102 0 Rd (check Appendix F). To solve (20), we implement the EG method using two types of step size strate- gies: (1) constant step size 7A wy =/c,, and (2) adaptive step size 78 wi 1/co-ca [=x) For the constant step size EG, we perform a grid search over с E {10?, {10",10", 10
10 10 10²) We find that 10t yields the best performance: larger values lead slower convergence. while smaller values cause divergence. Figures 4a and 4b present the relative error and step size for the case 10 For our adaptive EG method, perform a grid search over co {10, 100, 1000) and C1 E (0.1, 10), evaluating all possible combinations. The performance of all adaptive variants is plotted in Figures 4a and 4b. We observe that most combinations outperform the constant step size EG. with (co,c)) = (10, 10) achieving the best results (see Figure 4a).
Interestingly, while the adaptive EG starts with smaller step sizes compared to the constant step size EG, its step sizes increase over time and eventually surpass those the constant step size approach (see Figure 4b). This highlights the practical effectiveness of our proposed method in handling non-Lipschitz operators such as the one (20).
Performance on Weak Minty Problem. Here we consider the unconstrained GlobalForsaken problem from Pethick al. [2022] given by
min max [(wi, W2) == wi + (b((1))) (((2),, ER W2ER
(21)
where (w)) = 2n 21 + 3. As shown in Pethick et al. [2022], the saddle-point problem in (21)
admits global Nash equilibrium with parameter Re 0.119732. We implement Adap-
(W1,w2) = (0, 0) and satisfies the weak Minty condition (10)
tiveEG+, EG+ and EG with our step size strategy to solve this problem. For each algorithm, size tuning on a a grid of {10 10 ...). We observe that both AdaptiveEG+ and EG+ perform best with a fixed step size of > = 0.1. For our method, we set the step size parameters (co, e1) (1, 1). In Fig- ure 5, we present the trajectory plots of these algorithms, all initialized at (W1, W2) (1, 1). Our findings indicate that all algorithms eventually converge to the equilibrium (0, 0), but the convergence of method is significantly faster. This demonstrates the advantage of our step size strategy in solving challenging problems that satisfy only weak Minty conditions.
3.3
perform step
-0.
EG-IDalonketas 30231
AdaptiveE ct
-1.
Equiitr sum. Stort
-1.0
6.5
0.0
0.5
W3
Figure 5: Trajectories of algorithms for solv- ing problem (21).
Conclusion
This work extends the analysis of the EG method to broader class of a-symmetric (Lo- L1)- Lipschitz operators. We establish new convergence guarantees for strongly monotone, monotone, and weak Minty settings, supported by novel adaptive step size rule.
limitation of our current analysis that it focuses solely on root- not-finding problems and does not handle the constrained setup. However, the results included in this work advance the theoretical understanding EG and open several promising directions, including extensions to constrained and stochastic settings, well as the analysis of optimistic gradient methods under this relaxed assumption. Furthermore, another important research direction is the estimation of the unknown constants Lo. L1. which would pave the way for fully adaptive algorithms.
10

---

References
K. Ahn, X. Cheng, M. Song. C. Yun, A. Jadbabaie, and S. Sra. Linear attention is (maybe) all you need (to understand transformer optimization). ICLR, 2024.
K. Antonakopoulos, F. V. Belmega, and P. Mertikopoulos. Adaptive extra-gradient methods for min-max optimization and games. ICI.R, 2021.
D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel. The mechanics of n-player differentiable games. In ICML, 2018.
H. H. Bauschke, J. Bolte, and M. Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 2017.
A. Bezmosikov, Dvurechenskii, Koloskova, Samokhin, S. Stich, and A. Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. NeurlPS, 2022.
A. Beznosikov, E. Gorbunov, H. Berard, Loizou. Stochastic gradient descent- ascent: Unified theory and new efficient methods. In AISTATS, 2023.
A. Böhm. Solving nomconvex-nonccoccae min-max problems exhibiting weak minty solutions. TMLR, 2023.
N. Brown, A. Bakhtin, A. Lerer, and Q. Gong. Combining deep reinforcement learning and search for imperfect- information games. NewrlPS, 2020.
A. Chambolle and T. Pock. On the ergodic convergence rates of a first-order primal dual algorithm. Mathematical Programmming, 2016.
Z. Chen, Y. Zhou, Y. Liang. and Z. Lu. Generalized-smooohh nonconvex optimization is as efficient as smooth nonconvex optimization. In ICML, 2023.
Choudhury, Gorbunov, and N. Loizou. Single-call stochastic extragradient methods structured non- monotone variational inequalities: Improved analysis under weaker conditions. NewrIPS, 2024.
C. Daskalakis, Nyas, Syrgkanis, arXiv:1111.00141, 2017.
Zeng. Training gans with optimism. arXiv preprint
J. Diakonikolas. Halpern iteration for near-optimal and parameter-fre monotone inclusion and strong solutions to variational incqualitics. In COLT, 2020.
J. Diakonikolas, C. Daskalakis, and M. I. Jordan. Efficient methods for structured nonconvex-nonncocave min-max optimization. AISTATS, 2021.
Y. Fan, Y. Li, and B. Chen. Weaker mvi condition: Extragradient methods with multi-step step exploration. In ICLR, 2023.
C. Fox, A. Mishkin, S. Vaswani, and M. Schmidt. Glocal smoothness: Line search can really help! arXiv preprint arXiv:2506. 12648, 2025.
G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A variational inequality perspective on generative adversarial networks. ICLR, 2019.
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial networks. Communications of the ACM, 2020.
E. Gorbunov, H. Berard, G. Gidel, and N. Loizou. Stochastic extragradient: General analysis and improved rates. In AISTATS, 2022a.
E, Gorbunov, N. Loizou, and G. Gidel. Extragradicnt method: (1/k) last-iterate convergence for monotone variational incqualities and connections with cocoercivity. In AISTATS, 2022b.
Gorbunov, M. Danilova, I. Shibaev, P. Dvurechensky, and A. Gasnikov. High probability complexity bounds for non-smooth stochastic optimization with heavy tailed noise. JOTA, 2024.
Gorbunov, N. Tupitsa, S. Choudhury, A. Aliev, Richtárik, S. Horváth, and M. Takáč. Methods for convex ()smooh optimization: Clipping, acceleration, and adaptivity. ICLR, 2025.
S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 1997.
Y.G. Hsieh, F. lutzeler. J. Malick, and P. Mertikopoulos. On the convergence of single-call stochastic extra- gradient methods. NewrIPS, 2019.

---

G. Korpelevich. Extragradient method for finding saddle points and other problems. Matekon, 1977.
S. Lee and D. Kim. Fast extra gradient methods for smooth structured non.oocave minimax problems. NewrlPS, 2021.
J. Y. Ya, N. Loizou, G. Gidel, Y. Ma, N. Le Roux, and M. Jordan. On the convergence of stochastic extragradient for bilinear games using restarted iteration averaging. In AISTA7S, 2022.
N. Loizou, H. Berard, A. Jolicoeu-Maartneauu P. Vincent, S. Lacoste-Julien, and I. Mitliagkas. Stochastic hamiltonian gradient methods for smooth games. In JCML,
N. Loizou, H. Berard, G. Gidel, I. Mitliagkas, and S. Lacoste-Julien Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. NeurIPS, 2021.
Luo and M. O'Neill. Adaptive extragradient methods for root-finding problems under relaxed assumptions. In AISTATS, 2025.
Luo and Q. Tran-Dinh. Extragradient-tye methods momoonote root- noot-finding problems. UNC-STOR Technical Report, 2022.
K. Mishchenko, Kovalev, E. Shulgin, Richtárik, and Y. Malitsky. Revisiting stochastic extragradient. In AISTATS, 2020.
A. Mokhtari, A. Ozdaglar, and S. Pattathil. A unified analysis of extra extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In AISTATS, 2020.
H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. NeurIPS, 2016.
T. Pethick, P. Latafat, P. Patrinos, O. Fercoq, and V. Cevher. Escaping limit cycles: Global convergence for constrained -enconeeee-noccoccvve minimax problems. ICLR. 2022.
L. D. Popov. A modification of the arow-hurwice method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 1980.
A. Riabinin, E. Shulgin, K. Gruntkowska, and P. Richtárik. Gluon: Making muon & scion great again!(bridging thcory and practice of Imo-based optimizers for 1lms), arXiv preprint vrXiv:2505.1341 2025.
E. K. Ryu and W. Yin. Large-scale convex optimization: algorithms & analyses via monotone operators. Cambridge University Press, 2022.
S. Sokota, R. D'Orazio, J. Z. Kolter, N. Loizou, M. Lanctot, I. Mitliagkas, N. Brown, and C. Kroer. A unified approach reinforcement leamning quantal response equilibria, and two-player zero-sum games. In ICLR, 2023.
Q. Tran- Fran, Variance-reduced reelerddefflecee--ee backward splitting methods nonmonotone generalized equations. ICMI,, 2024.
Tseng. linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 1995.
D. Vankow, A. Nedich, and I.. Sankar. Generalized smooth variational inequalities: Methods with adaptive stepsizes. In JCML, 2024.
D. Vankov, A. Rodomanov, A. Nedich, L. Sankar, and S. U. Stich. Optimizing (L_,,_1) (1)--mootttt functions by gradient methods. ICLR, 2025.
A. Vaswani, N. Shazeer. N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and Polosukhin. Attention is all you need. NewrIPS, 2017.
W. Xian, Z. Chen, and H. Huang. Delving into the convergence of generalized smooth minimax optimization. In ICML, 2024.
T. Yoon and E. K. Ryu. Accelcrated algorithms for smooth convex-concave minimax problems with rate on squared gradient norm. ICML, 2021.
T. Yoon. S. Choudhury, and N. Loizou. Multiplayer federated learning: Reaching equilibrium with less communication. NewrIPS, 2025.
12

---

B. Zhang, J. Jin. C. Fang, and L. Wang. Improved analysis of clipping algorithms for non-convex optimization. NeurIPS, 2020a.
J. Zhang. T. He, S. Sra, and A. Jadbahaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR, 2020b.
S. Zhang, S. Choudhury, S. U. Stich, and N. Loizou. Communication-effiiin gradient descent-accent methods for distributed variational inequalities: Unified analysis and local updates. In ICLR, 2024.
T. 7heng, N. Loizou, P. You, and E. Mallada. Dissipative gradient descent ascent method: A control theory inspired algorithm for min max optimization. IEEE Control Systems Letters, 2024.
13

---

NeurIPS Paper Checklist
1. Claims
Question: the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Section 3 and 4.
Guidelines:
The answer NA means that abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match thcorctical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: see Section 3.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper limitations, but those are not discussed the paper.
The authors encouraged create separate "Limitations" scction their paper.
The paper should point out any strong assumptions and how robust the results these assumptions (e.g.. independence assumptions, noiseless settings, model well well-specificnn specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
violations of
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should he articulated.
The authors should reflect the factors that inffuence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their hest judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: see Section and 3.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
14

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proofs provided in appendix or supplemental material.
Theorems and Lemmas the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: see Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g.. a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct
dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the of cosed-source models, it may be that access to the model is limited some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open faithfully reproduce the main experimental results, described supplemental material?
the data and code, with sufficient instructions
Answer: [Yes]
Justification: see Section 4.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines
muides/CodeSuuen ssionPolccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot rejected simply for not including code, unless this is central to the contribution (e.g.. for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: :/ //np///p...//////// cc/public/ nu..des//odeeuuumiissooooooo for more details.
15

---

The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) recommended, but including URLs to data and code is permitted.
6. Experimental sefting/details
Question: Does the paper specify all the training and test details (c.g,, data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: see Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate informa- tion about the statistical significance of the experiments?
Answer: [NA]
Justification: all experiments are deterministic.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should given (e-g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error than state that they not verified.
if the hypothesis of Normality of errors
asymmetric distributions, authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). crror bars are reported tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, docs the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: see Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
16

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform. every respect, with NeurIPS Code Ethics https:://eeuee
cc/ cc/public/Ethi ceGuidelinen
Answer: [Yes]
Justification: the paper follows NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: the paper is mostly thcoretical and docs not have direct socictal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations. (e.g.. deploy- of technologies that could make decisions that unfairly impact specific groups), privacy considcrations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it not needed point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated relcase of models, providing defenses in addition to attacks, mechanisms for monitor- ing misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible relcase of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: we do not release data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors take this into account and make best faith effort.
17

---

12. Licenses for existing assets
Question: Are creators or original owners assets (e.g., code, data, models), used the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected"'
Answer: [Yes]
Justification: see Section 4.
Guidelines:
The answer NA means that the paper does not use existing assets.
authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the
is used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged reach out asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training. license, limitations.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as as details about compensation (if any)?
Answer: [NA]
Justification: not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection. curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: not applicable.
Guidelines:
18

---

The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
recognize that procedures this may vary significantly between institutions and Iocations, and we expect authors adhere to the NeurIPS Code of Ethics the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review,
Declaration LLM usage
Does the paper describe the usage of LLMs if it important, original, or non-standard component of the core methods in this rescarch? Note that if the LLM is used only for writing, editing, or formatting purposes and does impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were not used.
Guidelines:
answer NA means that core method development this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https pettts://neurdii http::pp...../ttteeeee/e//////// for what should or should not be described.
19

---

Supplementary Material
The supplementary material organized as follows. In Section A, we discuss papers that are closely related to our work. Section B presents several technical lemmas used in our theoretical analysis. Section C provides illustrative examples of e-symmetric (Lo, L1) -iipsciii operators, while Section D contains the detailed proofs of the main convergence theorems presented in the paper. Next, in Section the a-symmetric (La, L1)-Lipschitz condition. Finally, Section offers additional details on the experimental setup and results.
discuss an equivalent formulation of
Contents
1 Introduction
1.1 Main Contributions
2 On the a--Symeerric (Lo, L1 Liipschitz Assumption
4
2.1 Equivalent Formulation of a-Symmetric (Lo, - Assumption
5
2.2 Examples of a-Symmetric (Lo, L1 L-ipschitz Operators
5
3 Convergence Analysis
6
3.1 Convergence Guarantees for Strongly Monotone Operators
6
3.2 Convergence Guarantees for Monotone Operators
7
3.3 Local Convergence Guarantees for Weak Minty Operators
8
4 Numerical Experiments
5 Conclusion
10
A Further Related Work
22
B Technical Lemmas
23
C Further Examples of a-Symmetric (Lo, Li)-Liscchttz Operators
25
Convergence Analysis
30
D.1 Proof of Proposition 3.1
30
D.2 Convergence Guarantees for Strongly Monotone Operators
31
D.2.1 Proof of Theorem 3.2
31
D.2.2 Proof of Corollary 3.3
32
D.2.3
Proof of Theorem 3.4
33
D.3
Convergence Guarantees for Monotone Operators
35
D.3.1
Proof of Theorem 3.5
35
D.3.2 Proof of Theorem 3.6
36
D.3.3
Proof of Theorem 3.7
36
D.4 Local Convergence Guarantees for Weak Minty Operator
38
D.4.1 Proof of Theorem 3.8
38
D.4.2 Proof of Theorem 3.9
39
Equivalent Formulation of a-Symmetric (Lo, L1 -Lpscchizz Assumption
41
20

---

E.1
Proof of Theorem 2.1
41
E.2 Computation of at Lo, L1 for (ww, wa).
42
Additional Details on Numerical Experiments
43
21

---

A Further Related Work
Relaxing Lipschitzness. The (Lo, L1 --moothnnesss assumption was first introduced by Zhang et al. [2020b] and further developed in Zhang al. [2020a]. Chen et al. [2023]. More recently, improved convergence guarantees for optimization under this relaxed smoothness were obtained by Gorbunov et al. [2025], Vankov et al. [2025]. This assumption has also been used in the analysis modern large-scale optimization algorithms, for example, Gluon for LLM training [Riabinin et al., 2025].
Beyond (Lo. L1 L -smoothness, several alternative notions or relaxations of smoothness have been proposed in the literature, including relative smoothness [Bauschke et al., 2017], glocal smoothness [Fox et al., 2025], and Hölder smoothness [Gorbunov al., 2024], among others. The (Lo. L1 --mmotthness framework has recently [2024], while Xian et al. [2024] analyzed
been extended to the variational inequality setting by Vankov min max problems under a similarly general smoothness perspective. A recent line work by Loizou et al. [2021]. Gorbunov et al. [2022b], Beznosikov et al. [2023] studies star coc-cocceee operators, which could hold even when the operator is not Lipschitz.
On Methods for Solving VTs. A variety of methods have been developed to solve root-finding problems and, generally, variational incqualities. The most basic approach is the gradient method and its stochastic counterpart [Loozzou et al., 2021, Beznosikov et al., 2023]. More variants the gradient method have been proposed in different settings. like the dissipative gradient method [Zheng et al., 2024] and distributed methods for VIs [Zhang et al.. 2024]. However the gradient method fails to converge in simple monotone problems [Gidel al., 2019].To obtain convergence guarantees in more relaxed settings (including monotone problems), Korpele- vich [1977] introduced the EG method, which has since been extended adaptive |Antonakopoulos al., 2021 11, stochastic [Gorbunov et al., 2022a, Gidel et al., 2019, Mishchenko et al., 2020, Diakonikolas et al., 2021, Li ct al., 2022], and decentralized variants [Beznosikov ct al., 2022], A key drawback of EG is that it requires two oracle calls per iteration. To address this, Popov [1980] proposed the Optimistic Gradient (OG) method, which uses only a single oracle call. Similar to EG, OG has been analyzed in stochastic settings [Hsich al., 2019, Gidel al., 2019, Daskalakis et al., 2017, Choudhury al., 2024, Böhm, 2023]. Beyond these methods, accelerated variants have also been developed, achieving faster convergence rates [Yoon and Ryu, 2021, Diakonikolas, 2020, Lee and Kim, 2021].
22

---

B Technical Lemmas
In this section, we present some technical lemmas, which will be used to prove the main results of the work in subsequent sections.
Lemma B.I. For a, E R". we have
2 (a, b) ||a|1² + +|1811 1|a b11
(22)
Lemma B.2. For a, E R. we have
-||a|1 1 - -211a + b1l2 + 11611
(23)
Lemma B.3. For positive numbers 6 have
c+bs v2
(24)
Proof. From AM-GM inequality on o, b 0 have
2ab < a² + b²
Adding a² + b² on both sides we have
(a + 6)2 s 2(a² + b²). Then the result follows by taking square root on both sides.
Lemma B.4 (Cauchy-Schhe Schwwry Inequality). For vectors a, b R., we have
(a, b) < ||]|||b|_
(25)
Lemma B.5. Chen et al. [2023] Operator F is a-symmetric (Lo, L1 Lipscchit if and only
[F((x) - F(v)lI < Lo + L1 J"" [|F(0z + (1 - -)v))l de || vll
Ya, E Rd.
(26)
Lemma B.6. For 2 symmetric matrix, the maximum eigenvalue is given by
[a b b
(a + d) + V(a d)2 40
Amaix
(27)
d
2
where b, E IR.
Proof. Let A be symmetric 2 2 matrix given by
b
A b d
where b, d R. Since symmetric, has real eigenvalues. The eigenvalues are the roots its characteristic polynomial:
det(A A1) = det (1r=^>
b d d- - (a- A)
Expanding determinant, we obtain the characteristic equation:
X² (a + d)A + (ad - b3) = 0.
This is quadratic equation in X, and its solutions are:
(a d) + / (a - d)2 + 403
2
Thus, the maximum eigenvalue the larger of the two roots:
Amax (a d) d)² 48
This completes proof.
23

---

Lemma B.7. For the quadratic problem min,, maX L(wi, w2) 2 wi wi w2 2 w.. the Jacobian (a) is given by
((x) |
1
1
In this we get [[]())]]| 7max (J(x)) v2.
Proof. Note that
2 0 21.
J [ J(z) =
which has maximum eigenvalue v2. Hence, [x]]] a (J()) v Amax (J(x) J(x)) v2.
Lemma B.8 (Vankov et [2025] Example 2.2). The function f(x) p+1 | where p >
is
(To, Ti -rmmohhhhh with arbitary and
i.c.
2-1
v f(x)] <
Vf(c))I
(28)
for any TI >> 0.
Lemma B.9 (Equivalence of Ly Norm), For any vector i RR, and 0 q, we have
|| S | S d ||
(29)
In particular, for any a, E IR and < r < we have
(a" + b²)² $ (a" + b²}
(30)
and
(a" + b 2 (a + b
(31)
Proef.
The proof of (29) follows from Holder's Inequality. (30) and (31) follows from (29) with d and b).
24

---

C Further Examples of a-Symmetric Li)-L-hhtis Operators
In this section, we provide further examples of operators that satisfy the a-symmetric (Lo, Li J-Lischhitzz assumption. We first start with the details of Examples 2 and from Section 2.2, then provide three more examples for the min-mat max optimization problem and N- -lpaayer game that satisfy the assumption.
Example 2: Here we consider the operator F(x) = [ui, x²) for x = (2), u2). Then for (21, U2), we have
[1((x) F())
[1(u] - vî, u2 v²)
((uî ui)² 2 + (uă v²) ?) 1/2
((wı )² (u1 + 1z)² + (w2 02) (uz o2)²)² 2)122
((w) 01)* + (mz - v2)²) ((ur + 01)² + (uz + v2) 1/4
((w1 21)² (w2 02)²) 1/2 ((u1 + v1)* + +(2 v2) 1/1
((w1 e1
+ (m2 m2)")) || wl
1/4
2
21
+
|| - vll
2
2
2
11
2/2
2
1/2
|| vl
2
2
+ y
1/2
2 F
||
yl
2
2 max eE(0.1]
|| (Ox (1 0) /2
vll
Here, the first inequality follows from the Cauchy-Schward inequality. This completes the proof of 1 4-ymmeetric-
(0, 2) Lipschitz property of F. Now, consider the vectors x = ol2 and y 12 where 1 (1, 1). Then we have
Fx)) F(VIl
-a - 1)2 + (a² 1)²
x
Vla 1)2 + (a 1)²
2(22 113
22 1)2
(a () + 1)2
(a 1)2
1/.
Therefore,
[x(x) F(y)l
lim
lim la
x
vll
00
This proves that F is not Lipschitz.
25

---

Example 3. Consider the min-max optimization problem
min max [(w), p |
||at|
Buz
(32)
w2
p
2v2 ||
Then the corresponding operator F defined in (2) is 1-symmetric
2To
Lipschitz with any
B
arbitary 9ι and To
p-1
where M
Moreover, P' is not Lipschitz for any finite
B
0
Proef. For the simplicity of the proof, we define the function f(w) == PFT |w The following properties of this function will used to prove our result.
1. Gradient of [w): The gradient of f(w) p+I |||l== (lee)1)) 2 is given by
1 p+
|| 12) + v ([[wl1²) 2 (11w113)
" 2w [elll w.
v (w)
(33)
p+1 2
Here, the first equality follows from chain rule.
f (mo, ni >-mooohh: From Lemma B.8, we know f (7o, m)) -msoohh.. Choose arbitary ni > 0. then from Lemma B.8, f satisfies
f(w)) S + ++
(34)
where To
p-11
Now, we will get back to original min-max prohlem. Note that, using the definition of f(w), we can rewrite the objective function in (32) as
[(w1, w22 = f(w1) w. Bwy fww2)-
(35)
Then the operator F corresponding to the min-max problem (32) is given by
W C(wi, w2) ((wi,w)) F(x) = V wy (wi, w2)
V + Bw
69
w1 + B
(36)
f((w)) B
w1
||22|
p
W22
B
w2
Moreover, the Jacobian matrix corresponding to this min-max problem (32) is
V L(w1, W22
V "umm L(wi, w2))
f((m)
B f(2(2))
(x)
(37)
V wo ((wi, w2)
Wawng (wwi, w2)
B
Furthermore, note that, we can hreak the operator F from (36) as F(r)
(x) + Mr with
V ((())
(x) = vf(wa)
(38)
W22
M
Then the Jacobian J(z) of this min-max problem satisfies
B
[=)]l
67
V (wi)
B
B
V
f[w2))
(w)(w)
0
+ M
4 [(wa)
(2((w)
+ ||
AV II I VN I
max (|V2 (1) || f(w))l] [|2
||
[[==)) [M]]
TO + + [M]
2m [ - (1/
(2nu + [M]] + - /
(2th + [M]) + 1 (x))
(39)
where > 0 is arbitary and nu = ( Above, the second inequality follows from the fact that the maximum eigenvalue of a block diagonal matrix is less than equal the maximum eigenvalues of it's diagonal
26

---

matrices. Now, we want to find bound on || (x)] in terms of [x]]) Towards that end, we will first find the relation between (x)) and (F()), Note that
() = (H())))) + (Mæ, x)
Bwz
wi wa
= (H()) +
B w1
(z)
[[]lu] ||0 11-1 wi
[|]]w]] |- W2
=
|
||
|
p+1
(40)
and
|[()]]
(1))
||wa||"
u22
(11w> 1|"
wi 112 (11e0211 (110=11==1)) |10021
(1lw) 1 + ||wwel (p))
(41)
Then note that
[x)]]
(|w1 + ||w=||1 3p))
(1|w)]13 + ||02|| (, #
(0)
(|w1)|/** + |ala|l Iottll ste
(|wm]|
x)
[F(x)]]
नी |
(110a11² ||1021 +
|F(x)||
I|w (212 # #
|+())||
2 :o (1lmn112r
(1 2" +1 # Zt4
_
|F()
[F(2)]]
(1
+ 1|
49
)+)))))
Therefore, dividing both sides by [[H ptI we get
|| $ [()))
Thus raising both sides to the power get
11 < उサ [F(())]
[H()]|
(42)
Combining this bound on [x)]] with (39) we get
[x)
IA
(2ro + [|M]] + 2 [+))]
2
(2r0 + |M]] + 2 20 (()l())]]
(2ro + [M]]] +2 برسي [()
Thus, the result follows using Theorem 2.1.
27

---

Next show F is not Lipschitz. Consider, (twi, 0) and (0,0) with || = 1. Then we get
F((x) F(y)ll
ta p²
|
vl
+ p+1
As we take oo, we get [I P(vIll F is not L-Lipschitz.
co. Hence, there doesn't exist any finite bound on
(()))
|=-y1
[|e-vll
Example 4: Consider the min-max problem
min max L(W1, w2) p+ || ||
|10211
p+
Then the corresponding operator F defined (2) is 1-symmetric (Lo, Li >-Lipschitz where L1 = v and Lo p-1 for any 7i > Moreover,
L-Lipschitz for any finite
p+1 ||w]| p+1, From Lemma B.8, know i' (ro, ( -moothh. Choose arbitary m then from Lemma B.8, satisfies
Proof. Define f(w)
f(w)] To fw))l
(43)
where p-1 p-1
Then we have L(wi, w2) = (wi) f(w2) and the corresponding operator and
Jacobian are given by
f((w)) Vf(w>)
and J(z) = 2 f(1)
F(x)=
V2 f(2(
respectively, Note that the Jacobian matrix J(x) is block diagonal. Hence, the maximum eigenvalue of J(x) less than the maxiumum cigenvalue of both f²((w)) and V² f(w2)) Therefore,we get
[x)]l
= 14 IA V
max [I1
To 3
2no +o (1//\v\)) [[))]]
(4) x
27 + V2n,
27o + (=))ll
p-1 p-1
Then F is 1-symmetric (Lo, -Lipschtt from Theorem 2.1 with L = 2 and Lo 2ng =
for > 0.
Next show F is not Lipschitz. Consider, (Iw), 0) and (0,0) with || = 1. Then we get
F(()) F(y)ll
-=-1
t
1 vl1
++1 p+1
As we take 0o, we get [F()) oo. Hence, there doesn't exist any finite bound on [[())))(()]] Therefore, F is not L-Lipschitz.
||=-v|l
|z-v1
Example 5: Min-max optimization problems he studied using operators. Here we consider one such example, the bilinearly coupled min-max optimization Chambollc and Pock [2016] problem
min max C(w1, w2) == f(w11 + mi Bwz g(w2)
for matrix B E Rdxd and functions f.g Bd R. The associated operator for this problem is given by F(x) (xx) Mr where
V (((w)) V
0
B
H(x)
and M
B
0
If f. are individually (Lv, L1) smooth Zhang et al. [2020b], we show that
[[[(x) - F(y)ll 5
(2Lo + 21 [M| (2L,1[F(>11)
I|x vll-
28

---

Thus, F is 1-symmetric (2Lo + (1 2L, RM| v2L,) Lipschitz. Consider the min-max problem
min max || wwlllR
[(wi, 102) == (um) wi Buz g(v2).
where f,g are (Lo, Li) smooth. Then for (wi, w2) have
F(x) =
(V((i) (g(w2)
+
0 B
D
B) wi (wz)
H(x) + Mr
where M is matrix and an operator. Now note that for (wi, w2) and y = (V1, 12)) we get
V f((1) - f((1)) Vg(w2) (
[x))) Hv)l
(IIV/(w)) - V ( 1/2
((Lo + [= ||01 v1ll + (Lo + L1 (g( 1|w2 -2]l3)
((4o + (4, + /1 1/4 (I] - =ill + ||w2 - 2/2 11 4/4
1/2 (Iww -=ll" ||w2 - 22 11²) 1/2
(4L3 + 21} (117/\1=a)(+++=s((((0))1 1/2 (1 v1l || ezll?) 1/2
(4T3 + 21, [+) || vll
(2l v2L Hz), || v/1
Therefore, using the above inequality, we derive
[I((x) F(v)ll
[H(x) Hv)ll |Mr Myll
-
2L + V2L [+())]] | - ul + |M]]|= all
(2Lo |M| + V2L, V2L: (((() || |-==wll wll
Now using [+((=]] = [[{{())
Mæ M & |[(i)]| [ | S [[()=)]++++++++0++ /2R||M] we get
[F(x) - F(y)l <
2T (1 2) M | /2L= ||
vll-
Example 6: In this example, we consider an N-player game Balduzzi et al. [2018], Loizou et al. [2021]. Yoon al. [2025], where each player [N] selects an action E IR,, and the joint action vector of all players is denoted as x = (W1, Way ... wyy) E +u+++ Each player i aims to minimize their loss function f, for their action w,. The objective is to find an equilibrium x. = (Wi,, W2.: WN.) such that
Wh- = argmin fi (1s, 2-)
Here we abuse the notation to denote w = (Wi,-'. Wi- W441, WN) and f.W,, w-.) f. W.). When the functions fa are convex, this equilibrium corresponds to solving F(x.) = 0. where the operator F is defined as
F(x) = (v), V2fa(x), vnfn(*)).
In case each of these partial gradients V.S: are (Lo, - ie. (z) v.f((v)ll s (Lo (Vo vll
then we obtain
[F(x) -(y)
-v)()))
(Lo + Li [V= - =1
N
< I| yl Σ
(2L + ((
| - v2 2
s || (V2 + (=)))
This completes the proof.
29

---

D Convergence Analysis
In this section, we present the missing proofs from Section 3. We start with the proof of Proposition 3.1 and then provide the results related to strongly monotone, monotone and weak Minty problems.
D.1 Proof of Proposition 3.1 Proposition D.I. Suppose F is a-symmetric (Lo. Li)-Lipschitzz operator. Then, for
[F(x) F(v)ll s (Lo (xx])) (L1 vlli vll
and for a (0, 1) we have
[F(x)) F(u)l1 - Ke + (i]l + K2ll y y/ || ull
where Ko L0(20*/1 1), K1 L /1 and K2 L 20 u. 30 /
Prouf. For proving this theorem, we follow the proof technique similar to Chen et [2023]. start with == 1 case. Let i. E I2d and define zp == Oz + (1 0)y. Since is 1-symmetric (Lo, Li Liipsshhh we have for all @ [0, 1].
- IF())) (3))
Lo + L1 S. (IP(xo:)ldd) 11:00 vll-
Note that
Tie + (1 - -) =(0x (1 01y) + +L (1- 7)y --y= OTx + (1 0r)y.
define function
H = Lao Ln L. ([F(x))
Then, note that (0) = Lo + Li ((=)) Moreover, we have
[F(x)) F(v)ll s
Lo + ||((==)]ldr) 1:20 yll
Lo + L1 f." |[F(x0))]ld 110c + (1 - 0)v - all
Lo + L1 !." [|F(xxr)lldr ||0z Avll
LoB Ln
[F((x=))l(dd || wll
Loo Lı
||((0T +1 Or (r)))((0 ||. wll
P1)
LoO L1
|| + + (1-
u)gilldu
1|= wll
0 |IF(zm))ldu ||= vll
ToB Ta
H(]]||= wll-
Therefore we obtain
(0)
Lo + Li [x+))(
< La + Li ([)F(z)) ) F(v)ll ([F())))
Lo + L1 (H(0)) vll + (((())
alT(O)
where a L, |r bll.b= Lo L || (v)ll- Then we integrate both sides E [0,00] get
H(O0) S (c 1).
Here, set 8 = 1 obtain
b
H(L) s (c -1) 1)
a
Lo L1 (())l
(e -ill=-vll 1).
Li w1
30

---

Now, put this back into the original inequality
[()) F(v)ll
< H(1) vll
e'alle-vil
s (Lo + LI1IF(DDI)
Tu
Lo - -1F(wVl)) (ehile-ol -1).
=
11
Finally, using the inequality e² -1s ze" for 2 2 0, we get
[[F(x) - F(v)ll -
To
L + |[F(W)1)) La |1 ullefalle
< (Lo + L1ll (el dalle-vllll vll
This completes the proof for = 1. The proof for E (0, 1) follows similarly from Chen et al. [2023).
D.2 Convergence Guarantees for Strongly Monotone Operators
Lemma D.2. Suppose I' is j-strongly monotone operator. Then Extragradient method with step size T/ = wk
satisfy
|11+1 - x. (1 - 7ap) |0 x. 11 -2 (1- 2Tx4) + (1)) (() F(
(44)
Proof. From the update step of the Extragradient method, we obtain
| - x. 1|
a YA F(t)) x.
| 1| 27x (F [ft) x.) + rill F(xx)1
|| 1. 2% (ft)) 82 - x.) - 2n (f(xx), 22 - ax) + (#x))
M
|| x.1 1| - 2 =.,l" 2 2n (F(#x), In - -x)) + =[l
BV
|| x.112 - 7x 112 + 2T/u11 tx 1110 17th (F($.), fm)
+22) ((xx))
(1 7x/4 I
x. 1/ - 2%x (F(B)), 2u) + + (2x))
(1 7x/4) I
x. 112 2- F(xx)11 - 2- (F( F F(xx)) + -211 x..1 2-221(1((22)))
2
(1 7444 |
rd (1IF(5))]1 [| 11(())) - F(xx)11) +
(1 - 74/4 | ==.11 -11(1 - F(xw)) + +~211F(ax)) 3
D.2.1 Proof of Theorem 3.2
Theorem D.3. Suppose F is j-strongly monotone and 1-symmetric (Lo, Ln)-Lipschitz operator. Then Extragradient method with step size 7 = wa [ satisfy
k+1 ||20 x 11?
|12+]
1.11
(1-
vp
Lo (1+ exp (xp (Ir 2- 11111100 2.ll)
where v > 0 root of
2y - 122 exp 2v
Proof. From the update rule of Extragradient and using p-strong monotonicty, we obtain
[1011- - x
(1 7444 |ark
2.11 - 71 2 F( + +2ll F(2))1?
7xp) ||r
x=112 -1:11 2TH1)
+y Lo + Li Li|IF(xx)l1) exp (2L1 || &u 12 22
2w) 1|= - 11
2 (1 27 (Lo L F()l)())) exp (2 (1 (xx)))2.(45)
31

---

Now se [(oo]]
Then we want to choose such that
201
v² exp 2v 2 0.
Lo LA F(2))l
Note that μ S Lo + ((x)) for any zx. Therefore, get 1 La+Zi|P[app 12 exp 2v 2 1 2v v² exp 2v and is enough to choose such that
2v exp 2v 0.
This inequality holds for any s 0.22. Hence, for this choice of v the following inequality from (45).
||xx+1 x.11²
(1 - ma)lla z.1l".
(46)
This proves that the distance of the iterates ay from x. are bounded by ||z0 xxIl. Now note that using (13)
with x Th, y with | -xal
1| x. we get
(13) S
[F(x)]]
Lo exp (Li I|= - 2-11][[=x x-ll
La exp (Li 1120 - x. 1))| 2.11,
(47)
Therefore, we have the following lower bound on the step size
7
La L ((x)]
(48)
Lo (1 + exp (L1 v. 111111100 J..
Hence, we get
[ - x.l
(46)
1 Lo [1 + exp (T1 ||= v., 1)) xall]
1/
||5e xal1?
x+1
1 Lo [1+ L1 exp (11 100 x.
vp
|
2.11²
1) x-11]
D.2.2 Proof of Corollary 3.3
Corollary D.4. Suppose is p-sstronlyy monotone and I-symmetric (Lu, L2) J-ipschhtt operator. Then
Extragradient with step size 7/6 = wh 11+ satisfy || x.1 < after
20o log K
||-00 =2.1%
1
2T. 11000 =.
+
log
7/4
72 Lo
many iterations, where satisfy
4v 2nd exp and
= Lo (1 + L1 exp (L1 x. II) Iro x-11)
Proof.
We 7/4
Lo [1 and choose E (0, 1) such that 4y 2u² exp 0. Then
have
2nμ
1 27 Hē(Lo + Li ( exp
2 1 Lo + Li F(xx)l
exp 2v
> 1 2v 1² exp 2v
=
(49)
Therefore, from (45) and (49) we get
22
| I.
(1 mm)) =.11
2 [
(50)
In (48), we found that a lower bound of is
7/ 2
(1 + exp (Tal - x, 11 x+1l)
Then from (50) we get
[(xx))] 3 (1 rH)]lEe =.11² < (1 ++1) - x.11
(51)
2
32

---

This can be rearranged to write
[F(x))]1 2(1 7u) 6+2
1100 x-11
This implies [ax)) &
La after Ti
1 log 7/
211 11:00 11.
K'
(52)
72
many iterations. Hence for k 2 K' we have
Tk
La + L1 [[xx)l
2La
the last inequality we used [Fxx)))] 2
Le for 2 K'. Therefore for 2 K' we obtain
| 11441-x111 x.11
up
|
x=11"
2Lo
k+1-k'
vp
|00 x.1
2La
641-K"
11000 - x. 11
2Lu
Thus conclude that, ||
1.11² 112 < after atmost
2La
xo
K
log
+ K"
uj
many iterations.
D.2.3 Proof of Theorem 3.4
Theorem D.5. Suppose F is j--strongly monotone and a-symmetric (Lo, L1 Jippecizt operator with E satisfy
(0, 1). Then Extragradient method with
22K +21 "K] [[((()))
k+1 ||a00 I.
| - x=11²= S 22o Ka "00 ho-
where E (0, 1) is constant such that 1 2² 0.
Proof. Using the update steps of the Extragradient method and using /r-strong monotonicity, have
| - 2-11"
|| 7w4)
11 ~1
F(xw) F(+))ll
S
(1 7x4) || x. 11. - 71(1 [(xx))
t (Ko K=11 Kall=a -111"/1-0 ||00a &all"
(1 mui)l 1
+7 27 xh Ko + (I(F(==)]1* + - "K(]((([))))" || [1=()))
Here will choose 7 such that
1- 2 2h Ko + K1 F(x))(
7 2 F(xx)1 2 0
choose 74 2Ko+ 2K +2 12----03 ""
for some (0, 1). Then we observe that
v (Ko + Ki [(xx))
7t (Ko K=][F(2x)11") + + 1/2 K=
2Ko +2K, + 2 2 K2 -9) [f(x)]]
1/ "Kal
(2Kg + (2K; 2 K K2-") [I 4/-
4/1
2
33

---

The last inequality follows from é (0. Therefore it is enough to choose (0, 1) such that
20μ
v² Σ
2Kg + (2K1 + 2 K2
[+(x))]
However, note that, always have j I Ku. thus it enough choose (0, 1) such that Henec, for this choice of get
-- v² 2 0.
|| - 2.11 S (1 7010] - xx
Here we lower bound the step size with
V
2
2Ko + (2Ki + 21-ak]
"Koo K2|lz0 z. )/)10/ x. 11
Hence we obtain
| 12112 =
||se x011
(2K) +2 -K2-" "KKa K2 1100
2+1
| 11
22K+ 2222-"KK
14 1 K2o
This completes the proof of the theorem.
34

---

D.3 Convergence Guarantees for Monotone Operators
Lemma D.6. Suppose F is a monotone operator. Then EG with step size = satisfy
|+++1 x. S 2* x. 1I [F(=)l] + (())(() F(E+)]l.
(53)
Proof. From the update rule the Extragradient method, we have
[
_.1
| 7/ ((x) x=11²
| 2. |²= 2% { [Bx ( -ill
|| vta 12 2n (( ; 5
- 2nm (F Jo 2x) + +111)
|| x. 2 27h ; + ((t)))
|| - V.
+ ((
(22)
|| x+ - +
|| - 2. - (2) - F(2))1
D.3.1 Proof of Theorem 3.5 Thcorem D.7. Suppose I' is monotone and 1-symmetric (Lo, L1 Liipschizz operator. Then EG with step size ,/o LotZiliF(a)) satisfy
min [F(xx)]| 21h (1 I, exp (T, (T,11100 - (1) 1|50 x.11)² ||50 x.112
OSkSK
(*K+1)
where vexpu= 1/v2.
Proof. From the update rule of the Extragradient method and using monotonicity, we have
(53)
| x211
|| x. 11? - (x==)) (x)) F(++)]l
||ak 112 - F
Lok ==114 exp (2L1 - 2x11) lxll
|| 112 n (1 - -E L1|[F(2x)]l (xx L1 [F(m)]]
<
||e 11
- (1 - (Lo + L, F (xx))l) exp 2. [F [F())))
Here we use 7p
Fott11F(eee)) for some E (0, 1) to get
||x1+1 1.11 $
| 1. 7h (1 v² exp (2n)) [<x(2))]
Then we choose such that vexp 1/v5 / to obtain
| 2=1 <
| v.
7h
[1F((x))1
(54)
2
In particular the distance of the iterates 2y from v, are bounded i.e. ||r++1 I. S || - x.ll S 1|200 - x. Therefore, using (13) with and
we get
[(*x)l s La exp (TI|| || - xx. x.11) x+
< Lo exp (Lx)lag I. [D] 2=|1
Then we have the lower bound on step size given as follows
(55)
Lo Li [((x)
Lo (1 Li exp (Li 100 1- 100 x=Il)
Rearranging (54) we have
1 2
F(xx)1?
S [Ire 1.1 ||+++1 x.
Summing up the above inequality for ls 1.1.... K and dividing by K + we get
[[((x)))
1 x. 11
| 2-11
1t0
(56)
K
K +
K 1
R=0
35

---

Here will use the lower bound on step size T/E given in (55) to
1 K
2n (1 + L1 exp L1 I.o I. x.ll) 1120 22(K +1)
I. x.11)²1|an 11200 x.1
K+1
Finally, note that minoSksK [F(xx))l & K+1 Σ K== [ )l Therefore we have
2L3 (1 L1 exp (1, 1gg x- 11) 1000 v²(K + 1)
2. 11) 11000 - v.
mim
[F(x))|
OSKSK
This completes the proof of the Theorem.
D.3.2 Proof of Theorem 3.6
Theorem D.8. Suppose F is monotone and 1-symmetric (Lo, Ln >Lipschtt operator. Then Extragradient method with step size 7 [f satisfy
v Vo x.
min OSRSK
[F(x)]]
VV K +1 22l, 1100 x.1
26 26
where vexpv v 1/v2 and
Proof. From (56), know steps of Extragradient method satisfy
2h [1((1)11
200 x. K +
K+1
Taking the minimum on the left left-hand side have
21[30 x.112
Thl (x1))1 OSkSK
min
K-1
or equivalently,
2o 2- 1|
min OSkSk
(Lo L1 F(xx)(
K +
Taking the square root on both sides we have
min v((F( OSKSK K La + Li [F(xa)l
2 22 x.
/ K 1
Therefore, for 0 S.A Ko K have
[
v2 arg x.1
Lo + L1 [F
vVK
Therefore, rearranging these terms, we get
(pvK+I- V2Lilizo -ILLllo
x. [1F(2x))] II
V2Lol|zo x=11.
When we have +12 21 21 then we can rearrange terms to obtain
V2Lolizo r.
F( (PVK +I /2L x-
for some 0 S ko < K. Hence, complete the proof of the theorem
/2Lo x. vV +1 V2T, 1| rall
min DSkSk K
[((x))
D.3.3 Proof of Theorem 3.7
Theorem D.9. Suppose F is monotone and a-symmetric (To, I.) Lipshhitt operator with E (0,1). Then Extragradient method with step size 7/k 2222k+ wi/2 F)(F(())) satisfy
Kot (x
-x, (1a) 120
minogAgK [F(xx)]12 <
K+1
36

---

Proof. Here operator o-yymmetrii (Lo, L1 Lipschhtz i.c. it satisfies (14). For the update steps of the Extragradient method, we have
[+++1 - x.
alar - x-11 -
F(
133
1l 2-11² (2)x)
+ Ko + (xx1F(==)11 Kallaa &xll' ) 11:0 - fxll2
2 2-
- 1 Kn Ki|l "aal"== [F(xx)]|.15)
Here we want to choose "/2 such that
Th (Ko Ki (111F(+))1"")
7 "Ka]l((ra)))**
$ /2
For this, is enough to make
(Ko + Ki (=][F(+*)]1)) s
1
and T 1/10 K2 [F())]]]
S
1
2v2
2v2
Therefore, choose 7 2v )+ 1000 (F(
and we get the following from (57)
|Ire x. - v2 |12411 - 2011? I
2 [(x2))]
(58)
Rearranging this inequality, we have
T F(x))] $ 2
IIre =a11? |,041 2-1²
Then we sum up this incquality for = 0, .. K to get
2||200 - x.
nhl [==))
(59)
K +
K 1
For this step size, also have || 2o following bound with æ my and y v.
|Ir0 x. 1| from (62). Now note that from (14) obtain the
[[(()))l"
(Ko K2llax 20.1 101111110000111110 2-1l"
(Ko K2llao x. -/t10/ | x-11%
We use this lower bound the step size "/x as follows
2001 13/1-0//2 K3 F 2/2(Ko (=
2/2Ko + 2/2(K, 2- "Ko + K2l - x. /0 11:00 x.Il"
Therefore from (63) we obtain
16 Ko (K, +2 -2- 3/2/// + K2/ xx11%/2 a) 1x 10 11:00 x.1 11
min USkSk
[[(x))1
K +
37

---

D.4 Local Convergence Guarantees for Weak Minty Operator
D.4.1 Proof of Theorem 3.8 Theorem D.10. Suppose F is weak Minty and 1-symmetric (Lo, L1 )- Lipsschit assumption. Moreover assume
V
A
4p > O.
(60)
Lo (1 + L1 |1=0 x. le.lle21 11l00 (e2
Then EG with step size T/e = [ and wE = 7w/2 satisfies
ALo (1 + L1 exp (L1 11200- Io 10 x+ll) 1100 r.
min aSASK
[1(
(61)
(K (1+1)
where y vexp = 1.
Preef. From the update rule of the Extragradient method, we have
| x.112
x* 2
2 F(tx) x
2 |1x x. 112 - 74 (F( 20 - x.) + F(x)))
|| x. 1| 7h (F(tt), #x =.) 7x (F($)), oh xx) + 28
4 (1
(0) S
|| x. 2|2 + F( (F(in), 2x - (n)) + 2 |
22 (F(ie), F(xx)) + 22 [
|I+ x. 11? + =
22 (I
28
|1 11 21 FxPl
|F()))]
2
2
+ rh || F FI + 2h [[F()x))1
28
22 |F()))]
|. I.11 21 + F
[|(())))
4
+ Th 1 ((*)) F(
2
[1 |I x.11 (
22
22 |F(x))]
S
4
+
7k
(Lo L1 F(xx))l))) exp (2/,
* - 2xll
2
| rr112
7h (7x 4p) (
2
%k
(1
7To L F(*x)
(2 [F((=]]]
2
< ||, r.Il
7A (7x 4p) (
(1
ALo L [(xx))) 11) exp exp (27a L. (+x))
2
Similar to the proof of Theorem 3.5, we have
|
1 S
||2| x. 1|2
7h (T4 (+x))
4
for Mh F( and eepp= 1. Again similar to Thcorem 3.5, step size m is lower bounded with
The Lo + LillF(tw)1
Lo (1 + L1 exp (L1 x. II) 1|av xx11)*
Hence from (17) we get
m
[(()))1
< || - x.11
|| x. 1
Then we sum up this inequality for 1,
K get
1200 xx 11? K + 1
F(2x)1
K + R=0
4
38

---

Therefore, we gel
11120- =. 7Ai(K + 1)
min 0SAS
[
D.4.2 Proof of Theorem 3.9 Theorem D.11. Suppose F is weak Minty and a-symmetric (Lo, L1 L-ipscitt with (0, 1). Moreover assume
A. 2V2K, + 2V2((K) +2 (P-3--)(E + K2 fr - 2.|10//1 2)0l|00 - x.1 4p >
Then EG with step size 7 2/2Kg0 (2/2K, +2 1/2k ")]IF(=2)1" and we z satisty
(Ko (
[Ko- 11l 1000
minogAsk [|F(
(K+1)
Proof. From the update rule the Extragradient method, we have
|10411 - x. 112
The F((x) - 2. Ia
|| 2-11² 212- - 7/ (F()) 2k [((
|| 2.11 - (F(*)) ) fs - -.,) - 7h (F(ts). 2x - ix) + 2h
|F(+))]
=
4
(10 S
||ar 2.11 + + 74 (F(2x), Io - ax) + 2e (
|| 2-11 +
T/ (F(2x). [(x))) + 4
||((@)
2
|| x21 + THP F(h)))
Th 11
2h F(xx)]
2h
2 [[((Ea]]
[1xx)) F(#x)]l
= ||0 x111 + (( z2 [((+)))
22
[(xx))
2
22 1((x)) F(Rx)11
||== 1111 + + 22 [[
2h. [[
+ 2h
Ko - ((+|F(+=)11 + Kallax - 2x 1
|| - fxel2
||
2=11
Tk (7x 4p) [1F(2))1
4
2ee - 7he Ko + K1 FF(x)( + w//t (a]](()))) -)²) [IF
Here we choose 7 2(Ko Ki [F(x)))] " 42 a//2k1- (F((x)" and we get the following from (57)
| - 1=112 S
|| - x=11 4 (tx 4p) F
(62)
Rearranging this inequality. we have
(7x (F(xx)1
< | - 1. || x=11?
Then we sum up this incquality for 0, 1,1, K get
Yk (7x - 4p) (((22)1
<
21 xx
(63)
K
4
K + 1
k=
39

---

For this step size, also have 1|2 x. 1|2 Σ ||:0 - -r, from (62). Now note that from (14) we obtain the following bound with ue and
[px IIl"
(Ko + K2llax 2. 2=11"/1-0)0111 2-1l"
(62
(Ko + Kallæo x.1l ==.1 120 22.11
We this lower bound the step size 7 follows
2v2(Ko Ki K=I1 2 2/2 K2 1 F[(=))
2/2Ko 22/2 + 22 (Ko + K2 1m0 xz 9 x. 1
Therefore from (63) obtain
Al120 x. x.1
min uSksR
||((x)]] -
>A(K + +1)
40

---

E Equivalent Formulation of a-Symmetrii (Lo, Li)-pischttt Assumption
In this section, consider the min-max optimization problem given min.; max.w L(wi, w2) and provide an equivalent formulation of a-symmetric (Lo, - operator. Next, we provide an example where we use this formulation to compute the constants a, Lo, L1.
E.1 Proof of Theorem 2.1
Theorem E.I. Suppose F is the operator for the problem
min max L(w1, W2)-
Then F' satisfies a-symmetric (Lo, Liipsshhhiizzzz assumption if and only if
J=(x)] sup [1(x))ll S Lo (x)))
||||=1
where
V m L(wi, W2)
V
wy un L(wi, W2) (wi, W2)
(xr
- -n (wi, W2)
-
Here [](x)]] = mmax ( (x)) i.e. maximum singular value of J(x).
Proof.
Following (26), have the equivalent characterization of F given by
[IF(y)- - F(x)) & Lo + L1 [." ||[(yy (1 (1- ()=)l d0 l1 x|l
Ve, E R
As this inequality holds for any I.". we choose = x + 0'u where ||w|| = and o' E (0,1), 1). Then we get
[F ((u)) - F(x)l (1 L. ||F(x + 0'ow)l " d0 [10'al|
Wa E Rd.
The right-hand side of this inequality can be rewritten
LLo + L1 L/' ||[( d'Ou)ll d0) 10''a] ull
0' (Lo+ L1 L( ||fe [[[(e+00u)]] d0)
Loo' In S( || 0'Ou))l d'
Lab' + L1 1. |F pulll" de.
In the last line, we used the change of variable with 0'0. Therefore, we get
F( + - F(x))l
L1 < Lo + 0r /- ||F(z + pu)l de.
0'
Then take 0' and I''ôópitll' rule and Leibniz Integral rule to obtain
[F 60u) F(x)ll & Lo + L, [
lim
00
0'
Moreover, note that the left-hand side is given by [[]())l|| where
My in L(w1, W2)
V2 Mog un C(wi, W2)
(.)
V
Nery wa [wwi, w2)
mog C(wi, w2)
Therefore, for any ||u||| = we have
[[]]]u||| To +o [()
Hence we get
[]()]] sup [ Lo 1= =
Now we want to show the other way, i.c. suppose we have |(>) S Lo La (x))] For this we define,
(())
F0r (1 0)²)
41

---

Then v(1) F(2) and q(0) F(v) and we have
[1F(x) F(v)ll
(1
(0)]
(Q())
d0 d8
1%
dFx (1 0lv) d0
d0
!
J(Or + (1 (0)) y)d8
[[](0z + (1 0)v) 11 || =0l
(/, [J + (1 0)z) ||< #1l
[ Lo + LillF(0x + (1 0)0)1 dB
|| vll
To + In I-" ||F(0x ()0)) do
|| vll
Then, using Lemma B.5, we have the result.
E.2
Computation of a, Lo, Lı for [(wi, W2)-
We now revisit the min-max problem defined in (6). Note that, the operator corresponding to this problem is given by
w w2
F(x)=
w wi
Then the norm of operator is |[(()]] / (wf + w2)² + (w3 w1)²
Moreover, the Jacobian matrix is given
by
2ww
(z)
-11 2w²2
Then the maximum singular value at any point x is given by
[x(xl]
Amax
((x))
4wf + 1 22(w)
2(w1 - w2) 4w3
))
Amax
w2)
2(w2 + wf) + ++ 2/ (wi wy)2 + (wf wg)
(64)
validate whether the operator satisfies condition (7), we examine whether the following function non-negative:
gww,, w2) = Ta + Ln [[=)] [[(()]]|-
(65)
In Figure 6, plot g(W,, Wa) using Lo 10 and L1 10. We observe that g(W, W2) has real solution and remains positive for all W1, wa R. confirming that the function (6) satisfies (12) with (a, La, Lt) (1, 10, 10). Thus, the corresponding operator is 1-symmetric (10, Lipschitz.
42

---

1.2
9 1MM1 w2)
1.0
0.8
0.6
0..4
0.2
1000
750
500
10095909500 259 50 0000 1000
250
250
W2
500
750
W2
Figure 6: Plot of g(wi, wz) (65). Here, the z-axis is 107 scale.
Additional Details on Numerical Experiments
In this section, we provide additional details on the second experiment related to the monotone problem. First, we show that
3/2 wi Buz
3/2
C(wi, w2) ui Awi)
Wu2 Cwz)
convex-coneave, and then find the equilibrium point of C.
Convex-Concave L(w1: w2). Note that for L(w1, W2) in (20)
have We, [(W1,
(w] Awi) 1/2 Awi + Buz vwzf(wi, = B T w1 (wi Cwz) 1/2 Cwz. Then the second-order
derivatives are given by
Awpwi A | V
V mawe L(w1, W2) A 1 ||A
Here, A is positive definite Awn wi A is positive semidefinite matrix. Hence, wy [(wn, w2) positive definite matrix as well and L(, W2) is convex for any w2. Similarly, we show that
Cwyw CT
wy C(wi, w2) | w2ll ||
[C/wwlll
and - Verye L(wi, w2) is positive definite. Therefore, ((w1,)) is concave for any w1. This proves that C(w1, w2) is convex with respect to wi and concave with respect to w2. Thus, we conclude that the correspond- ing operator is monotone.
Equilibrium of L(w1,w2) To find the equilibrium points, we solve the set of equations given by V., L(wi, w2) and VuzC (wui, w2) 0, i... solve for
wi Awi) Awi + Buy
0,
1/2
B w1 [ Cws)
Cwz
0.
Now multiplying the first equation with wI and second one with w. we have
wi Aw1)
wi Awi + wi Bwz
1/2
W2 B wi [w] Cwz)
u22
Cws
Combining these two equations, we get
1/2 wi Aw +
1/2
[w] Aws
(w) Cuzz
M02 Cwv
= 0
43

---

which can be equivalently written as
A
1/
3 wi
+
1/ W2
0
which implies wn w2 both A, are positive definite matrices (hence A 1/2 C are invertible).
44


Reviews:
[{"review_id": "WMC273TNTl", "reviewer": "Reviewer_4hmy", "summary": "This paper analyzes the extragradient method for min-max and variational inequality problems under relaxed assumptions. In particular, the common (and often strong) L-Lipschitz continuous assumption is relaxed to an $\\alpha$-symmetric $(L_0, L_1)$-Lipschitz continuity assumption, which allows the Lipschitz constant to scale with the operator norm. Under this more general condition, convergence analysis is given for strongly monotone and monotone variational inequalities. In addition, a local convergence rate is given for variational inequalities which satisfy the weak Minty variational inequality condition. Experimental results are provided that validate the effectiveness of a newly proposed adaptive stepsize based on $(L_0, L_1)$-Lipschitz continuity.", "questions": "Is the exponential dependence on $\\|x-y\\|$ tight in Proposition 3.1? Are there any conditions under which this exponential dependence may vanish (other than $L_1 = 0$)? My curiosity stems from the fact that this appears to cause major issues throughout the paper, such as for the strongly monotone case (where this only shows up in a constant now, but still persists), but especially in the weak Minty variational inequality case, where the neighborhood of convergence is directly dependent on this exponential dependence, which seriously restricts the applicability of the result. If it was possible to find reasonable conditions under which this exponential dependence vanished or was more controlled, it could significantly improve my evaluation score, as it would significantly improve the result in the weak Minty case.\n\nFor the weak Minty experiment, do the methods struggle when started far from the solution? I am curious if the authors observe the issue of only obtaining local convergence using their adaptive stepsize or if this is just an artifact of the analysis.\n\nIn the theoretical results, the adaptive stepsize is dependent on the constant $\\alpha$ in the $\\alpha$-symmetric assumption, however in the numerical experiments, $\\alpha = 1$ is used throughout. Do the experimental results change much when $\\alpha$ varies away from 1? In particular, for the monotone case, the introduction suggests that this problem should use an $\\alpha < 1$, which partially motivates the assumption, but this is not used in the experiments, which raises questions about the value behind this relaxation of $\\alpha$.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: This paper analyzes the highly popular extragradient method for variational inequalities under a relaxed set of assumptions. The convergence results improve upon known results in the strongly monotone case and are the first convergence results under the $(L_0, L_1)$-Lipschitz continuity condition for monotone operators. In addition, the work provides the first convergence results for weak Minty variational inequalities, though the convergence is only local. These results are proven when a novel adaptive stepsize is used. This stepsize strategy is validated numerically on a number of simulated experiments.\n\nWeaknesses: In the strongly monotone case, the improved convergence rate comes from an argument that shows that the exponential dependence on the distance of the initial point to the solution can be moved into a constant factor, as opposed to multiplying a $\\mathcal{O}(\\log(\\epsilon^{-1}))$ factor (where $\\epsilon$ is the optimization tolerance), as it is in prior work. While this is an improvement, it is a relatively minor change that is only relevant for extremely small values of $\\epsilon$. In addition, the convergence rate for weak Minty variational inequalities requires that $\\rho$ is sufficiently small relative to $L_1 e^{\\|x_0-x_*\\|}$, which essentially requires that either $\\|x_0-x_*\\|$ is extremely small for any non-monotone problem or $L_1 = 0$, in which case the generalization to $(L_0, L_1)$ smoothness is irrelevant.\n\nQuality: The focus on extending convergence results for extragradient methods beyond is a reasonable focus, as current results rely on restrictive assumptions that may not hold in practical applications. The relaxed assumptions provide a nice generalization and the results appear to be technically sound. However, a number of the results are only minor improvements over previous works or require extremely strong assumptions that limit their applicability.\n\nClarity: The paper is well written and well organized. There are a number of examples given to motivate the modified assumptions and the relationship with prior work is clearly stated. The limitations of the work could be stated more clearly, as they are spread throughout the main convergence results. It would also be nice if there was a brief discussion or conclusion section added to this work discussing potential future directions.\n\nSignificance: This paper provides some of the first results for extragradient methods under the $(L_0, L_1)$ smoothness assumption. However, the strongly monotone result is only a mild improvement on prior work and the weak Minty variational case only applies to an extremely tight neighborhood of the solution. Therefore, the main contributions are mostly limited to the monotone case.\n\nNovelty: The main change from prior work is the use of the $(L_0, L_1)$ smoothness assumption and applying this to the monotone and weak Minty variational inequality cases. While this is novel, it feels more incremental than a major new direction of research.", "was_revised": true, "final_justification": "I have decided to improve my score to a borderline accept due to the author's responses regarding some concerns I had related to the exponential dependence on the initialization which is present throughout the paper. I stopped short of a full accept as I find the motivation for root finding problems under these more general assumptions somewhat lacking and am concerned about the limitations of the local convergence result for weak Minty problems.", "rebuttal": "We thank the reviewer for their insightful comments and suggestions. Our detailed responses are provided below.\n\n## Weaknesses\n**[In the strongly monotone .... it is a relatively minor change.....]** We respectfully disagree with the reviewer’s comment. In optimization, practical interest typically lies in obtaining high-accuracy solutions, i.e., small values of $\\epsilon$. In such cases, any significant constant multiplying the $ \\log(1/\\epsilon)$ term can have a substantial impact on the convergence rate.\n\nTo illustrate this, consider the well-known comparison between Gradient Descent and Accelerated Gradient Descent for smooth, strongly convex functions. Gradient Descent achieves a rate of $O\\left(\\frac{L}{\\mu} \\log(1/\\epsilon)\\right)$, while Accelerated Gradient Descent achieves $O\\left(\\sqrt{\\frac{L}{\\mu}} \\log(1/\\epsilon)\\right)$. The difference between $\\frac{L}{\\mu}$ and $\\sqrt{\\frac{L}{\\mu}}$ leads to huge improvements in performance, especially as higher accuracy is desired.\n\nIn our setting, removing the exponential dependence on the initial distance to the solution from the convergence rate and moving it into a constant factor is a meaningful theoretical improvement. The exponential factor can be arbitrarily large depending on the initialization, and its removal explains the performance of the algorithm in practice. Moreover, in experiments, we show improvement with our proposed step size compared to the prior work (check figure 3a, 3b). We hope this clarifies the significance of our result.\n\n> .... for weak Minty variational inequalities, though the convergence is only local.... \n \nWe agree that the assumption on $\\rho$ for weak Minty problems is currently restrictive. However,  this is the first analysis conducted under the $\\alpha$-symmetric $(L_0, L_1)$ Lipschitz assumption for this class of problems, and we believe it lays the groundwork for further theoretical developments in this direction.\n\n> However, a number of the results are only minor improvements....] + [it feels more incremental than a major new direction of research. \n\nWe disagree with this statement. As mentioned in the previous response, the improvement in the strongly monotone setting is not minor. Moreover, we provide the first analysis in a monotone and weak Minty setting.\n\n> It would also be nice if there was a brief discussion or conclusion section added to this work discussing potential future directions. \n\nWe were unable to do that due to space constraints. Thanks for the suggestion, and we will include it in the updated version.\n\n## Questions \n\n> .... Are there any conditions under which this exponential dependence may vanish ... \n\nThank you for the insightful question. We would like to clarify that the convergence analysis of our proposed algorithms fundamentally relies on the equivalent formulation in Proposition 3.1. This formulation introduces the exponential dependence you noted, and we currently do not believe it is possible to eliminate this term entirely from the convergence rate. We can only improve how this term appears in the rate and minimize its impact on the convergence rate. \n\nAs mentioned in our earlier response, in the strongly monotone case, we show that the exponential dependence no longer appears as a multiplicative factor to the $O(\\log(1/\\epsilon))$ term, but rather as an additive constant. As explained earlier, this is not a minor improvement. We agree with the reviewer that, in the weak Minty setting, the condition on $\\rho$ is currently restrictive. However, we believe that the dependence of $\\rho$ on the exponential term can be improved even in the weak minty setting, and we view this as an important direction for future research.\n\n> For the weak Minty experiment, do the methods struggle when started far from the solution?...\n\nThat is an excellent suggestion. We can easily include such experimental evaluation in the camera-ready version of our work to visually verify our theoretical findings. \n\n> In the theoretical results, the adaptive stepsize is dependent on the constant $\\alpha$ in the $\\alpha$-symmetric assumption, however in the numerical experiments, $\\alpha = 1$ is used throughout....\n\nIndeed, for our proposed experiments, we used $\\alpha = 1$ as all problems satisfy the $1$-symmetric $(L_0, L_1)$ assumption. Let us highlight that the primary goal of our experiments is to demonstrate the benefit of using the adaptive step size $1/(c_0 + c_1 \\|F(x_k)\\|^{\\alpha})$ over the constant step size typically used in the extragradient method. In our experiments, we show that our proposed step-size selection with $\\alpha = 1$ yields better performance than the constant step size. That said, we agree that exploring different values of $ \\alpha$ may lead to further improvements. We can easily include additional experiments to investigate the impact of varying $\\alpha$ in the updated version of our paper.\n\n**We hope we have addressed all the questions and concerns raised by Reviewer 4hmy. We believe that most concerns raised can be easily addressed in the updated version of our work (not major issues). If you find our clarifications satisfactory, please consider increasing your score. If not, we would appreciate the opportunity to respond further.**"}, {"review_id": "ZtordkoJed", "reviewer": "Reviewer_Fpia", "summary": "This work analyzes the convergence rate of extragradient method under the α-symmetric (L0,L1)-Lipschitz continuity, a smoothness condition that generalizes both the classical Lipschitz assumption and the (L0,L1)- Lipschitz framework (where α = 1) introduced by [1]. The authors claim that the classical global L-smooth condition is often too restrictive for certain optimization problems, and instead propose an adaptive method that performs effectively under the α-symmetric assumption. In Section 3, they establish convergence guarantees under three different assumptions on the monotone operator F, which matches known upper bounds in certain extreme cases. Specifically, their Lyapunov-style analysis results in an adaptive stepsize that ensures the distance to the solution decreases across iterations. Finally, the authors present experimental results that support and validate their theoretical findings.", "questions": "In addition to the mentioned weaknesses, I have some questions:\n• What are the problem parameters (L0,L1, α) of equation (19)? Does it matches the parameteres that lead to good performance in Figure 3c?\n• The choice of stepsize differs significantly depending on whether α = 1 or not. However, in practice, α is typically unknown. Given only a problem instance, how should one select an appropriate stepsize? Would it be necessary to sweep over possible α values or estimate α in advance? Is it possible to design an algorithm that works reliably for all values of α without prior knowledge?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n - The results are both strong and straightforward. The authors establish convergence guarantees across all six scenarios by varying the parameter α and the monotonicity assumptions on the operator. They successfully extend the analysis of prior works (e.g., [2]) to the extragradient method. Most of the convergence results are novel and contribute meaningfully to the theory of the extragradient method.\n - In my opinion, this paper is written in a very clear and reader-friendly manner. Six different cases in Section 3 as well as their proof in Appendix are presented in a nice parallel structure, making both the theory and its proof easy to follow. This also makes the paper a valuable reference for future research upon these findings.\n- The class of operators considered in this work is broad enough to encompass many practical problems. Combined with the significant role of the extragradient method in optimization, these results broaden its applicability to a wide range of optimization problems. The broad nature of this work opens up future research directions, such as extensions to other momentum-based methods or the development of alternative stepsize schemes.\n\n\nWeaknesses\n -  The proposed method is not fully “adaptive,” as the step sizes still depend on global problem parameters (L0,L1, α). I understand that the primary goal of this work is not to develop an adaptive method, but to establish convergence guarantees under a new problem assumption. However, the contribution could have been stronger if the method had incorporated local estimates of global parameters. For example, [3] proposes an approach that estimates L0 locally. In fact, the importance of choosing proper (L0,L1) is also evident in the experiments, as the performance appears to vary depending on their choice. \n - As previously mentioned, the core content is well-structured. However, the paper lacks a dedicated prior work section, either in the main text or the appendix. As a result, it is difficult to clearly understand how this work relates to existing literature or how it compares to previous methods developed under similar assumptions. It seems that most of related works cited in the main text appear to focus on the (L0,L1)-smooth and α-symmetric assumption, rather than on method-level analyses.\n - I found the experimental section to be somewhat limited. While the paper is primarily theoretical—so this may not be a major concern—it seems that most experiments were conducted on synthetic data. Including experiments on more practical problems or scaling up the current ones could help further demonstrate the method’s effectiveness in realistic settings.\n\n\nTypos\n• Line 3: Variational inequalities problems → Variational inequality problems\n• Line 45 : Memorys → Memories\n• For theorems 3.2,3.4,3.5,3.6,3.7,and 3.9: satisfy → satisfies\n• x∗ not defined in Assumption 1.3.", "was_revised": true, "final_justification": "I appreciate the contribution of this paper, and the weaknesses that are brought up are minor. I vote to accept this paper.", "rebuttal": "We thank the reviewer for a positive evaluation and for providing us with valuable feedback. We address the questions and concerns raised by the reviewer below.\n\n## Weaknesses\n\n> .... For example, [3] proposes an approach that estimates L0 locally.... \n\nWe are not sure which paper the reviewer is referring to with [3] in this context. We agree that it would be highly valuable to develop a fully adaptive algorithm for this general class of problems. However, we would like to emphasize that even the analysis of such problems, assuming knowledge of $(L_0, L_1, \\alpha)$, has been missing in several important settings. Our current work addresses this gap, and in future work, we aim to extend the analysis further and explore techniques for estimating these constants in practice.\n\n> .... It seems that most of related works cited in the main text appear to focus on the (L0,L1)-smooth and α-symmetric assumption, rather than on method-level analyses...\n\nThank you for the suggestion. Indeed, our related work section is primarily organized around the assumptions rather than the methods. This is because, to the best of our knowledge, there are no prior works analyzing algorithms under the $\\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, except for [1], which we have referenced multiple times.\nThat said, we agree it would be helpful to include a broader discussion. In the revised version, we can easily add a section in the appendix reviewing methods developed in the minimization setting that are analyzed under the $\\alpha$-symmetric $(L_0, L_1)$-smoothness assumption.\n\n> .... While the paper is primarily theoretical—so this may not be a major concern—it seems that most experiments were conducted on synthetic data. ... \n\nYes, the primary focus of this work is to strengthen the theoretical foundations for this general setting. Our current experiments are designed to demonstrate the advantage of using step sizes of the form $ 1 / (c_0 + c_1 \\| F(x_k) \\|^{\\alpha}) $ over constant step sizes. We will include additional experiments in the updated version to validate the effectiveness of our algorithm further.\n\n> Typos \n\nWe thank the reviewer for carefully reading our work and pointing out the typos. We will fix them in the updated version of the paper.\n\n## Questions\n\n> What are the problem parameters (L0,L1, α) of equation (19)? ... \n\nIn Appendix D2, we explained a way to compute these values in a simplified setting. \n\n> The choice of stepsize differs significantly depending on whether α = 1 or not. However, in practice, α is typically unknown. Given only a problem instance, how should one select an appropriate stepsize? \n\nAt present, for general problems, one can only consider sweeping over different values of $ \\alpha$ and check which one performs best. However, our future goal is to develop methods for estimating the parameter $\\alpha$, which we believe will be a significant contribution to the literature.\n\n**We hope we have addressed all the questions and concerns of the reviewer. If not, please let us know so we can respond accordingly.**\n\n## References\n\n[1] Vankov, Daniil, Angelia Nedich, and Lalitha Sankar. \"Generalized smooth variational inequalities: Methods with adaptive stepsizes.\" Forty-first International Conference on Machine Learning. 2024."}, {"review_id": "zFAhaw6ctp", "reviewer": "Reviewer_wYYi", "summary": "This paper studies the Extragradient (EG) method under the $(L_0, L_1)$-Lipschitz condition. This is a generalized and perhaps more practical condition compared to the traditional $L$-Lipschitz assumption commonly used when studying the EG method. The paper provides sublinear convergence under the monotone assumption, linear convergence under the strongly monotone assumption, and local convergence under the weak Minty (non-monotone) assumption. Together with the theoretical analysis, the paper presents numerical experiments that demonstrate the effectiveness of the proposed step sizes.", "questions": "- **Q1.** In lines 185–187, the authors state that the results in their paper recover the result in [Gorbunov et al., 2022b]. However, as the title of the cited paper suggests, it provides 'last-iterate' convergence, rather than an ergodic convergence rate. The reviewer is confused, as the results provided in the submitted paper are ergodic convergence rates (Theorem 3.5). Can the authors clarify this point?\n\n- **Q2.**  Is there a significant technical difficulty compared to the function minimization problem or the standard $L$-Lipschitz setup that the authors would like to highlight, which the reviewer might be overlooking?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- This paper starts by introducing the motivation for the $(L_0, L_1)$-Lipschitz condition they are considering, and they did a good job on this point. To the best of this reviewer's understanding, they needed to come up with new observations related to EG for this purpose, and the reviewer believes these are meaningful observations worth sharing. They also provided persuasive examples.\n\n- They provide theoretical convergence analyses under popular assumptions—monotone, strongly monotone, and weak Minty—commonly considered for the EG method. In the context that these results are generalizations of results already established in function minimization problems or setups with only an $L$-Lipschitz condition, they could be seen as somewhat expected. Nonetheless, the reviewer believes they still contribute meaningfully and represent work that needed to be done for the field.\n\n- The paper provides meaningful equivalent formulations of the core assumptions. They seem useful in carrying out the analyses and are also meaningful on their own.\n\n\n**Weakness**\n\n- **W1.** To the best of this reviewer's understanding, most of the techniques used in the theoretical analyses are extended versions of the techniques used for function minimization or merely the $L$-Lipschitz setup. The extension may not be trivial, but it seems like something that could be expected. However, this reviewer does not consider this a weakness, though it may have contributed to a slightly more moderate overall assessment.", "was_revised": true, "final_justification": "I believe that minimizing the norm of a monotone and $L$-Lipschitz continuous operator is one of the standard setups in optimization theory. I view this as a classic setup, similar to the minimization of an $L$-smooth convex function. Moreover, I think the Extragradient (EG) method in this setup is as classic as Gradient Descent (GD) is in $L$-smooth convex minimization. And I view this paper as a theoretical work.\n\nI believe it is meaningful to question what the possible applications of a setup might be. However, I am not sure that this point can be the main criterion for judging this paper. The monotone and $L$-Lipschitz operator setup is already a classic framework, and this paper considers a more advanced setup. Additionally, I think this paper provides good examples highlighting improvements over the existing $L$-Lipschitz monotone setup. Criticizing this paper based on the usefulness of the setup sounds to me like rejecting a large portion of the optimization theory field. That said, I understand that some may have a lower preference for theory papers. Nonetheless, I value theoretical contributions and therefore vote to accept.\n\nAnd, as mentioned in my review, to the best of my understanding, some reviewers seem to have concerns regarding the comparison of this work with PPM or Halpern. Carefully speaking, I think that criticism is not appropriate. To the best of my knowledge, relating methods in fixed-point problems to the monotone operator setup requires considering a proper equivalence that involves the proximal operation. Therefore, I believe that if we want to relate fixed-point problems to monotone operator norm minimization, it should be viewed as an implicit setup. PPM (Proximal Point Method) indeed requires the proximal operation, and Halpern is a technique considered to improve the convergence of methods for fixed-point problems (at least in the referenced work). Just as we can't say “GD is slower than PPM” because they belong to different setups (when considering function value minimization), I think it is difficult to make a direct comparison between EG and PPM or Halpern.", "rebuttal": "We thank the reviewer for the positive evaluation of our work. We address the questions and concerns raised by the reviewer below.\n\n## Weaknesses\n\n> ...The extension may not be trivial, but it seems like something that could be expected.... + ....  Is there a significant technical difficulty compared to the function minimization problem or the standard Lipschitz ..] \n\nThank you for the question. Compared to the literature in the minimization setting, our submission solves unconstrained variational inequality problems with the extragradient method. Our submission has no notion of functional values in contrast to the minimization analysis, and moreover, the extragradient method has an extrapolation step, which introduces further challenges. The proof technique of analyzing the extragradient methods is very different from the methods used in minimization problems. \n\nCompared to the analysis of extragradient method under Lipschitz assumption, this new assumption introduces further challenges. In the submission we have, the $\\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, which involves a more general bound of the form $L_0 + L_1 \\max_{\\theta \\in [0,1]} \\| F(\\theta x + (1 - \\theta) y) \\|^{\\alpha}$ instead of the standard Lipschitz constant L. This generalization makes the analysis significantly more challenging. For example, in the standard L-Lipschitz case, one can easily bound $\\| F(x_k) - F(\\hat{x}_k) \\|^2$ by $L^2 \\| x_k - \\hat{x}_k \\|^2$, which appears in line 9 of the proof of Theorem 3.2 (Appendix page 24). However, under the $\\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, it introduces a much involved term, which complicates the analysis. \n\nThis difficulty motivates the use of an adaptive step size of the form $\\eta / (L_0 + L_1 \\|F(x_k)\\|^{\\alpha})$,\nwhich is better suited for this setting. Moreover, throughout the analysis, several steps require us to carefully use the structure of the $\\alpha$-symmetric Lipschitz condition and develop proof techniques that differ from those used under the standard Lipschitz assumption.\n\n## Questions\n\n> ...the authors state that the results in their paper recover the result in [Gorbunov et al., 2022b]. However, as the title of the cited paper suggests...]** Thank you for the question. Although [1] only emphasizes last-iterate convergence in its title, which is indeed their main contribution, the paper also provides an ergodic convergence rate, as stated in Theorem 3.1. We hope this clarifies the confusion, and we will include this clarification in the updated version of the submission.\n\n**We hope we have addressed all the questions and concerns of the reviewer. If not, please let us know so we can respond accordingly.**\n\n## References\n\n[1] Gorbunov, Eduard, Nicolas Loizou, and Gauthier Gidel. \"Extragradient method: O (1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022."}, {"review_id": "KQXXe6ye7J", "reviewer": "Reviewer_bk47", "summary": "This paper studies the extragradient method (EG) for variational inequality problems under the assumption that the operator in question satisfies the recently introduced $\\alpha$-symmetric $(L_0,L_1)$-Lipschitz condition. Under this assumption, a new step-size rule for EG is proposed. Convergence of EG under various additional assumptions on F (strongly monotone, monotone, and weak Minty condition) are shown. The paper is rounded out by a short experimental section.", "questions": "- How easily do your results extend to the true VI problem, where there is a non-trivial constraint set?\n - Could you apply your analysis to, say, the optimistic gradient method?\n - The definition of $\\alpha$-symmetric is new to me and very interesting. It feels somehow 'dual' to Holder continuity. Is there a reason for choosing to focus on $\\alpha$-symmetry as opposed to Holder continuity in this setting?\n - I'm not familiar with the weak Minty condition. Could you provide some intuition for why this is interesting? Is there an analogue of this condition in the convex optimization world? (like the analogue between (strong) monotonicity and (strong) convexity)?\n - In the proof of Theorem 3.4, in the ninth line, I believe there is a sign error. I think $-\\gamma^2_k\\|F(x_k) - F(\\hat{x}_k)\\|^2$ should be $+\\gamma^2_k\\|F(x_k) - F(\\hat{x}_k)\\|^2$. It seems this will affect some of the constants in the statement of the theorem. Relatedly, the first 9 lines of the proofs of Theorem 3.4 and Theorem 3.2 are the same, so I suggest you package them into a lemma.\n - Similarly, there is duplication in the first several lines of the proofs of Theorems 3.5 and 3.7 which might benefit from being packed into a lemma.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strengths\n - Writing is clear and easy to follow\n - Theorems are presented in an easy to digest manner. The proofs are well-structured.\n - Variational inequalities are a topic of perennial importance to the optimization/ML community, so this work is likely to be of interest.\n - I like the extension to \"weak Minty\" operators, which is not something I've seen before. It's good to see some results under assumptions weaker than monotonicity.\n\n### Weaknesses\n - In my opinion, the biggest weakness of this paper pertains to its scope/significance. Specifically:\n\t - The authors focus on unconstrained variational inequalities, which might more appropriately be called root-finding problems. This makes comparisons with prior work, particularly [Vankov 2024] somewhat misleading. \n\t - The authors focus only on extragradient. It would be nice to see if this analysis applies to similar methods, e.g. KM iteration, optimistic gradient method.\n - It would also be good to see some discussion of, and comparison to Halpern-style methods [Park & Ryu].\n - Although the new step-size rule is nice, it requires knowing three parameters ($L_0,L_1,\\alpha$) of $F$. Step-sizes based on the Lipschitz assumption just require one parameter $L$. This should probably be discussed somewhere.\n\n### Typos etc\n - line 674: \"maximum eigenvalue $\\sqrt{2}$ \" should be $2$. \n - line 690--691: \"We add the details of this example to 691 Appendix ??.\" is probably a typo.\n - lines 707--708 duplicate said in lines 705--706.\n - line 714: Can you change the label \"Proposition C.1.\" --> \"Proposition 3.1\" ? Same for all Theorem/Proposition statements in the appendix.\n - In the proof of Theorem 3.2: the (7) over the first inequality should be (8). Similarly for the proof of Theorem 3.4\n - In final line of proof of Theorem 3.2 suggest using square brackets $[\\ldots ]$ in addition to parentheses $(\\ldots)$ as the final factorization is a bit challenging to parse.\n - line 729: I think you want $x=x_{*}$ so that $F(x_{*}) = 0$.  Same for line 761\n\n### References\n[Vankov 2024]: _Generalized Smooth Variational Inequalities: Methods with Adaptive Stepsizes_ Vankov _et al_ (ICML2024)\n\n[Park & Ryu]: _Exact Optimal Accelerated Complexity for Fixed-Point Iterations_ Park & Ryu (ICML2022)\n\n\n-----\n\nAfter author-reviewer discussion, I raised my score 3 --> 4.", "was_revised": true, "final_justification": "See discussion below.", "rebuttal": "We thank the Reviewer bk47, for reading our work carefully and providing us with a valuable review. We respond to the questions and concerns raised by the reviewer below.\n\n## Weaknesses\n> ....This makes comparisons with prior work, particularly [Vankov 2024] somewhat misleading.... \n\nThanks for the suggestion. We use unconstrained variational inequalities because they are extensively used as terminology in several papers over the last few years. This paper provides an analysis of the extragradient method under $\\alpha$-symmetric $(L_0, L_1)$ Lipschitz assumption, and to the best of our knowledge, [1] is the only prior work that addresses this, even if in a different setting (constrained VIPs). We intended to ensure that we provide proper credit and offer a fair comparison with existing literature.\n\n> The authors focus only on extragradient. It would be nice to see if this analysis applies to similar methods, e.g. KM iteration, optimistic gradient method\n \n**We do not view this as a weakness of our work.** Prior to this, even the convergence behavior of the extragradient method under generalized Lipschitz conditions was not fully understood. In this paper, we improve the convergence rate for strongly monotone problems and provide the first analysis for monotone and weak Minty problems under $\\alpha$-smmteric $(L_0, L_1)$ Lipschitz assumptions. These results lay the groundwork for extending the analysis to more advanced algorithms such as the optimistic gradient method and KM iteration. We appreciate the reviewer’s suggestion, and exploring such extensions is indeed on our research agenda. \n\nTypically, in the limited conference space, a paper can focus on one algorithm and understand the behavior in depth in different important settings, or focus on a setting and explore the behavior of different algorithms. Having several methods in all different settings can be quite challenging in a limited number of pages with a proper exposition.  \n\n> It would also be good to see some discussion of, and comparison to Halpern-style methods [Park & Ryu]. \n\nThank you for the suggestion. We will include a discussion in the updated version comparing our results with the Halpern iteration method [2]. **However, this is not a weakness of our work.** We would like to emphasize that [2] analyzes under the standard L-Lipschitz assumption, whereas our analysis is conducted under the more general $\\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption. Therefore, the settings are not directly comparable.\n\n> Although the new step-size rule is nice, it requires knowing three parameters (L_0, L_1, \\alpha) of F....\n\nYes, Reviewer bk47 is correct in observing that solving this more general class of problems requires knowledge of three parameters, in contrast to standard L-Lipschitz settings. **However, this is not a limitation of our work.** The problem class we consider is significantly more general and complex, and thus naturally demands more information for effective algorithm design and analysis. That said, developing methods that do not require prior knowledge of these parameters, i.e., tuning-free algorithms for this broader class of problems, is an exciting direction for future research.\n\n> Typos \n\nWe appreciate the reviewer for carefully reviewing the appendix and identifying the typos. We agree with all the typos mentioned and will make the necessary corrections in the updated version.\n\n## Questions\n\n> How easily do your results extend to the true VI problem, where there is a non-trivial constraint set?\n\nExtending the algorithm to handle non-trivial constraint sets would require significant modifications. In particular, solving the constrained version would involve incorporating projections in both the extrapolation and update steps. Additionally, the presence of projections would also affect the step size choices in that scenario.\n\nFor these reasons, we focus on the unconstrained setting in this work, as it lays the theoretical groundwork and provides key insights that can facilitate the analysis of more complex algorithms for constrained problems in the future. It is definitely on our to-do list to extend the analysis to a constrained setting in the future.\n\n> Could you apply your analysis to, say, the optimistic gradient method?\n\nAs mentioned earlier, this is one of the directions we intend to explore in future work. We firmly believe that our proof technique can be extended to analyze the optimistic gradient method and KM iterations under the $\\alpha$-symmteric $(L_0, L_1)$ Lipschitz assumption.\n\n> Is there a reason for choosing to focus on ... \n\nThank you for the question. The $\\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption was introduced because many deep learning problems appear to satisfy this condition empirically in the minimization setting with the operator replaced by the gradient of the objective function. We provide a detailed discussion motivating this assumption between lines 32–65 in the introduction, along with illustrative examples in Section 2.2. Our analysis under this assumption is purely motivated by its relevance and empirical support in practical scenarios.\n\n> I'm not familiar with the weak Minty condition. Could you provide some intuition for why this is interesting?.. \n\nThe weak Minty condition was first introduced in [4]. General unconstrained variational inequality problems are known to be computationally intractable, which has motivated the search for structural assumptions that allow for meaningful convergence guarantees. Among the known conditions, the weak Minty condition is currently the most relaxed assumption under which convergence of algorithms can be established.\n\n> In the proof of Theorem 3.4, in the ninth line, I believe there is a sign error. \n\nThank you for the pointer. The expressions in lines 9 and 10 contain a typo, which is corrected in line 11 of the same proof. As a result, this does not affect any of the constants appearing in the final result of Theorem 3.4. We will correct the typo in the updated version of the paper.\n\n> ..so I suggest you package them into a lemma...\n\nThanks for the suggestion. We will incorporate this in the revised version of the paper.\n\n**We hope we have addressed all the questions and concerns of the reviewer. If you agree, please consider increasing your score. If not, please let us know so we can respond accordingly.**\n\n## References\n\n[1] Vankov, Daniil, Angelia Nedich, and Lalitha Sankar. \"Generalized smooth variational inequalities: Methods with adaptive stepsizes.\" Forty-first International Conference on Machine Learning. 2024.\n\n[2] Park, Jisun, and Ernest K. Ryu. \"Exact optimal accelerated complexity for fixed-point iterations.\" International Conference on Machine Learning. PMLR, 2022.\n\n[3] Zhang, Jingzhao, et al. \"Why gradient clipping accelerates training: A theoretical justification for adaptivity.\" arXiv preprint arXiv:1905.11881 (2019)."}, {"review_id": "gyBybj1dmk", "reviewer": "Reviewer_tsMk", "summary": "The paper extends extragradient methods to variational inequality problems with relaxed assumptions. Most existing work assumes an L-Lipschitz condition on the operator. This paper relaxes this to the more general $\\alpha$-symmetric $(L_0,L_1)$-Lipschitz condition. This condition has been studied in the past under a wide range of contexts and captures a number of basic loss functions that the standard L-Lipschitzness cannot capture. \n\nThe paper has a few main contributions. The first is that they tighten existing analysis based on extragradient methods. Concretely, consider the function $f(x) = \\log (1+\\exp(-a^{\\top}x))$. This function is $\\|a\\|^2$ Lipschitz under the standard definition but it is also $\\alpha$-symmetric $(L_0,L_1)$-Lipschitz with $\\alpha = 1$, $L_0 = 1$, $L_1 = \\|a\\|$. When $\\|a\\|>>1$ then these new methods significantly improve upon existing ones. The second contribution is that they give the first convergence analysis of EG methods for weak minty variational inequality problems under this generalized smoothness. The third contribution is that the step size considered for the EG algorithm is new and is adaptive. The rates of convergence in all cases improve upon previous works.", "questions": "1. Can the authors give some more information on the methods used to solve these generalized smooth problems? It seems like they are focussed entirely on EG methods, which I am not sure give the best rates of convergence compared to other prox point methods.\n2. A complete algorithm box would certainly help.\n3. It is not clear what the main challenge is with generalizing the EG methods to this setting. Maybe a bit more description on this would help.", "limitations": "I am not sure I see where these are addressed explicitly.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper provides a new EG algorithm and the only one which works for VIPs under the generalized smoothness condition. Their algorithm improves upon previous works. The key improvement is via their new adaptive step size.\n\nWeaknesses:\n\nI am not entirely sure of the exact algorithm used in implementations and also the one analyzed. Maybe an algorithm box would help. Also the paper only talks about EG methods. It is not clear if there are other existing works based on other methods that show convergences for these kinds of problems.", "was_revised": true, "final_justification": "Based on the justifications and rebuttal, I would like to retain my score.", "rebuttal": "We thank the reviewer for a positive evaluation of our work and for providing us with valuable questions and comments. We respond to the questions and concerns below.\n\n## Weakness\n> I am not entirely sure of the exact algorithm used in implementations and also the one analyzed. Maybe an algorithm box would help.] + [...A complete algorithm box would certainly help... \n\nThat is an excellent suggestion. We will incorporate that in the updated version of the paper. \n\n## Questions\n\n> Also the paper only talks about EG methods. It is not clear if there are other existing works based on other methods that show...\n\nIn this work, we analyze the extragradient (EG) algorithm under the $\\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption. To the best of our knowledge, [1] is the only work that analyzes extragradient, past extragradient, and the projection method under this assumption. We have included a comparison with this work for EG, and we will include the comparison with the other two algorithms in the updated version.\n\n> It is not clear what the main challenge is with generalizing the EG methods to this setting. Maybe a bit more description on this would help.\n\nIn this work we analyze the extragradient method under the $\\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, which involves a more general bound of the form $L_0 + L_1 \\max_{\\theta \\in [0,1]} \\| F(\\theta x + (1 - \\theta) y) \\|^{\\alpha}$ instead of the standard Lipschitz constant L. This generalization makes the analysis significantly more challenging. For example, in the standard L-Lipschitz case, one can easily bound $\\| F(x_k) - F(\\hat{x}_k) \\|^2$ by $L^2 \\| x_k - \\hat{x}_k \\|^2$, which appears in line 9 of the proof of Theorem 3.2 (Appendix page 24). However, under the $\\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, it introduces a much involved term, which complicates the analysis.\n\nThis difficulty motivates the use of an adaptive step size of the form $\\eta / (L_0 + L_1 \\|F(x_k)\\|^{\\alpha})$, which is better suited for this setting. Moreover, throughout the analysis, several steps require us to carefully use the structure of the $\\alpha$-symmetric Lipschitz condition and develop proof techniques that differ from those used under the standard Lipschitz assumption.\n\nWe hope this clarifies the technical challenges involved in working under this more general setup. We can easily include this discussion in the updated version of our submission.\n\n**We hope we have addressed all the questions and concerns of the reviewer. In our opinion, all concerns raised are clarification points and not really weaknesses of our work.  If you agree, please consider increasing your score. If not, please let us know so we can respond accordingly.**\n\n## References\n\n[1] Vankov, Daniil, Angelia Nedich, and Lalitha Sankar. \"Generalized smooth variational inequalities: Methods with adaptive stepsizes.\" Forty-first International Conference on Machine Learning. 2024."}]

Author rebuttal:

Meta-review: This work focuses on solving root-finding problems, by relaxing the standard Lipschitzness assumption to an L0,L1 Lipschitzness, motivated by the recent advances in the minimization case.

The reviewing team found the developments interesting since they provided a new setting under which the classical extragradient method is analyzed and the reviewers thought that the techniques in this paper could be of value in the future to solve more complicated variational inequalities.

One main concern about this paper is regarding its motivation. Indeed, the L0-L1 smoothness in minimization arose from some interesting examples, whereas in this work, it seems to me that the extension is lacking motivation. When it comes to VIs, constraints are very important for handling even the most basic of interesting problem classes that require VI solvers (such as constrained optimization or matrix games).

Another remark from the discussion phase was: "The proposed step size requires knowing three parameters. Without a clear motivating example, its not clear if the juice is worth the squeeze."

The work needs to be polished further, especially in the appendix: It is not only that long equality chains such as those in pages 24, 26, 28, 31 and 32 are not the easiest to read, but also that many estimates are out of bounds, such as page 30 (here, even the equation numbering is covered with symbols), page 27, 26 and so on. 

In summary, the authors are strongly recommended to provide **precise** motivating examples for their new assumption, in line with the discussion process between the authors and the AC and polish their proofs. Moreover, they should make sure to use the precise terminology to differentiate between VIs and root-finding problems and acknowledge clearly in their paper the shortcoming of their results (not able to handle constraints) and acknowledge clearly that extension to general VI is an open question.
Decision: Accept (poster)