Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates

## Abstract

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 the generalized smoothness assumption and consider two well-known stochastic methods with clipping, namely, projection and Korpelevich. 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. Furthermore, we provide the first in-expectation convergence rate results for these methods under a relaxed smoothness assumption.

## 1 Introduction

This paper focuses on the stochastic variation inequality (SVI) problem, which consists of finding a point $u^{*}\in U$, such that

$$ $\langle F(u^{*}),u-u^{*}\rangle\geq 0\qquad\text{for all }u\in U,$ $$

where the operator $F(\cdot)$ is specified as the expected value of a stochastic operator $\Phi(\cdot,\cdot):U\times\Xi\rightarrow\mathbb{R}^{m}$, i.e.,

$$ $F(u)=\mathbb{E}[\Phi(u,\xi)]\qquad\hbox{for all }u\in U,$ $$

where $\xi\in\Xi$ is a random vector.
Variational Inequality (VI) problems encompass many practical applications, such as optimization, min-max problems, and multi-agent games. In particular, they play a vital role in modeling equilibrium problems where it’s important to capture an interaction between many agents. In machine learning literature, the increasing focus on VIs is due to their relevance to generative adversarial networks (GANs) Gemp and Mahadevan (); Gidel et al. (), actor-critic methods Pfau and Vinyals (), adversarial training, and multi-agent reinforcement learning Sokota et al. (); Kotsalis et al. ().
In many such applications, the corresponding operator is defined as an expected value of stochastic or finite sum of operators, which motivates us to study SVIs.
One of the pivotal works Nemirovski (); Juditsky et al. () on SVIs proposed and studied the celebrated Mirror-Prox method under assumptions on monotonicity and Lipschitz continuity of an operator.(^1^11The well-studied Mirror-Prox method Nemirovski () has been proven to be optimal for solving VIs under strong monotonicity and Lipschitz continuity assumptions. In fact, this method is the stochastic version of the classical extragradient method.) These assumptions become classical for the analysis of first-order methods for solving SVIs Beznosikov et al. (); Hsieh et al. (, ); Loizou et al. ().

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. This effect might be explained by the experiment conducted in Zhang et al. (). In this work, authors observed that when training deep neural network, the norm of the hessian of the loss function correlates with a norm of a gradient along the optimization trajectory.

This observation motivated Zhang et al. () 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 investigating new assumptions on generalized smoothness and convergence behavior of classical gradient Li et al. (), normalizedChen et al. (), clipped Koloskova et al. (), and adaptive methods . Despite this progress in optimization, there are only a few works on generalized smooth min-max Xian et al. () and VI (Vankov et al., ) problems. This motivates us to delve into investigation of first-order methods for generalized smooth SVIs.

### 1.1 Related Work

Weaker Assumption on SVIs
More work has focused on stochastic methods for SVI under more relaxed assumptions to develop and analyze the methods applicable to broader problem classes. In particular, some studies have explored SVIs under pseudo-monotonicity Kannan and Shanbhag (), quasi-monotonicity Loizou et al. (), co-coercivity Beznosikov et al. () and quasi-sharpness Vankov et al. (). Diakonikolas et al. () showed that such conditions may not be satisfied even in two played Markov games and introduced the weakest known structured non-monotone assumption. Later, weak Minty SVIs were studied Pethick et al. (); Choudhury et al. (); Alacaoglu et al. () under Lipschitz’s assumption on the operator.
In our work, we consider the generalized smooth assumption that goes beyond thr existing settings.

Normalized and Clipped Methods for SVIs
Jelassi et al. () 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. () focuses on smooth SVIs under heavy-tail noise. Using Lipschitz’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. () considered generalized smooth stochastic min-max problems and provided convergence rates for variants of SGDA with normalized, clipped, and adaptive stepsizes. In this work, the crucial part of the analysis is in the fact that the norm of a gradient can be upper bounded by a function residual. One can not use such bounds in SVIs due to the absence of function values. In our analysis, we develop a new 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. (), authors analyzed clipped gradient method under *a.s.* bounded error assumption. Koloskova et al. () showed that gradient method with standard clipping may not converge to a solution even with small stepsizes. The authors analyzed clipped gradient descent as a biased method and provided convergence rate for non-convex functions. Later, Li et al. () developed a new technique allowing to bound a stochastic gradients by the function value residual along the optimization trajectory which helps to find convergence rate for gradient with the right choice of stepsizes. In our work we do not make an assumption on *a.s.* bounded noise and bounded stochastic gradients. Furthermore, we provide not only in-expectations, but also *a.s.* convergence of the considered clipped methods.

In the light of the existing literature, we consider stochastic VIs with $p$-quasi sharp *generalized smooth* $\alpha$-symmetric 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 [1](#S1.T1)):

- •
We provide the first known analysis of clipped stochastic clipped projection method (clipped SGDA) for solving stochastic generalized smooth VIs with $p$-quasi sharp and $\alpha$-symmetric operators.
The key feature of our analysis is the use of cleverly chosen clipped stochastic stepsizes $\gamma_{k}$. We use two different samples of stochastic operator, one for clipping stepszies $\gamma_{k}$ and another for the direction of the method update. This choice allows us to use separate clipping part from the stochastic error and analyses the method in an unbiased manner. To show *a.s.* convergence, we prove that the series of clipped *stochastic* stepsizes is not summable *a.s.*, i.e. $\mathbb{P}(\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]=\infty)=1$.
- •
We also provide convergence rate for stochastic clipped projection method for $\alpha\leq 1/2$. For $p=2$ we achieve $\mathcal{O}(1/k^{-1})$ last iterate convergence. For $p>2$, we show the best iterate convergence rate of $\mathcal{O}(k^{-2(1-q)/p})$, where $1>q>1/2$ is a parameter of the stepsize choice.
- •
We provide the first known analysis of stochastic clipped Korpelevich method for solving stochastic generalized smooth VIs with $p$-quasi sharp and $\alpha$-symmetric operators.
By reusing clipping stepsizes $\gamma_{k}$ for both iterates updates $h_{k}$ and $u_{k}$ we separate stochastic stepsize from the stochastic error, similary to the projection method analysis. To show *a.s.* convergence, we prove that the series of clipped *stochastic* stepsizes is not summable *a.s.*, i.e. $\mathbb{P}(\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]=\infty)=1$.
- •
Moreover, we prove in-expectation convergence rates for the stochastic clipped Korpelevich methods for $\alpha\leq 1/2$. For $p=2$, we show the last iterate sublinear convergence rate $\mathcal{O}(k^{-1})$. For $p>2$, we show the best iterate convergence rate of $\mathcal{O}(k^{-2(1-q)/p})$, where $1>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 $q>1/2$ and quasi-sharpness parameter $p$.

**Table 1: Summary of convergence rate results showing the decrease of certain performance measures with the number $k$ 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_{k}=\mathbb{E}[{\rm dist}^{2}(u_{k},U^{*})]$ and $D_{k}=\mathbb{E}[{\rm dist}^{2}(h_{k},U^{*})]$, respectively. For $p>2$, the performance measure for both methods is $D_{k}^{\rm best}=\min_{t=0,\ldots,k}D_{t}$. The constant $C_{F}$ denotes the upper bound on $\mathbb{E}[\|F(u_{k})\|]$ and $\mathbb{E}[\|F(h_{k})\|]$ for stochastic projection and Korpelevich methods, respectively.**
|  | Stochastic Projection | Stochastic Korpelevich |
| --- | --- | --- |
| $p>0$ | Asym (Thm [3.2](#S3.Thmtheorem2)) | Asym (Thm [4.2](#S4.Thmtheorem2)) |
| $p=2$ | $\mathcal{O}\left(\dfrac{D_{0}}{k^{2}}+\dfrac{\sigma^{2}(C_{F}+\sigma)^{2}}{\mu^{2}k}\right)$ | $\mathcal{O}\left(\dfrac{(C_{F}+\sigma)^{2}K^{2}D_{0}}{\mu^{2}k^{2}}+\dfrac{(\sigma^{2}+K_{1}\sigma^{2\alpha})(C_{F}+\sigma)^{2}}{\mu^{2}k}\right)$ |
| $p>2$ | $\mathcal{O}\left(\dfrac{(D_{0}+\sigma^{2})^{2/p}(C_{F}+\sigma)^{2/p}}{\mu^{2/p}k^{2(1-q)/p}}\right)$ | $\mathcal{O}\left(\dfrac{\sigma^{4/p}(D_{0}+\sigma^{2}+K_{1}\sigma^{2\alpha})^{2/p}(C_{F}+\sigma)^{2/p}}{\mu^{2/p}k^{2(1-q)/p}}\right)$ |

The rest of the paper is organized as follows. In Section 2, we define the assumption on the operator class we consider and define the first-order methods we focus on. In Section 3 we show the almost sure convergence result of clipped stochastic projection method. In Section 4, we provide *a.s.* convergence results and in-expectation convergence rates for the clipped stochastic Korpelevich method. In Section [5](#S5) 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 [6](#S6) concludes our work and presents some further research directions.

## 2 Preliminaries

In this section, we provide the necessary concepts and assumptions for the considered SVI problem.
We start with a standard definition; the operator $F$ is said to be Lipschitz continuous on a set $U$ if there exists $L>0$ such that

$$ $\|F(u)-F(v)\|\leq L\|u-v\|\quad\hbox{for all }u,v\in U.$ (1) $$

So far, Lipschitz continuity of operator was the most common assumption to study SVIs Nemirovski (); Yousefian et al. (, ); Hsieh et al. (); Loizou et al. (); Alacaoglu et al. ().
However, this assumption does not hold in modern deep-learning applications. Based on the experiments provided in Zhang et al. (), the norm of Jacobian of the operator correlates with the norm of the operator. Recent work Chen et al. ()
proposed a new, more realistic, and weaker assumption termed $\alpha$-symmetric given as follows:
$F$ is $(L_{0},L_{1})$-smooth operator on a set $U$ if

$$ $\|F(u)-F(v)\|\leq\left(L_{0}+L_{1}\max_{\theta\in(0,1)}\|F(w_{\theta})\|^{\alpha}\right)\|u-v\|\quad\text{ for all }u,v\in U,$ (2) $$

where $w_{\theta}=\theta u+(1-\theta)v$ and $\alpha\in(0,1]$.
When the operator $F(\cdot)$ is $L$-Lipshitz continuous, it satisfies ([2](#S2.E2)) with $L_{0}=L$ and $L_{1}=0$.
The class of $\alpha$-symmetric operators includes the class of $(L_{0},L_{1})$-smooth operators and coincides with it when an operator is differentiable for $\alpha=1$.
Given that the class of $\alpha$-symmetric operators includes the class of $(L_{0},L_{1})$-smooth and Lipschitz continuous operators
we focus on this class in our work.

###### Assumption 2.1 .

Given a convex set $U\subseteq\mathbb{R}^{m}$, the operator $F(\cdot):U\to\mathbb{R}^{m}$ is $\alpha$-symmetric over $U$, i.e.,
for some $\alpha\in(0,1]$ and $L_{0},L_{1}\geq 0$, we have for all $u,v\in U$,

$$ $\|F(u)-F(v)\|\leq\left(L_{0}+L_{1}\max_{\theta\in(0,1)}\|F(w_{\theta})\|^{\alpha}\right)\|u-v\|,$ (3) $$

where $w_{\theta}=\theta u+(1-\theta)v$.

An alternative characterization of $\alpha$-symmetric operators has been proved in Chen et al. (), as given in the following proposition.

###### Proposition 2.2 ( Chen et al. ( 2023 ) , Proposition 1) .

Let $U\subseteq\mathbb{R}^{m}$ be a nonempty convex set and let
$F(\cdot):U\to\mathbb{R}^{m}$ be an operator. Then, the following statements hold:

- (a)
$F(\cdot)$ is $\alpha$-symmetric with $\alpha\in(0,1)$ and constants $L_{0},L_{1}\geq 0$ if and only if the following relation holds for all $y,y^{\prime}\in U$,
$\displaystyle\|F(y)-F(y^{\prime})\|$
$\displaystyle\leq\|y-y^{\prime}\|(K_{0}+K_{1}\|F(y^{\prime})\|^{\alpha}+K_{2}\|y-y^{\prime}\|^{\alpha/(1-\alpha)}),$
(4)
where $K_{0}=L_{0}(2^{\alpha^{2}/(1-\alpha)}+1)$, $K_{1}=L_{1}2^{\alpha^{2}/(1-\alpha)}3^{\alpha}$, and $K_{2}=L_{1}^{1/(1-\alpha)}2^{\alpha^{2}/(1-\alpha)}3^{\alpha}(1-\alpha)^{\alpha/(1-\alpha)}$.
- (b)
$F(\cdot)$ is $\alpha$-symmetric with $\alpha=1$ and constants $L_{0},L_{1}\geq 0$ if and only if the following relation holds for all $y,y^{\prime}\in U$,
$\displaystyle\|F(y)-F(y^{\prime})\|\leq\|y-y^{\prime}\|(L_{0}+L_{1}\|F(y^{\prime})\|)\exp(L_{1}\|y-y^{\prime}\|).$
(5)

Proposition [2.2](#S2.Thmtheorem2) is useful for our analysis, since it describes an $\alpha$-symmetric operator by using two points $y,y^{\prime}\in U$, and bypasses the evaluation of $\max_{\theta\in(0,1)}\|F(w_{\theta})\|^{\alpha}$.
The solution set for the variational inequality problem defined by the set $U$ and operator $F$, denoted $U^{*}$, is given by

$$ $U^{*}=\{u^{*}\in U\mid\langle F(u^{*}),u-u^{*}\rangle\geq 0\ \ \hbox{for all }u\in U\}.$ $$

Throughout this paper, we make the following assumption on the set $U$ and the solution set.

###### Assumption 2.3 .

The set $U\subseteq\mathbb{R}^{m}$ is a nonempty closed convex set, and the solution set $U^{*}$ is nonempty and closed.

We use $p$-quasi sharp operators since, for such operators, the inner product between an operator value $F(u)$ and $u-u^{*}$ is positive, which is crucial in our analysis. Moreover, this class encompasses both strongly monotone and strongly coherent operators and aligns with the class of operators that satisfy the Saddle-Point Metric Subregularity Wei et al. () for $p>2$.
The formal definition of the $p$-quasi sharpness property is presented below.

###### Assumption 2.4 .

The operator $F(\cdot):U\to\mathbb{R}^{m}$ has a $p$-quasi sharpness property over $U$ relative to the solution set $U^{*}$, i.e.,
for some $p>0$, $\mu>0$, and for all $u\in U$ and $u^{*}\in U^{*}$,

$$ $\langle F(u),u-u^{*}\rangle\geq\mu\,{\rm dist}^{p}(u,U^{*}).$ (6) $$

For solving the SVI problem,
we consider stochastic variants of projection and Korpelevich methods, where stochastic approximations
$\Phi(u_{k},\xi_{k})$ and $\Phi(h_{k},\xi_{k}^{1})$ are used, respectively, instead of the directions $F(u_{k})$ and $F(h_{k})$. The iterates of each of the stochastic methods are defined as follows:

Stochastic projection method:

$$ $\displaystyle u_{k+1}$ $\displaystyle=P_{U}(u_{k}-\gamma_{k}\Phi(u_{k},\xi_{k})),$ (7) $$

Stochastic Korpelevich method:

$$ $\displaystyle u_{k}$ $\displaystyle=P_{U}(h_{k}-\gamma_{k}\Phi(h_{k},\xi_{k}^{1})),$ (8) $\displaystyle h_{k+1}$ $\displaystyle=P_{U}(h_{k}-\gamma_{k}\Phi(u_{k},\xi_{k}^{2})),$ $$

where $\{\gamma_{k}>0\}$ is a sequence of stochastic stepsizes, and $u_{0},h_{0}\in U$ are arbitrary deterministic initial points(^2^22The results easily extend to the case when the initial points are random as long as $\mathbb{E}[\|u_{0}\|^{2}]$ and $\mathbb{E}[\|h_{0}\|^{2}]$ are finite.).
At each operator evaluation of these stochastic methods, a random sample $\xi_{k}$ is drawn according to the distribution of the random variable $\xi$.
We assume that the stochastic approximation error $\Phi(u,\xi)-F(u)$ is unbiased and has finite variance, leading to the following formal assumption.

###### Assumption 2.5 .

The random sample $\xi$ is such that
for all $u\in U$,

$$ $\mathbb{E}[\Phi(u,\xi)-F(u)\mid u]=0,\qquad\mathbb{E}[\|\Phi(u,\xi)-F(u)\|^{2}\mid u]\leq\sigma^{2}.$ $$

Our proof techniques in the following sections can be applied to analyze the (*a.s.*) convergence and convergence rate of the stochastic Popov method with an appropriate selection of stochastic clipping. However, due to space constraints, we leave this exploration for future research.

###### Assumption 2.1 .

###### Proposition 2.2 ( Chen et al. ( 2023 ) , Proposition 1) .

###### Assumption 2.3 .

###### Assumption 2.4 .

###### Assumption 2.5 .

## 3 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 for $\alpha$-symmetric operators:

$$ $\gamma_{k}=\beta_{k}\min\left\{1,\frac{1}{\|\Phi(u_{k},\xi_{k}^{2})\|}\right\},$ (9) $$

where $\beta_{k}>0$ for all $k\geq 0$ and $\xi_{k}^{2}$ is a random variable, such that $\xi_{k}^{2}$ and $\xi_{k}$ are independent conditionally on $u_{k}$.
In other words, at every iteration of the projection method, having $u_{k}$, two independent samples of the stochastic operator are drawn: (1) $\Phi(u_{k},\xi_{k})$ for the direction of update and (2) $\Phi(u_{k},\xi_{k}^{2})$ for clipping stepsize $\gamma_{k}$. We define the sigma-algebra $\mathcal{F}_{k}$ for the method:

$$ $\mathcal{F}_{k}=\{\xi_{0},\xi_{0}^{2},\ldots,\xi_{k},\xi_{k}^{2}\}\qquad\hbox{for all }k\geq 0,$ (10) $$

with $\mathcal{F}_{-1}=\emptyset$. 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 a key relation for the iterate sequence $\{u_{k}\}$ generated by the stochastic projection method with stochastic clipping stepsizes.
Its proof is in Appendix [B.1](#A2.SS1)

###### Lemma 3.1 .

Let Assumptions [2.1](#S2.Thmtheorem1), [2.3](#S2.Thmtheorem3), [2.4](#S2.Thmtheorem4), [2.5](#S2.Thmtheorem5) hold, and $\{u_{k}\}$ be the iterate sequence generated by stochastic projection method ([7](#S2.E7)) with stepsizes $\gamma_{k}$ defined in ([9](#S3.E9)). Let parameter $\beta_{k}$ be such that $\sum_{k=0}^{\infty}\beta_{k}=\infty$ and $\sum_{k=0}^{\infty}\beta_{k}^{2}<\infty$. Then, the following relation holds almost surely for all $k\geq 0$,

$$ $\mathbb{E}[\|u_{k+1}-u^{*}\|^{2}\mid\mathcal{F}_{k-1}]\leq\|u_{k}-u^{*}\|^{2}-2\mu\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]{\rm dist}^{p}(u_{k},U^{*})+3\beta_{k}^{2}(2\sigma^{2}+1).$ (11) $$

Furthermore, almost surely, we have

$$ $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\,{\rm dist}^{p}(u_{k},U^{*})<\infty,$ (12) $$

and, the sequence $\{\|u_{k}-u^{*}\|^{2}\}$ is bounded almost surely for all $u^{*}\in U^{*}$.

In the conventional analysis of methods for SVIs with Lipschitz continuous operators, the sequence $\{\gamma_{k}\}$ of stepsizes is deterministic and such that $\sum_{k}\gamma_{k}=\infty$. In our case, $\gamma_{k}$ is a random variable, and to show *a.s.* convergence we have to show that the sequence $\{\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\}$ is not summable. We do so, providing a sequence of lower bounds for series $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]$ and by showing that random variable $\|F(u_{k})\|$ is *a.s.* upper bounded for all $k\geq 0$. In the next theorem, we present the first results on *a.s.* convergence of the stochastic projection method.

###### Theorem 3.2 .

Let Assumptions [2.1](#S2.Thmtheorem1), [2.3](#S2.Thmtheorem3), [2.4](#S2.Thmtheorem4), and [2.5](#S2.Thmtheorem5) hold,
and $\{u_{k}\}$ be the iterate sequence generated by stochastic projection method ([7](#S2.E7)) with stepsizes $\gamma_{k}$ defined in ([9](#S3.E9)). Let parameter $\beta_{k}$ be such that $\sum_{k=0}^{\infty}\beta_{k}=\infty$ and $\sum_{k=0}^{\infty}\beta_{k}^{2}<\infty$.
Then, the iterates $u_{k}$ converge almost surely to a point $\bar{u}$ such that $\bar{u}\in U^{*}$ almost surely.

The full proof of Theorem [3.2](#S3.Thmtheorem2) can be found in Appendix [B.2](#A2.SS2).

###### Lemma 3.1 .

###### Theorem 3.2 .

### 3.2 Convergence rate

The difficulty of the convergence rate analysis is in the randomness of stepsizes $\gamma_{k}$. To show in-expectation convergence, we can take a total expectation on both sides of equation ([11](#S3.E11)) of Lemma [3.1](#S3.Thmtheorem1). However, since $\gamma_{k}$ is a random variable, we have to provide a lower bound on $\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})]$. With this goal in mind, in the next lemma we show that the sequence $\{\mathbb{E}[\|F(u_{k})\|]\}$ of expected norms is bounded. The proof of the lemma is in Appendix [B.3](#A2.SS3).

###### Lemma 3.3 .

Let Assumption [2.1](#S2.Thmtheorem1) hold, with $\alpha\in(0,1/2]$, Assumptions [2.3](#S2.Thmtheorem3), [2.4](#S2.Thmtheorem4), [2.5](#S2.Thmtheorem5) hold, and $\{u_{k}\}$ be iterate sequence generated by stochastic projection method ([7](#S2.E7)) with stepsizes $\gamma_{k}$ defined in ([9](#S3.E9)). Let parameter $\beta_{k}$ be such that $\sum_{k=0}^{\infty}\beta_{k}=\infty$, and $\sum_{k=0}^{\infty}\beta_{k}^{2}<\infty$. Then, the sequence $\{\mathbb{E}[\|F(u_{k})\|]\}$ is bounded by some constant $C_{F}>0$.

To prove the preceding lemma, we show that the expected norms of the operator are bounded by some constant $C_{F}$ on the trajectory of the method. To show this, we use the properties of the method and the generalized smoothness of the operator in Proposition [2.2](#S2.Thmtheorem2) to obtain that for all $k\geq 0$, and arbitrary solution $v^{*}$,

$$ $\displaystyle\|F(u_{k})\|$ $\displaystyle\leq\|F(u_{k})-F(v^{*})\|+\|F(v^{*})\|$ (13) $\displaystyle\leq\|u_{k}-v^{*}\|(K_{0}+K_{1}\|F(v^{*})\|^{\alpha}+K_{2}\|u_{k}-v^{*}\|^{\alpha/(1-\alpha)})+\|F(v^{*})\|.$ (14) $$

Notice that by taking an expectation in ([13](#S3.E13)), the RHS is undefined for $\alpha>1/2$. For $\alpha\in(0,1/2]$, using  ([13](#S3.E13)) and boundedness of $\mathbb{E}[\|u_{k}-v^{*}\|]$ we achieve the desired bound on $\mathbb{E}[\|F(u_{k})\|]$. Using this result, in the next theorem, we provide a convergence rate for the projection method with clipping.

###### Theorem 3.4 .

Let Assumption [2.1](#S2.Thmtheorem1), with $\alpha\in(0,1/2]$, and Assumptions [2.3](#S2.Thmtheorem3), [2.4](#S2.Thmtheorem4), [2.5](#S2.Thmtheorem5) hold.
Let
$\{u_{k}\}$ be the sequence generated by stochastic projection method ([7](#S2.E7)) with stepsizes $\gamma_{k}$ defined in ([9](#S3.E9)). Let $D_{k}=\mathbb{E}[{\rm dist}^{2}(u_{k},U^{*})]$ and $C_{F}$ be an upperbound on $\mathbb{E}[\|F(u_{k})\|]$. Then, we have:

Case $p=2$. Let $\beta_{k}=\frac{2}{a(2+k)}$ with $a=\mu\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}$. Then, the following inequality holds

$$ $\displaystyle D_{k+1}\leq\dfrac{8D_{0}}{k^{2}}+\frac{6(2\sigma^{2}+1)}{a^{2}k}\qquad\hbox{for all $k\geq 1$}.$ (15) $$

Case $p>2$. Let $\beta_{k}=\frac{b}{(k+1)^{q}}$, where $1/2<q<1$ and $b>0$.
Then, the following inequality holds

$$ $\displaystyle D^{\rm best}_{k}$ $\displaystyle\leq\dfrac{(1-q)^{2/p}\left(D_{0}+3b^{2}(2\sigma^{2}+1)/(2q-1)\right)^{2/p}}{(ab)^{2/p}\,\left((k+1)^{1-q}-2^{1-q}\right)^{2/p}}\qquad\hbox{for all $k\geq 1$},$ (16) $$

where $D^{\rm best}_{k}=\min_{t\in[0,\ldots,k]}D_{t}$
and $a=\mu\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}$.

For the simplicity of convergence rate comparison, assume $2(C_{F}+\sigma)\geq 1$. Then, from Theorem [4.4](#S4.Thmtheorem4) we obtain $\mathcal{O}(\frac{D_{0}}{k^{2}}+\frac{\sigma^{2}(C_{F}+\sigma)^{2}}{\mu^{2}k})$ last iterate convergence rate for $p=2$, and $\mathcal{O}(\frac{(D_{0}+\sigma^{2})^{2/p}(C_{F}+\sigma)^{2/p}}{\mu^{2/p}k^{2(1-q)/p}})$ for $p>2$ with $q\in(1/2,1)$. The proof of Theorem [3.4](#S3.Thmtheorem4) is in Appendix [B.4](#A2.SS4).

###### Lemma 3.3 .

###### Theorem 3.4 .

## 4 Korpelevich method

The stepsizes for the stochastic Korpelevich method for $\alpha$-symmetric operators are as given below

$$ $\gamma_{k}=\beta_{k}\min\left\{1,\frac{1}{\|\Phi(h_{k},\xi^{1}_{k})\|}\right\},$ (17) $$

where $\beta_{k}>0$ for all $k\geq 0$ and $\xi_{k}^{1}$ is a random variable associated with the stochastic approximation $\Phi(h_{k},\xi_{k}^{1})$ of $F(h_{k})$. We define the sigma-algebra $\mathcal{F}_{k}$ for the method, as follows:

$$ $\mathcal{F}_{k}=\{\xi_{0}^{1},\xi_{0}^{2},\ldots,\xi_{k}^{1},\xi_{k}^{2}\}\qquad\hbox{for all }k\geq 0,$ (18) $$

with $\mathcal{F}_{-1}=\emptyset$. Notice that to obtain $h_{k+1}$ from a point $u_{k}$, the stepsize $\gamma_{k}$ clips $\Phi(h_{k},\xi_{k}^{1})$, not the stochastic approximation $\Phi(u_{k},\xi_{k}^{2})$ of the operator at point $u_{k}$, i.e., we have

$$ $h_{k+1}=P_{U}\left(u_{k}-\beta_{k}\min\left\{1,\frac{1}{\|\Phi(h_{k},\xi^{1}_{k})\|}\right\}\Phi(u_{k},\xi_{k}^{2})\right).$ (19) $$

Thus, sample $\xi_{k}^{2}$ is drawn after $\xi_{k}^{1}$, and
$\Phi(h_{k},\xi_{k}^{1})$ is measurable with respect to $\mathcal{F}_{k-1}\cup\xi_{k}^{1}$. This property of the stochastic Korpelevich method with clipping stepsizes $\gamma_{k}$ is crucial for further convergence analysis of the method. In the sequel, we provide important results on the behavior of the iterates of the clipped stochastic 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](#S2.Thmtheorem1), [2.3](#S2.Thmtheorem3), [2.4](#S2.Thmtheorem4), and [2.5](#S2.Thmtheorem5) hold. Also, let $\{h_{k}\}$ and $\{u_{k}\}$ be iterates generated by stochastic Korpelevich method ([8](#S2.E8)) with stepsizes $\gamma_{k}$ defined in  ([17](#S4.E17))
and with parameter $\beta_{k}$ such that $\sum_{k=0}^{\infty}\beta_{k}=\infty$ and $\sum_{k=0}^{\infty}\beta_{k}^{2}<\infty$.
Then, the following relation holds almost surely

$$ $\displaystyle\mathbb{E}[\|h_{k+1}-u^{*}\|^{2}\mid\mathcal{F}_{k-1}]$ $\displaystyle\leq\|h_{k}-u^{*}\|^{2}-\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^{*})$ (20) $\displaystyle+6\beta_{k}^{2}(\sigma^{2}+C_{e}(\beta_{k},\alpha)\sigma^{2\alpha})\qquad\hbox{for all $k\geq 0$},$ $$

where $C_{e}(\beta_{k},\alpha)=K_{1}$, when $\alpha\in(0,1)$, and
$C_{e}(\beta_{k},\alpha)=\exp(L_{1}\beta_{k})$, when $\alpha=1$. Moreover, the following relations hold almost surely,

$$ $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\,{\rm dist}^{p}(u_{k},U^{*})<\infty,\quad\sum_{k=0}^{\infty}\|h_{k}-u_{k}\|^{2}<\infty.$ (21) $$

Furthermore,
the sequence $\{\|h_{k}-u^{*}\|\}$ is bounded almost surely for all $u^{*}\in U^{*}$.

The proof of Lemma [4.1](#S4.Thmtheorem1) is in Appendix [C.1](#A3.SS1).

In a standard analysis of the Korpelevich method for SVI with Lipschitz operators Kannan and Shanbhag (); Vankov et al. (), *a.s.* convergence results were achieved for a deterministic sequence $\{\gamma_{k}\}$. In our case, similarly to projection method analysis, $\{\gamma_{k}\}$ is a sequence of random variables, which makes the analysis of the methods more difficult and involved.
By the choice of stepsizes $\gamma_{k}$ as given in ([17](#S4.E17)), the following relation holds true

$$ $\displaystyle\mathbb{E}[\gamma_{k}\langle\Phi(u_{k},\xi_{k}^{2})-F(u_{k}),u_{k}-u^{*}\rangle\mid\mathcal{F}_{k-1}]=0\qquad\hbox{for all }k\geq 0.$ (22) $$

To prove ([22](#S4.E22)) for the stochastic Korpelevich method, we note that the clipping stepsize is using $\|\Phi(h_{k},\xi_{k}^{1})\|$, which decouples from $\Phi(u_{k},\xi_{k}^{2})$ by properly using conditional expectation.
Specifically, we first take the expectation conditioned on $\mathcal{F}_{k-1}\cup\xi_{k}^{1}$. Since $\gamma_{k}$ is measurable with respect to $\mathcal{F}_{k-1}\cup\xi_{k}^{1}$, we use Assumption [2.5](#S2.Thmtheorem5) and the law of the total expectation. Interestingly, we do not have to take another sample for the clipping in the stochastic Korpelevich method, as we have done in the stochastic projection method. Thus, to perform one iteration, we use two oracle calls in both methods.

Using Lemma [4.1](#S4.Thmtheorem1), we next present the almost sure convergence of the clipped Korpelevich method.

###### Theorem 4.2 .

Let Assumptions [2.1](#S2.Thmtheorem1), [2.3](#S2.Thmtheorem3), [2.4](#S2.Thmtheorem4), and [2.5](#S2.Thmtheorem5) hold
and $\{h_{k}\}$, $\{u_{k}\}$ be iterates generated by stochastic Korpelevich method ([8](#S2.E8)) with stepsizes $\gamma_{k}$ defined in ([17](#S4.E17)). Let parameter $\beta_{k}$ be such that
$\sum_{k=0}^{\infty}\beta_{k}=\infty$, and $\sum_{k=0}^{\infty}\beta_{k}^{2}<\infty$.
Then, the iterates $h_{k}$ and $u_{k}$ converge almost surely to a point $\bar{u}$ such that $\bar{u}\in U^{*}$ almost surely.

To prove *a.s.* convergence, we firstly show that $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]=\infty$ *a.s.*, by providing a sequence of lower bounds on $\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]$, using *a.s.* boundedness of $\|h_{k}-u^{*}\|$ of Lemma [4.1](#S4.Thmtheorem1), and proving that $\|F(h_{k})\|$ is *a.s.* bounded.
The full proof can be found in Appendix [C.2](#A3.SS2).

###### Lemma 4.1 .

###### Theorem 4.2 .

### 4.2 Convergence rate

We start our analysis by taking the total expectation on both sides of equation ([20](#S4.E20)) from Lemma [4.1](#S4.Thmtheorem1). For further analysis, similar to the clipped stochastic projection methods, the challenge lies in the randomness of the stepsizes $\gamma_{k}$. To handle this,
firstly, we establish a lower bound for $\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})]$ by showing that the sequence $\{\mathbb{E}[|F(u_{k})|]\}$ of expected norms remains bounded, as shown in the next lemma. The proof of the lemma can be found in Appendix [B.3](#A2.SS3).

###### Lemma 4.3 .

Let Assumption [2.1](#S2.Thmtheorem1), with $\alpha\in(0,1/2]$, and Assumptions [2.3](#S2.Thmtheorem3),  [2.4](#S2.Thmtheorem4),  [2.5](#S2.Thmtheorem5) hold. Let $\{u_{k}\}$, $\{h_{k}\}$ be iterates generated by stochastic Korpelevich method ([8](#S2.E8)) with stepsizes $\gamma_{k}$ defined in ([17](#S4.E17)) and the parameter $\beta_{k}$ such that $\sum_{k=0}^{\infty}\beta_{k}=\infty$ and $\sum_{k=0}^{\infty}\beta_{k}^{2}<\infty$. Then, $\mathbb{E}[\|F(h_{k})\|]$ is bounded by some constant $C_{F}>0$ for all $k\geq 0$.

Similarly to the analysis presented in Section [3](#S3), we bound $F(h_{k})$ by using a triangle inequality and the property of $\alpha$-symmetric operators, and by taking the total expectation, we obtain

$$ $\displaystyle\mathbb{E}[\|F(u_{k})\|]$ $\displaystyle\leq K_{0}\mathbb{E}[\|u_{k}-v^{*}\|]+K_{2}\mathbb{E}[\|u_{k}-v^{*}\|^{\alpha/(1-\alpha)})]+\|F(v^{*})\|+K_{1}\|F(v^{*})\|^{\alpha}.$ (23) $$

We can show that the preceding bound has a finite expectation only for $0<\alpha\leq 1/2$, which motivates the restriction on $\alpha$ in Lemma [4.3](#S4.Thmtheorem3).
Equipped with the boundedness of the sequence $\{\mathbb{E}[\|F(h_{k})\|\}$ of expected norms of the operator along the iterates $\{h_{k}\}$, we present the next convergence rate theorem.

###### Theorem 4.4 .

Let Assumption [2.1](#S2.Thmtheorem1), with $\alpha\in(0,1/2]$, and Assumptions [2.3](#S2.Thmtheorem3), [2.4](#S2.Thmtheorem4), [2.5](#S2.Thmtheorem5) hold.
Let $\{u_{k}\}$, $\{h_{k}\}$ be iterates generated by stochastic Korpelevich method ([8](#S2.E8)) with stepsizes $\gamma_{k}$ defined in ([17](#S4.E17)). Let $D_{k}=\mathbb{E}[{\rm dist}^{2}(h_{k},U^{*})]$ and $C_{F}$ be an upperbound on $\mathbb{E}[\|F(h_{k})\|]$ then the following results holds:

Case $p=2$.
Let $\beta_{k}=\dfrac{2}{a(\frac{2d}{a}+k)}$, with $a=\mu\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}$, $d=\max\{4\mu,2\sqrt{3}(K_{0}+K_{1}+K_{2})\}$
where $K_{0},K_{1},$ and $K_{2}$ are from Proposition [2.2](#S2.Thmtheorem2)(a).
Then, the following relation holds

$$ $\displaystyle D_{k+1}\leq\dfrac{8d^{2}D_{0}}{a^{2}k^{2}}+\frac{12(\sigma^{2}+K_{1}\sigma^{2\alpha})}{a^{2}k}\qquad\hbox{for all $k\geq 1$}.$ (24) $$

Case $p>2$. Let $\beta_{k}=\frac{b}{(k+1)^{q}}$, where $1/2<q<1$
and $0<b\leq\min\left\{\frac{1}{4\mu},\frac{1}{2\sqrt{3}(K_{0}+K_{1}+K_{2})}\right\}$.
Then, the following inequality holds for all $k\geq 1$,

$$ $\displaystyle D^{\rm best}_{k}$ $\displaystyle\leq\dfrac{2^{2(p-2)/p}(1-q)^{2/p}\left(D_{0}+6b^{2}(\sigma^{2}+K_{1}\sigma^{2\alpha})(2\sigma^{2}+1)/(2q-1)\right)^{2/p}}{(ab)^{2/p}\,\left((k+1)^{1-q}-2^{1-q}\right)^{2/p}},$ (25) $$

where $a=\mu\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}$ and $D^{\rm best}_{k}=\min_{t\in[0,\ldots,k]}D_{t}$.

The proof of Theorem [4.4](#S4.Thmtheorem4) is provided in Appendix [C.4](#A3.SS4). For the simplicity of convergence rate comparison, assume $2(C_{F}+\sigma)\geq 1$ and $K_{0}+K_{1}+K_{2}\geq\frac{2\mu}{\sqrt{3}}$. Then by denoting $K=K_{0}+K_{2}+K_{3}$, from Theorem [4.4](#S4.Thmtheorem4), we obtain $\mathcal{O}(\frac{(C_{F}+\sigma)^{2}K^{2}D_{0}}{\mu^{2}k^{2}}+\frac{(\sigma^{2}+K_{1}\sigma^{2\alpha})(C_{F}+\sigma)^{2}}{\mu^{2}k})$ last iterate convergence for $p=2$, and $\mathcal{O}\left(\frac{\sigma^{4/p}(D_{0}+\sigma^{2}+K_{1}\sigma^{2\alpha})^{2/p}(C_{F}+\sigma)^{2/p}}{\mu^{2/p}k^{2(1-q)/p}}\right)$ for $p>2$ with $q\in(1/2,1)$.

###### Lemma 4.3 .

###### Theorem 4.4 .

## 5 Numerical Experiments

We study the performance of the clipped stochastic projection and Korpelevich methods, for different values of parameters $\alpha>0$ and $p>0$. Despite the absence of analysis, we also implement the clipped stochastic Popov method with the sample for clipping and direction analogous to that of stochastic Korpelevich method.
We consider an unconstrained SVI$(\mathbb{R}^{2},F)$ with the following stochastic operator

$$ $\Phi(u,\xi)=\begin{bmatrix}\text{sign}(u_{1})|u_{1}|^{p-1}+u_{2}\\ \text{sign}(u_{2})|u_{2}|^{p-1}-u_{1}\end{bmatrix}+\xi,$ $$

where $\xi$ is a random vector with independent zero-mean Gaussian entries and with variance $\sigma^{2}=1$.
Then, $F(u)=\mathbb{E}[\Phi(u,\xi)]$ is an $\alpha$-symmetric and $p$-quasi sharp operator due to Vankov et al. ().
We set these parameters to be $\{(\alpha\approx 0.33,p=2.5),(\alpha\approx 0.5,p=3.0),(\alpha\approx 0.8,p=6.0)\}$.
We also compare our results with the projection method that uses the same sample clipping, meaning stepsizes $\gamma_{k}$ clip $\|\Phi(u_{k},\xi_{k})\|$ instead of a different sample $\|\Phi(u_{k},\xi_{k}^{2})\|$.

Figure: (a) $(\alpha\approx 0.33,p=2.5)$
Refer to caption: /html/2410.12334/assets/x1.png

Figure: (a) $(\alpha\approx 0.33,p=2.5)$
Refer to caption: /html/2410.12334/assets/x4.png

In Figure  [1](#S5.F1), we plot an average distance over twenty runs to the solution set as a function of the number of iterations. In particular, the stepsizes for clipped stochastic projection and Korpelevich methods are chosen according to Theorems [3.4](#S3.Thmtheorem4) and [4.4](#S4.Thmtheorem4), respectively, with $\beta_{k}=\frac{100}{100+k^{q}}$ for $q=1/2+\epsilon$ with $\epsilon>0$. Note that, according to Theorems [3.4](#S3.Thmtheorem4) and [4.4](#S4.Thmtheorem4), the parameter $q$ should be greater than $1/2$; meanwhile, the rates in these theorems are better for smaller choices of $q$. We also set $\beta_{k}=\frac{100}{100+k^{q}}$ for clipped stochastic Popov method and the clipped stochastic projection method using the same sample $\Phi(u_{k},\xi_{k})$ for clipping.

Based on this experiment, we made three important observations. Firstly, the clipped stochastic projection method and same-sample clipped stochastic projection method show similar results despite the fact that the same-sample stochastic projection method has a biased error. Secondly, for $\alpha\leq 1/2$ as predicted in theory (Theorems [3.4](#S3.Thmtheorem4), [4.4](#S4.Thmtheorem4)), both projection and Korpelevich methods show in-expectation convergence, while for $\alpha>1/2$ Korpelevich method has less stable performance. Finally, despite the fact that for stochastic Lipschitz SVI, Korpelevich method outperforms the projection method, we don’t see this in generalized smooth SVIs.

Next, we investigate the performance of the methods for larger values of $q$. In Figure [2](#S5.F2), we set $q=1-\epsilon$, and corresponding $\beta_{k}=\frac{100}{100+k^{1-\epsilon}}$ and run all four methods for the same problem parameter setting. We observe that for all considered $\alpha$, despite the theory, a larger choice of $q$ improved the performance of all methods. Furthermore, it seems that larger values of $q$ help to stabilize the clipped stochastic gradient method.
Additionally, we investigate the robustness of the methods for a larger choice of the initial parameter value $\beta_{0}$. In Figure [3](#S5.F3), we set $q=1-\epsilon$, and corresponding $\beta_{k}=\frac{50}{10+k^{1-\epsilon}}$, so the initial stepsize $\beta_{0}\approx 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 is comparable to that of both versions of clipped stochastic projection methods. 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.

Figure: (a) $(\alpha\approx 0.09,p=2.5)$
Refer to caption: /html/2410.12334/assets/x7.png

## 6 Conclusion

This paper studied the SVI problem under generalized smooth and structured non-monotone assumptions. Specifically, we consider $\alpha$-smooth and $p$-quasi-sharp operator, one of the widest classes of operators for SVIs. For this wide class of operators, we proved the first-known almost sure convergence of clipped stochastic projection and Korpelevich methods for all parameters $p$. We also provided $\mathcal{O}(1/k)$ convergence rate for both considered methods when the operator is $p$-quasi sharp with $p=2$. For $p>2$ we provided $\mathcal{O}(k^{-2(1-q)/p})$convergence rate for both methods, where $q$ is a stepsizes parameter $1/2<q<1$. Despite the generality of our results, there are still open questions remain. In particular, it would be interesting to know if it is possible to show in-expectation convergence rates for $\alpha$-smooth SVI $\alpha>1/2$. Another attractive direction of further research in generalized smooth SVIs is in relaxation of $p$-quasi sharpness assumption to Minty ($\mu=0$) or weak Minty ($\mu<0$) conditions. 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, clipped stochastic Popov method or first-order methods with adaptive stepsizes.

## Appendix A Technical Lemmas

In our analysis, we use the properties of the projection operator $P_{U}(\cdot)$ given in the following lemma.

###### Lemma A.1 .

(Theorem 1.5.5 and Lemma 12.1.13 in Facchinei and Pang []) Given a nonempty convex closed set $U\subset\mathbb{R}^{m},$ the projection operator $P_{U}(\cdot)$ has the following properties:

$$ $\langle v-P_{U}(v),u-P_{U}(v)\rangle\leq 0\quad\hbox{for all }u\in U,v\in\mathbb{R}^{m},$ (26) $$

$$ $\|u-P_{U}(v)\|^{2}\leq\|u-v\|^{2}-\|v-P_{U}(v)\|^{2}\quad\hbox{for all }u\in U,v\in\mathbb{R}^{m},$ (27) $$

$$ $\|P_{U}(u)-P_{U}(v)\|\leq\|u-v\|\quad\hbox{for all }u,v\in\mathbb{R}^{m}.$ (28) $$

In the forthcoming analysis, we use Lemma 11 Polyak [], which is stated below.

###### Lemma A.2 .

[Lemma 11 Polyak []]
Let $\{v_{k}\},\{z_{k}\},\{a_{k}\},$ and $\{b_{k}\}$ be nonnegative random scalar sequences such that almost surely for all $k\geq 0$,

$$ $\displaystyle\mathbb{E}[v_{k+1}\mid{\cal F}_{k}]\leq$ $\displaystyle(1+a_{k})v_{k}-z_{k}+b_{k},$ (29) $$

where
${\cal F}_{k}=\{v_{0},\ldots,v_{k},z_{0},\ldots,z_{k},a_{0},\ldots,a_{k},b_{0},\ldots,b_{k}\}$, and
*a.s.* $\sum_{k=0}^{\infty}a_{k}<\infty$, $\sum_{k=0}^{\infty}b_{k}<\infty$. Then, almost surely, $\lim_{k\to\infty}v_{k}=v$ for some nonnegative random variable $v$ and $\sum_{k=0}^{\infty}z_{k}<\infty$.

As a direct consequence of Lemma [A.2](#A1.Thmtheorem2), when
the sequences $\{v_{k}\},\{z_{k}\},\{a_{k}\},\{b_{k}\}$ are deterministic, we obtain the following result.

###### Lemma A.3 .

Let $\{\bar{v}_{k}\},\{\bar{z}_{k}\},\{\bar{a}_{k}\},\{\bar{b}_{k}\}$ be nonnegative scalar sequences such that for all $k\geq 0$,

$$ $\displaystyle\bar{v}_{k+1}\leq$ $\displaystyle(1+\bar{a}_{k})\bar{v}_{k}-\bar{z}_{k}+\bar{b}_{k},$ (30) $$

where $\sum_{k=0}^{\infty}\bar{a}_{k}<\infty$ and $\sum_{k=0}^{\infty}\bar{b}_{k}<\infty$. Then,
$\lim_{k\to\infty}\bar{v}_{k}=\bar{v}$
for some scalar $\bar{v}\geq 0$ and $\sum_{k=0}^{\infty}\bar{z}_{k}<\infty$.

###### Lemma A.4 .

Let $X$ be a non-negative random variable such that $\mathbb{E}[X^{\rho}]$ is defined for some $\rho\geq 1$, and $\mathbb{E}[X^{\rho}]\not=0$, then for every $a>0$ it holds

$$ $\displaystyle\mathbb{P}(X>a(\mathbb{E}[X^{\rho}])^{1/\rho}\leq\frac{1}{a^{\rho}}.$ (31) $$

###### Proof.

Let $Y=X^{\rho}$. By the conditions of the lemma, the expectation $\mathbb{E}[Y]=\mathbb{E}[X^{\rho}]$ is well defined. Then, by Markov’s inequality:

$$ $\displaystyle\mathbb{P}(X>a(\mathbb{E}[X^{\rho}])^{1/\rho})$ $\displaystyle=\mathbb{P}(Y>a^{\rho}\mathbb{E}[X^{\rho}])$ $\displaystyle\leq\frac{\mathbb{E}[X^{\rho}]}{a^{\rho}\mathbb{E}[X^{\rho}]}.$ $$

∎

###### Lemma A.5 .

Let $a_{1},a_{2}$ be nonnegative scalar and $p>0$. Then the following inequality holds:

$$ $\left(a_{1}+a_{2}\right)^{p}\leq 2^{p-1}(a_{1}^{p}+a_{2}^{p}).$ $$

###### Proof.

Let $a=(a_{1},a_{2}),b=(1,1)$, then by Hölder inequality:

$$ $\displaystyle a_{1}+a_{2}$ $\displaystyle=\|ab\|$ $\displaystyle\leq\|a\|_{p}\|b\|_{p/(p-1)}$ $\displaystyle\leq(a_{1}^{p}+a_{2}^{p})^{1/p}(1+1)^{(p-1)/p}.$ $$

Raising the inequality in the power $p$ we get the desired relation.
∎

###### Lemma A.1 .

###### Lemma A.2 .

###### Lemma A.3 .

###### Lemma A.4 .

###### Proof.

###### Lemma A.5 .

###### Proof.

### A.1 Auxiliary Results

In our analysis we make use of Lemma 3 and Lemma 7 from Stich [], as well as the sequences provided in the proofs in Stich [].

###### Lemma A.6 .

Let $\{r_{k}\}$ and $\{s_{k}\}$ be nonnegative scalar sequences that satisfy the following relation

$$ $r_{k+1}\leq(1-a\alpha_{k})r_{k}-b\alpha_{k}s_{k}+c\gamma_{k}^{2}\qquad\hbox{for all }k\geq 0,$ $$

where $a>0$, $b>0$, $c\geq 0$, and

$$ $\gamma_{k}=\frac{2}{a\left(\frac{2d}{a}+k\right)}\qquad\hbox{for all }k\geq 0,$ $$

where $d\geq a$.
Then, for any given $K\geq 0$, the following relation holds:

$$ $\frac{b}{W_{K}}\sum^{K}_{k=0}w_{k}s_{k}+ar_{K+1}\leq\frac{8d^{2}}{aK^{2}}\,r_{0}+\frac{2c}{aK},$ $$

where $w_{k}=2d/a+k$, $0\leq k\leq K$, and $W_{K}=\sum_{k=0}^{K}w_{k}$.

###### Lemma A.7 .

For $1>q\geq 1/2$ and $K\geq 1$, we have

$$ $\displaystyle\sum^{K}_{t=0}\frac{1}{(t+1)^{q}}$ $\displaystyle\geq\frac{1}{1-q}((K+1)^{1-q}-2^{1-q}).$ (32) $$

For $q=1/2$ and $K\geq 1$,

$$ $\displaystyle\sum^{K}_{t=0}\frac{1}{(t+1)^{2q}}$ $\displaystyle\leq\log(K+1).$ (33) $$

For $q>1/2$ and $K\geq 1$,

$$ $\displaystyle\sum^{K}_{t=0}\frac{1}{(t+1)^{2q}}$ $\displaystyle\leq\frac{1}{2q-1}.$ (34) $$

###### Proof.

Let $1>q\geq 1/2$ and $K\geq 1$. Then, it holds

$$ $\displaystyle\sum^{K}_{t=0}\frac{1}{(t+1)^{q}}\geq\int_{s=1}^{K}\frac{ds}{(s+1)^{q}}=\frac{1}{1-q}((K+1)^{1-q}-2^{1-q}).$ (35) $$

When $q=1/2$ and $K\geq 1$, then

$$ $\displaystyle\sum^{K}_{t=0}\frac{1}{t+1}\leq\int_{s=0}^{K}\frac{ds}{s+1}=\log(K+1).$ (36) $$

When $q>1/2$ and $K\geq 1$, we have that

$$ $\displaystyle\sum^{K}_{t=0}\frac{1}{(t+1)^{2q}}\leq\int_{s=0}^{K}\frac{ds}{(s+1)^{2q}}=\frac{1}{2q-1}-\frac{1}{(2q-1)(K+1)^{2q-1}}<\frac{1}{2q-1}.$ (37) $$

∎

###### Lemma A.6 .

###### Lemma A.7 .

###### Proof.

## Appendix B Projection Method Analysis

### B.1 Proof of Lemma 3.1

###### Proof.

Let $k\geq 0$ be arbitrary but fixed. From the definition of $u_{k+1}$ in ([7](#S2.E7)), we have $\|u_{k+1}-y\|^{2}=\|P_{U}(u_{k}-\gamma_{k}\Phi(u_{k},\xi_{k}))-y\|^{2}$ for all $y\in U$. Using the non-expansiveness property of projection operator ([28](#A1.E28)) we obtain for all $y\in U$ and $k\geq 0$,

$$ $\displaystyle\|u_{k+1}-y\|^{2}$ $\displaystyle\leq\|u_{k}-\gamma_{k}\Phi(u_{k},\xi_{k})-y\|^{2}$ (38) $\displaystyle=\|u_{k}-y\|^{2}-2\gamma_{k}\langle\Phi(u_{k},\xi_{k}),u_{k}-y\rangle+\gamma_{k}^{2}\|\Phi(u_{k},\xi_{k})\|^{2}$ (39) $\displaystyle=\|u_{k}-y\|^{2}+\gamma_{k}^{2}\|\Phi(u_{k},\xi_{k})\|^{2}$ (40) $\displaystyle-2\gamma_{k}\langle F(u_{k}),u_{k}-y\rangle+2\gamma_{k}\langle e_{k},u_{k}-y\rangle,$ (41) $$

where $e_{k}=F(u_{k})-\Phi(u_{k},\xi_{k})$. By the definition of the stepsizes ([9](#S3.E9)), $\gamma_{k}=\beta_{k}\min\{1,\frac{1}{\|\Phi(u_{k},\xi_{k}^{2})\|}\}$, then the term $\gamma_{k}^{2}\|\Phi(u_{k},\xi_{k})\|^{2}$ can be upper bounded as follows

$$ $\displaystyle\gamma_{k}^{2}\|\Phi(u_{k},\xi_{k})\|^{2}$ $\displaystyle=\gamma_{k}^{2}\|\Phi(u_{k},\xi_{k})-F(u_{k})+F(u_{k})-\Phi(u_{k},\xi_{k}^{2})+\Phi(u_{k},\xi_{k}^{2})\|^{2}$ (42) $\displaystyle\leq\beta_{k}^{2}\min\left\{1,\frac{1}{\|\Phi(u_{k},\xi_{k}^{2})\|^{2}}\right\}\,3(\|e_{k}\|^{2}+\|e_{k}^{2}\|^{2}+\|\Phi(u_{k},\xi_{k}^{2})\|^{2})$ (43) $\displaystyle\leq 3\beta_{k}^{2}\|e_{k}\|^{2}+3\beta_{k}^{2}\|e_{k}^{2}\|^{2}+3\beta_{k}^{2},$ (44) $$

where $e_{k}=F(u_{k})-\Phi(u_{k},\xi_{k}),e_{k}^{2}=F(u_{k})-\Phi(u_{k},\xi_{k}^{2})$. Thus,

$$ $\displaystyle\|u_{k+1}-y\|^{2}$ $\displaystyle\leq\|u_{k}-y\|^{2}-2\gamma_{k}\langle F(u_{k}),u_{k}-y\rangle$ (45) $\displaystyle+2\gamma_{k}\langle e_{k},u_{k}-y\rangle+3\beta_{k}^{2}(\|e_{k}\|^{2}+\|e_{k}^{2}\|^{2}+1).$ (46) $$

Plugging in $y=u^{*}\in U^{*}$, where $u^{*}$ is an arbitrary solution, and using $p$-quasi sharpness we get:

$$ $\displaystyle\|u_{k+1}-u^{*}\|^{2}$ $\displaystyle\leq\|u_{k}-u^{*}\|^{2}-2\mu\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})$ (47) $\displaystyle+2\gamma_{k}\langle e_{k},u_{k}-u^{*}\rangle+3\beta_{k}^{2}(\|e_{k}\|^{2}+\|e_{k}^{2}\|^{2}+1).$ (48) $$

Using stochastic properties of $\xi_{k}$ and $\xi_{k}^{2}$ imposed by Assumption [2.5](#S2.Thmtheorem5), and the conditional independence of $\xi_{k}$ and $\xi_{k}^{2}$, we have:

$$ $\mathbb{E}[\gamma_{k}\langle e_{k},u_{k}-u^{*}\rangle|\mathcal{F}_{k-1}]=\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\langle\mathbb{E}[e_{k}\mid\mathcal{F}_{k-1}],u_{k}-u^{*}\rangle=0.$ $$

$$ $\mathbb{E}[\|e_{k}\|^{2}\mid\mathcal{F}_{k-1}]\leq\sigma^{2},\quad\mathbb{E}[\|e_{k}^{2}\|^{2}\mid\mathcal{F}_{k-1}]\leq\sigma^{2}.$ $$

Thus, by taking the conditional expectation on $\mathcal{F}_{k-1}=\{\xi_{0},\xi_{0}^{2},\ldots,\xi_{k-1},\xi_{k-1}^{2}\}$ in relation ([47](#A2.E47)) we obtain for all $u^{*}\in U^{*}$ and for all $k\geq 0$:

$$ $\displaystyle\mathbb{E}[\|u_{k+1}-u^{*}\|^{2}|\mathcal{F}_{k-1}]$ $\displaystyle\leq\|u_{k}-u^{*}\|^{2}+3\beta_{k}^{2}(2\sigma^{2}+1)$ (49) $\displaystyle-2\mu\beta_{k}\mathbb{E}\left[\min\left\{1,\frac{1}{\|\Phi(u_{k},\xi_{k}^{2})\|}\right\}\mid\mathcal{F}_{k-1}\right]{\rm dist}^{p}(u_{k},U^{*}).$ (50) $$

The equation ([49](#A2.E49)) satisfies the condition of Lemma [A.2](#A1.Thmtheorem2) with

$$ $\displaystyle v_{k}=\|u_{k}-u^{*}\|^{2},\quad a_{k}=0,\quad z_{k}=2\mu\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\,{\rm dist}^{p}(u_{k},U^{*}),\quad b_{k}=3\beta_{k}^{2}(2\sigma^{2}+1).$ (51) $$

By Lemma [A.2](#A1.Thmtheorem2), it follows that the sequence $\{v_{k}\}$ converges a.s. to a non-negative scalar for any $u^{*}\in U^{*}$, and almost surely we have

$$ $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\,{\rm dist}^{p}(u_{k},U^{*})<\infty.$ (52) $$

Since the sequence $\{\|u_{k}-u^{*}\|^{2}\}$
converges a.s. for all $u^{*}\in U^{*}$, it follows that the sequence
$\{\|u_{k}-u^{*}\|\}$ is bounded a.s. for all $u^{*}\in U^{*}$.
∎

###### Proof.

### B.2 Proof of Theorem 3.2

###### Proof.

To show almost sure convergence, we need to show that $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]$ is not summable almost surely. To do so, we provide a sequence of lower bounds on $\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]$. First, consider the following event:

$$ $A_{k}=\{\|e_{k}^{2}\|\leq 2\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]\},$ $$

where $e_{k}^{2}=F(u_{k})-\Phi(u_{k},\xi_{k}^{2})$ is a stochastic error from the sample for the clipping stepsize $\gamma_{k}$. Then, by the law of total expectation

$$ $\displaystyle\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]=\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}]\mathbb{P}(A_{k}\mid\mathcal{F}_{k-1})+\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup\overline{A}_{k}]\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1}).$ (53) $$

We want to provide a lower bound on $\mathbb{P}(A_{k}\mid\mathcal{F}_{k-1})$. To do so, we upperbound $\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1})$ using Markov’s inequality and Assumption [2.5](#S2.Thmtheorem5):

$$ $\displaystyle\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1})=\mathbb{P}(\|e_{k}\|>2\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]\})\leq\frac{\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]}{2\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}])}=\frac{1}{2}.$ (54) $$

Thus,

$$ $\displaystyle\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]$ $\displaystyle=\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}](1-\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1}))+\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup\overline{A}_{k}]\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1})$ (55) $\displaystyle\geq\frac{1}{2}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}]+\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup\overline{A}_{k}]\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1})$ (56) $\displaystyle\geq\frac{1}{2}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}].$ (57) $$

By definition of $\gamma_{k}$, triangle inequality and definition of event $A_{k}$, it holds

$$ $\displaystyle\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}]$ $\displaystyle=\beta_{k}\mathbb{E}[\min\left\{1,\frac{1}{\|\Phi(u_{k},\xi_{k}^{2})\|}\right\}\mid\mathcal{F}_{k-1}\cup A_{k}]$ (58) $\displaystyle\geq\beta_{k}\mathbb{E}\left[\min\left\{1,\frac{1}{\|F(u_{k})\|+\|e_{k}^{2}\|}\right\}\mid\mathcal{F}_{k-1}\cup A_{k}\right].$ (59) $$

Next, we use the definition of the event $A_{k}$ to provide the next lower bound:

$$ $\displaystyle\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}]$ $\displaystyle\geq\beta_{k}\mathbb{E}[\min\left\{1,\frac{1}{\|F(u_{k})\|+2\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]}\right\}\mid\mathcal{F}_{k-1}\cup A_{k}]$ (61) $\displaystyle\geq\beta_{k}\mathbb{E}[\min\left\{1,\frac{1}{\|F(u_{k})\|+2\sigma}\right\}\mid\mathcal{F}_{k-1}\cup A_{k}]$ (62) $\displaystyle=\beta_{k}\min\left\{1,\frac{1}{\|F(u_{k})\|+2\sigma}\right\}.$ (63) $$

The first inequality in the preceding equation holds by definition of event $A_{k}=\{\|e_{k}^{2}\|\leq 2\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]\}$, the second inequality holds dues to Assumption [2.5](#S2.Thmtheorem5) on the noise and Jensen inequality, $\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]\leq\sqrt{\mathbb{E}[\|e_{k}^{2}\|^{2}\mid\mathcal{F}_{k-1}]}\leq\sigma$, and the last equality holds since $\|F(u_{k})\|$ is measurable in $\mathcal{F}_{k-1}$.
Hence, it follows that

$$ $\displaystyle\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\|F(u_{k})\|+\sigma}\right\}\leq\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}].$ (64) $$

Now, we want to show that $\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\|F(u_{k})\|+\sigma}\right\}$ is not summable almost surely, i.e. $\mathbb{P}(\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\|F(u_{k})\|+\sigma}\right\}=\infty)=1$.
We will do so by showing *a.s.* boundedness of $\|F(u_{k})\|$ for all $k\geq 0$, using property of $\alpha$-symmetric operators.
To estimate $\|F(u_{k})\|$, we add and subtract $F(v^{*})$, where $v^{*}\in U^{*}$ is an arbitrary but fixed solution, and get

$$ $\|F(u_{k})\|=\|F(u_{k})-F(v^{*})+F(v^{*})\|\leq\|F(u_{k})-F(v^{*})\|+\|F(v^{*})\|.$ $$

Define the following event:

$$ $A=\{\omega\in\Omega:\;\exists\;C(\omega)\in\mathbb{R}\text{ s.t.}\|u_{k}(\omega)-v^{*}\|\leq C(\omega)\;\forall\;k\geq 0\}.$ $$

Based on results of Lemma [3.1](#S3.Thmtheorem1), the sequence $\{\|u_{k}-u^{*}\|\}$ is bounded a.s., and thus $\mathbb{P}(A)=1$. Let $\omega\in A$, now we can estimate $\|F(u_{k}(\omega))\|$ using the $\alpha$-symmetric assumption on the operator.

Case $\alpha\in(0,1)$.

$$ $\displaystyle\|F(u_{k}(\omega))-F(u^{*})\|\leq\|u_{k}(\omega)-v^{*}\|(K_{0}+K_{1}\|F(v^{*})\|^{\alpha}+K_{2}\|u_{k}(\omega)-v^{*}\|^{\alpha/(1-\alpha)}).$ (65) $$

Since $\omega\in A$, it follows that for all $k\geq 0$,

$$ $\|u_{k}(\omega)-v^{*}\|\leq C(\omega).$ $$

Using this fact and equation ([65](#A2.E65)) we obtain that for all $k\geq 0$,

$$ $\displaystyle\|F(u_{k}(\omega))\|\leq C(\omega)(K_{0}+K_{1}\|F(v^{*})\|^{\alpha}+K_{2}C(\omega)^{\alpha/(1-\alpha)})+\|F(v^{*})\|.$ (66) $$

Thus, the sequence {$\|F(u_{k}(\omega))\|$} is upper bounded by some constant $C_{1}(\omega)$. Where $C_{1}(\omega)=C(\omega)(K_{0}+K_{1}\|F(v^{*})\|^{\alpha}+K_{2}C(\omega)^{\alpha/(1-\alpha)})+\|F(v^{*})\|$.

Case $\alpha=1$.

For $\alpha=1$ by Proposition [2.2](#S2.Thmtheorem2) we have

$$ $\displaystyle\|F(u_{k}(\omega))-F(v^{*})\|$ $\displaystyle\leq\|u_{k}(\omega)-v^{*}\|(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}\|u_{k}(\omega)-v^{*}\|).$ (67) $$

We can get the following bound for $\|F(u_{k}(\omega))\|$, for all $k\geq 0$:

$$ $\displaystyle\|F(u_{k}(\omega))\|$ $\displaystyle\leq\|F(u_{k}(\omega))-F(v^{*})\|+\|F(v^{*})\|$ (68) $\displaystyle\leq\|u_{k}(\omega)-v^{*}\|(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}\|u_{k}(\omega)-v^{*}\|)+\|F(v^{*})\|.$ (69) $$

Since $\omega\in A$, the following bound holds for any $k\geq 0$

$$ $\|u_{k}(\omega)-v^{*}\|\leq C(\omega).$ $$

Using these facts and equation ([68](#A2.E68)) for all $k\geq 0$:

$$ $\displaystyle\|F(u_{k}(\omega))\|$ $\displaystyle\leq\|u_{k}(\omega)-v^{*}\|(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}\|u_{k}(\omega)-v^{*}\|)+\|F(v^{*})\|$ (70) $\displaystyle\leq C(\omega)(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}C(\omega))+\|F(v^{*})\|.$ (71) $$

We showed that for all $k\geq 0$ the norm $\|F(u_{k}(\omega))\|$ is upper bounded by some constant $\overline{C}_{1}(\omega)$, where $\overline{C}_{1}(\omega)=C(\omega)(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}C(\omega))+\|F(v^{*})\|$.
Then, for both cases $\alpha\in(0,1)$ and $\alpha=1$ in equations ([66](#A2.E66)),  ([70](#A2.E70)) we showed that $\|F(u_{k}(\omega))\|$ is upper bounded by $\max\{C_{1}(\omega),\overline{C}_{1}(\omega)\}$. Using these results and comparison test it follows that: for all $\omega\in A$,

$$ $\displaystyle\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\|F(u_{k}(\omega))\|+\sigma}\right\}$ $\displaystyle\geq\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\max\{C_{1}(\omega),\overline{C}_{1}(\omega)\}+\sigma}\right\}$ (72) $\displaystyle=\min\left\{1,\frac{1}{\max\{C_{1}(\omega),\overline{C}_{1}(\omega)\}+\sigma}\right\}\sum_{k=0}^{\infty}\beta_{k}$ $\displaystyle=\infty,$ $$

where the last equality holds by the choice of parameters $\beta_{k}$: $\sum_{i=0}^{\infty}\beta_{k}=\infty$.
Since $\mathbb{P}(A)=1$, it follows that

$$ $\mathbb{P}\left(\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\|F(u_{k})\|+\sigma}\right\}=\infty\right)=1.$ $$

Combining this with ([64](#A2.E64)) we obtain

$$ $\mathbb{P}\left(\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]=\infty\right)=1.$ (73) $$

By Lemma [3.1](#S3.Thmtheorem1), we have

$$ $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\,{\rm dist}^{p}(u_{k},U^{*})<\infty.$ (74) $$

Due to $\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]=\infty$ almost surely, it follows that

$$ $\liminf_{k\to\infty}{\rm dist}^{p}(u_{k},U^{*})=0\qquad a.s.$ (75) $$

Since $\|u_{k}-u^{*}\|$ converges a.s. for any given $u^{*}\in U^{*}$, the sequence $\{u_{k}\}$ is bounded a.s. and has accumulation points a.s. Let $\{k_{i}\}$ be an index sequence, such that

$$ $\lim_{i\rightarrow\infty}{\rm dist}^{p}(u_{k_{i}},U^{*})=\liminf_{k\to\infty}{\rm dist}^{p}(u_{k},U^{*})=0\quad\it{a.s.}$ (76) $$

We assume that the sequence $\{u_{k_{i}}\}$ is convergent with a limit point $\bar{u}$; otherwise, we choose a convergent subsequence. Therefore,

$$ $\lim_{i\rightarrow\infty}\|u_{k_{i}}-\bar{u}\|=0\quad\it{a.s.}$ (77) $$

Then, by ([75](#A2.E75)), ${\rm dist}(\bar{u},U^{*})=0$, thus $\bar{u}\in U^{*}$ a.s. since $U^{*}$ is closed. Since the sequence $\{\|u_{k}-u^{*}\|\}$ converges a. s. for all $u^{*}\in U^{*}$, by ([77](#A2.E77)) we have

$$ $\lim_{k\rightarrow\infty}\|u_{k}-\bar{u}\|=0\quad\it{a.s.}$ (78) $$

∎

###### Proof.

### B.3 Proof of Lemma 3.3

###### Proof.

By taking the total expectation in ([49](#A2.E49)) in Lemma [3.1](#S3.Thmtheorem1) and using the definition of the stepsize $\gamma_{k}$,
we obtain for any solution $u^{*}\in U^{*}$ and all $k\geq 0$,

$$ $\displaystyle\mathbb{E}[\|u_{k+1}-u^{*}\|^{2}]$ $\displaystyle\leq\mathbb{E}[\|u_{k}-u^{*}\|^{2}]-2\mu\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})]+3\beta_{k}^{2}(2\sigma^{2}+1).$ (79) $$

The equation ([79](#A2.E79)) satisfies the conditions of Lemma [A.3](#A1.Thmtheorem3) with

$$ $\displaystyle\bar{v}_{k}=\mathbb{E}[\|u_{k}-u^{*}\|^{2}],\quad\bar{a}_{k}=0,\quad\bar{z}_{k}=2\mu\mathbb{E}[\gamma_{k}\,{\rm dist}^{p}(u_{k},U^{*})],\quad\bar{b}_{k}=3\beta_{k}^{2}(2\sigma^{2}+1).$ (80) $$

Thus, by Lemma [A.3](#A1.Thmtheorem3), it follows that the sequence $\{\mathbb{E}[\|u_{k}-u^{*}\|^{2}]\}$ converges to a non-negative scalar for any $u^{*}\in U^{*}$.
Therefore, the sequence $\{\mathbb{E}[\|u_{k}-u^{*}\|^{2}]\}$ is bounded for all $u^{*}\in U^{*}$. Next, using the property of $\alpha$-symmetric operators, we show that $\{\mathbb{E}[\|F(u_{k})\|]\}$ is bounded. Let $v^{*}\in U^{*}$ be an arbitrary, but fixed solution. Then, by the $\alpha$-symmetric property of $F$, we have that

$$ $\displaystyle\|F(u_{k})\|$ $\displaystyle\leq\|F(u_{k})-F(v^{*})\|+\|F(v^{*})\|$ (81) $\displaystyle\leq\|u_{k}-v^{*}\|(K_{0}+K_{1}\|F(v^{*})\|^{\alpha}+K_{2}\|u_{k}-v^{*}\|^{\alpha/(1-\alpha)})+\|F(v^{*})\|.$ $$

Taking expectation, we obtain

$$ $\displaystyle\mathbb{E}[\|F(u_{k})\|]\leq(K_{0}+K_{1}\|F(v^{*})\|^{\alpha})\mathbb{E}[\|u_{k}-v^{*}\|]+K_{2}\mathbb{E}[\|u_{k}-v^{*}\|^{1+\alpha/(1-\alpha)})]+\|F(v^{*})\|.$ (82) $$

Notice, that $\mathbb{E}[\|u_{k}-v^{*}\|^{1+\alpha/(1-\alpha)})]=\mathbb{E}[(\|u_{k}-v^{*}\|^{2})^{1/2(1-\alpha)})]$, and for $\alpha\leq 1/2$, the quantity $1/2(1-\alpha)\leq 1$. Thus, we can apply Jensen inequality for concave function

$$ $\mathbb{E}[(\|u_{k}-v^{*}\|^{2})^{1/2(1-\alpha)})]\leq\mathbb{E}[\|u_{k}-v^{*}\|^{2}]^{1/2(1-\alpha)}.$ $$

Therefore, using these results and Jensen inequality for the first term in equation ([82](#A2.E82)), we obtain

$$ $\displaystyle\mathbb{E}[\|F(u_{k})\|]\leq(K_{0}+K_{1}\|F(v^{*})\|^{\alpha})\mathbb{E}[\|u_{k}-v^{*}\|^{2}]^{1/2}+K_{2}\mathbb{E}[\|u_{k}-v^{*}\|^{2}]^{1/2(1-\alpha)}+\|F(v^{*})\|.$ (83) $$

Since $\mathbb{E}[\|u_{k}-v^{*}\|^{2}]$ is bounded, $\mathbb{E}[\|F(u_{k})\|]$ is bounded by some constant $C_{F}>0$ for all $k\geq 0$.
∎

###### Proof.

### B.4 Proof of Theorem 3.4

###### Proof.

Letting $y=P_{U^{*}}(u_{k})$ in equation ([45](#A2.E45)) in Lemma [3.1](#S3.Thmtheorem1) and using $p$-quasi sharpness we obtain

$$ $\displaystyle\|u_{k+1}-P_{U^{*}}(u_{k})\|^{2}$ $\displaystyle\leq\|u_{k}-P_{U^{*}}(u_{k})\|^{2}-2\mu\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})$ (84) $\displaystyle\quad+2\gamma_{k}\langle e_{k},u_{k}-P_{U^{*}}(u_{k})\rangle+3\beta_{k}^{2}(\|e_{k}\|^{2}+\|e_{k}^{2}\|^{2}+1).$ (85) $$

By the definition of the distance function, we have

$$ ${\rm dist}^{2}(u_{k+1},U^{*})\leq\|u_{k+1}-P_{U^{*}}(u_{k})\|^{2}.$ $$

Thus,

$$ $\displaystyle{\rm dist}^{2}(u_{k+1},U^{*})$ $\displaystyle\leq{\rm dist}^{2}(u_{k},U^{*})-2\mu\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})$ (86) $\displaystyle\quad+2\gamma_{k}\langle e_{k},u_{k}-P_{U^{*}}(u_{k})\rangle+3\beta_{k}^{2}(\|e_{k}\|^{2}+\|e_{k}^{2}\|^{2}+1).$ (87) $$

By Assumption [2.5](#S2.Thmtheorem5) and the law of total expectation, and independence of samples $\xi_{k}$ and $\xi_{k}^{2}$, it follows that

$$ $\displaystyle\mathbb{E}[\gamma_{k}\langle e_{k},u_{k}-P_{U^{*}}(u_{k})\rangle]$ $\displaystyle=\mathbb{E}[\mathbb{E}[\gamma_{k}\langle e_{k},u_{k}-P_{U^{*}}(u_{k})\rangle\mid\mathcal{F}_{k-1}]]$ (88) $\displaystyle=\mathbb{E}[\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\langle\mathbb{E}[e_{k}\mid|\mathcal{F}_{k-1}],u_{k}-P_{U^{*}}(u_{k})\rangle]$ (89) $\displaystyle=0.$ (90) $$

Also, we have $\mathbb{E}[\mathbb{E}[\|e_{k}^{1}\|\mid\mathcal{F}_{k-1}]\leq\sigma^{2}$ and $\mathbb{E}[\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]\leq\sigma^{2}$. Thus, by taking the total expectation in ([86](#A2.E86)), we obtain

$$ $\displaystyle\mathbb{E}[{\rm dist}^{2}(u_{k+1},U^{*})]$ $\displaystyle\leq\mathbb{E}[{\rm dist}^{2}(u_{k},U^{*})]-2\mu\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})]+3\beta_{k}^{2}(2\sigma^{2}+1).$ (91) $$

We aim to upper bound $2\mu\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})]$. To do so consider an event $A_{k}$, defined as follows:

$$ $A_{k}=\{\|F(u_{k})\|+\|e_{k}\|\leq 2(\mathbb{E}[\|F(u_{k})\|]+\mathbb{E}[\|e_{k}\|])\}.$ $$

Then, by the law of total expectation, we obtain

$$ $\displaystyle\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})]=\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})|A_{k}]\mathbb{P}(A_{k})+\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})|\overline{A}_{k}]\mathbb{P}(\overline{A}_{k}),$ (92) $$

where $\overline{A}$ denotes the complement of an event $A$.
We want to provide a lower bound on $\mathbb{P}(A_{k})$. To do so, we upperbound $\mathbb{P}(\overline{A}_{k})$ using Markov’s inequality, as follows:

$$ $\displaystyle\mathbb{P}(\overline{A}_{k})$ $\displaystyle=\mathbb{P}\left(\{\|F(u_{k})\|+\|e_{k}\|>2(\mathbb{E}[\|F(u_{k})\|]+\mathbb{E}[\|e_{k}\|])\}\right)$ (93) $\displaystyle\leq\frac{\mathbb{E}[\|F(u_{k})\|]+\mathbb{E}[\|e_{k}\|]}{2(\mathbb{E}[\|F(u_{k})\|]+\mathbb{E}[\|e_{k}\|])}$ (94) $\displaystyle=\frac{1}{2}.$ (95) $$

Thus,

$$ $\displaystyle\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})]$ $\displaystyle=\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})|A_{k}](1-\mathbb{P}(\overline{A}_{k}))+\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})|\overline{A}_{k}]\mathbb{P}(\overline{A}_{k})$ (96) $\displaystyle\geq\frac{1}{2}\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})|A_{k}]+\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})|\overline{A}_{k}]\mathbb{P}(\overline{A}_{k})$ (97) $\displaystyle\geq\frac{1}{2}\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})|A_{k}].$ (98) $$

By the definition of the event $A_{k}$, we have

$$ $\displaystyle\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})|A_{k}]$ $\displaystyle=\beta_{k}\mathbb{E}\left[\min\left\{1,\frac{1}{\|\Phi(u_{k},\xi_{k})\|}\right\}{\rm dist}^{p}(u_{k},U^{*})|A_{k}\right]$ (99) $\displaystyle\geq\beta_{k}\mathbb{E}\left[\min\left\{1,\frac{1}{\|F(u_{k})\|+\|e_{k}\|}\right\}{\rm dist}^{p}(u_{k},U^{*})|A_{k}]\right]$ (100) $\displaystyle\geq\beta_{k}\min\left\{1,\frac{1}{2(\mathbb{E}[\|F(u_{k})\|]+\mathbb{E}[\|e_{k}\|])}\right\}\mathbb{E}[{\rm dist}^{p}(u_{k},U^{*})|A_{k}].$ (101) $$

By Lemma [3.3](#S3.Thmtheorem3), $\mathbb{E}[\|F(u_{k})\|]\leq C_{F}$ for all $k\geq 0$, and by Assumption [2.5](#S2.Thmtheorem5) and Jensen inequality, we have $\mathbb{E}[\|e_{k}\|]\leq\mathbb{E}[\|e_{k}\|^{2}]^{1/2}\leq\sigma$.
Thus, it follows that

$$ $\displaystyle\mathbb{E}[\gamma_{k}{\rm dist}^{p}(u_{k},U^{*})]\geq\frac{1}{2}\beta_{k}\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}\mathbb{E}[{\rm dist}^{p}(u_{k},U^{*})].$ (102) $$

Combining equations ([91](#A2.E91)) and ([102](#A2.E102)), and using $a=\mu\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}$, we obtain

$$ $\displaystyle\mathbb{E}[{\rm dist}^{2}(u_{k+1},U^{*})]$ $\displaystyle\leq\mathbb{E}[{\rm dist}^{2}(u_{k},U^{*})]-a\beta_{k}\mathbb{E}[{\rm dist}^{p}(u_{k},U^{*})]+3\beta_{k}^{2}(2\sigma^{2}+1).$ (103) $$

Now let $D_{k}=\mathbb{E}[{\rm dist}^{2}(u_{k},U^{*})]$, and consider the following two cases:

Case $p=2$.
When $p=2$, equation ([103](#A2.E103)) satisfies the assumptions of Lemma [A.6](#A1.Thmtheorem6) with

$$ $\displaystyle r_{k}=D_{k},\quad\alpha_{k}=\beta_{k},\quad s_{k}=0,\quad d=a,\quad c=3(2\sigma^{2}+1).$ (104) $$

Then, by Lemma [A.6](#A1.Thmtheorem6),
we get the following convergence rate for all $k\geq 1$,

$$ $\displaystyle D_{k+1}\leq\dfrac{8D_{0}}{k^{2}}+\frac{6(2\sigma^{2}+1)}{a^{2}k}.$ (105) $$

Case $p>2$.
When $p>2$, by applying Jensen inequality, we obtain

$$ $\mathbb{E}[{\rm dist}^{p}(u_{k},U^{*})]=\mathbb{E}\left[\left({\rm dist}^{2}(u_{k},U^{*})\right)^{p/2}\right]\geq\left(\mathbb{E}[{\rm dist}^{2}(u_{k},U^{*})]\right)^{p/2}.$ $$

Thus,
from ([103](#A2.E103)) using $D_{k}=\mathbb{E}[{\rm dist}^{2}(u_{k},U^{*})]$, we get

$$ $\displaystyle D_{k+1}$ $\displaystyle\leq D_{k}-a\beta_{k}\left(D_{k}\right)^{p/2}+3\beta_{k}^{2}(2\sigma^{2}+1).$ (106) $$

By applying telescoping sum to inequality ([106](#A2.E106)) we obtain

$$ $\displaystyle D_{k+1}$ $\displaystyle\leq D_{0}-a\sum_{t=0}^{k}\beta_{t}D_{t}^{p/2}+3(2\sigma^{2}+1)\sum_{t=0}^{k}\beta_{t}^{2}.$ (107) $$

Let $D^{\rm best}_{k}=\min_{t=[0,\ldots,k]}D_{t}$. Then, by rearranging the terms in ([107](#A2.E107)) we obtain

$$ $\displaystyle(D^{\rm best}_{k})^{p/2}\sum_{t=0}^{k}\beta_{t}\leq\sum_{t=0}^{k}\beta_{t}D_{t}^{p/2}$ $\displaystyle\leq\frac{1}{a}\,\left(D_{0}-D_{k+1}+3(2\sigma^{2}+1)\sum_{t=0}^{k}\beta_{t}^{2}\right).$ (108) $$

Since $\beta_{k}=\frac{b}{(k+1)^{q}}$, with $b>0,1>q>1/2$,
then $\{\beta_{k}\}$ satisfies the conditions of Lemma [3.3](#S3.Thmtheorem3). Also, by Lemma [A.7](#A1.Thmtheorem7) the following inequalities hold: for all $k\geq 1,$

$$ $\displaystyle\sum^{k}_{t=0}\beta_{t}\geq\frac{b}{1-q}((k+1)^{1-q}-2^{1-q}),\qquad\quad\sum^{k}_{t=0}\beta_{t}^{2}\leq\frac{b^{2}}{2q-1}.$ (109) $$

Combining equations ([108](#A2.E108)) and  ([109](#A2.E109)), and omitting $D_{k+1}$, we obtain

$$ $\displaystyle(D^{\rm best}_{k})^{p/2}$ $\displaystyle\leq\dfrac{(1-q)\left(D_{0}+3b^{2}(2\sigma^{2}+1)/(2q-1)\right)}{ab\,\left((k+1)^{1-q}-2^{1-q}\right)}.$ (110) $$

Raising both sides of the preceding inequality in power $2/p$, we obtain

$$ $\displaystyle D^{\rm best}_{k}$ $\displaystyle\leq\dfrac{(1-q)^{2/p}\left(D_{0}+3b^{2}(2\sigma^{2}+1)/(2q-1)\right)^{2/p}}{(ab)^{2/p}\,\left((k+1)^{1-q}-2^{1-q}\right)^{2/p}}.$ (111) $$

∎

###### Proof.

## Appendix C Korpelevich Method analysis

###### Lemma C.1 .

Let $U$ be a closed convex set. Then, for the iterate sequences
$\{u_{k}\}$ and $\{h_{k}\}$ generated by the stochastic Korpelevich method ([8](#S2.E8)) and $y\in U$ and $k\geq 0$,

$$ $\displaystyle\|h_{k+1}-y\|^{2}$ $\displaystyle\leq\|h_{k}-y\|^{2}-\|h_{k}-u_{k}\|^{2}-2\gamma_{k}\langle F(u_{k}),u_{k}-y\rangle-2\gamma_{k}\langle e_{k}^{2},u_{k}-y\rangle$ $\displaystyle\ \ +3\gamma_{k}^{2}\|F(h_{k})-F(u_{k})\|^{2}+3\gamma_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}),$ $$

where $e_{k}^{1}=\Phi(h_{k},\xi_{k}^{1})-F(h_{k})$, $e_{k}^{2}=\Phi(u_{k},\xi_{k}^{2})-F(u_{k})$ for all $k\geq 0$.

###### Proof.

Let $k\geq 0$ be arbitrary but fixed. By the definition of $h_{k+1}$ in ([8](#S2.E8)), we have
$\|h_{k+1}-y\|=\|P_{U}(h_{k}-\gamma_{k}\Phi(u_{k},\xi^{2}_{k}))-y\|$ for any $y\in U$. Using the projection inequality,
we obtain for any $y\in U$,

$$ $\displaystyle\|h_{k+1}-y\|^{2}$ $\displaystyle\leq\|h_{k}-\gamma_{k}\Phi(u_{k},\xi^{2}_{k})-y\|^{2}-\|h_{k+1}-h_{k}+\gamma_{k}\Phi(u_{k},\xi^{2}_{k})\|^{2}$ (112) $\displaystyle\leq\|h_{k}-y\|^{2}-\|h_{k+1}-h_{k}\|^{2}+2\gamma_{k}\langle\Phi(u_{k},\xi^{2}_{k}),y-h_{k+1}\rangle.$ $$

Next, we consider the term $\|h_{k+1}-h_{k}\|^{2}$, where we add and subtract $u_{k}$, thus

$$ $\displaystyle\|h_{k+1}-h_{k}\|^{2}$ $\displaystyle=\|h_{k+1}-u_{k}\|^{2}+\|h_{k}-u_{k}\|^{2}-2\langle h_{k+1}-u_{k},h_{k}-u_{k}\rangle.$ (113) $$

Adding and subtracting $2\gamma_{k}\langle\Phi(h_{k},\xi^{1}_{k}),u_{k}-h_{k+1}\rangle$, and combining ([112](#A3.E112)) and ([113](#A3.E113)) we obtain

$$ $\displaystyle\|$ $\displaystyle h_{k+1}-y\|^{2}\leq\|h_{k}-y\|^{2}-\|h_{k+1}-u_{k}\|^{2}-\|h_{k}-u_{k}\|^{2}+2\langle h_{k+1}-u_{k},h_{k}-u_{k}\rangle$ (114) $\displaystyle\ \ +2\gamma_{k}\langle\Phi(u_{k},\xi^{2}_{k}),y-u_{k}+u_{k}-h_{k+1}\rangle+2\gamma_{k}\langle\Phi(h_{k},\xi^{1}_{k})-\Phi(h_{k},\xi^{1}_{k}),u_{k}-h_{k+1}\rangle$ $\displaystyle\leq\|h_{k}-y\|^{2}-\|h_{k+1}-u_{k}\|^{2}-\|h_{k}-u_{k}\|^{2}+2\langle h_{k+1}-u_{k},h_{k}-\gamma_{k}\Phi(h_{k},\xi^{1}_{k})-u_{k}\rangle$ $\displaystyle\ \ +2\gamma_{k}\langle\Phi(u_{k},\xi^{2}_{k}),y-u_{k}\rangle+2\gamma_{k}\langle\Phi(h_{k},\xi^{1}_{k})-\Phi(u_{k},\xi^{2}_{k}),h_{k+1}-u_{k}\rangle.$ $$

Since $u_{k}=P_{U}(h_{k}-\gamma_{k}\Phi(h_{k},\xi_{k}^{1}))$ and $h_{k+1}\in U$, by the projection inequality in ([26](#A1.E26)), it follows that

$$ $2\langle h_{k+1}-u_{k},h_{k}-\gamma_{k}\Phi(h_{k},\xi^{1}_{k})-u_{k}\rangle\leq 0.$ $$

Using Cauchy-Schwarz inequality and relation $2ab\leq a^{2}+b^{2}$ for $a,b\in\mathbb{R}$, we obtain

$$ $\displaystyle 2\gamma_{k}\langle\Phi(h_{k},\xi^{1}_{k})-\Phi(u_{k},\xi^{2}_{k}),h_{k+1}-u_{k}\rangle$ $\displaystyle\leq 2\gamma_{k}\|\Phi(h_{k},\xi^{1}_{k})-\Phi(u_{k},\xi^{2}_{k})\|\|h_{k+1}-u_{k}\|$ $\displaystyle\leq\gamma_{k}^{2}\|\Phi(h_{k},\xi^{1}_{k})-\Phi(u_{k},\xi^{2}_{k})\|^{2}+\|h_{k+1}-u_{k}\|^{2}.$ $$

Using triangle inequality and relation $(\sum_{i=1}^{m}a_{i})^{2}\leq m\sum_{i=1}^{m}a_{i}^{2}$ we get

$$ $\displaystyle\|\Phi(h_{k},\xi^{1}_{k})-\Phi(u_{k},\xi^{2}_{k})\|^{2}$ $\displaystyle=\|\Phi(h_{k},\xi^{1}_{k})-F(h_{k})+F(h_{k})-F(u_{k})+F(u_{k})-\Phi(u_{k},\xi^{2}_{k})\|^{2}$ $\displaystyle\leq 3(\|e_{k}^{1}\|^{2}+\|F(h_{k})-F(u_{k})\|^{2}+\|e_{k}^{2}\|^{2}).$ $$

Combining the preceding three estimates with ([114](#A3.E114)), we get the stated relation

$$ $\displaystyle\|h_{k+1}-y\|^{2}$ $\displaystyle\leq\|h_{k}-y\|^{2}-\|h_{k}-u_{k}\|^{2}-2\gamma_{k}\langle F(u_{k}),u_{k}-y\rangle-2\gamma_{k}\langle e_{k}^{2},u_{k}-y\rangle$ $\displaystyle\ \ +3\gamma_{k}^{2}\|F(h_{k})-F(u_{k})\|^{2}+3\gamma_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}).$ $$

∎

###### Lemma C.1 .

###### Proof.

### C.1 Proof of Lemma 4.1

###### Proof.

By Lemma [C.1](#A3.Thmtheorem1) we have for all $k\geq 0$ and for all $y\in U$,

$$ $\displaystyle\|h_{k+1}-y\|^{2}$ $\displaystyle\leq\|h_{k}-y\|^{2}-\|h_{k}-u_{k}\|^{2}-2\gamma_{k}\langle F(u_{k}),u_{k}-y\rangle-2\gamma_{k}\langle e_{k}^{2},u_{k}-y\rangle$ (115) $\displaystyle\ \ +3\gamma_{k}^{2}\|F(h_{k})-F(u_{k})\|^{2}+3\gamma_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}),$ $$

with $e_{k}^{1}=\Phi(h_{k},\xi_{k}^{1})-F(h_{k})$ and $e_{k}^{2}=\Phi(u_{k},\xi_{k}^{2})-F(u_{k})$ for all $k\geq 0$.
We want to estimate the term $\|F(h_{k})-F(h_{k-1})\|^{2}$ on the LHS of the inequality using the fact that $F(\cdot)$ is an $\alpha$-symmetric operator for two cases (a) $\alpha\in(0,1)$ and (b) $\alpha=1$.

Case $\alpha\in(0,1)$.
Using the alternative characterization of $\alpha$-symmetric operators from Proposition [2.2](#S2.Thmtheorem2)(a) (as given in  ([4](#S2.E4))), when $\alpha\in(0,1)$, the next inequality holds for any $k\geq 0$,

$$ $\displaystyle\|F(h_{k})-F(u_{k})\|\leq\|h_{k}-u_{k}\|(K_{0}+K_{1}\|F(h_{k})\|^{\alpha}+K_{2}\|h_{k}-u_{k}\|^{\alpha/(1-\alpha)}).$ (116) $$

We want to separate $\|F(h_{k})\|$ into two parts: stochastic approximation of operator $\Phi(h_{k},\xi_{k}^{1})$ and error $e_{k}^{1}$. Recall that $e_{k}^{1}=F(h_{k})-\Phi(h_{k},\xi_{k}^{1})$, then based on triangle inequality $\|F(h_{k})\|\leq\|\Phi(h_{k},\xi_{k}^{1})\|+\|e_{k}^{1}\|$, and since $\alpha\leq 1$ we obtain

$$ $\displaystyle\|F(h_{k})\|^{\alpha}\leq\|\Phi(h_{k},\xi_{k}^{1})\|^{\alpha}+\|e_{k}^{1}\|^{\alpha}.$ (117) $$

Thus, combining this fact with ([116](#A3.E116)) we get the following estimation

$$ $\displaystyle\|F(h_{k})-F(u_{k})\|\leq\|h_{k}-u_{k}\|(K_{0}+K_{1}\|\Phi(h_{k},\xi_{k}^{1})\|^{\alpha}+K_{1}\|e_{k}^{1}\|^{\alpha}+K_{2}\|h_{k}-u_{k}\|^{\alpha/(1-\alpha)}).$ (118) $$

By the projection property ([27](#A1.E27)) and the stepsize choice ([17](#S4.E17)), we have

$$ $\displaystyle\|h_{k}-u_{k}\|\leq\gamma_{k}\|\Phi(h_{k},\xi_{k}^{1})\|=\beta_{k}\min\{1,\frac{1}{\|\Phi(h_{k},\xi_{k}^{1})\|}\}\|\Phi(h_{k},\xi_{k}^{1})\|\leq\beta_{k}\leq 1.$ (119) $$

Then, $K_{2}\|h_{k}-u_{k}\|^{\alpha/(1-\alpha)}\leq K_{2}$, and

$$ $\displaystyle\gamma_{k}\|F(h_{k})$ $\displaystyle-F(u_{k})\|\leq\gamma_{k}(K_{0}+K_{1}\|\Phi(h_{k},\xi_{k}^{1})\|^{\alpha}+K_{1}\|e_{k}^{1}\|^{\alpha}+K_{2})\|h_{k}-u_{k}\|$ (120) $\displaystyle\leq\beta_{k}(K_{0}\min\{1,\frac{1}{\|\Phi(h_{k},\xi_{k}^{1})\|}\}+K_{1}\min\{1,\frac{1}{\|\Phi(h_{k},\xi_{k}^{1})\|}\}\|\Phi(h_{k},\xi_{k}^{1})\|^{\alpha})\|h_{k}-u_{k}\|$ $\displaystyle\ \ +\beta_{k}(K_{1}\|e_{k}^{1}\|^{\alpha}+K_{2}\min\{1,\frac{1}{\|\Phi(h_{k},\xi_{k}^{1})\|}\})\|h_{k}-u_{k}\|$ $\displaystyle\leq\beta_{k}(K_{0}+K_{1}+K_{2})\|h_{k}-u_{k}\|+\beta_{k}K_{1}\|e_{k}^{1}\|^{\alpha}\|h_{k}-u_{k}\|.$ $$

By inequality ([119](#A3.E119)), we have $\|h_{k}-u_{k}\|\leq 1$, and using this estimate in equation ([120](#A3.E120)) we obtain

$$ $\displaystyle\gamma_{k}\|F(h_{k})-F(u_{k})\|$ $\displaystyle\leq\beta_{k}(K_{0}+K_{1}+K_{2})\|h_{k}-u_{k}\|+\beta_{k}K_{1}\|e_{k}^{1}\|^{\alpha}.$ (121) $$

Case $\alpha=1$.
Based on the alternative characterization of $\alpha$-symmetric operators from Proposition [2.2](#S2.Thmtheorem2)(b) (as given in  ([17](#S4.E17))), when $\alpha=1$, the following inequality holds for any $k\geq 0$,

$$ $\displaystyle\|F(h_{k})-F(u_{k})\|$ $\displaystyle\leq\|h_{k}-u_{k}\|(L_{0}+L_{1}\|\Phi(h_{k},\xi_{k}^{1})\|)\exp(L_{1}\|h_{k}-u_{k}\|).$ (122) $$

We upperbound $\|F(h_{k})\|$ using equation ([117](#A3.E117)) and get

$$ $\displaystyle\|F(h_{k})-F(u_{k})\|$ $\displaystyle\leq\|h_{k}-u_{k}\|(L_{0}+L_{1}\|F(h_{k})\|+L_{1}\|e_{k}^{1}\|)\exp(L_{1}\|h_{k}-u_{k}\|).$ (123) $$

Note that relation in ([119](#A3.E119)) holds irrespective of the value of $\alpha$. Thus, since $\|h_{k}-u_{k}\|\leq 1$,
we have $\exp(L_{1}\|h_{k}-u_{k}\|)\leq\exp(L_{1}\beta_{k})$, and we obtain

$$ $\displaystyle\gamma_{k}\|F(h_{k})-F(u_{k})\|$ $\displaystyle\leq\gamma_{k}(L_{0}+L_{1}\|\Phi(h_{k},\xi_{k}^{1})\|+L_{1}\|e_{k}^{1}\|)\exp(L_{1}\beta_{k})\|h_{k}-u_{k}\|$ (124) $\displaystyle=\exp(L_{1}\beta_{k})L_{0}\beta_{k}\min\{1,\frac{1}{\|\Phi(h_{k},\xi_{k}^{1})\|}\}\|h_{k}-u_{k}\|$ $\displaystyle\ \ +\exp(L_{1}\beta_{k})L_{1}\beta_{k}\min\{1,\frac{1}{\|\Phi(h_{k},\xi_{k}^{1})\|}\}\|\Phi(h_{k},\xi_{k}^{1})\|\|h_{k}-u_{k}\|$ $\displaystyle\ \ +\exp(L_{1}\beta_{k})L_{1}\beta_{k}\min\{1,\frac{1}{\|\Phi(h_{k},\xi_{k}^{1})\|}\}\|e_{k}^{1}\|\|h_{k}-u_{k}\|$ $\displaystyle\leq\exp(L_{1}\beta_{k})\beta_{k}(L_{0}+L_{1}+L_{1}\|e_{k}^{1}\|)\|h_{k}-u_{k}\|.$ $$

By inequality ([119](#A3.E119)), we have $\|h_{k}-u_{k}\|\leq 1$. Using this estimate in ([124](#A3.E124)), we furher obtain

$$ $\displaystyle\gamma_{k}\|F(h_{k})-F(u_{k})\|$ $\displaystyle\leq\exp(L_{1}\beta_{k})\beta_{k}(L_{0}+L_{1})\|h_{k}-u_{k}\|+\exp(L_{1}\beta_{k})\beta_{k}\|e_{k}^{1}\|.$ (125) $$

Now, we are done with the cases of $\alpha$ values. Let

$$ $\displaystyle C_{a}(\beta_{k},\alpha)=\begin{cases}(K_{0}+K_{1}+K_{2}),\quad\text{when }\alpha\in(0,1),\\ \exp(L_{1}\beta_{k})(L_{0}+L_{1}),\quad\text{when }\alpha=1.\end{cases}$ (126) $$

Also, define

$$ $\displaystyle C_{e}(\beta_{k},\alpha)=\begin{cases}K_{1},\quad\text{when }\alpha\in(0,1),\\ \exp(L_{1}\beta_{k}),\quad\text{when }\alpha=1.\end{cases}$ (127) $$

Then, by inequality $(\sum_{i=1}^{m}a_{i})^{2}\leq m\sum_{i=1}^{m}a_{i}^{2}$, for both cases we have

$$ $\displaystyle\gamma_{k}^{2}\|F(h_{k})-F(u_{k})\|^{2}\leq 2\beta_{k}^{2}C_{a}(\beta_{k},\alpha)^{2}\|h_{k}-u_{k}\|^{2}+2\beta_{k}^{2}C_{e}(\beta_{k},\alpha)^{2}\|e_{k}^{1}\|^{2\alpha}.$ (128) $$

Combining preceding inequality with ([115](#A3.E115)) we obtain that for any $k\geq 0$,

$$ $\displaystyle\|h_{k+1}-y\|^{2}$ $\displaystyle\leq\|h_{k}-y\|^{2}-(1-6\beta_{k}^{2}C_{a}(\beta_{k},\alpha)^{2})\|h_{k}-u_{k}\|^{2}-2\gamma_{k}\langle F(u_{k}),u_{k}-y\rangle$ (129) $\displaystyle\ \ -2\gamma_{k}\langle e_{k}^{2},u_{k}-y\rangle+6\beta_{k}^{2}C_{e}(\beta_{k},\alpha)^{2}\|e_{k}^{1}\|^{2\alpha}+3\gamma_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}).$ $$

Next, we plug $y=u^{*}$, where $u^{*}\in U^{*}$ is an arbitrary solution and use $p$-quasi sharpness of the operator $F$ to obtain

$$ $\displaystyle\|h_{k+1}-u^{*}\|^{2}$ $\displaystyle\leq\|h_{k}-u^{*}\|^{2}-(1-6\beta_{k}^{2}C_{a}(\beta_{k},\alpha)^{2})\|h_{k}-u_{k}\|^{2}-2\gamma_{k}\mu{\rm dist}^{p}(u_{k},U^{*})$ (130) $\displaystyle\ \ -2\gamma_{k}\langle e_{k}^{2},u_{k}-u^{*}\rangle+6\beta_{k}^{2}C_{e}(\beta_{k},\alpha)^{2}\|e_{k}^{1}\|^{2\alpha}+3\gamma_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}).$ $$

By the stepsize choice $\gamma_{k}\leq\beta_{k}$, thus

$$ $\displaystyle\|h_{k+1}-u^{*}\|^{2}$ $\displaystyle\leq\|h_{k}-u^{*}\|^{2}-(1-6\beta_{k}^{2}C_{a}(\beta_{k},\alpha)^{2})\|h_{k}-u_{k}\|^{2}-2\gamma_{k}\mu{\rm dist}^{p}(u_{k},U^{*})$ (131) $\displaystyle\ \ -2\gamma_{k}\langle e_{k}^{2},u_{k}-u^{*}\rangle+6\beta_{k}^{2}C_{e}(\beta_{k},\alpha)^{2}\|e_{k}^{1}\|^{2\alpha}+3\beta_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}).$ $$

Since $\sum_{k=0}^{\infty}\beta_{k}^{2}<\infty$, it follows that $\beta_{k}\to 0$. By definitions of $C_{a}(\beta_{k},\alpha)$ and $C_{e}(\beta_{k},\alpha)$ in ([126](#A3.E126)) and ([127](#A3.E127)), respectively, there exists $N\geq 0$ such that the stepsizes satisfy $1-6\beta_{k}^{2}C_{a}(\beta_{k},\alpha)^{2}\geq\frac{1}{2}$ and $C_{e}(\beta_{k},\alpha)^{2}\leq\max\{K_{1},\exp(L_{1},\beta_{k})\}\leq\max\{K_{1},2\}$. Thus, the following inequality holds for any $k\geq N$,

$$ $\displaystyle\|h_{k+1}-u^{*}\|^{2}$ $\displaystyle\leq\|h_{k}-u^{*}\|^{2}-\frac{1}{2}\|h_{k}-u_{k}\|^{2}-2\gamma_{k}\mu{\rm dist}^{p}(u_{k},U^{*})$ (132) $\displaystyle\ \ -2\gamma_{k}\langle e_{k}^{2},u_{k}-u^{*}\rangle+3\beta_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}+2\max\{K_{1},2\}\|e_{k}^{1}\|^{2\alpha}).$ $$

Recalling that $e_{k}^{1}=\Phi(h_{k},\xi_{k}^{1})-F(h_{k}),\;e_{k}^{2}=\Phi(u_{k},\xi_{k}^{2})-F(u_{k})$ and
using the stochastic properties of $\xi_{k}^{1},\xi_{k}^{2}$ imposed by Assumption [2.5](#S2.Thmtheorem5) and method’s updates, we have

$$ $\mathbb{E}[\gamma_{k}\langle e_{k}^{2},u_{k}-u^{*}\rangle\mid\mathcal{F}_{k-1}]=\mathbb{E}[\gamma_{k}\mathbb{E}[\langle e_{k}^{2},u_{k}-u^{*}\rangle\mid\mathcal{F}_{k-1}\cup\{\xi_{k}^{1}\}]\mid\mathcal{F}_{k-1}]=0,$ $$

since stepsize $\gamma_{k}$ is measurable in $\mathcal{F}_{k-1}\cup\{\xi_{k}^{1}\}$. Also, it holds that for all $k\geq 0$,

$$ $\mathbb{E}[\mathbb{E}[\|e_{k}^{2}\|^{2}\mid\mathcal{F}_{k-1}\cup\{\xi_{k}^{1}\}]|\mathcal{F}_{k-1}]\leq\sigma^{2},\quad\text{and}\quad\mathbb{E}[\|e_{k}^{1}\|^{2}\mid\mathcal{F}_{k-1}]\leq\sigma^{2}.$ $$

Moreover, since $\alpha\leq 1$, the conditional expectation $\mathbb{E}[\|e_{k}^{1}\|^{2\alpha}|\mathcal{F}_{k-1}]$ is finite, and by Jensen inequality, it follows that for all $k\geq 0$,

$$ $\mathbb{E}[\|e_{k}^{1}\|^{2\alpha}|\mathcal{F}_{k-1}]\leq\sigma^{2\alpha}.$ $$

Therefore, by taking the conditional expectation on $\mathcal{F}_{k-1}$
in relation ([132](#A3.E132)), we obtain
for all $u^{*}\in U^{*}$ and for all $k\geq N$,

$$ $\displaystyle\mathbb{E}[\|h_{k+1}-u^{*}\|^{2}|\mathcal{F}_{k-1}]$ $\displaystyle\leq\|h_{k}-u^{*}\|^{2}-\frac{1}{2}\|h_{k}-u_{k}\|^{2}-2\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\mu{\rm dist}^{p}(u_{k},U^{*})$ (133) $\displaystyle\ \ +6\beta_{k}^{2}(\sigma^{2}+\max\{K_{1},2\}\sigma^{2\alpha}).$ $$

By Lemma [A.2](#A1.Thmtheorem2), it follows that the sequence $\{\|h_{k}-u^{*}\|^{2}\}$ converges a.s. to a non-negative scalar for any $u^{*}\in U^{*}$, and almost surely we have

$$ $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\,{\rm dist}^{p}(u_{k},U^{*})<\infty,\quad\sum_{k=0}^{\infty}\|h_{k}-u_{k}\|^{2}<\infty.$ (134) $$

Since the sequence $\{\|h_{k}-u^{*}\|^{2}\}$
converges a.s. for all $u^{*}\in U^{*}$, it follows that the sequence $\{\|h_{k}-u^{*}\|\}$ is bounded a.s. for all $u^{*}\in U^{*}$.
∎

###### Proof.

### C.2 Proof of Theoreom 4.2

###### Proof.

By Lemma [4.1](#S4.Thmtheorem1), we almost surely have

$$ $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]\,{\rm dist}^{p}(u_{k},U^{*})<\infty.$ (135) $$

The structure of the stepsizes $\gamma_{k}$ ([17](#S4.E17)) for the Korpelevich method is similar to the stepsizes sequence for the projection method. Following the proof of Theorem [3.2](#S3.Thmtheorem2) we obtain

$$ $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathbb{F}_{k-1}]=\infty\quad\it{a.s.}$ (136) $$

We provide the full proof of this result below, in spite of the fact it is equivalent to the proof of the same result in Theorem [3.2](#S3.Thmtheorem2).

Firstly, we provide a sequence of lower bounds on $\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]$. First, consider the following event:

$$ $A_{k}=\{\|e_{k}^{1}\|\leq 2\mathbb{E}[\|e_{k}^{1}\|\mid\mathcal{F}_{k-1}]\},$ $$

where $e_{k}^{1}=F(h_{k})-\Phi(h_{k},\xi_{k}^{1})$ is a stochastic error from the sample for the clipping stepsize $\gamma_{k}$. Then, by the law of total expectation

$$ $\displaystyle\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]=\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}]\mathbb{P}(A_{k}\mid\mathcal{F}_{k-1})+\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup\overline{A}_{k}]\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1}).$ (137) $$

We want to provide a lower bound on $\mathbb{P}(A_{k}\mid\mathcal{F}_{k-1})$, to do so, we upperbound $\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1})$ using Markov’s inequality and Assumption [2.5](#S2.Thmtheorem5):

$$ $\displaystyle\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1})=\mathbb{P}(\|e_{k}^{1}\|>2\mathbb{E}[\|e_{k}^{1}\|\mid\mathcal{F}_{k-1}]\})\leq\frac{\mathbb{E}[\|e_{k}^{1}\|\mid\mathcal{F}_{k-1}]}{2\mathbb{E}[\|e_{k}^{1}\|\mid\mathcal{F}_{k-1}])}=\frac{1}{2}.$ (138) $$

Thus,

$$ $\displaystyle\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]$ $\displaystyle=\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}](1-\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1}))+\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup\overline{A}_{k}]\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1})$ (139) $\displaystyle\geq\frac{1}{2}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}]+\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup\overline{A}_{k}]\mathbb{P}(\overline{A}_{k}\mid\mathcal{F}_{k-1})$ (140) $\displaystyle\geq\frac{1}{2}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}].$ (141) $$

By the definition of $\gamma_{k}$ and the triangle inequality, we have

$$ $\displaystyle\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}]$ $\displaystyle=\beta_{k}\mathbb{E}[\min\left\{1,\frac{1}{\|\Phi(h_{k},\xi_{k}^{2})\|}\right\}\mid\mathcal{F}_{k-1}\cup A_{k}]$ (142) $\displaystyle\geq\beta_{k}\mathbb{E}\left[\min\left\{1,\frac{1}{\|F(h_{k})\|+\|e_{k}^{2}\|}\right\}\mid\mathcal{F}_{k-1}\cup A_{k}\right].$ (143) $$

Next, we use the definition of the event $A_{k}$ and obtain the following lower bound:

$$ $\displaystyle\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}\cup A_{k}]$ $\displaystyle\geq\beta_{k}\mathbb{E}[\min\left\{1,\frac{1}{\|F(h_{k})\|+2\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]}\right\}\mid\mathcal{F}_{k-1}\cup A_{k}]$ (145) $\displaystyle\geq\beta_{k}\mathbb{E}[\min\left\{1,\frac{1}{\|F(h_{k})\|+2\sigma}\right\}\mid\mathcal{F}_{k-1}\cup A_{k}]$ (146) $\displaystyle=\beta_{k}\min\left\{1,\frac{1}{\|F(h_{k})\|+2\sigma}\right\}.$ (147) $$

The first inequality in the preceding equation holds by the definition of the event $A_{k}=\{\|e_{k}^{2}\|\leq 2\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]\}$, while the second inequality holds due to Assumption [2.5](#S2.Thmtheorem5) on the $\xi$-samples and Jensen inequality, $\mathbb{E}[\|e_{k}^{2}\|\mid\mathcal{F}_{k-1}]\leq\sqrt{\mathbb{E}[\|e_{k}^{2}\|^{2}\mid\mathcal{F}_{k-1}]}\leq\sigma$.
Hence, we have that

$$ $\displaystyle\sum_{k=0}^{\infty}\frac{1}{2}\beta_{k}\min\left\{1,\frac{1}{\|F(h_{k})\|+2\sigma}\right\}\leq\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}].$ (148) $$

Now, we want to show that $\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\|F(h_{k})\|+2\sigma}\right\}$ is not summable almost surely, i.e. $\mathbb{P}(\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\|F(h_{k})\|+2\sigma}\right\}=\infty)=1$.
We will do so by showing *a.s.* boundedness of $\|F(h_{k})\|$ for all $k\geq 0$, using property of $\alpha$-symmetric operators. To estimate $\|F(h_{k})\|$, we add and subtract $F(v^{*})$, where $v^{*}\in U^{*}$ is an arbitrary but fixed solution, and get

$$ $\|F(h_{k})\|=\|F(h_{k})-F(v^{*})+F(v^{*})\|\leq\|F(h_{k})-F(v^{*})\|+\|F(v^{*})\|.$ $$

Define the following event:

$$ $A=\{\omega\in\Omega:\;\exists\;C(\omega)\in\mathbb{R}\text{ s.t.}\|h_{k}(\omega)-v^{*}\|<C(\omega)\;\forall\;k\geq 0\}.$ $$

Based on Lemma [4.1](#S4.Thmtheorem1), the sequence $\{\|h_{k}-v^{*}\|\}$ is bounded a.s., and thus $\mathbb{P}(A)=1$. Let $\omega\in A$, now we can estimate $\|F(h_{k}(\omega))\|$ using the $\alpha$-symmetric assumption on the operator.

Case $\alpha\in(0,1)$.

$$ $\displaystyle\|F(h_{k}(\omega))-F(u^{*})\|\leq\|h_{k}(\omega)-v^{*}\|(K_{0}+K_{1}\|F(v^{*})\|^{\alpha}+K_{2}\|h_{k}(\omega)-v^{*}\|^{\alpha/(1-\alpha)}).$ (149) $$

Since $\omega\in A$, it follows that
$\|h_{k}(\omega)-v^{*}\|\leq C(\omega)$ for all $k\geq 0$.
Using this fact and ([149](#A3.E149)) we obtain that for all $k\geq 0$,

$$ $\displaystyle\|F(h_{k}(\omega))\|\leq C(\omega)(K_{0}+K_{1}\|F(v^{*})\|^{\alpha}+K_{2}C(\omega)^{\alpha/(1-\alpha)})+\|F(v^{*})\|.$ (150) $$

Therefore, the sequence {$\|F(h_{k}(\omega))\|$} is upper bounded by $C_{1}(\omega)=C(\omega)(K_{0}+K_{1}\|F(v^{*})\|^{\alpha}+K_{2}C(\omega)^{\alpha/(1-\alpha)})+\|F(v^{*})\|$.

Case $\alpha=1$.

For $\alpha=1$ by Proposition [2.2](#S2.Thmtheorem2) we have

$$ $\displaystyle\|F(h_{k}(\omega))-F(v^{*})\|$ $\displaystyle\leq\|h_{k}(\omega)-v^{*}\|(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}\|h_{k}(\omega)-v^{*}\|).$ (151) $$

Therefore, for all $k\geq 0$,

$$ $\displaystyle\|F(h_{k}(\omega))\|$ $\displaystyle\leq\|F(h_{k}(\omega))-F(v^{*})\|+\|F(v^{*})\|$ (152) $\displaystyle\leq\|h_{k}(\omega)-v^{*}\|(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}\|h_{k}(\omega)-v^{*}\|)+\|F(v^{*})\|.$ (153) $$

Since $\omega\in A$, we have
$\|h_{k}(\omega)-v^{*}\|\leq C(\omega)$ for all $k\geq 0$,
which when used in ([152](#A3.E152)), implies that for all $k\geq 0$,

$$ $\displaystyle\|F(h_{k}(\omega))\|$ $\displaystyle\leq\|h_{k}(\omega)-v^{*}\|(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}\|h_{k}(\omega)-v^{*}\|)+\|F(v^{*})\|$ (154) $\displaystyle\leq C(\omega)(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}C(\omega))+\|F(v^{*})\|.$ (155) $$

Hence, the sequence
$\{\|F(h_{k}(\omega))\|\}$ is upper bounded by $\overline{C}_{1}(\omega)$, where $\overline{C}_{1}(\omega)=C(\omega)(L_{0}+L_{1}\|F(v^{*})\|)\exp(L_{1}C(\omega))+\|F(v^{*})\|$.

Now, for both cases $\alpha\in(0,1)$ and $\alpha=1$ in ([150](#A3.E150)) and ([154](#A3.E154)), respectively, we have that $\|F(h_{k}(\omega))\|$ is upper bounded by $\max\{C_{1}(\omega),\overline{C}_{1}(\omega)\}$. Using this and a comparison test, we obtain

$$ $\displaystyle\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\|F(h_{k}(\omega))\|+2\sigma}\right\}$ $\displaystyle\geq\sum_{k=0}^{\infty}\beta_{k}\min\left\{1,\frac{1}{\max\{C_{1}(\omega),\overline{C}_{1}(\omega)\}+2\sigma}\right\}$ (156) $\displaystyle=\min\left\{1,\frac{1}{\max\{C_{1}(\omega),\overline{C}_{1}(\omega)\}+2\sigma}\right\}\sum_{k=0}^{\infty}\beta_{k}$ $\displaystyle=\infty,$ $$

where the last equality holds by $\sum_{i=0}^{\infty}\beta_{k}=\infty$. Thus,

$$ $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]=\infty\quad\it{a.s.}$ (157) $$

Since, $\sum_{k=0}^{\infty}\mathbb{E}[\gamma_{k}\mid\mathcal{F}_{k-1}]=\infty$ almost surely, from ([135](#A3.E135)) it follows that

$$ $\liminf_{k\rightarrow\infty}{\rm dist}^{p}(u_{k},U^{*})=0\quad\text{\it a.s.}$ (158) $$

By Lemma [4.1](#S4.Thmtheorem1), the sequence $\{\|h_{k}-u^{*}\|\}$
converges a.s. for any given $u^{*}\in U^{*}$.
Thus, the sequence $\{h_{k}\}$ is bounded a.s. and, consequently,
it has accumulation points a.s.
In view of relation ([21](#S4.E21)) in Lemma [4.1](#S4.Thmtheorem1), it follows that

$$ $\displaystyle\lim_{k\to\infty}\|h_{k}-u_{k}\|=0\qquad\hbox{a.s.}$ (159) $$

Therefore,
the sequences $\{u_{k}\}$ and $\{h_{k}\}$ have the same accumulation points a.s.

Now, let $\{k_{i}\mid i\geq 1\}$ be a (random) index sequence such that

$$ $\lim_{i\to\infty}{\rm dist}^{p}(u_{k_{i}},U^{*})=\liminf_{k\to\infty}{\rm dist}^{p}(u_{k},U^{*})=0\quad{\it a.s.}$ (160) $$

Without loss of generality, we may assume that $\{h_{k_{i}}\}$ is a convergent sequence (for otherwise, we will select a convergent subsequence), and let $\bar{u}$ be its (random) limit point, i.e.,

$$ $\lim_{i\to\infty}\|h_{k_{i}}-\bar{u}\|=0\qquad{\it a.s.}$ (161) $$

By relation ([21](#S4.E21)), it follows that
$\lim_{k\to\infty}\|h_{k}-u_{k}\|=0$ a.s., which in view of the preceding relation implies that

$$ $\lim_{i\to\infty}\|u_{k_{i}}-\bar{u}\|=0\qquad{\it a.s.}$ $$

By continuity of the distance function ${\rm dist}(\cdot,U^{*})$, from relation ([160](#A3.E160)) we conclude that ${\rm dist}(\bar{u},U^{*})=0$ a.s., which implies that $\bar{u}\in U^{*}$ almost surely since the set $U^{*}$ is closed.
Since the sequence $\{\|h_{k}-u^{*}\|^{2}\}$
converges a.s. for any $u^{*}\in U^{*}$, it follows that
$\lim_{k\to\infty}\|h_{k}-\bar{u}\|=0$ a.s.
By relation ([159](#A3.E159)) we conclude that
$\lim_{k\to\infty}\|u_{k}-\bar{u}\|=0$ a.s.
∎

###### Proof.

### C.3 Proof of Lemma 4.3

###### Proof.

The choice of parameters $\beta_{k}$, ensures that $1-6\beta_{k}^{2}(K_{0}+K_{1}+K_{3})^{2}\geq 1/2$. Then, by taking the expectation in ([20](#S4.E20)) of Lemma [4.1](#S4.Thmtheorem1) and using Assumption [2.5](#S2.Thmtheorem5), and definition of $C_{e}(\beta_{k},\alpha)=K_{1}$ for $\alpha\in(0,1)$, we obtain

$$ $\displaystyle\mathbb{E}[\|h_{k+1}-u^{*}\|^{2}]$ $\displaystyle\leq\mathbb{E}[\|h_{k}-u^{*}\|^{2}]-\frac{1}{2}\mathbb{E}[\|h_{k}-u_{k}\|^{2}]-2\mathbb{E}[\gamma_{k}\mu{\rm dist}^{p}(u_{k},U^{*})]$ (162) $\displaystyle\quad+6\beta_{k}^{2}(\sigma^{2}+K_{1}\sigma^{2\alpha}).$ $$

The equation ([162](#A3.E162)) satisfies the condition of Lemma [A.3](#A1.Thmtheorem3) with

$$ $\displaystyle\bar{v}_{k}=\mathbb{E}[\|u_{k}-u^{*}\|^{2}],\quad\bar{a}_{k}=0,\quad\bar{b}_{k}=6\beta_{k}^{2}(\sigma^{2}+K_{1}\sigma^{2\alpha}),$ (163) $\displaystyle\bar{z}_{k}=2\mu\mathbb{E}[\gamma_{k}\,{\rm dist}^{p}(u_{k},U^{*})]+\frac{1}{2}\mathbb{E}[\|h_{k}-u_{k}\|^{2}].$ (164) $$

By Lemma [A.2](#A1.Thmtheorem2), it follows that the sequence $\mathbb{E}[\|h_{k}-u^{*}\|^{2}]$ converges to a non-negative scalar for any $u^{*}\in U^{*}$.
Since the sequence $\{\mathbb{E}[\|h_{k}-u^{*}\|^{2}]\}$
converges for all $u^{*}\in U^{*}$, it follows that the sequence $\{\mathbb{E}[\|h_{k}-u^{*}\|^{2}]\}$ is bounded for all $u^{*}\in U^{*}$. Next, using property of $\alpha$-symmetric operators, we show that $\mathbb{E}[\|F(h_{k})\|]$ is bounded for all $k\geq 0$. Let $v^{*}\in U^{*}$ be an arbitrary but fixed solution. Since $\alpha\leq 1/2$, it holds that

$$ $\displaystyle\|F(h_{k})\|$ $\displaystyle\leq\|F(h_{k})-F(v^{*})\|+\|F(v^{*})\|$ (165) $\displaystyle\leq\|h_{k}-v^{*}\|(K_{0}+K_{1}\|F(v^{*})\|^{\alpha}+K_{2}\|h_{k}-v^{*}\|^{\alpha/(1-\alpha)})+\|F(v^{*})\|.$ $$

Taking the expectation, we obtain

$$ $\displaystyle\mathbb{E}[\|F(h_{k})\|]\leq(K_{0}+K_{1}\|F(v^{*})\|^{\alpha})\mathbb{E}[\|h_{k}-v^{*}\|]+K_{2}\mathbb{E}[\|h_{k}-v^{*}\|^{1+\alpha/(1-\alpha)})]+\|F(v^{*})\|.$ (166) $$

Notice that $\mathbb{E}[\|h_{k}-v^{*}\|^{1+\alpha/(1-\alpha)})]=\mathbb{E}[(\|h_{k}-v^{*}\|^{2})^{1/2(1-\alpha)})]$ and, for $\alpha\leq 1/2$, the quantity $1/2(1-\alpha)\leq 1$. Thus, we can apply Jensen inequality for concave function

$$ $\mathbb{E}[(\|h_{k}-v^{*}\|^{2})^{1/2(1-\alpha)})]\leq\mathbb{E}[\|h_{k}-v^{*}\|^{2}]^{1/2(1-\alpha)}.$ $$

Therefore, using the preceding relation and Jensen inequality for the first term on the RHS of equation ([166](#A3.E166)), we obtain

$$ $\displaystyle\mathbb{E}[\|F(h_{k})\|]\leq(K_{0}+K_{1}\|F(v^{*})\|^{\alpha})\mathbb{E}[\|h_{k}-v^{*}\|^{2}]^{1/2}+K_{2}\mathbb{E}[\|h_{k}-v^{*}\|^{2}]^{1/2(1-\alpha)}+\|F(v^{*})\|.$ (167) $$

Since $\mathbb{E}[\|h_{k}-v^{*}\|^{2}]$ is bounded, it follows that $\mathbb{E}[\|F(h_{k})\|]$ is bounded by some constant $C_{F}>0$ for all $k\geq 0$.
∎

###### Proof.

### C.4 Proof of Theorem 4.4

###### Proof.

The choice of the parameters $\beta_{k}$ ensures that $1-6\beta_{k}^{2}(K_{0}+K_{1}+K_{2})^{2}\geq\frac{1}{2}$, then by letting $u^{*}=P_{U^{*}}(h_{k})$ in ([132](#A3.E132)) in the proof of Lemma [4.1](#S4.Thmtheorem1), with $C_{e}(\beta_{k},\alpha)=K_{1}$, we get

$$ $\displaystyle\|h_{k+1}-P_{U^{*}}(h_{k})\|^{2}$ $\displaystyle\leq{\rm dist}^{2}(h_{k},U^{*})-\frac{1}{2}\|h_{k}-u_{k}\|^{2}-2\gamma_{k}\mu{\rm dist}^{p}(u_{k},U^{*})$ (168) $\displaystyle\quad-2\gamma_{k}\langle e_{k}^{2},u_{k}-u^{*}\rangle+3\beta_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}+2K_{1}\|e_{k}^{1}\|^{2\alpha}).$ $$

By the definition of the distance function, we have

$$ ${\rm dist}^{2}(u_{k+1},U^{*})\leq\|u_{k+1}-P_{U^{*}}(u_{k})\|^{2}.$ $$

Thus,

$$ $\displaystyle{\rm dist}^{2}(h_{k+1},U^{*})$ $\displaystyle\leq{\rm dist}^{2}(h_{k},U^{*})-\frac{1}{2}\|h_{k}-u_{k}\|^{2}-2\gamma_{k}\mu{\rm dist}^{p}(u_{k},U^{*})$ (169) $\displaystyle\quad-2\gamma_{k}\langle e_{k}^{2},u_{k}-u^{*}\rangle+3\beta_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}+2K_{1}\|e_{k}^{1}\|^{2\alpha}).$ $$

Next, we estimate the term ${\rm dist}^{p}(u_{k},U^{*})$ in ([169](#A3.E169)). By the triangle inequality, we have

$$ $\|h_{k}-u^{*}\|\leq\|u_{k}-h_{k}\|+\|u_{k}-u^{*}\|\qquad\hbox{for all }u^{*}\in U^{*},$ $$

and by taking the minimum over $u^{*}\in U^{*}$ on both sides of the preceding relation, we obtain

$$ ${\rm dist}(h_{k},U^{*})\leq\|u_{k}-h_{k}\|+{\rm dist}(u_{k},U^{*}).$ (170) $$

Applying Lemma [A.5](#A1.Thmtheorem5) with $p>0$ in equation ([170](#A3.E170)) yields

$$ $\displaystyle{\rm dist}^{p}(h_{k},U^{*})$ $\displaystyle\leq(\|u_{k}-h_{k}\|+{\rm dist}(u_{k},U^{*}))^{p}$ (171) $\displaystyle\leq 2^{p-1}\|u_{k}-h_{k}\|^{p}+2^{p-1}\,{\rm dist}^{p}(u_{k},U^{*}).$ $$

Using projection inequality ([27](#A1.E27)), and stepsizes choice ([17](#S4.E17)), we obtain

$$ $\|u_{k}-h_{k}\|\leq\|\gamma_{k}\Phi(h_{k},\xi_{k}^{1})\|\leq 1.$ $$

Combining this result with equation ([171](#A3.E171)), with $p\geq 2$, we get

$$ $\displaystyle{\rm dist}^{p}(h_{k},U^{*})$ $\displaystyle\leq 2^{p-1}\|u_{k}-h_{k}\|^{2+(p-2)}+2^{p-1}{\rm dist}^{p}(u_{k},U^{*})$ (172) $\displaystyle\leq 2^{p-1}\|u_{k}-h_{k}\|^{2}+2^{p-1}\,{\rm dist}^{p}(u_{k},U^{*}).$ $$

By dividing the relation in ([172](#A3.E172)) with $2^{p-1}$
and by rearranging the terms, we obtain the following relation

$$ $\displaystyle-{\rm dist}^{p}(u_{k},U^{*})$ $\displaystyle\leq\|u_{k}-h_{k}\|^{2}-2^{1-p}\,{\rm dist}^{p}(h_{k},U^{*}).$ (173) $$

Combining the preceding inequality with ([169](#A3.E169)), we find that for any $k\geq 0$,

$$ $\displaystyle{\rm dist}^{2}(h_{k+1},U^{*})$ $\displaystyle\leq{\rm dist}^{2}(h_{k},U^{*})-2^{2-p}\mu\gamma_{k}{\rm dist}^{p}(h_{k},U^{*})-\frac{1}{2}\|u_{k}-h_{k}\|^{2}+2\mu\gamma_{k}\,\|u_{k}-h_{k}\|^{2}$ (174) $\displaystyle\quad-2\gamma_{k}\langle e_{k}^{2},u_{k}-u^{*}\rangle+3\beta_{k}^{2}(\|e_{k}^{2}\|^{2}+\|e_{k}^{1}\|^{2}+2K_{1}\|e_{k}^{1}\|^{2\alpha}).$ $$

By the choice of $\beta_{k}$, we have
$\beta_{k}=\dfrac{2}{a(\frac{2d}{a}+k)}$, where $a=\mu\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}$ and $d\geq 4\mu$. Thus, for all $k\geq 0$,

$$ $\beta_{k}\leq\frac{1}{d}\leq\frac{1}{4\mu}\qquad\implies\qquad 2\mu\beta_{k}\leq\frac{1}{2}.$ $$

By the definition of the stepsize $\gamma_{k}$, we always have $\gamma_{k}\leq\beta_{k}$.
Therefore, $2\mu\gamma_{k}\leq 2\mu\beta_{k}\leq\frac{1}{2}$ for all $k\geq 0$, thus implying that

$$ $\displaystyle-\frac{1}{2}\|u_{k}-h_{k}\|^{2}+2\mu\gamma_{k}\,\|u_{k}-h_{k}\|^{2}\leq 0.$ (175) $$

Using the stochastic properties of $\xi_{k}$ imposed by Assumption [2.5](#S2.Thmtheorem5), we have for all $k\geq 0$,

$$ $\displaystyle\mathbb{E}[\mathbb{E}[\gamma_{k}\mathbb{E}[\langle e_{k}^{2},u_{k}-u^{*}\rangle\mid\mathcal{F}_{k-1}\cup\{\xi_{k}^{1}\}]\mid\mathcal{F}_{k-1}]]=0,$ (176) $\displaystyle\mathbb{E}[\mathbb{E}[\|e_{k}^{2}\|^{2}\mid\mathcal{F}_{k-1}\cup\{\xi_{k}^{1}\}]]\leq\sigma^{2},\qquad\mathbb{E}[\mathbb{E}[\|e_{k}^{1}\|^{2}\mid\mathcal{F}_{k-1}]]\leq\sigma^{2}.$ (177) $$

Moreover, since $\alpha\leq 1$ then the conditional expectation $\mathbb{E}[\|e_{k}^{1}\|^{2\alpha}|\mathcal{F}_{k-1}]$ is defined, and by Jensen inequality $\mathbb{E}[\|e_{k}^{1}\|^{2\alpha}|\mathcal{F}_{k-1}]\leq\sigma^{2\alpha}$ for all $k\geq 0$. Thus, by taking the total expectation in relation ([174](#A3.E174)) and using an estimate from ([175](#A3.E175)), we obtain
for all $u^{*}\in U^{*}$ and for all $k\geq 0$,

$$ $\displaystyle\mathbb{E}[{\rm dist}^{2}(h_{k+1},U^{*})]$ $\displaystyle\leq\mathbb{E}[{\rm dist}^{2}(h_{k},U^{*})]-2^{2-p}\mu\mathbb{E}[\gamma_{k}{\rm dist}^{p}(h_{k},U^{*})]+6\beta_{k}^{2}(\sigma^{2}+K_{1}\sigma^{2\alpha}).$ (178) $$

The equation  ([178](#A3.E178)) is similar to equation  ([91](#A2.E91)) in the proof of Theorem [3.4](#S3.Thmtheorem4), with the same stepsize structure. Thus, by following the same arguments from equations ([91](#A2.E91)) to equation ([103](#A2.E103)) in the proof of Theorem [3.4](#S3.Thmtheorem4), we arrive at

$$ $\displaystyle\mathbb{E}[{\rm dist}^{2}(h_{k+1},U^{*})]$ $\displaystyle\leq\mathbb{E}[{\rm dist}^{2}(h_{k},U^{*})]-2^{2-p}\mu\beta_{k}\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}\mathbb{E}[{\rm dist}^{p}(h_{k},U^{*})]$ (179) $\displaystyle\quad+6\beta_{k}^{2}(\sigma^{2}+K_{1}\sigma^{2\alpha}),$ $$

where $C_{F}$ is an upperbound on $\mathbb{E}[\|F(h_{k})\|]$ from the statement of Lemma [4.3](#S4.Thmtheorem3). Now let $D_{k}=\mathbb{E}[{\rm dist}^{2}(h_{k},U^{*})]$, and consider two cases $p=2$ and $p>2$.

Case $p=2$.
We note that by the definition of $a=\mu\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}$ and $d$, we have that $d\geq 4\mu$ and $\mu\geq a$, implying that $d\geq a$. Hence, for $p=2$, relation ([179](#A3.E179)) satisfies the conditions of Lemma [A.6](#A1.Thmtheorem6) with the following identification

$$ $\displaystyle r_{k}=D_{k},\quad a=\mu\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\},\quad\alpha_{k}=\beta_{k},\quad s_{k}=0,\quad c=6(\sigma^{2}+K_{1}\sigma^{2\alpha}).$ (180) $$

Therefore, for the choice $\beta_{k}=\dfrac{2}{a(\frac{2d}{a}+k)}$, we get the following convergence rate for all $k\geq 1$,

$$ $\displaystyle D_{k+1}\leq\dfrac{8d^{2}D_{0}}{a^{2}k^{2}}+\frac{12(\sigma^{2}+K_{1}\sigma^{2\alpha})}{a^{2}k}.$ (181) $$

Case $p>2$.
From ([179](#A3.E179)) by using $D_{k}=\mathbb{E}[{\rm dist}^{2}(h_{k},U^{*})]$ and $a=\mu\min\left\{1,\frac{1}{2(C_{F}+\sigma)}\right\}$,
we obtain for all $k\geq 0,$

$$ $\displaystyle D_{k+1}$ $\displaystyle\leq D_{k}-2^{2-p}a\beta_{k}\mathbb{E}[{\rm dist}^{p}(h_{k},U^{*})]+6\beta_{k}^{2}(\sigma^{2}+K_{1}\sigma^{2\alpha}).$ (182) $$

When $p>2$,
by applying Jensen inequality, we obtain

$$ $\mathbb{E}[{\rm dist}^{p}(h_{k},U^{*})]=\mathbb{E}\left[\left({\rm dist}^{2}(h_{k},U^{*})\right)^{p/2}\right]\geq\left(\mathbb{E}[{\rm dist}^{2}(h_{k},U^{*})]\right)^{p/2}=(D_{k})^{p/2}.$ $$

Thus, for all $k\geq 0$, we have

$$ $\displaystyle D_{k+1}$ $\displaystyle\leq D_{k}-2^{2-p}a\beta_{k}(D_{k})^{p/2}+6(\sigma^{2}+K_{1}\sigma^{2\alpha})\beta_{k}^{2}.$ (183) $$

By telescoping the inequalities in ([183](#A3.E183)), we obtain for $k\geq 0$,

$$ $\displaystyle D_{k+1}$ $\displaystyle\leq D_{0}-2^{2-p}a\sum_{t=0}^{k}\beta_{t}(D_{t})^{p/2}+6(\sigma^{2}+K_{1}\sigma^{2\alpha})\sum_{t=0}^{k}\beta_{t}^{2}.$ (184) $$

Let $D^{\rm best}_{k}=\min_{t=[0,\ldots,k]}D_{t}$, then, by rearranging the term we get for all $k\geq 0$,

$$ $\displaystyle(D^{\rm best}_{k})^{p/2}\sum_{t=0}^{k}\beta_{t}\leq\sum_{t=0}^{k}\beta_{t}(D_{t})^{p/2}$ $\displaystyle\leq\dfrac{D_{0}-D_{k+1}+6(\sigma^{2}+K_{1}\sigma^{2\alpha})\sum_{t=0}^{k}\beta_{t}^{2}}{2^{2-p}a}.$ (185) $$

Now, we use the choice for $\beta_{k}$, i.e., $\beta_{k}=\frac{b}{(k+1)^{q}}$, where $0<b<\frac{1}{2\sqrt{3}(K_{0}+K_{1}+K_{2})}$ and $1/2<q<1$.
Then, the sequence $\{\beta_{k}\}$ satisfies the conditions of Lemma [4.3](#S4.Thmtheorem3). Furthermore, by Lemma [A.7](#A1.Thmtheorem7), we have that for all $k\geq 1$,

$$ $\displaystyle\sum^{k}_{t=0}\beta_{t}\geq\frac{b}{1-q}((k+1)^{1-q}-2^{1-q}),\qquad\qquad\sum^{k}_{t=0}\beta_{t}^{2}\leq\frac{b^{2}}{2q-1}.$ (186) $$

Combining equations ([185](#A3.E185)) and  ([186](#A3.E186)), and omitting $D_{k+1}$, we obtain for all $k\geq 1$,

$$ $\displaystyle(D^{\rm best}_{k})^{p/2}$ $\displaystyle\leq\dfrac{2^{p-2}(1-q)\left(D_{0}+6b^{2}(\sigma^{2}+K_{1}\sigma^{2\alpha})(2\sigma^{2}+1)/(2q-1)\right)}{ab\left((k+1)^{1-q}-2^{1-q}\right)}.$ (187) $$

Raising both sides of the preceding inequality in power $2/p$, we have that for all $k\geq 1$,

$$ $\displaystyle D^{\rm best}_{k}$ $\displaystyle\leq\dfrac{2^{2(p-2)/p}(1-q)^{2/p}\left(D_{0}+6b^{2}(\sigma^{2}+K_{1}\sigma^{2\alpha})(2\sigma^{2}+1)/(2q-1)\right))^{2/p}}{(ab)^{2/p}\,\left((k+1)^{1-q}-2^{1-q}\right)^{2/p}}.$ (188) $$

∎

###### Proof.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: Please see above.
soundness: 2
strengths: This work relaxes several assumptions:
- uses a relaxed notion of L-Lipschitzness, called $\alpha$-symetric operator.
- does  not rely on the assumptions of bounded noise and bounded gradients
summary: This paper focuses on stochastic variational inequality (SVI) problems involving non-monotone operators. Applying clipping to projected gradient descent and extragradient methods establishes almost-sure convergence and in-expectation convergence rates under generalized smoothness conditions, without boundedness assumptions.
weaknesses: - Proposition 2.2. is written for an operator, and is taken from Proposition 1 in (Chen et al. 2023a). The latter is for a gradient of a real-valued function, the former is for an operator that is a more general vector field. It is unclear if Proposition 1 in (Chen et al. 2023a) directly extends to non-gradient field operators. The first equivalence (eq. 9) in  (Chen et al. 2023a) already fails for vector fields. Also, since the proof for (9) in  (Chen et al. 2023a) also relies on ODEs it involves solving the integral involving $h$ therein that contains a vector field. Could you please elaborate?


- Provide citations for the Extragradient and the Popov method.

- It is confusing that Chen et al 2023 is cited twice with the same title and authors. 

# Writing

*Structure.* The contributions are listed in related works; perhaps introduce a paragraph.

*Abstract.* 
- After reading the abstract I could not tell which setup this paper focuses on. It mentions "structured non-monotone operators" but it should be more specific. 
- I could not tell which methods the paper focuses on. It states "well-known stochastic methods with clipping, namely, projection and Korpelevich". The former can be combined with all methods, so I was confused. For the latter, it is common to use 'extragradient'. Please use projected gradient descent (PGD) and projected extragradient throughout the paper. However, even with this change, the abstract is still confusing, as it gives the impression that you are focusing on problems beyond monotonicity, for which PGD last iterate does not converge; clarify if you are focusing on last, average, or best iterate.
After reading the abstract, I could not tell what rate you get and whether it matches the lower bound? Please add that.


*Other.* 
- Use citing with brackets when needed
- line 49 missing citation for Adam 
- line 57 missing citation for adaptive methods
- line 71 typo

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: See weaknesses section.
soundness: 3
strengths: The paper is clearly written and easy to follow. Furthermore the math supporting the main contribution of the paper, namely the theoretical convergence guarantees for two classical optimization algorithmic schemes run with stochastic clipped methods seems solid.
Moreover, as far as my knowledge goes the particular result are novel in the literature.
Finally, the numerical/experimental part seems clear and supports the theoretical results
summary: The paper focuses on solving stochastic variational inequalities which do not satisfy the typical regularity (Lipschitz continuity) and structural assumptions (monotonicity). More precisely, the authors in order to extend the notion of Lipschitz continuity they consider the class of $\alpha-$ asymmetric operators (introduced by Chen 2023). Furthermore, their extension of non-monotonicity, they consider operators which satisfy the so-called $p$-quasi sharpness property. This structural assumption actually can be seen as a local type relaxation of strong convexity relative to the solutions.
To that end, the authors investigate under these assumption the behaviour of (stochastic) projected gradient descent and extra-gradient algorithm run with stochastic clipped step-sizes. In doing so, they provide asymptotic and non-asymptotic convergence guarantees for each respective method
weaknesses: Concerning the weaknesses, three observations are in order:

1.  The key innovation, compared to the variational coherent literature is the introduction of two independent samplings per iteration. In my opinion this needs further clarifications on how it affects the complexity of the rates both in theory and in the numerical experiments.

2. The under study relaxation of the Lipschitz continuity of the (VI) defining operator introduces some extra parameters which require an additional tuning effort (see the respective non-asymptotic convergence rate theorems). This fact requires an additional discussion concerning the practical efficiency of the methods.

3. The case of $p>2$ the respective guarantees are given with respect to the expected best distance.  To that end, this prohibits the proposal (due to the stochastic nature of the methods) of an actual output rule of the respective methods.

That being said, I still find the particular work interesting and look forward for a fruitful discussion period.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: - Eq. 9: could you elaborate why you need a fresh sample? Is this an artifact of the analysis?
- It is curious that Popov's method dominates all other methods in the experiments:
     - Is there any intuition for why this is the case? 
    - It is not clear to me how the clipping is performed for Popov since each update involves to gradients (the old and new). Is the old gradient clipped with a fresh sample, such that the number of gradient calls are the same as for the clipped version of the gradient/extragradient method?
     - What is the difficulty in analysing a clipped version of Popov's method under generalization smoothness? 
- It seems strange that a large choice of $q$ improves performance, while the theory suggests otherwise. What are possible explanations?
- As a sanity check do you recover Theorem 2.5 of Koloskova et al. (2023) in the strongly convex deterministic case?
soundness: 3
strengths: - The paper reads very easily and is transparent about contributions
- Relaxing smoothness assumptions for VIs seems like an interesting direction
summary: The paper considers $L_0,L_1$-smooth stochastic variational inequalities satisfying a generalization of strong monotonicity/coherence called $p$-quasi sharpness.
For both a clipped variant of projection stochastic gradient method and the projected stochastic extragradient method they show:

- $\mathcal O(1/k)$ rates in expectation for the last iterate when $p=2$ (strongly coherent problems), matching the one under (standard) Lipschitz continuity (e.g. Hsieh et al. 2019b)
- $\mathcal O(k^{-2(1-q)/p})$ rates for the best iterate for $q\in (1,1/2)$. 
- With a Robbins-Monro stepsize factor they show almost sure convergence.

Both methods uses two gradient computations since the gradient method requires the clipping to be performed with a fresh sample.
weaknesses: - Assuming $p$-quasi sharpness seems like a strong assumption since even (clipped) gradient descent suffice in this setting, making it close to the minimization case. In light of this the result does not seem particularly surprising.
- considering that gradient descent suffice I do not understand the motivation for considering the extragradient variant. It would be helpful if the authors could elaborate on the benefit/reason. I could see it being interesting if clipped extragradient also have a guarantees for bilinear or convex-concave problems (in which case the guarantee would only be for the average in light of e.g. Hsieh et al. 2020), but this is not currently provided.
- Even the clipped gradient method requires 2 gradient computations, which seems unconventional (cf. e.g. Gorbunov et al. 2022). It would be interesting if the additional gradient call could be removed.

Minor:

- l. 481 maybe don't state that p-quasi-sharp is a wide class, consider the (weak) Minty variational inequality also mentioned later.
- l. 489 $\mu < 0$ does not seems to correspond to the weak Minty variational inequality (you need the operator evaluation on the right hand side instead of solution distance). It might be worth also providing a reference.

Typos:

- l. 99 stepszies -> stepsizes
- l. 105 should be $O(k^{-1})$
- l. 75 thr -> the

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: - Since the analysis of the stochastic projection method seems to require two stochastic oracles, one for the update step and one for the computation of the stepsize, the total number of stochastic oracles needed would be twice the number of oracles the same method would require when analyzed without the generalized smoothness assumption. Do you think that this is a limitation of the current proof technique or it is required in general for establishing convergence under the more relaxed smoothness condition?
- Which of the two methods, stochastic Projection or Stochastic Korpelevich, should be preferred in the quasi-sharp regime?
soundness: 3
strengths: - The convergence is established under an assumption that is more general than smoothness.
- The paper establishes asymptotic convergence for two algorithms in the quasi-sharp setting.
- The associated rates of convergence are provided for each algorithm.
summary: The paper focuses on solving Stochastic Variational Inequalities (SVI) under a generalized smoothness assumption. More specifically, the authors analyze two methods, the Projection method and the Korpelevich method, in the quasi-sharp regime. The asymptotic convergence of both algorithms is established under the general smoothness assumption. In addition, the authors provide theoretical guarantees for the last iterate and establish the rate of convergence of both methods. Experimental results compare the two methods, validating the theoretical results for different stepsizes.
weaknesses: - Even though the paper provides a good amount of previous work on the topic, the positioning of the new results in the established literature is not done sufficiently. It would be nice to have a comparison of the provided convergence rates for the two methods with existing results. For example, one can compare the rate of the Projection method with the algorithm in [1] in the special setting of minimax problems.
- Based on the start of Section 3, it seems that two stochastic oracles are needed in the Projection method for the analysis to go through. This approach seems to require double the number of stochastic oracles than the classical Stochastic Projected Gradient Descent Ascent (or Stochastic Projection method with one oracle per iteration), which is not favorable.
- It would be nice to have a comparison between the two methods, Projection algorithm and Korpelevich method. Even though there is a reference to that in the Experimental section, a precise comparison of the two algorithms and their rate after providing the rates of convergence would be beneficial to have.
- The assumption on bounded variance of the stochastic oracles might be strong in some settings.

Some Typos:
- In the introduction (line 57): “normalizedChen et al. (2023b)” the reference is not correctly inserted.
- In section 1.1: “SVIs Jelassi et al. (2022)” the reference is not correctly inserted.
- In section 1.1: “Generalized Smooth Optimization In Zhang et al. (2019)” the reference needs to be correctly inserted.
- In section 3.2, it is mentioned “Then, from Theorem 4.4 we obtain”. However, I think that Theorem 3.4 was meant to be mentioned.


References

[1]: Delving into the Convergence of Generalized Smooth Minimax Optimization, W Xian, Z Chen, H Huang, ICML 2024

Meta-review: The paper studies stochastic variational inequalities under generalized smoothness assumptions and for operators that are "quasi-sharp." Although the problem class is presented as corresponding to "structured non-monotone" operators, the quasi-sharpness is quite a strong assumption that excludes even some monotone problems (e.g., coming from bilinear problems) and suffices for GDA to converge (while GDA provably diverges for bilinear problems). The paper proves that GDA and EG methods with proposed step size & gradient estimation strategies (involving gradient clipping) exhibit almost sure convergence. They also provide complexity results for some of the considered settings, where the guarantees hold in expectation.

While the paper is technically solid, the motivation and the strength of contributions are not clear at this point. The paper would benefit from a better motivation for the considered problem class, better connection to and comparison to related work, and a broader discussion of how the results might extend to other cases of interest (at least handling all the monotone settings we know how to address at the moment).

Decision: Reject