Solving stochastic weak Minty variational inequalities without increasing batch size
Authors: Thomas Pethick
Olivier Fercoq
Puya Latafat
Panagiotis Patrinos
Volkan Cevher
Venue: ICLR 2023 poster (2023)
Keywords: Variational inequalities
stochastic first-order methods
nonconvex-nonconcave
minimax

Abstract: This paper introduces a family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty variational inequality (MVI). Unlike existing results on extragradient methods in the monotone setting, employing diminishing stepsizes is no longer possible in the weak MVI setting. This has led to approaches such as increasing batch sizes per iteration which can however be prohibitively expensive. In contrast, our proposed methods involves two stepsizes and only requires one additional oracle evaluation per iteration. We show that it is possible to keep one fixed stepsize while it is only the second stepsize that is taken to be diminishing, making it interesting even in the monotone setting. Almost sure convergence is established and we provide a unified analysis for this family of schemes which contains a nonlinear generalization of the celebrated primal dual hybrid gradient algorithm.


Published as a conference paper at ICLR 2023
SOLVING STOCHASTIC WEAK MINTY VARIATIONAL INEQUALITIES WITHOUT INCREASING BATCH SIZE
Thomas Pethick
Olivier Fercoq"
Puya Latafat
Panagiotis Patrinos Volkan Cevher"
ABSTRACT
This paper introduces family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty vari- ational inequality (MVI). Unlike existing results on extragradient methods in the monotone setting, employing diminishing stepsizes is longer possible in the weak MVI setting. This has led to approaches such as increasing batch sizes per iteration which can however be prohibitively expensive. In contrast, our proposed methods involves two stepsizes and only requires one additional oracle evaluation per iteration. We show that it is possible to keep fixed stepsize while is only the second stepsize that is taken to be diminishing, making it interesting even the monotone setting. Almost unified analysis for this family of schemes which contains a nonlinear generaliza- tion of the celebrated primal dual hybrid gradient algorithm.
convergence established and provide
INTRODUCTION
Stochastic first-order methods have been at the core of the current success in deep learning appli- cations. These methods mostly well-understood for minimization problems at this point. This is even the case in the nonconvex setting where there exists matching upper and lower bounds on the complexity for finding approximately stable point (Arjevani et al., 2019).
The picture becomes less clear when moving beyond minimization into wenconvex--ooconcann min- more generally nonmonotone variational incqualities. Even in the deterministic case, finding stationary point is in general intractable (Daskalakis et al., 2021; Hirsch & Vavasis, 1987). This is in stark contrast with minimization where only global optimality is NP-hard.
imax problems-
An interesting nonmonotone class for which we do have efficient algorithms characterized by the called weak Minty variational inequality (MVI) (Diakonikolas al., 2021). This problem class captures nontrivial structures such as attracting limit cycles and is governed by a parameter whose negativity increases the degree of nonmonotonicity. It turns out that the stepsize y for the exploration step in extragradient-tyne type schemes lower bounds the problem class through p > -7/2 (Pethick et al., 2022). In other words, it seems that we need to take y large to guarantee convergence for a large class.
This reliance on a large stepsize is at the core of why the community has struggled to provide a stochastic variants for weak MVIs. The only known results effectively increase the batch size at every iteration (Diakonikolas et al., 2021, Thm. 4.5) strategy that would be prohibitively expensive in most machine learning applications. Pethick al. (2022) proposed (SEG+) which attempts to tackle the noise by only diminishing the second stepsize. This suffices in the special case of unconstrained quadratic games but can fail even the monotone case as illustrated Figure This naturally raises the following research question:
Can stochastic weak Minty variational inequalities be solved without increasing the batch size?
We resolve this open problem in the affirmative when the stochastic oracles are Lipschitz in mean, with a modification of stochastic extragradient called bias-corrected stochastic extragradient (BC- SEG+). The scheme only requires one additional first order oracle call, while crucially maintaining the fixed stepsize. Specifically, we make the following contributions:
Laboortory for Information and Inference Systems (L.OOSS), EPFL fihoomas.pethche @epfl.ch)
'Laboratoire Traitement et Communication d' I'Information, Télécom Paris, Institut Polytechnique de Paris DDearrmeen of Electrical Engineering (ESAAAIAA,, KU Leuven

---

Published as a conference paper at ICLR 2023
(i) We show that it is possible to converge for weak MVI without increasing the batch size, by in- troducing a correctot term. The scheme introduces no additional hyperparameters and recovers the maximal range p (-1/2, oo) of explicit deterministic schemes. The rate tablish is interesting already in the star-monotone case where only asymptotic convergence of the norm of the operator was known when refraining from increasing the batch size (Hsieh et al., 2020, Thm. 1). Our result additionally carries over to another class of problem treated in Appendix G, which we call negative weak MVIs.
(ii) We generalize the result to whole family of schemes that can treat constrained and regular- ized settings, First and foremost the class includes generalization of the forward-back ward- forward (FBF) algorithm of Tseng (2000) to stochastic weak MVIs. The class also contains stochastic nonlinear extension of the celebrated primal dual hybrid gradient (PDHG) algo- rithm (Chambolle Pock, 2011). Both methods are obtained as instantiations of the same template scheme, thus providing unified analysis and revealing an interesting requirement on the update under weak MVI when only stochastic feedback is available.
(iii) We prove almost sure convergence under the classical Robbins- Monro stepsize schedule of the second stepsize. This provides guarantee on the last iterate, which is especially important in the nonmonotone case, where average guarantees cannot be converted into a single candidate solution. Almost sure convergence is challenging already in the monotone case where even stochastic extragradient may not converge (Hsich et al., 2020, Fig. 1).
2 RELATED WORK
Weak MVI Diakonikolas et al. (2021) was the first to observe that an extragradient-like scheme called extragradient+ (EG+) converges globally for weak MVIs with p E (-1/s1,, oo). This re- sults was later tightened to p (-1/2Le, 0o) and extended to constrained and regularized settings in (Pethick et al., 2022). single-call variant has been analysed in Böhm (2022). Weak MVI is a star variant of cohypomonotonicity, for which an inexact proximal point method was originally stud- ied in Combettes & Pennanen (2004). Later, tight characterization was carried out by Bauschke et al. (2021) for the exact case. It was shown that acceleration is achievable for extragradient-type scheme even for cohypomonotone problems (Lee & Kim, 2021). Despite this array of positive re- sults the stochastic case is largely untreated for weak MVIs. The only known result (Diakonikolas et al., 2021, Theorem 4.5) requires the batch size to be increasing. Similarly, the accelerated method in Lee & Kim (2021, Thm. 6.1) requires the variance of the stochastic oracle to decrease O(1
Stochastic & monotone When more structure is present the story is different since diminishing stepsizes becomes permissible. the monotone case rates for the gap function was obtained for stochastic Mirror-Prox in Juditsky et al. (2011) under bounded domain assumption, which was later relaxed for the extragradient method under additional assumptions (Mishchenko et al., 2020). The norm of the operator shown to asymptotically converge for unconstrained MVIs in Hsich et al. (2020) with a double stepsize policy. There exists a multitude of extensions for monotone prob- lems: Single-call stochastic methods are covered in detail by Hsieh al. (2019), variance reduction was applied to Halpern-type iterations (Cai et al., 2022), cocoercivity was used in Beznosikov et al. (2022), and bilinear games studied in Li al. (2022). Beyond monotonicity, range of structures have been explored such as MVIs (Song et al., 2020), pseudomonotonicity (Kannan & Shanbhag, 2019: Bot et al., 2021), two-sided Dolyak-Lojassewiics condition (Yang al., 2020). expected coco- ercivity (Loizou et al., 2021), sufficiently bilinear (Loizou et al., 2020), and strongly star-monotone (Gorbunov al., 2022).
Variance reduction The assumptions we make about the stochastic oracle in Section 3 are similar to what is found in the variance reduction literature (see for instance Alacaoglu & Malitsky (2021, Assumption 1) or Arjevani al. (2019)). However, our use of the assumption are different in a crucial way. Whereas the variance reduction literature uses the stepsize y x 1/Lç (see e.g. Alacaoglu & Malitsky (2021, Theorem 2.5)), we aim at using the much larger y 1/Lr. For instance, in the special case of finite sum problem of size N, the mean square smoothness constant Lp from Assumption III can be vN times larger than Lp (see Appendix I for details). This would lead to prohibitively strict requirement on the degree of allowed nonmonotonicity through the relationship p -7/2
2

---

Published as a conference paper at ICLR 2023
Bias-correction The idea of adding correction term has also been exploited in minimization, specifically in the context of compositional optimization Chen et al. 12021). Due to their distinct problem setting it suffices to simply extend stochastic gradient descent (SGD), albeit under addi- tional assumptions such as (Chen et al., 2021, Assumption 3). In our setting, however, SGD is not possible even when restricting ourselves monotone problems.
3 PROBLEM FORMULATION AND PRELIMINARIES
We are interested in finding e R" such that the following inclusion holds,
0 Tz Az + Fz.
(3.1)
wide range of machine learning applications can be cast as an inclusion. Most noticeable, struc- tured minimax problem can be reduced to (3.1) as shown in Section 8.1. We will rely common notation and concepts from monotone operators (see Appendix for precise definitions). Assumption I. In problem (3.1).
(i) The operator R R" Lp- Lipsschht with Lp e [0, oo), i.e.
F| - Fz'll s L - z'll V2, E R".
(3.2)
(i) The operator A RR 3 R" is a maximally monotone operator.
(iti) Weak Minty variational inequality (MVI) holds, i.e., there exists nonempty set S* C zer T such that for all 2* E S* and some p E (- 2I. 20)
(v-2-2²) 2 pllvll for all (z, v) E gphhT.
(3.3)
Remark the unconstrained and smooth case (A 0), Assumption I(ūi)) reduces to (Fz,z-z") 2 p||Fz| for all RR When P 0 this condition reduces to the MVI (i.e. star-monotonicity), while negative p makes the problem increasingly nonmonotone. Interestingly, the inequality is not symmetric and one may instead consider that the assumption holds for -F. Through this observation, Appendix G extends the reach the extragradient-type algorithms developed for weak MVIs.
Stochastic oracle
We assume that cannot compute Fz casily. but instead have access to the stochastic oracle f(z. which we assume unbiased with bounded variance. We additionally assume that + f(z. 5) is Lp Lipschitz continuous in mean and that it can be simultancously queried under the same randomness.
Assumption II. For the operator f(:g): R" R" the following holds.
(i) Two-point oracle: The stochastic oracle can be queried for any two points z, R",
F(z,E),F(E F(2,E)) where & E-P.
(3.4)
(i) Unbiased: Bef ((( =z V²
(ii) Bounded variance: Be(1If(E,E) (())) s of R..
Assumption III. The operator f(,E): Th R² is Lipschitz continuous in mean with Lp E [0, oo);
B1(11((2,8) f(2', EMII < Lilk- z'11 for all 2,'' R.
(3.5)
Remark 2. Assumptions II(i) and III are also common in the variance reduction literature (Fang al., 2018; Nguyen et al., 2019; Alacaoglu & Malitsky, 2021), but in contrast with variance re- duction we will not necessarily need knowledge of Le to specify the algorithm, in which case the problem constant will only affect the complexity. Crucially, this decoupling of the stepsize from Lę will allow the proposed scheme to converge for larger range of p in Assumption I(iūi. Finally, note that Assumption II(i) commonly holds in machine learning applications, where usually the stochas- ticity is induced by the sampled mini-batch.
4 METHOD
To arrive at a stochastic scheme for weak MVI we first need to understand the crucial ingredients in the deterministic setting. For simplicity we will initially consider the unconstrained and smooth
3

---

Published as a conference paper at ICLR 2023
Algorithm (BC-SEG+) Stochastic algorithm for problem (3.1) when A 0
REQUIRE x- === = E R" a E (0, 1), y E 1/1pp).//L)))
REPEAT for k = 0,1,,.... until convergence
1.1:
Sample & =P
1.2:
= -
+ -x) - +yF(t-)).50
1.3:
Sample & ~ p
1.4: ztll = = a (t)
RETURN 2+1
setting, i.. A = 0 in (3.1). The first component is taking the second stepsize smaller done in extragradient+ (EG+),
전 = z A+l = aryFt
(EG+)
where a E (0, 1). Convergence in weak MVI was first shown in Diakonikolas et al. (2021) and later tightened by Pethick et al. (2022), who characterized that smaller allows for a larger range of the problem constant Taking a small is unproblematic for a stochastic scheme where usually the stepsize taken diminishing regardless.
However, Pethick et al. (2022) also showed that the extrapolation stepsize plays critical role for convergence under weak MVI. Specifically, they proved that a larger stepsize y leads looser bound on the problem class through p -y/2. While a lower bound has not been established we provide an example in Figure 3 of Appendix H where small stepsize prevents convergence. Unfortunately, picking y large (e.g. as y 1/2,) causes significant complications in the stochastic case where both stepsizes are usually taken to be diminishing as in the following scheme,
z = 2 - B
with & PP
(SEG)
|+! = - a.yf(et & with & ~~P
where a = Br oc 1/x. Even with a two-timescale variant (when Pg > a²) it has only been possible to show convergence for MVI (i.e. when p 0) (Hsieh et al., 2020). Instead of decreasing both stepsizes, Pethick et al. (2022) proposes a scheme that keeps the first stepsize constant,
전² = (F( with &x ا+l = a . with E-
SEE++)
However, (SEG+) does not necessarily converge even in the monotone case as we illustrate in Figure The non-convergence stems from the bias term introduced by the randomness of in P(z ()) Intuitively, the role of z is to approximate the deterministic exploration step = -==--Fa While 전 is an unbiased estimate of 2 this does not imply that f(Z is an un- biased estimate of F(2). Unbiasedness only holds in special cases, such as when F is linear and = for which we show convergence of (SEG+) in Section under weak MVI. In the monotone case it suffice to take the exploration stepsize y diminishing (Hsieh et al., 2020, Thm. I), but this runs counter to the fixed stepsize requirement of weak MVI.
Instead propose bias corrected stochastic extragradient+ (BC-SEG+) in Algorithm 1. BC-SEG+ adds a bias correction term of the previous operator evaluation using the current randomness &s. This crucially allows to keep the first stepsize fixed. We further generalize this scheme constrained and regularized setting with Algorithm 2 by introducing the use of the resolvent, (id + y
5 ANALYSIS OF SEG+
In the special case where is affine and A we can show convergence of (SEG+) under weak MVI up to arbitrarily precision even with a large stepsize y. Theorem 5.1. Suppose that Assumptions I and II hold. Assume Fz Bz + v and choose as E (0, 1) and y E (0, 1/LF) such that 2 y(ax 1)/2. Consider the sequence (z² (et) generated by (SEG+).
Then for all zt E St.
12 E
(5.1)
7211-A1 Ef
4

---

Published as a conference paper at ICLR 2023
10-
00'7
00-1
PyREG-
7,500 (1)
BCCINND (y- (u))
1030 (y 1o0
Figure 1: Monotone construined case illustrating the issue for projected variants of (SEG+) (see Ap- pendix H.2 for algorithmic details). The objective is bilinear dxx,y (x 0.9) (y 0.9) under box constraints y)l.
1. The unique stationary point (x* y²) = (0.9, 0.9) lies the interior, even [lF can be driven to zero. Despite the simplicity of the problem both projected variants of (SEG+) only converges to y-dependent neighborhood. For weak MVI with p < O this neighborhood cannot be made arbitrarily small since y cannot be taken arbitrarily small (see Figure 3 of Appendix HI..
The underlying reason for this positive results that ((z is unbiased when F linear. This no longer holds when either linearity of F is dropped or when the resolvent is introduced for A æ 0, in which case the scheme only converges to a y-dependent neighborhood as illustrated in Figure 1. This problematic in weak MVI where y cannot be taken arbitrarily small (see Figure 3 of Appendix H).
6 ANALYSIS FOR UNCONSTRAINED AND SMOOTH CASE
For simplicity we first consider the case where A = O. To mitigate the bias introduced in F(z -E:) for (SEG+), we propose Algorithm which modifies the exploration step. The algorithm can be seen particular instance of the more general scheme treated in Section 7.
Theorem 6.1. Suppose that Assumptions I to III hold. Suppose in addition that y E (l-2pl., 1/tr) and (EN (0, 1) is a diminishing sequence such thut
,1ī Then, the following estimate holds for all S*
2yL Vag (1 (-713 LG))> L.) a S 11+ 20
(6.1)
(1 ny U. M1 201 112 Co ΣK 2
B1I
(6.2)
1 1C (rj
1 レー y Lb y11 vin
where = 1 2n) 1) 200). 17 chosen from (0, 1.....K K) according probability Plk. = k] Σn
H (1- and k, is
Remark 6.2. As ag O, the requirement (6.1) reduces to p > -7/2 in the deterministic setting of Pethick et al. (2022). Letting d' anf yker the rate becomes O(1/ vR), thus matching the rate for the gap function of stochastic extragradient in the monotone case (see e.g. Juditsky al. (2011)). O
The above result provides a rate for a random iterate pioneered by Ghadimi & Lan (2013). Show- ing last iterate results even asymptotically is more challenging. Already in the monotone case, vanilla (SEG) (where Bx ax) only has convergence guarantees for the average iterate (Juditsky et al., 2011). In fact, the scheme can cycle even in simple examples (Hsieh et al., 2020, Fig. 1).
Under the classical (but more restrictive) Robbins-Monro stepsize policy, it is possible to show almost sure convergence for the iterates generates by Algorithm 1. The following theorem demon- strates the result in the particular case of as 1/ker. The more general statement is deferred to Appendix D.
Theorem 6.3 (almost sure convergence). Suppose that Assumptions to III hold. Suppose y 1 (L-2p)+, 1/L.), 0g key for any positive natural number and
(yLp + Daa +
Ity/1
1-7
L, + yLp Jarent + Da $ 2
(6.3)
5

---

Published as a conference paper at ICLR 2023
Algorithm 2 (BC-PSEG+) Stochastic algorithm for problem (3.1)
REQUIRE x- = R", h- R", ag (0, 1). y E (L-2pl++, 1/Lpp)
REPEAT for k 1,... until convergence
2.1: Sample & p
2.2: H = - yF(c-yieeeee .()c + (1 an) -
(+-11 -
-yf(tt-
2.3: *= (id yA)
2.4: Sample & ~ -p
2,5: gktl = E az(l - + y .2))
RETURN g+1
Then, the sequence ReN generated by Algorithm converges almost surely to some zt zer T. Remark 6.4. As an O the condition on p reduces to p -1/2 like in the deterministic case.
To make the results more accessible, both theorems have made particular choices of the free param- eters from the proof, that ensures convergence for a given p and y. However, since the parameters capture inherent tradeoffs, the choice above might not always provide the tightest rate. Thus, the more general statements of the theorems have been preserved the appendix.
7 ANALYSIS FOR CONSTRAINED CASE
The result for the unconstrained smooth case can be extended when the resolvent is available. Al- gorithm 2 provides direct generalization of the unconstrained Algorithm 1. The construction relies on approximating the deterministic algorithm proposed in Pethick et al. (2022), which iteratively projects onto a half-space which guaranteed contain the solutions. By defining Hz Z yFz, the scheme can concisely be written as,
* = (1 711
(CEG+)
d+l = = - an -
for a particular adaptive choice of a E (0, 1). With a fair amount hindsight we choose to replace Hz with the bias-corrected estimate ht (as defined in Step 2.2 in Algorithm 2), such that the estimate also reused in the second update.
Theorem 7.1. Suppose that Assumptions I to III hold. Moreover, suppose that a E (0, y (l-2p) 1/t,) and the following holds,
- 2 + + >
(7.1)
Vas
where 1)
Vonu
Consider the sequence (z') (E")eN KEN generated by Algorithm 2. Then, the
1,
Vim
following estimate holds for all x" E S*
Bllk& - + - 11
Cy x a
E(dist(O, T2.
y² Ex
where C 2n(11 + (2)) + 2no and k2 is chosen from (0, I..... K) according to probability
Plk, = =k]
Remark 3. The condition p in (7.1) reduces p -X/2 when de 0 as in the deterministic case. As oppose to Theorem 6.3 which tracks 1|2 the convergence measure of Theorem 7.1 reduces ? ||FZ11 when A 0. Since Algorithm and Algorithm 2 coincide when A = 0, Theorem 7.1 also applies to Algorithm 1 in the unconstrained case. Consequently, we obtain rates for both || and ||F2/1|2 in the unconstrained smooth case.
ASYMMETRIC & NONLINEAR PRECONDITIONING
In this section we show that the family of stochastic algorithms which converges under weak MVI can be expanded beyond Algorithm 2. This is achieved by extending (CEG+) through introducing

---

Published as a conference paper at ICLR 2023
Algorithm 3 Nonlinearly preconditioned primal dual extragradient (NP-PDEG) for solving (8.5)
REQUIRE x- 2" (x².y9 ,y) with x², xx.x'.,""" 1......' RRR,".." ER. 0e (0,)
~0
REPEAT for k = 0, 1,... until convergence
3.1: & ~
3.2: 8 = -IVV (1-)a=))))+++00=====)00== +
3.3: & =prox;
! (+*)
3.4 E. P
3.5 8 = y +T2(HV, (
3.6:
+(1 - +(1-ax)
- - -2(0V, .50 (1 (
3.7: 5 -prxxx
_ (ft)
3.8: & P
3.9: xt+1 = x + as 1t - 8t VE :t)
3.10: yht1 = = + a (5t -²t + (. -t)
RETURN dill (xlttl (etl)
a nonlinear and asymmetrical preconditioning. Asymmetrical preconditioning has been used in the literature to unify a large range of algorithm in the monotone setting Latafat & Patrinos (2017). A subtle but crucial difference, however, is that the preconditioning considered here depends nonlin- early the current iterate. As it will be shown in Section 8.1 this nontrivial feature is the key for showing convergence for primal-dual algorithms in the nonmonotone setting.
Consider the following generalization of (CEG+) by introducing potentially asymmetric nonlinear preconditioning P that depends on the current iterate ztt
find 전 such that
1₂(2²) E P2 + A(Z). = -
(8. la)
update
(b.
where Hv(v) := Pa(v) - F(v) and I is some positive definite matrix. The iteration independent and diagonal choice P y and r yl correspond the basic (CEG+). More generally we consider
Pa(=) = 1 Qu(=)
(8.2)
where Qz(z) captures the nonlinear and asymmetric part, which ultimately enables alternating up- dates and relaxing the Lipschitz conditions (see Remark (.i() Notice that the iterates above does not always yield well-defined updates and one must inevitably impose additional structures on the preconditioner (we provide sufficient condition in Appendix F.I). Consistently with (8.2), in the stochastic case we define
p=t.,):=I'z+ Qn(z.g).
(8.3)
The proposed stochastic scheme, which introduces a carefully chosen bias-correction term, is sum- marized as
compute Hº - +1 - Pt- ...+ f(c ,Ex)
(8.4a)
Qu- + (++ (5p) with E,E, ~p
find z such that # # Pt AF#
(8.4b)
update 1+1 an P 2t) ( -\)
with E ~P
(8.4c)
Remark 4. The two additional terms in (8.4a) are due the interesting interplay between weak MVI and stochastic feedback, which forces a change of variables (see Appendix F.4).
To make a concrete choice of (z(zg)) we will consider a minimax problem motivating example (see Appendix F.1 for a more general setup).
8.1 NONLINEARLY PRECONDITIONED PRIMAL DUAL HYBBRID GRADIENT
We consider the problem of
minimize maximize xER=
f(x) + ((x,)) 80). -g0).
(8.5)
7

---

Published as a conference paper at ICLR 2023
where yxxx,) y) := yg(((x,),.)) The first order optimality conditions may be written as the inclusion 0 T= = Az Fz, where = (öf.0g) F(z) - -
(8.6)
while the algorithm only has access to the stochastic estimates f(z.E)= (V, -V,(Z, E)). Assumption IV. For problem (8.5), let the following hold with stepsize matrix blkdiag(T [2) where 1 E R" and 2 R' are symmetric positive definite matrices:
(i) f. g are proper Isc convex
(ii q R - R is continuously differentiable and for some symmetric positive definite matrices
Dxa, Day. Dyn, Dyy the following holds for all z (x. y') R
[V,e((e) V=+p()))i,, = 1'gllx' xIlB
12 1ly >llaa
(1 0) L - -xll,,. + -Lglls' - -ylb,,
(iii Stepsize condition: 12 12 < T and 12g + 1 Dry r
(iv) Bounded variance: Be Be(1iR(e,E) F(d,, (ttd. of Vz,z' E R".
(v) ((,,)) Ratt + R is continuously differentiable and for some symmetric positive definite ma- trices Dj. Dÿ., Djs, Dÿy, the following holds for all = (x,y). = (x,y)) E R= and v, v E R"
for & 10, Be VV -V,42, 5/A
12 =llb2
i 1: [V 00 s 1/ -2lBp
M1
if0 0: (VV v,
1 - -vils, + +1y ylby.
Remark 8.1. In Algorithm 3 the choice of 0 e [0, oo) leads to different algorithmic oracles and underlying assumptions in terms of Lipschitz continuity Assumptions IV(íi) and IV(v).
(i) If 0 0 then the first two steps may be computed in parallel and we recover Algorithm 2. Moreover, to ensure Assumption [V in this case it suffices to assume for L,, L, E (0,,,),
[|V,p(z)= v.4(2))l= s L.lk'' - zll. [V,,p(z) Vyy(()) Lylkz' - z]]-
(i)) Taking 0 = leads to Gauss- Senussl updates and a nonlinear primal dual extragradient algorithm with sufficient Lipschitz continuity assumptions for some L,x, by [0, co),
[V,,((z) v,4(z)) s L,lla' - zll. IVV,((=)) - V,Ø(x', y)ll s L,lly' - yll.
Algorithm 3 is an application of (8.4) applied for solving (8.6). In order to cast the algorithm as an instance of the template algorithm (8.4), we choose the positive definite stepsize matrix as r = blkdiag(T, I2) with r > 0, I2 > 0, and the nonlinear part of the preconditioner as (.(2.))= = (o. ((). and 2x(3) = (0.
(8.7)
where u = yx and ج = (). Recall Hz(z)= = Pa(=) F(z) and define S Sz(z; = - Q,(
The convergence in Theorem 8.2 depends on the distance between the initial estimate I r- with g-1 = (f-1, 1 and the deterministic S (z ;,,1, See Appendix B for additional notation.
Theorem 8.2. Suppose that Assumption I(ii)) to Ii(ii) and IV hold. Moreover, suppose that (0, 1), 0 E [0, oo) and the following holds,
Vin + 3/ ao - 20ro(:1 + 20 + C2)) > and 1 - 422000 > 0
(8.8)
where y denotes the smallest eigenvalue ofT, 17 2 (1 4220 |1o(----)
1- 1- yom
)(1 4220ro) and
é 12 D 2(1 1 IDD 20 12 211ll, 2 = 20 II, Drall. 83 1.2 DT
22 = max (22 D Il + 12 LI, ril. II2 11y + 22 Dn
Consider the sequence (2 AEN generated by Algorithm 3. Then, the following holds for all zt e S*
(eE
Eldistr 73 )s B|||=" z" 1 + 1 - -s
Co2 Σx= o²
a)
8

---

Published as a conference paper at ICLR 2023
1011
107
1077
00'11
1071
SF EiGe
50 PRGC
5005
0077 15000
Figure 2: Comparison of methods in the unconstrained setting of Example 2 (left) and the constrained setting of Example (right). Notice that only BC-SEG+ and BC-PSEG+ converges properly while (SEG) diverges, (PSEG) cycles and both (SF-EG+) and (SF-PEG+) only converge neighborhood. BC- (P)SEG+ is guaranteed to converge with probability as established through Theorem 6.3 and ??
where C = 2(17 ao( 1 and k, is chosen from (0, I...., , according to probability Plk,
)1 282) + + + +82( (3 with Q = (1 (1-0)² 0)² 202
Σ
Remark 5. When ap 0 the conditions in (8.2) reduces 1 3/ in the deterministic case.
For Algorithm 3 reduces to Algorithm 2. With this choice Theorem 8.2 simplifies, since the constant 2 = O, and we recover the convergence result of Theorem 7.1.
EXPERIMENTS
We compare BC-SEG+ and BC-PSEG+ against (EG+) using stochastic feedbbacc (which we refer to (SF-EG+)) and (SEG) in both unconstrained setting and constrained setting introduced in Pethick et al. (2022). See Appendix H.2 for the precise formulation the projected variants which we denote (SF-PEG+) and (PSEG) respectively. In the unconstrained example control all problem constant and set p = - 1/ while the constrained example a specific minimax problem where p -1/2,, holds within the constrained constrained set. To simulate a stochastic setting in both examples, we consider additive Gaussian noise, i.e. f)z.g) Fz + & where ~ N(0, o² /). In the experiments we choose or 0.1 and ag o 1/s, which ensures almost sure convergence of BC-(P)SEG+. For more aggressive stepsize choice a; 1/ see Figure Further details can be found in Appendix H.
for Lipsehitz constant Lp restricted to the same
The sequence generated by (SEG) and (PSEG) diverges for the unconstrained problem and cycles in the constrained problem respectively. and (SF-PEG+) gets within neighborhood of the solutions but fails to converge due to the non- diminishing stepsize, while BC-SEG+ and BC-PSEG+ converges in the examples.
The results are shown in Figure 2.
comparison (SF-EG+)
10 CONCLUSION
This paper shows that mononnncveee problems characterize by the weak Minty variational inequality can be solved efficiently even when only stochastic gradients are available. The approach crucially avoids increasing batch sizes by instead introducing bias-correction term. We show that convergence is possible for the same range of problem constant p E (-7/2, oo) as in the determin- istic case. Rates are established for a random iterate, which matches those of stochastic extragra- dient in the monotone case, and the result is complemented with almost sure convergence, thus providing asymptotic convergence for the last iterate. We show that the idea extends to a family of extragradient-type methods which includes nonlinear extension of the celebrated primal dual hy- brid gradient (PDHG) algorithm. For future work it is interesting to see the rate can be improved by considering accelerated methods such Halpern iterations.

---

Published as a conference paper at ICLR 2023
11 ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement n 725594 time-data). This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 200021_205011. The work of the third and fourth author was supported by the Research Founda- tion Flanders (FWO) postdoctoral grant 12Y7622N and research projects GO8 1222N, G033822N, G0A0920N; Research Council KU Leuven C1 project No. C14/18/068; European Union's 's Horizon 2020 research and innovation programme under the Marie Sklodowska-Cuni grant agreement No. 953348. The work of Olivier Fercoq was supported by the Agence National de la Recherche grant ANR-20-CE500-022, Optimal Primal-Dual Algorithms (APDO).
REFERENCES
Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality meth- ods. arXiv preprint arXiv:2102.08352 2021.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1rXiv:1912.022 2019.
Heinz H. Bauschke and Patrick L. Combettes. Convex analysis and monotone operator theory in Hilbert spaces. CMS Books in Mathematics. Springer, 2017. ISBN 978-3-319-481108.
Heinz H Bauschke, Walaa M Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Mathematical Programming, 189(1)555-74, 2021.
Dimitri P. Bertsekas. Incremental proximal methods for large scale convex optimization. Mathe-
matical programming, 129(2):163-195, 2011.
Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradi- ent descent-ascent: Unified theory and new efficient methods. arXiv preprint arXiv:2202.07262, 2022.
Axel Böhm. Solving noncomnee--noncoocavy min-max problems exhibiting weak minty solutions. arXiv preprint wrXiv:2201.122477 2022.
Radu Ioan Bot, Panayotis Mertikopoulos, Mathias Staudigl, and Phan Tu Vuong. Minibatch forward- bockward-forwand methods for solving stochastic variational inequalities. Stochastic Systems, (2):112-139, 2021.
Xufeng Cai, Chaobing Song, Cristóbal Guzmán, and Jelena Diakonikolas. A stochastic Halpern iteration with variance reduction for stochastic monotone inclusion problems. arXiv preprint arXiv:2203.09436. 2022.
A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applica- tions to imaging. Journal of Mathematical Imaging and Vision, 40(1):120-145, 2011.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937- 4948, 2021.
Patrick L Combettes and Teemu Pennanen. Proximal methods for cohypomonotone operators. SIAM journal control and optimization, 43(2):731-743 2004.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Anmual ACM SIGACT Symposium Theory of Computing, pp. 1466-1478, 2021.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for struc- tured canconvex--ooccneee min-max optimization. In International Conference on Artificial Intelligence and Statistics, pp. 7754-2754. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2023
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic -att-nnterrtte differential estimator. Advances Neural Information Processing Systems, 31, 2018.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-236 2013.
Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou. Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, pp. 7865-7901, PMLR, 2022.
M Hirsch and Vavasis. Exponential lower bounds for finding Brouwer fixed points. Proceedings of the 28th Symposium on Foundations of Computer Science, pp. 401-410, 1987.
Yu-Guan Hsich, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. Advances in Neural Information Processing Systems, 32, 2019.
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggres- sively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. arXiv preprint arXiv:2003. 2020.
Anatoli Juditsky. Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Aswin Kannan and Uday V Shanbhag. Optimal stochastic extragradient schemes for pseudomono-
tone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74(3):77-8800, 2019.
Puya Latafat and Panagiotis Patrinos. Asymmetric
adjoint splitting for solving monotone inclusions involving three operators. Computational Optimization and Applications, 68(1):57-955 Sep 2017.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. arXiv preprint arXiv:2 /06.0236, 2021.
Chris Junchi Li, Yaodong Yu, Nicolas Loizou, Gauthier Gidel, Yi Ma, Nicolas Le Roux, and Michael Jordan. On the convergence of stochastic extragradient for bilinea games using restarted iteration averaging. In International Conference Artificial Intelligence and Statistics, pp. 9793-9826.
PMLR, 2022.
Nicolas Loizou, Hugo Berard, Alexia Dolicoeur-Martineall Pascal Vincent, Simon Lacoste-Julice and Ioannis Mitliagkas. Stochastic hamiltonian gradicnt methods for smooth games. In Interna- tional Conference on Machine Learning, pp. 6370-6381. PMLR, 2020.
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Advances in Neural Information Processing Systems, 34: 19095-19108, 2021.
Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revis- iting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, pp. 4573-4582. PMLR, 2020.
Lam M Nguyen, Marten van Dijk, Dzung T Phan, Phuong Ha Nguyen, Tsui- Wei Weng, and Jayant R Kalagnanam. Finite-sum smooth optimization with SARAH. arXiv preprint 100iv:1901000600 2019.
Thomas Pethick, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq, and Volkan Cevher. Escaping limit cycles: Global convergence for constrained conconvex-nonconeee minimax problems. In International Conference on Learning Representations, 2022.
Ralph Tyrell Rockafellar. Convex analysis. Princeton University Press, 1970.

---

Published as a conference paper at ICLR 2023
Chaobing Song. Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrapo- lation for coherent mon-monotonn variational inequalities. Advances in Neural Information Pro- cessing Systems, 33:14303-14314 2020.
Tseng. A modified forward-backward splitting method for maximal monotone mappings. SIAM
Journal on Control and Optimization, 38(2):331-44,, 2000.
Junchi Yang. Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for class of noneonvex-noneomeee nonconcave minimax problems. arXiv preprint arXiv:2002.09621, 2020.
12

---

Published as a conference paper at ICLR 2023
Appendix
TABLE OF CONTENTS
Prelude
14
Preliminaries
14
C Proof for SEG+
15
Proof of Theorem 5.1
15
Proof for smooth unconstrained case
16
Proof of Theorem D.2
16
Proof of Theorem 6.1
18
Proof of Theorem D.3
19
Proof of Theorem 6.3
20
Proof for constrained case
21
Proof of Theorem E.2
Proof of Theorem 7.1
23
Proof for NP-PDEG through a nonlinear asymmetric preconditioner
23
F.1
Preliminaries
23
F.2
Deterministic lemmas
24
F3
Stochastic results
25
Proof of Theorem F.5
26
Proof of Theorem 8.2
30
F.4
Explanation bias-correction
30
G Negative weak Minty variational inequality
31
Experiments
32
H.1 Synthetic example
32
H.2 Additional algorithmic details
33
I Comparison with variance reduction
34
13

---

Published as a conference paper at ICLR 2023
Table 1: Overview of the results. The second row is obtained as special cases of the first row.
Unconstrained & smooth (A = 0)
Constrained (A स 0)
Random iterate Theorem D.2
Last iterate
BC-PSEG+
NP-PDHG
Appendix
Theorem D.3
Theorem E.2
Theorem F.5
U
U
V
Main paper
Theorem 6.1
Theorem 6.3
Theorem 7.1
Theorem 8.2
A PRELUDE
For the unconstrained and smooth setting Appendix C treats convergences of (SEG+) for the re- stricted case where F is linear. Appendix shows both random iterate results and almost sure con- vergence of Algorithm 1. T.Thhorems 6. 1 and 6.3 in the main body are implied by the more general re- sults in this section, which preserves certain free parameters and more general stepsize requirements. Appendices E and F moves beyond the unconstrained and smooth case by showing convergence for instances the template scheme (8.1). The analysis of Algorithm in Appendix applies to Al- gorithm 2, but for completeness establish convergence for general F separately in Appendix E. The relationship between the theorems are presented in Table
B PRELIMINARIES
Given a psd matrix V we define the inner product as (t.-)v == (., and the corresponding norm set 2/ R" with respect a positive definite matrix
|| = dy. The distance from u V is defined as disty(", 2() == min.eu |lu u'llv, which we simply denote dist(u, U. when V = I. The norm [|X|] refers to spectral norm when X is a matrix.
We summarize essential definitions from operator theory, but otherwise refer to Bauschke & Com- bettes (2017); Rockafellar (1970) for further details.
An operator A R² 3 Rd maps each point E R" to subset Ax Rd, where the notation A(x) and Ax will be used interchangably. We denote the domain of by dom A [x E R" Ax # 0), its graph by gph == ((x,)) E R" x Rd E Ax). The inverse of A is defined through its graph, gph = x) (x E gph A] and the set of its zeros by zer = (x E R" Ax).
Definition B.1 montonnityy Bauschke et al. (2021)). An operator A R" 3 R" said to be p-monotone for some e IR, if for all (x,)), (x', (x) gphA1
xy-y,x-x) x') 2 p|
and it is said to be p-comonotone for all (x. g
(v-y,x-x)) poli-xx)>>llyy>>// -
The operator A is said to be maximally (co)monotone there exists other (monotoee operator B for which gph A c gph B properly.
is O-monotone we simply say it monotone. When p < O, p-comonotonicity is also referred to as ppl- cohypomoootoniccty. Definition B.2 (Lipschitz continuity and cocoercivity). Let D C R" be nonempty subset of R". A single-valued operator D R" is said to L-Lipschitz continuous if for any x, e D
||Ax - Ax'I s D||x x'll.
and ccccoorrceeeeeeeeee if
' Ax' 2 BIAAX Ax'1I
Moreover, A is said to be nonexpansive if 1-Lipschitz continuous, and firmly nonexpansive if is l-cocoercive.
8-cocoercive operator is also 8- -Lipschitz continuity by direct implication Cauchy-Schward The resolvent operator JA (id + A) is firmly nonexpansive (with dom Ja RR) if and only if A is (maximally) monotone.
We will make heavy of the Fenchel- Young inequality. For all b RR and 0 have,
14

---

Published as a conference paper at ICLR 2023
2(a, b) z e||a|l + 11bb1
(B.1)
||a bll (1 e)l|all (1 + I)1bb1
(B.2)
-l|a bll - The Iall !|bbi
(B.3)
C
PROOF FOR SEG+
Proof of Theorem 5.1. Following (Hsieh et al., 2020) closely, define the reference state _ : yF to be the exploration step using the deterministic operator and denote the second stepsize as Th azy. We will let denote the additive noise term, i.e. f(z,E) F(z) + 5. Expanding the distance to solution,
|| - 2 lk T7. F --)=-11
|k - =² 2m Ec), - + + &WII
(C.1)
Ik - z²1p² (f -t), 2h -z²)=------ - 2y (E &t) F(Eh) + PE &WIl..
Recall that the operator is assumed to be linear Fz = Bz + in which case we have,
f(E'. B + + Ze
= =B(e yF .k,) + V Zx
=B(2² yB yv 744 V &
(C.2)
=B(L² y(tt + r)) + - y
- + 2r-
The two latter terms are zero in expectation due the unbiasedness from Assumption IT(i),, which lets us write the terms on the RHS of (C.1) as,
EF こ²) = - BF
(C.3)
= -(F(()),(())
(C.4)
B &WIl = =IF BBlly B.lZZ
(C.5)
We can bound (C.3) directly through the weak MVI in Assumption I(iii) which might still be posi- tive,
(F - オー) -
(C.6)
For the latter terms of (C.5) have
BxllyBaa1? Bellžall = ( F()) + EaIielP & 1y 1)0
(C.7)
where the last inequality follows from Lipschitz in Assumption I(i) and bounded variance in As- sumption I((ū)..
Combining everything into (C.1) we are left with Bxll=*+1 - =1 s I1 - -12 + 2 + Do - (F F(eh) + Or (
(C.8)
By assuming the stepsize condition, (n 2)/2, we have oî - 2np S ymk. This allows us to complete the square,
-2ym F(E)) of 2 -2ym ymil
$ F(
= -( -
(C.9)
-
where the last inequality follows from Lipschitzness of F and the definition of the update rule. Plugging into (C.8) we are left with
E+ =²122 z I - =-1 L 1)0 ym -
(C.10)
The result is obtained by total expectation and summing.
L
15

---

Published as a conference paper at ICLR 2023
D PROOF FOR SMOOTH UNCONSTRAINED CASE
Lemma D.1. Consider the recurrent relation Be+1 ExBs + dg such that & 0 for all k 2 0. Then
de
B++1 (II (=0p= Bo Σ
D p=ofo
Assumption V. y (l-2p)+, 1/1s) and for positive real valued b, bb # == (1
(D.1)
Theorem D.2. Suppose that Assumptions to III hold. Suppose in addition that Assumption V holds and that (a2) C (0, 1) is diminishing sequence such that
2yL Var + (1 ((b 1yy,,),, 00 S 1+ 1
(D.2)
Consider the sequence (z REN generated by Algorithm Then, the following estimate holds
- 11F(( + Co 2--0
at
B(F
(D.3)
11 E_ aj
K=0
a-
where C + 2n + 1) + 200) and 17 {bb 1
yhs vi
Proof of Theorem D.2. The proof relies establishing a (stochastic) descent property the fol- lowing potential function
Us+t == ||e - z²112 + A As- + B e/p2.
where n² 2 F((+) measures the difference of the bias-corrected step from the deterministic exploration step, and (Ae),n: (Bx)en are positive scalar parameters to be identified. We proceed to consider each term individually.
Let us begin by quantifying how well estimates - yF((t).
x² = - 2 + yF(()) yF(e) yf(t (2) (1 a=) --1 + +yf(s .EO).
Therefore,
[1 1 Ex)
an) -0 1DI 11
(F(FFF))))))))))))) ,.((()) + - -- +
(x) ) (1 anlyy(etttt (x) yF(c
Conditioned on Fx. in the inner product the left term is known and the right term has expectation that equals zero. Therefore, we obtain
+(1-aa)211ut11p
< + =203 P
(z (WIPIIT
[Ta]
> 1f
(D.4)
where in the first inequality used Young inequality and the fact that the second moment is larger than the variance, and Assumptions II(iūi) and III were used in the second inequality.
By step 1.4, the equality
+|2 z0122 -11=-~2"
-2-112
(D.5)
16

---

Published as a conference paper at ICLR 2023
holds. The inner product in (D.5) can be upper bounded using Young inequalities with positive parameters E2, k 1 0, and as follows.
11-yyfe''E.e -2) = (((()))) -(
+ + - + -FF()) = - F(E))
s {>(( - F(2))1 - 2 |F(E ||p - 1IF) + Xe 11 2
2
11 _1=2= - + + yP( ypllF(=>11f Ilf
+ 22t
< y 14 1+b
1+b y [( - 11(E25)2
2
1|r +
2
2
/
|1F(tt)1 + 82
|IE( I1f + 1
- )X)
2
2
25%
L/ 1
|1lpp +
1)
|
=
2
28k
2
+ ( - 1)
(F)
(D.6)
2
Conditioning (D.6) with B[ = B|
F Fxl, since Tu yields
(11-F((2'E)..4 - こー) 1Fa S L2 + b) - BBI| Fi - =
8%
+ (y - 1) 1)- [1F(E ITa}
(D.7)
where μ was defined in (D.1).
The condition expectation of the third term in (D.5) is bounded through Assumption ll(iti) by
E(IIA FR E T| ( 2oIf
Fil Fzl
|F +z.
which in turn implies
B ||e - 1 = 03 ( Fi| s oz. || FF/ + o2
(D.8)
Combining (D.7), (D.8), and (D.5) yields
BlIk - -1 1 + B I1? - -11 | Fil
< 1| - z + (Ax.1 + az L3 + b) + E%
) [Tdl - ax)l)(((((()))
+ (1 (8x - 1) - 2yp) + ofrr² ) (1F(EEE DI F + az
+ B 2 |Fa|
+ 1
(D.9)
Further using (D.4) and denoting
x = =x((> 17 + b) + 1 + Asti.
x = ax(>'(E: 1) 2py + as x²)
leads to
B[ Fxl - U1: F(x))l )l2 (x-(1 -os)² - Ass) -Ai)lle
+ (2x7(1 ox) L.g- - Bi)) Bi)llt - 112 + (x² + (ariar))3(1reee NP Fi]
+ +BErTO + or 2x (r)))² 207
(D.10)
Having established (D.10), set A = A, BN = 2Ay L/x- and & = & to obtain by the law of total expectation that
B| - B[44] و - anyi |1 MP] (x1(11 - ax) - A)E(11=-11??
+ +2 -111-1ax)) az) - A) [1= 1| + (xt + L.
+ +(247213 + + +
(D.11)
17

---

Published as a conference paper at ICLR 2023
To get recursion require
a(1-a:)-As- and 2A S. By developing the first requirement of (D.12) we have,
(D.12)
0 x a1--a)²~ -A= ax(1 (y) L + = axlax 2)A.
(D.13)
Equivalently, A needs to satisty
(1 - a²)²²
A
L7 + b) + n
(D.14)
2 0%
for any ar (0, 1). Since
(-ax) 2-0
given az (0. 1) it suffice to pick
[b + 13 !
(D.15)
For the second requirement of (D.12) note that we can equivalently require that the following quan- tity is negative
x + 2Ay 2 L
32 + ax + 22 = = 1- 1--1- ..- + (b + 12 + L7))0
where we have used that on I an and the choice of A from (D.15). Setting the Young parameter & = yLL var we obtain that X + 2Ay 12 s 0 owing to (D.2).
On the other hand, the last term in (D.11) may be upper bounded by
2Ay 13 1 2x
= 1
(b 1 yhe von
(6) + 1) + +2xx)
$ 1 + (b 1)y²
*4s van ((>2 + 1) + 200) C.
Thus, it follows from (D.11) that
- s ann (IFEEIFF(>>?? Caty?oz
Telescoping the above inequality completes the proof.
Proof of Theorem 6.1. The theorem is obtained as particular instantiation of Theorem D.2.
2y²r3
The condition in (D.1) can be rewritten as b back into j we obtain
A reasonable choice is b 1-
Substituting
1-
# == y= ~=>
1-اي (11 0.
(D.16)
2y'1:
Similarly, the choice of b is substituted into 17 and (D.2) of Theorem D.2.
The rate in (D.2) further simplified by applying Lipschitz continuity of from Assumption I(i) to ||F22|12 ||F2 F2 The proof is complete by observing that the guarantee the weighted sum can be converted into an expectation over a sampled iterate in the style of Ghadimi & Lan (2013).
Assumption VI (almost sure convergence). Let d [0, 11, > Suppose that the following holds
(i) the diminishing sequence (aW)eN (0, 1) satisfies the classical conditions
Eie 0z = 00, à == Ei= of < oo;
(ii) letting e :1 b)b + yLp a for all k
m Ex (cranTT (1 - 00,
v Liz Tk. /11 (1 00,
(D.17)
and
yLLpa + az 2y² 12 an 1 p- 1 30
(D.18)
18

---

Published as a conference paper at ICLR 2023
Although at first look the above assumptions may appear involved, shown in Theorem D.3 clas- sical stepsize choice of on is sufficient to satisfy (D.17), and to ensure almost sure convergence kej provided that instead (D.20) holds. Note that with this choice as k goes to infinity, 0g > 0 and the deterministic range y + 2p > 0 is obtained.
Theorem D.3 (almost sure convergence). Suppose that Assumptions I to III hold. Additionally, suppose the stepsize conditions in Assumplions V and VI. Then, the sequence (z")eny generated by Algorithm/ I converges almost surely some z" zer Moreover, the following estimate holds
Ik 2² + noy"11F(E M1
+ +
ak B[IIF(2
(D.19)
1 EE
E
F0
where C= of ((> + +)y a( + (b+ D2 + +t,) is finite.
In particular, if a = koy for any positive natural number r, and d = 1, then Assumption Vi(ii) can be replaced by
(yLp 1) + +2((1+ + b)y L2 + yLF)) Da $1+ 2 (D.20)
y
Proof of Theorem D.3 (almost sure convergence). Having established (D.10), let B₃
such that (2x) - = - -as)² - - -Ae)lle 2-11
B.)IE'
(D.21)
In what follows we show that it is sufficient to ensure
x1(1 ar)) S Ac. X 24 11, O.
(D.22)
resulting in the inequality
B[U Fil Us S a( (2Ar11 1. + Ja?
(D.23)
A reasonable choice for the Young parameter E is to choose
yl.po! for some d E [0, 1]. The rational for this choice will become more clear in what follows.
(D.24)
The first inequality in (D.22) is linear and we can solve it to equality by Lemma D.1. Let
Ao Σ
(Car p= ax,))) 170 < and ==
(D.17)
A < c0.
(.17)
(D.25)
Z=
A=0
Furthermore, let C2 and m be as in Assumption Vi(ii). Then, Lemma D.I yields
Ac+1 [1T (1 a1-
Ao
Σ (Car)) - ap)²) 7 7=0
1T
(D.26)
p=0
ap,)
which would ensure A₁ 2 for all k. Therefore, assumptions (D.17) and (D.18) (which is a re- statement of the conditions in (D.22) are sufficient for ensuring (D.23), Substituting X and Aet1 in (D.23) yields
E 1 Fxl - U1 S -auull +E. where & = 2AA L2 + 1) + (b+ L,
(D.27)
of By Assumption VI we have a
that
Me Ex= 27 L3 1)
Σ
of 2
(b 1 L3
3-d
0
yT.
k=O
A=1
k=0
k=
$ $2 12 + 1)
a + +( + (b + 1y>²
< 0
A=0
where we used the fact that aj s af and d S in the first inequality, while the second inequality uses (D.25), and Assumption VI(i). The claimed convergence result follows by the Robbins- -Sieguud supermartingale theorem (Bertsekas, 2011, Prop. 2) and standard arguments as in (Bertsekas, 2011, Prop. 9).
The claimed rate follows by taking total expectation and summing the above inequality over k and noting that initial iterates were set z - =
19

---

Published as a conference paper at ICLR 2023
To provide an instance of the sequence (a that satisfy the assumptions, let r denote positive natural number and set
0 K+y"
(D.28)
Then,
II p- - aap)² = - (ppr)) )²
(r-1)" (tor
(r - 1)9
and for any K 0
[caaell p=o ox,))
Σ
(--1) (T+p
Cc.
1=0
1=0
Plugging the value of ct and from Assumption Vi(ii) and (D.24) we obtain that Ap is finite valued since Ee=D (C-ri'e, = 21=0 (etrjtdd
owing to the fact that
Moreover,
(k + r)2
8
Ag+1
(r 1)2
Ag
Σ (m0
(o-1 (etpy
ct)
r)2
(1tp)
Ct
(D.29)
(mk+1
Cmk+1
On the other hand, for we have the following bound
f Exeny dx (ktleny
Σ
o
i++1+ry +
(e-1)(e+1+r
(D.30)
[=k+1
Therefore, follows from (D.29) that
ARt1a = Σ
(a²(1 + byr + sto a)
t=k+1
(D.30) s (11 + byy Lp 2,t.o11) (z + Entor + ( (- Martor + 1)
= -1 (
L 0 (2 + De + ( a enl ( + 1)0x+1
a- $ 5(11 b L + xL,2-1) 1-d ( + 1)axt1
(D.31)
In turn, this inequality ensures that v as defined Assumption Vi(ūi) is finite. To see this note that
(D.31) E A E ((1 b + -
(0241 + D0g-107 5 & of oo,
where in the last two inequalities Assumption VI(i) was used.
remains confirm the second inequality in (D.22). With the choice of as and & as in (D.28) and (D.24) we have azy" (X2 + 2A (4,7)
= =yLpat -
04 + 2
(D.31) S YLoa + an + 2y² 1/2(11 (11 + 13are+1 + ,,,2- ( + 1) - 1- y.
It follows that with d the assumption (D.20) is sufficient to ensure that the second condition in (D.22) holds.
Proof of Theorem 6.3 (almost sure convergence). The result is a restatement the special case in Theorem D.3 where 0j Etr We proceed similarly to the proof of Theorem 6.1.
224 T-y-1,
A reasonable choice is b 2y243 Tー
The condition in (D.1) can be rewritten b of b is substituted into (D.1), (D.20) and Č of Theorem D.3. This completes the proof.
The choice
20

---

Published as a conference paper at ICLR 2023
E PROOF FOR CONSTRAINED CASE
We will rely from (Pethick et al., 2022, Lm. A.3) that we restate here for convenience.
well-known and useful properties of the deterministic operator H id yF
Lemma E.1. Let F R" R be a Lp Lipschitt operator and H id id-yF with E (0, 1/rr). Then,
(i) The operator is /2-cocoercive.
(i) The operator is (1 - -LF (yLs)-monne monooone, and in particular
| Hall 2 (1 - yLF)llz' - zll V2,z' E R"
(E.1)
Proof. The first claim follows from direct computation
(Il HE' z²) (IIz 11.,, 12- 112'
|||H2 - Hz'll² - 11F2' Fell + 1 - all² 2 3|| -||':-H''11..
(E.2)
where the last inequality is due Lipschitz continuity and y I 1/r, The strongly monotonicity of H is consequence of Seuchy-Schwarr and Lipschitz continuity of F.
(Hz' Hz,z' 2) = ||.' z|I - -((F2' - Fz,z' z) 2 (1 yl))kk' a|1.
The last claim follows from the Cauchy-Scheee Schhar inequality.
Theorem E.2. Suppose that Assumptions to III hold. Moreover, suppose that as E (0, 1), y (l-2pl+, 1/L)) and for positive parameters and b the following holds,
=== 1- all-yep)) - ag(1 12 > and all-yLe
(E.3)
where A 2 8 511 al-yLop). Consider the sequence (e*) generated by Algorithm 2. Then, the following estimate holds for all zt E S*
Blll2" 2=11=+ ABIII -12+ Σx
Li=0
BiI H2111
(E.4)
k=0
where C 2A(1 + +²( ) 200A.
Proof of Theorem E.2. We rely the following potential function,
Ukat || 1²1 A H²*112 + B -11
where (Aw)en and LeN positive scalar parameters be identified.
We will denote i := t - P E.), so that .++1 = & ag(h - Å..) Then, expanding one step,
d| 201 || 2 20 A - z²) aqlli A.,
(E.5)
Recall that Hz == - yFz in the deterministic case. In the Algorithm 2, A estimates H Let us quantify how good this estimation is.
ax- 01-1) + +yf(e+1.Ea) .E)) at H -f yf -E)
||A 2 (1 - au a - t-1 + 1111
+ +llyFt - -f(' ...) +1 a1-1)lyP(E .5x) - -
+ 2(1 ( - 1 +
yF - Ev) + (1 an-1)
)F
In the scalar product, the left term is known when 전 known and the right term has an expectation equal 0 by Assumption Ii(ū)) when & is known. Thus, taking conditional expectation and using
21

---

Published as a conference paper at ICLR 2023
the fact that the second moment is larger than the variance, can go BII - Hz'12 Ffa s (1 ax -
+ -1121 a1) -x) F( .EDIl [ill
-
=1 - - 1
2(1 1 -xg) - 1 20. (E.6) where we have used Assumption II(iii) and Assumption III.
s (1 -1-aa -
We continue with the conditional expectation of the inner term in (E.5).
-BIH - f.r. =>> = -(h² - -z²
-hh HE L -²² (hh Hº, z z²)
=(hh- 11 + - -IIE 11 Lt -tト (Hf -1 z z²)
-(hh- - - 111Ht* HEI (1F H22 ,t z*)
(E.7)
where the last inequality uses 1/2-cocoercivity of H from Lemma F.2(i) under Assumption I(i) and the choice y s 1/Lf.
By definition z in Step 2.3, we have h² E E + yA(t), so that { - -1*)= E F(zt) + A(Z"). Hence, using the weak MVI from Assumption I(iii).
-²> ElIn H2-112
(E.8)
Using (E.8) in (E.7) leads to the following inequality, true for any &N > O:
-B(hh - - - =²) [F) s IIIl" - H= + _ 1| - =112 +IImE== - HE²1 - -1I1"* H2²11
To majorize the term || AP, we use Lemma F.2(ūi) to get
|1E - H=-122 2 (1 > -
Hence, as long as yLF < 1, then
Bich A 2²) 1F s $1/ H211 (2a11---007 - 1111+ HE²1 -11 - H2222
(E.9)
The third term in (E.5) bounded by fi afBII
Fil
af'l HE'" of
F(E5.E01' 1F) S az HELl + af
(E.10)
Combined with the update rule, (E.10) can also be used to bound the difference of iterates
Blll+ - 2 Fil B[a Årl FF s afll - H2 + az Using (E.5), (E.9), (E) and (E.11) 1) have,
(E.11)
B[U
[2l S I 21 (Ax+1 -
Hz2112 - ail x 11 - -H2112
+ a,(a - 2 ag Be.1)))ll A1 - + a²(1 B B2
$ || - 2² + (A++1 + (z + {1 .
))ll H:-1
(E.12)
+ uulur - 20 2 ar Bi+1 + (1 -ل- )llkk* HE²1
+ af B
where the last inequality follows from Young's inequality with positive b and requiring 1 A(1-yTp]) 2 also stated in (E.3). By defining
x = Agai + ar(es
(1
-0(1-)177)))
(E.13)
x² an
32 + aa
22

---

Published as a conference paper at ICLR 2023
and applying (E.6), we finally obtain
B 1F1 Uu s X2lII* 12212
+ +xx aaa)² - A+lll H
(E.14)
-1 -a.) B&ll - 11 + 2x a2 aj + Ba-1
We can pick B₃ LgA, in which case, to get recursion, we only require the following.
(1 ((1-a))* - A s and x <0
(E.15)
Set A = A, = 8. For the first requirement of (E.15),
X at)² - A = a1 (6 + [[ x(1ー>, + (1 a A
s a (1 x )) + -1-a;)AA- -A
(E.16)
S a { <1-ylş} )) + + az) A
= a + [1 x1-ン|+
)) a
where the first inequality follows from (1 - a1) < 1 and the second inequality follows from (1 - aa) z (1 az). Thus, to satisfy the first inequality of (E.15) it suffice to pick
A E [1 -(1>,,}))
(E.17)
The noise term in (E.14) can be made independent of by using I a and (E.17) follows 1 + 2A(1 + + 20x + t/(1 xा-))_)))
2x + + B
(E.18)
1 2A(1 + 200A C.
Thus it follows from (4. and 0% S oz that
B[
Fdl - U
(E.19)
s ar az
32 + 20ro 2 1 - ((0--1--)))) )II 112-112 + atCy
y The result obtained by total expectation and summing the above inequality while noting that the initial iterate were set as z-' = z".
Proof of Theorem 7.1. The theorem a specialization of Theorem E.2 with a particular a choice of b and The second requirement in (E.3) can be rewritten as,
2 [1-yLe)F
(E.20)
which is satisfied by & \= We substitute in the choice of e, b = vag and denotes == A.
The weighted sum in (E.4) can be converted into expectation over sampled iterate in the style of Ghadimi & Lan (2013).
B[Ilh- H2--11]=
au BII H2
with k, chosen from (0, I...., K} according to probability Plk, k] Σ aj
Noticing that h - H E -(F + AF* = - so
B[|l 12*11 min B[]ly[| 2 B[ min [|yu[[2] =: B distt( (.. w
#57
where the second inequality follows from concavity of the minimum. This completes the proof.
PROOF FOR NP-PDEG THROUGH A NONLINEAR ASYMMETRIC PRECONDITIONER
F.1 PRELIMINARIE
Consider the decomposition 2 (Z),..., Zm)) u (U)...., um)) with 2₁. U1; E R and define the short- hand notation ugg == (41, 42, .2...., u;)) and My (Mi...,, Mm)) for the truncated vectors. Moreover sup-
23

---

Published as a conference paper at ICLR 2023
pose that A conforms to the decomposition Az (A,,Z1..... Am with A, RD 3 R" maximally monotone. Consistently with the decomposition define I b I....,Tmm mm) where r e R positive definite matrices and let
4z3)..... When P, furnishes such an asymmetric structure the preconditioned resolvent has full domain, thus ensuring that the algorithm is well-defined.
Pa(c) == r Qu(2), where Qx(2) (0, qı (2), uz2), 92(21. 22, ..... 9m- (Zsmm- Um)) (F.1)
In the following lemma we show that the iterates in (8. 1) are well-defined for a particular choice of the preconditioner P., in (F.1). The proof is similar to that of (Latafat & Patrinos, 2017, Lem. 3.1) and is included for completeness.
Lemma F.1. Let = (Zi,..., 2mn). u == (ui..... "iil....,uui Um) be given vectors, suppose that A conforms to the decomposition Az (A1, AmZm) with A; R = RR" maximally monotone, and let Pa be defined as in (F.1). Then, the preconditioned resolvent (Pu + AY is Lipschitz continuous and has full domain. Moreover, the update (Pn + A)=+ reduces the following update
+ -
if i=
(F.2)
+ +A (z ((
if i = 2...,
Proof. Owing to the asymmetric structure (F.1), the resolvent may equivalently be expressed as == (Z1......) Zmm) = (Pu + A) = 1 + A,(Z)) E (E-1(Eg-1,,,)) i= I....,,,
where 40 0. The Geaus-SSidel--yyee update (F.2) of immediate verification after noting that (r + A, is single-valued (in fact Lipschitz continuous) since the sum of r; > 0 and A; is (maxi- mally) strongly monotone. This also implies that r A, = Ā, f1 for some > 0 and some max- imally monotone operator Á, Thus dom (T,' + A)) range(I;" A,) range( A + D R", where we used Minty's theorem in the last equality.
L
F.2 DETERMINISTIC LEMMAS
To eventually prove Theorem E55 we will compare the stochastic algorithm (8.4) with its determin- istic counterpart (8.1), so we introduce
H2(z) = Pı(z) F(z)
(F.3a)
G(z) = (P: A)
(F.3b)
G(z) = -r--aT/// (r.-aTT((H())) -1,((())(H((G()) H((G())
(F.3c)
We first derive results for the deterministic operator G and then shows that et*1 from the stochastic scheme behaves similarly to G(z²) when ag small enough, even I, which also appears inside the preconditioner P.(.E), F), remains large.
Instead of making assumptions on directly, we instead consider the following important operator, M2(2) == F(z) Q.(2).
(F4)
such that write (F.3) as
M,(2). As shorthand write M(z) M,(z).
Assumption VII. The operator M,, as defined in (F.4) is LM LM-Lisschitz with LM S 1 with respect to a positive definite matrix I E Raxn i.e.
[M,(t)) M2(2')li Lulk - 2'1r- Vz. R". Remark 6. This is satisfied by the choice of Qu (8.7) and Assumptions iii and IV
(F.)
With M, defined, is straightforward to establish that H, is 1/2-cocoercive and strongly monotone.
Lemma E2. Suppose Assumption VII holds. Then,
(i) The mapping H,, is 1/2-cocoercive for all IR", i.e.
(H,(Z') - 2,,(z) - 2 )('H((²)) H₂(r) V2, E R".
(F.)
(i) Furthermore, Hμ is (1 Lm)-monotone for all u E R", and in particular [H,(z') H.(z))lr 2 (1 I zilr-1 Vz,z E RR.
(F.7)
24

---

Published as a conference paper at ICLR 2023
Proof. By expanding using (F.4),
H₂(2)- - H₂(() = 1- (2- (M,(2) M((E)).
(F.8)
Using this can show cocoercivity,
(Halz) - 2 - z) = (Ha(z) - HL(z), Hu(E) - H.(t) (Ma(z) - Ma(t()
(F88 }11H,(z') - Halellf Ellk' - =lff {11 Mule))ff
Assumption VII 2 }1|H((E') Hzl2lli
(F.9)
That H, is strongly monotone follows from Cauchy-Schwand and Assumption VII, (Hg(t)) H=(z),z' z) = =| - - (M,(z') M,(x).
(1 LM)llE' zlff-
(F.10)
The last claim follows from Sauchy-Schward and dividing by lk' - z||r-
We will rely on the resolvent remaining nonexpansive when preconditioned with variable stepsize matrix.
Lemma F.3. Let r RRaa be positive definite and the operator A IR" 3 R" be maximally monotone. Then, R (T~ + A) is nonexpansive, i.e. ||Rx - Ryllr- s ||x yllr for all x. E R".
Proof. Let v E Rx and u E Ry. By maximal monotonicity of A, - ||x ylf + (v (v- u, y).
0 (v (v r +,,',, y,x- y)
Therefore, using the Cauchy-Schwarc inequality
| ||--y0ドド s (v- u, y) ||xx yll 1|| u||
(F.11)
The proof is complete by rearranging.
F3 STOCHASTIC RESULTS
The stochastic assumptions on in Theorem F.5 propagates to M and Q. as captured by the follow- ing lemma.
Lemma F.4. Suppose Assumptions Iíūi) and IV(iv) for f(z, (V.g(z.)), ())(z,E)) defined in (8.6). Let M and M be defined in (F.15) and Qu and Qu as in (8.7) with 0 [0. oo). Then, the following holds for all z, R.
(i) BA(M(2,E)) = ((2) and
22(2)
(i) (+Il M(z, [ s ((1 (1- R)o and (xlllQ.- (. s oz.
Proof. Unbiasedness follows immediately through Assumption II(ii). For the second claim we have for all y) z R"
BellIM(2) M(z. 1IA Bg
v.((z, - (22(2) (V,((12,)) Top(=))
(VV,((2,)) - v.((2)) + +VV (1-0(V, v,,((2)
V,((Z,E) (.6(2) F, - (2p(2))
(.0(2,.) V.((())
(Assumption II(i)) (1 83²E5
10
0
(Assumption IV(ir)) - ((1-0) -)2 00
(F.12)
The last claim follows directly through Assumption IVviv). This completes the proof.
Theorem F.5. Suppose that Assumption I(ii)) to II(ii) and IV hold. Moreover, suppose that aş (0, 1), 0 E [0, oo) for positive parameter and the following holds,
# T
x|-La|) + 3/4 - 0ro 20r(Ce + 28,(1 (2))AA > 0,
(F.13
- 4820r > 0 and 1
al al- 2
25

---

Published as a conference paper at ICLR 2023
where y denotes the smallest eigenvalue of A (1 + 48sa))e t[11
اuاLاp 1)((1 - 48200) and
è = 1TT + 2(1 - 23 + 20 2 22 15:200 1011 Drlll := 2 Dell
Ls == max (L .r. Fill + L,, III.
+ Dyyll-
Consider the sequence (et) AEN
(EN generated by Algorithm 3. Then, the following holds for all x² S* B[[ - : BlIk z"Iff .I AB[]I --- - :Z + Cor, Σ o²
2,
1 22
(F.14)
where := 2(A + crp( + t(1 -11-<1-1ap) al-Lu) +))) 28,(1 + 23))AA and (1 (1-0))+20) 20
Proof of Theorem F.5. The proof relies on tracking the two following important operators instead of F and F
M(2) = F(z) - Qz(z) and M(z.5)== := F(z,E) (2
(F.15)
We will denote A. : P E.) fitt, ,E)) so that e(t1 + - are - M.). We will further need
the following change of variables later be able to apply weak MVI (see Appendix F.4):
st h² Q..(t'.5 .5)
8. = A (2.(t
(F.16)
5,(7) = HZ) - Qu(2)
S,(z;)) = (z) Qu(E)
where Qa(z) and H,, are as defined in Section 8.
In contrast with the unconstrained smooth we will rely slightly different potential function, namely,
Uk-1 == || - -z- 1 + A - (E( + Be- - d
where (AN)EN and (Bx) are positive scalar parameters be identified.
We start by writing out one step of the update
|| z" [p = ||=. z=Iff= 20x AA - + azll Auil
(F.17)
= ||.." - 20r - - azi1s* - 321f
(F.18)
In the algorithm, st estimates S (z"; Let us quantify how good this estimation is. We will make use of the careful choice of the bias-correction term to shift the noise index by in the second equality.
+ -(((()))) = -(() Q+ - - -
(1-a)00---1 + M .E0 Q. ((-1))))) (2-1
= (2))) - - .1) - (x(
+(1-a0(5 + Q (5- -1) + MiE'
()) - Q, () + (1 (s))))(s S (1
+ +1-aa) .51) M( (-- QQ--
Using the shorthand notation
x= v S (((t)) 0.( 0+) (
M = M(²') - M EE:)
it follows that
| (1 115 11. +IM((+ (. (1 (M(((tt .Et) + Q.-((=-) .5pIi
+ +(11- (3- (MM(( +0. - (1 (M (Ex) Q+ ((211. (gD) (F.19)
26

---

Published as a conference paper at ICLR 2023
In the scalar product, the left term is known when et is known. Moreover, since B[- Fıl B[B[-)
Till T'. owing to T C T we have
B Mic Ex) Q. EE (1 (1-aa) (1-agMM(=** (M Qz (1-a)(Me++t)++00000
Fr. =B[M -1) (1 .Ea) F$ 0.
where we use Assumption I[(ūi) through Lemma F.4(i).
Since the second moment is larger than the variance we have
BlIME 6.) + (E. - M(=-
-Ex) .E.)
(2- Fi| -
E| BIMEE'' -x) - M(e-' .Et) + (.", i. &illf Fi
(F:20)
Using the Young inequality follows from (F.19), (F:20) that
B|| Fil s (1 11) Iff
..) + Q+ Kpllf Fi
+ 2(1 or.) B 4 (z -M( 0,-1 .ED0 Fil
s (1 - 113
20 BII M(2 + Q2) Q. & Fill
+ [ - a3 ) MIM 5.) M(2 2.(t x Q..((=-1,EE)1 F
(F221)
To bound the second last term of (F.21) we use unbiasedness due to Assumption Ii(ii) through Lemma F.4(i) and that Bl- | Fi| B[B|- [ Fz). owing to Fx C Fx
B[Il((2)) MiL ( + (+) . Fil
B(IM(E)) DOI Fil B(BLIQ, - (E FA
S O
(F.22)
with θ- = (1- (1-0)++20 20 where the last inequality follows from Assumptions II and IV( through Lemma F.4(ii).
To bound the last term of (F21) we use the particular choice of Qu.
M (.)) M 5 (2 5 - (2-1 1
V.g(t V. .Es (11 -T 7, (V, y st..)) -V,((t, .t))
(F.23)
So Assumption IV(v) applies after application of Young's inequality and the tower rule, leading to the following bound
BBIM(E Ex) - M(e .x) + - -E0II Fil
Q.-
= &( EE) V.p(=-) &EIFF |Fel
B[I[ - (V v,gle* .Ex) VV, - Fr
$ EIIVV,((E.. & - V.P(C 1- .EOIP, FFdl
2(1 BII Alc (x) v &Wll F
+ 20 BIII G(F" ,gg) V,G(T' , Hills I 1F Fi
Assumption (V(r) s 12 - 1 + 2(1 0)² 13l1 - 1B
11
+ +
115 -y 11 20 L -411
"3
94
$ 0 - - E01 - - 11.
(F.24)
where 21 := -IITD + 2(1 - 2 Dzll + 20 21T and E₂ = 20 1
Using (F.24) and (F:22) in (F.21) yields.
B| Fi s (1 - ag 1|35 - 112 + 207 + 2(1 - - 11 + 2 - (1. )
(F.25)
To majorize - I1: in (F:25) let . be the primal components of st in what follows. Recall that A decomposes as specified in Section 8, such that we write si 1r'1* +A())) By monotonicity
27

---

Published as a conference paper at ICLR 2023
of A we have through Lemma F.3 that
11 x2-1111 || S 1155 5
(F.26)
We can go on as
1s
x II, , - v.ò(et Ex) + arx (1 - _ .2))))))))))))))))))))))) 1
$ -ux)ll - (1 02)) (z)a Vid( - V.
+ x v, sf
(Assumption IV(r)) S (1 a1-ax) x + +(1 an) - 10R
+ + x - V. Ex) Ir
(1 - a+)la - x |,, (1 a;) I
+ azllss I + a2 az)]l[ - 1-1 - V, .E. - -
where the last equality uses ||a bil= = ||a||2 + ||b|| 2(a b) and unbiasedness from Assumption II(ii) to conclude that the inner product is zero
Hence, by subtracting lx
ب|,, and diving by 0kk we get
B + 1F Fa
2(1 d x Rp-
20 x-1
v,0(E 1 - " I Fil
Assumptions (iii)) and (V(iv)= = 2(1
( - + -
55 +
Fi + 20203
< 2(1 + & -
(- / || FF + 20
where è3 == Dell and the last inequality reintroduces the y-components.
We finally obtain
BlIl* - 1 Fi s 2(1 + + - 1 22 - S S. -1 F2l + 20
(F.27)
Introducing (F.27) into (F:25) yields
B[||s* S (c 2b Fil (1 a1 + 482a -1 -
2(1 ( + 202(1 +,)))ll - 20 + (1 - az 20
(F228
We continue with the inner term in (F.18) under conditional expectation.
-BI(s - -.,tt -
= --s - -E)
- - - - (f
- -))
- - - -2) - 22-
- (Z))
S where the last equality uses that S - =1,())))))( -1,((+)-111()))
By definition of in (8.4b), we have s H² Qu( E r' + A(2 so that 5 - (x*)
F(E + A(E*). Hence, using the weak MVI from Assumption I(iii).
(5' - (2)) # - z²) 2 plls 5 (E
(F.29)
Using also cocoercivity of H, from Lemma F.2(i), this leads the following inequality, true for any 6 > 0:
-EI(s* - - 1Td I|ss - -
2 1 - =1
- [1H+ - H. If - plls* - S (
To majorize the term I|E - ~ we may use Lemma F.2(ü) for which we need to determind L--- For the particular choice of Q.. we have through Assumption IV(ii) that
[IM(2') M(>Iff ly zif-
(F.30)
28

---

Published as a conference paper at ICLR 2023
with 3n max maxx + II,, + L,,,D,, By the stepsize choice As-
sumption IVíiti, Lu < 1, which will be important promptly.
From Lemma F.2(i)) it then follows that
([H+(E) DI 2 (1 - L - =
Hence, given LM 1,
-B[(s* - 3x,t - - rr Fi.
s ? - S (e( 2z5 Ii
Sz
/ | S o (e : MF
|z - (())
plis
- - S (F31)
The conditional expectation of the third term in (F.18) is bounded by
Bl Sal? Fil aglls S (z) || -( &w) Fil
S afils S e ( || a
(F.32)
where we have used Assumption IV(iv).
Combined with the update rule, (F.32) can also be used to bound the conditional expectation of the difference of iterates
B||k+ _ F = B[aills* - 3xlf Fel s aflls S (t + añ
(F.33)
Using (F.18), (F31), (F.32), (F.33) and that -plis - - ( I 1 - -llsst l 2 with y denoting the smallest eigenvalue of I we have,
B[U
Fil s I|e z" 2 (As-1 + a18))lss* 2 (e:: : 2 |} az - IIS (t): (z
+ +aylx=
3r a 2 |If a1 + B
$ I1ee z" I (At-1 axlex + [1 কा-ل )> * S ( = M
+ arlaas 3 ax T -
|| / )
H1 (2
+ a1211 B
(F.34)
where the last inequality follows from Young's inequality with positive as long as 1
4(1-11)) 2 0.
By defining
x Ax+1 + ar2(E2 {1( -(--2a))) ))
(F:35)
x 2 ar aB + T+ exll-Lut
and applying (F.28), we finally obtain
Bltk.1 FFF Uh s -xxll - S (2)
-1 -
4l20a) A+)1s - +f
(F.36)
+ +1x)
20 + (3)) BA]l - -2 -
+ + 22 + a2 B
If A X a1) + 422a,), then it suffice to pick B
(1 - (c) + 22,(1 03)) = 242+23,(1++)M s 2()) + 28,(1 + (3)))A =: Br.
(F.37)
1+46aa;
To get a recursion, we then only require the following conditions
x| (1 + (1
42zaa) s A and
X > 0.
(F.38)
Set A A, & For the first inequality of (F.38), since (1 )² (1 -rg), the terms involving A are bounded as
a1 + 482a/)A
$ (1 - (1 4220 A
= = + (1 - as (482a7))
S -0 48
(F.39)
29

---

Published as a conference paper at ICLR 2023
where the last inequality follows from (1 -ax) S 1 and dg S cy. Thus satisfy the first inequality of (F.38) suffice to pick
(1 + 4820g) + } a1-Las)
2
(F.40)
1 --2000
where 1 - 48200 0 is required.
The second equality of (F.38) is satisfied owing to (F.13).
The noise term in (F.36) be made independent of k by using dg a0-
21 + (1 ax)) 20²) 1 Bx+1
2(A + ag + {[ حلاー () + (1 - ax) 26))
2 20,(1 + 23))A
2(A + an(s + {(1 a(-1a)) +) 22g) 2(6 + 20₂(1 + +c))A =: C.
(F.41)
Thus, it follows from (F.36) that
B[U
Fill 11--4, Us
S ag av Y/² + 20u(d; + 202(1 + +2)))A T - - ( Dlf
(F.42
+ co
The result obtained by total expectation and summing the above inequality while noting that the initial iterate were set z- z".
Proof of Theorem 8.2. The theorem is a specialization of Theorem F.5 for a particular a choice of b and The third requirement of (F.13) can be rewritten as,
& 2 (1-L))²*
(F.43)
which is satisfied by 8= (1n() We substitute in the choice of b = voo and denotes 1) A.
The weighted sum in (F.14) is equivalent to an expectation sampled iterate in the style of Ghadimi & Lan (2013),
- S. (2
B 1 (
with k, chosen from (0, I..... K} according to probability Plk. k]
Noticing that Light - S (Z th. Fz + + = T2 so
B|| a - S. (2' + m min B|] 2 El min || =: Bidist (0, (0
(e'
#
w
where the second inequality follows from concavity of the minimum. This completes the proof.
E.4 EXPLANATION OF BIAS-CORRECTION TERM
Consider the naive analysis which would track 4², By the definition of 전 in (8.4b) and Hę(2") we would have A - Hz(3²) + Px PA(E" & E F(E + A(z)). Hence, assuming zero mean and using the weak MVI from Assumption I(ii),
B - Hx(Z). z²) 19 BI(H - H2(2)) - x2) -
(F.44)
Blplih H&(Zz) P.(E)) P.C & IF].
To proceed we could apply Young's inequality. but this would produce noise term, which would propagate to the descent inequality in (F.36) with as factor in front. To show convergence we would instead need a smaller factor of oz.
To avoid this error term entirely we instead do a change of variables with st = 1² P .0 such that,
#t E P. + A e # P (E) AE
(F.45)
3 s E AZ
30

---

Published as a conference paper at ICLR 2023
This make application of Assumption I(iii) unproblematie, but affects the choice of the bias- correction term, since the analysis will now apply to s'. we instead of the careful choice of / in (8.4a) had made the choice
If = P.(t F(e + (1 ag)(t - P 5w F(E
(F.46)
then
s = (2) -(t (x)) - P. 50 -W - P .50
- +t)) F .5x) P -5-1))
Notice how the latter term is evaluated under 5-1 instead of 5. The choice in (8.4a) resolves this issue.
G NEGATIVE WEAK MINTY VARIATIONAL INEQUALITY
In this section we consider the problem of finding a zero of the single-valued operator F (with the set-valued operator A = 0). Observe that the weak MVI in Assumption I(iii), 2 --> 2 pllF? for all 2 E R", not symmetric and one may instead consider that the assumption holds for -F. As will see below this simple observation leads to nontrivial problem classes extending the reach of extragradient-Iype methods both in the deterministic and stochastic settings.
Assumption VIII (negative weak MVT). There exists a nonempty set S S zer T such that for all z* E S* and some p E (-c0, 1/2L)
( S Fall for all z R".
(G.1)
Under this assumption the algorithm of Pethick et al. (2022) leads to the following modified iterates:
オ = 2 F + = (ay = = where idi++
(G.2)
=
(G.3)
We next consider the lower bound example of (Pethick et al., 2022, Ex. 5) to show that despite the condition for weak MVI being violated for smaller than a certain threshold, the negative weak MVI in Assumption VIII holds for any negative b and thus the extragradient method applied to -F guaranteed to converge.
Example 1. Consider (Pethick et al., 2022, Ex. 5)
minimize maximize f(x,y) == axy + +22 =x² -2), yER
(G.4)
XER
where b < 0 and 0. The associated is linear mapping. For a linear mapping M, Assump- tion VIII holds if
J(M M PM M s 0.
(- 1/21)
While Assumption I(iū)) holds if
(M + M pM M
pe (-1/2...))).
For this example L= Va² + 12 and
=M:
F(z) (bx + ay, -ax by).
Since M a bisymmetric linear mapping, M = (a² bP)1 which according to the above charac-
terizations implies
P 2L 76
a 27
The range for p is nonempty if while this is not an issue for f which allows any negative b.
We complete this section with a corollary Theorem 6.3 when replacing weak MVI assumption with Assumption VIII.
Corollary G.1. Suppose that Assumptions I(i) and I(ii), Assumptions II, III and VIII hold. Let (z' ) denote the sequence generated by Algorithm applied to -F. Then, the claims of Theorem 6.3 hold Irue.
31

---

Published as a conference paper at ICLR 2023
10-1
10-2
10
PGSEG+ (1 = 0.5)
PjSEG+ (1 = 0.1)
10-1
P 0.C1)
BC-PSEG+ (r 0.5)
10a
10a
10
10
10a
Traention &
Figure 3: The (projected) (SEG+) method needs take arbitrarity small guarantee convergence to an arbitvarily small neighborhood. We show instance satisfying the weak MVI where y cannot be taken arbitvarily small. objective ((x,y) = 6(x from Example where L. = and p = -1/10r The unique stationary point (x*.y") (0.9.0.9) lies in the interior, so even [[F can be driven zero. Taking y smaller does not make the neighborhood smaller as oppose the monotone in Figure
0.9) under box constraints II(x, y)lo $ with &
H EXPERIMENTS
H.1 SYNTHETIC EXAMPLE
Example 2 (Unconstrained quadratic game (Pethick et al., 2022, Ex. 5)). Consider,
b b minimize 6ax axy 2x² 2 yel
(H.I)
where a R4 and b e R.
The problem constants in Example 2 can easily be computed as pspp o+ and L. Va² + b2. We can rewrite Example terms of L and p by choosing VL² Ltp² and b Lip.
Example 3 (Constrained minimax (Pethick et al., 2022, Ex. 4)). Consider
minimize maximize ((x,)) xy + (xxx ((y),
(GlobalForsaken)
biss
where (1z))
21
In both Example and Example the operator F is defined as Fz= (V,6(,.))).
To simulate stochastic setting in all examples, we consider additive Gaussian noise, i.e. f(z.g) F where & ~ NO0, o²1). choose or 0.1 and initialize with 2" The default configuration is 1/21, with aa = 1/18.k/e+1), stepsize schemes and a = 1/18 for fixed stepsize schemes. We make two exceptions: Figure 1 uses the slower decay 1000 when y 0.1 and Figure 3 uses 5000 for y 0.01 (and otherwise
not specified otherwise. 100 and Br as for diminishing
c = 1000) to ensure fast enough convergence. When the aggressive stepsize schedule is used then Cr 1/18 v...o.TT.
32

---

Published as a conference paper at ICLR 2023
007
10710
10-10
Pormation
174
11
10-1
10-11
10
SF-80-
10"1
SF-PEG+
17-17
S80
PSDO
B0 9B01
DC PAEG
Figure 4: Instead of taking Oe 1/2 (for which almost convergence is established through The- orem 6.3 and ??) we take as 1/ S as permitted Theorems 6.1 and 7.1. We consider the example provided Figure (top row) and the two examples from Figure (bottom row). Under this more aggres- sive stepsize schedule the guarantee is only in expectation over the iterates which is also apparent from the relutively large volatility in comparison with Figures and 2.
H.2 ADDITIONAL ALGORITHMIC DETAILS
For the constrained setting in Figure I, we consider two extensions of (SEG+), One variant uses single application the resolvent as suggested by Pethick al. (2022),
전 (id + -y)
with & P
(P₁SEG+)
A+l -
f(t -
EE:)) with &
The other variant applies the resolvent twice as in stochastic Mirror-Prox (Juditsky et al., 2011),
전 (id + yA) yf(2' with &s P ++ (id + a.y - (() with & When applying (SEG) to constrained settings we similarly use the following projected variants:
(PSSGG+)
(id (.d)) Boyffey ()) with & ~
(PSEG)
A+1 (id + aayd) (c- (uy Ec) with & ~ p
and (EG+) (using stochastic feedback denoted SF)
전 (id y (E with & p
(SF-PEG+)
++ (id ayy) ( - azf( &0) with & p which we in the unconstrained case = 0) refer as (SF-EG+) as defined below.
전 yf(Et Ex) with & ~
(SF-EG+)
++| = - ayy(t' Eo with à Pp
33

---

Published as a conference paper at ICLR 2023
I COMPARISON WITH VARIANCE REDUCTION
Consider the case where the expectation comes in the form a finite sum,
N
Fz
F(z,E).
(1.1)
In the worst case the averaged Lipschitz constant Fr scales proportionally the number of elements squared, i.c. Lp = Q v) is casy to construct such an example by taking one elements to have Lipschitz constant NL while letting the remaining elements have Lipschitz constant L. Re- calling the definition in Assumption III, 1 Nº N=1 NL² while the average becomes LF + L 2L Lp Wa/21,. Thus, Lp can be VN times larger than Lr, leading po- tentially strict requirement on the weak MVI parameter p > 4L/2 for variance reduction methods.
34


Reviews:
[{"review_id": "YPX7XkEBajP", "reviewer": "Reviewer_sw4D", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "For the first time, the authors introduces a family of stochastic extragradient-type algorithms that positively solves a class of nonconvex-nonconcave problems which can be cast as stochastic weak Minty variational inequality (MVI). In the monotone setting, extragradient methods adopt constant stepsizes and bounded batchsizes (both of which are critical in practical performances), and when extending to the weak MVI setting, only theories adopting expensive increasing batch sizes per iteration approaches are available.", "summary_of_the_review": "This paper is theoretically strong in the sense that it made an important step in fixing SEG with constant extrapolation stepsize and diminishing updating stepsize. This makes an important step upon existing work (e.g. Hsieh et al., 2020; Diakonikolas et al., 2021; Pethick et al., 2022) even for the monotone case. This supports my high rating of this work. It would be even better if the authors have a chance to include richer empirical findings relative to this work. ", "strength_and_weaknesses": "Strength\n\nThis work answers affirmatively an open problem by proposing a *bias-corrected* stochastic extragradient (BCSEG+) algorithm that solves stochastic weak Minty variational inequalities without increasing the batch size. As the authors indicated, Pethick et al. (2022) \"suﬃces in the special case of unconstrained quadratic games but can fail even in the monotone case ...\". Also, earlier works such as Hsieh et al. (2020) adopt diminishing but larger exploration stepsize and smaller updating stepsize.\n\n\nWeakness\n\nThere is not much from my perspective, as long as the proof is correct (which I took a high-leve look at but did not go into all details). Two small comments:\n\n--MVI can be short for \"monotone\" variational inequality instead of \"Minty\" variational inequality. Adopting this shorthand as in some earlier work might cause unnecessary confusion. Therefore, I would suggest the authors avoid this shorthand as much as possible.\n\n--The authors should do more literature reviews. Missing reference includes but not limited to \"Bot et al., Minibatch Forward-Backward-Forward Methods for Solving Stochastic Variational Inequalities, 2021\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8EX0XGqf5D4", "reviewer": "Reviewer_6PPj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper addresses an important open question of deriving rates in terms of the expected squared norm of the operator for stochastic weak MVIs without large batchsizes. The result is novel even in the special case of monotone operators. The authors also propose the generalization to the constrained case and propose and analyze the variants with a nonlinear asymmetric preconditioner. The key algorithmic novelty is a modification of Stochastic Extragradient Method that uses bias correction term.", "summary_of_the_review": "The main results are very good and outweigh multiple weaknesses that the paper has. I strongly encourage the authors to address the issues I mentioned. It will improve the paper a lot. If the authors address my concerns, I will increase my score.\n\n\n========UPDATE==========\n\nI thank the authors for the detailed response to my comments and for improving the paper. The problematic parts became much easier to follow (including Section 8) and almost all of my questions/concerns are resolved. In general, I am satisfied with the changes. Therefore, I am increasing my score from 6 to 8: as I explained in the original review, the paper fully deserves this.", "strength_and_weaknesses": "## Strengths\n1. **Strong theoretical results.** The open question that authors resolved (analysis in terms of the expected squared norm of the operator without large batchsizes) is highly non-trivial. In particular, even in the monotone case, all previous works that have convergence results in terms of the expected squared norm of the operator do rely on the usage of large $\\mathcal{O}(1/\\varepsilon)$ batchsizes (or even worse) to achieve $\\min_{k = 0,\\ldots,K}\\mathbb{E}||F(z^k)||^2 \\leq \\varepsilon$. In contrast, the analysis of the method proposed in this work achieves the same complexity result *with $\\mathcal{O}(1)$* batchsize. Moreover, it is done for weak MVIs with Lipschitz operator, which is a more general setup than monotone Lipschitz case. Even this result makes the paper strong enough to be accepted to the conference. However, the authors do not stop here and generalize their results (and algorithm) to the constrained case and show some interesting (though very hard to read) extensions.\n\n## Weaknesses\n1. **Clarity.** Some parts of the paper are very hard to understand. In particular, it is hard to follow some parts of the proofs (see my detailed comments below). Next, the paper does not provide the intuition behind the algorithm development: why does the bias-correction term was chosen this way? Moreover, Section 8 and Appendix E are very hard to follow due to the lack of the intuition and details. The authors introduce too many notations there, I cannot thoroughly check this part during the time given for reviewing. Therefore, I encourage the authors either to remove Section 8 from the paper or substantially improve the clarity there (why we consider such preconditioners, why we change the algorithms this way, what is the intuition behind the proof).\n\n2. **Strong assumptions.** The key trick allowing the authors to get rid of the large batchsizes is that the authors assume bounded variance and Lipschitzness in mean at the same time (see derivation of formula (C.4)). Usually, these assumptions are not used simultaneously: either bounded variance is assumed without any assumptions like Assumption III or Assumption III is used without bounded variance assumption (instead one needs to assume just boundedness of the variance at the optimum). I think, this should be highlighted more in the paper and listed as a limitation of the derived results.\n\n3. **Numerical experiments.** Based on what is written in the paper, the authors used similar stepsizes for all tested methods. However, this is not a fair comparison: one should tune stepsizes for each method separately. Next, the proposed method was not tested on real problems (minor). It would be interesting to see how BCSEG+ behaves in training GANs, for example. \n\n\n## Main concerns/comments/questions (this is very important to address)\n\n1. The authors write \"When monotone-like conditions holds the story is different since it suffices\nto take diminishing stepsizes.\" I believe, this is not accurate. All mentioned results in the monotone case either provide guarantees in terms of the gap function (and thus do not need large batchsizes) like Juditsky et al. (2011) and Mishchenko et al. (2020) or in terms of  the squared norm of the operator but with large batchiszes like in Gorbunov et al. (2022). Other works consider setups where one can achieve linear rates in deterministic case (and thus these cases are easier). Therefore, the question that the authors resolved was in fact open even in the monotone case.\n\n2. Could the authors explain why the metric chosen in the constrained case is good? How does it relate to the standard squared residual metric like $||z^k - z^{k-1}||^2$?\n\n3. Figure 1 does not imply that SEG+ does not converge in general: it implies only that it does not converge for given stepsize policy.\n\n4. Figure 2: why EG+ does not converge to any predefined accuracy? Since EG+ is a deterministic method, it should converge with fixed stepsizes.\n\n**Below I list the issues with the proofs to justify my claim about the clarity.**\n\n5. In (B.7), the derivation is not accurate: one should have extra $-||v||^2$ in the second step.\n\n6. In (C.1), $b$ is not defined.\n\n7. Why the potential function $\\mathcal{U}_{k+1}$ is chosen this way? How was it found?\n\n8. The formula above (C.4), after the word \"Therefore\": in the first term of the inner product, one should have $F(z^{k-1})$ instead of $\\hat F(z^{k-1})$.\n\n9. Formula (C.6), third row from below\" one should have $+ \\frac{\\gamma^2 \\varepsilon_k}{2}||F(\\bar{z}^k)||^2$ instead of $- \\frac{\\gamma^2 \\varepsilon_k}{2}||F(\\bar{z}^k)||^2$.\n\n10. The end of the proof of Theorem C.2 is very hard to follow (after (C.11)). I have checked it, everything is correct. However, it required me to derive few things myself. The authors should provide all missing derivations with the detailed comments on each step.\n\n11. In (C.16), one should have extra factor $2$ in front of the second $\\gamma L_{\\hat{F}}$ (it goes from (C.27), where in the second row one should have $\\frac{2}{k+1+r}$ in the second multiplicative factor).\n\n12. (C.22) should go before (C.21).\n\n13. The part after (C.23) is very hard to check: the authors should refer to particular inequalities that they use in each step and also explain each step in details.\n\n14. Page 18: \"Plugging the value of $c_\\ell$ and $\\varepsilon_k$ from (C.21)\" --> \"Plugging the value of $c_\\ell$ and $\\varepsilon_k$ from Assumption VI and (C.20)\" \n\n15. The first inequality on page 20: the authors use $||a+b||^2 \\geq ||a||^2 - ||b||^2$, which is not correct. The correct version: $||a+b||^2 \\geq \\frac{1}{2}||a||^2 - ||b||^2$. However, in this case, one should assume that $\\gamma \\leq \\frac{1}{\\sqrt{2}L}$ that reduces the maximal range for $\\rho$. To avoid this one should estimate $||Hz - Hz'||$ instead of $||Hz - Hz'||^2$. In this case, one can use the triangle inequality instead of Young. As the result, the authors will get $(1 - \\gamma L_F)^2$ factor instead of $1 - \\gamma^2 L_F^2$.\n\n16. I do not understand the derivation of (D.13). In particular, I do not see what left-hand side of (D.14) corresponds to. The authors should provide complete derivation with all the details.\n\n17. How (D.15) was obtained? The authors should provide complete derivation with all the details.\n\n## Minor comments\n\n1. Assumption II(ii): the second term inside the norm should be $F(z)$.\n\n2. \"However, Pethick et al. (2022) also showed that the extrapolation stepsize plays a critical role for convergence under weak MVI.\" Could the authors provide a reference to the particular result from Pethick et al. (2022)?\n\n3. Page 13, above (B.3): \"The two latter term are\" --> \"The two latter terms are\"\n\n4. Page 15, the first sentence: \"By step 1.2\" --> \"By step 1.4\"\n\n5. Sometimes the authors use $F(\\bar{z}^k)$, sometimes they use $F\\bar{z}^k$. The notation should be verified.\n\n6. The end of page 16: \"... is sufficient to satisfy (C.13)\" -- > \"... is sufficient to satisfy (C.13) and (C.14)\"\n\n7. Page 20, \"The third term in (D.2) is bounded by\": it is not the third term but its conditional expectation. One should fix it here and everywhere else.\n\n8. In (D.9), $H_k(\\bar{z}^k)$ is not defined. Is it $H(\\bar{z}^k)$?\n\n9. Above (D.18): one should have $\\Gamma = I$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6pcSeK61NI", "reviewer": "Reviewer_o1sj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides a stochastic algorithm for a class of problem characterized by weak minty variational inequality. The algorithm modifies stochastic extra-gradient by adding a bias-correction term in the exploration step. ", "summary_of_the_review": "I find the algorithm interesting, but a few questions remain. ", "strength_and_weaknesses": "Strength:\n\n(1) The design of the algorithm is interesting, as it only uses diminishing stepsize for in one step of EG update and introduces a novel correction term. \n\nI have the following questions:\n\n(1) The paper mentions the lwoer bound $\\rho > \\gamma/2$ from [Pethick et al., 2022] several times and it serves an intuition for the algorithm in page 4. However, based on my understanding, from the example given in  [Pethick et al., 2022], the stepsize $\\gamma$ is fixed to be $1/L$. I am not sure whether that still holds for  other stepsize or time-changing stepsize.\n\n(2) In Theorem 7, the convergence measurement $|| H\\bar{z}^{k\\star} - Hz^{k\\star}||$ seems to only consider the operator F and ignore A by the definition of $H$. Why is it a good measurement here? Also in Algorithm 2, it returns $z^{k+1}$, but I do not know how it will guarantee that it will satisfy the constraint if operator A corresponds to a constraint. \n\n(3) The experiment in Figure 1 is not representative. It is a bilinear game, so it can be easily solved by stochastic EG. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "03d7VYCwUZf", "reviewer": "Reviewer_eJWH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper, proposes new variants of stochastic extra-gradient methods for solving inclusion problems that satisfy the minty variational inequality (MVI). The proposed algorithms BCSEG+ (Alg. 1 and Alg. 2) and NP-PDGG (Alg. 3) have been designed and analyzed for solving the inclusion problem under the unconstrained smooth case, constrained case, and min-max problem (8.5) respectively. The most important contribution of this work is that by using the new algorithms it is possible to provide analysis without requiring increasing batch sizes as the algorithm progress. ", "summary_of_the_review": "I give \"6: marginally above the acceptance threshold\" for this work. \nThe theoretical results are novel however there are several points of weakness (in terms of clarity) of the paper and limitations in terms of experiments. ", "strength_and_weaknesses": "The paper is well-written and the idea is easy to follow. The authors did a great job on the separation of sections and on the presentation of the results. In particular, I find that it is very helpful for the reader that the authors included separate sections for the unconstrained and constrained setting. \n\nHowever, I believe the paper has some issues in terms of notation and numerical evaluation. In addition, the paper missing some relevant recent works on other classes of structured non-monotone problems.\n\nLet me provide some details below:\n\nOn presentation: \n1. There is no part in the paper where the sets $zer T$, and $gph T$ are defined. Even if the definition is trivial is currently missing. In addition, what do we call a maximally monotone operator (assumption on operator A in the main problem)? this detail is required for a self-contained paper. \n\n2. Inequality 3.2 used $\\Gamma$ and $\\Gamma^{-1}$ without a proper explanation of why the  $ \\Gamma^{-1}$ is needed. The standard $L_f$-Lipschitz used identity matrices, so further details are needed. The same holds for Assumption III.\n\n3. The paper mentions in several parts that: ``employing diminishing stepsizes is no longer possible in the weak MVI setting.\" but they do not properly explain why. Why is this true? is there an existing paper that proves that or is it a speculation of the authors? more details are needed.\n\n4. Minor: The deterministic operator is defined as $Fz$ while the stochastic estimator is denoted with $F(z,\\xi)$. It might have been better if one used F(z) as well for the deterministic variant. \n\n5. After the definition of SEG, the paper mentions: ``Even with a two-timescale variant (when $\\beta_k > \\alpha_k$) it has only been possible to show convergence for MVI (Hsieh et al., 2020).\"  what this means exactly? note that (Hsieh et al., 2020) has nothing to do with MVI. \n\nOn proofs:\n1. What is b in equation C.1 in the appendix?\n2. I find that the steps in the proofs require further explanation for the reader to be able to follow easily (probably by splitting steps into several parts). The parts where Young's inequality is used are not always very clear. \n3. In C.8 the previous bound is used by now it has expectation conditional on $f_k$ even if the quantity is deterministic. This is not wrong but it is not standard.\n\nOn experiments: (This is probably an important issue of the current version of the paper) \n\nThe authors mentioned the following: \"Except for BCSEG+, all methods fail to converge in these examples.\" and \"In comparison (EG+) gets closer to a solution in both problems but fails to converge due to the non-diminishing stepsize, while BCSEG+ converges for both example.\" \nIn my viewpoint figure, 2 does not show any benefit of BCSEG+, compared to EG+. both methods converge to a very similar neighborhood $(10^{-2})$ of the solution. Probably the methods should be run for more iterations to obtain something useful. \nAlso, I suspect that the method here is SEG+ and not EG+, right? \n\nMissing references on other structured non-monotone problems: \n\n[1] Yang, J., Kiyavash, N., and He, N. (2020). Global convergence and variance reduction for a class of nonconvexnonconcave minimax problems. NeurIPS\n\n[2] Song, C., Zhou, Z., Zhou, Y., Jiang, Y., and Ma, Y.\n(2020). Optimistic dual extrapolation for coherent nonmonotone variational inequalities. NeurIPS\n\n[3] Loizou, N., Berard, H., Gidel, G., Mitliagkas, I., and\nLacoste-Julien, S. (2021). Stochastic gradient descentascent and consensus optimization for smooth games:\nConvergence analysis under expected co-coercivity.NeurIPS\n\n[4] Loizou, N., Berard, H., Jolicoeur-Martineau, A., Vincent,\nP., Lacoste-Julien, S., and Mitliagkas, I. (2020). Stochastic hamiltonian gradient methods for smooth games. ICML\n\n[5] Kannan, A. and Shanbhag, U. V. (2019). Optimal\nstochastic extragradient schemes for pseudomonotone\nstochastic variational inequality problems and their variants. Computational Optimization and Applications,\n74(3):779–820.\n\n[6] Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas\nLoizou. Stochastic gradient descent-ascent: Unified theory and new\nefficient methods. arXiv preprint arXiv:2202.07262, 2022\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster