Generalized Smooth Stochastic Variational Inequalities:  Almost Sure Convergence and Convergence Rates
Authors: Daniil Vankov
Angelia Nedich
Lalitha Sankar
Venue: Accepted by TMLR ()

Abstract: This paper focuses on solving a stochastic variational inequality (SVI) problem under relaxed smoothness assumption for a class of structured non-monotone operators. The SVI problem has attracted significant interest in the machine learning community due to its immediate application to adversarial training and multi-agent reinforcement learning. In many such applications, the resulting operators do not satisfy the smoothness assumption. To address this issue, we focus on a weaker generalized smoothness assumption called $\alpha$-symmetric. Under $p$-quasi sharpness and $\alpha$-symmetric assumptions on the operator, we study clipped projection (gradient descent-ascent) and clipped Korpelevich (extragradient) methods. For these clipped methods, we provide the first almost-sure convergence results without making any assumptions on the boundedness of either the stochastic operator or the stochastic samples.  We also provide the first in-expectation unbiased convergence rate results for these methods under a relaxed smoothness assumption for $\alpha \leq \frac{1}{2}$.

Lalitha Sankar Published in Transactions on Machine Learning Research (09/2025)
Generalized Smooth Stochastic Variational Inequalities: Al- most Sure Convergence and Convergence Rates
Daniil Vankov Arizona State University
dvankov@asu.edu edu
Angelia Nedié Arizona State Universiby
ongeeia.nedichh@aase
Ssankar@aser edu
Arizona State University
Reviewed on OpenReview: https: // optpreveew.....w...mmmoe net/ forum? EjqSpbUBUU
Abstract
This paper focuses on solving stochastic variational inequality (SVI) problem under relaxed smoothness assumption for a class structured non-monotone operators. The SVI problem has attracted significant interest in the machine learning community due its immediate application to adversarial training and multi-agent reinforcement learning. In many such applications, the resulting operators do not satisfy the smoothness assumption. To address this issue, we focus on a weaker generalized smoothness assumption called a-symmetric. Under p-quasi sharpness and a-symmetric assumptions on the operator, we study clipped projection (gradient descent-ascent)) and clipped Korpelevich (extragradient) methods. For these clipped methods, we provide the first almost-sure convergence results without making any assumptions on the boundedness of either the stochastic operator the stochastic samples. We also provide the first in-expectation unbiased convergence rate results for these methods under relaxed smoothness assumption for < 1.2
Introduction
This paper focuses on the stochastic variational inequality (SVT) problem, which consists of finding a point u' e U, such that
(F(u"), 20 20 for all e U,
where the operator F(-) is specified as the expected value of a stochastic operator :(:-): x E Rmm, i.e.,
F(u) = E((uu{) for all U,
where E 3\t random vector. Variational Inequality (VI) problems encompass many practical applications, such optimization, min-max problems, and multi-agent games. In particular, they play vital role in modeling equilibrium problems where it's important to capture machine learning literature, the increasing focus on VIs is due to their relevance to generative adversarial networks (GANs) Gemp & Mahadevan (2018); Gidel et al. (2019), actor-crilic methods Pfau & Vinyals (2016), adversarial training, and multi-agent reinforcement learning Sokota et al. (2022): y Kotsalis et al. (2022). ) many such applications, the corresponding operator defined as an expected value of stochastic or finite sum of operators, which motivates us to study SVIs. One of the pivotal works Nemirovski (2004): Juditsky al. (2011) SVTs proposed and studied the celebrated Mirror-Prox method under assumptions monotonicity
interaction between many agents. In

---

Published in Transactions on Machine Learning Research (09/2025)
and Lipschitz continuity of operator [ These assumptions become classical for the analysis of first-order
methods for solving SVTs Beznosikov et al. 2022 Hsieh et al. (211 2020 Loizou et al. (2021).
In adversarial and multi-agent training, where the corresponding operator is a gradient of a highly non- linear neural network model, these classical assumptions might not be satisfied. It is well-known that one possible remedy for such non-convergent behavior is in clipping, normalization, or adaptive stepsizes, such as ADAM (Kingma & Ba 2015). This effect might be explained by the experiment conducted in Zhang et al. (2020). In this work, authors observed that when training deep neural network, the norm of the hessian of the loss function correlates with norm of gradient along the optimization trajectory.
This observation motivated Zhang et al. (2020) to introduce a new and more realistic assumption on the linear growth of the hessian. This led to a great number of works in optimization invesl igating new assumptions on
generalized smoothness and convergence behavior classical gradient (Li et al. 2023) normalized (Chen
ct al. )023), clipped (Koloskova et al. 2023), and adaptive methods (Wang et al. 2023: Zhang et al. 2024h.
Despite this progress in optimization, there are only few works on generalized smooth min-max 4Xian et al., 2024) and VI |Vankov et al., 2024) problems. This motivates us to delve into investigation of the first-order methods for generalized smooth SVIs.
1.1 Related work
Weaker Assumption on SVIs. More work has focused on stochastic methods for SVT under more relaxed assumptions develop and analyze the methods applicable to broader problem classes. In particular, some studies have explored SVIs under moouddomoontonicity Kannan & Shanbhag (2019), quasi- massiimonotonicity Loniooooiittyooozouuu Loizou (0 1 co-coercivity [Beznosikov et al. 2023) and quasi-sharpness Vankov et al. (022)) Diakonikolas 2021 showed that such conditions may not be satisfied even in two played Markov games and introducod the weakest known structured non-monotone assumption. Later, weak Minty SVIs were studied Pethick eet al. (002); Choudhury et al. (2023); |Alacaoglu et al. (2024) under Lipschitz continuity assumption on the operator. In our work, we consider the generalized smooth assumption that goes beyond the existing scttings.
et al.
ct al.
Normalized and Clipped Methods for SVIs. Jelassi al. (0022] studied the performance of normalized stochastic gradient descent-ascent and ADAM and suggested the crucial role of normalization for training GANs. It is worth noting that, with the right clipping parameters, clipped and normalized step sizes are equivalent up to a constant. Another line of works Gorbunov et al. (2022) focuses on smooth SVIs under heavy-tail noise. Using Lipschitz's 's continuity of operator and the right choice of clipping parameters, the authors showed a high probability convergence rate for the clipped stochastic Korpelevich method. Recent work Xian et al. (2024) considered generalizod smooth stochastic nonconvex strongly-concave min-max convergence rates for variants of stochastic gradient descent-ascent (SGDA) with normalized stepsizes. Due to the specific structure of the minmax problem and the fact that the gradient of the corresponding function nonmonotone one variable and strongly monotone another, to compare this work with ours. Moreover, in this work, the crucial part of the analysis is in the fact that the be upper bounded by function residual. One not use such bounds in SVIs due
problems and provided O( VK
difficult
norm of gradient to the absence of function values. In our analysis, we develop technique to bound the operator norm in almost sure (a.s.) sense and in expectation
Stochastic Analysis of Clipped Methods for Generalized Smooth Optimization. In Zhang et al. (2020), authors analyzed clipped gradient method under a.s. bounded error assumption. Koloskova et al. (2023) showed that the gradient method with standard clipping may not converge a solution even with small stepsizes. The authors analyzed clipped gradient descent as a biased method and provided a convergence rate for non-convex functions. Later, Li et al. (2024) developed a new technique allowing to bound stochastic gradients by the function value residual along the optimization trajectory, which helps to find the convergence rate for the gradient with the right choice of stepsizes. In our work, we do not make an assumption on a.s.
The well-studied Mirror-Prox method Nemirovski (2004) has been proven to be optimal for solving VIs under strong monotonicity and Lipschitz continuity assumptions. In fact, this method the stochastic version of the classical extragradient. method.
2

---

Published in Transactions on Machine Learning Research (09/2025)
bounded noise and bounded stochastic gradients. Furthermore, we provide not only in-expectations but also 0.8. convergence of the considered clipped methods.
Contribations. In light the cxisting literature, we consider stochastic VIs with p-quasi sharp generalized
smooth a-symmelric operators. We assume bounded variance of the noise and do not use a restrictive assumption of bounded stochastic operators or bounded samples. Our key contributions are summarized below (see also Table I
We provide the first known analysis of the clipped stochastic projection method (clipped SGDA) for solving stochastic generalized smooth VIs with p-quasi sharp and a-symmetric operators. The key feature of our analysis is the use of cleverly chosen clipped slochastic slepsizes "Mk We use two different samples of stochastic the operator, one for clipping stepsizes " and another for the direction of the method update. This choice allows us to separate the clipping part from the stochastic error and analyze the method in an unbiased manner. To show a.s. convergence, we prove that the series of clipped stochaslic stepsizes is not summable a.s., i.e. P(E 7tk 20) =1.
We also provide convergence rate for stochastic clipped projection method for S 1/2. For p 2 we achieve O(k-1) last iterate convergence. For p > 2, we show the best ilerate convergence rale of ((k22(1)))/)) where 1 >> q 1/2 is a parameter of the stepsize choice.
We provide the first known analysis of the stochastic clipped Korpelevich method for solving stochastic generalized smooth VIs with p-quasi sharp and a-symmetric operators. By reusing clipping stepsizes ")k for both iterates updates h2 and uk, we separate stochastic stepsize from the stochastic error, similar to the projection method analysis. show a.s. convergence, we prove that the series of clipped stochastic stepsizes not summable a.s., ie. P( T 20)=
Morcover, we prove in-cxpoctation convergence rates for the stochastic clipped Korpelovich mothods for 1/2. For p 2, show the last iterate sublinear convergence rate O(k-1). For p 2, we show the best iterate convergence rate of O 0(k-2(1-9)/1) where > q 1/2 is a parameter of the stepsize choice.
Finally, we present numerical experiments where we compare the performance of the methods with proposed stochastic clipping for different stepsize parameter g > 1/2 and quasi-sharpness parameter p.
Stochastic Projection
Stochastic Korpelevich
p> 6, [0,1]
Asym (Thm 3.2
Asym (Thm 4.2g
Do
Ur +o)
(Cr + o RK Do (o K1020) + to)² k2h2
p 2=2,a 21
k2
12k
122
(Do + 22)2/P((C
CCF+ 2
AAPP(Do + + + K
21022/2/00 2/02a +0)000
p> 2,a E ()
2//pk2(1-0))
Summary of convergence rate results showing the decrease of certain performance measures with the number of iterations. We use "Asym' as an abbreviation for asymptotic almost sure convergence results. For p-quasi sharp operators, with p 2, and for stochastic projection and Korpelevich methods, the performance measures are Dę Efdist" (wx, U*)] and D₁ Ejdist Aidist?(lux) (hu, U*),, respectively. For p 2, the performance measure for both methods Dx = (idist?(uxs-)) (ū,,U*)], ún = ( 3:) Σ 3ru. The constant Cp denotes the upper bound on E[] [(xx) [] and F()))(()))]] |I] for stochastic projection and Korpelevich methods, respectively.
Table 1:
The rest of the paper is organized as follows. In Section 2 we provide the assumption the operator class we consider and the first-order methods we focus on. In Scction 3 we show the almost sure convergence result of clipped stochastic ion method. In Section 4 we provide a.s. convergence results and in-expectat convergence rates for the clipped stochastic Korpelevich method. In Section 5 we conduct experiments on solving generalized smooth SVIs and compare the performance of the stochastic clipped projection and Korpelevich method for different problem and stepsize parameters. Section concludes our work and presents some further research directions.
3

---

Published in Transactions on Machine Learning Research (09/2025)
2 Preliminaries
In this section, we provide the necessary concepts and assumptions for the considered SVI problem. We start with a standard definition; the operalor F is said to be Lipschitz continuous on a set U if there exists L > 0 such that
[[F(u)) - F(+)) - 4 -ul v|l
for all u, E U.
(1)
So far, the Lipschitz continuity of the operator was the most common assumption study SVIs Nemirovski 2004) Yousefian et al. (2014 2017
Hsieh al. (2019): Loizou et al. 2021 Alacaoglu et al. (2024)
However, this assumption does not hold in modern deep-learning applications. Based the experiments neural network training provided in Zhang et al.] (2020), the norm of Jacobian of the operator correlates with the norm of the operator. Motivated by this observation, Zhang et al. (2020) proposed new, more realistic, and weaker assumption named (Lo, L-mmmhoth:: a diffcrentiable operator is (Lu, I1)-shooth operator on a
set U when the following relation holds
[V((W) Lo (()(( for all u E U.
(2)
When the operator F(-) is L-Lipschitz continuous, it satisfies 2 with Lg = L and L = O. Recent work Chen et al. (2023) generalized class of (Lo, L1 smoothh operators and introduced a new class termed a-symmetric. The class of a-symmetric operators includes the class of 41)-moottttth operators and coincides with it 1. Given that the class of a-symmetric operators includes (Lo, L1)-moothh and Lipschitz continuous operators, we focus on this class in our work.
when the operator is differentiable for
Assumption 2.1. Given convex set U R", the operator F()):U + R is a-symmetric over U, i.c., for some E (0, 1] and Lo, L1 2 O, have for all u, E U,
[F(u)) - F(v)l < Lo + Li max [I ||u vll. BE(0,1)
(3)
where wy = Ou O)c.
An alternative characterization of a-symmetric operators has been proved in Chen et al. (2023), given in the following proposition.
Proposition 2.2 (Chen al. 2023). Proposition 1). Let U C R be a nonemply conver set and let
F:U + R be operator. Then, the following statements hold:
(a) F()) is a-symmelric with a E (0,1) and constants Lo, In 2 if and only if the following relation holds for all y, y e U,
|1F(y) - F(y')ll < by - //K + (KIIF((F))))
+ K2lly lly - 3/ //())(
(4)
where Ko = (112)) /1-a) 1), K1 = 1/222/(1-a)))) and K₂ = L 1/(1-a)ai (11 111-1111110 a) a)a/(1aa))
(b) F(-) is a-symmetric with and constants Lo. L1 if and only if the following relation holds for all s EU,
[F(y) - F()I - o/ (/o L/IIP())))
v/11)-
Proposition 2.2 is useful for our analysis, since it describes an a-symmetric operator by using two points y, U, and bypasses the evaluation of maxeg(0.1) [[F(w))]| The solution set for the variational inequality problem defined by the set U and operator F, denoted U*, is given by
U (u" U (F(u"), ) u²) 0 for all u U).
Throughout this paper, we make the following assumption the set U and the solution set..
4

---

Published in Transactions on Machine Learning Research (09/2025)
Assumption 2.3. The set U _ Rm is nonempty closed convex set, and the solution set U is nonempty and closed.
In our analysis assume that operator F is p-quasi sharp Vankov et al. 2023
Assumption 2.4. The operator F' U + R has p-quasi sharpness property over U relative the solution set U*, i.e., for some p 0, j O, and for all u U and u" E U*,
(00))-u00 (F(u), - =²) 2 p dist" U*).
(6)
the optimization community, such assumptions are called error bounds and are widely studied Zhou &
So (2017). This class of operators encompasses strongly monotone, p-monotone Facchinei & Pang (2003)
Lin & Jordan 2025), strongly quasi-monotone Loizou et al. (2021] and strongly coherent [Song al. (2020)
operators and aligus with the class of operators that satisfy the saddle-point metric subregularity Wei et al.
[2021] for > 2. The are many applications where operator satisfy (6, for example robust learning Wang
et al. 2023 Zarifis et al. 2024). network congestion games Xiao & Shanbbag 2025
Assumption 2.4 is onc of the most general assumptions with the positive inner product between an operator value F(u) and u - u², which crucial our analysis.
For solving the SVI problem, we consider stochastic variants of projection and Korpelevich 19766) methods, where stochastic approximations o(uk- (x) and o(hg, E)) are used, respoctively, instead of the directions F(Ux) and F(hx). The ilerates of each of the stochastic methods are defined as follows:
Stochastic projection method:
uk+1 = Pu(u: - -7k pu:x Ex)),
(7)
Stochastic Korpelevich method:
Uk Pu(hu -7h phux, (1)),
(8)
h&41 Purlu: (uu: (2)),
where {rr} is a sequence of stochastic positive stepsizes, and up, ho E U are arbitrary deterministic initial At each operator evaluation of these stochastic methods, a random sample & is drawn according to the distribution of the random variable g. We assume that the stochastic approximation error ( E) - F(u) is unbiased and has finite variance, leading to the following formal assumption.
points Q
Assumption 2.5. The random sample & is such that for all E U,
B(b(u, F(w)] 0, ([, - P(u)l3
Our proof techniques in the following sections can be applied to analyze the convergence and convergence rate of the stochastic Popov [Popoy] 1980) method with an appropriate selection of stochastic clipping. However, due to space constraints, we leave this exploration for future research.
3 Stochastic Clipped Projection Method
Common approaches to developing convergent methods for generalized smooth optimization and VI problems are normalized or clipping stepsizes. We focus on the latter one and present stepsizes for the stochastic projection method (7] applied to a-symmetric operators:
= 3 min (1,
1
(9)
$
where 3& for all h: 2 0 and & random variable, such that 5 and & are independent conditionally on ug. In other words, at every iteration of the projection method, having ug, two independent samples of
2he results easily extend the case when the initial points are random as long E[[lvo| [?] and B|]]hol|?] are finite.
5

---

Published in Transactions on Machine Learning Research (09/2025)
the stochastic operator are drawn: (1) ((ux, Eke for the direction of update and (2) D(ux, (2) for clipping
stepsize 7h- We define the sigma-algebres Fk for the method:
F tEu. E4
for all A 0,
(10)
with F-1 0. In the sequel, we provide important results on the behavior of the iterates of the clipped stochastic projection method.
3.1 Almost sure convergence
The following lemma establishes key relation for the iterate sequence {wx) generated by the stochastic projection method with stochastic clipping stepsizes. Its proof is in Appendix B.1
Lemma 3.1.
Let Assumptions 2.1
2.3 2.4 2.3 hold, and {uu} be the iterate sequence generated by stochastic
projection method
7
with stepsizes "ik defined in {0). Let parameter 3k be such that se 3r = 00 and
Ex=o Be < 00. Then, the following relation holds almost surely for all k 2 0,
Blllu+t- - =2 | U UE2 S llu 1² - 2pr (uk: U*) (20 +1).
(11)
Purthermore, almost surely, we have
Th dist? (ux, U*) oc,
(12)
and the sequence {1lix - x²' 11 is bounded almost surely for all u² E E
In the conventional analysis of the methods for SVIs with Lipschitz continuous operators, the sequence {ra} of stepsizes is deterministic and such that Σx= Tkk cc. In our case, Ykk is random variable, and to show a.s. convergence we have to show that the series Ek= is not summable. We do so, providing sequence of lower bounds for the series and by showing that random variable F(4))) is a.s. upper bounded for all k 2 0 and constructing. Moreover, we separate the series into
00
00
Σ Th
Σ TTk
St) +
Sk.
where {Sk} is a convergent martingale. In the next theorem, we present the first results on a.s. convergence of the stochastic projection method.
and 2.5 hold, and {un} be the ilerate sequence generated by stochastic projection method 7 with stepsizes "/k defined in (g) Let parameter 33 be such that Ex Sy.
Theorem 3.2. Let Assumptions
2.1 2.3 2.4
and Ex 32 < co. Then, the iterates us converge almost surely to a point ū such that ā E U almost surely-
The proof of Theorem 3.2 can be found in Appendix B.2
Notice that an unconstrained setting (U = R')
according to Theorems 3.1 and 3.2 in Koloskova et al. (2023), 1, for any clipping parameters 0, e > 0, there
exist a stochastic gradient operator Vf(-.) which satisties Assumptions 2.1 2.4 (with p ==2), 2). 2.5 for which
there exists fixed point of a standard clipping with one-sample which there exists solution
Eg13, min [v)(
|o] =0 = and [|E]|V)(O,E]]] 2 d2/12,
where > 0 is constant independent from step sizes parameter Sr. This observation leads to an unavoidable bias in onc-sample clipped SGD Koloskova et al. 2023). In contrast, by using two samples in clipped projection method, we overcome this problem and provide a.s. convergence to a solution.
3.2 Convergence rate
The difficulty of the convergence rate analysis is in the randomness of stepsizes 7/- To show in-expectation convergence, we can take a total expectation on both sides equation [1] of Lemma 3.1 However, since % is a random variable, we have to provide a lower bound on E(yy (ug, U*] With this goal in mind, in the next lemma we show that the sequence (E]][F((x)III] of expected norms is bounded. The proof of the lemma is in Appendix B.3
6

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma 3.3. Let Assumption 2.1 hold, with E (0, 1/21 Assumptions 2.5 2.4 and 2.5 hold, and let {uk
be the ilerale sequence generaled by stochastic projection method 77) with slepsizes 7hh defined in (9] Let parameter Sx be such that h 3x = 0c, and 0 8% < 00. Then, the sequence (wx))) is bounded by some constant CF > O.
To prove the preceding lemma, we show that the expected norms of the operator are bounded by some constant OF the trajectory of the method. Unfortunately, even though the sequence ([)))l) is bounded almost surely, it does not imply that [[u))[( is bounded. To show this, rely on the properties of the method and the generalized smoothness of the operator in Proposition 2.2 to obtain that for all k 2 0, and arbitrary solution v",
[[ & P(e))
uu v" [[ Kill "11 + K2llux - ballaa--ll///000 00110/(1-a)) + +|I[(v)]]
(13)
Notice that by taking expectation in 13 the RHS is undefined for 1/2. For (0, 1/2], using 13
and boundedness of [[[| uu o II], that follows from taking expectation in [1I) we achieve the desired bound on [|[] ((=))(())))))))( Using this result, in the next theorem, we provide convergence rate for the projection method with clipping.
Theorem 3.4. Let Assumption 2. with a E (0,1/2), and Assumptions 2.3 2.4 and 2.5 hold. Leb
}ux} be the sequence generated by stochastic projection method (7) with stepsizes Yhk defined in Let D& Eldist (ux, U*]] and CF be an upperbound on (ux))( Then, we have:
Case 2. Let Bx= a(2+k)
2
with =ummn ( (1 }.
Then, the following inequality holds
8Do
6(20² +1)
D&+1 I k22
+
for all k k
(14)
a²k
Case 22 2. Let Bx- =
(Kt1y7, where 1/2 < < and > 0. Then, the following inequality holds
b
(1 - 2/2 (Do + (20" +
2/D
Dr S
for all k 2 1,
(15)
(ab)2/r p/p ((k + 1)1-111---- - 21 2//0//
where Dj = E[dist? 2 (ux, U'}], ūp = 1E B1) Σk=o Beue and = ummn { Z
To derive the convergence rate in terms of E(dist (ux, U*] we need to relate the progress at each iteration,
measured by dist [*]] to E[dist (ux, U*)]. Using the boundedness of (((x)( we first bound
Elyxdist" (u,, U*]] in terms of EEdditt( (ut. U*)]. Finally, we estimate E[dist" (uę, U through E(dist (u., U+]
by applying Jensen's inequality, which holds for p 2 2. The proof Theorem 3.4 is in Appendix B.4
For the simplicity of convergence rate comparison, assume 2(#++0) 2 1. Then, from Theorem 3.4 we obtain O + "'(Coto'') last iterate convergence rate for p 2, and O (Do (C)))" average (or best.) pa/agan -3/5 iterate convergence rate for > 2 with g E (1/2, It is worth mentioning that obtained rates are unbiased,
unlike the analysis in Koloskova et al. (2023). However, comes with the price of two oracle calls per iteration. For p 2, the rate from Theorem 3.4 matches the rate O obtained in Theorem 4.3 (Loizou et al. 2021 for SGDA under stronger assumption
quasi-strong monotonicity and Lipschitz continuity of the operator. interestingly, for p = 2, the parameter y appears in the rate as / in both (Loizou et al. 2021 and in our Theorem 3.4 which is known to be the optimal dependence on μ (Beznosikov al. 2022. The rate for p > 2 is new in the stochastic case and generalizes the convergence results in deterministic setting (Vankov et al. 2024h. From theoretical perspective, the clipped projection method and its two-sample variant differ in several key aspects. In terms of asymptotic convergence, the standard clipped projection method suffers from an unavoidable bias, whereas our elipped projection method with two samples per ileration enjoys almost sure convergence. For convergence rates, our theorem shows a sublinear rate for the two-sample variant, while there are no known results for the standard clipped projection method in the sctting of stochastic VIs. This makes the two-sample clipped projection method more favorable from a theoretical point of view. We also compare the performance of the two methods in the numerical experiments section.
7

---

Published in Transactions on Machine Learning Research (09/2025)
4 Stochastic Clipped Korpelevich Method
The stepsizes for the stochastic Korpelevich method for a-symmetric operators are as given below
k 3x min
(16)
( 401
where Bk for all & 0 and & is random variable associated with the stochastic approximation @(hy, + of F(hx). We define the sigma-algebra Fk for the method, follows:
F = = Sa . 42) for all k 0,
(17)
with F-1 = 0. Notice that to obtain hx+1 from point uR, the stepsize " clips @(hx: (b), not the stochastic approximation ((ug, E of the operator point uk, i.c., the update for h4+1 in relation (8) is given by
uk Puche BR min
1, [he, Etil
1
((hn: Ek)),
(18)
{1,
h&+1 Pu
hx BK min
[0 [/)1l
Thus, sample & is drawn after Eh. and @hh, ( is completely determined when Fe-1 U (4) is given, thus the stepsize is determined as well. This property of the stochastic Korpelevich method with clipping stepsizes is crucial for further convergence analysis of the method. In the sequel, we provide important results on the behavior of the iterates of the stochastic elipped Korpelevich method.
4.1 Almost sure convergence
In the forthcoming lemma,, we provide some basic relations that hold almost surely for the iterates of the stochastic Korpelevich method with clipped stochastic stepsize.
Lemma 4.1. Let Assumptions 2.1 2.5
2.4 and 2.5 hold. Also, let { and {ux} be iterates generated
by stochastic Korpelevich method (8) with stepsizes "i defined in (16) and with parameter By such that Ei= Be co and Σx 82 co. Let uk = l| u² + 2 u + 2y (uk, U*), then the following relation holds almost surely.
E[us+1 FR-1]
(u--1, S Us 2 h4 up-1l dwt
(19)
+ 0632( + Ce a)020)
for all 2 0,
where C. (e,,, K1, when (0,1), and C. (Bk, a) exp(L1 when 1. Moreover, the following relations hold almost surely,
n dist (ux, U*) < 0o,
Σ
lhk - uxl2 < oc.
(20)
k=0
Furthermore, the sequence (1]hg un ||} is bounded almost surely for all u" U*
The proof of Lemma 4.1 is in Appendix
In the standard analysis of the Korpelevich method for SVIs with Lipschitz operators Kannan & Shanbhag (2019); Vankov et al. (2023), a.s. convergence results were achieved for a deterministic stepsize sequence {7x] J- In our case, similarly to projection method analysis, {**} is a sequence random variables, which makes the analysis of the methods more difficult and involved. By the choice of stepsizes 7 as given in (16) and the iterated expectation rule, the following relation holds true
E| El 2 F(ux), un u²) = for all A: 2 0.
(21)
8

---

Published in Transactions on Machine Learning Research (09/2025)
To prove 21 for the stochastic Korpelevich method, we note that the clipping stepsize is using [1 (ehghh&)))l which decouples from ((ux, {i) by properly using conditional expectation. Specifically, we first take the expectation conditioned on Fk-1 U 4 and observe that " is completely determined given FR-1 U Then, we use Assumption 2.5 for the sample 22, and the relation (21) follows by the law of iterated expectation. Interestingly, we do not. have to take another sample for the clipping in the stochastic Korpelevich method, as we have done the stochastic projection mothod. Thus, perform one iteration, we use two oracle calls in both methods.
Using Lemma 4.1 next present the almost sure convergence of the stochastic clipped Korpelevich method.
Thcorem 4.2. Let Assumptions 2.1
2.3 2.4 and 2.5 hold and {hx}, {wx} } be iterates generated by stochastic
with slepsizes "kk defined in (16). Let parameter Se be such that Ek=o 3r. 00, and Ex=o S c0. Then, the iterotes h2 and up converge almost surely a point u such that U almost surely.
Korpelevich method {
To prove 0.8. convergence, we firstly show that Lk= = 0c 0.8., by providing a sequence of lower bounds on Yks using a.s. boundedness of || - u²'l of Lemma 4.1 and proving that [1x)l is a.s. bounded. Similarly
to the proof of 3.2 we scparate the scries into
Σ Sk.
7kk
+
k 0
Amm0
where { is a convergent martingale. The full proof can be found in Appendix C.2
4.2 Convergence rate
We start our analysis by taking the total expectation on both sides of equation 19 from Lemma 4.1 For further analysis, similar the stochastic clipped projection method, the challenge lies in the randomness of the stepsizes "yk- To handle this, firstly, we establish lower bound for E/yydist" U*)] by showing that the sequence [R[[F(u:)]]] of expected norms remains bounded, as shown in the next lemma. The proof of the Jemma can be found in Appendix B.3
2.5 hold. Let {uz]: {he} be iterates generated by stochastic Korpelevich method ( with stepsizes Vi defined in (16) and the parameter Br. such that E 3x = and Zk=u2 32 k 2 0.
Lemma 4.3. Let Assumption 2.1 with a E (0. 1/2), and Assumptions 2.3
2.4
Then, E F(hx)]] is bounded by some constant Cp > O for all
Similarly to the analysis presented in Section 3 we bound F(hx) by using a triangle inequality and the property of a-symmotric operators, and by taking the total expectation, we obtain
B[]lF( K,EIIlu w*ll + K2 e ["110/(--a)]] + +[F((=)I (o0)(0
(22)
We can show that the preceding bound has finite expectation only for 0 < a S 1/2, which motivates the restriction a in Lemma 4.3 Equipped with the boundedness of the sequence [E|]l [(h))l) of expected norms of the operator along the iterates } we present the next convergence rate theorem.
Theorem 4.4. Let Assumption 2.1 with a E (0, 1/2]/ and Assumptions 2.3 2.4 and 2.5 hold. Let {ux],
{ be the iterate sequences generated by stochastic clipped Korpelevich method (8) with stepsizes ?h defined 16). Let D Eldist? (hy,st?(hu,Uu U*]] and Cp be an upperbound on (()))( then the following results holds:
2 with a = =umin (1, 2iCt+oj). }. d max[44, 2nxx444.2/36 2/3(KK + K1 + +k2] where
Case = 2. Let Bx
al 2d k) Ko, K1, and K2 are from Proposition
2.2 u). Then, the following relation holds
8d 8d2
12 + (i)2a)
DE41 <
a² +
for all k 2 1.
(23)
a²k
9

---

Published in Transactions on Machine Learning Research (09/2025)
Case p 2 2. Let B% = [kt1je, where 1/2 < q < 1 and 0 < I min {
1
Then, the
Jollowing inequality holds for all 2 1,
2 20(x-2)/0(1 - //2/r (Do + (o² ( + K10 (202 + +1/ 1)) 1))2/2
D2 S
(24)
(ab)2/P ((k: + 1)2-9 21 22-9)
where Dr = E|dist (ūk. ( U² ūg- = -E -i Ei=oBeuu Beus, and a = jmin { MCC+o))
Similarly to the proof of Theorem 3.4 to derive the convergence rate in terms of Eldist (hg, U*]] need to relate the progress at cach iteration, measured by B(yudist"(h,, U*)] to Ejdist (h2, U*) Using the boundedness of (ha)) and applying Jensen's inequality, which holds for p 2 2 we obtain the final rates. The proof of Theorem 4.4 is provided in Appendix C.4
For the simplicity of convergence rate comparison, assume 2(Cr +0) 2 1 and Ko + +K + KK 2 2p Then
v3"
by denoting K Ko + K2 + K3, from Theorem 4.4 obtain O ((Cpto)"k3 + ( last
nzk
iterate convergence for p p= 2, and O (o"i"(Doto" 2 -K 2 ( (C
average (or best) iterate convergence
/2/0k20 w/r
rate for p > with q E (1/2, 1). In both cases p = 2 and p > 2 the convergence rate of clipped stochastic projection method in Theorem 3.4 and the rate of stochastic clipped Korpelevich method in Theorem 4.4 have the same dependency in k. For p p-2 the rate from Theorem 4.4 matches the rate O(+) obtained in Proposition 5 (Kannan & Shanbhag 2019) for stochastic Korpelevich method under stronger assumption strong pscudo monotonicity and Lipschitz continuity of the operator. Interestingly, for p p= 2, the parameter I appears in the rate as , in both Kannan & Shanbhag (2019) and in our Theorem 4.4 which is known to
be the optimal dependence f (Beznosikov et al. 2022). For p 2, the obtained rate is new in stochastic case and gencralizes the results in deterministic sctting for Lipschitz contimuous operators (Wei et al.) 2021
and a-symmetric operators (Vankov et al. 2024).
5 Numerical Experiments
We study the performance of the stochastic clipped projection and Korpelevich methods, for different values of parameters a > O and p > O. Despite the absence of analysis, we also implement the stochastic clipped Popov method with 7hk = 3x min(1, (To)) (llve Il
uk++1 Pur (ue nh (ha, (x), het1 = Po 7K+1 1
where un ha E U are arbitrary deterministic initial. We consider an unconstrained minmax game:
1 min max - | II + (wi, w2) lwall", U2
with p> 1, and un E IRd, u2 Rdd Then, the corresponding operator F: 1R2dd -> Redd is defined by
||u ||l|P- |-2 un + u2) 1-2 u1
F(u)
(25)
We assume that we have an access only to noise evaluation of the corresponding operator and aim to solve unconstrained SVI(R2d, F)) with the following stochastic operator Φ(u, <) F(u)) + E, where & is random vector with independent zero- mean Gaussian entries and with variance o² 1. Then, F(u) = (u, is an a-symmetric and p-quasi sharp operator due to Vankov et al. (2024). We set these parameters to be {(a Rs 0.33, = 2.5), (a ss 0.5, p = 3.0), (a x 0.8,p p = 6.0)]. We also compare our results with the projection method that uses the same sample clipping, meaning stepsizes " clip [[ Ex)ll instead of different sample (1 (.)
In Figure D we plot an average distance to solution from the current iterate over twenty runs to the solution set function of the number of iterations. In particular, the stepsizes for clipped stochastic projection
10

---

Published in Transactions on Machine Learning Research (09/2025)
Cermergerce
Corvergencs
Convergeo
Carwergerc
(a) (a R5 0.33, p 1.5)
(b) (a R3 0.33, 2.5)
(c) (a R 0.8,p 4.0)
(d) (a Rs 0.8, 6.0)
Figure 1: Comparison of the clipped stochastic projection, samo-sample projection, Korpelevich, and Popov methods with B&= 100/(100 k2/2tc).
1991
(a) (o sz 0.33. 1.5)
(b) (a 0.33. 2.5)
(c) (a 2 0.8.p
(d) (a R2 0.8. 6.0)
Figure 2: Comparison of the clipped stochastic projection, same-sample projection, Korpelevich, and Popov methods with Bg+ = 100/((10- + k²-9).
and Korpelevich methods are chosen according to Theorems 3.4 and 4.4 respectively, with 8g = 100+ for g = 1/2 + e with e >>00 O. Note that, according to Theorems 3 and 4.4 than 1/2: meanwhile, the rates in these theorems are better for smaller choices of q. We also set Br 100+ for stochastic clipped Popov method and the stochastic clipped projection method using the same sample ((u,,Ex) Ex) for clipping.
100
the parameter q should be greater
Based on this experiment, we made three important observations. Firstly, the stochastic clipped projection method and the same-sample stochastic clipped projection method show similar results, despite the fact that the latter has a biased error. We speculate that this is because the biased error is relatively small, and in practice dominated by the term redist"(us, U*). Secondly, although in the stochastic Lipschitz SVI setting the Korpelevich method outperforms the projection method, we do not observe this advantage in the generalized smooth SVI setting. This aligns with our theoretical results, since both methods have the same complexity and require two oracle calls per iteration. Morcover, even in the standard Lipschitz continuous strongly monotone case, both methods achieve the same order O (k) rate in the leading stochastic term, with the Korpelevich method enjoying a smaller non-leading term because it can use a larger stepsize of + Beznosikov et al. (2022) compared to + for the projection method Loizou et al. (2021) However, in the generalized smooth case, where stepsizes are clipped, the Korpelevich method no longer benefits from larger stepsizes.
Next, we investigate the performance of the methods for larger values of q. In Figure 2 we set q 1-6,, e, 100 3r 1004 e, and run all four methods for the same problem parameter setting. We observe that for all considered a, despite the theory, larger choice of improved the performance of all methods in the o-neighborhood.
For the same setting, in Figures 8 and 4 now we plot the distance to the solution from the average iterate Th = / - Interestingly, the clipped projection methods outperform the clipped Korpelevich method, even though both enjoy the same convergence guarantee of order 0(1)k((19)/p))
o Ruu, In terms of average iterates, we obscrved that smaller values of g are preferable.
11

---

Published in Transactions on Machine Learning Research (09/2025)
Cerwergerce
Corveggece
Corvergew
Corwergrro
(a) (a R5 0.33, p 1.5)
(b) (a R 0.33, == 2.5)
(c) (a R 0.8,p 4.0)
(d) (a Rs p.8,p= 6.0)
Figure 3: Comparison of the clipped stochastic projection, samo-sample projection, Korpelevich, and Popov methods with B&= 1000 + kl/2te) for averaged iterales.
Coneeggaars
Conanggarr
Pape
(a) (a p 1.5)
(b) (a 0.33, = 2.5)
(c) (a = 0.8,p 4.0)
(d) (a 23 0.8 6.0)
Figure 4: Comparison of the clipped stochastic projection, same-sample projection, Korpelevich, and Popov methods with & 100/(100 k) for averaged iterates.
6 Conclusion
This paper studied the SVI problem under generalized smooth and structured non-monotone assumptions. Specifically, we consider a-symmetric and p-quasi-sharp operators, a class of generalized smooth and structured non-monotone operators for SVIs. For this wide class of operators, we proved the first-known almost sure convergence of stochastic clipped projection and Korpelevich methods for all parameters We also provided O(1/k) convergence rate for both considered mothods when the operator is p-quasi sharp with p p= For p p> we provided ((k-2(1-9)/4
average (or best) iterate convergence rate for both methods, where q is a stepsize parameter 1/2 < 9 < 1. Despite the generality of our results, there are still open questions that remain. In particular, it would be interesting to know if it is possible to show in-expectation convergence rates for a-smooth SVI for > 1/2. Another attractive direction of further research in generalized smooth SVTs is in the relaxation of p-quasi sharpness assumption to Minty (μ 0) or weak Minty conditions (Jx < 0). We also believe that our technique for proving almost sure convergence and in-expectation rates can be used for the analysis of other methods whose stepsizes are random variables, for example, stochastic clipped Popov method or first-order methods with adaptive slepsizes.
Acknowledgments
We thank the anonymous reviewers for their valuable comments. This work supported in part by NSF grants CIF-2134256, SCH-2205080 and CIF-2207688.
References
Ahmet Alacaoglu, Doughwan Kim, and Stephen Wright. Revisiting inexact fixed-point iterations for min-max problems: Stochasticity and structured nonconvexity. In Forty-first International Conference Machine Learning, 2024.
Aleksandr Beznosikov, Boris Polyak, Eduard Gorbunov, Dmitry Kovalev, and Alexander Gasnikov. Smooth monotone stochastic variational inequalities and saddle point problems survey. Xiviv preprint
12

---

Published in Transactions on Machine Learning Research (09/2025)
orXiu:2208.13592 2022.
Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent- ascent: Unified theory and new efficient methods. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 Proceedings of Machine Learning Research, pp. 172-235. PMLR, 2023.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooth nonconvex optimization is as efficient smooth nonconvex optimization. In International Conference on Machine Learning, 2023.
Sayantan Choudhury, Eduard Gorbunov, and Nicolas Loizou. Single-call stochastic extragradient methods for structured non-monotone variational incqualities: Improved analysis under weaker conditions. preprint ar arXiv:2302.1400 2023.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured nonconvex--oncooeenn min-max optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2746-2754. PMLR, 2021.
Rick Durrett. Probability: theory and eramples, volume 49. Cambridge university press, 2019.
Francisco Facchinei and Jong-Shi Pang. Finite-dimension variational inequalitics and complementarity problems. Springer, 2003.
lan Gemp and Sridhar Mahadevan. Global convergence to the equilibrium of gans using variational inequalities. arXiv preprint arXiv: 1008: 808. 01551, 2018.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. variational inequality perspective on generative adversarial networks. In International Conference on Learning Representations, 2019.
Eduard Gorbunov, Marina Danilova, David Dobre, Pavel Dvurechenskii, Alexander Gasnikov, and Gauthier Gidel. Clipped stochastic methods for variational incqualitics with heavy-tailed noise. Advances in Neural Information Processing Systems, 35:31319 --3332,, 2022.
Yu-Guan Hsieh, Franck lutzeler, 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 Tuizeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Advances in Newral Information Processing Systems, 33:16223-16233 2020.
Samy Jelassi, David Dobre, Arthur Mensch, Yuanzhi Li, and Gauthier Gidel. Dissecting adaptive methods in gans. arXiv preprint arXiv:2210.04510 2022.
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 pscudomonotone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74(3):779-895 -20, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Anastasia Koloskova, Hadrien Hendrikx, and Scbastian Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pp. 77343-17366 PMLR, 2023.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Motecon, 12: 747-756, 1976.
Georgios Kotsalis, Guanghui Lan, and Tianjiao Li. Simple and optimal methods for stochastic variational inequalities, i: Operator extrapolation. STAM Journal Optimization, 32(3):2041 2073, 2022.
Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Convergence of adam under relaxed assumptions. arXiv preprint 23044 13972, 2023.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2024.
Tianyi Lin and Michael 1 Jordan. Perseus: A simple and optimal high-order method for variational inequalities. Mathematical Programméng, 209(1):609-650, 2025.
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.
Arkadi Nemirovski. Prox- meexm with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229 251, 2004.
Thomas Pethick, Olivier Fercoq, Puya Latafat, Panagiotis Patrinos, and Volkan Cevher. Solving stochastic weak minty variational inequalities without increasing batch size. In The Eleventh International Conference on Learning Representations, ICLRR, 2023.
David Pfau and Oriol Vinyals. Connecting generative adversarial networks and actor-crite methods. ar preprint arXio:1610.01453 2016.
Boris T Polyak. Introduction to optimization. optimization software. Inc., Publications Dinision, New York, 1:32, 1987.
Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathe- matical notes of the Academy of Sciences of the USSR, 28(5):845-845 1980.
Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Mare Lanctot, loannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. arXiv preprint arXiv:2206. 200555200 2022.
Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrapolation for coherent mon-monotone variational inequalities. Advonces in Neural Information Processing Systems, 33: 14303-14314, 2020.
Scbastian U Stich. Unified optimal analysis of the (stochastic) gradient method. ar preprint arXiv:1907.04232, 2019.
Daniil Vankov, Angelia Nedić, and Lalitha Sankar. Last iterate convergence popov method for non-monotone stochastic variational inequalities. arXiv preprint arXiv:2310. 16910, 2023.
Daniil Vankov, Angelia Nedié, and Lalitha Sankar. Generalized smooth variational inequalities: Methods with adaptive stepsizes. In Proceedings of the 4 41st International Conference on Machine Learning, PMLR, volume 235, pp. 49137-49170, 2024.
Bohan Wang Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sirth Annual Conference on Learning Theory, pp- 161-190. PMLR, 2023.
Chen-Yi Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence constrained saddle-point optimization. In International Conference Learning Representations, 2021.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Wenhan Xian, Ziyi Chen, and Heng Huang. Delving into the convergence of generalized smooth minimax optimization. In Forty-first International Conference Machine Learning, 2024.
Zhnoyu Xiao and Uday V Shanbhag. Computing equilibria in stochastic nonconvex and non-monotone games via gradient-response schemes. arXie preprint orXiv22504.14556 2025.
Farzad Yousefian, Angelia Nedié, and Uday V. Shanbhag. Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems. In 53rd IEEE Conference on Decision and Control (CDC), Los Angeles, CA, USA, December 15-17, 2014, pp. 5831-5836 IEEE, 2014.
Farzad Youscfian, Angelia. Nedić, and Uday V. Shanbhag. On smoothing, regularization, and averaging stochastic approximation methods for stochastic variational inequality problems. Malhemalical Programeming, 165:391-430 2017.
Nikos Zarifis, Pugian Wang, Ilias Diakonikolas, and Jelena Diakonikolas. Robustly learning single-index models via alignment sharpness. arXiv preprint arXiv:2402.11730 2024.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020.
Qi Zhang, Yi Zhou, and Shaofeng Zou. Convergence guarantees for rmsprop and adam in generalized-smooth non-convex optimization with affine noise variance. arXiv preprint or arXiv:2404.01436 2024.
Zirui Zhou and Anthony Man-Cho So. A unified approach to error bounds for structured convex optimization problems. Mothematical Programming, 165:689-728, 2017.
A Technical Lemmas
In our analysis, use the properties of the projection operator Po(-) given in the following lemma.
Lemma A.1. (Theorem 1.5.5 and Lemma 12. 1.13 Facchinei & Pang (2003)) Given a nonempty conver closed set U Rm the projection operalor Pv(-) has the following properlies:
- Po-Po u- Pc(()) 0o for all u E U,VER"
(26)
|/u Po(l))1 ||u v112 - ||c
for all E UEU, (v)) (v)l
(27)
[PPu(u) (v))l $ | for all E.".
(28)
In the forthcoming analysis, we use Lemma 11 Polyak (1987) which is stated below.
Lemma A.2. [Lemma 11 |Polyak (1987) Let (vx), (2x), { and {bu} be nonnegalive random scalar sequences such that almost surely for all k 2 0,
E 1k+1
Fil 5(1 + ax)ek 26 + Dy.
(29)
where Fx = (vo...... Uks 20. 2k, ao...... Ok bo..... bu), and a.s. En an < 00, En by < 00. Then, almost surely, lim Up = v for some nonnegative random variable v and Σi= 2x <0.
As a direct consequence of Lemma A.2 when the sequences {rc), (zch tauts {bx} are deterministic, we obtain the following result.
Lemma A.3. Let (Ta), (.x), (āx). (ba) be nonnegalive scalar sequences such that for all l 2 0,
ū 5(1 + 2x) Es + bb:
(30)
where Exso āz < and De by 00. Then, lim Tt. ē for some scalar 6 2 0 and Ek=o 2o
15

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma A.4. Let X be non-negative random variable such that B[X"] is defined for some p 1, and B[X*] # O, then for every a > 0 it holds
P(X > ((( = ap
1
(31)
Proof. Let Y XP. By the conditions of the lemma, the expectation E|y] E'x]] is well defined. Then, by Markov's inequality:
P(X ((E(X))) = PP > (x)()"))
B[X"
a
Lemma A.5. Let a1, a2 be nonnegative scalor and > 0. Then the following inequality holds:
(01 az)² 2 (a) 22 + ag).
Proof. Let = (21, b = (1,1), then by Hölder inequality:
an + 02 = ||bbl
-
s (a ab) (P( + 1/(p-1//P
Raising the inequality in the power p get the desired relation.
A.1 Auxiliary Results
In our analysis make use of Lemma 3 and Lemma 7 from Stich 2019), as well the sequences provided in the proofs in [tich (2019) Lemma A.G. Let {rw} and {sk} be nonnegative scolar sequences that satisfy the following relation
Tk+1 S (1 aaa))) ru - barsk + on for all k 2 0,
where > 0, b> 0, 0, and
7k- 2d k)
for all 2 0,
where d 2 a. Then, for any given K 2 0, the following relation holds:
b
8d
2c
W K
WESk + ar S
To
aK
k=0
where = =2d/a + k, 0 < k < K, and WK = Ek wk.
Lemma A.7. For > q 2 1/2 and K 2 1, we have
K
((K + 111--9 -22-9..
(32)
t 1+D
1
For = 1/2 and K 2 1,
K
S log K + +))
(33)
t + 1)29
0
For > 1/2 and K 2 1,
K
1
(34)
(l 1)24
2g
0=0
16

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. Let > 2 1/2 and K 2 1. Then, it holds
K
K
ds
((K + 1) 110---2--11 -21-9).
(35)
(1+
1)0
1 (8+ 1)
t=
s=1
When q= 1/2 and 2 1, then
K
ds
Σ
log(K 1).
(36)
t++1
s+1
==
When q > 1/2 and 2 1, we have that
Σ
K
1 K
ds
1
1
(37)
1)20
==
(8
2g + 1)20
(2q
1)(K + 1)20-1
2q
B Projection Method Analysis
B.1 Proof of Lemma 3
Proof. Let k > 0 be arbitrary but fixed. From the definition of uk+1 in 7 we have ||ux+1 y|I IPPo (ux a up. Ex)) y/12 for all E U. Using the non-expansiveness property of projection operator we obtain for all E U and k: 2 0,
28
||u+11 y/1²
alu 7n (uk: [x) 811²
Ilu y/1² 2 ( ukk Ex), un 3) + +2211 Ex]l
|lu - y11 + >il ( puux, 112
2mt (F(x); ux y) 2n (ek, us v),
(38)
where eq F(ux) (uu Ex).
By the definition of the stepsizes 19 N Bg min(1, (o then the term bb 1l? can be upper bounded follows
NHl (uu, Ex]ll = > (uN: Ex) F(ux) + F(ux) ( ( + $ (uR: =²)1
I B min
3(1ee 12 12 +|el2 (ux =))1
[ +2) 2
3,3 where 6 Ex) - F(ux), ot Tuux, <2) F(ux). Thus,
- 35tllew11 + +3381le2
(39)
||ux+1 - 2/2 < ||uu - y/1 -
1, 2 (Fxx), up - y) + 27x (ex: uy 3) + 33 (llexl || 2 + ||e 1).
(40)
Plugging in y u² U* where u' is an arbitrary solution, and using p-quasi sharpness get:
||u4 u² 12 < || - u² 2ur (us, U*)
+ (ex, us - u²) + 3. + ||e2| + 1). 2
(41)
Using stochastic properties of & and & imposed by Assumption 2.5 and the conditional independence of & and e2, we have;
El (ex, un u²)(Fa-11 Blar F (B(eR Fa-1). 4 u²) 0.
17

---

Published in Transactions on Machine Learning Research (09/2025)
B||lex1 Fk-11 $ o², E| Fk-1l S 5
Thus, by taking the conditional expectation on FR-1 U & = (En- .......,k.11 1 in relation 41 we obtain for u* U and for all k 2
Fa-1 U EA S lue 1²112 + 333 +1) 243x min { (w Eil
E U -
dist dust U*). (42)
The equation
(2 satisfies the condition of Lemma A.2 with
Uk uu
u² 11?,
a O, 2 2pr dist (ux, U*), by 336 +1).
(43)
By Lemma A.2 it follows that the sequence { converges a.s. to non-negative scalar for any u² U*, and almost surely we have
dist (uz, U*) < co.
(44)
k=
Since the sequence [llu - }²] converges a.s. for all w' E U it follows that the sequence {Ilux u=| is bounded a.s. for all u² E U
B.2 Proof of Theorem
Lemma B.1. Let "k are given by then the series of {7k} is non-summable almost surely,
00 a.s.
(45)
k=
Proof. We will show that Σ = Be min (1, [o(uu ]
co almost surely by the sequences of lower bound
on this scries. Consider the following event:
A {lee2l 2
where of = D(us, 2 min {1, [ } then,
F(ux) is stochastic error from the sample for the clipping stepsize %h Define
I₁ = IxI((AA + =xl((A)) 2 xxI(As).
(46)
where the random variable I((Aa) is the indicator function of the event As taking value when the event occurs, and taking value 0 otherwise.
By the definition of kg, the triangle incquality and definition of I(As), we have
T(A)) = min
T(As)
min
1. [F(u))] + ||e
I(As)
1
min
1 [F(u)]] 20 I(Aa))
(47)
18

---

Published in Transactions on Machine Learning Research (09/2025)
By combining the resulting relation with B[T(Ax) | [k-1l] we have the following lower bound
47 using the definition of % and adding and subtracting
Σ
BN min
(1(At) E(((AN) FR--1))
[[((u))] 20
k=U
1 [F(u)) || + 20
BR min
(B[T(AR) FR-1).
(48)
k=0
To bound pk: B[T((A)))FFi1 = P(A FR-1) provide upperbound on P(Ak Fk-1) using Markov's
inequality and Assumption 2.5
Bllee||| Fk
P(Ax Fk-1) = P(]ee) > 2BIl|c|1| |Fx-1l)) = 2B 2B||e; [R-1I) 2
(49)
This implies ETT((A)) FR-1] 2 1. 2- Define Sn = & (T(A)) - B(T((A)) by construction, Sn is a martingale:
E[S So: , Sn] Sr, + Bl8n+1 1 (I(An+1) B[I(AA+ ()F,,))) ....... Sml Sn.
We want to show that limn- Sn + S < oc almost surcly. We provide an upper bound for E[Sa]:
B|S
PET((T(AN) (Pp)))
Σ
(E((((AA)) (T)(T(A)) -Pi)
(50)
Osk<isn
By the law of total expectation, and noting that B[((As)) Pke FR-11 = for any k, we find that for all k <isn,
[I( (IAAT pa) = ([((A)) PA)B((((A.) P&) Fi-1l] 0.
(51)
implying that, for all n 20
E[SA] Σ (T(() -Pa)
(52)
Since [{{((AA)) - px)) [Fr-)==Var(((AA) FFx-1) and the random variable T(Aa) is a Bernoulli given Fk-1
with mean Pk, then
E[(I(AA) - p2)) Fx = Var(I(AA) ( <
By taking the total expectation we get [[([(A+) - pp) s 1. and combining the previous two relations, we obtain
1
B
<
3 < x a.s.
4
k=0
From Theorem 4.4.6. in Durrett
2019 follows that S, converges to < oo almost surely (and in Lg).
To further lower bound xxI(AA we show a.s. boundedness of |[F())))l for all & 2 0, using property of a-symmetric operators. To estimate [[F(u))],, we add and subtract P(v"), where v² U is an arbitrary but fixed solution, and get
[[(x)] = [[(())) F())
- + [[('']]]
Define the following event:
A = (w Ω: C(w)) E ER s.t.llu((())) 0'1l -0 <[]] 0).
19

---

Published in Transactions on Machine Learning Research (09/2025)
Based on Lemma 3.1 the sequence {llu =01l} is bounded a.s., and thus P(A) 1. Let A, now est astimate Case E (0,
using the a-symmetric assumption the operator.
(w)) F(u")] I [l)x(w) 0z (K (v)) + K2llux(w) -0 11/0110)))
(53)
Since E A, it follows that [|ux(w) 0"11 ((w) for all & 2 0. Using this fact and 53 we obtain that for all k 2 0,
[F((x(W))I S ((W)(Ko + Ki (1 K2C(W)//UL-)) |F(x")]]
(54)
Therefore, the sequence (I]F(ux())]II is upper bounded by Ci(w) C(w) (i]lF(b))1 KzC(w))o/L=aa) [[[(')) Case = 1. For = 1 by Proposition 2.2 we have
[F(u((w)) F(v")l S (on((w)-""lle + [1IF((")]I) (xp(((lll)) - -0 ==1))-
(55)
Therefore, for all 0,
[[](u(())]] < | [(ux F F(v*)|| +|](==)
$ [[)x(w) - 10 (Lo + L II) exp(Lillux(w) =0ll) + +[[(())]
(56)
Since w E A, we have [1 - 10 < ((w) for all k 2 0, which when used in (56, implies that for all k 2 0,
[F(u( < 12 (w) - 0" 00 + L exp(()))l))) IIl + [[=((")]
$ (To + [ exp(II + |F(
(57)
Hence, the sequence (w)) is upper bounded by Ci(w), where Ci(w) C(w) + F exp(L,C(w)) + [[]))]| Now, for both cases a E (0, 1) and a = 54 and 57 respectively, we have that [w)(ll upper bounded by max(Cr(w), (w)) Thus
P(F(u;)) is bounded) = 1.
Then almost surely we have (i) F(ux) is bounded (ii) Σx (I(AT())) - E[T(AA) | Fk-1l) converges to S < oc, (iii) E[(((s)) Fx 2 1. Consider w E Ω such that (i), (ii), and (iii) hold, then in a view of 48) we have
Σ Bwox(w) 2 min { (ww + 20 22
S(w) + +2 min {
CC
Σ
Br = 0a
(58)
(w(w) + 20
k=0
k=0
where the last equality comes from Exe By co, which concludes the proof.
Proof of Theorem 3.2
Proof. By Lemma 3.1 have
Th dist dist?(ux, U*) < oc a.s.
(59)
Due to Lemma B.1 the series
k== 7k
almost surely, then it follows that
lim inf dist. (uk, U*) = a.s.
(60)
8-+00
20

---

Published in Transactions on Machine Learning Research (09/2025)
Since 1lux u²Il converges for any given u² E U*, the sequence {ux} is bounded and has accumulation points 0.8. Let (ki) be an index sequence, such that
lim dist" (ux, U*) = lim inf tist""ux: U*) = a.s. x-+00
(61)
R-+00
We assume that the sequence {uk,} is convergent with a limit point ú; otherwise, we choose a convergent subsequence. Therefore,
lim
ūll
a.s.
(62)
10000
Then, by 60 dist u, U*) 0, thus ū E U
since U is closod. Since the sequence {llux =²I]} converges
for all u² E U by 62 we have
lim ||us - ū/ = a.s. k-000
(63)
B.3 Proof of Lemma 33
Proof. By taking the total expectation in 42 in Lemma 3.1 and using the definition the stepsize Yk. we obtain for any solution U and all & 0,
B uk+1 u" [| S B[| a" "=1["]
2i (us, (u, + 33, + +
(64)
The equation 64 satisfies the conditions of Lemma A.3 with
0 Elllux- [[3] as = 0, Es =2 dist (uR, dist
U*)], by 3,822202 + +1)
(65)
Thus, by Lemma A.3 it follows that the sequence {Eillu, 113}} converges to non-negative scalar for
any a² E E Therefore, the sequence [B]]] u= [[]]] is bounded for all u* E U Next, using the property of a-symmetric operators, we show that [(x)))(()))l]] is bounded. Let v* E U be an arbitrary, but fixed solution. Then, by the a-symmetric property of F, we have that
[[(w))]] < [[F(ux) F(v II [F()")
(66)
< |lux - u² (Koo + K1 (()) + K2llux -=1///a-00)++ + +|
Taking expectation, obtain
[[][F(ux)]] S (Ko + FilIF(M (( -
w² - K2Elllu- 0" 00||)ta((1-a)) [IF(("))I
(67)
Notice, that Elllux 0" 1 ] B[[l|u:
and for S 1/2, the quantity 1/2(1- a) S 1.
Thus, we can apply Jensen inequality for concave function
E[[[44 - n.' -1)))//00-000 < Billu - v' 1112//2(1)00
Therefore, using these results and Jensen inequality for the first term in equation 67 we obtain
E[]lF(u)]l (Ko + K2 F "[) o" 1191//22 K2El|lu 8. 1/21 + [(u*)]
(68)
Since [[[lu 1|] is bounded, B[]] is bounded by some constant CF > 0 for all k 2 0.
B.4 Proof of Theorem 3.4
Proof. Letting y Pu. (u.( in equation
40 in Lemma 3.1 and using p-quasi sharpness we obtain
|| Po- (2+) < l|u Po. (uw) - 2pr (ux U*)
+ (Yx, un Po- (u+)) ) + ( + || +1).
(69)
21

---

Published in Transactions on Machine Learning Research (09/2025)
By the definition of the distance function, we have dist dist? (ux+1. U*) S 1x+1 Pu- (ux)))
Thus,
dist (us+i, U*) dist (ust U*) 2p (ux: U*)
(ek, us Pu- (wx)) 3,2 |e2ll + 1).
(70)
By Assumption 2.5 and the law of total expectation, and independence of samples &L and E follows that
E Elnwee up Pu- Pu-(u)))
E (Tx Uy Pu- (ux)) FR-1l]
E E (B
| 1), uu Pu-(uu))
0.
(71)
Also, we have || [k-11] s 0² and e| FR-11 s o?. Thus, by taking the total expectation
in 70 we obtain
Eldist (4++1. Eldist((ux+1 U*) S Crdiist(uss U*} 2 (ug, U*)] + 332 +1)
(72)
We aim to upper bound dnxtt (ux, U- To do so consider an event Ag. defined as follows:
A (1IF(u))] + ||ex|l s 2(B[I B[le
Then, by the law of total expectation, we obtain
E[nadist U*)] = E[yudist (n)(a) + Elyadist"(ux, ("N
(73)
where A denotes the complement of an event We want to provide a lower bound on P(Ax). To do so, we upperbound P(Ax) using Markov's inequality, as follows:
P(Ax) P (()) |lex|| > 2(E[]) + [[[le>|l)))
E|| [()) + + [[]eex]]
2 [[[]] [[ lx
(74)
2
Thus,
Ely (ux, U²]] dist (ux A1) P(Ax)) + Blyadist U*)
2 2 Blyadist (ux, [ + E[y (u,, U² (As
2 Elu (ux, U²) [AR].
(75)
By the definition of the event Ax: we have
ElzadistP (ux, (*)|AR) = B min 1, [ Ex) dist (ux, U²)) |
) dist [
2 E min
1, |[F(wu)] + +|eexll
2 Bx min
2(E +(leell+((llel]]] Eldist (mn. U²)
(76)
By Lemma 3.3. F(ux)) [I] < Cp for all & 2 0, and by Assumption
2.5 and Jensen inequality, have
E[[lex|l| ||] < E [| 22 < a. Thus, it follows that
1 Elyadisst (wx, U*)] 5 3 min {1, 2(Cr +o)
1
Eldist (uk,U").
(77)
22

---

Published in Transactions on Machine Learning Research (09/2025)
Combining equations 72 and 770, and using a = ummnn { 2(C++o) }. we obtain
dddist (u++1, U+] s B E[dist U*)] - a.3,. a. U*)]+ + 320 + 1).
(78)
Now let D3 E| 2 (uy U,},, and consider the following two cases:
Case p= 2. When p == 2, equation
78 satisfies the assumptions of Lemma A.6 with
Vk Dks
0 Bk,
8k =0 0, d= a, =322 1).
(79)
Then, by Lemma A.6 we get the following convergence rate for all A: 2 1,
8Do
6(202+1)
DK+1 S 12
(80)
a²k
Case > 2. When p 2 2, by applying telescoping to inequality obtain
78
and rearranging the terms we
& Σ
Ela
(uxis Budist" (ux, U*)] S Do DK+1 + +(202 + 1)
3
(81)
1=0
Since p 2 2, the function dist? (+UU*) is convex, thus by defining on -Et=o 3x) 3x) -t Snue and applying
Jensen inequality be obtain
By E[dist (ūp, U*) S E Bedist U*)]
Since p 2 2, by applying Jensen inequality one more time, we obtain
u/ p/2 p/2 [E]dist (*))) s (dist (ux,
EElistt (ūx, U*)]
Applying these estimates, we get
(Da)o/2
Be <
3/D s Do DD--D+++*o + 3(20² +1)
Σ
3
(82)
t=0
1=0
t=
Since Ba 1jt with 0,1 q 1/2, then {Ba} satisfies the conditions of Lemma 3.3
Also, by
Lemma A.7 the following inequalities hold: for all k 2 1,
b ((k + 171-9 21-9),
b²
8
52 <
(83)
29
Combining equations
82 and and omitting DA+1, we obtain
(Dx 9) (Do 3b2 (202 + +1/ 1))
(84)
ab ((k 1)1-9 -2--9)
Raising both sides of the preceding inequality in power 2/p, we obtain
D₂ S (1 22/0 (Do + 312 (202 + 1) 11) (ab)2/r ((k: + 1)1-9 - - -1 21-9)2/1
(85)
23

---

Published in Transactions on Machine Learning Research (09/2025)
C Korpelevich Method analysis
Lemma C.1. Let U be a closed convex set. Then, for the iterate sequences {uz} and {hr} generated by the 8 and y EU and k 2 0,
stochastic Korpelevich melhod
[1x+1 312 - h1 yl12 - 11k - ux12 -2 (F(s) uu -9) 2nxlek, ux - v) + ( - =(uu)l1++ 37 +|(c21)),
where c/ = (bh; Ett F(hx), of = +(us. + F(u)) for all &20 O.
Proof. Let k 220 be arbitrary but fixed. By the definition of h&+1 (8), we have || yll = PP 7A 2 (uk {E) yll for any y E U. Using the projection inequality, we obtain for any y U,
||++1 - y11 1 like - 7h (uxx ( (2) - y112 |1 - hx + 7x Ouu E2)1
(86)
= l1ke - yl1² - -1 - hx + 27 ( Ek), hR+1).
Next, we consider the term |1x+1 h where we add and subtract ug, thus
|ha+1 12 |1 uxll? 2 + ||4 uxll² 2(hx+11 uk, hy ua)-
(87)
Adding and subtracting 2%x (101k <k), uk - hx41), and combining S6 and 87 we obtain
| -y12 - like y/1² |lhx+1 uxll l 1 2 uk he ux)
+ 27% (77 (T 22, y - ur + us - h1+1) 2n ( <t) + (1iA, [1), ur hx+1) $ 114 yll² - | - uull like ux 2 + 2(hx+1 +1 uk, hx - 7/ Tx (ha, Ett - un)
(88)
+ 2yx (p(uu. (k), y - un) + ( h4. ( (uk: 22), h us)-
Since uh-
Ph vo B1ic, ()) and h8+1 E U, by the projection inequality in 26) it follows that 2(h++1 uk, ha 7x (ha:: (/i ux)
Using Cauchy-Schwaad inequality and relation 2ab S a² + 6² for a, R, we obtain
2%x (T + ((uk: (2), hat1 ux) 2 | (hx (bd - Tuux, 1111 well
S 2 <t o(u, 112 + ||h++I - 1el1
Using triangle inequality and relation
(E a;) v m E a? we get
+t) - (u4 20)
= (10 (t) F(hx) + F(he) - F(ux) + F(ux) - Fuun, 2211 S <3 +1| 2 + 112
Combining the preceding three estimates with 88
get the stated relation
[1a41 2/1 < l4 y/12 - 1hke - w (Fu(F( un 9) 27x un v)
+ ( - =(u))1 +1 [12
C.1 Proof of Lemma 4.1
Proof. By Lemma C.1 we have for all k 2 and for y E U,
1 2/2 < || y/l - lhg - 11 2 2 (F(x)) us - 2nx u4 1)
(89)
+ F3(2) - -F(u))1 + + +122]1))
24

---

Published in Transactions on Machine Learning Research (09/2025)
with c/ @hhg, (t) - F(h)) and o = @uu 2
F(ux) for all & 2 0. We want to estimate the term [(ha)) - F on the RHS of the inequality using the fact that F()) is an a-symmetrie operator for two cases (a) a E (0, and (b) a =1
Case a (0.1). Using the alternative characterization a-symmetric operators from Proposition 2.2 a) (as given 4 when a E (0, 1), the next inequality holds for any k 2 0,
[[((ha) F(ux)ll s I1 ux (Ko (h)l + K2ll/e (x/10/(1-a))
(90)
We want to separate [|F()))] into two parts: stochastic approximation of operator @(h,, { and error el- Recall that e = F(h)) - (1,,, then based on triangle inequality |[F(hs)]] S (1x 4l + ||eb]l. and since a < 1 we obtain
|F(h))]l < (1h,,, + Ie
(91)
Thus, combining this fact with (90 we get the following estimation
[F(h)) F(u))ll S |/x - -u ( + ( 4D1l + Ki Killelll* + 12l/1x - ux (l)))))-))).
(92)
By the projection property 27 and the stepsize choice 16 we have
l1k uxll S 7k / (ha. <b)ll = 3x min [h &l
H1 +2) s Bx 1
(93)
Then, K2llhe ux / K2, and
mh F ((xx) F(ux)ll & Th + (lll@(hs.: <Iil" + K1 Kelle|11" + k2x - uxll
S BBaKK min(1,
Ki min [1+( +t } (1o ( [))1
-ull
[1 ctll|
(94)
+ (x |e2211 K2 min(1.
1)1h - uxll
[1 E/)
$ (Ko K1 + K2)llhe uxll + B& K₁ |1 us Il-
By inequality 93 we have l14e uxll < 1, and using this estimate in equation 94 we obtain
7% (h F(xx)) (Ko + K1 + K2)l( ux!l 8
(95)
Case = 1. Based on the alternative characterization of a-symmetric operators from Proposition 2.2 b) (as
given
16 when a = 1, the following incquality holds for any l: 2 0,
[F(h))) F(w)ll $ ||h ux LI + L, [F(h))) exp(L, |h uxl))
(96)
We upperbound [h+)] using equation 91 and get
(h+) Flux)ll < ||be ux (Lo + ( +1) + L bllckl exp(In 11x uxll).
(97)
Note that relation in 93 holds irrespective of the value of a. Thus, since l| uill 1 1, we have exp(LilI4x uxll) < exp((1 3x), and we obtain
(h))F(b)) F(4)ll S (Lo + L
L (ha: Elll + L [e exp(L1 uill
1 11 uxll
=x min
[ [
+ + L1 3n min
H| (106)/==E))11 111/ uxll
(98)
+ (x min
|1l uxll
[ E
s (xp(L186)3 + In + La Iallet1) uxll-
25

---

Published in Transactions on Machine Learning Research (09/2025)
By incquality 93
we have l|Ae ux 1l $ 1. Using this estimate in 98 further obtain
Tell - F(w))ll S exp(Li + Li)l - ue ex
(99)
Now, we are done with the cases of values. Let
(Ki + K₁ + K2), when a E (0, 1), (x) + I1), when =
() =
(100)
Also, define
a) = K1, when (0,
(101)
(x))(L when 1.
Then, by incquality C a,)² 2 S m Σx= ag for both cases we have
F(ba) F [u=)]l < (3k. ux 2
(102)
Combining preceding inequality with (99 we obtain that for any k 2 0,
hx++1 - y/12 1 hb - y/1 (1 (3kk a) 11
uzll 2 -2% (F(u)) up - y)
(103)
2 (ek up y) (Bx 3) + (1ee |e/b1
Next, we plug y = u², where u² E U is an arbitrary solution and use p-quasi sharpness of the operator F to obtain [|&+1
w²1 -e'+1= l1k u² (1 6,3%
uxl1 - pn U*)
(104)
(e, uk - u²) + ( a))le + (11e21 + 112211))
By the stepsize choice 7 S 3k, thus
|lb+1 - u²112 s | u² 1²1 (1-6 - u211 27x (uk U*)
(105)
(c,, uk - u²) + C. (3.. a) 20 + 331 1122
Since Ex=o 32 < oo, oo, respectively, there exists N 2 O such that the stepsizes satisfy 6.8.Ca (3e, a)2 2 2 and Co Ca a²² [ai (xp()) I ma, 23. Thus, the following inequality holds for any k N,
follows that 3r - O. By definitions of Ca ar) and Ce a)) 1100 and 101
[ha+1 112 s l1, 1²1 2 1llh - 11 pu (ux, 1ik, U²)
(106)
27x (c2 us - -²) + +3332 3:32(1e2211 + ||e||| 2 + 2 max (1,,)]|le 11112
By rearranging the terms, defining us = |// - u² u=1 111 + 1111111-1111- - 11 + 27u (ux U*) and adding, and substituting hh - u + 1rik-/udist ( U²) on the RHS we obtain
1 uk+1 S U/ | 1111112 2 27 1udist (ux-1,U*) pui U*)
(107)
- -2 ux - u²) 3,3 (1le2) 2 || + 2 max ( [1, 2)1e
Recalling that et = (he, (t F(hx), ; o = puu, + F(ux) and using the stochastic properties of Q <2 imposed by Assumption 2.5 and method's updates, we have
Eby (e2. up u²) Fx = E[>x (E(e FR-IU up u²) FR-ill = 0,
since stepsizes 7% measurable F U [ Also, holds that for all l: 2 0,
[ F U ( & and Bllle2ll [ S a²
26

---

Published in Transactions on Machine Learning Research (09/2025)
Moreover, since I 1, the conditional expectation B[[le] 20 [Fk-1] is finite, and by Jensen incquality, it follows that for all k 2 0,
1al S 2
Therefore, by taking the conditional expectation on Fk-1 in relation 107 we obtain for all u E U and for k 2 N,
E Elve+1
[ < uk - 2 11 - ux|1 2pm dist (wx; U*)
(108)
+ 6,% (o² + max (K1, 2)02a).
By Lemma A.2 it follows that the sequence {llh un }1?} converges to non-negative scalar for any a² E U*, and almost surely we have
udist (uz, (udist U*) < 00,
Σ
114 uxll
(109)
k=0
km0
Since the sequence {|] u 3=]] converges a.s. for all w" U it follows that the sequence {1l u"|l) is bounded a.s. for all u² E U
||
C.2 Proof of Theoreom 4.2
Lemma C.2, The stepsizes "ik are given by 16 are nonsummable almost surely,
0 a.s.
(110)
k=
Proof. We will show that Ex= Bx min {I, [+ch,,
] almost surely by the sequences of lower bound
on this series. Consider the Tollowing event:
A
fllefll 20),
where oj @hhr, ( F(hx) is stochastic error from the sample for the clipping stepsize %i- Define min (1, [othn
then,
IK xxI(AA) + +zx((Ax)) xxI(As),
(111)
where the random variable I(AA)) the indicator function of the event Aş taking value 1 when the event occurs, and taking value 0 otherwise.
By the definition of zg. the triangle inequality and definition of I(Aa), we have
xxl((As) min
I(ARR)
min
1.
I(As))
[P(hk)]] + +lleg] ||
1
min
I(An).
[F(hx)]] + 20
(112)
Adding and subtracting B[T( [x) and combining 111 112
we have the following lower bound
Σ
BRok
3r min
F(h)]l + 2x (T(Ax) E[T(AA)
0=0
k=0
Br min
I B[[(Aa)]Fx-I]
(113)
[[(hk)]] +
k=0
27

---

Published in Transactions on Machine Learning Research (09/2025)
To bound Ph := F 1 FR-1) provide upperbound on P(Aş Fk-1) using Markov's
inequality and Assumption 2.5
E Bllee Fk
P(As Fk-1) = P([e 2B|l|e||| [F--1))) -
(114)
2E || FR-1]) 2
This implics martingale:
2 2. Define S, = EEk= P (I(AA
by construction, {Sa} ] is a
11 So: :o:...;;mn] Sm]
Sn, + BlBa+1 1 (I(An+1) BA 1)F SS -....., Sn) Sn.
We want to show that limm- Sn + S < oc almost surely. We provide an upper bound for E[S.]::
(T(A)( +
Σ
(E Px)(T(AA) -P:)l
(115)
aSkciιn
By the law of total expectation,and noting that E[[(A)) Pk Fk-1] for any k, we find that for all 0 <isn,
[[(T(A)) P)a)(((A))) pc)] = ([(((A.) PI(TTA( pb)) Fi-1l] = =0
(116)
implying that, for all n 2 0,
E|SA Σ RE(I(L(A)) P&)
(117)
Since [[(](As) - 1 Var(((As) FR-1) and the random variable I(Ax) is a Bernoulli given Fk-1 with mean Pk. its variance cannot exceed 1/4, i.c.,
1
B[[[(A+) - -Px)2 Fx = Var(I(Au) Fi-1) S
By taking the total expectation we get ([(((Aa) - pp)) S 2 and combining the preceding two relations, we obtain
n
B
3 50.
From Theorem 4.4.6. in Durrett (2019) it follows that Sn converges to S almost surely.
To further lower bound IxA((A)) we show a.s. boundedness of [[F(h))] for all k 2 0, using property of a-symmetric operators. To estimate [[(hh)]], we add and subtract F(o"), where v" E U an arbitrary but
fixed solution, and get
(((h))l=[[F(ha))) -(6( [F(ha)) 1 -(0)))
Define the following event:
ER A = tw EΩ: 3(w)) E R s.t.)//x(()) - 0' < c(w) A 0}.
Based on Lemma 4.1 the sequence {llie I1I bounded a.s., and thus P(A) 1. Let E A, now we can estimate (1)()(()) using the a-symmetric assumption the operator.
Case 1).
[[((hx F(w")] S (1)) - V'] + K( - -"'
(118)
Since ws A, follows that [[h((w) - w²1l S C(w) for all 2 Using this fact and 118) we obtain that for all & >
[F(h(w))] (K))(Ko 11 ((C(w)/(U-o)) + [[
(119)
28

---

Published in Transactions on Machine Learning Research (09/2025)
Therefore, the sequence K2C(w))/(1=a)) [[F()))|
(1))() is upper bounded by (i(w) C(W)(Ko + K]]I(("']] +
Case = 1. For a = by Proposition 2.2 we have
[[((n(()) F(v")l S -
- v²))).
(120)
Therefore, for all 0,
[1((h(w))]] < [[F(h)(w)) F(v))(")) [1]))
$ [l)((w)) v² (Lo + (1 exp(Lillbx(w) -²ll) + [F(**)]
(121)
Since w E A, we have [[Nx(w) - w0 s ((w) for all k 2 0, which when used in 121 implies that for all A: 2
0,
[P((h(W))]] & (w) - o" 2011(L0 (xx) exp + [F(x")]
w0 [F((")]
S ((w) +
(122)
Hence, the sequence (w)) is upper bounded by Ci(w), where Ci(w) CLw)(Lo +
L [I|F((*)II exp(LIC(w)) + [[]())]] Now, for both cases a (0, 1) and 1 in 1119 and 122 re-
spectively, we have that (w))) is upper bounded by max (w)) (iw)) Thus
P([F(h:) is bounded) 1.
Thus, almost surely we have (i) (F(h)) is bounded, (ii El 3y (T(AK) E[T(AA)) Fk-1l) converges
S < oo as + 00, and (iii) [[a(A)))FFaD)) 2 1. Now, consider ll such that (i), (ii), and (iii) hold, then
in view of 113
have
Σ (w) 2 min { Ci(w) 20 } S(w) + min {1, (w(w) 20
By = 00,
(123)
k=
where the last equality comes from Ee=p Br = co, which concludes the proof.
Proof of Theorem 4.2
Proof. By Lemma
we almost surely have
diss (ux, U*) < oc.
(124)
By Lemma C.2 we have Ex 7/k 00 almost surely, than from 124 it follows that
lim inf dist (ux, U*) = a.s. k
(125)
By Lemma 4.1 the sequence [[he - u ||} converges a.s. for any given u² E U Thus, the sequence (h+] } is bounded a.s. and, consequently, it has accumulation points a.s. In view of relation 200 in Lemma 4.1 it follows that.
lim lik 10000
ux
a.s.
(126)
Therefore, the sequences {mx} and (1x have the same accumulation points a.s.
Now, let (k: i 2 13 be (random) index sequence such that
lim dist (uk,, U*) lim inf dist (ux, U²)
a.s.
(127)
1-000
k-000
29

---

Published in Transactions on Machine Learning Research (09/2025)
Without loss of generality, we may assume that (hk,} } is convergent sequence (for otherwise, we will select convergent subsequence), and let it be its (random) limit point, i.e.,
lim |/x, - ūl =0 a.s. 100
(128)
By relation 20 it follows that limg- 1xx that
Up
0 a.s., which in view of the preceding relation implies
lim 12 al = 0 a.s.
20000
By continuity of the distance function dist(,,U') from relation 127 we conclude that dist( U*) a.S., which implies that U* almost surely since the set U is closed. Since the sequence {[] - u" || converges a.s. for any u" U*, it follows that lim lIfe ull 0 a.s. By relation (126) conclude that
limg-+20 | Tl = 0 a.s.
C.3 Proof of Lemma 4.3
Proof.
The choice of parameters 3x. ensures that 1 - 1-63g Ku + K Ks)² 2 1/2. Then, by taking the
expectation in 19 of Lemma 4.1 and using Assumption 2.5 and definition of Ce o) = Kı for a E (0,1),
we obtain
E /1 - u [11]]] S El u² =='1
Bllla uxll 2 (ux, U*)
2
(129)
+ 636(0² + kl)2a).
The equation
129 satisfies the condition of Lemma
A.3 with
2 Ellluk =2'131, ag 0, by 6,3 + k)
Σn = 2/TE/7e dist (us, U*) + 2 Elll/x - us 1x.
(130)
By Lemma A.2
follows that the sequence Ei[ih - uz 1²] converges a non-negative scalar for any u" E U
Since the sequence [E[l) - 1²] converges for all u² U*, follows that the sequence {IE[I] - [|]]] is bounded for all u² E U Next, using property of a-symmetric operators, show that ((() II] is bounded for all & 2 0. Let o- U* be arbitrary but fixed solution. Since 1/2, it holds that
[F(h))] < [F(h)) - - [F(")||
(131)
< 1/4 - =0 + K2 F('))] + Kell4 -0110/000a) [[F("")]
Taking the expectation, we obtain
E[]]F()))ll < (Ko + K, [[ w0ll
K2Ellhe 0011tt/(1-0))) [[F("))]
(132)
Notice that Elilhg- =² (1| [[ 0* 113))) and, for 1/2, the quantity 1/2(1 a) s 1.
Thus, we can apply Jensen inequality for concave function
B[ - u -13))//(000011 < E[llaa- - -11111/2((1-))
Therefore, using the preceding relation and Jensen inequality for the first term the RHS of equation 132 we obtain
[h]lF(h))ll < (Ko + K1 (o]l - o "131/// K2Blllh, - -117)/20000) + +IF((*)]I
(133)
Since Elli w- [12] bounded, follows that (hb))( is bounded by some constant Cf for all
k > 0.
30

---

Published in Transactions on Machine Learning Research (09/2025)
C.4 Proof of Theorem 4.4
Proof. The choice of the parameters 3y ensures that 1 1-635 + +K1+KK+t +x2+ ? 2 2.2 then by letting u² Pu (hx)
in 106 in the proof of Lemma 4.1 with C. (3 a)) K1, we get.
||+++1 Pu- (Ia) < dist (hs, U*) 2 l/ uxll2 - 27 (ux, U*)
(134)
y* (c Uk u²) 3.ee 12 ||_2|| + 2K 12a)
By the definition of the distance function, we have
dist (hx+1, U*) S hx+11 - Py- (hx))l
Thus,
dist (hx+, S dist (hst U*) |1: - -ux12 PrauuissP((u,, U*)
(135)
27 (e -u") + (1 + ||+||| + 2K 1122
Next, we estimate the term dist" U*) in 135 By the triangle inoquality, we have
1 u² Uu hill
| =='l for all u² EU",
and by taking the minimum over o² E U on both sides of the preceding relation, we obtain
dist U*) S l hall + dist(ux, U*).
(136)
Applying Lemma A.5 with p > in equation 136) yields
dist (h,, U*)
I [Uk hg + dist(u,,
(137)
< 2P- 1 hall + 2n dist Dust"(uk,1) U*).
Using projection inequality 27 and stepsizes choice 16
we obtain
Iu hall S |l (1x, 41) s 1.
Combining this result with equation 137 with 2 2, we gel
dist? (hu, U*) < 2 llus - 14 2+ (-(()2) + 20- (uk, U*)
(138)
< 2
I|ux - hu 1| + 20-1
U*).
By dividing the relation in 138 with 2p-1 and by rearranging the terms, we obtain the following relation
dist (un, U*) < uu hwll2 - 22-P dist" (ha, U*).
(139)
Combining the preceding inequality with 135 find that for any & 2 0,
dist (ha+1, U*) S dist (hu,, U*) - 22 pr U*) || hell2 + 24rre ||ux hvell
(140)
27 (e us u²) 3,3 ||e2|1 + 2Ki aikilee, 2aa)
2
where a = l pmin {1 2(( } and d 2 4p. Thus, for all k: 2 0,
By the choice of 8e, we have Br
a
2d + k))
1
248x S 1
1
3x <
<
d
4p
2
31

---

Published in Transactions on Machine Learning Research (09/2025)
By the definition of the stepsize Yk, we always have 7A S Bg. Therefore, 2pr0x - 24Bx I 1/2 for all & 0, thus implying that.
2 lluk hss 2 + 2pry 11ue - hxll2 S..
(141)
Using the stochastic properties of Ea imposed by Assumption 2.5 we have for all A 2 0,
[ uu u²) U U (EgH) F=-1l]=0 =0;
E E F (1 S o²: [[ [e-ill
(142)
Moreover, since a S 1 then the conditional expectation 2| is defined, and by Jensen inequality Elllet [ [x-]] I 20 for all & 2 0. Thus, by taking the total expectation in relation 140) and using an
estimate from 141 we obtain for all u² E U* and for all 2 0,
Eldist (ha+1, < E[dist((hss U*]] 1 "uE=ppiisdstt (he, + + Kio2a).
(143)
The equation [43) is similar to equation 72 in the proof of Theorem
3.4
with the same stepsize structure.
Thus, by following the same arguments from equations arrive at
72 to equation
78 in the proof of Theorem 3.4 we
(hx+1; U[)] s E[dist 2 (1x: U*]] - 22-P PBB min {
2(Cr +o)
Eldist" (he, U*)]
(144)
+ (, + Kio2a),
where CF is an upperbound on E[]| F()))))))))))) from the statement of Lemma 4.3 Now let Dx = E[dist (hg. U*)] and consider two cases and p > 2. Case
We note that by the definition of pmmin (1, 2[C++o] j and d, we have that d 2 4 and 2 a, implying that d 2 a. Hence, for 2, relation 144) satisfics the conditions of Lemma A.6 with the following identification
1 2(CF }
Th Dj, min
ag Bk, 8k = 0, c= 6(2² + K))2n).
(145)
2
Therefore, for the choice By
get the following convergence rate for all k > 1,
al? 2d + +k)
8d Do
12 + 2))
D441 S
(146)
R²k2
a²k
Case p 2. When p2 2, by applying telescoping sum to inequality [44 and rearranging the terms obtain
k
B222
a
Bgdist (ha,stt"hux,"")) < Do DR+I + 6(02 + KKo2ay
k-
(147)
1=
1=
Since p 2 2, the function dist"(., U²) is convex, thus by defining un (Eto 3x) Ek Sahe and applying Jensen incquality be obtain
Bd)ss (he, U³) < By (hR. U*)]
Since p 2 2, by applying Jenson incquality one more time, we obtain
(Dx)/22 -EEddist" 2 (hr. U+)) < [dist p22) (hx,st)(hx.UU))
32

---

Published in Transactions on Machine Learning Research (09/2025)
R
2m)) < Do Do- Dx+1 + 6(o² + K Σh $2
(Dx)p/2
Σ t=0
B
B.(D))pi
(148)
22-Pa
t=0
Now, we use the choice for Bk, ie., Pk (k+1)e: where 0 < b <
2/3(Kn K +Ka] and 1/2 q < 1. Then, the
sequence {Px satisfies the conditions of Lemma 4.3 Furthermore, by Lemma A.7
we have that for all k 2 1,
b ④
6²
Σ
3
((k: 1)_-4 -2 9)
Σ
(149)
2g
Combining equations 148 and
149 and omitting D we obtain for all
1,
2D 21 4) (Do + 6b2 + (20 + 1)/(2q 1)) ab ((k + 1) 2!
(D&)p/2 S
(150)
Raising both sides of the preceding incquality in power 2/p, we have that for all 2 1,
DR 22 2)/p(1 2/2 (Do + (b² + 11o20 + 1)/ /3/r (ab)2/v / ((I: + 1)1-9 v 21-0)
(151)
D Additional Experiments
We investigate the robustness of the methods for larger choice of the initial parameter value Sg. In Figure 5 we set = and corresponding $s = 10+Ai-e, so the initial stepsize 3o x 5 and run all four methods for the same problem parameter choice. We observe that for a generalized smooth SVI when we increase stepsizes, the performance of clipped stochastic Popov and Korpelevich comparable that of both clippod stochastic versions. While in smooth SVI, the stepsizes for stochastic Korplevich and Popov methods can be much larger than for stochastic projection methods, improving the convergence performance of stochastic Korplevich and Popov methods.
Gorverpence
Convergence
Convergence
Projet ot
Injject on
Pepax Merphksch
Kapelooch
Keracizcch
(a 0.09. 2.5)
(b) (a Rd 0.5,p= 3.0)
(c) (a 0.8, 6.0)
Figure 5: Comparison of the clipped stochastic projection, samc-sample projection, Korpelevich, and Popov methods with B = 50/(10 (10- + k² 1--)).
33


Reviews:
[{"review_id": "6BQ1R17O0N", "reviewer": "Reviewer_tt4P", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "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": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors proposed two methods to solve the stochastic variational inequality problem under relaxed smoothness assumption for a class of structured non-monotone operators. The contributions are summarized below:\n\n1. The authors provided the first known analysis of the clipped stochastic clipped projection method for solving stochastic generalized smooth variational inequality problems with p-quasi sharp and α-symmetric operators. They proved the convergence rate of this clipped stochastic clipped projection method.\n\n2. The authors provided the first known analysis of the stochastic clipped Korpelevich method for solving stochastic generalized smooth variational inequality problems with p-quasi sharp and α-symmetric operators. They proved the convergence rate of this stochastic clipped Korpelevich method.\n\n3. The authors conducted numerical experiments and the empirical results are consistent with the theoretical analysis.\n\nOverall, this submission has some meaningful contributions in term of the optimization theory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors provided all the technical lemmas and theoretical proof for all the propositions and theorems of this submission in the appendix. These mathematical proof is correct. Moreover, the authors also conduct multiple numerical experiments and the empirical results are consistent with the theoretical analysis.", "audience_yn": "Yes", "audience_explanation": "This submission provides some interesting theoretical convergence analysis of two different methods regarding solving the stochastic variational inequality problem under relaxed smoothness assumption. The convergence results are summarized in table 1. The stochastic variational inequality problem has attracted significant interest in the machine learning community due to its immediate application to adversarial training and multi-agent reinforcement learning. Therefore, this submission has some interesting contributions to the optimization and machine learning community.", "requested_changes": "Here is request changes:\n\n1. Please add more detailed explanations about the stochastic variants of projection method and Korpelevich method before Assumption 2.5 in section 2.\n\n2. One limitation of this submission is that all theoretical results only apply to the case of $\\alpha \\leq \\frac{1}{2}$. The authors list the case for $\\alpha > \\frac{1}{2}$ as future direction. It is better to explain more about why the current analysis failed for the case of $\\alpha \\leq \\frac{1}{2}$.\n\n3. Another limitation of this submission is that the authors only proved the non-asymptotic convergence rates under the case of $p \\geq 2$. When $p < 2$, there are only asymptotic convergence results. It is better to explain more about why it is difficult to prove the non-asymptotic results when $p < 2$\n\n4. In the numerical experiments, it is better to add the results for the case of projection to some closed set $U$ that is not $R^d$. The current results are only unconstrained optimization problem. It is better to add some results about the constrained projection method.\n\n5. In the numerical experiments, there are only results for $p > 2$. It is better to add the results for the case $p < 2$ to check if it can still reach the converence.", "broader_impact_concerns": "No ethical impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6rwUZgjpbc", "reviewer": "Reviewer_1mwa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "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": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates stochastic variational inequalities (SVIs) with **\\$p\\$-quasi-sharp, \\$\\alpha\\$-symmetric operators**, a class that relaxes the classical assumptions of strong monotonicity and Lipschitz smoothness. Unlike much of the existing literature, the analysis here does not require bounded stochastic operators or bounded samples. The authors study two clipped methods—**the clipped stochastic projection method (clipped SGDA)** and **the stochastic clipped Korpelevich method**—and establish, for the first time, their **almost sure convergence** for solving SVIs with \\$p\\$-quasi-sharp and \\$\\alpha\\$-symmetric operators. A key innovation lies in the **two-sample clipping strategy** for the projection method, which eliminates bias from stochastic stepsizes. Building on this, the authors further derive **in-expectation convergence rates** for the case \\$\\alpha \\le 1/2\\$:\n\n1. For \\$p = 2\\$: \\$O(1/k)\\$ convergence.\n2. For \\$p > 2\\$: \\$O(k^{-2(1-q)/p})\\$ convergence, with \\$1/2 < q < 1\\$.\n\nThe theoretical analysis is further supported by **numerical experiments**.\n\n### Strengths\n\n1. The paper is logically clear, establishing almost sure convergence for two clipped methods and providing explicit convergence rates.\n2. The main contribution lies in proving convergence under more relaxed assumptions, notably removing the boundedness requirements for stochastic operators or samples, and weakening the smoothness and strong monotonicity assumptions.\n3. By employing carefully chosen stepsizes \\${\\gamma\\_k}\\$ in the stochastic clipped projection method, the inherent bias of clipped SGD observed in \\[1] is avoided.\n4. For \\$p\\$-quasi-sharp operators (\\$p=2\\$), the convergence rates in Theorems 3.4 and 4.4 align with those in Theorem 4.3 of \\[2] and Proposition 5 of \\[3], respectively. For \\$p>2\\$, this paper establishes the best known convergence rates for both clipped methods.\n\n### Weaknesses\n\n1. It is not entirely clear whether the clipped SGDA with the proposed two-sample clipping strategy is novel. If it is indeed original, a more detailed comparison with the vanilla clipped SGDA is recommended; otherwise, further clarification is needed.\n2. The convergence results are established only for \\$\\alpha\\$-symmetric operators with \\$\\alpha \\in (0, 1/2]\\$, meaning that the analysis does not recover the standard \\$(L\\_0, L\\_1)\\$-smoothness case (\\$\\alpha=1, \\theta=1\\$).\n3. There is an issue in the statement and proof of Lemma 4.1: \\$u\\_k\\$ is not measurable with respect to \\$\\mathcal{F}\\_{k-1}\\$.\n4. The statement and proof of Theorem 4.4 appear inconsistent.\n5. The numerical experiments provide only partial validation of the theoretical results and could be strengthened.\n6. Several typos need correction.\n\nFor more detailed comments, please refer to Section **Are the claims ... accurate, ...** and Section **Additional Comments**.\n\n\\[1] Koloskova, A., Hendrikx, H., & Stich, S. U. (2023, July). Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In *International Conference on Machine Learning* (pp. 17343–17363). PMLR.\n\n\\[2] Loizou, N., Berard, H., Gidel, G., Mitliagkas, I., & Lacoste-Julien, S. (2021). 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.\n\n\\[3] Kannan, A., & Shanbhag, U. V. (2019). Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants. *Computational Optimization and Applications, 74*(3), 779–820.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Overall, most of the claims are well supported, but several points require further clarification and revision.\n\n1. For **Lemma 4.1**, the right-hand side of the stated inequality involves two terms containing \\$u\\_k\\$. However, recalling the update rule of the stochastic Korpelevich method in (8), \\$u\\_k\\$ is not measurable with respect to \\$\\mathcal{F}\\_{k-1}\\$. Hence, the correct form should be\n\n   $$\n   \\frac{1}{2}\\mathbb{E}[\\\\|h\\_k - u\\_k\\\\|^2 \\mid \\mathcal{F}\\_{k-1}] - 2\\mu \\mathbb{E}[\\gamma\\_k \\, {\\rm dist}^p(u\\_k,U^*) \\mid \\mathcal{F}\\_{k-1}],\n   $$\n\n   instead of\n\n   $$\n   \\frac{1}{2}\\\\|h_k - u_k\\\\|^2 - 2\\mu \\mathbb{E}[\\gamma_k \\mid \\mathcal{F}_{k-1}] {\\rm dist}^p(u_k,U^*).\n   $$\n\n   Therefore, the proofs of Lemmas and Theorems in Section 4 should be carefully revised.\n\n2. In **Theorem 4.4**, the authors define $\\bar{u}\\_k = (\\sum^k_{t=1}\\beta\\_t)^{-1}\\sum^k\\_{t=0}\\beta\\_tu\\_t$ and state that they establish an upper bound for $\\bar{D}\\_k=\\mathbb{E}[{\\rm dist}^2(\\bar{u}\\_k,U^\\*)]$. However, in the proof, only an upper bound for $D\\_{k}^{\\rm best} = \\min_{t\\in[0,k]}D\\_t$ is actually derived. This mismatch between the theorem statement and the proof requires correction.\n\n3. Regarding the **clipped projection method**, the authors claim that their two-sample clipping strategy removes the bias from stochastic stepsizes. While the paper notes that this requires two oracle calls per iteration, it does not provide sufficient discussion on whether this additional cost is justified. More explanation is needed, especially because although the strategy theoretically eliminates bias without changing the convergence rate, the numerical experiments show little practical advantage, that is, **Projection** method and **Projection-Same** method perform similarly.\n\n4. Concerning the **assumptions**, the authors claim that their results are established under relaxed smoothness assumptions. However, all convergence results hold only for \\$\\alpha \\in (0, 1/2]\\$. When \\$\\alpha = 1\\$, the \\$\\alpha\\$-symmetric condition corresponds to the standard \\$(L\\_0,L\\_1)\\$-smoothness \\[1]. Thus, the analysis here does not recover this classical case, and the scope of the claimed relaxation should be made clearer.\n\n\\[1] Zhang, J., He, T., Sra, S., & Jadbabaie, A. *Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity*. In International Conference on Learning Representations.", "audience_yn": "Yes", "audience_explanation": "Yes.\n\n1. This paper introduces a new paradigm for analyzing almost sure (a.s.) convergence and convergence rates of algorithms under generalized smoothness assumptions, i.e., based on \\$p\\$-quasi sharpness and \\$\\alpha\\$-symmetric assumptions, while removing the restrictive assumptions of bounded stochastic operators and bounded samples.\n2. It proposes a two-sample clipping strategy, demonstrating that the bias inherent in one-sample clipped SGD can be eliminated.\n3. The paper derives the best known convergence rates for clipped methods under the \\$p\\$-quasi sharpness assumption (\\$p>2\\$), namely \\$O(k^{-2(1-q)/p})\\$, with \\$1/2 < q < 1\\$.", "requested_changes": "1. Recheck and revise the proofs in Section 4 as indicated in Section **Are the claims ... accurate, ...**.\n2. Clarify the originality of the two-sample clipping strategy and discuss its pros and cons:\n\n   1. In Section 3, make a detailed comparison and explain why this strategy is preferable and why it does not affect the convergence rate.\n   2. In Section 5, clarify why this strategy does not outperform the vanilla clipped projection method in practice.\n3. Provide a more detailed discussion on the assumptions:\n\n   1. For \\$p\\$-quasi sharpness: include several concrete examples of operators satisfying this assumption.\n   2. For \\$\\alpha\\$-symmetry: explain why Theorems 3.4 and 4.4 exclude the case \\$\\alpha=1\\$.\n   3. Discuss whether the methods still converge without \\$p\\$-quasi sharpness or \\$\\alpha\\$-symmetry. (For example, under the \\$(L\\_0, L\\_1)\\$-smoothness assumption, it seems that removing \\$p\\$-quasi sharpness may still allow convergence.)\n   4. Provide a more comprehensive introduction to the assumptions themselves: give explicit examples that satisfy these relaxed assumptions, explain how they differ from and relate to the commonly used assumptions in the literature, and briefly justify the necessity of introducing these two assumptions in this work.\n4. Review and correct the typos mentioned in Section **Additional Comments**.", "broader_impact_concerns": "No ethical issues are apparent, and the current scope of the work does not necessitate a Broader Impact Statement.", "additional_comments": "Some typos:\n1. P2, Contributions 1: \"clipped stochastic clipped projection method\" $\\rightarrow$ \"clipped stochastic projection method\".\n2. P3, before Eq. (2): \"F is $(L_0,L_1)$-smooth\" $\\rightarrow$ \"F is $\\alpha$-symmetric\".\n3. P6, after Theorem 3.2: \"$\\mathbb{E}\\_{\\xi}[\\beta_k\\min\\\\{1, \\frac{c}{\\|\\nabla\\_{\\xi}f(\\hat{v})\\|}\\\\}] = \\hat{v}$\" $\\rightarrow$ \"$\\mathbb{E}\\_{\\xi}[\\beta_k\\min\\\\{1, \\frac{c}{\\|\\nabla\\_{\\xi}f(\\hat{v})\\|}\\\\}\\hat{v}] = 0$\".\n4. P6, after Theorem 3.2: \"$C>0$\" $\\rightarrow$ \"$c>0$\".\n5. P13, Lemma A.4: \"$\\mathbb{P}(X>a(\\mathbb{E}[X^{\\rho}])^{1/\\rho}$\" $\\rightarrow$ \"$\\mathbb{P}(X>a(\\mathbb{E}[X^{\\rho}])^{1/\\rho})$\".\n6. P16, Eq. (45): \"$\\mathbb{P}(\\\\|e\\_k\\\\|>2\\mathbb{E}[\\\\|e^2\\_k\\\\||\\mathcal{F}\\_{k-1}])$\" $\\rightarrow$ \"$\\mathbb{P}(\\\\|e^2\\_k\\\\|>2\\mathbb{E}[\\\\|e^2\\_k\\\\||\\mathcal{F}\\_{k-1}])$\".\n7. P17, before Eq. (50): \"$A=\\{ \\omega\\in\\Omega ...\\}$\" $\\rightarrow$ define $\\Omega$ first.\n8. P17, Eq. (50): \"$\\\\|F(u\\_k(\\omega)) - F(u^\\*)\\\\|$\" $\\rightarrow$ \"$\\\\|F(u\\_k(\\omega)) - F(v^\\*)\\\\|$\".\n9. P18, before Eq. (58): \"Due to $\\mathbb{E}[\\gamma\\_k|\\mathcal{F}\\_{k-1}] = \\infty$\" $\\rightarrow$ \"Due to $\\sum^{\\infty}\\_{k=0}\\mathbb{E}[\\gamma\\_k|\\mathcal{F}\\_{k-1}] = \\infty$\".\n10. P21, Eq. (84): \"$... \\leq ... \\leq ...$\" $\\rightarrow$ \"$... \\leq ... = ...$\"\n11. P22, after Eq. (87): \"We want to estimate the term $\\\\|F(h\\_k) - F(h\\_{k-1})\\\\|^2$ on the LHS ...\" $\\rightarrow$ \"We want to estimate the term $\\\\|F(h\\_k) - F(u\\_k)\\\\|^2$ on the RHS ...\"\n12. P22, after Eq. (88): \"Recall that $e^1_k=F(h\\_k)-\\Phi(h\\_k,\\xi^1\\_k)$\" $\\rightarrow$ \"Recall that $e^1\\_k=\\Phi(h\\_k,\\xi^1\\_k)-F(h\\_k)$\"\n13. P23, Eq. (94): \"$... \\leq ...(L\\_0+L\\_1\\\\|\\Phi(h\\_k,\\xi^1\\_k)\\\\|)...$\" $\\rightarrow$$... \\leq ...(L\\_0+L\\_1\\\\|F(h\\_k)\\\\|)...$\"\n14. P23, Eq. (95): \"$... \\leq ...(L\\_0+L\\_1\\\\|F(h\\_k)\\\\|+L\\_1\\\\|e^1\\_k\\\\|)...$\" $\\rightarrow$ \"$... \\leq ...(L\\_0+L\\_1\\\\|\\Phi(h\\_k,\\xi^1\\_k)\\\\|+L\\_1\\\\|e^1\\_k\\\\|)...$\"\n15. P24, before Eq. (104): \"$...\\leq\\max\\{K\\_1,\\exp(L\\_1,\\beta\\_k)\\}\\leq...$\" $\\rightarrow$ \"$...\\leq\\max\\{K\\_1,\\exp(L\\_1\\beta_k)\\}\\leq...$\"\n16. P24, Eq. (108) \" $\\sum^{\\infty}_{k=0}\\mathbb{E}[\\gamma\\_k|\\mathbb{F}\\_{k-1}] = \\infty$\" $\\rightarrow$ \" $\\sum^{\\infty}\\_{k=0}\\mathbb{E}[\\gamma\\_k|\\mathcal{F}\\_{k-1}] = \\infty$\"\n17. P25, Eq. (112) \"$\\\\|\\Phi(h\\_k,\\xi^2\\_k)\\\\|$\" $\\rightarrow$ \"$\\\\|\\Phi(h\\_k,\\xi^1\\_k)\\\\|$\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "k5H3sJsg7l", "reviewer": "Reviewer_xXpU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "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": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents convergence analysis for two stochastic methods for generalized smooth variational inequalities. The paper considers a generalized smoothness assumption called the $\\alpha$-symmetric condition and a $p$-quasi sharpness condition, which means that the distance from the solution set can be controlled by the dot product between the operator and the direction to the solution set. The paper establishes both almost sure convergence and the convergence rate for both two stochastic methods. Experimental results are also reported to verify the theoretical findings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper develops the first almost sure convergence for variational problems associated with a\u000b-symmetric and p-quasi-sharp operators. The problem class considered in the paper is very general and includes many existing problems as special cases. The paper considers clipped step sizes which are stochastic. These stochastic stepsizes make the analysis challenging. The theoretical analyses are conducted without assumptions on the boundedness of iterates, which are often imposed in the existing studies. In particular, the paper shows that these iterates are bounded almost surely, which is also interesting in its own since it shows the algorithm is somewhat stable.", "audience_yn": "Yes", "audience_explanation": "The paper considers stochastic optimization algorithms for variational inequalities, which cover many practical problems such as optimization, min-max problems, multi-agent games and GANs. The paper introduces several techniques to establish the first almost sure convergence of clipped methods, which have the potential to be applied to other stochastic optimization algorithms. The generalized smoothness assumption considered in the paper also attracts a growing interest in the community.", "requested_changes": "- Eq (2) and Eq (3) look almost the same. However, Eq (2) is called the $(L_0,L_1)$-smoothness, while Eq (3) is called $\\alpha$-symmetric. It would be beneficial if the authors can clarify the difference. \n\n- While the convergence rate in Theorem 3.4 shows the rate of order $O(1/k)$, the dependency w.r.t. the parameter $\\mu$ is $1/\\mu^2$. It is not clear to me whether this dependency on $\\mu$ is optimal. Note that in the standard minimization problem with strongly convex conditions, the optimal rate should be $1/(\\mu k)$. It would be interesting if the authors can add some discussions here. \n\n- The paper considers two methods: project method and Korpelevich method. According to theoretical analysis, these two methods seem to have similar behavior. Both of them converge almost surely, and have similar convergence rate in expectation. It would be interesting to clarify the advantage of one method as compared to the other.\n\n- For the convergence rate in expectation, the paper considers the convergence of the last iterate in the case $p=2$, and the convergence of an average iterate in the case $p>2$. It is not clear to me why the paper has different choices of iterates in these two cases. Some discussions would be beneficial.\n\n- The paper considers the p-quasi sharpness property. It would be interesting to give some examples for which this condition holds. \n\nMinor changes\n- Introduction: \"stochastic variation inequality\" should be \"stochastic variational inequality\"\n- Eq (30): there is a missing \")\"\n- Above Eq (49): \"holds dues to\" should be \"holds due to\"\n- Below Eq (65): there is an additional \")\" \n- Below (78): \", By applying\" should be \", by applying\"\n- Above (97): \"furher\" should be \"further\"", "broader_impact_concerns": "I do not see broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)