Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions
Authors: Sayantan Choudhury
Eduard Gorbunov
Nicolas Loizou
Venue: NeurIPS 2023 poster (2023)
Keywords: Optimization
Machine Learning
Extragradient Methods
Min-Max Optimization
TL;DR: We provide an efficient convergence analysis of single-call  stochastic extragradient methods for solving structured non-monotone VIPs.

Abstract: Single-call stochastic extragradient methods, like stochastic past extragradient (SPEG) and stochastic optimistic gradient (SOG),  have gained a lot of interest in recent years and are one of the most efficient algorithms for solving large-scale min-max optimization and variational inequalities problems (VIP) appearing in various machine learning tasks. However, despite their undoubted popularity, current convergence analyses of SPEG and SOG require strong assumptions like bounded variance or growth conditions. In addition, several important questions regarding the convergence properties of these methods are still open, including mini-batching, efficient step-size selection, and convergence guarantees under different sampling strategies. In this work, we address these questions and provide convergence guarantees for two large classes of structured non-monotone VIPs: (i) quasi-strongly monotone problems (a generalization of strongly monotone problems) and (ii) weak Minty variational inequalities (a generalization of monotone and Minty VIPs). We introduce the expected residual condition, explain its benefits, and show how it allows us to obtain a strictly weaker bound than previously used growth conditions, expected co-coercivity, or bounded variance assumptions. Finally, our convergence analysis holds under the arbitrary sampling paradigm, which includes importance sampling and various mini-batching strategies as special cases.

Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions
Sayantan Choudhury AMS & MINDS Johns Hopkins University
Eduard Gorbunov MBZUAI
Nicolas Loizou AMS & MINDS Johns Hopkins University
Abstract
Single-call stochastic extragradient methods, like stochastic past extragradient (SPEG) and stochastic optimistic gradient (SOG), have gained a lot of interest recent years and are one of the most efficient algorithms for solving large-scale min- max optimization and variational inequalities problems (VIP) appearing in various machine learning tasks. However, despite their undoubted popularity, current convergence analyses of SPEG and SOG require strong assumptions like bounded variance or growth conditions. In addition, several important questions regarding the convergence properties of these methods are still open, including mini-batching, efficient step-size selection, and convergence guarantees under different sampling strategies. In this work, we address these questions and provide convergence guarantees for two large classes of structured non-monotone VIPs: (i) quasi- strongly monotone problems (a generalization of strongly monotone problems) and (ii) weak Minty variational inequalities (a generalization of monotone and Minty VIPs). We introduce the expected residual condition, explain its benefits, and show how allows us to obtain a strictly weaker bound than previously used growth conditions, expected co-coercivity, or bounded variance assumptions. Finally, our convergence analysis holds under the arbitrary sampling paradigm, which includes importance sampling and various mini-batching strategies special cases.
Introduction
Differentiable game formulations where several parameterized models/players compete to minimize their respective objective functions have recently gained much attention from the machine learning community. Some landmark advances in machine learning that are framed as games (or in their simplified form as min-max max optimization problems) are Generative Adversarial Networks (GANs) [19, 21. adversarial training of neural networks [46, 72], reinforcement learning [9, 64), and distributionally robust learning [51, 73).
In this work, we consider a more abstract formulation of the problem and focus on solving the following unconstrained stochastic variational inequality problem (VIP):
"
Find x" E IR such that F(x*) = Σ F((x")= =0
where each F; Rd + Rd is a Lipschitz continuous operator. Problem (1) generalizes the solution of
several types of stochastic smooth games [16, 44, 20, 7]. The simplest example is the unconstrained min-max optimization problem (also called a zero-sum game):
Σ (2),
min at ER
max EER
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

where each component function 9: : Rd x I + R is assumed to be smooth. In this scenario.
operator F; of (1) represents the appropriate concatenation of the block-gradients of g (x := Vzg9i (11,
where I == (x1 #2). Solving (1) then amounts to finding stationary point x= (.];+>) x2)) for (2), which under a convex-coneavity assumption for gr, implies
that it is global solution for the min-max problem.
However, in modern machine learning applications, game-theoretical formulations that are special cases of problem (1) are rarely monotone. That is, the min-max optimization problem (2) does not satisfy the popular and well-studied convex-concaye setting. For this reason, the ML community started focusing
non-monotone problems with extra structural properties. In this work, we focus on such settings (structured non-monotone operators) for which we are able provide tight convergence guarantees and avoid the standard issues (like cycling and divergence of the methods) appearing in the more general non-monotone regime. In particular, we focus on understanding and efficiently analyze the performance of single-call extragradient methods for solving (i) j--uassi- strongly monotone VIPs [44, 6] and (ii) weak Minty variational inequalities [14, 33].
Classes of structured non-monotone VIPs. Throughout this work assume that operator F in (1) is -- Lipschit i.e. Vx, y E TRd operator F satisfy || [F(x) F(y)l v L|| yll-
As we have already mentioned, in this work, we deal with two classes of structured non-monotone problems: the μ-quasi strongly monotone VIPs and the weak Minty variational inequalitics.
Definition 1.1. F is said to be u-quasi strongly monotone if there is > 0 such that:
Vz Rd
(F(x), x²) 2 p|| 1²1
Condition (3) is relaxation of ju-ttrong monotonicity, and it includes several non-monotone games as special cases [44]. Inequality (3) can be seen as an extension of the popular quasi-strong convexity assumption from optimization literature [53, 25] to the VIPs [44]. In the literature of variational incquality problems, quasi strongly monotone problems are also known as strong coherent VIPs [66]
or VIPs satisfying the strong stability condition [47], strong Minty variational incquality [14].
One of the weakest possible assumptions on the structure of non-monotone VIPs is the weak Minty variational inequality [14].
Definition 1.2. We say weak Minty Variational Inequality (MVI) holds for F if for some p >> 0:
Vx
Rd -P(x),===))) -
(4)
To the best of our knowledge, the weak Minty variational inequality (4) as an assumption was first introduced in [14]. The more popular and extensively studied Minty variational inequality [12, 37,
38, 48] a particular case of (4) with p = O. In addition, the weak MVI condition is implied by the negative comonotonicity [4] equivalently, the positive cohypomonotonicity [11]. Finally, when we focus on min-max optimization problems (2), weak MVI condition (with p = 0) is satisfied for several non-convex non-concave families of min-max objectives, including quasi-convex quasi-coneave or star convex- star concave [20]. Extragradient-type methods for solving VIPs satisfying the weak MVI
have been proposed in [14, 54] and [8].
1.1
Main Contributions
Our main contributions are summarized below.
Expected Residual. We propose the expected residual (ER) condition for stochastic variational inequality problems (I). We explain the benefits of ER and show how can be used derive an upper bound on E]] (see Lemma 3.2) that it is strictly weaker than the bounded variance assumption and "growth conditions" previously used for the analysis of stochastic algorithms for solving (1). We prove that ER holds for a large class of operators, i.e., whenever F; of (1) are Lipschitz continuous.
Novel Convergence Guarantees. We prove the first convergence guarantees for SPEG (7) in the quasi-strongly monotone (3) and weak MVI (4) cases without using the bounded variance
'The computation of approximate first-order locally optimal solutions for general non- monotone problems (without extra structure) is intractable. See [13] and [14] for more details.

---

Table 1: Summary known new convergence results vensions SEG and SPEG with constant step applied to solve quasi- strongly monotone variational inequalities and variational inequalities with operators satisfying Weak Minty condition. Columns: "Setup" = quasi-strongly monotone or Weak MVI: "No UBV?"= the result derived without bounded variance assumption:: "Singlo-call"" does the method require oracle call per iteration.. "Convergence rate" rale of convergence noglocting numerical factors. Notation: K number iterations; Linax = [ [n] L,, where L, is Lipschitz constami of F;; F Limi Hs. where μ4, is quasi strong monotonicity constant of (see details in [20]]: Ls.
Eis [i IlI constant of F; quasi-strong monotenicity constant of F; 5, parameters from (8); parameter from Weak Minty condition; hatchsize.
Eis
Li: a- Ei= F. F1,(())))) ; Lipschitz
Seuu
Methodd
No URV!
Singlo-callP
Convergence
S-SEG-US
[20)
x
Emax
exp
Fmax
S-SEG-IS
T exp
[20]
Quasi-stoeg mon.
SPEG
[28]
x
/
exp
23)
oZ nax
SPEG
(This work))
/
max
exp
min t.
R
R
SEG+
[14]
x3
x
L 1'-x-=-11
o²
OGDA+
x3
[leg "|
Weak MVF
[X]
Nacia-p)
+12acia-p
SPEG (This works)
Laya
1=0-2"12
48
Eoprauyy
Quasi-strong monotonicity of all F; is assumed.
(2) assumed that holds with
O.
[28] do derive this result hut it can be obtained from their proff using standard choice of step-sizes.
All mentioned results in this case require large batchsizes r = O(K) to get (1/K) rate.
(9) The result is derived for p < 1/s/IL.
(6) The result is derived for p < 9/sz. Here a and c are assumed to satisly aL S I-V1+4822
8(14c)
c Dand a > p.
(1) The result derived for p 1/2r. Here assume that max, 1/(ara) < and 0 < < min(y 2p, (4 (4-41//ar...
assumption. We achieve that by using the proposed (ER) condition. In particular, for the class of quasi-strongly monotone VIPs, we show a linear convergence rate to neighborhood of xx when constant step-sizes are used. We also provide theoretically motivated step-size switching rules that guarantee exact convergence of SPEG to x". In the weak MVI case, we prove the convergence of SPEG for p < 1/21, improving the existing restrictions on p. We compare our results with the existing literature in Table 1.
Arbitrary Sampling. Via stochastic reformulation the variational inequality problem (1) we explain how our convergence guarantees of SPEG hold under the arbitrary sampling paradigm. This allows us to cover a wide range of samplings for SPEG that were never considered in the literature before, including mini-batching, uniform sampling, and importance sampling special cases. In this sense, our analysis of SPEG is unified for different sampling strategies. Finally, to highlight the tightness of our analysis, show that the best-known convergence guarantees of deterministic PEG for strongly monotone and weak MVI can be obtained as special cases of our main theorems.
2 Stochastic Reformulation of VIPs & Single-Call Extragradient Methods
In this work, we provide a theoretical analysis of single-call stochastic extragradient methods that allows us to obtain convergence guarantees of any minibatch and reasonable sampling selection. We achieve that by using the recently proposed "stochastic reformulation" of the variational inequality problem (1) from [44]. That is, to allow for any form of minibatching, we use the arbitrary sampling notation
x3
g(z) (z)
Fz()).
(5)
n
where v E T& is a random sampling vector drawn from a user-defined distribution D such that
Ep [u:] 1, for i I, I....,h n. ,. In this setting, the original problem (1) can be equivalently written as,
Find x- E Id Ep F((x)) = Fx(( = 0,
(6)
where the equivalence trivially holds since Ex(F.(x)] ΣE Eplu:]F(()) = =F())
3

---

In this work, we consider Stochastic Past Extragradient Method (SPEG) applied to (6):
f = .kk - -7 Fo. 1
2k+1 = 21, Fu. (fx)
where ش-1 = To and v* is sampled i.idd at each iteration and T > and We > are the extrapolation step-size and update step-size respectively. We note that in our convergence analysis, we allow selecting any distribution that satisfies Ep |/] = 1 Vi. This means that for a different selection of D, (7) yields different interpretations of SPEG for solving the original problem (1).
One example of distribution is r-minibatch sampling, which is defined as follows.
Definition 2.1 (7-Minibatch sampling). Let [n]. We say that 2" is r-minibatch sampling if for every subset S E [n] with [S] = т. we have that [v = Eies cs]
r!(n-r)!
m
By using a double counting argument, one can show that if is a T- r-minibatch sampling, it is also a valid sampling vector (E [vy] = 1) [25]. We highlight that our analysis holds for every form of minibatching and for several choices of sampling vectors u. Later in Section 5, we provide more details related non-uniform sampling.
addition, by Definition 2.1, it is clear that if r = n, then 0 1 for all i [rr]. Later in Section 4, we prove how our analysis captures the deterministic Past Extragradient Method as a special case.
In [44], an analysis of stochastic gradient descent-ascent (Tx+1 Ig - F. (xrg)) under the arbitrary sampling paradigm was proposed for solving star-co-ceereive VIPs. Later [20], extended this approach and provided general convergence guarantees for stochastic extragradient method (SEG) (a stochastic variant of the popular extragradient method [32, 30)) for solving quasi-strongly monotone and monotone VIPs. Despite its popularity, SEG requires two oracle calls per iteration which makes it prohibitively expensive many large-scale applications and not easily applicable to the online learning problems [18]. This motivates us to explore in detail the convergence guarantees of single-call variants of extragradient methods (extragradient methods that require only a single oracle call per iteration).
On Single-Call Extragradient Methods. The seminal work of [56] the first paper that proposes the deterministic Past Extagradient method. In the stochastic setting, [28] provides an analysis of several stochastic single-call extragradient methods for solving strongly monotone VIPs. [28], was also shown that in the unconstrained setting, the update rules of Past Extragradient and Optimistic Gradient are exactly equivalent (see also Proposition B.6 in appendix). Through this connection, and via stochastic reformulation (6) our theoretical results hold also for the Stochastic Optimistic Gradient Method (SOG): Zx++1 = Ty Fo.Fog (Ix) 7h (Fe, (2t) Fo._,(xk-11)
(Zx-1)). [8] provides
the convergence guarantees of SOG for weak MVI. To the best of our knowledge, our work is the
first that provides convergence guarantees for SOG under the arbitrary sampling paradigm (captures
sampling beyond uniform sampling) and also without using the bounded variance assumption.
3 Expected Residual
In our theoretical results, we rely on Expected Residual (ER) condition. In this section, we define ER and explain how it is connected with similar conditions used in optimization literature. We further provide sufficient conditions for ER to hold and prove how it can be used to obtain a strictly weaker upper bound of [x)]2 than previously used growth conditions, expected co-coereivity, or bounded variance assumptions.
Assumption 3.1. We say the Expected Residual (ER) condition holds if there is a parameter such that for an unbiased estimator g(x) of the operator F, we have
5 =110 x²1
E [[(((()) - g(x")) (F(x) F(x)))) )) <
(ER)
2
The ER condition bounds how far the stochastic estimator g(x) = F.(xx) (5) used in SPEG is from the true operator F(x). ER depends on both the properties the operator F(x) and of the selection of sampling (via g(x)). Conditions similar to ER appeared before in optimization literature but they

---

have never been used in operator theory and the analysis of SPEG. In particular, [24] used a similar condition for analyzing SGD in stochastic optimization problems but with the right-hand side of ER to be the function suboptimality f((::) f(a") (such concept is not available in VIPs). In [68] and [22], similar conditions appear under the name "Hessian variance" assumption for distributed
minimization problems. In the context of distributed VIPs, similar but stronger condition to ER is used by [5].
Bound on Operator Noise. A common approach for proving the convergence of stochastic algo- rithms for solving the VIPs assuming uniform boundedness of the stochastic operator or uniform boundedness of the variance. However, we explain below, these assumptions either do not hold or are true only for a restrictive set of problems. In our work, we do assume such bounds. Instead, we use the following direct consequence of ER.
Lemma 3.2. Let o² == E g(( I|( then
oc (operator noise at the optimum is finite). If ER holds,
E|(g())11 & 8|1z +== 2o?.
(8)
Sufficient Conditions for ER. Let us now provide sufficient conditions which guarantee that ER condition holds and give a closed-form expression for the expected residual parameter d and a [l[g(=")] Il? for the case of r-minibatch sampling (Def. 2.1).
Proposition 3.3. Let Fj of problem (1) be Li-Lisschitz operators, then ER holds. If, in addition, vector V 12 is r-minibatch sampling (Def. 2.1) then: å 2. n-z
n-1 E Li and of =
1 Σ (2
Similar results to Prop. 3.3 but under different sufficient conditions have been obtained for minibatch sampling under expected smoothness and a variant of expected residual for solving minimization problems in [25] and [24] respectively. In [44], similar proposition derived but for the much more restrictive class of co-coercive operators.
Connection to Other Assumptions. In the proofs of convergence results, the bound (8), which, as we explained above, is a direct consequence of ER. In this paragraph, we place this bound in hierarchy of common assumptions used for the analysis of stochastic algorithms for solving VIPs. In the literature on stochastic algorithms for solving the VIPs and min-max optimization problems, previous works assume either bounded operator (El (#))g(>>)) S c) [1, 52], bounded variance (Fl]g(z) - F2x)]l2 S c) [35, 69, 30] (in Appendix C we provide a simple example where bounded variance assumption does hold) or growth condition (E)lg(=)]11 S c1 (z)) + c2) [36]. In all of these conditions, the parameters c, C1, and C2 are usually constants that do not have closed-form expression. The closer works to our results are [44, 6] which assumes existence of IF
such g(x") )1 < 1p (F(z), x²)) holds. Their
that the expected co-coercivity condition (Bllg(z) convergence guarantees provide an efficient analysis for several variants SGDA for solving co- coercive VIPs. In the proposition below, we prove how these conditions are related to the bound (8) obtained using ER.
Proposition 3.4. Suppose F is a L-Lipschitz operator. Then we have the following hierarchy of assumptions:
Bounded Operator
Bounded Variance
Growth Condition
(8)
F; are L,-Lisschitz
(ER)
Expected Cocoercivity
Let us also mention that [29] provided convergence guarantee of double-oracle stochastic extragra- dient (SEG) method under the variance control condition El]g(z) F2x)]|2 < (al]æ x² + b)2 where a, b 2 0. their work, they focus on solving VIPs satisfying the error-bound condition, and they did not provide dosed-form expressions of parameters and b. Although the analysis of [29]
5

---

can be conducted with > 0. the authors only provide rates for the case a = 0. The main difference between their results (for SEG) and our results (for SPEG) is that our bound (8) is not really an assumption, but it holds for free when F; are Læ=L-ipschiz. In addition, the values of parameters d and o in (8) could have different values based on the sampling used in the update rule of SPEG.
Convergence Analysis
In this section, present and discuss the main convergence results of this work. In the first part, we focus on the ones derived for μ-quasi strongly monotone problems (3) (both for constant and decreasing step-sizes), and in the second part on the Weak Minty VIP (4).
4.1 Quasi-Strongly Monotone Problems
Constant Step-size: We start with the case of y-quasi strongly monotone problems and consider the convergence of SPEG with constant step-size.
Theorem 4.1. Let F be L--Lipschitz, jr ju-quasi strongly monotone, and ER hold. Choose step- sizes Nkk W/ such that
μ 1
< w S min
(9)
188"
4L
for all Then the iterates produced by SPEG, given by (7) satisfy
n2 S (1- will h R 24wa 2
(10)
/
where R
=
E
|| - x=1
+
22 - f 11 11 Hence, given any > 0, and choos-
ing
min 185
SPEG achieves Ellæx x²11² < after K >
4T
4867
max
8L
366
96 E
log
2n
iterations.
To the best of our knowledge, the above theorem the first result on the convergence of SPEG that does not rely on the bounded variance assumption. Theorem 4.1 recovers the same rate of convergence with the Serppendent-Saapple
SEG (I-SEG) under assumption (8) [20], although [20] simply assume (8), while we show that it follows from Assumption 3.1 holding whenever all summands F; are Lipschitz. However, the case when all F; are μı-uaasi strongly monotone and L,-Lipschitz (on average), one can use Samele SEG (S-SEG). The existing results for S-SEG have better exponentially decaying term [49, 20] then Theorem 4. 1, e.g., the case when L, L for all [n], we have 8 O(L)) meaning that the exponentially decaying term in (10) is 0 while S-SEG has much better exponentially decaying term (R exp( exp(-pt/z))).
Such discrepancy can be partially explained by the following fact: S-SEG can be seen as one step of deterministic Extragradient for stochastic operator Fo, allowing to use one-iteration analysis of Extragradient without controlling the variance. In contrast, there is no version of SPEG that uses the same sample for extrapolation and update steps. This forces use different samples for these steps and this is key reason why SPEG cannot be seen as one iteration of deterministic Extrrarrdddden for some operator. Due this, we need rely on some bound on the variance to handle the stochasticity in the updates; see also [20, Appendix F.1]. Therefore, in our analysis, we use Assumption 1. implying (8). Nevertheless,
still an open question whether it possible to improve the rate of SPEG in the case of μ-quasi strongly monotone and I. Lipschitz operators F,
To highlight the generality of Theorem 4.1, we note that for the deterministic PEG, in the definition 2.1 of minibatch sampling). In this case, Theorem 4.1 recovers
and o
(by selecting the well-known result (up 1/2 factor the rate) for deterministic PEG proposed in [17] as shown in the following corollary.
Corollary 4.2. Let assumptions of Theorem 4.1 hold and a deterministic version of SPEG is considered, i.e., 8 0, o 0. Then, Theorem 4.1 implies that for all k > 0 the iterates produced

---

by SPEG with step-sizes "/ wi w such that 0 << w S Zr satisfy Ry S 2 - 22 xx 11 + | -
Ry. where
Decreasing Step-size: In this section, we consider two different decreasing step-sizes policies for SPEG applied to solve quasi-strongly monotone problems.
Theorem 4.3. Let be L-Lipschitz, ju-quasi strongly monotone, and Assumption 3.1 hold. Let
W
if S k"
7ke Wk
26+1 (k+1)² R
if k*,
(11)
where / == min (/(84) and k- SPEG with step-sizes (11) satisfy
[4/ma)]
Then for all K k- the iterates produced by
k- 2
RB
1920 112 K
S 12
(12)
K
exp(2)
where R3x == E || - x=1 + || T |1
SPEG with step-size policy² (11) has two stages of convergence: during first k- iterations it uses constant step-size to reach some neighborhood the solution and then the method switches to the decreasing (1/2x) step-size allowing to reduce the size of the neighborhood.
For the case of strongly monotone problems (a special case of our quasi-strongly monotone setting) [28] also analyze SPEG with decreasing (1/kk) step-size" under bounded variance assumption. i.c., when (8) holds with
and some o² 0, which equivalent the uniformly bounded variance
assumption. In particular, Theorem 5 [28] states E [||EK x [|3] I a² o ( ( where C' is some numerical constant. If the problem is strongly monotone, the result of [28] is closely related to what is obtained in Theorem 4.3: the main difference in the upper-boune is that we provide an explicit form of o (1/x) term. Moreover, in contrast to the result from [28]. Theorem 4.3 holds even when
Co
5 > 0 in (8), which covers a larger class of problems.
Following [67, 20, 6]. we also consider another decreasing step-size policy.
Theorem 4.4. Let F be I.-Lipschitz, jı-quasi strongly monotone, and Assumption 3.1 hold. Let @ = min (2/(4n), H/(16)). (/(10)) If for K 2 0 step-sizes (2k, {4x)220 satisfy 7 wg and
2 if K
S
p 2
Wi ==
and k < Ko.
(13)
K >
and > kip
(K- ko)
where Ko = [K/2]. then the iterates produced by SPEG with the step-sizes defined above satisfy
64R3
{ {- min
112
1728
R& <
exp
{
K
+
(14)
Wi
16L
725
u2K
where R3x E [||0
1²1
|| fK--1l??
In contrast to (12), the rate from (14) has much better (exponentially decaying) o (1/K) term. When of is large and one needs to achieve very good accuracy of the solution, this difference is negligible, since the dominating (1/K) term is the same for both bounds (up to numerical factors). However, when o² is small enough, e.g., the model is close to over- over-parameterized, or it is sufficient to achieve low accuracy of the solution, the dominating term in (14) is typically much smaller than the one from (12). Finally, it is worth mentioning, that the improvement of o (1/k) is not achieved for free: unlike the policy from (11), step-size rule (13) relies the knowledge of the total number of steps K, which can be inconvenient for the practical use in some cases.
Similar step-size policy used for SGD [25] and SGDA [44].
'We point out the proof by [28] can be generalized to the case of constant step-size, though the authors do not consider this step-size schedule explicitly.
7

---

4.2 Weak Minty Variational Inequality Problems
In this subsection we will discuss convergence of Stochastic Past Extragradient method for Minty Variational Inequality problem. To solve the Minty variational inequality problem we use different step-sizes for SPEG iterates (7).
Theorem 4.5. Let F be L-Lipschitz and satisty Weak Minty condition with parameter 1/22L). 1 Let Assumption 3.1 hold. Assume that */k y, w = such that max (2p, 26 < < < L and
0 < < min {- 2p,
1 $ Then, for all K 2 the iterates produced by mini-batched
4T
SPEG with batch-size
328
48 -1) 2K -1)
2 max
1, (1- Ly)
(15)
(1-1n] ; '(1 [1)l|200 x=
satisfy
min ogkgk-1
E [fx)(
< C12-0=0'11 where C'= wn(( [(x++4]]
48
The above result establishes O(/K) convergence with O(K) batchsizes for SPEG applied to problems satisfying Weak Minty condition." The closest result is obtained by [8], for the same method under bounded variance assumption, i.e., when ō = 0. In particular, the result of [8] also gives (2/K) rate and requires (K)) batchsizes at each step. We extend this result to the case of non-zeroth d and we also improve the assumption on p: [8] assumes that p 3/SL. while Theorem 4.5 holds for < 1/2r. The bound on cannot be improved even in the deterministic case [23]. Moreover, it is worth mentioning that the proof of Theorem 4.5 noticeably differs from the one obtained by [8].
In the case of a deterministic oracle, we recover the best-known result for Optimistic Gradient in the Weak Minty setup [8, 23].
Corollary 4.6. Let the assumptions of Theorem 4.5 hold and deterministic version of SPEG is considered, i.e., by SPEG with step-sizes max (2p, 2L < 7 1. and 0 < w min {- 2p, ar 2 satisfy
o 0. Then, Theorem 4.5 implies that for all k: 2 0 the iterates produced
min OSkEK
[f < Clاao- -lao--='1 where C w7(1-1(++41)
48
K
5 Beyond Uniform Sampling
In this section, we illustrate the generality of our analysis by focusing on the non-uniform sam- pling. In particular, we focus on single-element sampling in which only the singleton sets (i} for i
n2} have non-zero probability of being sampled; that is, P [[[|| 1] 1. We have P e//.] Pt- [25] proved that if is a single-clement sampling. is also valid sampling vector [Ep[ = 1). With the following proposition, we provide closed-form expressions for the ER
parameter 8 and o² E Egg((")) for the case of (non-uniform) single-element sampling.
Proposition 5.1. Let F, of problem (1) be L, Li-Lipschitz operators. If, vector & E R is single element sampling then 2 Σ 1. and o² = + Σ 1 [1
Importance Sampling. In importance sampling we aim to choose the probabilities p; that optimize the iteration complexity. [25] and [20] analyze importance sampling for SGD and SEG respectively. In this work, we provide the first convergence guarantees of SPEG with importance sampling. In particular, we optimize the expected residual parameter 5 with respect to which in turn affects
the iteration complexity. Note that, by using Cauchy-Schwarr inequality (20), we have Σ L7 >
(ELL, 2.) and this lower bound can be achieved for pỘ = L./Ey=, L3- case of importance sampling, we will use these probabilities of which optimizes and define the corresponding as 81S = 2 (E L.)?. For uniform sampling (i.e. pt )). the value of the parameter is óus Ei= I.P. Note that, dis equals dus when all I,; are equal, however dis be much smaller than dus when L, are very different from each other, e.g., when all L, are relatively small (close to
"See also Appendix E.5 for discussion related the oracle complexity of Theorem 4.5.

---

zero) and one L; is large, ōis is almost n times smaller than ōus In this latter scenario (when ófs much smaller than òus). importance sampling could be useful and can significantly improve the performance of SPEG. For example, note that the exponentially decaying term in (14) decreases with 5. Hence, this term will decrease much faster with importance sampling than with uniform sampling.
6 Numerical Experiments
To verify our theoretical results, we run several experiments on two classes of problems, i.e., strongly monotone problems (a special case of the quasi-strongly monotone VIPs) and weak MVI problems. The code to reproduce our results can found at https//ggttub.oommiaaaaaaaaggggg Stoocsaaat Extragradient-Methods.
6.1 Strongly Monotone Problems
Our experiments consider the quadratic strongly-convex strongly-concave min-max prob- lem from [20]. That is, we implement SPEG on quadratic games of the form
minlERd mäXyeRd EE fi(r, where
fI xT A,T x B.y 2 C +a.x -c.-
(16)
Here A, B,, Cj are generated such that the quadratic game is strongly monotone and smooth. In all our experiments, we take n = 100 and d = 30. We generate positive semi-definite matrices A, B,, C2 such that their eigenvalues lie in the interval [u,, La]: |KB, La] and luc, Lc] respectively. In all our experiments, we consider LA- = LB = Lc = and μ4 = PC = 0.1, uu = unless otherwise mentioned. The vectors a, and e; are generated from Wo Ia). Here, the ith operator is given by
V (lla,,)) ( (,li(z,)))
[Ax + B&y aj (d:n Cay - B, x +
Fj
1/
In Figures 2, and 3, we plot the relative error the y-axis i.e.
I --p-x
1000
Constant vs Switching Step-size Rule. In Fig. 1, we illus- trate the step-size switching rule of Theorem 4.3. We place the dotted line to mark when we switch from constant step-size to decreasing step-size. In Fig. I, the trajectory switching step- size rule (11) matches that of constant step-size (9) in the first phase (where SPEG runs with constant step-size following (11). However, it becomes stagmant when the constant step- size SPEG reaches neighbourhood of optimality, In contrast, the step-size of Theorem 4.3 helps the method to converge to better accuracy.
ceiter Popseer (heeen 4:2
Decasang Eaplla (hwoor
Relative Entor
acece
wdice
00:00
110035
Number of Iteraatioss
Figure 1: Constant vs Switching
Comparison to Hsieh et al. [28]. In this experiment, we compare SPEG step-sizes proposed in Theorems 4.1 and 4.3 with step-sizes from [28]. To implement SPEG with the step-sizes from [28], we choose and such that 1 < S II and set we = 7 = Zे.. For Fig. 2a, we generate Ai, B,, C2 as before. First, we sample optimal points x", from NN Ia) and then generate such that F(x", .v) 0.
A
B C.
B
V²
In Fig. 2a, we run the algorithms on interpolated model (Fi(x*) = 0 for all i E [n]). Since the model is interpolated, we have of 0 in Theorem 4.1 and linear convergence to the exact optimum asymptotically. this setting, as shown in Fig. 2a, our proposed step-size results in major improvement compared to the decreasing step-size selection analyzed in [28]. In Fig, 2b, we compare the switching step-size rule with step-size from [28]. Fig. 2b, we generate as 6s from the normal distribution. In this plot, we manually switch the step-size from constant to decreasing after 305 steps. We observe that such a semi-empirical rule has comparable performance to the step-size selection of Hsich et al. [28].

---

10
(Teoren Decreasing sinpatee libihh 2219)
Chance dipe
13
Error
100
10-3
2000
4200
0020
0002
10200
5
12000
20002
20005
40020
50200
Number of Iterationn
Number of Iteratio
(a) Interpolated Model
(b) Non-Interpolated Model
Figure 2: Comparison of our SPEG using our step-size against decreasing step-size of Hsieh et al. [28]. In plot (a), for constant step-size of SPEG we use the upper bound of (9). In plot (b), we run our switching step-size SPEG (11).
Rulalvve Enoo
Relative Encar
fulativ
henations
teration
Reradions
(a)
(c) 10
(d) A 20
Figure 3: Comparison of SPEG with Uniform and Importance Sampling for different A (2, 10, where the eigenvalues of matrices AI, Ci uniformly generated from the interval [0.
Uniform vs. Importance Sampling. In this experiment, we highlight the advantage of using importance sampling over uniform sampling. The eigenvalues of A1, C1 are uniformly generated from the interval [0.1, A] while the rest of the matrices are generated as mentioned before. We vary the value of A E {2, 5, 10, 20} and run and compare SPEG with both uniform and importance sampling (see Fig. 3). For importance sampling, we use the probabilities
= 11/Ey-, L, In Fig. it is clear that as the value of A increases, the trajectories under uniform sampling get worse, while the trajectory under importance sampling remains almost identical. This behavior aligns well with discussion in Section 5.
6.2 Weak Minty Variational Inequality Problems
This experiment verifies the convergence guarantees SPEG
in Theorem 4.5. Following the min-max problem mentioned in [8], we consider the objective function
S160 on WMV
Squared Operator Norm Error
min max- ZER PER TO
Eizy
(a0- 12).
1 2
(17)
In this experiment, we generate &., S. such that L = 8 and p 1/32 for the above min-max problem [8]. We implement SPEG with extrapolation step 7 = 0.08 and update step w/ = 0.01 which satisfies the conditions on step-size in Theorem 4.5. In Fig. 4, we use batchsize of 6. This plot illustrates that for some weak MVI problems the requirement on the step- size from Theorem 4.5 can be too pessimistic and SPEG with relatively small batchsize achieves reasonable accuracy of the solution. The choice of batchsize ensures that bound (15) holds and small enough to guarantee convergence of SPEG. We also tried to compare SPEG with SEG+ from [54], however, the authors do not mention their choice of update step-size. We examined several decreasing update step-size for which SEG+ failed to converge. Further details on experiments can be found in Appendix G.I.
503
3300
Figure 4: Trajectory of SPEG for solving weak MVI. "Squared Operator Norm Error" in vertical axis denotes min E [[[((+)]] osksk-1 4.5.
Theo-
10

---

Acknowledgement
Sayantan Choudhury acknowledges support from the Acheson Duncan Fund for the Advancement of Research in Statistics. Nicolas Loizou acknowledges support from CISCO Research.
References
[1] Abernethy, K. A. Lai, and A. Wibisono. Last-iterate convergence rates for min-max optimiza- tion: Convergence of hamiltonian gradient descent and consensus optimization. In Algorithmic Learning Theory, pages 3-47. PMLR, 2021.
[2] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks, In ICML, 2017.
[3] S. Arora, N. Cohen, W. Hu, and Y. Luo. Implicit regularization in deep matrix factorization. NeurlPS, 2019.
[4] H. H. Bauschke, W. M. Moursi, and X. Wang. Generalized monotone operators and their averaged resolvents. Mathematical Programming, 189(1):55-74, 2021.
[5] A. Beznosikov and A. Gasnikov. Compression and data similarity: Combination of two tech- niques for communicatoon-elliceen solving of distributed variational incqualities. In Optimiza- tion and Applications: 13th International Conference, OPTIMA 2022, Petrovac, Montenegro, September 26-30, 2022, Revised Selected Papers, pages 151-162. Springer, 2023.
[6] A. Beznosikov, E. Gorbunov, Berard, and N. Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. AISTATS, 2023.
[7] A. Beznosikov, B. Polyak, E. Gorbunov, D. Kovalev, and A. Gasnikov. Smooth monotone stochastic variational incqualities and saddle point problems- survey. European Mathematical Society Magazine, 2023.
[8] A. Böhm. Solving nonconnvex-noncconave min-max problems exhibiting weak minty solutions. arXiv preprini arXiv: 12247, 2022.
[9] N. Brown, A. Bakhtin, A. Lerer, and Q. Gong. Combining deep reinforcement learning and search for imperfect-informattie games. NeurIPS, 2020.
[10] Y. Cai, A. Oikonomou, and W. Zheng. Tight last-iterate convergence of the extragradient method for constrained monotone variational inequalities. arXiv preprint arXiv:2204.09223 2022.
[11] P. L. Combettes and T. Pennanen. Proximal methods for cohypomonotone operators. SIAM journal control and optimization, 43(2):731-742, 2004.
[12] C. D. Dang and G. Lan. On the convergence properties of non-euclidean extragradient methods for variational incqualities with generalized monotone operators. Computational Optimization and applications. 60(2):277-310, 2015.
[13] C. Daskalakis, S. Skoulakis, and M. Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 1466-1478, 2021.
[14] J. Diakonikolas, C. Daskalakis, and M. Jordan. Efficient methods for structured nonconvex- nonconcave min-mat optimization. In AISTATS, 2021.
[15] R. D'Orazio, N. Loizou, I. Laradji, and Mitliagkas. On stochastic mirror descent: Convergence analysis and adaptive variants. ICML, 2021.
[16] F. Facchinei and C. Kanzow. Generalized Nash equilibrium problems. 4OR, 573::133-210, 2007.
[17] G. Gidel, H. Berard, Vignoud, P. Vincent, and S. Lacoste-Julien. variational inequality perspective generative adversarial networks. ICLR, 2019.
11

---

[18] N. Golowich, S. Pattathil, and C. Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. NeurIPS, 2020.
[19] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Bengio. Generative adversarial nets. In NeurIPS, 2014.
[20] E. Gorbunov, H. Berard, G. Gidel, and N. Loizou. Stochastic extragradient: General analysis and improved rates. In AISTATS, 2022.
[21] E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O (1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In AISTATS, 2022.
[22] E. Gorbunov, Horváth, P. Richtárik, and G. Gidel. Variance reduction is an antidote to byzantines: Better rates, weaker assumptions and communication compression cherry the top. ICLR, 2023.
[23] E. Gorbunov, A. Taylor, S. Horváth, and G. Gidel. Convergence of proximal point and extragradient-based methods beyond monotonicity: the case negative comonotonicity. ICML, 2023.
[24] R. Gower, O. Sebbouh, and N. Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. In AISTATS, 2021.
[25] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and Richtárik. Sgd: General analysis and improved rates. In /CML, 2019.
[26] Hanzely and P. Richtárik. Accelerated coordinate descent with arbitrary sampling and best rates for minibatches. In AISTATS, 2019.
[27] S. Horváth and Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. In ICML, 2019.
[28] Y.-G. Hsieh, F. lutzeler, J. Malick, and P. Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. NeurlPS, 2019.
[29] Y.-G. Hsich, F. Iutzeler, J. Malick, and P. Mertikopoulos. Explore aggressively, update conser- vatively: Stochastic extragradient methods with variable stepsize scaling. NeurIPS, 2020.
[30] A. Juditsky, A. Nemirovski, and C. Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[31] A. Khaled, O. Sebbouh, N. Loizou, R. M. Gower, and P. Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. Journal of Optimization Theory and Applications, 2020.
[32] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[33] S. Lee and D. Kim. Fast extra gradient methods for smooth structured noncomvex-nnonconcaww minimax problems. NeurlPS, 2021.
[34] C. J. Li, Y. Yu, 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 AISTATS, 2022.
[35] T. Lin, C. Jin, and M. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In ICML,, 2020.
[36] T. Lin, Z. Zhou, P. Mertikopoulos, and M. Jordan. Finite-time last-iterate convergence for multi-agent learning in games. In ICML, 2020.
[37] M. Liu, Y. Mroueh, J. Ross, W. Zhang, Cui, P. Das, and Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. ICLR, 2020.
12

---

[38] M. Liu, H. Rafique. Q. Lin, and T. Yang. First-order convergence theory for weakly- weakly-concave min-max problems. J. Mach. Learn. Res., 22:169-1, 2021.
[39] N. Loizou and P. Richtárik. A new perspective on randomized gossip algorithms. In 2016 IEEE global conference on signal and information processing (GlobalSIP), pages 440-444. IEEE, 2016.
[40] N. Loizou and P. Richtárik. Convergence analysis of inexact randomized iterative methods. SIAM Journal on Scientific Computing, 4266) 2020.
[41] N. Loizou and P. Richtárik. Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. Computational Optimization and Applications, 77(3)6653-710, 2020.
[42] N. Loizou and P. Richtárik. Revisiting randomized gossip algorithms: General framework, convergence rates and novel block and accelerated protocols. IEEE Transactions on Information Theory, (7(1 83244 2021.
[43] N. Loizou. H. Berard, A. Marttnnen,, P. Vincent, S. Lacoste-Julien, and I. Mitliagkas. Stuchastic hamiltonian gradient methods for smooth games. In ICML, 2020.
[44] 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-coereivity. NeurIPS, 2021.
[45] N. Loizou, S. Vaswani, I. Hadj Laradji, and S. Lacoste-Julien, Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In AISTATS, 2021.
[46] A. Madry, A. Makelov, Schmidt, D. Tsipras, and Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR. 2018.
[47] Mertikopoulos and Z. Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173(1):4655077, 2019.
[48] P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Op- timistic mirror descent in saddle-point problems: Going the extra (gradient) mile. ICLR, 2019.
[49] K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik, and Y. Malitsky. Revisiting stochastic extragradient. In AISTATS, 2020.
[50] A. Mokhtari, A. Ozdaglar, and S. Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In AISTATS, 2020.
[51] H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust optimiza- tion with f-divergences. NeurIPS, 2016.
[52] A. Nemirovski, A. Juditsky, G. Lan, and Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-1699 2009.
[53] Y. Nesterov. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175:69-107, 2019.
[54] Pethick, P. Patrinos, O. Fercoq, Cevherå, et al. Escaping limit cycles: Global convergence for constrained noncomvex-noonconcaee minimax problems. In ICLR, 2022.
[55] T. Pethick, O. Fercoq, P. Latafat, P. Patrinos, and V. Cevher. Solving stochastic weak minty variational inequalities without increasing batch size. ICLR, 2023.
[56] L. D. Popov. A modification of the -rrowhhuwicz method for search of saddle points. Mathe- matical notes of the Academy of Sciences of the USSR, 28(5):845-848, 1980.
[57] X. Qian, Z. Qu, and P. Richtárik. Saga with arbitrary sampling. In ICML, 2019.
13

---

[58] Z. Qu and P. Richtárik. Coordinate descent with arbitrary sampling i: Algorithms and complexity. Optimization Methods and Software, 31(5):829-855 2016.
[59] Richtárik and M. Takáč. On optimal probabilities stochastic coordinate descent methods. arXiv preprini
2013.
[60] P. Richtárik and M. Takác. Stochastic reformulations of linear systems: algorithms and convergence theory. SIAM Journal on Matrix Analysis and Applications, 41(2):887-524, 2020.
[61] M. Rolinek and G. Martius. L4: Practical loss-based stepsize adaptation for deep learning. NeurIPS, 2018.
[62] E. K. Ryu, K. Yuan, and W. Yin. Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems. arXiv preprint arXiv: 1905. 10899, 2019.
[63] O. Sebbouh, N. Gazagnadou, S. Jelassi, F. Bach, and R. Gower. Towards closing the gap between the theory and practice of svig. NeurlPS, 2019.
[64] S. Sokota, R. D'Orazio, J. Z. Kolter, N. Loizou, M. Lanctot, I. Mitliagkas, N. Brown, and C. Kroer. unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. ICLR, 2023.
[65] M. V. Solodov and F. Svaiter. hybrid approximate extragradient-proximall point algorithm using the enlargement of maximal monotone operator. Set-Valued Analysis, 7(4):323-345, 1999.
[66] C. Song, Z. Zhou, Zhou, Y. Jiang, and Y. Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. In NeurlPS, 2020.
[67] S. U. Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint arXiv:190.004232. 2019.
[68] R. Szlendak, A. Tyurin, and P. Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. ICLR, 2022.
[69] Q Tran Dinh, D. Liu, and L. Nguyen. Hybrid variance-reduced sgd algorithms for minimax problems with nonconvex-linewt function. NeurlPS, 2020.
[70] S. Vaswani, F. Bach, and M. Schmidt. Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron. In AISTATS, 2019.
[71] S. Vaswani. A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. NeurIPS, 2019.
[72] Wang, T. Zhang, S. Liu, P.-Y. Chen, Xu, M. Fardad, and B. Li. Adversarial attack generation empowered by min-max optimization. NeurIPS, 2021.
[73] Y. Yu, T. Lin, E. V. Mazumdar, and M. Jordan. Fast distributionally robust learning with reduced min-max optimization. In AISTATS, 2022.
14

---

Supplementary Material
We organize the Supplementary Material follows: Section A discusses the existing literature related to our work. In Section B. we present some technical lemmas required for our analysis, while in Section C, we provide simple problem where the bounded variance assumption does hold. Then, in Section D, we provide the proofs of propositions related to Expected Residual. Next, Section E presents the proofs of the main theorems, while a proposition related arbitrary sampling proved in Section F. Finally, additional numerical experiments are presented in Section G.
Contents
Introduction
Main Contributions
Stochastic Reformulation VIPs & Single-Call Extragradient Methods
3
Expected Residual
4
Convergence Analysis
4.1 Quasi-Strongly Monotone Problems..
4.2 Weak Minty Variational Inequality Problems
5
Beyond Uniform Sampling
8
6
Numerical Experiments
6.1
Strongly Monotone Problems
6.2 Weak Minty Variational Inequality Problems
10
Further Related Work
17
Technical Preliminaries
19
Example: Problem where the Bounded Variance Condition not Hold
20
Proofs Results on Expected Residual
D.1 Proof of Lemma 3.2
21
D.2 Proof of Proposition 3.3
22
D.3 Proof of Proposition 3.4
23
Main Convergence Analysis Results
24
E.1 Proof of Theorem 4.1
25
E.2 Proof of Theorem 4.3
26
E.3 Proof of Theorem 4.4
27
E.4 Proof of Theorem E.4
27
E.5 Proof of Theorem 4.5
33
F Further Results Arbitrary Sampling
35
E1 Proof of Proposition 5.1
35
15

---

Numerical Experiments
37
G.1 More Details on the Numerical Experiments of Section 6
37
G.2 Additional Experiments
37
G.2.1 Strongly Monotone Quadratic Game:
38
G.2.2 Weak Minty VIPs Continued
38
16

---

A Further Related Work
The references necessary to motivate our work and connect it to the most relevant literature are included in the appropriate sections of the main body of the paper. In this section, we present broader view of the literature, including more details on closely related work and more references to papers that are not directly related to our main results.
Classes of Structured Non-monotone Operators. With an increasing interest in improved computational speed, first-order methods are the primary choice for solving VIPs. However, computation of an approximate first-order locally optimal solution of a general non-monotone VIP is intractable [13, 33]. It motivates us to exploit the additional structures prevalent in large classes of non-monotone VIPs. Recently [20, 28] provide convergence guarantees of stochastic methods for solving quasi-strongly monotone VIPs, while [29] for problems satisfying error-bound conditions. [14] defined the notion of a weak MVI (4) covering classes of non-monotone VIPs.
Assumptions on Operator Noise. The standard analysis of stochastic methods for solving VIPs relies on bounded variance assumption. [8. 14, 28, 17] use bounded variance assumption (i.e. [()))(( F F(x)|12 < o² for all z) while [52, 1] assume bounded operators for their analysis. However, there are examples of simple quadratic games that do not satisfy these conditions. It has motivated researchers to look for alternattvee/ellaxd assumptions on distributions. [44] provides convergence of Stochastic Gradient Descent Ascent Method under Expected Cocoercivity. [29, 49] considered alternative assumptions for analyzing Stochastic Extragradient Methods that do not imply boundedness of the variance. However, there no analysis of single-call extragradient methods without bounded variance assumption.
Weak Minty Variational Inequalities. Numerous contemporary studies look to identify first-order methods for efficiently solving min-max optimization problems. It varies from simple convex- concave to nontrivial nonconvex nonconcave objectives. Though there has been a significant development in the convex-concave setting, [13] demonstrates that even finding local solutions are intractable for general nonconvex nonconcave objectives. Therefore, researchers seek to identify the structure of objective functions for which it is possible to resolve the intractability issues. [14] proposes the notion of non-monotonicity, which generalizes the existence of a Minty solution (i.e., p 0 in (4)). This problem is known as weak Minty variational inequality in the literature. [14, 54] provides convergence guarantees of the Extragradient Method for weak Minty variational inequality. They establish a convergence rate of O for the squared operator norm. [33] shows that it is possible to have an accelerated extragradient method even for non-monotone problems. Furthermore, [8] provides a convergence guarantee for the SOG with a complexity bound of O( 2). However, all papers exploring stochastic extragradient methods for solving weak Minty variational inequality consider bounded variance assumption [8, 14]. Moreover, all algorithms solving Weak Minty variational inequality require increasing batchsize. Recently, [55] introduced BCSEG+ which can solve weak minty variational inequality without increasing batchsize. BCSEG+ involves three oracle calls per iteration and addition of a bias-corrected term in the extrapolation step.
Arbitrary Sampling Paradigm. As mentioned in the main paper, the stochastic reformulation (6) of the original problem (1) allows us to analyze single-call extragradient methods under the arbitrary sampling paradigm. That is, provide unified analysis for SPEG that captures multiple sampling strategies, including r-minibatch and importance samplings. An arbitrary sampling analysis of stochastic optinmization method was first proposed in the context of the randomized coordinate descent method for solving strongly convex functions in [59]. Since then, several other stochastic methods were studied in this regime, including accelerated coordinate descent algorithms [58, 26], randomized iterative methods for solving consistent linear systems [60, 41, 40), randomized gossip algorithms [39, 42], stochastic gradient descent (SGD) [25, 24], and variance reduced methods [57, 27, 31]. The first analysis of stochastic algorithms under the arbitrary sampling paradigm for solving variational inequality problems was proposed in [43, 44]. In [43, 44], the authors focus on algorithms like the stochastic Hamiltonian method, the stochastic gradient descent ascent, and the stochastic consensus optimization. These ideas were later extended to the case of Stochastic Extragradient by [20]. To the best of our knowledge, our work is the first that provides an analysis of single-call extragradient methods under the arbitrary sampling paradigm.
17

---

Overparameterized Models and Interpolation. For function f(z) = Σn fa(a) we say that interpolation condition holds if there exists such that min, f((x) fi(a") for all i [n] (or equivalently Vii("") 0 for smooth convex functions) [24]. The interpolation condition is satisfied when the underlying models are sufficiently overparameterized [70]. Some known examples include deep matrix factorization and classification using neural networks [3, 61, 70]. The interpolated model structure enables SGD and other optimization algorithms to have faster convergence [24, 45, 15J. Inspired by this, one can extend the notion of the interpolation condition to operators. In this scenario, we say that the VIP (1) is interpolated if there exists solution x of (1) such that (z 0 for all E [n]. This concept has been explored for analyzing the stochastic extragradient method [71, 34]. We highlight that our proposed theorems show fast convergence of SPEG in this interpolated regime (when o 0). To the best of our knowledge, work is the first that proves such convergence for SPEG. In Fig. 2a, we experimentally verify the fast convergence for solving strongly monotone interpolated problem.
Deterministic Extragradient Methods. The Extragradient method (EG) [32] and its single-call variant, Optimistic Gradient (OG) [56], were proposed to overcome the convergence issues of gradient descent-ascent method for solving monotone problems. Since their introduction, these methods have been revisited and explored in various ways. [50] analyzed EG and OG as an approximation of the Proximal Point method solve bilinear and strongly convex-strongly concave min-max problems. [65] and [62] provide the best-iterate convergence guarantees of EG and OG with a rate of O1/K) for solving monotone problems. However, providing last-iterate convergence rate of EG and OG for monotone VIPs has been long-lasting open problem that was only recently resolved. The works of [18, 21, 10] prove last-iterate O(/K) convergence rate for these methods. Finally, in the deterministic setting, some recent works provide convergence analysis of EG and OG for solving weak MVI (4) [14, 54, 23].
18

---

B Technical Preliminaries
Throughout our work, assume
Assumption B.1. Operator F in (1) is L Lipschitz. i.., Vz, y E R2 operator F satisfies
[F(z) F(y)l - L yll.
(18)
Operators F; RRd Rd of problem (1) are L4- Lipschitz, i.e., Var, y IRd operator P; satisfies
[[](2)) F1 - L; vll-
(19)
In our proofs, we often use the following simple inequalities.
Lemma B.2. For all a, b, a1, 02 a. an E Rdd n 2 1, > O, we have the following inequalities:
{a, b)
||||||6|||
(20)
1 ||ll + 2 |612
{a,
(21)
2a
|la
b1l2
2||a|12 + 2||b|1
(22)
||]|1
|aa + bl12 - |1b11
(23)
2
n
Σ
a
71
|a.11
(24)
Inequality (22) is well known as Young's Inequality. Now, we present a simple property of unbiased estimators.
Lemma B.3. For an unbiased estimator y of operator F i.e E[g(z)] = F(z) we have
Bl]g(x) F EE [=) [3
(25)
Next, we present the following lemma from [67], which plays vital role in proving the convergence guarantee of Theorem 4.4.
Lemma B.4. (Simplified Verison of Lemma from [67]) Let the non-negative sequence {rk k20
satisfy the relation rk+1 I (1 ari )rk + cyξ for all k 2 0, parameters a, c 2 and any non-
negative sequence {7w 1220 such that 7 < for some 2 a, h O. Then for any K 2 one can choose F as follows:
1 7k
if K < a'
T
h
1
if K
and k < ku,
h"
h
if K and A 2 ko.
a(k + k ko)
where
2h and ko
For this choice of Th the following inequality holds:
32hro
aK
36c
FK <
exp
+
2h
a² K
We use the next lemma to bound the trace of matrix products.
19

---

Lemma B.5. For positive semidefinite matrices A, B E Rddd we have
tr(AB) S Amax (A),
(26)
where Amax denotes the maximum eigenvalue of B.
Next lemma proves equivalence of SPEG and SOG:
Proposition B.6 (Equivalence of SPEG and SOG). Consider the iterates of SPEG [T T. J with constant step-sizes wi: w, 7 7 in (7). Then de follows the iteration rule of SOG i.e.
kk+1
2x FvFFv (t*)
The (F (fxx Fuz-s (#x-1)l
(27)
Proof. From the update rule of SPEG (7) get
dx+1
Tk Fe, (ix)
Ik w Fr, (frx) - 7 FFr (3xx)
(w F) (fxx)
It + 7 Fon-1 (ix-1) ( () Fr. (1tk)
ix - w Fug (fx)) - 7 Fox (fx) Pue.. (ix-1))
This shows that SPEG iterations are equivalent to SOG, with dg being the k-th iterate of SOG.
C Example: Problem where the Bounded Variance Condition not Hold
Here, provide simple problem that does satisfy the bounded variance assumption. Consider the linear regression problem
1 (a 61)² + (a22 b2)
1
min (x) ZER
where R. Here fi) (aΙz 6, and f2 = (azæ b2) Now consider the estimator g(x)
of fz))) under uniform sampling i.c. g(x) takes the value (f(()) with probability and f22(2) with probability z-
Then we have
1
El]g(r) - vf(x)]²
Vf((z) vx(=) + V22(2) - vf(=)]²
2
2
2 4 [V/((a) V/2())1 1
1
2 Vf2(2> (f(()))
[Vf(z=) - [=2(2)]1
4 12(azz-bija - - 2( - b2)a2)²
- -a)p - (arb - azb2))² 2
Therefore, Bl]g(x) f= is quadratic function of with the coefficient of æ being positive. Hence, as x - 2o, we have El]g(=) - ff(=)] + co, which means that a constant can not bound the variance.
20

---

D Proofs of Results on Expected Residual
D.1 Proof of Lemma 3.2
Proof. Using Young's 's Inequality (22), we get
Bllg(=) 1 2 F(x) - (0x")|²² 21=
8||0 101==11122
x²11 -
Then breaking down the RHS, obtain
(25)
[ [= S 8 x - -= +=
Now rearrange the terms and set of: B x" )| 2/2 complete the proof of this Lemma.
Proposition D.1. If F; are I.y-lipschizz then Expected Residual condition (ER) holds. In that case
8 m
(v3))
In addition, ju-quasi strongly monotone (3) then we have
2
L B
2p
Proof. Note that
(F) Fo(x))) (F(x) =(x*))11
E( F(**)12
2E (FF F(x'))
(X),(x)- - -F("')]- - F(x*)12
(IF (F("())-F(("'))P11FF
E
(x(((x)) - -F((z)) - -IF(2)]1
Σ v((F((x) - F((2))) - [1(()))1
(24)
E(
F( |
IAG
-
(28)
The first part of the lemma follows by ignoring the positive term F ) 12. For the second part we assume F is ye-uasii strongly monotone. Then we have
u|| 1|2 (3) S (F(x), - x3) S [F())ll x"1|-
(20)
Cancelling | - x11 from both sides we get
A|ı - x0 || < [[)(]]]]
(29)
Therefore we have the following bound for yı-quasi strongly monotone operator F:
(l)(F((>) F.(x*)) (F(x) F(x*)))) ||
(28)
I
I E(
n1? |1
x= 1=12.
This proves the second part of the lemma. This lemma ensures that the Lipschitz property is sufficient to guarantce Expected Residual (ER) condition.
21

---

D.2 Proof of Proposition 3.3
Proof. Proposition D.I implies that Lipschitzness of all operators is enough ensure that ER holds.
For minibatch sampling, denote the matrix R ( ,F(( -Fxx)))(((*1) R2xx.
Then we obtain the following bound:
E (x( Fo(x*) - (F(z) - F(x)))
1/ (F((t)) - Fi(x))) - -(((()) -F((=)(())
(o:
- 1)(
B
R 1>11
n²
B(v 1)TR v 1)
n²
1 n
E
ir RTR(F 1)(1 1)T
1 n²
RTRE (o- 1)(F 1)T
1
tr
R RTRVar(ul]
n
(26)
Amaxx
Var(ul)
(r(RR)
n²
Amax
n Var (1)
[F((z) F1
n2
Amaxx (Var
[u)) x²1
D3
n²
From the proof details of Lemma F.3 in [63] we have Amax (aarx))) sampling. Thus we obtain
m(n-r) for r-minibatch r[n-1] 1)
E (x() -
- ((()))
2(n - 7)
Σ
1i11- x²1
nT(n - :=1
Now we focus on the derivation of of = (x)F(xx))) for r-minibatch sampling. We expand E|| (x as follows:
U
(x')
n
Σ
Fz(x²)
n
iEs Ps
1
E
1 LES
F((x²))
pt
LiS Pi
Fi(x*),
Σ
lEEs FF
Pj
J=1
Pu (Fi(*), Fz(a)))
(30)
2
P.Pj
where P.j = j(i,j E S) and p; P(i S). For r-minibatch sampling, we obtain P. = 7
a(n
and p; = Plugging in these values of P.y and Pt in (30) we get the closed-form expression of a² This completes the proof of Proposition 3.3.
22

---

D.3 Proof of Proposition 3.4
Here we enlist the assumptions made on operators. Suppose g is an estimator of operator F.
Bounded Operator: Bl[g(x)]| o²
2. Bounded Variance: [
- F 0²
3. Growth Condition: Elgg(>)] - a F +/3
4. Expected Co-coercivity: [l]g()) g(x )1² l (P(x),
Expected Residual: [1(((()) - (F(())))))))))((((((( - - | ---1'11 x=1
6. Bound from Lemma 3.2: [=) - | 20
Fi are Lipschitz: [1F((z) (y)l - -,| y/ vi= I.....
Proof. Here we will prove Proposition 3.4
1 2. Note that []]g(=) < 0² < [F()]]| + Bl(g(x) F(x))l < 0².
2 3. Here [=]g(() - = < o² = [ - [F(x) 1 + 0² as g is an
unbiased for estimator of F. Then take a = and 3 ==
3 + Note that [l]g(=)]1 - all (x)) ) 122 8 S aT x01 + B. The last inequality
follows from lipschitz property of F and F(x*) = 0. Then choose 5 aL and o B/2 to get the result.
Note that expected cocoercivity and L- L-Lipschitzness of F imply (g(()(
g(x))) - (F(x)) F(x")) ))[ [B]g(()) - -(x ||2 - [1 - F(x*)| < Blg(r)
g(2*)1 1| (F (F(x) - x²) (B.2) #1)) Lef || x²12 S 1=
7 + 5. This follows from Proposition D.
5 This follows from Lemma 3.2
23

---

E Main Convergence Analysis Results
First, we present some results followed by iterates of SPEG. These will play a key role in proving the Theorems later in this section. Recall that iterates of SPEG are
K = 2k - Fo. (ax-1),
Fk+1 2k Fu (f*).
Lemma E.1. For SPEG iterates with step-size we 7/k wi we have
| x 112 | fx 21 + || - x² 112 - 1 - xxll 2w (Foz (2x), In - -x)). (31)
Proof. We have
|| z²12 = 1 - 2x + 0x - 2k + 22 x=1
|,++11 - 1x + 1 1x + || - x." 1=1 + ( - Ik. Tk - x²))
+2 (3x+1 3g ft xz)
2 (xxx+1 -kk I'k x²)
|| 1221² 2 + 1 Ix
+ |1 x² x²1 + 2(xx+1 5bk 32 x²)
+2 (fxx - Zky Tk x²)
||+=-1 - h 112 ||0 .& 2 + ||,rk - x² x²112 + 2xx4+1 .k. 3x x²))
+2 (fx Tk, 2x + n x²)
|| - 22 + [6 1 + || - x² z²12 + 2 -b. 52 x²))
+2 (6x - Ik, R4 x²) - 2 3t 11
|| - .x 112 1 xxl1? + || - x "12 [2= + (xx+11 - -2z 3x x²)
+2 (fxx Zb, 34 x²)
|| - 12 1 1 + || - x²112 + 2 2xx+11 - -kk 5/ x²)
= || - 2x11 [ xx11 + || - x² 2²112 2w (For (2x), 30p - x²)
Lemma E.2. Let F' be L-Lipschitz, and let ER hold. Then SPEG iterates satisfy
ED EDI( Fo, (0x) Fu ( <
8||اb 2=1 + - x=1 22 - - - 60 (32)
Proof.
EF (fx) - Fo (21-
= (fx) - F(+x)1 EE - F 111-
+2Ep (+x) - F(*x), F(xx) - F (ik-1)) 1))
Es, || Fo, (36) - F(+x))1 E F(tx) F (fx- 1)11
EpI|Fr, (ix) - F 2 + 2E F F(2x) F(1
+2Ep [(x - FF 1)12
ED|( ($x) ]| 222== |1 [( + 2 P (+xx F 161-
+2Ep || F 11) 2/ F (
<
6|] - x 1- + 26 2 x 112 + 60
F(xx) - F)
(18)
<
81|62 - x²1 + 20 x0 + Go?
+2I2 11
24

---

Lemma E.3. For w
0, 47.
the following two conditions hold:
2wl wō) + - - 80 + L2) S 1 - wp + Aw
(33)
and
(34)
Proof. Note that for
0, 47 we have
-2620 S
ws w μ S
1
HSL
2w(μ - wo) + 2,
2wp
8,
+ 2
S 0.
2L
This proves the first condition. The second condition is equivalent to w(μ w6) + 8w 1.2 - which is again true using similar arguments.
E.1
Proof of Theorem 4.1
Proof. For w E
0, 186
we have w( 9wdd) 2 0 and 1 w(p -9wd) S 2
wp
Then we derive
Ep ||| [14+1 - x²1 + |0 2x
3D
| - x²1 + 2 | -xll2 - 11 - Ix11
D (Fer (.x), ft x²)
1 - x² 112 + 2Bp | 2x|1
|| 2t 112
-2 (F 82 - x²)
(
2 x²1 + 2ED | .x112
11 xx 11
2wyu| |+ xx'' 2²2
| - x² 1= + 2w 2D Fug (.x)
F (f)2
=
- 1 xx 2
2w/u | =x"1'
(22)
| - x²11² + 2w²
81 x=112
$112 + +220+ -20l - 101
-2I² - ft 11- 11
+ +60²) - -1 - xxl12
-2up|l8x x² 2²12
| - x²112 - 2w w - -x²12
=
-4 1 - x + 2 2 112
- 18x - xn 12 + 12w² 0
(22)
| x²1 1|2 (1+ w6)| r"1 112
- 2w (1r w -x 2
+ 4w 1 x011
4w² L12 - | xxll 11?
2
(22)
1 - xx x=1 - w(u (u w6)l 12
22 w6) (10)| 112 + 8w2511 - 2 2x
sw2 28112z x² x0112 + sw 22 xx
112
sw 2 r.2 1.211.7x - || - 1x + 12w200
w/ + 9w )w²0) ||05 - =1
-8w26 5 sw2 T.2)|lare - ||2
(2w(1 w6) sw2 2² 1) ||| x 2x + 12w20?.
25

---

Then using (33), (34) we have
EpI| - x=Il || 1x1 Σ (1 wy + 9w ||:06 - |106--
x=1 1
1| 8x
112
+
Then we take total expectation with respect to the algorithm to obtain the following recurrence:
R8++1 S wp + 9w 12w2 Using the inequality w(H - 9w6)= I
(35)
wide
we have
2
I |a++1 - x²112 |1:0+11 - 111 S
W/l
Iazk - x x²112 + 1| -x-1 12 + 12w oa
(36)
The theorem follows by unrolling the above recurrence. order to compute the iteration complexity of SPEG, we consider any arbitrary & > Then we choose the step-size w such that 24we,
I
i.e. S 480? Next we will choose the number of iterations k such that (1 we equivalent choosing k such that
R
It is
2
log
S k log 1
Now using the fact log (1) 2 for 0 p S 1. get log
22
kwa 2
or equivalently
k 2 wa log (2R)
Therefore, with step-size min 186 AL 480?
Ep
we get the following lower
bound on the number of iterations
8L 368
960 en22
2R
k M max
log
1 112
E.2 Proof of Theorem 4.3
Proof. For w min { 14h 188 }. from Theorem 4.1 we obtain
R2 I (1 w/
24w +
Let the step-size Wk
2k++ and k* be integer that satisfies wa- I w. In particular this holds (++ i
when k. 2 -1_ Note that is decreasing in k and consequently we S W for all k 2 k". Therefore, from (36) we derive
R2 < (1- wh Rd + 12wio
for all k 2 k". Then we replace w/ with
2k++1 2 to obtain (A+1)² a
(1
R + 48o7 (2k: + 1)2 (k: + 1)2
2k
R R 5
112 + 1)4
R.2
(2k: + 1)2
R& + 4802 12 + 1)
(k + 1)
Multiplying both sides by (I: 1)² we get
48o² 122
2k
(k: + 1)2 R2
< R +
k+ 1
+ 1920?
<
1.2
R2
26

---

where in the last line follows from 2k+1 2.
Rearranging and summing the last expression for
t = k², .. k we obtain
1926 - R - 112
[++
(k - k*).
t=
Using telescopic sum and dividing both sides by (k 1)² obtain
k
1920 (k k*)
12
Ri
+
(37)
k
12 + 1
Suppose for k², we have wk min
M i.c. constant step-size. Then from (10), we 188 f
42
obtain R - (1
RB
21w0? +
This bound on R combined with (37) yields
R2 S
k + )
b:*
(1-
Nen RØ
+
k
2Awa
1926 - k*)
2
k+1
p² +
Now we want to choose k* which minimizes the expression
R' K+T
22400? P
(k-o, 1²(k-1)²
Note that,
is minimized at p hence we choose 1=*
Therefore, using this value of k., we obtain
pw
2
24o
R
1
R +
(8k: - 4k*)
+ 1
k
1²2 + 1)2
R
2
192ko
RØ +
+ 1
112 + 1)2
k
2
R2
1920
+
1r2 +1)
The last line follows from
(
[
< <e- for all x 2 1. This completes the proof.
E.3 Proof of Theorem 4.4
Proof. For 0 < wi S { az 18 we obtain the following bound from Theorem 4.1:
R <
pWWk
R + 12wfo?
2
Then using Lemma B.4 with S4 and 12o complete the proof of this Theorem.
E.4 Proof of Theorem E.4
Theorem E.4. Let F be L-Lipschitz and satisfy Weak Minty condition with parameter p 1/(2L). Assume that inequality (8) holds (e.g., it holds whenever Assumption 3.1 holds, see Lemma 3.2). Assume that 7 = 7, W/ w and
1 7 T,' 0 w min { - 2p,
7 85 (1 L3)
max 2p, 2T.
4T.
4
32
27

---

Then, for all K 2 2 the iterates produced by SPEG satisfy
K-1
+ 8- + I22 - In) (1+ + (1- 1n112
48w78
11:00 - -x=10 x²1
min osksK-1
E [1
wy(1 L(y + 4w) ) 1)
8 8 سーسس"²
K-l (1 + [1-1
48wry8
K
o²
(38)
(1 Ln) L(y + 4w))
Proof. The proof closely follows the proof of Lemma C.3 and Theorem C.4 from [23]. The update rule of SPEG implies for l 2 1
|
x=1
|| x²1 112 - (w x², Fo, (&x)) + w0 || Fr.. (12
|| x² = -2w x², Foz (&x)) 2wry (F u (3x 1), Fux (2x))
+w2 FF, (8xx)]1
|| x²1 1|2 -ww x², Foz (2x)) w F (3 1)
-w(7 Fo, (ax) 112 + w/|| Fi (5x) Pu (#x-1))1
where the last step we apply 2(a, b) = |||| 12 + |1bl1 - ||a b1l2. which holds for all a, E TR..
Taking the full expectation and using E,, [-]] [[] and Weak Minty condition, we derive
E || - - [²]
E
I| - x [=] 2 [ x², F( wrLE [1] 11
-(7 - w | [[] [1 || + wy [1| (2x) Fez (fx- 1]1]]]
WV3
[| - x= || + 2w pp ||| [| ( - - [|] Fix 1 (+x 1) ||
-w(7 - )E' ||| || (+x) + wylE [1 (Āx) - F 11
E ||| x || - w> [|| F Fox 13)3
-w(7 - 2p WE [1I (1x))
+wyB Fl (+x) Fo.., (i (05-1))0 ]
x
E [| - x= [|2] - w []] Fuz (ix-1))l 1>]
+wyB [11 (fx) Foo (2k ||
(39)
where we apply Jensen's inequality [(x ) 12 ||B,, [F (fxx ]]1
I E. [|] F (fx) and y
2p + w. For = 0 we have ø1 = 20 WF Fe (0o) = xu FF,, (2o) and
E ||| - ==' = ||30 x 112 - 2wlE 11000- x Fro (xo) ))l + wºE (zoo)l
1|000 x 112 - 2w(xx - xx, F(xoo) + w || (33)
Applying Weak Minty condition, we get E ||II| - x1] = ||-0 - x x011 + 2wpl + [1
< ||:0 - x x11 + w(w + 2 [1 (zo))
(40)
28

---

The next step of our proof is in estimating the last term from (39). Using Young's inequality
laa + bll2 I (1 + a)lla| + (1 + a ")]b[?? which holds for any a, b E R
we get for all
k 2
Fl (fx) ( a [((b))
F., (fx) - F F(xx)
-F (fx-1) - F(
< <1+ [[]6x 8x-1 =12]
+2(1 + + F (.x) - =
+1| (Bx-1) F(
2 (1+ [| Tk + Thk Ik- + Ik-1 5x- [2]]
+2(1 + 1 [||i x² 111 + || - x=" 1
+8(1+
< 51+aa) [[[(] w) P (i 7 Fv. (#x 2 2]
+4(1+a01)01 | - x= 112 + || - x |13]
+4(1+a-1)67 [|] o6 ((x=1))1 )|( + F (8 231
+8(1+a=103
= =1++))(()++ F 1/ ( 1) |2]
+(1+a)12, || un 22)
+ -2(1+a)(>>(7
E (F (Foz- ( 1), Fu (xx-2))
+4(1+a-1)0 |, - x 112 + || - x x²1
+4(1+a-")67"B [1 (ax- )] + Frx 2 2
+8(1+a-100
= =1 [I (ox- |²
+(1 +(1+a) ( 1| [²]
=(++)) [1] (G ))12 + || F pn ( []
())+ [1] (ix Fur., 2
[1 x1 + || - x 211
+1(1+a")0," (fx || + F (
+8(1+a71)0
= +)) ( (fx 1
-(1 a(1+ [1 26) [|
+(1+a)13) + w)) [|| 0z (+ - Frx. (
+4(1+a-1)0B [| x= 1| + || - x [1
1100+a-1007' 'E F 11l= + | (
+8(1 +
Since t0 To and 21 = Φ1 7Fu, (20) = xо (7 + F) (zo), for ls we have
E [[I (.1) Fro [+])
E [[ (.1) Fno [1
S (1 a [()) F(ao) ['2]
+(1 + - | [| (.1) - F((1) - (Fo) - [1
s (1+a)L 2 [| - zo ||
+2(1 1 a )E [1 (21) F( 11. (2O) F(xo))1]]
29

---

Then using (8) we get,
(8)
E Fl, (21) Fi, (6o)]l²)
() (20)]
+2(1 +2(1+a-))0L [|] x x²1 + 1 x x01 + 8(1 + a
+ 4(1 ((1+))
- &++ F1 (xo)
+6(1 -a=
- - + 88 + aao²
K-1 be non-increasing sequence of positive numbers that will be specified later and Let {wx) [=]
WK km Wk. Summing up the above two inequalities with weights {ww)km) 1K11 we derive
WrE [1] (+x) - Fox , (fx= (1 + a) (w(T + w) E [11 (1x)
YYowk 2B Fr (3]
+(1 a) w + w)wK- [1] Fo (xx 2)]
-(1 a) L)L ywwno
E [|| F (xo)))
(, + w) +(1 + a) 1/2 ()
Wk++ E [1] (8xz)
k=1
K
- 1)1 + 4(1 + a a1) 16
Σ
wnE [|| - x=113]
km
+wyB 11 x²1
K-2
+4(1 + a 1087 2
Wk+1 || (8x))1
+ Fee (#x |1 + 8(1 + a ) - wh w2)o?
+ ((1 a) L2 + 4(1 + a 16) ( + 3) (zo))?
+6(1 + a Yow ||000 x 2| + 8(1 a)wio?
Next, we rearrange the terms
using
w/
wk+1 and new notation A
FI (ix) - F (
K-1
K-2
(1 - (1 + a.).37(7 + w))
Σ
W
Σ k=1
(1 + (1++)) a)) + w)r Fo. (#x)
8(1 + a -1 107 w E [|| F (3x [
((1 + T.2 + 8(1 + a -1) )6) (r + w [1] (oo [=3]
K-1
+12(1 a 1 Σ
wk E [| 17
+8(1 + a a (W K wo)o
To simplify the above inequality we choose a = 2T- 1 which is positive due to y < 1/4
and + < l/1. In this case, we have
(1 (1+)) + w) 2 127(77 ww) +
2'
()+ w)² = L + +w)²+
+ w
<
3
2
27
2
La
1
1
3lw
(I+a)[2w(7+t) + 1PW(y + ww +
[[(y w) + 7T.
S
27
2
21. + w)
14 1,2x(7 + w)
2
1
1+ 1 - L27(7 + w)
1 L27(7 + w)
1 1- L22 w)
30

---

where we also use 1/2L < y < 1/4 and Y w < 1/2. Using these relations, we can continue our
derivation as follows:
(1 1-
K-1
Σ
Σ
3lw
16
672 W.E [1I (f=)
2
1 "1- 1- + w)
R=1
k=
3
16
8(7 + w)2 w Fl (2r))l
1,27(7 + w)
K-1
24
8
w [||T - x=11?]
1,2((7 + w)
k=1
16
(WK- wo)o
127(17 + w)
Dividing both sides by (1 - L + W)), we derive
K
K-
Wk Ab
$
Σ
3Lw
(1- 1- + +w]) 672) wr [1F (+x)l
32
I
L2r((y + +w)
k=1
3
(1- - I22(7 + w))2 6(7 00 (() WtE (zo))²
32
+
+
1 L27(1 +w)
K-1
48
8
Σ
E |||ا - x=
(1 (2 w))
k=1
32
LL7(7 w) (WK ww)o
2-2
OrwEE [l (ix) [2] + C2walE [1l |/21
k=1
K-1
+3Cz6
w&B E |||T*
x 1|2] + 2C2WWRo
(41)
where Ci [-L"
3lw
32 (w= 072, C2 [-b')( (I-L""((+w)) 0( + w)
(I
and C3 = (1-Lz Summing up inequalities (39) for k = 1...., K - with weights Wi..... WK-1 and (40) with weight Wo. we get
16
K-1
K-1
K-1
wpl [| - 21]
<
wyE
x²1
w
w.E Foe_, 16x=
k=0
K
+wy
Σ
W. + wlw + 2p) [I[ (so))l
k=1
Since Wp Wk41. can continue the derivation as follows:
K-1
K
E [[==1=+==*0 -
<
E
[0x - 112] - wy Σ
E [l [1]
k=0
k=0
K
twy
Σ
Ar + w(w + 2p) [1 11
k=1
K-1
(1
(1 + (CCWn8))KBBB [||0 - x=1
k==
R-2 -wy(1 - -1)
Σ
F (B+))1]
k=0
+2w7CowoBB [ (2) 2w
31

---

Now we need to specify the weights w-1, wo. wi..... wK-1- Let wK-2 = 1 and wh-1 = (1 +
3Czwyd)wk. Then, rearranging the terms, dividing both sides by wy(1 Cj)Wx= B-W--. we get
min E [11
min
OSkSK
0SkSK-1
K
Wk
E [1 (++)
W WK-1
k=0
K-
(wx-1E IE' [| xx112
wy(1 - Ci)WK-I
k=0
202woB3 [[]Fro [30
wrE [| - -x x211])
(1-C1) -I-Ck)
2C3WRo
(1 Ci)WK-1
w 1000 x011
+ 2C (60)
W0,
w7 C))WK
(--G)WK- K-1 (1-O))KK- K-1
remains to simplify the right-hand side of the above inequality. First, we notice that W WK-1- = k-2 we 2 (K- - 11)x-2 K - 1 since wP 2 wh+t. Moreover, w-1 = (1 + +C33wwd) K-1
Next,
3LW
32
C = 1- 1127(7 +w)
+
(1 - 11-22777- + w)) 872
3Lw
32
(1- LW
4Lw
S 1 1- Ly + (1 (1- 1ا,
- 1 - Lyj
32
3
32
C2 1- L27(7 +w)
+
8(7 + w)²
(1
(1-L' L'2 + w))2
3
32
(1- L')
4
< 1- In (1
(I+ - $1-L7 In'
(1-L))
32
16
16
C3 = (1 - 122(17 + w)
I (1 Ly)
where we use ā < (1- 1/16 and 7 + w follows:
< 1/L. Using these inequalities, we simplify the bound as
(1- + +1 33
- x²1
min osk$K-1
E [1 <
w7(1 I1(7 + 4w:) K - 11)
8(1 + 30 K -2 (1))1((0)) [1
- (1-1(7- + (K
320
(1 - [I-T))(1- 1(( + 4w))
K-1
(1 - 117) (1 + 18w78
11:00 x1
(1-17)²
w7 (1 - L( + (ww) -1)
8 ( 1 + 48w788
K-2
E (o)))l1))
(1-1
(1 - L(y + (K-))
320²
(42)
(1 - [-)(11 - 1(7 + 4w))
where use WK W WK-1 -K-1-
WK-1 S WK-1 + WK-2 1 2Wx-1- Finally, we use (8) to
upper-bound E [1. [q]:
(8)
E
F (fo) [|]]
= E [l (2o)
- 01110 -
-x-''" 12 + [[ +
< (8 + +3) 120 - =2"112 20
32

---

Plugging this inequality in (42), we derive
K-1
+ Buy(6 + L2) 1n) (1+ 488mg
11:0 - 1=
11-17)3
min 0sksK-1
E [11
g
w - Ily + ( -1)
(1+ 48wr88 K-1
8 1-47 k-1
(1-17)2
(1 I,)(11 T. 4w))
which concludes the proof.
E.5 Proof of Theorem 4.5
Theorem E.5. Let F be L-Lipschitz and satisfy Weak Minty condition with parameter p 1/(2L). Assume that inequality (8) holds (e.g., it holds whenever Assumption 3.1 holds, see Lemma 3.2).
Assume that γ y, Wk and
max
2p.
1 2L
+
0 < min {
2p,
1 1 4L
-
Then, for all K 2 the iterates produced by mini-batcher SPEG with batch-size
325
48wyō(K -1 2 1)
t 2 max
(1. (1-11) 11- '(1 L x=
(43)
satisfy
48| x²
min E [IIF(B)]] o
(44)
w L(7 + 4w ) 1)
Proof. Mini-batched SPEG uses estimator
Fox (fxx
Σ (it): 1=1
where Fen, (#x). Fe.,, (fx) are independent samples satisfying (8) with parameters and o².
Using variance decomposition and independence of Fer.1 ($x)...., Fox. (πx), we get
Evg Fll (fx) = Evg [|| Fry (5x) F( + [
1
Eve
F (ax) (
[[F(()))
1=1
Evy [I|For, (ix) - [(x))11 +1|
1=1
x 211 +[(() 20
That is, mini-batched estimator Fu, (fx) satisfies (8) with parameters 5/7 and o:/7. Therefore,
Theorem E,4 implics
K-1
(1 + 4w7 ( + 1.2) - Iy) (1 48wn6
1
x
(1-L7)-5
E (1 osksK-1
min
w>(1 (1 - L(7 + 4ww) (W -1)
K-1
8 + 1يا 1 48wry
(1-17)
(45)
(1 - Lx)(1 - 1(7 + 4w))T
33

---

Since r satisfies (43) and 1 1/1, S 1/4L, we have
4w7
8
+
1
6
(1 - IADL
+ +12) 11,
41,2
166
48 (1 2
K-1
48wyd
(1 - LT)
R-1
1
1 +
(1
bn)
48wy0(K -1)
K-1
1
+
S
<xx((1) <3
K K-1
Using this, we can simplify (45) as follows:
6||20 - x² 1=1
880
min B [[ osksk
w>(1 - L(7 + (w) ) ) 1) (1- Ly) - L(7 + 4W))T
61|20 - x² 1²112
wy(1 - L(7 + ( -
880
(1 - Ii)l 200 11
+ (1 - [T)(1 - I,y + 4w))
2wyo?
48 120 - x
wy(1 - L(y + 4w)) 1)
This concludes the proof.
On Oracle Complexity of Theorem 4.5. Let express the result of Theorem 4.5 via oracle complexity.
Oracle complexity captures the computational requirements required to solve specific optimization problem. That is, given prespecified accuracy E >> 0, it measures number of oracle calls needed to solve the problem to this accuracy. In setting, oracle call indicates the computation of one operator, Fú (for some E [rz). Therefore, in Theorem 4.5, where a mini-batch of size т is required in each iteration of the update rule, we have many oracle calls per iteration. In that scenario, the total number of oracle calls required to obtain specific accuracy e >> 0 is given by KT (multiplicatiion of K iterations with oracle calls).
Cllea-z' iterations.
Note that according to Theorem 4.5 achieve an e accuracy, we need K 2 This follows trivially by
Theorem 4.5 Cl|z0 x²1
min OCkEK-1
E [1(()))
K - S..
(46)
Therefore, using K -1=0-=+11 in combination with the lower bound on from (15), the total number oracle calls to satisfy (46) is given by:
KT 2 max Cl|zo 112
32C6| 11 48C - 211 2C | - x=11
(1 L3)
- 2L)22
(1 - L7)E2
34

---

Further Results on Arbitrary Sampling
F.1 Proof of Proposition 5.1
Expanding the left hand side of Expected Residual (ER) condition we have
(z) - Fz(x))) - (F F F1
@
(F)
(1F(z) F
Bl]F((t) - F.
(47)
For any x and y with 14 pi we obtain
- Folil11
1
(F((z) - -F(())
n²
Pi
EE
Σ
((lo)-F((w))
- -1(00)
nps
npj
iESS
Then taking expectation on both sides we get (x))) - Fo
Eec E
1 (F.(()) - F((U)), (P)(z)) (F(())))((1))
np:
mpj
WJEC
Σ
Σ
1 (F((2) Fi())), np,
(F)(x) -Fy(U))
PC
npp
CageC
Σ
Pij
(F((z) F(())), 1 ((F(())-F)()) P,(0))
PiPj
Now we consider the case, where the ratio the above computations we derive
Psi 02 i.c constant for * and Ps = Pa. Then from pip/
E (x) - F.(11)? = Σ
L ((.(()) (F(())-F(()),,)) F(())), (F((e)) - R(OI))
nPpp
1=1
11
(L(((()) - F((r)), ((((()) R(O))
Σ
11=1
Picz
[F((x) F((1)11
n'p: Pi
1=1
(19)
c2
n F(y)ll2 + Σ
p:0₂
L ||20 - y012
n2p;
iml
(18)
S
(2,L3 +
m
pica
L3 |1--y|1 3112.
n2
Thus replacing y = xx and combining with (47) we get the following bound on the Expected Residual:
(II(F.(x) - F,(x')) -PG
c222²
piO2 13
x1122.
(48)
n
pi
For single-element sampling C2 = 0 (as probability of two points appearing in same sample is zero for single element sampling i.e. P.ş 0). Then obtain
2
1
85
Ps
1=1
35

---

from (48). This completes the derivation of å for single element sampling. To compute o for single element sampling, we replace
Pr
i j
Pis = 0
otherwise
in (30) to get
2
[[((*') )1
22
Pi
36

---

G Numerical Experiments
In Appendix G.I, we add more details on the experiments discussed in the main paper. Furthermore, in Appendix G.2, we run more experiments to evaluate the performance of SPEG on quasi-strongly monotone and weak MVI problems.
G.1 More Details on the Numerical Experiments Section 6
On Constant vs Switching Stepsize Rule. We run the experiments on two synthetic datasets. In Fig. of the main paper, we take μ4 P.C 0.6. Here we include one more plot with a similar flavor but in different setting. For Fig. 5, we generate the data such that eigenvalues of A1, B1, C are generated uniformly from the interval [0.1, 10). In the new plot, similar to the main paper, we can see the benefit of switching the step-size rule of Theorem 4.3.
104
Constant Stepsize (Theoram 4.1) Decreasing Stepsize (Thecrem 4.4) Change step-ize
Relative Error
10-1
10-3
20000
60000
80000
100000
Number of Iterations
Figure 5: Comparison of the constant step-size rule (9) with the switching step-sizes (11) on the strongly monotone quadratic game.
On Weak Minty VIPs. this experiment, we generate Er, S. such that E/ E
v63 and
1 "E= & -1. This choice of &., ç. ensures that = 8 and p = 1/32 for the min-max problem considered in Section 6.2. In Fig. 6, we again implement the SPEG on (17) with batchsize 0.15 x n (diffcrent batchsize compare to the plot of the main paper).
SPEG WMVI
Squared Operator Norm Emor
10-9
10
10
10
10-33
400
600
Number of iterations
Figure 6: Trajectory of SPEG for solving weak MVI using batchsize = 0.15 x n.
G.2 Additional Experiments
In this subsection, we include more experiments evaluate the performance SPEG on quasi- strongly monotone and weak MVI problems. First, we run the experiment comparing constant and switching step-size rules on a different setup than the one we included in the main paper to analyze the performance of SPEG under different condition numbers. Then, we implement SPEG on the weak MVI of (17). To evaluate the performance in this experiment, we plot [((())) |F(r)) l on the y-axis.
37

---

G.2.1 Strongly Monotone Quadratic Game:
In this experiment, we compare the proposed constant step-size (9) and the switching step-size rule (11). We implement our algorithm on operator F R+ F+ given by
1 (M1(z zi) + M2(x 22)) + Ms(x - 233)), F(x) = 3
where M1, M2 and M3 are the diagonal matrices,
)1A)
1
A
M1 =
M2 =
Ms =
A
and
0
A
0
222
0
23
A
This choice of Mj and x; ensures that the Lipschitz constant of operator F is monotonicity parameter (3) is μ 1. Hence the condition number of F is given by A+2 This allows us to vary the condition number of operator F by changing the value A. For Fig. 7a we take A = (condition number 1.67) while for Fig. 7b we choose A 10 (condition number 10.67). The vertical dotted line in plots of Fig. 7 marks the transition point from constant to switching step-size rule predicted by theoretical result in Theorem 4.3.
A+2 while quasi-strong 3
Steostte (Theorem
10a
Conslant Stepaize (Theorem: 4,11 Decreasing Stepsize (Theorem 4.4) Change step-size
16-1
Change ge of stop size
10"1
Relative Error
Relative Error
20-2
10
10-2
10-1
10-4
20000
40000
60000
80000
100000
0.0
0.2
0.4
0.6
0.8
10
Number of Iterations
Number iterations
1e5
Condition Number 1.67.
(b) Condition Number
10.67.
Figure 7: Illustration of switching rule (11) Theorem 4.3. The dotted line marks the transition from phase | (where we use constant step-size) to phase (where we use decreasing step-size).
G.2.2 Weak Minty VIPs Continued
In this experiment, we reevaluate the performance SPEG on weak MVI example of (17). That is, we generate the data in exactly the same way the ones in section 6.2 with = 100. In Fig. 8a and 8b, we implement SPEG with batchsize 10 and 15, respectively (we note that in this setting the full-gradient evaluation requires batchsize of 100). For these plots, we use the relative operator norm on the y-axis, [[+((&))) //=F(=)) where Tn denotes the starting point of SPEG.
expected, the plots illustrate that SPEG performs better as we increase the batchsize. From Fig. 8 it is clear that with batchsize 15 SPEG reaches an accuracy close 10-10 while when we use batchsize of 10 for the same number of iterations only able to converge to accuracy of 1
38

---

Relative Operator Norm
+ SPEG
Relative Operator Norm
10a
+ SPEG
20
10-4
10-4
10000
20000
30000
40000
50000
10000
20000
30000
40000
50000
Number of Iterations
Number Iterations
(a) Batchsize = 0.1 x n1.
(b) Batchsize 0.15 x n.
Figure 8: Performance of SPEG for solving weak MVI different batchsizes, plot (a) we use a batchsize of 10 while in plot (b) we use 15.
39


Reviews:
[{"review_id": "7ZlJOHNqpX", "reviewer": "Reviewer_Bwgk", "summary": "The paper explores single-call stochastic extragradient methods like stochastic past extragradient (SPEG) and stochastic optimistic gradient (SOG), which are increasingly popular and efficient algorithms for tackling large-scale min-max optimization and variational inequalities problems (VIP) commonly found in diverse machine learning tasks. Notwithstanding their growing popularity, the current convergence analyses of SPEG and SOG demand strong assumptions like bounded variance or growth conditions. Moreover, numerous key questions related to the convergence properties of these methods, such as mini-batching, effective step-size selection, and convergence guarantees under various sampling strategies, remain unaddressed.\n\nThis research endeavors to answer these questions, presenting convergence guarantees for two extensive classes of structured non-monotone VIPs: (i) quasi-strongly monotone problems, which extend strongly monotone problems, and (ii) weak Minty variational inequalities, which expand upon monotone and Minty VIPs. The paper introduces the expected residual condition and discusses its advantages, demonstrating how it enables a strictly weaker bound than those achieved by previously employed growth conditions, expected co-coercivity, or bounded variance assumptions. Lastly, the presented convergence analysis is applicable under the arbitrary sampling paradigm, encompassing special cases like importance sampling and various mini-batching strategies.\n", "questions": "Address the weaknesses' section", "limitations": "N/a", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The main contributions of the paper include the following:\n\n- **Expected Residual:** The authors introduce the Expected Residual (ER) condition for stochastic variational inequality problems. The ER condition is used to derive an upper bound on $E\\|g(x)\\|^2$ (as detailed in Lemma 3.2), offering a strictly weaker alternative to the bounded variance assumption and previously used \"growth conditions\" for the analysis of stochastic algorithms. The paper shows that the ER condition holds for a large class of operators, specifically when the $F_i$ of the problem are Lipschitz continuous.\n\n- **Novel Convergence Guarantees:** The paper presents novel convergence guarantees for Stochastic Past Extragradient (SPEG) without the need for a bounded variance assumption in the cases of quasi-strongly monotone and weak Minty Variational Inequalities (MVI). This is achieved through the use of the proposed ER condition. For the class of quasi-strongly monotone Variational Inequalities Problems (VIPs), the paper demonstrates a linear convergence rate to a neighborhood of $x^*$ when constant step-sizes are utilized. Furthermore, theoretically motivated step-size switching rules are provided that guarantee exact convergence of SPEG to $x^*$. In the weak MVI case, the convergence of SPEG is proved for $\\rho < 1/2L$, improving existing restrictions on $\\rho$. The authors compare their results with the existing literature in Table 1.\n\n- **Arbitrary Sampling:** By reformulating the variational inequality problem stochastically, the authors explain how their convergence guarantees for SPEG hold under the arbitrary sampling paradigm. This approach allows them to cover a wide range of sampling strategies for SPEG not previously considered, including mini-batching, uniform sampling, and importance sampling. Therefore, their analysis of SPEG is unified for different sampling strategies. The authors also demonstrate the tightness of their analysis by showing that the best-known convergence guarantees of deterministic Past Extragradient (PEG) for strongly monotone and weak MVI can be obtained as special cases of their main theorems.\n", "weaknesses": "- **Redundant Main Result:** The primary outcome of this research could essentially be seen as a single-call version of \"Stochastic Extragradient: General Analysis and Improved Rates,\" but under simpler guarantees. This could potentially question the novelty of this research.\n\n- **Uncertainty of Expected Residual (ER):** The Expected Residual (ER) is proposed as a new and beneficial condition, however, it is unclear whether this condition is indeed intuitive and interesting in practice. It would be beneficial if the authors could provide more justification or insights on the relevance of the ER condition in practical scenarios.\n\n- **Importance of Single-Call Methods:** While the paper puts substantial focus on single-call methods, it is unclear whether these methods are significantly important in practical scenarios. Theoretical advantages are evident, but it would be constructive if the authors could provide more practical motivations or empirical examples where single-call methods bring notable improvements.\n\n- **Comparison with Existing Methods:** If Stochastic Extragradient (SEG) methods already have satisfactory rates and guarantees, it is intuitive to assume that Stochastic Optimistic Gradient (SOG) methods would offer similar advantages. Therefore, a clear delineation between the contributions of the proposed method and existing ones would be beneficial for the reader.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review and positive evaluation. Below, we address questions and concerns raised by the reviewer. \n\n**\\[... question the novelty of this research\\]** We politely disagree with this remark. Our work on the single-call method uses a different proof technique compared to [Gorbunov et al. 2021](https://proceedings.mlr.press/v151/gorbunov22b/gorbunov22b.pdf) for proving the convergence. Analysing single-call methods involve dealing with the term $E||F_{v_k}(\\hat{x_k}) - F_{v_{k-1}} (\\hat{x_{k-1}})||^2$ (however, these do not appear in the analysis of the Extragradient method). Moreover, note that the Lyapunov function used to analyse our method is $E(||x_{k} - x^\\ast ||^2 + ||x_{k} - \\hat{x_{k-1}}||^2)$ in contrast to $E||x_{k} - x^\\ast||^2$ for the Extragradient method. Moreover, we provide convergence guarantees for a larger class of non-monotone problems, i.e. weak Minty variational inequality, while Gorbunov et al. 2021 solve only quasi-strongly monotone problems. Therefore, our work is not just a simple extension of Gorbunov et al. 2021.\n\n**\\[...provide more justification or insights on the relevance of the ER condition in practical scenarios.\\]** As discussed in the paper, the Expected Residual is a more relaxed condition than the bounded variance assumption (bounded variance is used to provide convergence guarantees for the stochastic single-cell methods). Moreover, Expected Residual is not an assumption and holds for free whenever the operators $F_i$ are Lipschitz. However, there are several examples where bounded variance may not hold. We provide one such example here:<br>\n<br>Consider the simple linear regression problem: $$\\min_{x \\in \\mathbb{R}} f(x) := \\frac{1}{2} (a_1x - b_1)^2 + \\frac{1}{2} (a_2x - b_2)^2$$ where $x \\in \\mathbb{R}$ and $f: \\mathbb{R} \\to \\mathbb{R}$. Here let us denote $f_1(x)=(a_1x - b_1)^2$ and $f_2(x) = (a_2x - b_2)^2$. Now consider the estimator $g(x)$ of $\\nabla f(x)$ under uniform sampling i.e. $g(x)$ takes the value $\\nabla f_1(x)$ with probability $\\frac{1}{2}$ and $\\nabla f_2(x)$ with probability $\\frac{1}{2}$. Then we have $$\\mathbb{E} ||g(x) - \\nabla f(x)||^2 = \\frac{1}{2} ||\\nabla f_1 (x) - \\nabla f(x)||^2 + \\frac{1}{2} ||\\nabla f_2(x) - \\nabla f(x)||^2 = \\frac{1}{2} \\cdot \\frac{1}{4}||\\nabla f_1 (x) - \\nabla f_2(x)||^2 + \\frac{1}{2} \\cdot \\frac{1}{4}||\\nabla f_2 (x) - \\nabla f_1(x)||^2 =  \\frac{1}{4} ||\\nabla f_1(x) - \\nabla f_2(x)||^2 = \\frac{1}{4} \\left( 2(a_1x - b_1)a_1 - 2(a_2x - b_2)a_2 \\right)^2 = \\left( (a_1^2 - a_2^2) x - (a_1b_1 - a_2b_2) \\right)^2.$$ Thus, the expression $\\mathbb{E} ||g(x) - \\nabla f(x)||^2$ is a quadratic function of $x$. Hence, as $x \\to \\infty$, we have $\\mathbb{E} ||g(x) - \\nabla f(x) ||^2 \\to \\infty$ and the variance can not be bounded by a constant. On the other hand, this function has a Lipscihtz gradient, and from our results, ER and condition (9) hold for free. In addition, an analysis under Expected Residual allows us to capture the performance of stochastic methods for various sampling strategies used in practice. For example, practitioners frequently use minibatch or importance sampling to train machine learning models. Our analysis with Expected Residual allows us to explicitly derive the convergence rates under different sampling strategies. However, bounded variance does not capture the analysis under such sampling strategies.\n\n**\\[...it is unclear whether these methods are significantly important in practical scenarios...\\]** The single-call extragradient method requires two oracle calls per iteration in contrast to the two oracle calls by the extragradient method. In order to make a fair comparison of the two methods, we should count the number of oracle calls required to achieve a given accuracy. We compared the stochastic extragradient method of [Gorbunov et al. 2021](https://proceedings.mlr.press/v151/gorbunov22b/gorbunov22b.pdf) with the stochastic past extragradient method. The number of oracle calls required by the single-call method was less than the extragradient method. We have provided a plot (.pdf file comparing SPEG and SSEG) to compare the two methods in th General Response to the reviewers. In the attached figure, the Stochastic Past extragradient requires 2000 oracle calls, while the stochastic extragradient method requires more than 3000 oracle calls for convergence. It highlights the lower computational complexity of the single-call method and provides empirical evidence of notable improvements for these methods. \n\n**\\[...a clear delineation between the contributions of the proposed method and existing ones would be beneficial for the reader.\\]**\n- As discussed in answer to the previous question, the empirical evidence shows that the single-call method can have lower computational complexity than the SEG methods. It motivates us to study the single-call methods in more detail. \n- We want to highlight that, previously, researchers used bounded variance to study single-call methods. However, we have provided an example in the previous answer of why this may not hold in simple scenarios. We lift such unrealistic assumptions and work under Expected Residual in our work.\n- Furthermore, we provide convergence guarantees of SPEG for various sampling strategies. We also provide empirical evidence to show the advantage of using importance sampling over uniform sampling for SPEG. \n- Moreover, we provide convergence guarantees of the stochastic single-call method for solving weak minty variational inequality problems with $\\rho < \\frac{1}{2L}$. It also improves the existing restriction on $\\rho$ for stochastic methods. Previously, the best-known result used bounded variance assumption with $\\rho < \\frac{3}{8L}$ to provide a convergence guarantee of the stochastic method.\n\n**If you agree that we managed to address all issues, please consider raising your score. If you believe this is not the case, please let us know so that we have a chance to respond.**\n"}, {"review_id": "Gp4GXF1yk3", "reviewer": "Reviewer_rrNt", "summary": "This work studies single-call stochastic extra-gradient method for quasi strongly monotone and weak Minty Variational Inequality (VI). They relax the commonly-used bounded noise variance assumption and used the expected residual condition.", "questions": "Please see the weakness section. If you could elaborate on the novelty that would be great.", "limitations": "N/A", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is well-written and the problem is relevant.", "weaknesses": "In short, I think the technical novelty in this paper is minimal. I substantiate my claim below. \n\n\n1. It introduces expected residual condition which has been studied before in SGD literature as the authors correctly state. So the condition itself is not a contribution. **As the authors agree (line 173-175), the main difference between this work and [29] is that (8) is an Assumption in [29] whereas Assumption 3.1 implies (8) in this work. But it is easy to see that the proof of Lemma 3.2 just requires a single use of Young's inequality (and indeed, that's how it's done in the Appendix).**\n\n2. **Authors in [29] use another condition** $ E || g(x) − F(x) ||^2 \\leq (a||x − x^*|| + b)^2 $ **which is extremely similar to ER condition. But in line $171$, the authors claim that the constants $a$ and $b$ are not available in closed form. But this is a trivial result (Proposition 3.3). These calculations are routinely done in literature involving  stochastic gradient as the authors themselves agree (line 153, [24-25]).**\n\n3. **Use of ER condition relaxes the bounded condition on the noise variance but the additional technical innovation needed, compared to the bounded noise variance, is minimal.** Familiarity with the stochastic extra-gradient proof techniques right away reveals that the RHS of ER condition, $||x-x^*||_2^2$, is designed to be subsumed in other terms appearing in the proof which effectively leaves the proof almost same as the bounded variance case.\n\nSpecifically, **note that ER condition only introduces the term** $\\omega^2\\delta || \\hat{x}_k - x^* ||_2^2$ **in the 5th line of the display appearing after line 664. But there is another term** $ -2 \\omega \\mu ||\\hat{x}_k-x^*||_2^2$. **So the convergence can be guaranteed if** $\\omega $ **is chosen small enough such that** $2\\omega\\mu ||\\hat{x}_k-x^*||_2^2> \\omega^2\\delta ||\\hat{x}_k-x^*||_2^2$. **This is almost trivial.**\n\nIn fact, one can easily think of allowing for bigger bounds for the noise variance keeping the proof unimpacted. For example, convergence can be easily shown if one allows for a noise variance bound like $\\omega^{-1/2}\\delta ||\\hat{x}_k-x^*||_2^2$. **All the proofs depend on this simple and trivial extension.**", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review. Below, we address questions and concerns raised by the reviewer.\n\n**\\[...the condition itself is not a contribution\\]** Here, we want to highlight that the ER condition in minimization literature involves the functional value, i.e. the right-hand side is $f(x) - f^\\ast$ (check Assumption 3.1 [SGD for Structured Nonconvex Functions: Learning Rates,\nMinibatching and Interpolation](http://proceedings.mlr.press/v130/gower21a/gower21a.pdf)). However, there is no notion of function values in VIPs. Therefore, we have replaced the $f(x) - f^\\ast$ with $||x - x^\\ast||^2$, which completely changes the proof technique compared to the minimization setup.\n\n**\\[...the main difference between this work and [29] is that (8) is an Assumption in [29]...\\]** Yes, authors of [29](https://arxiv.org/pdf/2003.10162.pdf) also use similar conditions as we have mentioned in our work. But the reviewer ignores the setup considered in their paper. [29](https://arxiv.org/pdf/2003.10162.pdf) considers the extragradient method with two oracle calls and solves for operators satisfying error-bound condition, whereas we consider the single-call method for solving quasi-strongly monotone and weak minty variational inequalities. Even though the conditions are similar, our work is completely different in other aspects. \n\n**\\[...These calculations are routinely done in literature involving stochastic gradient...\\]** Yes, this kind of computation is not new; similar calculations exist in the literature, which we have also mentioned in our paper. However, we don't consider it a weakness of our work. We want to highlight that this was never done for the single-call extra gradient method for solving VIPs. As mentioned in the previous answer, our ER condition is a modification of the ER condition introduced in the minimization setup. Therefore, no work precisely computes the constants like $\\delta$ of our ER. Moreover, we are the first to capture different sampling strategies (like minibatch, importance or any other single-element sampling) of the single-call method for solving VIPs. \n\n**\\[...ER condition only introduces the term $\\omega^2 \\delta ||\\hat{x_k} - x^\\ast||^2$ in the 5th line of the display appearing after line 664...\\]**\n- The reviewer rrNt argues ER condition only introduces the extra term $\\omega^2 \\delta ||\\hat{x_k} - x^{\\ast}||^2$, which can be handled easily. We politely disagree with the statement and ask the reviewer to check the 5th line after line 664 again. Reviewer rrNt completely ignores the term $\\omega^2\\delta||\\hat{x_{k-1}} - x^\\ast||^2$, which ER also introduced. Moreover, this term can not be canceled following the procedure mentioned by rrNt. Indeed, for handling such terms, we have introduced $||x_{k+1} - \\hat{x}_k||$ in the Lyapunov function under consideration.\n- The reviewer also overlooks the different stepsizes proposed in our work. There were no switching stepsizes for single-call methods, even under the bounded variance assumption, to get exact convergence. \n- Moreover, reviewer rrNt also ignores our contributions for weak minty VIPs. We analyse stochastic single-call methods for $\\rho < 1/2L$, improving the previous restriction on $\\rho$.\n\n**We believe a score of 2 is too harsh for our work, and it definitely deserves better. If you agree that we addressed all issues, please consider raising your score. If you believe this is not the case, please let us know so that we have a chance to respond.**\n"}, {"review_id": "rCYsiMiUMm", "reviewer": "Reviewer_bysm", "summary": "This paper studies the single-call stochastic extragradient methods for solving two classes of structured variational inequality (VI) problems, i.e., (i) quasi-strongly monotone problems and (ii) weak Minty variational problems. These two classes generalize the assumptions of strong monotonicity and comonotonicity to be only satisfied w.r.t. the solution point, respectively. The authors consider the stochastic reformulation of VIs, which allows for mini-batching with arbitrary sampling. The convergence results are built upon the expected residue condition, which can be explicitly implied by the component Lipschitzness and can imply bounded variance. Convergence are analyzed in both settings and with different stepsize strategies. The authors also provide numerical experiments to support their theoretical discussion.", "questions": "1. Although the weak Minty variational problems look more general than comonotonicity assumption, but I am not sure whether it is more of a theoretical artifact. Could the authors provide some practical examples which satisfy Def 1.2 but are not comonotone?\n2. Could the authors clarify the stochastic settings this paper focused on, finite-sum or infinite-sum? I feel confused because $n$ never appears in the convergence results, and the choice of the batch size $\\tau$ in Theorem 4.5 (Eq. 15) can essentially be larger than $n$.", "limitations": "Please see the weaknesses and questions above.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The authors generalize the idea from stochastic minimization and propose the expected residue condition, which can be explicitly implied by the Lipschitzness of the component operator, and can be used to provide a variance bound. Thus, this paper does not require a bounded variance assumption nor growth conditions.\n2. The authors provide a thorough discussion for the convergence results and detailed comparison with prior works, such as Lines 183--200.", "weaknesses": "1. Although the authors state the stochastic problem in term of the **finite-sum** structure (see Eq. 1 and 5), the convergence analysis is more likely for **infinite-sum** problems, especially when the authors also consider mini-batch in this paper.\n2. The expected residue condition proposed in the paper looks restricted because the authors make this assumption directly on the stochastic estimator $g(x)$ instead of the stochastic oracle queries. It seems non-trivial to assume it for the stochastic estimators beyond the mini-batching ones, such as SVRG or SARAH.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review and positive evaluation. Below, we address questions and concerns raised by the reviewer.\n\n**\\[...the convergence analysis is more likely for infinite-sum problems, especially when the authors also consider mini-batch in this paper.\\]** We consider only the finite-sum structure of the operator in our work. We have rigorous proofs that hold as long as (ER) condition holds. Indeed, it can be satisfied not only for finite-sum problems. However, it also works for the finite-sum case since we show that (ER) holds for finite-sum problems. Could the reviewer point us to the steps where the analysis does not work for finite-sum cases?\n\n**\\[...non-trivial to assume it for the stochastic estimators beyond the mini-batching ones, such as SVRG or SARAH.\\]** We make Assumption 3.1 directly about $g(x) = F_v(x)$. One can think about $g(x)$ as about oracle call or some other estimator constructed using some procedure (e.g., batching): our analysis holds whenever (ER) is satisfied. We provide multiple examples when (ER) holds. This assumption is not that restrictive as standard bounded variance assumption used in prior works in SEG.\n\n Yes, our work does not capture the variance-reduced algorithms. However, this is not a weakness of our work. We provide the analysis without the bounded variance assumption, and our analysis captures several sampling strategies, including minibatch and importance sampling. However, we will try to have a unified study that will capture variance-reduced algorithms as the future work direction. \n\n**\\[...Could the authors provide some practical examples which satisfy Def 1.2 but are not comonotone?\\]** We don't have such a practical example in mind. However, we want to highlight that any comonotone problem is a special case of our Def 1.2. Therefore our convergence guarantee holds for comonotone problems as well.\n\n**\\[Could the authors clarify the stochastic settings this paper focused on, finite-sum or infinite-sum?...\\]** In our work, we focus on the finite-sum problems. However, if the assumptions (in particular, Assumption 3.1) are satisfied, our analysis works for different types of problems as well, e.g., when $F(x) = E_{\\xi \\sim \\mathcal{D}}[F_{\\xi}(x)]$ where $\\mathcal{D}$ can be continuous distribution.\n\n**If you agree that we managed to address all issues, please consider raising your score. If you believe this is not the case, please let us know so that we have a chance to respond.**\n"}, {"review_id": "HHXyRGEYUY", "reviewer": "Reviewer_dTzE", "summary": "This paper proposes new convergence results for single-call stochastic extragradient methods under weaker conditions. More specifically, the authors consider quasi-strongly monotone and weak Minty VI problems, both under an unconstrained finite-sum (or arbitrary sampling) setting. The authors propose the expected residual (ER) condition, which extends similar conditions used in stochastic optimization (minimization) to the VI setting. ER is more general than the boundedness assumption on operator noise, and is sufficient for establishing their convergence results. The authors also give sufficient conditions for ER and explain its connections to other widely used technical conditions/assumptions. Using ER, the authors establish convergence results for single-call stochastic extragradient methods for quasi-strongly monotone and weak Minty VI problems. For quasi-strongly monotone problems, two results are given for constant and decreasing step size rules. The authors then give expressions for the ER parameters (which factor into convergence rates) under non-uniform sampling. Numerical experiments complement the theoretical findings.", "questions": "My main question is around the practicality of the proposed step size rules. In previous work, most (static, non-adaptive) step sizes used in convergence theorems tend to be highly conservative, and more aggressive or adaptive step size rules (which may weaken/break convergence guarantees) need to be used in order to make the algorithms converge in experiments.\n\nIn this work, to achieve desirable convergence rates, the step sizes (constant or decreasing) depend on $\\delta$, $\\mu$, and $L$. My concern is that (i) these constants may be hard to find, or (ii) only conservative, safe estimates can be given. Therefore, the step sizes given by the theorems may be too small. It seems that in all experiments, theoretically safe constants are used. Have the authors considered using more aggressive step sizes which do not follow the theorems entirely (but partially, such as the $1/k^2$ decreasing trend in (11) but with different constants)? If so, it would be helpful to point these out. If the theorems' suggested step size rules are already \"near-optimal\" in experiments (meaning that further increasing them would lead to non-convergence), it would also be worth pointing out this favorable observation. In fact, if true, this would be such a rarity based on my experience and other work, and should be worth highlighting.", "limitations": "This is a theoretical and methodological work. The limitations are mainly technical: many practical problems mentioned as a motivation of the work do not (or cannot be easily shown to) satisfy the exact technical assumptions. However, this is typical and not a concern.\n\nI do not see potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- Clear presentation of results.\n- Sufficient discussion of the background and context of the new ER condition.\n- First convergence guarantee for SOG under arbitrary sampling.\n- First convergence guarantee for SPEG without any bounded variance assumption.", "weaknesses": "See **Questions**.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review and positive evaluation. Below, we address questions and concerns raised by the reviewer.\n\n**\\[My main question is around the practicality of the proposed step size rules...\\]** We appreciate the reviewer's concern regarding the adaptive stepsizes. However, this should not be noted as a weakness of our work. In our work, we focus on the situation when the problem parameters are known since it is important to understand this case first before moving to the adaptive stepsizes. Not all papers on optimization should be about adaptive stepsizes, and it is beyond the scope of our work. There are various practical examples where the constants $L, \\mu, \\delta$ can be computed. One such example would be the Robust Least Square problem. Check out the Robust Least Square subsection under Numerical Experiments of the paper [Global Convergence and Variance Reduction for a\nClass of Nonconvex-Nonconcave Minimax Problems](https://proceedings.neurips.cc/paper/2020/file/0cc6928e741d75e7a92396317522069e-Paper.pdf). The objective function of equation 8 in this paper is a quadratic game, and the values of constants $L, \\mu$ and $\\delta$ can be easily computed. \n\n**\\[...Therefore, the step sizes given by the theorems may be too small...\\]** The reviewer writes the step sizes given by Theorems may be too small. However, we want to mention the fact that our analysis of SPEG recovers the best rate of convergence in a deterministic setting for both quasi-strongly monotone and weak minty variational inequality problems. This highlights the tightness of our stepsize choices.\n\n**\\[... Have the authors considered using more aggressive step sizes which do not follow the theorems entirely (but partially, such as the $\\frac{1}{k^2}$ decreasing trend in (11) but with different constants)?...\\]** We did not try the stepsize choice of $\\frac{1}{k^2}$ with a different constant. In the paper, we run experiments only to validate our theory. We appreciate this feedback and will add more details on this in the updated version of our work. \n\n**If you agree that we managed to address all issues, please consider raising your score. If you believe this is not the case, please let us know so that we have a chance to respond.**\n"}]

Author rebuttal:
We thank the reviewers for their valuable feedback and time. In particular, we appreciate that the reviewers acknowledged the following strengths of our work:

- Reviewer rrNt acknowledges the problem (considered in our work) is relevant and needs to be addressed.
- All the reviewers identify relaxing assumptions like bounded variance or growth conditions as one of the main strengths of our work.
- Both Bwgk and dTzE recognize our work as the first to provide convergence analysis of single-call methods under arbitrary sampling.
- Reviewer Bwgk acknowledges the improvement provided in our work for solving weak minty VIPs (we improved the restriction on $\rho$ in the stochastic setting to provide convergence). 
- All the reviewers think the paper is well-written, and we have done a good job presenting the prior literature and providing thorough discussion.
- Reviewers bysm and dTze appreciate our numerical experiments to support the theoretical findings.

The reviewers also have several questions and concerns that we address in our responses to each reviewer. We have attached a plot called SSEGvsSPEG.pdf here. This plot is for reviewer **Bwgk** to answer one of his questions. You can find more details about the plot in the response to **Bwgk**.

If the reviewers have further questions/concerns/comments, we will be happy to participate in the discussion.


Meta-review: After carefully going through all the reviews, rebuttal, and the discussions, even though the technical contributions of the paper (e.g., introducing a new proof technique etc) are incremental, the overall contribution (broader problems, weaker assumptions, improved algorithms) is at the strong side. Hence I am recommending an acceptance for the submission.

Please implement and clarify all the changes requested by the reviewers. 

That being said, while understanding that writing a rebuttal can be frustrating, I find the tone and the attitude of the authors quite aggressive and sometimes impolite. I suggest using a milder and more diplomatic tone in your next submissions and preferably not ask for specific scores from the reviewers.
Decision: Accept (poster)