# Stochastic Relaxed Inertial Forward-Backward-Forward splitting for Monotone
Inclusions in Hilbert spaces

Shisheng Cui Department of Industrial and Manufacturing Engineering,
Pennsylvania State University, University Park, PA 16802, USA  Uday V.
Shanbhag Department of Industrial and Manufacturing Engineering, Pennsylvania
State University, University Park, PA 16802, USA  Mathias Staudigl
Corresponding author Department of Data Science and Knowledge Engineering,
Maastricht University, P.O. Box 616, NL–6200 MD Maastricht, The Netherlands
<EMAIL_ADDRESS> Phan Tu Vuong Mathematical Sciences,
University of Southampton, Highfield Southampton SO17 1BJ, United Kingdom

###### Abstract

We consider monotone inclusions defined on a Hilbert space where the operator
is given by the sum of a maximal monotone operator $T$ and a single-valued
monotone, Lipschitz continuous, and expectation-valued operator $V$. We draw
motivation from the seminal work by Attouch and Cabot [1, 2] on relaxed
inertial methods for monotone inclusions and present a stochastic extension of
the relaxed inertial forward-backward-forward (RISFBF) method. Facilitated by
an online variance reduction strategy via a mini-batch approach, we show that
(RISFBF) produces a sequence that weakly converges to the solution set.
Moreover, it is possible to estimate the rate at which the discrete velocity
of the stochastic process vanishes. Under strong monotonicity, we demonstrate
strong convergence, and give a detailed assessment of the iteration and oracle
complexity of the scheme. When the mini-batch is raised at a geometric
(polynomial) rate, the rate statement can be strengthened to a linear
(suitable polynomial) rate while the oracle complexity of computing an
$\epsilon$-solution improves to $\mathcal{O}(1/\epsilon)$. Importantly, the
latter claim allows for possibly biased oracles, a key theoretical advancement
allowing for far broader applicability. By defining a restricted gap function
based on the Fitzpatrick function, we prove that the expected gap of an
averaged sequence diminishes at a sublinear rate of $\mathcal{O}(1/k)$ while
the oracle complexity of computing a suitably defined $\epsilon$-solution is
$\mathcal{O}(1/\epsilon^{1+a})$ where $a>1$. Numerical results on two-stage
games and an overlapping group Lasso problem illustrate the advantages of our
method compared to stochastic forward-backward-forward (SFBF) and SA schemes.

##  1 Introduction

###  1.1 Problem formulation and motivation

A wide range of problems in areas such as optimization, variational
inequalities, game theory, signal processing, or traffic theory, can be
reduced to solving inclusions involving set-valued operators in a Hilbert
space $\mathsf{H}$, i.e. to find a point $x\in\mathsf{H}$ such that $0\in
F(x)$, where $F:\mathsf{H}\to 2^{\mathsf{H}}$ is a set-valued operator. In
many problems such inclusion problems display specific structure revealing
that the operator $F$ can be additively decomposed. This leads us to the main
problem we consider in this paper.

######  Problem 1.

Let $\mathsf{H}$ be a real separable Hilbert space with inner product
$\langle\cdot,\cdot\rangle$ and associated norm
$\lVert\cdot\rVert=\sqrt{\langle\cdot,\cdot\rangle}$. Let $T:\mathsf{H}\to
2^{\mathsf{H}}$ and $V:\mathsf{H}\to\mathsf{H}$ be maximally monotone
operators, such that $V$ is $L$-Lipschitz continuous. The problem is to

$\text{ find }x\in\mathsf{H}\text{ such that }0\in F(x)\triangleq V(x)+T(x),$
(MI)

We assume that Problem 1 is well-posed:

######  Assumption 1.

$\mathsf{S}\triangleq\mathsf{Zer}(F)\neq\varnothing$.

We are interested in the case where (MI) is solved by an iterative algorithm
based on a _ stochastic oracle (SO) representation_ of the operator $V$.
Specifically, when solving the problem, the algorithm calls to the SO. At each
call, the SO receives as input a search point $x\in\mathsf{H}$ generated by
the algorithm on the basis of past information so far, and returns the output
$\hat{V}(x,\xi)$, where $\xi$ is a random variable defined on some given
probability space $(\Omega,\mathcal{F},\mathbb{P})$, taking values in a
measurable set $\Xi$ with law ${\mathsf{P}}=\mathbb{P}\circ\xi^{-1}$. In most
parts of this paper, and the vast majority of contributions on stochastic
variational problems in general, it is assumed that the output of the SO is
unbiased,

$V(x)=\mathbb{E}_{\xi}[\hat{V}(x,\xi)]=\int_{\Xi}\hat{V}(x,z)\>d{\mathsf{P}}(z)\qquad\forall
x\in\mathsf{H}.$ (1.1)

Such stochastic inclusion problems arise in numerous problems of fundamental
importance in mathematical optimization and equilibrium problems, either
directly or through an appropriate reformulation. An excellent survey on the
existing techniques for solving problem (MI) can be found in [9] (in general
Hilbert spaces) and [29] (in the finite-dimensional case).

###  1.2 Motivating examples

In what follows, we provide some motivating examples.

######  Example 1.1 (Stochastic Convex Optimization).

Let $\mathsf{H}_{1},\mathsf{H}_{2}$ be separable Hilbert spaces. A large class
of stochastic optimization problems, with wide range of applications in signal
processing, machine learning and control, is given by

$\min_{u\in\mathsf{H}_{1}}\\{f(u)+h(u)+g(Lu)\\}$ (1.2)

where $h:\mathsf{H}_{1}\to\mathbb{R}$ is a convex differentiable function with
a Lipschitz continuous gradient $\nabla h$, represented as
$h(u)=\mathbb{E}_{\xi}[\hat{h}(u,\xi)]$. $f:\mathsf{H}_{1}\to(-\infty,\infty]$
and $g:\mathsf{H}_{2}\to(-\infty,\infty]$ are proper, convex lower semi-
continuous functions, and $L:\mathsf{H}_{1}\to\mathsf{H}_{2}$ is a bounded
linear operator. Problem (1.2) gains particular relevance in machine learning,
where usually $h(u)$ is a convex data fidelity term (e.g. a _population risk_
functional), and $g(Lu)$ and $f(u)$ embody penalty or regularization terms;
see e.g. total variation [74], hierarchical variable selection [46, 88], and
graph regularization [83, 84]. Applications in control and engineering are
given in [5, 53]. We refer to (1.2) as the _primal problem_. Using Fenchel-
Rockafellar duality [9, ch.19], the dual problem of (1.2) is given by

$\min_{v\in\mathsf{H}_{2}}\\{(f+h)^{\ast}(-L^{\ast}v)+g^{\ast}(v)\\},$ (1.3)

where $g^{\ast}$ is the Fenchel conjugate of $g$ and
$(f+h)^{\ast}(w)=f^{\ast}\square
h^{\ast}(w)=\inf_{u\in\mathsf{H}_{1}}\\{f^{\ast}(u)+h^{\ast}(w-u)\\}$
represents the infimal convolution of the functions $f$ and $h$. Combining the
primal problem (1.2) with its dual (1.3), we obtain the saddle-point problem

$\inf_{u\in\mathsf{H}_{1}}\sup_{v\in\mathsf{H}_{2}}\\{f(u)+h(u)-g^{\ast}(v)+\langle
Lu,v\rangle\\}.$ (1.4)

Following classical Karush-Kuhn-Tucker theory [69], the primal-dual optimality
conditions associated with (1.4) are concisely represented by the following
monotone inclusion: Find
$\bar{x}=(\bar{u},\bar{v})\in\mathsf{H}_{1}\times\mathsf{H}_{2}\equiv\mathsf{H}$
such that

$-L^{\ast}\bar{v}\in\partial f(\bar{u})+\nabla h(\bar{u}),\text{ and
}L\bar{u}\in\partial g^{\ast}(\bar{v}).$ (1.5)

We may compactly summarize these conditions in terms of the zero-finding
problem (MI) using the operators $V$ and $T$, defined as

$\displaystyle V(u,v)\triangleq(\nabla h(u)+L^{\ast}v,-Lu)\text{ and
}T(u,v)\triangleq\partial f(u)\times\partial g^{\ast}(v).$

Note that the operator $V:\mathsf{H}\to\mathsf{H}$ is the sum of a maximally
monotone and a skew-symmetric operator. Hence, in general, it is not
cocoercive111An operator $C:\mathsf{H}\to\mathsf{H}$ is cocoercive if there
exists $\beta>0$ such that $\langle C(x)-C(y),x-y\rangle\geq\beta\lVert
C(x)-C(y)\rVert^{2}$.. Conditions on the data guaranteeing Assumption 1 are
stated in [21].

Since $h(u)$ is represented as an expected value, we need to appeal to
simulation based methods to evaluate its gradient. Also, significant
computational speedups can be made if we are able to sample the skew-symmetric
linear operator $(u,v)\mapsto(L^{\ast}u,-Lu)$ in an efficient way. Hence, we
assume that there exists a SO that can provide unbiased estimator to the
gradient operators $\nabla h(u)$ and $(L^{\ast}v,-Lu)$. More specifically,
given the current position $x=(u,v)\in\mathsf{H}_{1}\times\mathsf{H}_{2}$, the
oracle will output the random estimators
$\hat{H}(u,\xi),\hat{L}_{u}(u,\xi),\hat{L}_{v}(v,\xi)$ such that

$\displaystyle\mathbb{E}_{\xi}[\hat{H}(u,\xi)]=\nabla
h(u),\;\mathbb{E}_{\xi}[\hat{L}_{u}(u,\xi)]=Lu,\text{ and
}\mathbb{E}_{\xi}[\hat{L}_{v}(v,\xi)]=L^{\ast}v.$

This oracle feedback generates the _random operator_
$\hat{V}(x,\xi)=(\hat{H}(u,\xi)+\hat{L}_{v}(v,\xi),-\hat{L}_{u}(u,\xi))$,
which allows us to approach the saddle-point problem (1.4) via simulation-
based techniques.

######  Example 1.2 (Stochastic variational inequality problems).

There are a multitude of examples of monotone inclusion problems (MI) where
the single-valued map $V$ is not the gradient of a convex function. An
important model class where this is the case is the _ stochastic variational
inequality (SVI)_ problem. Due to their huge number of applications, SVI’s
received enormous interest over the last several years from various
communities [48, 75, 80, 58]. This problem emerges when $V(x)$ is represented
as an expected value as in (1.1) and $T(x)=\partial g(x)$ for some proper
lower semi-continuous function $g:\mathsf{H}\to(-\infty,\infty]$. In this
case, the resulting structured monotone inclusion problem can be equivalently
stated as

$\displaystyle\text{find }\bar{x}\in\mathsf{H}\text{ s.t. }\langle
V(\bar{x}),x-\bar{x}\rangle+g(x)-g(\bar{x})\geq 0\quad\forall x\in\mathsf{H}.$
(1.6)

An important and frequently studied special case of (1.6) arises if $g$ is the
indicator function of a given closed and convex subset
$\mathsf{C}\subset\mathsf{H}$. In this cases the set-valued operator $T$
becomes the normal cone map

$T(x)=\operatorname{\mathsf{N}}_{\mathsf{C}}(x)\triangleq\left\\{\begin{array}[]{ll}\left\\{p\in\mathsf{H}|\sup_{y\in\mathsf{C}}\langle
y-x,p\rangle\leq 0\right\\}&\text{if }x\in\mathsf{C},\\\
\varnothing&\text{else}.\end{array}\right.$ (1.7)

This formulation includes many fundamental problems including fixed point
problems, Nash equilibrium problems and complementarity problems [29].
Consequently, the equilibrium condition (1.6) reduces to

$\text{find }\bar{x}\in\mathsf{C}\text{ s.t. }\langle
V(\bar{x}),x-\bar{x}\rangle\geq 0\quad\forall x\in\mathsf{C}.$

###  1.3 Contributions

Despite the advances in stochastic optimization and variational inequalities,
the algorithmic treatment of general monotone inclusion problems under
stochastic uncertainty is a largely unexplored field. This is rather
surprising given the vast amount of applications of maximally monotone
inclusions in control and engineering, encompassing distributed computation of
generalized Nash equilibria [17, 86, 31], traffic systems [34, 35, 43], and
PDE-constrained optimization [10]. The first major aim of this manuscript is
to introduce and investigate a relaxed inertial stochastic forward-backward-
forward (RISFBF) method, building on an operator splitting scheme originally
due to Paul Tseng [85]. RISFBF produces three sequences
$\\{(X_{k},Y_{k},Z_{k});k\in\mathbb{N}\\}$, defined as

$\displaystyle\begin{aligned} Z_{k}&=X_{k}+\alpha_{k}(X_{k}-X_{k-1}),\\\
Y_{k}&=J_{\lambda_{k}T}(Z_{k}-\lambda_{k}A_{k}(Z_{k})),\\\
X_{k+1}&=(1-\rho_{k})Z_{k}+\rho_{k}[Y_{k}+\lambda_{k}(A_{k}(Z_{k})-B_{k}(Y_{k}))].\end{aligned}$
(RISFBF)

The data involved in this scheme are explained as follows:

  * •

$A_{k}(Z_{k})$ and $B_{k}(Y_{k})$ are random estimators of $V$ obtained by
consulting the SO at search points $Z_{k}$ and $Y_{k}$, respectively;

  * •

$(\alpha_{k})_{k\in\mathbb{N}}$ is a sequence of non-negative numbers
regulating the memory, or _inertia_ of the method;

  * •

$(\lambda_{k})_{k\in\mathbb{N}}$ is a positive sequence of step-sizes;

  * •

$(\rho_{k})_{k\in\mathbb{N}}$ is a non-negative _relaxation_ sequence.

If $\alpha_{k}=0$ and $\rho_{k}=1$ the above scheme reduces to the stochastic
forward-backward-forward method developed in [15, 24], with important
applications in Gaussian communication networks [80] and dynamic user
equilibrium problems [82]. However, even more connections to existing methods
can be made.

Stochastic Extragradient. If $T=\\{0\\}$, we obtain the inertial extragradient
method

$\displaystyle Z_{k}$ $\displaystyle=X_{k}+\alpha_{k}(X_{k}-X_{k-1}),$
$\displaystyle Y_{k}$ $\displaystyle=Z_{k}-\lambda_{k}A_{k}(Z_{k}),$
$\displaystyle X_{k+1}$ $\displaystyle=Z_{k}-\rho_{k}\lambda_{k}B_{k}(Y_{k}).$

If $\alpha_{k}=0$, this reduces to a generalized extragradient method

$\displaystyle Y_{k}$ $\displaystyle=X_{k}-\lambda_{k}A_{k}(X_{k}),$
$\displaystyle X_{k+1}$ $\displaystyle=X_{k}-\lambda_{k}\rho_{k}B_{k}(Y_{k}),$

recently introduced in [27].

Proximal Point Method.  If $V=0$, the method reduces to the well-known
deterministic proximal point algorithm [2], overlaid by inertial and
relaxation effects. The scheme reads explicitly as

$\displaystyle Z_{k}=X_{k}+\alpha_{k}(X_{k}-X_{k-1}),$ $\displaystyle
X_{k+1}=(1-\rho_{k})Z_{k}+\rho_{k}J_{\lambda_{k}T}(Z_{k}).$

The list of our contributions reads as follows:

  * (i)

_Wide Applicability._ A key argument in favor of Tseng’s operator splitting
method is that it is provably convergent when solving structured monotone
inclusions of the type (MI), without imposing _cocoercivity_ of the single-
valued part $V$. This is a remarkable advantage relative to the perhaps more
familiar and direct forward-backward splitting methods (aka projected
(stochastic) gradient descent in the potential case). In particular, our
scheme is applicable to the primal-dual splitting described in Example 1.1.

  * (ii)

_Asymptotic guarantees._ We show that under suitable assumptions on the
relaxation sequence $(\rho_{k})_{k\in\mathbb{N}}$, the non-decreasing inertial
sequence $(\alpha_{k})_{k\in\mathbb{N}}$, and step-length sequence
$(\lambda_{k})_{k\in\mathbb{N}}$, the generated stochastic process
$(X_{k})_{k\in\mathbb{N}}$ weakly almost surely converges to a random variable
with values in $\mathsf{S}$. Assuming demiregularity of the operators yields
strong convergence in the real (possibly infinite-dimensional) Hilbert space.

  * (iii)

_Non-asymptotic linear rate under strong monotonicity of $V$._ When $V$ is
strongly monotone, strong convergence of the last iterate is shown and the
sequence admits a non-asymptotic linear rate of convergence without a
conditional unbiasedness of the SO. In particular, we show that the iteration
and oracle complexity of computing an $\epsilon$-solution is no worse than
$\mathcal{O}(\log(\tfrac{1}{\epsilon}))$ and
$\mathcal{O}(\tfrac{1}{\epsilon})$, respectively.

  * (iv)

_Non-asymptotic sublinear rate under monotonicity of $V$._ When $V$ is
monotone, by leveraging the _Fitzpatrick function_ [30, 77, 9] associated with
the structured operator $F=T+V$, we propose a restricted gap function. We then
prove that the expected gap of an averaged sequence diminishes at the rate of
$\mathcal{O}(\tfrac{1}{k})$. This allows us to derive an
$\mathcal{O}(\tfrac{1}{\epsilon})$ upper bound on the iteration complexity,
and an $\mathcal{O}(\tfrac{1}{\epsilon^{2+\delta}})$ upper bound (for
$\delta>0)$ on the oracle complexity for computing an $\epsilon$-solution.

The above listed contributions shed new light on a set of urgent open
questions, which we summarize below:

  * (i)

Absence of rigorous asymptotics. So far no aymptotic convergence guarantees
have been available when considering relaxed inertial FBF schemes when $T$ is
maximally monotone and $V$ is a single-valued monotone expectation-valued map.

  * (ii)

Unavailability of rate statements. We are not aware of any known non-
asymptotic rate guarantees for algorithms solving (MI) under stochastic
uncertainty. A key barrier in monotone and stochastic regimes in developing
such statements has been in the availability of a residual function. Some
recent progress in the special stochastic variational inequality case has been
made by [45, 44, 15], but the general Hilbert-space setting involving set-
valued operators seems to be largely unexplored (we will say more in Section
1.4).

  * (iii)

Bias requirements. A standard assumption in stochastic optimization is that
the SO generates signals which are unbiased estimators of the deterministic
operator $V(x)$. Of course, the requirement that the noise process is unbiased
may often fail to hold in practice. In the present Hilbert space setting this
is in some sense even expected to be the rule rather than the exception, since
most operators are derived from complicated dynamical systems or the
optimization method is applied to discretized formulations of the original
problem. See the recent work [37, 38] for an interesting illustration in the
context of PDE-constrained optimization. Some of our results go beyond the
standard unbiasedness assumption.

###  1.4 Related research

Understanding the role of inertial and relaxation effects in numerical schemes
is a line of research which received enormous interest over the last two
decades. Below, we try to give a brief overview about related algorithms.

Inertial, Relaxation, and Proximal schemes.

In the context of convex optimization, Polyak [67] introduced the _Heavy-ball
method_. This is a two-step method for minimizing a smooth convex function
$f$. The algorithm reads as

$\left\\{\begin{array}[]{l}Z_{k}=X_{k}+\alpha_{k}(X_{k}-X_{k-1}),\\\
X_{k+1}=Z_{k}-\lambda_{k}\nabla f(X_{k})\end{array}\right.$ (HB)

The difference from the gradient method is that the base point of the gradient
descent step is taken to be the extrapolated point $Z_{k}$, instead of
$X_{k}$. This small difference has the surprising consequence that (HB)
attains optimal complexity guarantees for strongly convex functions with
Lipschitz continuous gradients. Hence, (HB) resembles an optimal method [64].
The acceleration effects can be explained by writing the process entirely in
terms of a single updating equation as

$X_{k+1}-2X_{k}-X_{k-1}+(1-\alpha_{k})(X_{k}-X_{k-1})+\lambda_{k}\nabla
f(X_{k})=0.$

Choosing $\alpha_{k}=1-a_{k}\delta_{k}$ and
$\lambda_{k}=\gamma_{k}\delta^{2}_{k}$ for $\delta_{k}$ a small parameter, we
arrive at

$\frac{1}{\delta_{k}^{2}}(X_{k+1}-2X_{k}-X_{k-1})+\frac{a_{k}}{\delta_{k}}(X_{k}-X_{k-1})+\gamma_{k}\nabla
f(X_{k})=0.$

This can be seen as a discrete-time approximation of the second-order
dynamical system

$\ddot{x}(t)+\frac{a}{t}\dot{x}(t)+\gamma(t)\nabla f(x(t))=0,$

[68] introduced this dynamical system in an optimization context. Since then,
it has received significant attention in the potential, as well as in the non-
potential case (see e.g [3, 13, 4] for an appetizer). As pointed out in [81],
if $\gamma(t)=1$, the above system reduces to a continuous version of
Nesterov’s fast gradient method [63]. Recently, [36] defined a stochastic
version of the Heavy-ball method.

Motivated by the development of such fast methods for convex optimization,
Attouch and Cabot [1] studied a _relaxed-inertial forward-backward algorithm_
, reading as

$\left\\{\begin{array}[]{l}Z_{k}=X_{k}+\alpha_{k}(X_{k}-X_{k-1}),\\\
Y_{k}=J_{\lambda_{k}T}(Z_{k}-\lambda_{k}V(Z_{k}))\\\
X_{k+1}=(1-\rho_{k})Z_{k}+\rho_{k}Y_{k}.\end{array}\right.$ (RIFB)

If $V=0$, this reduces to a relaxed inertial proximal point method analyzed by
Attouch and Cabot [2]. If $\rho_{k}=1$, an inertial forward-backward splitting
method is recovered, first studied by Lorenz and Pock [56].

Convergence guarantees for the forward-backward splitting rely on the
cocoercivity (inverse strong monotonicity) of the single-valued operator $V$.
Example 1.1, in which $V$ is given by a monotone plus a skew-symmetric linear
operator, illustrates an important instance for which this assumption is not
satisfied (see [16] for further examples). A general-purpose operator
splitting framework, relaxing the cocoercivity property, is the forward-
backward-forward (FBF) method due to Tseng [85]. Inertial [12] and relaxed-
inertial [14] versions of FBF have been developed. An all-encompassing
numerical scheme can be compactly described as

$\left\\{\begin{array}[]{l}Z_{k}=X_{k}+\alpha_{k}(X_{k}-X_{k-1}),\\\
Y_{k}=J_{\lambda_{k}T}(Z_{k}-\lambda_{k}V(Z_{k})),\\\
X_{k+1}=(1-\rho_{k})Z_{k}+\rho_{k}[Y_{k}-\lambda_{k}(V(Y_{k})-V(Z_{k}))].\end{array}\right.$
(RIFBF)

Weak and strong convergence under appropriate conditions on the involved
operators and parameter sequences are established in [14], but no rate
statements are given.

Related work on stochastic approximation. Efforts in extending stochastic
approximation methods to variational inequality problems have considered
standard projection schemes [48] for Lipschitz and strongly monotone
operators. Extragradient and (more generally) mirror-prox algorithms [61, 50]
can contend with merely monotone operators, while iterative smoothing [87]
schemes can cope with with the lack of Lipschitz continuity. It is worth
noting that extragradient schemes have recently assumed relevance in the
training of generative adversarial networks (GANS) [40, 59]. Rate analysis for
stochastic extragradient (SEG) have led to optimal rates for Lipschitz and
monotone operators [50], as well as extensions to non-Lipschitzian [87] and
pseudomonotone settings [45, 51]. To alleviate the computational complexity
single-projection schemes, such as the stochastic forward-backward-forward
(SFBF) method [15, 24], as well as subgradient-extragradient and projected
reflected algorithms [25] have been studied as well.

SFBF has been shown to be nearly optimal in terms of iteration and oracle
complexity, displaying significant empirical improvements compared to SEG.
While the role of inertia in optimization is well documented, in stochastic
splitting problems, the only contribution we are aware of is the work by
Rosasco et al. [72]. In that paper asymptotic guarantees for an inertial
stochastic forward-backward (SFB) algorithm are presented under the hypothesis
that the operators $V$ and $T$ are maximally monotone and the single-valued
operator $V$ is cocoercive.

Variance reduction approaches. Variance-reduction schemes address the
deterioration in convergence rate and the resulting poorer practical behavior
via two commonly adopted avenues:

  * (i)

If the single-valued part $V$ appears as a finite-sum (see e.g. [40, 66]),
variance-reduction ideas from machine learning [41] can be used.

  * (ii)

Mini-batch schemes that employ an increasing batch-size of gradients [32] lead
to deterministic rates of convergence for stochastic strongly convex [47],
convex [49], and nonconvex optimization [39], as well as for pseudo-monotone
SVIs via extragradient [45], and splitting schemes [15].

In terms of run-time, improvements in iteration complexities achieved by mini-
batch approaches are significant; e.g. in strongly monotone regimes, the
iteration complexity improves from $\mathcal{O}(\tfrac{1}{\epsilon})$ to
$\mathcal{O}(\ln(\tfrac{1}{\epsilon}))$ [24, 25]. Beyond run-time advantages,
such avenues provide asymptotic and rate guarantees under possibly weaker
assumptions on the problem as well as the oracle; in particular, mini-batch
schemes allow for possibly biased oracles and state-dependency of the noise
[25]. Concerns about the sampling burdens are, in our opinion, often
overstated since such schemes are meant to provide $\epsilon$-solutions; e.g.
if $\epsilon=10^{-3}$ and the obtained rate is $\mathcal{O}(1/k)$, then the
batch-size $m_{k}=\lfloor k^{a}\rfloor$ where $a>1$, implying that the batch-
sizes are $\mathcal{O}(10^{3a})$, a relatively modest requirement, given the
advances in computing.

Outline. The remainder of the paper is organized in five sections. After
dispensing with the preliminaries in Section 2, we present the (RISFBF) scheme
in Section 3. Asymptotic and rate statements are developed in Section 4 and
preliminary numerics are presented in Section 5. We conclude with some brief
remarks in Section 6.

##  2 Preliminaries

###  2.1 Notation

Throughout, $\mathsf{H}$ is a real separable Hilbert space with scalar product
$\langle\cdot,\cdot\rangle$, norm $\lVert\cdot\rVert$, and Borel
$\sigma$-algebra $\mathcal{B}$. The symbols $\to$ and $\rightharpoonup$ denote
strong and weak convergence, respectively.
$\operatorname{Id}:\mathsf{H}\to\mathsf{H}$ denotes the identity operator on
$\mathsf{H}$. Stochastic uncertainty is modeled on a complete probability
space $(\Omega,\mathcal{F},\mathbb{P})$, endowed with a filtration
${\mathbb{F}}=(\mathcal{F}_{k})_{k\geq 0}$. By means of the Kolmogorov
extension theorem, we assume that $(\Omega,\mathcal{F},\mathbb{P})$ is large
enough so that all random variables we work with are defined on this space. A
$\mathsf{H}$-valued random variable is a measurable function
$X:(\Omega,\mathcal{F})\to(\mathsf{H},\mathcal{B})$. We denote by
$\ell^{0}({\mathbb{F}})$ the set of sequences of real-valued random variables
$(\xi_{k})_{k\in\mathbb{N}}$ such that, for every $k\in\mathbb{N}$, $\xi_{k}$
is $\mathcal{F}_{k}$-measurable. For $p\in[1,\infty]$, we set

$\ell^{p}({\mathbb{F}})\triangleq\left\\{(\xi_{k})_{k\in\mathbb{N}}\in\ell^{0}({\mathbb{F}})|\sum_{k\geq
1}\lvert\xi_{k}\rvert^{p}<\infty\quad\mathbb{P}\text{-a.s.}\right\\}.$

We denote the set of summable non-negative sequences by
$\ell^{1}_{+}(\mathbb{N})$. We now collect some concepts from monotone
operator theory. For more details, we refer the reader to [9]. Let
$F:\mathsf{H}\to 2^{\mathsf{H}}$ be a set-valued operator. Its domain and
graph are defined as
$\operatorname{dom}F\triangleq\\{x\in\mathsf{H}|F(x)\neq\varnothing\\},\text{
and }\operatorname{gr}(F)\triangleq\\{(x,u)\in\mathsf{H}\times\mathsf{H}|u\in
F(x)\\},$ respectively. Recall that an operator $F:\mathsf{H}\to
2^{\mathsf{H}}$ is monotone if

$\langle v-w,x-y\rangle\geq 0\qquad\forall(x,v),(y,w)\in\operatorname{gr}(F).$
(2.1)

The set of zeros of $F$, denoted by $\mathsf{Zer}(T)$, defined as
$\mathsf{Zer}(F)\triangleq\\{x\in\mathsf{H}|0\in T(x)\\}$. The inverse of $F$
is $F^{-1}:\mathsf{H}\to 2^{\mathsf{H}},u\mapsto
F^{-1}(u)=\\{x\in\mathsf{H}|u\in F(x)\\}$. The resolvent of $F$ is
$J_{F}\triangleq(\operatorname{Id}+F)^{-1}.$ If $F$ is maximally monotone,
then $J_{F}$ is a single-valued map. We also need the classical notion of
_demiregularity_ of an operator.

######  Definition 2.1.

An operator $F:\mathsf{H}\to 2^{\mathsf{H}}$ is demiregular at
$x\in\operatorname{dom}(F)$ if for every sequence
$\\{(y_{n},u_{n})\\}_{n\in\mathbb{N}}\subset\operatorname{gr}(F)$ and every
$u\in F(y)$, we have

$\displaystyle[y_{n}\rightharpoonup y,v_{n}\to v]\Rightarrow y_{n}\to y.$

The notion of demiregularity captures various properties typically used to
establish strong convergence of dynamical systems. [5] exhibit a large class
of possibly set-valued operators $F$ which are demiregular. In particular,
demiregularity holds if $F$ is uniformly or strongly monotone, or when $F$ is
the subdifferential of a uniformly convex lower semi-continuous function $f$.

##  3 Algorithm

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a complete probability space. Our aim
is to solve the monotone inclusion problem (MI) under the following
assumption:

######  Assumption 2.

Consider Problem 1. The set-valued operator $T:\mathsf{H}\to 2^{\mathsf{H}}$
is maximally monotone with an efficiently computable resolvent. The single-
valued operator $V:\mathsf{H}\to\mathsf{H}$ is maximally monotone and
$L$-Lipschitz continuous ($L>0)$ with full domain
$\operatorname{dom}V=\mathsf{H}$.

Assumption 2 guarantees that the operator $F=T+V$ is maximally monotone [9,
Corolllary 24.4].

For numerical tractability, we make a _finite-dimensional noise_ assumption,
common to stochastic optimization problems in (possibly infinite-dimensional)
Hilbert spaces [42].222Our analysis does not rely on this assumption. It is
made here only for concreteness and because it is the most prevalent one in
applications.

######  Assumption 3 (Finite-dimensional Noise).

All randomness can be described via a finite dimensional random variable
$\xi:(\Omega,\mathcal{F})\to(\Xi,\mathcal{E})$, where
$\Xi\subseteq\mathbb{R}^{d}$ is a measurable set with Borel sigma algebra
$\mathcal{E}$. The law of the random variable $\xi$ is denoted by
${\mathsf{P}}$, i.e.
${\mathsf{P}}(\Gamma)\triangleq\mathbb{P}(\\{\omega\in\Omega|\xi(\omega)\in\Gamma\\})$
for all $\Gamma\in\mathcal{E}$.

To access new information about the values of the operator $V(x)$, we adopt a
_stochastic approximation_ (SA) approach where samples are accessed
iteratively and online: At each iteration, we assume to have access to a
stochastic oracle (SO) which generates some estimate on the value of the
deterministic operator $V(x)$ when the current position is $x$. This
information is obtained by drawing an iid sample form the law ${\mathsf{P}}$.
These fresh samples are then used in the numerical algorithm after an initial
extrapolation step delivering the point
$Z_{k}=X_{k}+\alpha_{k}(X_{k}-X_{k-1})$, for some extrapolation coefficient
$\alpha_{k}\in[0,1]$. Departing from $Z_{k}$, we call the SO to retrieve the
mini-batch estimator with _sample rate_ $m_{k}\in\mathbb{N}$:

$A_{k}(Z_{k},\omega)\triangleq\frac{1}{m_{k}}\sum_{t=1}^{m_{k}}\hat{V}(Z_{k},\xi_{k}^{(t)}(\omega)).$
(3.1)

$\xi_{k}\triangleq(\xi_{k}^{(1)},\ldots,\xi_{k}^{m_{k}})$ is the data sample
employed by the SO to return the estimator $A_{k}(Z_{k})$. Subsequently we
perform a forward-backward update with step size $\lambda_{k}>0$:

$Y_{k}=J_{\lambda_{k}T}\left(Z_{k}-\lambda_{k}A_{k}(Z_{k})\right).$ (3.2)

In the final updates, a second independent call of the SO is made, using the
data set $\eta_{k}=(\eta^{(1)}_{k},\ldots,\eta^{(m_{k})}_{k})$, yielding the
estimator

$B_{k}(Y_{k},\omega)\triangleq\frac{1}{m_{k}}\sum_{t=1}^{m_{k}}\hat{V}(Y_{k},\eta_{k}^{(t)}(\omega)),$
(3.3)

and the new state

$X_{k+1}=(1-\rho_{k})Z_{k}+\rho_{k}\left[Y_{k}+\lambda_{k}(A_{k}(Z_{k})-B_{k}(Y_{k}))\right]$
(3.4)

This iterative procedure generates a stochastic process
$\\{(Z_{k},Y_{k},X_{k})\\}_{k\in\mathbb{N}}$, defining the relaxed inertial
stochastic forward-backward-forward (RISFBF) scheme. A pseudocode is given as
Algorithm 1 below.

Input:  $X_{0},X_{1}\in\operatorname{dom}T$, Terminal time $K\in\mathbb{N}$,
nonnegative sequences
$(\alpha_{k})_{k=1}^{K},(\lambda_{k})_{k=1}^{K},(\rho_{k})_{k=1}^{K},(m_{k})_{k=1}^{K}$.

for $k=1,\ldots,K$ do

Compute $Z_{k}=X_{k}+\alpha_{k}(X_{k}-X_{k-1})$;

Draw an iid sample $\\{\xi_{k}^{(1)},\ldots,\xi_{k}^{(m_{k})}\\}$ from the law
${\mathsf{P}}$;

Compute $A_{k}(Z_{k})$ and $Y_{k}$ as in (3.1) and (3.2);

Draw an iid sample $\\{\eta_{k}^{(1)},\ldots,\eta_{k}^{(m_{k})}\\}$ from the
law ${\mathsf{P}}$;

Compute $B_{k}(Y_{k})$ and $X_{k+1}$ as in (3.3) and (3.4).

end for

Report
$\bar{X}_{K}=\sum_{k=1}^{K}\frac{\rho_{k}Y_{k}}{\sum_{k=1}^{K}\rho_{k}}.$
(3.5)

Algorithm 1 RISFBF

Note that RISFBF is still conceptual since we have not explained how the
sequences $(\alpha_{k})_{k\in\mathbb{N}},(\lambda_{k})_{k\in\mathbb{N}}$ and
$(\rho_{k})_{k\in\mathbb{N}}$ should be chosen. We will make this precise in
our complexity analysis, starting in Section 4.

###  3.1 Equivalent form of RISFBF

We can collect the sequential updates of RISFBF as the fixed-point iteration

$\left\\{\begin{array}[]{l}Z_{k}=X_{k}+\alpha_{k}(X_{k}-X_{k-1}),\\\
X_{k+1}=Z_{k}-\rho_{k}\Phi_{k,\lambda_{k}}(Z_{k})\end{array}\right.$ (3.6)

where $\Phi_{k,\lambda}:\mathsf{H}\times\Omega\to\mathsf{H}$ is the time-
varying map given by

$\Phi_{k,\lambda}(x,\omega)\triangleq x-\lambda
A_{k}(x,\omega)-(\operatorname{Id}_{\mathsf{H}}-\lambda
B_{k}(\cdot,\omega))\circ J_{\lambda
T}\circ(\operatorname{Id}_{\mathsf{H}}-\lambda A_{k}(\cdot,\omega))(x).$

Formulating the algorithm in this specific way establishes the connection
between RISFBF and the Heavy-ball system. Indeed, combining the iterations in
(3.6) in one, we get a second-order difference equations, closely resembling
the structure present in (HB):

$\frac{1}{\rho_{k}}(X_{k+1}-2X_{k}-X_{k-1})+\frac{(1-\alpha_{k})}{\rho_{k}}(X_{k}-X_{k-1})+\Phi_{k,\lambda_{k}}(X_{k}+\alpha_{k}(X_{k}-X_{k-1}))=0.$

Also, it reveals the Markovian nature of the process
$(X_{k})_{k\in\mathbb{N}}$; It is clear from the formulation (3.6) that
$X_{k}$ is Markov with respect to the sigma-algebra
$\sigma(\\{X_{0},\ldots,X_{k-1}\\})$.

###  3.2 Assumptions on the stochastic oracle

In order to tame the stochastic uncertainty in RISFBF, we need to impose some
assumptions on the distributional properties of the random fields
$(A_{k}(x))_{k\in\mathbb{N}}$ and $(B_{k}(x))_{k\in\mathbb{N}}$. One crucial
statistic we need to control is the SO variance. Define the _oracle error_ at
a point $x\in\mathsf{H}$ as

$\varepsilon(x,\xi)\triangleq\hat{V}(x,\xi)-V(x).$ (3.7)

######  Assumption 4 (Oracle Noise).

We say that the SO

  * (i)

is conditionally unbiased if $\mathbb{E}_{\xi}[\varepsilon(x,\xi)|x]=0$ for
all $x\in\mathsf{H}$;

  * (ii)

enjoys a uniform variance bound:
$\mathbb{E}_{\xi}[\lVert\varepsilon(x,\xi)\rVert^{2}|x]\leq\sigma^{2}$ for
some $\sigma>0$ and all $x\in\mathsf{H}$.

Define

$\displaystyle
U_{k}(\omega)\triangleq\frac{1}{m_{k}}\sum_{t=1}^{m_{k}}\varepsilon(Z_{k}(\omega),\xi_{k}^{(t)}(\omega)),\text{
and
}W_{k}(\omega)\triangleq\frac{1}{m_{k}}\sum_{t=1}^{m_{k}}\varepsilon(Y_{k}(\omega),\eta^{(t)}_{k}(\omega)).$

The introduction of these two processes allows us to decompose the random
estimator into a mean component and a residual, so that

$\displaystyle A_{k}(Z_{k})$ $\displaystyle=V(Z_{k})+U_{k},\text{ and
}B_{k}(Y_{k})=V(Y_{k})+W_{k}$

If Assumption 4(i) holds true then
$\mathbb{E}[W_{k}|\hat{\mathcal{F}}_{k}]=0=\mathbb{E}[U_{k}|\mathcal{F}_{k}]=0$.
Hence, under conditional unbiasedness, the processes
$\\{(U_{k},\mathcal{F}_{k});k\in\mathbb{N}\\}$ and
$\\{(W_{k},\hat{\mathcal{F}_{k}});k\in\mathbb{N}\\}$ are martingale difference
sequences, where the filtrations are defined as
$\mathcal{F}_{0}\triangleq\hat{\mathcal{F}}_{0}\triangleq\mathcal{F}_{1}\triangleq\sigma(X_{0},X_{1})$,
and iteratively, for $k\geq 1$,

$\displaystyle\hat{\mathcal{F}}_{k}\triangleq\sigma(X_{0},X_{1},\xi_{1},\eta_{1},\ldots,\eta_{k-1},\xi_{k}),\;\mathcal{F}_{k+1}\triangleq\sigma(X_{0},X_{1},\xi_{1},\eta_{1},\ldots,\xi_{k},\eta_{k}).$

Observe that
$\mathcal{F}_{k}\subseteq\hat{\mathcal{F}}_{k}\subseteq\mathcal{F}_{k+1}$ for
all $k\geq 1$. The uniform variance bound, Assumption 4(ii), ensures that the
processes
$\\{(U_{k},\mathcal{F}_{k});k\in\mathbb{N}\\},\\{(W_{k},\hat{\mathcal{F}_{k}});k\in\mathbb{N}\\}$
have finite second moment.

######  Remark 3.1.

For deriving the stochastic estimates in the analysis to come, it is important
to emphasize that $X_{k}$ is $\mathcal{F}_{k}$-measurable for all $k\geq 0$,
and $Y_{k}$ is $\hat{\mathcal{F}}_{k}$-measurable.

The mini-batch sampling technology implies an online variance reduction
effect, summarized in the next Lemma, whose simple proof we omit.

######  Lemma 3.1 (Variance of the SO).

Suppose Assumption 4 holds. Then for $k\geq 1$,

$\displaystyle\mathbb{E}[\lVert
W_{k}\rVert^{2}|\mathcal{F}_{k}]\leq\frac{\sigma^{2}}{m_{k}}\text{ and
}\mathbb{E}[\lVert
U_{k}\rVert^{2}|\mathcal{F}_{k}]\leq\frac{\sigma^{2}}{m_{k}},\qquad\mathbb{P}-\text{a.s.}$
(3.8)

We see that larger sampling rates lead to more precise point estimates of the
single-valued operator. This comes at the cost of more evaluations of the
stochastic operator. Hence, any mini-batch approach faces a trade-off between
the _oracle complexity_ and the iteration complexity. We want to use mini-
batch estimators to achieve an online variance reduction scheme, motivating
the next assumption.

######  Assumption 5 (Batch Size).

The batch size sequence $(m_{k})_{k\geq 1}$ is non-decreasing and satisfies
$\sum_{k=1}^{\infty}\frac{1}{m_{k}}<\infty$.

##  4 Analysis

This section is organized into three subsections. The first subsection derives
asymptotic convergence guarantees, while the second and third subsections
provides linear and sublinear rate statements in strongly monotone and
monotone regimes, respectively.

###  4.1 Asymptotic Convergence

Given $\lambda>0$, we define the residual function for the monotone inclusion
(MI) as

$\mathsf{res}_{\lambda}(x)\triangleq\lVert x-J_{\lambda T}(x-\lambda
V(x))\rVert.$ (4.1)

Clearly, for every $\lambda>0$,
$x\in\mathsf{S}\Leftrightarrow\mathsf{res}_{\lambda}(x)=0$. Hence,
$\mathsf{res}_{\lambda}(\cdot)$ is a _merit function_ for the monotone
inclusion problem. To put this merit function into context, let us consider
the special case where $T$ is the subdifferential of a lower semi-continuous
convex function $g:\mathsf{H}\to[0,\infty]$, i.e. $T=\partial g$. In this
case, the resolvent $J_{\lambda T}$ reduces to the well-known _proximal-
operator_

$\operatorname{prox}_{\lambda
g}(x)\triangleq\operatorname*{argmin}_{u\in\mathsf{H}}\\{\lambda
g(u)+\frac{1}{2}\lVert u-x\rVert^{2}\\}.$

In the potential case, where $V(x)=\nabla f(x)$ for some smooth convex
function $f:\mathsf{H}\to\mathbb{R}$, the residual function is thus seen to be
a constant multiple of the norm of the so-called _gradient mapping_ $\lVert
x-\operatorname{prox}_{\lambda g}(x-\lambda V(x))\rVert$, which is a standard
merit function in convex [62] and stochastic [26, 52] optimization. We use
this function to quantify the per-iteration progress of RISFBF. The main
result of this subsection is the following.

######  Theorem 4.1 (Asymptotic Convergence).

Let $\bar{\alpha},\bar{\varepsilon}\in(0,1)$ be fixed parameters. Suppose that
Assumption 1-5 holds true. Let $(\alpha_{k})_{k\in\mathbb{N}}$ be a non-
decreasing sequence such that $\lim_{k\to\infty}\alpha_{k}=\bar{\alpha}$. Let
$(\lambda_{k})_{k\in\mathbb{N}}$ be a converging sequence in
$(0,\frac{1}{4L})$ such that
$\lim_{k\to\infty}\lambda_{k}=\lambda\in(0,\frac{1}{4L})$. If
$\rho_{k}=\frac{5(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}{4(2\alpha_{k}^{2}-\alpha_{k}+1)(1+L\lambda_{k})}$
for all $k\geq 1$, then

  * (i)

$\lim_{k\to\infty}\mathsf{res}_{\lambda_{k}}(Z_{k})=0$ in $L^{2}(\mathbb{P})$;

  * (ii)

the stochastic process $(X_{k})_{k\in\mathbb{N}}$ generated by algorithm
RISFBF weakly converges to a $\mathsf{S}$-valued limiting random variable $X$;

  * (iii)

$\sum_{k=1}^{\infty}\left[(1-\alpha_{k})\left(\frac{5(1-\alpha_{k}}{4\rho_{k}(1+L\lambda_{k})}-1\right)-2\alpha_{k}^{2}\right]\lVert
X_{k}-X_{k-1}\rVert^{2}<\infty\quad\mathbb{P}$-a.s.

We prove this Theorem via a sequence of technical Lemmas. Our proof strategy
for Theorem 4.1 follows [15], where a stochastic quasi-Fejér principle is
established, including the residual function. We start with a basic relation.

######  Lemma 4.2.

For all $k\geq 1$, we have

$-\lVert Z_{k}-Y_{k}\rVert^{2}\leq\lambda^{2}_{k}\lVert
U_{k}\rVert^{2}-\frac{1}{2}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k}).$ (4.2)

###### Proof.

By definition,

$\displaystyle\frac{1}{2}\mathsf{res}_{\lambda_{k}}^{2}(Z_{k})$
$\displaystyle=\frac{1}{2}\lVert
Z_{k}-J_{\lambda_{k}T}(Z_{k}-\lambda_{k}V(Z_{k}))\rVert^{2}=\frac{1}{2}\lVert
Z_{k}-Y_{k}+J_{\lambda_{k}T}(Z_{k}-\lambda_{k}A_{k}(Z_{k}))-J_{\lambda_{k}T}(Z_{k}-\lambda_{k}V(Z_{k}))\rVert^{2}$
$\displaystyle\leq\lVert Z_{k}-Y_{k}\rVert^{2}+\lVert
J_{\lambda_{k}T}(Z_{k}-\lambda_{k}A_{k}(Z_{k}))-J_{\lambda_{k}T}(Z_{k}-\lambda_{k}V(Z_{k}))\rVert^{2}\leq\lVert
Z_{k}-Y_{k}\rVert^{2}+\lambda^{2}_{k}\lVert U_{k}\rVert^{2},$

where the last inequality uses the non-expansivity property of the resolvent
operator. Rearranging terms gives the claimed result. $\blacksquare$
$\blacksquare$

Next, for a given pair $(p,p^{\ast})\in\operatorname{gr}(F)$, we define the
stochastic processes $(\Delta M_{k})_{k\in\mathbb{N}},(\Delta
N_{k}(p,p^{\ast}))_{k\in\mathbb{N}}$, and $(\mathtt{e}_{k})_{k\in\mathbb{N}}$
as

$\displaystyle\Delta
M_{k}\triangleq\frac{5\rho_{k}\lambda_{k}^{2}}{2(1+L\lambda_{k})}\lVert\mathtt{e}_{k}\rVert^{2}+\frac{\rho_{k}\lambda^{2}_{k}}{2}\lVert
U_{k}\rVert^{2},$ (4.3) $\displaystyle\Delta N_{k}(p,p^{\ast})\triangleq
2\rho_{k}\lambda_{k}\langle W_{k}+p^{\ast},p-Y_{k}\rangle,\text{ and }$ (4.4)
$\displaystyle\mathtt{e}_{k}\triangleq W_{k}-U_{k}.$ (4.5)

Key to our analysis is the following energy bound on the evolution of the
anchor sequence $\left(\lVert X_{k}-p\rVert^{2}\right)_{k\in\mathbb{N}}$.

######  Lemma 4.3 (Fundamental Recursion).

Let $(X_{k})_{k\in\mathbb{N}}$ be the stochastic process generated by RISFBF
with $\alpha_{k}\in(0,1)$, $0\leq\rho_{k}<\frac{5}{4(1+L\lambda_{k})}$, and
$\lambda_{k}\in(0,1/4L)$. For all $k\geq 1$ and
$(p,p^{\ast})\in\operatorname{gr}(F)$, we have

$\displaystyle\lVert X_{k+1}-p\rVert^{2}$
$\displaystyle\leq(1+\alpha_{k})\lVert X_{k}-p\rVert^{2}-\alpha_{k}\lVert
X_{k-1}-p\rVert^{2}-\frac{\rho_{k}}{4}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})$
$\displaystyle+\Delta M_{k}+\Delta
N_{k}(p,p^{\ast})-2\rho_{k}\lambda_{k}\langle V(Y_{k})-V(p),Y_{k}-p\rangle$
$\displaystyle+\alpha_{k}\lVert
X_{k}-X_{k-1}\rVert^{2}\left(2\alpha_{k}+\frac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}\right)$
$\displaystyle-(1-\alpha_{k})\left(\frac{5}{4\rho_{k}(1+L\lambda_{k})}-1\right)\lVert
X_{k+1}-X_{k}\rVert^{2}.$

###### Proof.

To simplify the notation, let us call $A_{k}\equiv A_{k}(Z_{k})$ and
$B_{k}\equiv B_{k}(Y_{k})$. We also introduce the intermediate update
$R_{k}\triangleq Y_{k}+\lambda_{k}(A_{k}-B_{k})$. For all $k\geq 0$, it holds
true that

$\displaystyle\lVert Z_{k}-p\rVert^{2}$ $\displaystyle=\lVert
Z_{k}-Y_{k}+Y_{k}-R_{k}+R_{k}-p\rVert^{2}$ $\displaystyle=\lVert
Z_{k}-Y_{k}\rVert^{2}+\lVert Y_{k}-R_{k}\rVert^{2}+\lVert
R_{k}-p\rVert^{2}+2\langle Z_{k}-Y_{k},Y_{k}-p\rangle+2\langle
Y_{k}-R_{k},R_{k}-p\rangle$ $\displaystyle=\lVert Z_{k}-Y_{k}\rVert^{2}+\lVert
Y_{k}-R_{k}\rVert^{2}+\lVert R_{k}-p\rVert^{2}+2\langle
Z_{k}-Y_{k},Y_{k}-p\rangle+2\langle Y_{k}-R_{k},R_{k}-p\rangle$
$\displaystyle=\lVert Z_{k}-Y_{k}\rVert^{2}+\lVert
Y_{k}-R_{k}\rVert^{2}+\lVert R_{k}-p\rVert^{2}+2\langle
Z_{k}-Y_{k},Y_{k}-p\rangle+2\langle Y_{k}-R_{k},Y_{k}-p\rangle$
$\displaystyle+2\langle Y_{k}-R_{k},R_{k}-Y_{k}\rangle$ $\displaystyle=\lVert
Z_{k}-Y_{k}\rVert^{2}+\lVert Y_{k}-R_{k}\rVert^{2}+\lVert
R_{k}-p\rVert^{2}+2\langle Z_{k}-R_{k},Y_{k}-p\rangle+2\langle
Y_{k}-R_{k},R_{k}-Y_{k}\rangle$ $\displaystyle=\lVert
Z_{k}-Y_{k}\rVert^{2}-\lVert Y_{k}-R_{k}\rVert^{2}+\lVert
R_{k}-p\rVert^{2}+2\langle Z_{k}-R_{k},Y_{k}-p\rangle.$

Since

$\displaystyle\lVert Y_{k}-R_{k}\rVert^{2}$
$\displaystyle=\lambda^{2}_{k}\lVert B_{k}(Y_{k})-Y_{k}(Z_{k})\rVert^{2}$
$\displaystyle\leq\lambda_{k}^{2}\lVert
V(Y_{k})-V(Z_{k})+W_{k+1}-U_{k+1}\rVert^{2}$
$\displaystyle\leq\lambda_{k}^{2}\lVert
V(Y_{k})-V(Z_{k})\rVert^{2}+\lambda_{k}^{2}\lVert
W_{k}-U_{k}\rVert^{2}+2\lambda_{k}^{2}\langle
V(Y_{k})-V(Z_{k}),W_{k}-U_{k}\rangle$ $\displaystyle\leq
L^{2}\lambda_{k}^{2}\lVert Y_{k}-Z_{k}\rVert^{2}+\lambda_{k}^{2}\lVert
W_{k}-U_{k}\rVert^{2}+2\lambda_{k}^{2}\langle
V(Y_{k})-V(Z_{k}),W_{k}-U_{k}\rangle$ $\displaystyle\leq
2L^{2}\lambda_{k}^{2}\lVert Y_{k}-Z_{k}\rVert^{2}+2\lambda_{k}^{2}\lVert
W_{k}-U_{k}\rVert^{2}.$

Introducing the process $(\mathtt{e}_{k})_{k\in\mathbb{N}}$ from eq. (4.5),
the aforementioned set of inequalities reduces to

$\lVert Y_{k}-R_{k}\rVert^{2}\leq 2L^{2}\lambda_{k}^{2}\lVert
Y_{k}-Z_{k}\rVert^{2}+2\lambda_{k}^{2}\lVert\mathtt{e}_{k}\rVert^{2}.$

Hence,

$\displaystyle\lVert Z_{k}-p\rVert^{2}\geq(1-2L^{2}\lambda_{k}^{2})\lVert
Z_{k}-Y_{k}\rVert^{2}-2\lambda_{k}^{2}\lVert\mathtt{e}_{k}\rVert^{2}+\lVert
R_{k}-p\rVert^{2}+2\langle Z_{k}-R_{k},Y_{k}-p\rangle.$

But $Y_{k}+\lambda_{k}T(Y_{k})\ni Z_{k}-\lambda_{k}A_{k}$, implying that

$\frac{1}{\lambda_{k}}(Z_{k}-Y_{k}-\lambda_{k}A_{k})\in T(Y_{k}).$

Pick $(p,p^{\ast})\in\operatorname{gr}(F)$, so that $p^{\ast}-V(p)\in T(p)$.
Then, the monotonicity of $T$ yields the estimate

$\langle\frac{1}{\lambda_{k}}(Z_{k}-Y_{k}-\lambda_{k}A_{k})-p^{\ast}+V(p),Y_{k}-p\rangle\geq
0.$

This is equivalent to

$\displaystyle\langle\frac{1}{\lambda_{k}}(Z_{k}-R_{k}-\lambda_{k}B_{k})-p^{\ast}+V(p),Y_{k}-p\rangle\geq
0,$ or $\displaystyle\langle Z_{k}-R_{k},Y_{k}-p\rangle\geq\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle+\lambda_{k}\langle
V(Y_{k})-V(p),Y_{k}-p\rangle.$ (4.6)

This implies that

$\displaystyle\langle Z_{k}-R_{k},Y_{k}-x^{\ast}\rangle\geq\lambda_{k}\langle
W_{k},Y_{k}-x^{\ast}\rangle.$

Hence, we obtain the following,

$\displaystyle\lVert Z_{k}-p\rVert^{2}$
$\displaystyle\geq(1-2L^{2}\lambda^{2}_{k})\lVert Y_{k}-Z_{k}\rVert^{2}+\lVert
R_{k}-p\rVert^{2}-2\lambda^{2}_{k}\lVert\mathtt{e}_{k}\rVert^{2}$
$\displaystyle+2\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle+2\lambda_{k}\langle
V(Y_{k})-V(p),Y_{k}-p\rangle.$

Rearranging terms, we arrive at the following bound on $\lVert
R_{k}-p\rVert^{2}$:

$\displaystyle\lVert R_{k}-p\rVert^{2}\leq$ $\displaystyle\lVert
Z_{k}-p\rVert^{2}-(1-2L^{2}\lambda_{k}^{2})\lVert
Y_{k}-Z_{k}\rVert^{2}+2\lambda^{2}_{k}\lVert\mathtt{e}_{k}\rVert^{2}+2\lambda_{k}\langle
W_{k}+p^{\ast},p-Y_{k}\rangle$ (4.7) $\displaystyle+2\lambda_{k}\langle
V(Y_{k})-V(p),p-Y_{k}\rangle$

Next, we observe that $\lVert X_{k+1}-p\rVert^{2}$ may be bounded as follows.

$\displaystyle\lVert X_{k+1}-p\rVert^{2}$
$\displaystyle=\lVert(1-\rho_{k})Z_{k}+\rho_{k}R_{k}-p\rVert^{2}$
$\displaystyle=\lVert(1-\rho_{k})(Z_{k}-p)-\rho_{k}(R_{k}-p)\rVert^{2}$
$\displaystyle=(1-\rho_{k})^{2}\lVert Z_{k}-p\rVert^{2}+\rho_{k}^{2}\lVert
R_{k}-p\rVert^{2}-2\rho_{k}(1-\rho_{k})\langle Z_{k}-p,R_{k}-p\rangle$
$\displaystyle=(1-\rho_{k})\lVert Z_{k}-p\rVert^{2}-\rho_{k}(1-\rho_{k})\lVert
Z_{k}-p\rVert^{2}+\rho_{k}\lVert R_{k}-p\rVert^{2}-\rho_{k}(1-\rho_{k})\lVert
R_{k}-p\rVert^{2}$ $\displaystyle+2\rho_{k}(1-\rho_{k})\langle
Z_{k}-p,R_{k}-p\rangle$ $\displaystyle=(1-\rho_{k})\lVert
Z_{k}-p\rVert^{2}+\rho_{k}\lVert R_{k}-p\rVert^{2}-\rho_{k}(1-\rho_{k})\lVert
R_{k}-Z_{k}\rVert^{2}$ $\displaystyle=(1-\rho_{k})\lVert
Z_{k}-p\rVert^{2}+\rho_{k}\lVert
R_{k}-p\rVert^{2}-\frac{1-\rho_{k}}{\rho_{k}}\lVert X_{k+1}-Z_{k}\rVert^{2}.$
(4.8)

We may then derive a bound on the expression in (4.8),

$\displaystyle\quad(1-\rho_{k})\lVert Z_{k}-p\rVert^{2}+\rho_{k}\lVert
R_{k}-p\rVert^{2}-\frac{1-\rho_{k}}{\rho_{k}}\lVert X_{k+1}-Z_{k}\rVert^{2}$
$\displaystyle\leq\lVert Z_{k}-p\rVert^{2}-\frac{1-\rho_{k}}{\rho_{k}}\lVert
X_{k+1}-Z_{k}\rVert^{2}-\rho_{k}(1-2L^{2}\lambda^{2}_{k})\lVert
Z_{k}-Y_{k}\rVert^{2}$
$\displaystyle+2\lambda^{2}_{k}\rho_{k}\lVert\mathtt{e}_{k}\rVert^{2}-2\rho_{k}\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle+2\rho_{k}\lambda_{k}\langle
V(Y_{k})-V(p),p-Y_{k}\rangle$ (4.9) $\displaystyle=\lVert
Z_{k}-p\rVert^{2}-\frac{1-\rho_{k}}{\rho_{k}}\lVert
X_{k+1}-Z_{k}\rVert^{2}-\rho_{k}(1/2-2L^{2}\lambda^{2}_{k})\lVert
Z_{k}-Y_{k}\rVert^{2}$
$\displaystyle+2\lambda^{2}_{k}\rho_{k}\lVert\mathtt{e}_{k}\rVert^{2}-2\rho_{k}\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle$ $\displaystyle-\frac{\rho_{k}}{2}\lVert
Y_{k}-Z_{k}\rVert^{2}+2\rho_{k}\lambda_{k}\langle
V(Y_{k})-V(p),p-Y_{k}\rangle.$ (4.10)

By invoking (4.2), we arrive at the estimate

$\displaystyle\lVert X_{k+1}-p\rVert^{2}$ $\displaystyle\leq\lVert
Z_{k}-p\rVert^{2}-\frac{1-\rho_{k}}{\rho_{k}}\lVert
X_{k+1}-Z_{k}\rVert^{2}+2\lambda^{2}\rho_{k}\lVert\mathtt{e}_{k}\rVert^{2}-2\rho_{k}\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle$
$\displaystyle-\rho_{k}(1/2-2L^{2}\lambda^{2}_{k})\lVert
Y_{k}-Z_{k}\rVert^{2}-\frac{\rho_{k}}{4}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})$
$\displaystyle+\frac{\rho_{k}\lambda^{2}_{k}}{2}\lVert
U_{k}\rVert^{2}+2\rho_{k}\lambda_{k}\langle V(Y_{k})-V(p),p-Y_{k}\rangle.$

Furthermore,

$\displaystyle\frac{1}{\rho_{k}}\lVert X_{k+1}-Z_{k}\rVert$
$\displaystyle=\lVert R_{k}-Z_{k}\rVert\leq\lVert R_{k}-Y_{k}\rVert+\lVert
Y_{k}-Z_{k}\rVert$ $\displaystyle\leq\lambda_{k}\lVert
B_{k}-A_{k}\rVert+\lVert Y_{k}-Z_{k}\rVert$
$\displaystyle\leq(1+L\lambda_{k})\lVert
Y_{k}-Z_{k}\rVert+\lambda_{k}\lVert\mathtt{e}_{k}\rVert,$

which implies that

$\displaystyle\frac{1}{2\rho^{2}_{k}}\lVert
X_{k+1}-Z_{k}\rVert^{2}\leq(1+L\lambda_{k})^{2}\lVert
Y_{k}-Z_{k}\rVert^{2}+\lambda^{2}_{k}\lVert\mathtt{e}_{k}\rVert^{2}.$ (4.11)

Multiplying both sides by
$\frac{\rho_{k}(1/2-2L\lambda_{k})}{1+L\lambda_{k}}$, a positive scalar since
$\lambda_{k}\in(0,\tfrac{1}{4L})$, we obtain

$\displaystyle\frac{1/2-2L\lambda_{k}}{2\rho_{k}(1+L\lambda_{k})}\lVert
X_{k+1}-Z_{k}\rVert^{2}$
$\displaystyle\leq\rho_{k}(1/2-2L\lambda_{k})(1+L\lambda_{k})\lVert
Y_{k}-Z_{k}\rVert^{2}$
$\displaystyle+\frac{\lambda^{2}_{k}\rho_{k}(1/2-2L\lambda_{k})}{1+L\lambda_{k}}\lVert\mathtt{e}_{k}\rVert^{2}.$
(4.12)

Rearranging terms, and noting that $(1/2-2L\lambda_{k})(1+L\lambda_{k})\leq
1/2-2L^{2}\lambda^{2}_{k}$, the above estimate becomes

$\displaystyle-\rho_{k}(1/2-2L^{2}\lambda^{2}_{k})\lVert
Y_{k}-Z_{k}\rVert^{2}$
$\displaystyle\leq-\frac{1/2-2L\lambda_{k}}{2\rho_{k}(1+L\lambda_{k})}\lVert
X_{k+1}-Z_{k}\rVert^{2}$
$\displaystyle+\frac{\rho_{k}\lambda^{2}_{k}(1/2-2L\lambda_{k})}{1+L\lambda_{k}}\lVert\mathtt{e}_{k}\rVert^{2}.$
(4.13)

Substituting this bound into the first majorization of the anchor process
$\lVert X_{k+1}-p\rVert^{2}$, we see

$\displaystyle\lVert X_{k+1}-p\rVert^{2}$ $\displaystyle\leq\lVert
Z_{k}-p\rVert^{2}-\left(\frac{1-\rho_{k}}{\rho_{k}}+\frac{1/2-2L\lambda_{k}}{2\rho_{k}(1+L\lambda_{k})}\right)\lVert
X_{k+1}-Z_{k}\rVert^{2}$
$\displaystyle+\rho_{k}\lambda_{k}^{2}\lVert\mathtt{e}_{k}\rVert^{2}\left(2+\frac{1/2-2L\lambda_{k}}{1+L\lambda_{k}}\right)+2\rho_{k}\lambda_{k}\langle
V(Y_{k})-V(p),p-Y_{k}\rangle$ $\displaystyle-2\rho_{k}\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle-\frac{\rho_{k}}{4}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})+\frac{\rho_{k}\lambda^{2}_{k}}{2}\lVert
U_{k}\rVert^{2}$ $\displaystyle=\lVert
Z_{k}-p\rVert^{2}-\frac{\rho_{k}}{4}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})+\frac{\rho_{k}\lambda^{2}_{k}}{2}\lVert
U_{k}\rVert^{2}-2\rho_{k}\lambda_{k}\langle W_{k}+p^{\ast},Y_{k}-p\rangle$
$\displaystyle-\frac{5/2-2\rho_{k}(1+L\lambda_{k})}{2\rho_{k}(1+L\lambda_{k})}\lVert
X_{k+1}-Z_{k}\rVert^{2}$
$\displaystyle+\frac{5\rho_{k}\lambda_{k}^{2}}{2(1+L\lambda_{k})}\lVert\mathtt{e}_{k}\rVert^{2}+2\rho_{k}\lambda_{k}\langle
V(Y_{k})-V(p),p-Y_{k}\rangle.$

Observe that

$\displaystyle\lVert X_{k+1}-Z_{k}\rVert^{2}$
$\displaystyle=\lVert(X_{k+1}-X_{k})-\alpha_{k}(X_{k}-X_{k-1})\rVert^{2}$
$\displaystyle\geq(1-\alpha_{k})\lVert
X_{k+1}-X_{k}\rVert^{2}+(\alpha^{2}_{k}-\alpha_{k})\lVert
X_{k}-X_{k-1}\rVert^{2},$ (4.14)

and Lemma A.1 gives

$\lVert Z_{k}-p\rVert^{2}=(1+\alpha_{k})\lVert
X_{k}-p\rVert^{2}-\alpha_{k}\lVert
X_{k-1}-p\rVert^{2}+\alpha_{k}(1+\alpha_{k})\lVert X_{k}-X_{k-1}\rVert^{2}.$
(4.15)

By hypothesis, $\alpha_{k},\rho_{k},\lambda_{k}$ are defined such that
$\frac{5/2-2\rho_{k}(1+L\lambda_{k})}{2\rho_{k}(1+L\lambda_{k})}>0$. Then,
using both of these relations in the last estimate for $\lVert
X_{k+1}-p\rVert^{2}$, we arrive at

$\displaystyle\lVert X_{k+1}-p\rVert^{2}$
$\displaystyle\leq(1+\alpha_{k})\lVert X_{k}-p\rVert^{2}-\alpha_{k}\lVert
X_{k-1}-p\rVert^{2}+\alpha_{k}(1+\alpha_{k})\lVert
X_{k}-X_{k-1}\rVert^{2}-2\rho_{k}\lambda_{k}\langle
W_{k+1}+p^{\ast},Y_{k}-p\rangle$
$\displaystyle-\frac{\rho_{k}}{4}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})+\frac{5\rho_{k}\lambda_{k}^{2}}{2(1+L\lambda_{k})}\lVert\mathtt{e}_{k}\rVert^{2}+\frac{\rho_{k}\lambda^{2}_{k}}{2}\lVert
U_{k}\rVert^{2}+2\rho_{k}\lambda_{k}\langle V(Y_{k})-V(p),p-Y_{k}\rangle$
$\displaystyle-\left(\frac{5}{4\rho_{k}(1+L\lambda_{k})}-1\right)\left[(1-\alpha_{k})\lVert
X_{k+1}-X_{k}\rVert^{2}+(\alpha^{2}_{k}-\alpha_{k})\lVert
X_{k}-X_{k-1}\rVert^{2}\right].$

Using the respective definitions of the stochastic increments $\Delta
M_{k},\Delta N_{k}(p,p^{\ast})$ in (4.3) and (4.4), we arrive at

$\displaystyle\lVert X_{k+1}-p\rVert^{2}$
$\displaystyle\leq(1+\alpha_{k})\lVert X_{k}-p\rVert^{2}-\alpha_{k}\lVert
X_{k-1}-p\rVert^{2}-\frac{\rho_{k}}{4}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})$
$\displaystyle+\Delta M_{k}+\Delta
N_{k}(p,p^{\ast})-2\rho_{k}\lambda_{k}\langle V(Y_{k})-V(p),Y_{k}-p\rangle$
$\displaystyle+\alpha_{k}\lVert
X_{k}-X_{k-1}\rVert^{2}\left(2\alpha_{k}+\frac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}\right)$
$\displaystyle-(1-\alpha_{k})\left(\frac{5}{4\rho_{k}(1+L\lambda_{k})}-1\right)\lVert
X_{k+1}-X_{k}\rVert^{2}.$ (4.16)

$\blacksquare$ $\blacksquare$

Recall that $Y_{k}$ is $\hat{\mathcal{F}}_{k}$-measurable. By the law of
iterated expectations, we therefore see

$\displaystyle\mathbb{E}[\Delta
N_{k}(p,p^{\ast})|\mathcal{F}_{k}]=\mathbb{E}\left\\{\mathbb{E}[\Delta
N_{k}(p,p^{\ast})|\hat{\mathcal{F}}_{k}]|\mathcal{F}_{k}\right\\}=2\rho_{k}\lambda_{k}\mathbb{E}[\langle
p^{\ast},p-Y_{k}\rangle|\mathcal{F}_{k}],$

for all $(p,p^{\ast})\in\operatorname{gr}(F)$. Observe that if we choose
$(p,0)\in\operatorname{gr}(F)$, meaning that $p\in\mathsf{S}$, then $\Delta
N_{k}(p,0)\equiv\Delta N_{k}(p)$ is a martingale difference sequence.
Furthermore, for all $k\geq 1$,

$\mathbb{E}[\Delta
M_{k}|\mathcal{F}_{k}]\leq\frac{5\rho_{k}\lambda_{k}^{2}}{1+L\lambda_{k}}\mathbb{E}[\lVert
W_{k}\rVert^{2}|\mathcal{F}_{k}]+\lambda^{2}_{k}\left(\frac{5\rho_{k}}{1+L\lambda_{k}}+\frac{\rho_{k}}{2}\right)\mathbb{E}[\lVert
U_{k}\rVert^{2}|\mathcal{F}_{k}]\leq\frac{\mathtt{a}_{k}\sigma^{2}}{m_{k}},$
(4.17)

where
$\mathtt{a}_{k}\triangleq\lambda^{2}_{k}\left(\frac{10\rho_{k}}{1+L\lambda_{k}}+\frac{\rho_{k}}{2}\right)$.

To prove the a.s. convergence of the stochastic process
$(X_{k})_{k\in\mathbb{N}}$, we rely on the following preparations. Motivated
by the analysis of deterministic inertial schemes, we are interested in a
regime under which $\alpha_{k}$ is non-decreasing.

For a fixed reference point $p\in\mathsf{H}$, define the anchor sequences
$\phi_{k}(p)\triangleq\frac{1}{2}\lVert X_{k}-p\rVert^{2}$, and the energy
sequence $\Delta_{k}\triangleq\frac{1}{2}\lVert X_{k}-X_{k-1}\rVert^{2}.$ In
terms of these sequences, we can rearrange the fundamental recursion from
Lemma 4.3 to obtain

$\displaystyle\phi_{k+1}(p)-$
$\displaystyle\alpha_{k}\phi_{k}(p)-(1-\alpha_{k})\left(\frac{5}{4\rho_{k}(1+L\lambda_{k})}-1\right)\Delta_{k+1}\leq\phi_{k}(p)-\alpha_{k}\phi_{k-1}(p)$
$\displaystyle-(1-\alpha_{k})\left(\frac{5}{4\rho_{k}(1+L\lambda_{k})}-1\right)\Delta_{k}+\frac{1}{2}\Delta
M_{k}+\frac{1}{2}\Delta N_{k}(p,p^{\ast})$
$\displaystyle-\rho_{k}\lambda_{k}\langle
V(Y_{k})-V(p),Y_{k}-p\rangle+\Delta_{k}\left[2\alpha^{2}_{k}+(1-\alpha_{k})\left(1-\frac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}\right)\right]$
$\displaystyle-\frac{\rho_{k}}{8}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k}).$

For a given pair $(p,p^{\ast})\in\operatorname{gr}(F)$, define

$Q_{k}(p)\triangleq\phi_{k}(p)-\alpha_{k}\phi_{k-1}(p)+(1-\alpha_{k})\left(\frac{5}{4\rho_{k}(1+L\lambda_{k})}-1\right)\Delta_{k}.$
(4.18)

Then, in terms of the sequence

$\beta_{k+1}\triangleq(1-\alpha_{k})\left(\frac{5}{4\rho_{k}(1+L\lambda_{k})}-1\right)-(1-\alpha_{k+1})\left(\frac{5}{4\rho_{k+1}(1+L\lambda_{k+1})}-1\right),$
(4.19)

and using the monotonicity of $V$, guaranteeing that $\langle
V(Y_{k})-V(p),Y_{k}-p\rangle\geq 0$, we get

$\displaystyle Q_{k+1}(p)$ $\displaystyle\leq
Q_{k}(p)-\frac{\rho_{k}}{8}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})+\frac{1}{2}\Delta
M_{k}+\frac{1}{2}\Delta
N_{k}(p,p^{\ast})+(\alpha_{k}-\alpha_{k+1})\phi_{k}(p)$
$\displaystyle+\left[2\alpha^{2}_{k}+(1-\alpha_{k})\left(1-\frac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}\right)\right]\Delta_{k}-\beta_{k+1}\Delta_{k+1}.$

Defining

$\theta_{k}\triangleq\frac{\rho_{k}}{8}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})-\left[2\alpha^{2}_{k}+(1-\alpha_{k})\left(1-\frac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}\right)\right]\Delta_{k},$

we arrive at

$Q_{k+1}(p)\leq Q_{k}(p)-\theta_{k}+\frac{1}{2}\Delta M_{k}+\frac{1}{2}\Delta
N_{k}(p,p^{\ast})+(\alpha_{k}-\alpha_{k+1})\phi_{k}(p)-\beta_{k}\Delta_{k+1}.$
(4.20)

Our aim is to use $Q_{k}(p)$ as a suitable energy function for RISFBF. For
that to work, we need to identify a specific parameter sequence pair
$(\rho_{k},\alpha_{k})$ so that $\beta_{k}\geq 0$ and $\theta_{k}\geq 0$,
taking the following design criteria into account:

  1. 1.

$\alpha_{k}\in(0,\bar{\alpha}]\subset(0,1)$ for all $k\geq 1$;

  2. 2.

$\alpha_{k}$ is non-decreasing with

$\sup_{k\geq 1}\alpha_{k}=\bar{\alpha},\text{ and}\inf_{k\geq 1}\alpha_{k}>0.$
(4.21)

Incorporating these two restrictions on the inertia parameter $\alpha_{k}$, we
are left with the following constraints:

$\beta_{k}\geq 0\text{ and
}2\alpha_{k}^{2}+(1-\alpha_{k})\left(1-\frac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}\right)\leq
0.$ (4.22)

To identify a constellation of parameters $(\alpha_{k},\rho_{k})$ satisfying
these two conditions, define

$h_{k}(x,y)\triangleq(1-x)\left(\frac{5}{4y(1+L\lambda_{k})}-1\right).$ (4.23)

Then,

$\displaystyle 0$ $\displaystyle\geq
2\alpha_{k}^{2}-(1-\alpha_{k})\left(h_{k}(\alpha_{k},\rho_{k})+(1-\alpha_{k})-1\right)$
$\displaystyle=2\alpha^{2}_{k}+\alpha_{k}(1-\alpha_{k})-(1-\alpha_{k})h_{k}(\alpha_{k},\rho_{k})$
$\displaystyle=\alpha_{k}(1+\alpha_{k})-(1-\alpha_{k})h_{k}(\alpha_{k},\rho_{k}),$

which gives

$h_{k}(\alpha_{k},\rho_{k})\geq\frac{\alpha_{k}(1+\alpha_{k})}{1-\alpha_{k}}.$
(4.24)

Solving this condition for $\rho_{k}$ reveals that
$\frac{1}{\rho_{k}}\geq\frac{4(2\alpha^{2}_{k}-\alpha_{k}+1)(1+L\lambda_{k})}{5(1-\alpha_{k})^{2}}.$
Using the design condition $\alpha_{k}\leq\bar{\alpha}<1$, we need to choose
the relaxation parameter $\rho_{k}$ so that
$\rho_{k}\leq\frac{5(1-\alpha_{k})^{2}}{4(1+L\lambda_{k})(2\alpha^{2}_{k}-\alpha_{k}+1)}$.
This suggests to use the relaxation sequence
$\rho_{k}=\rho_{k}(\alpha_{k},\lambda_{k})\triangleq\frac{5(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}{4(1+L\lambda_{k})(2\alpha^{2}_{k}-\alpha_{k}+1)}$.
It remains to verify that with this choice we can guarantee $\beta_{k}\geq 0.$
This can be deduced as follows: Recalling (4.23), we get

$h_{k}(\alpha_{k},\rho_{k})=(1-\alpha_{k})\left(\tfrac{5}{4\rho_{k}(1+L\lambda)}-1\right)=\tfrac{(1-\alpha_{k})(2\alpha_{k}^{2}-\alpha_{k}+1)}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}+\alpha_{k}-1.$

In particular, we note that if
$f(\alpha)\triangleq{\tfrac{(1-\alpha)(2\alpha^{2}-\alpha+1)}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}}+\alpha-1$,
then

$\displaystyle f^{\prime}(\alpha)$
$\displaystyle=\tfrac{(1-\alpha)(4\alpha-1)-(2\alpha^{2}-\alpha+1)}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}+1=\tfrac{-6\alpha^{2}+6\alpha-2+(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}=\tfrac{-6(\alpha-\frac{1}{2})^{2}-\frac{1}{2}+(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}$

We consider two cases:
Case 1: $\bar{\alpha}\leq 1/2$. In this case

$\displaystyle
f^{\prime}(\alpha)\leq\tfrac{-6(\bar{\alpha}-\frac{1}{2})^{2}-\frac{1}{2}+(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}\leq\frac{-5\bar{\alpha}^{2}+4\bar{\alpha}-1}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}<0.$

Case 2: $1/2<\bar{\alpha}<1$. In this case

$f^{\prime}(\alpha)\leq\frac{-6(1/2-1/2)^{2}-1/2+(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}\leq\frac{-1/2+(1-\bar{\varepsilon})(1-1/2)^{2}}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}<0.$

Thus, $f(\alpha)$ is decreasing in $\alpha\in(0,\bar{\alpha}]$, where
$0<\bar{\alpha}<1$.

Using these relations, we see that (4.20) reduces to

$Q_{k+1}(p)\leq Q_{k}(p)-\theta_{k}+\frac{1}{2}\Delta M_{k}+\frac{1}{2}\Delta
N_{k}(p,p^{\ast}),$ (4.25)

where $\theta_{k}\geq 0$. This is the basis for our proof of Theorem 4.1.

###### Proof of Theorem 4.1.

We start with (i). Consider (4.25), with the special choice $p^{\ast}=0$, so
that $p\in\mathsf{S}$. Taking conditional expectations on both sides of this
inequality, we arrive at

$\mathbb{E}[Q_{k+1}(p)|\mathcal{F}_{k}]\leq Q_{k}(p)-\theta_{k}+\psi_{k},$

where $\psi_{k}\triangleq\frac{\mathtt{a}_{k}\sigma^{2}}{2m_{k}}$. By design
of the relaxation sequence $\rho_{k}$, we see that

$\displaystyle\mathtt{a}_{k}$
$\displaystyle=\lambda^{2}_{k}\left(\frac{10\rho_{k}}{1+L\lambda_{k}}+\frac{\rho_{k}}{2}\right)=\lambda^{2}_{k}\left(\frac{10}{1+L\lambda_{k}}+\frac{1}{2}\right)\frac{5(1-\bar{\varepsilon})}{4(2\alpha^{2}_{k}-\alpha_{k}+1)(1+L\lambda_{k})}.$

Since $\lim_{k\to\infty}\lambda_{k}=\lambda\in(0,1/4L)$, and
$\lim_{k\to\infty}\alpha_{k}=\bar{\alpha}\in(0,1)$, we conclude that the
sequence $(\mathtt{a}_{k})_{k\in\mathbb{N}}$ is bounded. Consequently, thanks
to Assumption 5, the sequence $(\psi_{k})_{k\in\mathbb{N}}$ is in
$\ell^{1}_{+}(\mathbb{N})$. We next claim that $Q_{k}(p)\geq 0$. To verify
this, note that

$\displaystyle Q_{k}(p)$ $\displaystyle=\frac{1}{2}\lVert
X_{k}-p\rVert^{2}-\frac{\alpha_{k}}{2}\lVert
X_{k-1}-p\rVert^{2}+\frac{(1-\alpha_{k})}{2}\left(\frac{5}{4\rho_{k}(1+L\lambda_{k})}-1\right)\lVert
X_{k}-X_{k-1}\rVert^{2}$ $\displaystyle=\frac{1}{2}\lVert
X_{k}-p\rVert^{2}+\left(\frac{(1-\alpha_{k})(2\alpha_{k}^{2}+1-\alpha_{k})}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}-1+\alpha_{k}\right)\frac{1}{2}\lVert
X_{k}-X_{k-1}\rVert^{2}-\frac{\alpha_{k}}{2}\lVert X_{k-1}-p\rVert^{2}$
$\displaystyle\geq\frac{1}{2}\lVert
X_{k}-p\rVert^{2}+\left(\frac{(1-\alpha_{k})(\alpha_{k}^{2}+1-\alpha_{k})}{(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}-1+\alpha_{k}\right)\frac{1}{2}\lVert
X_{k}-X_{k-1}\rVert^{2}-\frac{\alpha_{k}}{2}\lVert X_{k-1}-p\rVert^{2}$
$\displaystyle\geq\frac{1}{2}\lVert
X_{k}-p\rVert^{2}+\left(\frac{(1-\alpha_{k})(\alpha_{k}^{2}+1-\alpha_{k})}{(1-\alpha_{k})^{2}}-1+\alpha_{k}\right)\frac{1}{2}\lVert
X_{k}-X_{k-1}\rVert^{2}-\frac{\alpha_{k}}{2}\lVert X_{k-1}-p\rVert^{2}$
$\displaystyle=(\alpha_{k}+(1-\alpha_{k}))\lVert
X_{k}-p\rVert^{2}+\left(\alpha_{k}+\frac{\alpha^{2}_{k}}{1-\alpha_{k}}\right)\lVert
X_{k}-X_{k-1}\rVert^{2}-\alpha_{k}\lVert X_{k-1}-p\rVert^{2}$
$\displaystyle\geq\frac{\alpha_{k}}{2}\left(\lVert X_{k}-p\rVert^{2}+\lVert
X_{k}-X_{k-1}\rVert^{2}\right)-\frac{\alpha_{k}}{2}\lVert
X_{k-1}-p\rVert^{2}+\alpha_{k}\lVert X_{k}-p\rVert\cdot\lVert
X_{k}-X_{k-1}\rVert$ $\displaystyle\geq\frac{\alpha_{k}}{2}\left(\lVert
X_{k}-p\rVert+\lVert X_{k}-X_{k-1}\rVert\right)^{2}-\frac{\alpha_{k}}{2}\lVert
X_{k-1}-p\rVert^{2}\geq 0.$

where the first and second inequality uses $\bar{\varepsilon}<1$ and
$\alpha_{k}\leq\bar{\alpha}\in(0,1)$, the third inequality makes use of the
Young inequality: $\frac{1-a}{2a}\lVert
X_{k}-p\rVert^{2}+\frac{a}{2(1-a)}\lVert X_{k}-X_{k-1}\rVert^{2}\geq\lVert
X_{k}-p\rVert\cdot\lVert X_{k}-X_{k-1}\rVert$. Finally, the fourth inequality
uses the triangle inequality $\lVert X_{k-1}-p\rVert\leq\lVert
X_{k}-X_{k-1}\rVert+\lVert X_{k}-p\rVert$. Lemma A.2 readily yields the
existence of an a.s. finite limiting random variable $Q_{\infty}(p)$ such that
$Q_{k}(p)\to Q_{\infty}(p)$, $\mathbb{P}$-a.s., and
$(\theta_{k})_{k\in\mathbb{N}}\in\ell^{1}_{+}({\mathbb{F}})$. Since
$\lambda_{k}\to\lambda$, we get
$\lim_{k\to\infty}\rho_{k}=\frac{5(1-\bar{\varepsilon})(1-\bar{\alpha})^{2}}{4(1+L\lambda)(2\bar{\alpha}^{2}+1-\bar{\alpha})}$.
Hence,

$\displaystyle\lim_{k\to\infty}\left(2\alpha_{k}^{2}-(1-\alpha_{k})\left(1-\tfrac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}\right)\right)\lVert
X_{k}(\omega)-X_{k-1}(\omega)\rVert^{2}=0,\text{ and }$
$\displaystyle\lim_{k\to\infty}\frac{\rho_{k}}{4}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k}(\omega))=0.$

$\mathbb{P}$-a.s. We conclude that
$\lim_{k\to\infty}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})=0$, $\mathbb{P}$-a.s..

To prove (ii) observe that, since $\bar{\varepsilon}\in(0,1)$ and
$\lim_{k\to\infty}\alpha_{k}=\bar{\alpha}$, it follows

$\left[2\alpha_{k}^{2}+(1-\alpha_{k})\left(1-\frac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}\right)\right]\leq\frac{-\bar{\varepsilon}}{1-\bar{\varepsilon}}(2\bar{\alpha}^{2}+1-\bar{\alpha})<0.$

Consequently, $\lim_{k\to\infty}\lVert X_{k}-X_{k-1}\rVert^{2}=0$,
$\mathbb{P}$-a.s., and
$\left(\phi_{k}(p)-\alpha_{k}\phi_{k-1}(p)\right)_{k\in\mathbb{N}}$ is almost
surely bounded. Hence, for each $\omega\in\Omega$, there exists a bounded
random variable $C_{1}(\omega)\in[0,\infty)$ such that

$\phi_{k}(p,\omega)\leq C_{1}(\omega)+\alpha_{k}\phi_{k-1}(p,\omega)\leq
C_{1}(\omega)+\bar{\alpha}\phi_{k-1}(p,\omega)\qquad\forall k\geq 1.$

Iterating this relation, using the fact that $\bar{\alpha}\in[0,1)$, we easily
derive

$\phi_{k}(p,\omega)\leq\frac{C_{1}(\omega)}{1-\bar{\alpha}}+\bar{\alpha}^{k}\phi_{1}(p,\omega).$

Hence, $(\phi_{k}(p))_{k\in\mathbb{N}}$ is a.s. bounded, which implies that
$(X_{k})_{k\in\mathbb{N}}$ is bounded $\mathbb{P}$-a.s. We next claim that
$(\lVert X_{k}-p\rVert)_{k\in\mathbb{N}}$ converges to a $[0,\infty)$-valued
random variable $\mathbb{P}$-a.s. Indeed, take $\omega\in\Omega$ such that
$\phi_{k}(p,\omega)\equiv\phi_{k}(\omega)$ is bounded. Suppose there exists
$\mathtt{t}_{1}(\omega)\in[0,\infty),\mathtt{t}_{2}(\omega)\in[0,\infty)$, and
subsequences $(\phi_{k_{j}}(\omega))_{j\in\mathbb{N}}$ and
$(\phi_{l_{j}}(\omega))_{j\in\mathbb{N}}$ such that
$\phi_{k_{j}}(\omega)\to\mathtt{t}_{1}(\omega)$ and
$\phi_{l_{j}}(\omega)\to\mathtt{t}_{2}(\omega)>\mathtt{t}_{1}(\omega)$. Then,
$\lim_{j\to\infty}Q_{k_{j}}(p)(\omega)=Q_{\infty}(p)(\omega)=(1-\bar{\alpha})\mathtt{t}_{1}(\omega)<(1-\bar{\alpha})\mathtt{t}_{2}(\omega)=\lim_{j\to\infty}Q_{l_{j}}(\omega)=Q_{\infty}(p)(\omega)$,
a contradiction. It follows that
$\mathtt{t}_{1}(\omega)=\mathtt{t}_{2}(\omega)$ and, in turn,
$\phi_{k}(\omega)\to\mathtt{t}(\omega)$. Thus, for each $p\in\mathsf{S}$,
$\phi_{k}(p)\to\mathtt{t}$ $\mathbb{P}$-a.s.
Since we assume that $\mathsf{H}$ is separable, [22, Prop 2.3(iii)] guarantees
that there exists a set $\Omega_{0}\in\mathcal{F}$ with
$\mathbb{P}(\Omega_{0})=1$, and, for every $\omega\in\Omega_{0}$ and every
$p\in\mathsf{S}$, the sequence $(\lVert
X_{k}(\omega)-p\rVert)_{k\in\mathbb{N}}$ converges.

We next show that all weak limit points of $(X_{k})_{k\in\mathbb{N}}$ are
contained in $\mathsf{S}$. Let $\omega\in\Omega$ such that
$(X_{k}(\omega))_{k\in\mathbb{N}}$ is bounded. Thanks to [9, Lemma 2.45], we
can find a weakly convergent subsequence
$(X_{k_{j}}(\omega))_{j\in\mathbb{N}}$ with limit $\chi(\omega)$, i.e. for all
$u\in\mathsf{H}$ we have $\lim_{j\to\infty}\langle
X_{k_{j}}(\omega),u\rangle=\langle\chi(\omega),u\rangle$. This implies

$\lim_{j\to\infty}\langle Z_{k_{j}}(\omega),u\rangle=\lim_{j\to\infty}\langle
X_{k_{j}}(\omega),u\rangle+\lim_{j\to\infty}\alpha_{k_{j}}\langle
X_{k_{j}}(\omega)-X_{k_{j-1}}(\omega),u\rangle=\langle\chi(\omega),u\rangle,$

showing that $Z_{k_{j}}(\omega)\rightharpoonup\chi(\omega)$. Along this weakly
converging subsequence, define

$r_{k_{j}}(\omega)\triangleq
Z_{k_{j}}(\omega)-J_{\lambda_{k_{j}}T}(Z_{k_{j}}(\omega)-\lambda_{k_{j}}V(Z_{k_{j}}(\omega))).$

Clearly, $\mathsf{res}_{\lambda_{k_{j}}}(Z_{k_{j}}(\omega))=\lVert
r_{k_{j}}(\omega)\rVert$, so that $\lim_{j\to\infty}r_{k_{j}}(\omega)=0$. By
definition

$\frac{1}{\lambda_{k_{j}}}r_{k_{j}}(\omega)-V(Z_{k_{j}}(\omega))+V\left(Z_{k_{j}}(\omega)-r_{k_{j}}(\omega)\right)\in
F(Z_{k_{j}}(\omega)-r_{k_{j}}(\omega)).$

Since $V$ and $F=T+V$ are maximally monotone, their graphs are sequentially
closed in the weak-strong topology
$\mathsf{H}^{\text{weak}}\times\mathsf{H}^{\text{strong}}$ [9, Prop.
20.33(ii)]. Therefore, by the strong convergence of the sequence
$(r_{k_{j}}(\omega))_{j\in\mathbb{N}}$, we deduce weak convergence of the
sequence
$(Z_{k_{j}}(\omega)-r_{k_{j}}(\omega),Z_{k_{j}}(\omega))_{j\in\mathbb{N}}\rightharpoonup(\chi(\omega),\chi(\omega))$.
Therefore
$\frac{1}{\lambda}r_{k_{j}}(\omega)-V(Z_{k_{j}}(\omega))+V\left(Z_{k_{j}}(\omega)-r_{k_{j}}(\omega)\right)\to
0$. Hence, $0\in(T+V)(\chi(\omega))$, showing that
$\chi(\omega)\in\mathsf{S}$. Invoking [22, Prop 2.3(iv)], we conclude that
$(X_{k})_{k\in\mathbb{N}}$ converges weakly $\mathbb{P}$-a.s to an
$\mathsf{S}$-valued random variable.

We now establish (iii). Let $q_{k}\triangleq\mathbb{E}[Q_{k}(p)]$, so that
(4.25) yields the recursion

$q_{k}\leq q_{k-1}-\mathbb{E}[\theta_{k}]+\psi_{k}.$

By Assumption 5, and the definition of all sequences involved, we see that
$\sum_{k=1}^{\infty}\psi_{k}<\infty$. Hence, a telescopian argument gives

$q_{k}-q_{0}=\sum_{i=1}^{k}(q_{i}-q_{i-1})\leq-\sum_{i=1}^{k}\mathbb{E}[\theta_{i}]+\sum_{i=1}^{k}\psi_{i}\leq-\sum_{i=1}^{k}\mathbb{E}[\theta_{i}]+\sum_{i=1}^{\infty}\psi_{i}.$

Hence, for all $k\geq 1$, rearranging the above reveals

$\sum_{i=1}^{k}\mathbb{E}[\theta_{i}]\leq
q_{0}+\sum_{i=1}^{\infty}\psi_{i}<\infty.$

Letting $k\to\infty$, we conclude
$\left(\mathbb{E}[\theta_{k}]\right)_{k\in\mathbb{N}}\in\ell^{1}_{+}(\mathbb{N})$.
Classically, this implies $\theta_{k}\to 0$ $\mathbb{P}$-a.s. By a simple
majorization argument, we deduce that $\mathbb{P}$-a.s.

$\displaystyle\infty$
$\displaystyle>\sum_{k=1}^{\infty}\left\\{\frac{\rho_{k}}{8}\mathsf{res}^{2}_{\lambda_{k}}(Z_{k})-\left[2\alpha^{2}_{k}+(1-\alpha_{k})\left(1-\frac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}\right)\right]\Delta_{k}\right\\}$
$\displaystyle\geq\sum_{k=1}^{\infty}\left[(1-\alpha_{k})\left(\frac{5(1-\alpha_{k})}{4\rho_{k}(1+L\lambda_{k})}-1\right)-2\alpha^{2}_{k}\right]\Delta_{k}.$

$\blacksquare$ $\blacksquare$

######  Remark 4.1.

The above result gives some indication of the balance between the inertial
effect and the relaxation effect. Our analysis revealed that the maximal value
of the relaxation parameter is
$\rho\leq\frac{5(1-\bar{\varepsilon})(1-\alpha)^{2}}{4(1+L\lambda)(2\alpha^{2}-\alpha+1)}$.
This is closely aligned with the maximal relaxation value exhibited in Remark
2.13 of [2]. Specifically, the function
$\rho_{m}(\alpha,\varepsilon)=\frac{5(1-\varepsilon)(1-\alpha)^{2}}{4(1+L\lambda)(2\alpha^{2}-\alpha+1)}$.
This function is decreasing in $\alpha$. For this choice of parameters, one
observes that for $\alpha\to 0$ we get
$\rho\to\frac{5(1-\varepsilon)}{4(1+L\lambda)}$ and for $\alpha\to 1$ it is
observed $\rho\to 0$.

As an immediate corollary of Theorem 4.1, we obtain a convergence result when
all parameter sequences are constant.

######  Corollary 4.4 (Asymptotic convergence under constant inertia and
relaxation).

Let the same Assumptions as in Theorem 4.1 hold. Consider Algorithm RISFBF
with the constant parameter sequences
$\alpha_{k}\equiv\alpha\in(0,1),\lambda_{k}\equiv\lambda\in(0,\tfrac{1}{4L})$
and
$\rho_{k}=\rho<\frac{5(1-\alpha)^{2}}{4(1+L\lambda)(2\alpha^{2}+1-\alpha)}$.
Then $(X_{k})_{k\in\mathbb{N}}$ converges weakly $\mathbb{P}$-a.s. to a
limiting random variable with values in $\mathsf{S}$.

In fact, the a.s. convergence with a larger $\lambda_{k}$ is allowed as shown
in the following corollary.

######  Corollary 4.5 (Asymptotic convergence under larger steplength).

Let the same Assumptions as in Theorem 4.1 hold. Consider Algorithm RISFBF
with the constant parameter sequences
$\alpha_{k}\equiv\alpha\in(0,1),\lambda_{k}\equiv\lambda\in(0,\tfrac{1-\nu}{2L})$
and
$\rho_{k}=\rho<\frac{(3-\nu)(1-\alpha)^{2}}{2(1+L\lambda)(2\alpha^{2}+1-\alpha)}$,
where $0<\nu<1$. Then $(X_{k})_{k\in\mathbb{N}}$ converges weakly
$\mathbb{P}$-a.s. to a limiting random variable with values in $\mathsf{S}$.

###### Proof.

First we make a slight modification to (4.10) that the following relation
holds for $0<\nu<1$

$\displaystyle\quad(1-\rho_{k})\lVert Z_{k}-p\rVert^{2}+\rho_{k}\lVert
R_{k}-p\rVert^{2}-\frac{1-\rho_{k}}{\rho_{k}}\lVert X_{k+1}-Z_{k}\rVert^{2}$
$\displaystyle\leq\lVert Z_{k}-p\rVert^{2}-\frac{1-\rho_{k}}{\rho_{k}}\lVert
X_{k+1}-Z_{k}\rVert^{2}-\rho_{k}((1-\nu)-2L^{2}\lambda^{2}_{k})\lVert
Z_{k}-Y_{k}\rVert^{2}$
$\displaystyle+2\lambda^{2}\rho_{k}\lVert\mathtt{e}_{k}\rVert^{2}-2\rho_{k}\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle-\rho_{k}\nu\lVert
Y_{k}-Z_{k}\rVert^{2}+2\rho_{k}\lambda_{k}\langle
V(Y_{k})-V(p),p-Y_{k}\rangle.$

Then similarly with (4.12), we multiply both sides of (4.11) by
$\frac{\rho_{k}((1-\nu)-2L\lambda_{k})}{1+L\lambda_{k}}$, which is positive
since $\lambda_{k}\in(0,\tfrac{1-\nu}{2L})$. The convergence follows in a
similar fashion to Theorem 4.1. $\blacksquare$

Another corollary of Theorem 4.1 is a strong convergence result, assuming that
$F$ is demiregular (cf. Definition 2.1).

######  Corollary 4.6 (Strong Convergence under demiregularity).

Let the same Assumptions as in Theorem 4.1 hold. If $F=T+V$ is demiregular,
then $(X_{k})_{k\in\mathbb{N}}$ converges strongly $\mathbb{P}$-a.s. to a
$\mathsf{S}$-valued random variable.

###### Proof.

Set $y_{k_{j}}(\omega)\triangleq Z_{k_{j}}(\omega)-r_{k_{j}}(\omega)$, and
$u_{k_{j}}(\omega)\triangleq\frac{1}{\lambda}r_{k_{j}}(\omega)-V(Z_{k_{j}}(\omega))+V(Z_{k_{j}}(\omega)-r_{k_{j}}(\omega))$.
We know from the proof of Theorem 4.1 that
$y_{k_{j}}(\omega)\rightharpoonup\chi(\omega)$ and $u_{k_{j}}(\omega)\to 0$.
If $F=T+V$ is demiregular then $y_{k_{j}}(\omega)\to\chi(\omega)$. Since we
know $r_{k_{j}}(\omega)\to 0$, we conclude $Z_{k_{j}}(\omega)\to\chi(\omega)$.
Since $Z_{k}$ and $X_{k}$ have the same limit points, it follows
$X_{k}\to\chi$. $\blacksquare$ $\blacksquare$

###  4.2 Linear Convergence

In this section, we derive a linear convergence rate and prove strong
convergence of the last iterate in the case where the single-valued operator
$V$ is _strongly monotone_. Various linear convergence results in the context
of stochastic approximation algorithms for solving fixed-point problems are
reported in [23] in the context of the random sweeping processes. In a general
structured monotone inclusion setting [73] derive rate statements for
cocoercive mean operators in the context of forward-backward splitting
methods. More recently, Cui and Shanbhag [24] provide linear and sublinear
rates of convergence for a variance-reduced inexact proximal-point scheme for
both strongly monotone and monotone inclusion problems. However, to the best
of our knowledge, our results are the first published for a stochastic
operator splitting algorithm, featuring _relaxation and inertial_ effects.
Notably, this result does not require imposing Assumption 4(i) (i.e. the noise
process be conditionally unbiased.) Instead our derivations hold true under a
weaker notion of an asymptotically unbiased SO.

######  Assumption 6 (Asymptotically unbiased SO).

There exists a constant $\mathtt{s}>0$ such that

$\displaystyle\mathbb{E}[\lVert
U_{k}\rVert^{2}|\mathcal{F}_{k}]\leq\frac{\mathtt{s}^{2}}{m_{k}}\text{ and
}\mathbb{E}[\lVert
W_{k}\rVert^{2}|\mathcal{F}_{k}]\leq\frac{\mathtt{s}^{2}}{m_{k}},\qquad\mathbb{P}-\text{a.s.}$
(4.26)

for all $k\geq 1$.

This definition is rather mild and is imposed in many simulation-based
optimization schemes in finite dimensions. Amongst the more important ones is
the simultaneous perturbation stochastic approximation (SPSA) method pioneered
by Spall [78, 79]. In this scheme, it is required that the gradient estimator
satisfies an asymptotic unbiasedness requirement; in particular, the bias in
the gradient estimator needs to diminish at a suitable rate to ensure
asymptotic convergence. In fact, this setting has been investigated in detail
in the context of stochastic Nash games [28]. Further examples for stochastic
approximation schemes in a Hilbert-space setting obeying Assumption 6 are [7,
8] and [38]. We now discuss an example that further clarifies the requirements
on the estimator.

######  Example 4.1.

Let $\\{\hat{V}_{k}(x,\xi)\\}_{k\in\mathbb{N}}$ be a collection of independent
random $\mathsf{H}$-valued vector fields of the form
$\hat{V}_{k}(x,\xi)=V(x)+\varepsilon_{k}(x,\xi)$ such that

$\displaystyle\mathbb{E}_{\xi}[\varepsilon_{k}(x,\xi)|x]={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{B_{k}}{\sqrt{m_{k}}}}\text{
and
}\mathbb{E}_{\xi}[\lVert\varepsilon_{k}(x,\xi)\rVert^{2}|x]\leq\hat{\sigma}^{2}\qquad\mathbb{P}-\text{a.s.},$

where $\hat{\sigma}>0$ and $\tilde{b}>0$ such that $(B_{k})_{k\in\mathbb{N}}$
is an $\mathsf{H}$-valued sequence satisfying $\|B_{k}\|^{2}\leq\hat{b}^{2}$
in an a.s. sense. These statistics can be obtained as

$\displaystyle\mathbb{E}[\lVert U_{k}\rVert^{2}|\mathcal{F}_{k}]$
$\displaystyle=\mathbb{E}\left[\left\|\frac{1}{m_{k}}\sum_{t=1}^{m_{k}}\varepsilon_{t}(Z_{k})\right\|^{2}|\mathcal{F}_{k}\right]$
$\displaystyle=\frac{1}{m_{k}^{2}}\sum_{t=1}^{m_{k}}\mathbb{E}[\lVert\varepsilon_{t}(Z_{k})\rVert^{2}|\mathcal{F}_{k}]+\frac{2}{m_{k}^{2}}\sum_{t=1}^{m_{k}}\sum_{l>t}\mathbb{E}[\langle\varepsilon_{t}(Z_{k}),\varepsilon_{l}(Z_{k})\rangle|\mathcal{F}_{k}]$
$\displaystyle\leq\frac{\hat{\sigma}^{2}}{m_{k}}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{(m_{k}-1)}{m_{k}}\frac{\lVert
B_{k}\rVert^{2}}{m_{k}}}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{\hat{\sigma}^{2}+\hat{b}^{2}}{m_{k}}}\qquad{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
Setting
$\mathtt{s}^{2}\triangleq\hat{\sigma}^{2}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\hat{b}^{2}}$,
we see that condition (4.26) holds. A similar estimate holds for the random
noise $\lVert W_{k}\rVert^{2}$.

######  Assumption 7.

$V:\mathsf{H}\to\mathsf{H}$ is $\mu$-strongly monotone ($\mu>0$), i.e.

$\langle V(x)-V(y),x-y\rangle\geq\mu\lVert x-y\rVert^{2}\qquad\forall
x,y\in\operatorname{dom}V=\mathsf{H}.$ (4.27)

Combined with Assumption 1, strong monotonicity implies that
$\mathsf{S}=\\{\bar{x}\\}$ for some $\bar{x}\in\mathsf{H}$.

######  Remark 4.2.

In the context of a structured operator $F=T+V$, the assumption that the
single-valued part $V$ is strongly monotone can be done without loss of
generality. Indeed, if instead $T$ is assumed to be $\mu$-strongly monotone,
then $(V+\mu\operatorname{Id})+(T-\mu\operatorname{Id})$ is maximally monotone
and Lipschitz continuous while $\tilde{V}\triangleq V+\mu\operatorname{Id}$
may be seen to be $\mu$-strongly monotone operator.

Our first result establishes a “perturbed linear convergence” rate on the
anchor sequence $\left(\lVert
X_{k}-\bar{x}\rVert^{2}\right)_{k\in\mathbb{N}}$, similar to the one derived
in [23, Corollary 3.2] in the context of randomized fixed point iterations.

######  Theorem 4.7 (Perturbed linear convergence).

Consider RISFBF with $X_{0}=X_{1}$. Suppose Assumptions 1-3, Assumption 6 and
Assumption 7 hold. Let $\mathsf{S}=\\{\bar{x}\\}$ denotes the unique solution
of (MI). Suppose
$\lambda_{k}\equiv\lambda\leq\min\left\\{\tfrac{a}{2\mu},b\mu,\tfrac{1-a}{2\tilde{L}}\right\\}$,
where $0<a,b<1$, $\tilde{L}^{2}\triangleq L^{2}+\tfrac{1}{2}$,
$\eta_{k}\equiv\eta\triangleq(1-b)\lambda\mu$. Define $\Delta M_{k}\triangleq
2\rho_{k}\lVert
W_{k}\rVert^{2}+\frac{(3-a)\rho_{k}\lambda_{k}^{2}}{1+\tilde{L}\lambda_{k}}\lVert\mathtt{e}_{k}\rVert^{2}$.
Let $(\alpha_{k})_{k\in\mathbb{N}}$ be a non-decreasing sequence such that
$0<\alpha_{k}\leq\bar{\alpha}<1$, and define
$\rho_{k}\triangleq\tfrac{(3-a)(1-\alpha_{k})^{2}}{2(2\alpha_{k}^{2}-0.5\alpha_{k}+1)(1+\tilde{L}\lambda)}$
for every $k\in\mathbb{N}$. Set

$\displaystyle H_{k}\triangleq\lVert
X_{k}-\bar{x}\rVert^{2}+(1-\alpha_{k})\left(\tfrac{3-a}{2\rho_{k}(1+\tilde{L}\lambda)}-1\right)\lVert
X_{k}-X_{k-1}\rVert^{2}-\alpha_{k}\lVert X_{k-1}-\bar{x}\rVert^{2},$ (4.28)
$\displaystyle c_{k}\triangleq\mathbb{E}[\Delta M_{k}|\mathcal{F}_{k}],\text{
and
}\bar{c}_{k}\triangleq\sum_{i=1}^{k}q^{k-i}\mathbb{E}[c_{i}|\mathcal{F}_{1}],$

where $q=1-\rho\eta\in(0,1)$,
$\rho=\frac{16(3-a)(1-\bar{\alpha})^{2}}{31(1+\tilde{L}\lambda)}$. Then the
following hold:

  * (i)

$(\bar{c}_{k})_{k\in\mathbb{N}}\in\ell^{1}_{+}(\mathbb{N})$.

  * (ii)

For all $k\geq 1$

$\mathbb{E}[H_{k+1}|\mathcal{F}_{1}]\leq q^{k}H_{1}+\bar{c}_{k}.$ (4.29)

In particular, this implies a perturbed linear rate of the sequence
$(\|X_{k}-\bar{x}\|^{2})_{k\in\mathbb{N}}$ as

$\mathbb{E}[\lVert X_{k+1}-\bar{x}\rVert^{2}|\mathcal{F}_{0}]\leq
q^{k}\left(\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}\lVert
X_{1}-\bar{x}\rVert^{2}\right)+\tfrac{2}{1-\bar{\alpha}}\bar{c}_{k}.$ (4.30)

  * (iii)

$\sum_{k=1}^{\infty}(1-\alpha_{k})\left(\tfrac{3-a}{2\rho_{k}(1+\tilde{L}\lambda)}-1\right)\lVert
X_{k}-X_{k-1}\rVert^{2}<\infty$ $\mathbb{P}\text{-a.s.}$.

###### Proof.

Our point of departure for the analysis under the stronger Assumption 7 is eq.
(4.6), which becomes

$\displaystyle\langle Z_{k}-R_{k},Y_{k}-p\rangle\geq\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle+\lambda_{k}\mu\lVert
Y_{k}-p\rVert^{2}\quad\forall(p,p^{\ast})\in\operatorname{gr}(F).$

Repeating the analysis of the previous section with reference point
$p=\bar{x}$ and $p^{\ast}=0$, the unique solution of (MI), yields the bound

$\displaystyle\lVert R_{k}-\bar{x}\rVert^{2}$ $\displaystyle\leq\lVert
Z_{k}-\bar{x}\rVert^{2}-(1-2L^{2}\lambda_{k}^{2})\lVert
Y_{k}-Z_{k}\rVert^{2}+2\lambda^{2}_{k}\lVert\mathtt{e}_{k}\rVert^{2}$
$\displaystyle+2\lambda_{k}\langle
W_{k},\bar{x}-Y_{k}\rangle-2\lambda_{k}\mu\lVert\bar{x}-Y_{k}\rVert^{2}.$

The triangle inequality $\lVert Z_{k}-\bar{x}\rVert^{2}\leq 2\lVert
Y_{k}-Z_{k}\rVert^{2}+2\lVert Y_{k}-\bar{x}\rVert^{2}$ gives

$\displaystyle\lVert R_{k}-\bar{x}\rVert^{2}$ $\displaystyle\leq\lVert
Z_{k}-\bar{x}\rVert^{2}-(1-2L^{2}\lambda_{k}^{2})\lVert
Y_{k}-Z_{k}\rVert^{2}+2\lambda^{2}_{k}\lVert\mathtt{e}_{k}\rVert^{2}+2\lambda_{k}\langle
W_{k},\bar{x}-Y_{k}\rangle$ $\displaystyle+2\lambda_{k}\mu\lVert
Y_{k}-Z_{k}\rVert^{2}-\lambda_{k}\mu\lVert Z_{k}-\bar{x}\rVert^{2}.$

By Young’s inequality, we have for all $c>0$,

$\displaystyle\langle W_{k},\bar{x}-Y_{k}\rangle$
$\displaystyle\leq\frac{1}{2c}\lVert W_{k}\rVert^{2}+\frac{c}{2}\lVert
Y_{k}-\bar{x}\rVert^{2}$ $\displaystyle\leq\frac{1}{2c}\lVert
W_{k}\rVert^{2}+c\left(\lVert Z_{k}-\bar{x}\rVert^{2}+\lVert
Z_{k}-Y_{k}\rVert^{2}\right).$ (4.31)

Observe that this estimate is crucial in weakening the requirement of
conditional unbiasedness. Choose $c=\frac{\lambda_{k}}{2}$ to get

$\displaystyle\lVert R_{k}-\bar{x}\rVert^{2}$ $\displaystyle\leq\lVert
Z_{k}-\bar{x}\rVert^{2}-(1-2L^{2}\lambda_{k}^{2})\lVert
Y_{k}-Z_{k}\rVert^{2}+2\lambda^{2}_{k}\lVert\mathtt{e}_{k}\rVert^{2}+2\lVert
W_{k}\rVert^{2}+\lambda^{2}_{k}\lVert\bar{x}-Z_{k}\rVert^{2}$
$\displaystyle+2\lambda_{k}\mu\lVert
Y_{k}-Z_{k}\rVert^{2}-\lambda_{k}\mu\lVert
Z_{k}-\bar{x}\rVert^{2}+\lambda_{k}^{2}\lVert Z_{k}-Y_{k}\rVert^{2}$
$\displaystyle=(1+\lambda_{k}^{2}-\lambda_{k}\mu)\lVert
Z_{k}-\bar{x}\rVert^{2}+2\lambda^{2}_{k}\lVert\mathtt{e}_{k}\rVert^{2}+2\lVert
W_{k}\rVert^{2}$
$\displaystyle-(1-2L^{2}\lambda^{2}_{k}-2\lambda_{k}\mu-\lambda^{2}_{k})\lVert
Y_{k}-Z_{k}\rVert^{2}.$

Assume that $\lambda_{k}\mu\leq\frac{a}{2}<1$. Then,

$1-2L^{2}\lambda^{2}_{k}-2\lambda_{k}\mu-\lambda_{k}^{2}\geq(1-a)-2L^{2}\lambda_{k}^{2}-\lambda_{k}^{2}=(1-a)-2\tilde{L}^{2}\lambda^{2}_{k},$

where $\tilde{L}^{2}\triangleq L^{2}+1/2$. Moreover, choosing $\lambda_{k}\leq
b\mu$, we see

$1+\lambda^{2}_{k}-\lambda_{k}\mu\leq 1-(1-b)\lambda_{k}\mu.$

Using these bounds, we readily deduce for
$0<\lambda_{k}\leq\min\\{\frac{a}{2\mu},b\mu\\}$, that

$\displaystyle\lVert R_{k}-\bar{x}\rVert^{2}$
$\displaystyle\leq\left(1-(1-b)\lambda_{k}\mu\right)\lVert
Z_{k}-\bar{x}\rVert^{2}-\left((1-a)-2\tilde{L}^{2}\lambda^{2}_{k}\right)\lVert
Y_{k}-Z_{k}\rVert^{2}$
$\displaystyle+2\lambda^{2}_{k}\lVert\mathtt{e}_{k}\rVert^{2}+2\lVert
W_{k}\rVert^{2}.$ (4.32)

Proceeding as in the derivation of eq. (4.1), one sees first that

$\frac{1}{2\rho_{k}^{2}}\lVert
X_{k+1}-Z_{k}\rVert^{2}\leq(1+\tilde{L}\lambda_{k})^{2}\lVert
Y_{k}-Z_{k}\rVert^{2}+\lambda^{2}_{k}\lVert\mathtt{e}_{k}\rVert^{2},$

and therefore,

$\displaystyle-\rho_{k}((1-a)-2\tilde{L}^{2}\lambda^{2}_{k})\lVert
Y_{k}-Z_{k}\rVert^{2}$
$\displaystyle\leq-\frac{(1-a)-2\tilde{L}\lambda_{k}}{2\rho_{k}(1+\tilde{L}\lambda_{k})}\lVert
X_{k+1}-Z_{k}\rVert^{2}$
$\displaystyle+\frac{\rho_{k}\lambda^{2}_{k}((1-a)-2\tilde{L}\lambda_{k})}{1+\tilde{L}\lambda_{k}}\lVert\mathtt{e}_{k}\rVert^{2}.$
(4.33)

Define $\eta_{k}=(1-b)\lambda_{k}\mu$. Using the equality (4.8),

$\displaystyle\lVert X_{k+1}$
$\displaystyle-\bar{x}\rVert^{2}=(1-\rho_{k})\lVert
Z_{k}-\bar{x}\rVert^{2}+\rho_{k}\lVert
R_{k}-\bar{x}\rVert^{2}-\tfrac{1-\rho_{k}}{\rho_{k}}\lVert
X_{k+1}-Z_{k}\rVert^{2}$
$\displaystyle\overset{\eqref{eq:Rnew}}{\leq}(1-\rho_{k}\eta_{k})\lVert
Z_{k}-\bar{x}\rVert^{2}-\tfrac{1-\rho_{k}}{\rho_{k}}\lVert
X_{k+1}-Z_{k}\rVert^{2}-\rho_{k}((1-a)-2\tilde{L}^{2}\lambda^{2}_{k})\lVert
Z_{k}-Y_{k}\rVert^{2}$
$\displaystyle+2\lambda^{2}_{k}\rho_{k}\lVert\mathtt{e}_{k}\rVert^{2}+2\rho_{k}\lVert
W_{k}\rVert^{2}$ $\displaystyle\overset{\eqref{bd-
eq3}}{\leq}(1-\rho_{k}\eta_{k})\lVert
Z_{k}-\bar{x}\rVert^{2}-\tfrac{(3-a)-2\rho_{k}(1+\tilde{L}\lambda_{k})}{2\rho_{k}(1+\tilde{L}\lambda_{k})}\lVert
X_{k+1}-Z_{k}\rVert^{2}+2\rho_{k}\lVert
W_{k}\rVert^{2}+\tfrac{(3-a)\rho_{k}\lambda_{k}^{2}}{1+\tilde{L}\lambda_{k}}\lVert\mathtt{e}_{k}\rVert^{2}$
$\displaystyle\overset{\eqref{eq:Z1},\eqref{eq:Xk1}}{\leq}(1-\rho_{k}\eta_{k})[(1+\alpha_{k})\lVert
X_{k}-\bar{x}\rVert^{2}-\alpha_{k}\lVert
X_{k-1}-\bar{x}\rVert^{2}+\alpha_{k}(1+\alpha_{k})\lVert
X_{k}-X_{k-1}\rVert^{2}]$
$\displaystyle-\tfrac{(3-a)-2\rho_{k}(1+\tilde{L}\lambda_{k})}{2\rho_{k}(1+\tilde{L}\lambda_{k})}[(1-\alpha_{k})\lVert
X_{k+1}-X_{k}\rVert^{2}+(\alpha^{2}_{k}-\alpha_{k})\lVert
X_{k}-X_{k-1}\rVert^{2}]$ $\displaystyle+2\rho_{k}\lVert
W_{k}\rVert^{2}+\tfrac{(3-a)\rho_{k}\lambda_{k}^{2}}{(1+\tilde{L}\lambda_{k})}\lVert\mathtt{e}_{k}\rVert^{2}$
$\displaystyle\leq(1+\alpha_{k})(1-\rho_{k}\eta_{k})\|X_{k}-\bar{x}\|^{2}-\alpha_{k}(1-\rho_{k}\eta_{k})\|X_{k-1}-\bar{x}\|^{2}+\Delta
M_{k}$ $\displaystyle+\alpha_{k}\lVert
X_{k}-X_{k-1}\rVert^{2}\left[(1+\alpha_{k})(1-\rho_{k}\eta_{k})+(\alpha_{k}-1)+\tfrac{(3-a)(1-\alpha_{k})}{2\rho_{k}(1+\tilde{L}\lambda_{k})}\right]$
$\displaystyle-(1-\alpha_{k})\left(\tfrac{3-a}{2\rho_{k}(1+\tilde{L}\lambda_{k})}-1\right)\lVert
X_{k+1}-X_{k}\rVert^{2},$

with stochastic error term $\Delta M_{k}\triangleq 2\rho_{k}\lVert
W_{k}\rVert^{2}+\frac{(3-a)\rho_{k}\lambda_{k}^{2}}{1+\tilde{L}\lambda_{k}}\lVert\mathtt{e}_{k}\rVert^{2}$.
From here, it follows that

$\displaystyle\lVert
X_{k+1}-\bar{x}\rVert^{2}+(1-\alpha_{k})\left(\tfrac{3-a}{2\rho_{k}(1+\tilde{L}\lambda_{k})}-1\right)\lVert
X_{k+1}-X_{k}\rVert^{2}-\alpha_{k}\|X_{k}-\bar{x}\|^{2}$
$\displaystyle\leq(1-\rho_{k}\eta_{k})\left[\lVert
X_{k}-\bar{x}\rVert^{2}+(1-\alpha_{k})\left(\tfrac{3-a}{2\rho_{k}(1+\tilde{L}\lambda_{k})}-1\right)\lVert
X_{k}-X_{k-1}\rVert^{2}-\alpha_{k}\|X_{k-1}-\bar{x}\|^{2}\right]$
$\displaystyle-\left[(1-\rho_{k}\eta_{k})(1-\alpha_{k})\left(\tfrac{3-a}{2\rho_{k}(1+\tilde{L}\lambda_{k})}-1\right)\right.$
$\displaystyle\left.-\alpha_{k}\left((1+\alpha_{k})(1-\rho_{k}\eta_{k})+(\alpha_{k}-1)+\tfrac{(3-a)(1-\alpha_{k})}{2\rho_{k}(1+\tilde{L}\lambda_{k})}\right)\right]\lVert
X_{k}-X_{k-1}\rVert^{2}$ $\displaystyle-\alpha_{k}\rho_{k}\eta_{k}\lVert
X_{k}-\bar{x}\rVert^{2}+\Delta M_{k}$
$\displaystyle=(1-\rho_{k}\eta_{k})\left[\lVert
X_{k}-\bar{x}\rVert^{2}+(1-\alpha_{k})\left(\tfrac{3-a}{2\rho_{k}(1+\tilde{L}\lambda_{k})}-1\right)\lVert
X_{k}-X_{k-1}\rVert^{2}-\alpha_{k}\|X_{k-1}-\bar{x}\|^{2}\right]$
$\displaystyle-\underbrace{\left[(1-\alpha_{k}-\rho_{k}\eta_{k})\left(\tfrac{(3-a)(1-\alpha_{k})}{2\rho_{k}(1+\tilde{L}\lambda_{k})}-1\right)-\alpha_{k}^{2}(2-\rho_{k}\eta_{k})\right]}_{\triangleq\tilde{I}}\lVert
X_{k}-X_{k-1}\rVert^{2}-\alpha_{k}\rho_{k}\eta_{k}\lVert
X_{k}-\bar{x}\rVert^{2}+\Delta M_{k}.$ (4.34)

Since $\lambda_{k}=\lambda$, and
$\rho_{k}=\tfrac{(3-a)(1-\alpha_{k})^{2}}{2(2\alpha_{k}^{2}-0.5\alpha_{k}+1)(1+\tilde{L}\lambda)}$,
we claim that $\rho_{k}\leq\tfrac{1-\alpha_{k}}{(1+4\alpha_{k})\eta}$ for
$\eta\equiv(1-b)\lambda\mu$. Indeed,333To wit, the function $x\mapsto
2x^{2}-0.5x+1$ is attains a global minumum at $x=1/8$, which gives the global
lower bound $31/32$. Furthermore, the function $x\mapsto(1-x)(1+4x)$ attains a
global maximum at $x=3/8$, with corresponding value $25/16$.

$\displaystyle\tfrac{\tfrac{1-\alpha_{k}}{(1+4\alpha_{k})\eta}}{\rho_{k}}=\tfrac{2(2\alpha_{k}^{2}-0.5\alpha_{k}+1)(1+\tilde{L}\lambda)}{(3-a)(1-\alpha_{k})(1+4\alpha_{k})\eta}\geq\tfrac{2(2\alpha_{k}^{2}-0.5\alpha_{k}+1)(1+\tilde{L}\lambda)}{(3-a)(1-\alpha_{k})(1+4\alpha_{k})\tfrac{a}{2}(1-b)}\geq\tfrac{2\cdot\tfrac{31}{32}\cdot
1}{\tfrac{25}{16}\cdot 1}=\frac{31}{25}>1.$

In particular, this implies $\eta\rho_{k}\in(0,1)$ for all $k\in\mathbb{N}$.
We then have

$\displaystyle\tilde{I}$
$\displaystyle=(1-\alpha_{k}-\rho_{k}\eta)\left(\tfrac{(3-a)(1-\alpha_{k})}{2\rho_{k}(1+\tilde{L}\lambda)}-1\right)-\alpha_{k}^{2}(2-\rho_{k}\eta)\geq\left(1-\alpha_{k}-\tfrac{1-\alpha_{k}}{1+4\alpha_{k}}\right)\left(\tfrac{2\alpha_{k}^{2}-0.5\alpha_{k}+1}{1-\alpha_{k}}-1\right)-2\alpha_{k}^{2}$
$\displaystyle=\tfrac{(1-\alpha_{k})4\alpha_{k}}{1+4\alpha_{k}}\cdot\tfrac{2\alpha_{k}^{2}+0.5\alpha_{k}}{1-\alpha_{k}}-\tfrac{2\alpha_{k}^{2}(1+4\alpha_{k})}{1+4\alpha_{k}}$
$\displaystyle=0.$ (4.35)

Next, we show that $H_{k}\geq\tfrac{1-\bar{\alpha}}{2}\|X_{k}-\bar{x}\|^{2}$,
for $H_{k}$ defined in (4.28). This can be seen from the next string of
inequalities:

$\displaystyle H_{k}$ $\displaystyle=\lVert
X_{k}-\bar{x}\rVert^{2}-\alpha_{k}\lVert
X_{k-1}-\bar{x}\rVert^{2}+(1-\alpha_{k})\left(\frac{3-a}{2\rho_{k}(1+\tilde{L}\lambda)}-1\right)\|X_{k}-X_{k-1}\|^{2}$
$\displaystyle\geq\lVert
X_{k}-\bar{x}\rVert^{2}+\left(\frac{(1-\alpha_{k})(2\alpha_{k}^{2}+1-0.5\alpha_{k})}{(1-\alpha_{k})^{2}}-1+\alpha_{k}\right)\lVert
X_{k}-X_{k-1}\rVert^{2}-\alpha_{k}\lVert X_{k-1}-\bar{x}\rVert^{2}$
$\displaystyle\geq\lVert
X_{k}-\bar{x}\rVert^{2}+\left(\frac{(1-\alpha_{k})(2\alpha_{k}^{2}+1-\alpha_{k})}{(1-\alpha_{k})^{2}}-1+\alpha_{k}\right)\lVert
X_{k}-X_{k-1}\rVert^{2}-\alpha_{k}\lVert X_{k-1}-\bar{x}\rVert^{2}$
$\displaystyle=\left(\alpha_{k}+\frac{1-\alpha_{k}}{2}\right)\lVert
X_{k}-\bar{x}\rVert^{2}+\left(\alpha_{k}+\frac{2\alpha_{k}^{2}}{1-\alpha_{k}}\right)\lVert
X_{k}-X_{k-1}\rVert^{2}-\alpha_{k}\lVert
X_{k-1}-\bar{x}\rVert^{2}+\frac{1-\alpha_{k}}{2}\lVert
X_{k}-\bar{x}\rVert^{2}$ $\displaystyle\geq\alpha_{k}\left(\lVert
X_{k}-\bar{x}\rVert^{2}+\lVert X_{k}-X_{k-1}\rVert^{2}\right)-\alpha_{k}\lVert
X_{k-1}-\bar{x}\rVert^{2}+2\alpha_{k}\lVert X_{k}-\bar{x}\rVert\cdot\lVert
X_{k}-X_{k-1}\rVert+\frac{1-\alpha_{k}}{2}\lVert X_{k}-\bar{x}\rVert^{2}$
$\displaystyle\geq\alpha_{k}\left(\lVert X_{k}-\bar{x}\rVert+\lVert
X_{k}-X_{k-1}\rVert\right)^{2}-\alpha_{k}\lVert
X_{k-1}-\bar{x}\rVert^{2}+\frac{1-\alpha_{k}}{2}\lVert
X_{k}-\bar{x}\rVert^{2}\geq\frac{1-\alpha_{k}}{2}\lVert
X_{k}-\bar{x}\rVert^{2}$ $\displaystyle\geq\frac{1-\bar{\alpha}}{2}\lVert
X_{k}-\bar{x}\rVert^{2}.$

In this derivation we have used the Young
inequality$\frac{1-\alpha_{k}}{2}\lVert
X_{k}-\bar{x}\rVert^{2}+\frac{2\alpha_{k}^{2}}{1-\alpha_{k}}\lVert
X_{k}-X_{k-1}\rVert^{2}\geq 2\alpha_{k}\lVert X_{k}-\bar{x}\rVert\cdot\lVert
X_{k}-X_{k-1}\rVert,$ and the specific choice
$\rho_{k}=\frac{(3-a)(1-\alpha_{k})^{2}}{2(2\alpha_{k}^{2}-\frac{1}{2}\alpha_{k}+1)(1+\tilde{L}\lambda)}$.

By recalling (4.34) and invoking (4.35), we are left with the stochastic
recursion

$H_{k+1}\leq q_{k}H_{k}-\tilde{b}_{k}+\Delta M_{k}.$ (4.36)

where $q_{k}\triangleq 1-\rho_{k}\eta$ and
$\tilde{b}_{k}\triangleq\alpha_{k}\rho_{k}\eta_{k}\|X_{k}-\bar{x}\|^{2}.$
Since
$\rho_{k}=\frac{(3-a)(1-\alpha_{k})^{2}}{2(2\alpha_{k}^{2}-\frac{1}{2}\alpha_{k}+1)(1+\tilde{L}\lambda)}\geq\rho=\frac{16(3-a)(1-\bar{\alpha})^{2}}{31(1+\tilde{L}\lambda)}$
for every $k$, we have that $q_{k}\leq q=1-\eta\rho$ for every $k$.
Furthermore, $1>\eta\rho_{k}\geq\eta\rho$, so that $q\in(0,1)$. Taking
conditional expectations on both sides on (4.36), we get

$\displaystyle\mathbb{E}[H_{k+1}|\mathcal{F}_{k}]+\tilde{b}_{k}\leq
qH_{k}+c_{k}\quad\mathbb{P}\text{-a.s.}$

using the notation $c_{k}\triangleq\mathbb{E}[\Delta M_{k}|\mathcal{F}_{k}]$.
Applying the operator $\mathbb{E}[\cdot|\mathcal{F}_{k-1}]$ and using the
tower property of conditional expectations, this gives

$\mathbb{E}[H_{k+1}|\mathcal{F}_{k-1}]\leq
q^{2}H_{k-1}-q\mathbb{E}[\tilde{b}_{k-1}|\mathcal{F}_{k-1}]-\mathbb{E}[\tilde{b}_{k}|\mathcal{F}_{k-1}]+q\mathbb{E}[c_{k-1}|\mathcal{F}_{k-1}]+\mathbb{E}[c_{k}|\mathcal{F}_{k-1}].$

Proceeding inductively, we see that

$\mathbb{E}[H_{k+1}|\mathcal{F}_{1}]\leq
q^{k}H_{1}+\sum_{i=1}^{k-1}q^{k-i}\mathbb{E}[c_{i}|\mathcal{F}_{1}]=q^{k}H_{1}+\bar{c}_{k}.$

This establishes eq. (4.29). To validate eq. (4.30), recall that we assume
$X_{1}=X_{0}$, so that $H_{1}=(1-\alpha_{1})\lVert X_{1}-\bar{x}\rVert^{2}$.
Furthermore, $H_{k+1}\geq\frac{1-\bar{\alpha}}{2}\lVert
X_{k+1}-\bar{x}\rVert^{2}$, so that

$\mathbb{E}[\lVert X_{k+1}-\bar{x}\rVert^{2}|\mathcal{F}_{1}]\leq
q^{k}\left(\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}\lVert
X_{1}-\bar{x}\rVert^{2}\right)+\frac{2}{1-\bar{\alpha}}\bar{c}_{k}.$

We now show that $(\bar{c}_{k})_{k\in\mathbb{N}}\in\ell^{1}_{+}(\mathbb{N})$.
Simple algebra, combined with Assumption 6, gives

$\displaystyle c_{k}$ $\displaystyle=\mathbb{E}[\Delta
M_{k}|\mathcal{F}_{k}]\leq
2\rho_{k}\left(1+\frac{(3-a)\lambda^{2}}{1+\tilde{L}\lambda}\right)\mathbb{E}[\lVert
W_{k}\rVert^{2}|\mathcal{F}_{k}]+\frac{2(3-a)\rho_{k}\lambda^{2}}{1+\tilde{L}\lambda}\mathbb{E}[\lVert
U_{k}\rVert^{2}|\mathcal{F}_{1}]$
$\displaystyle\leq\frac{2\mathtt{s}^{2}\rho_{k}}{m_{k}}\left(1+\frac{2(3-a)\lambda^{2}}{1+\tilde{L}\lambda}\right)\equiv\frac{\rho_{k}\mathtt{s}^{2}}{m_{k}}\kappa.$
(4.37)

Hence, since $(\rho_{k})_{k\in\mathbb{N}}$ is bounded, Assumption 5 gives
$\lim_{k\to\infty}c_{k}=0$ a.s. Using again the tower property, we see
$\mathbb{E}[c_{k}|\mathcal{F}_{1}]=\mathbb{E}\left[\mathbb{E}(c_{k}|\mathcal{F}_{k})|\mathcal{F}_{1}\right]\leq\kappa\frac{\rho_{k}\mathtt{s}^{2}}{m_{k}}\leq\kappa\frac{\bar{\rho}\mathtt{s}^{2}}{m_{k}}$,
where
$\rho_{k}=\frac{(3-a)(1-\alpha_{k})^{2}}{2(2\alpha_{k}^{2}-\frac{1}{2}\alpha_{k}+1)(1+\tilde{L}\lambda)}\leq\bar{\rho}=\frac{3-a}{2(1+\tilde{L}\lambda)}$
for every $k$. Consequently, the discrete convolution
$\left(\sum_{i=1}^{k-1}q^{k-i}\mathbb{E}[c_{i}|\mathcal{F}_{1}]\right)_{k\in\mathbb{N}}$
is summable. Therefore $\sum_{k\geq 1}\mathbb{E}[H_{k}]<\infty$ and
$\sum_{k\geq 1}\mathbb{E}[\tilde{b}_{k}]<\infty$. Clearly, this implies
$\lim_{k\to\infty}\mathbb{E}[\tilde{b}_{k}]=0,$ and consequently the
subsequently stated two implication follow as well:

$\displaystyle\lim_{k\to\infty}\lVert
X_{k}-\bar{x}\rVert=0\quad\mathbb{P}\text{-a.s.},\quad\text{ and }$
$\displaystyle\sum_{k=1}^{\infty}(1-\alpha_{k})\left(\tfrac{3-a}{2\rho_{k}(1+\tilde{L}\lambda)}-1\right)\lVert
X_{k}-X_{k-1}\rVert^{2}<\infty\quad\mathbb{P}\text{-a.s.}.$

$\blacksquare$ $\blacksquare$

######  Remark 4.3.

It is worth remarking that the above proof does not rely on unbiasedness of
the random estimators. The reason why we can lift this rather typical
assumption lies in our application Young’s inequality in the estimate (4.31).
The only assumption needed is a summable oracle variance as formulated in
Assumption 6 to get the above result working.

######  Remark 4.4.

The above result illustrates again nicely the well-known trade-off between
relaxation and inertial effects (cf. Remark 4.1). Indeed, up to constant
factors, the coupling between inertia and relaxation is expressed by the
function
$\alpha\mapsto\frac{(1-\alpha)^{2}}{2\alpha^{2}-\frac{1}{2}\alpha+1}$. Basic
calculus reveals that this function is decreasing for $\alpha$ increasing. In
the extreme case when $\alpha\uparrow 1$, it is necessary to let
$\rho\downarrow 0$, and vice versa. When $\alpha\to 0$ then the limiting value
of our specific relaxation policy is $\frac{3-a}{1+\tilde{L}\lambda}$. In
practical applications, it is advisable to choose $b$ small in order to make
$q$ large. The value $a$ must be calibrated in a disciplined way in order to
allow for a sufficiently large step size $\lambda$. This requires some
knowledge of the condition number of the problem $\mu/L$. As a heuristic
argument, a good strategy, anticipating that $b$ should be close to $0$, is to
set $\frac{a}{2\mu}=\frac{1-a}{2\tilde{L}}$. This means
$a=\frac{\mu}{\tilde{L}+\mu}$.

We obtain a full linear rate of convergence when a more aggressive sample rate
is employed in the SO. We achieve such global linear rates, together with
tuneable iteration and oracle complexity estimates in two settings: First, we
consider an aggressive simulation strategy, where the sample size grows over
time geometrically. Such a sampling frequency can be quite demanding in some
applications. As an alternative, we then move on and consider a more modest
simulation strategy under which only polynomial growth of the batch size is
required. Whatever simulation strategy is adopted, key to the assessment of
the iteration and oracle complexity is to bound the stopping time

$K_{\epsilon}\triangleq\inf\\{k\in\mathbb{N}|\;\mathbb{E}\left(\lVert
X_{k+1}-\bar{x}\rVert^{2}\right)\leq\epsilon\\}.$ (4.38)

In order to understand the definition of this stopping time, recall that
RISFBF computes the last iterate $X_{K+1}$ by extrapolating between the
current base point $Z_{k}$ and the correction step involving
$Y_{k}+\lambda_{K}(A_{k}-B_{k})$, which requires $2m_{k}$ iid realizations
from the law ${\mathsf{P}}$. In total, when executing the algorithm until the
terminal time $K_{\epsilon}$, where therefore need to simulate
$2\sum_{k=1}^{K_{\epsilon}}m_{k}$ random variables. We now estimate the
integer $K_{\epsilon}$ under a geometric sampling strategy.

######  Proposition 4.8 (Non-asymptotic linear convergence under geometric
sampling).

Suppose the conditions of Theorem 4.7 hold. Let
$p\in(0,1),\mathtt{B}=2\bar{\rho}\mathtt{s}^{2}\left(1+\frac{2(3-a)\lambda^{2}}{1+\tilde{L}\lambda}\right),$
and choose the sampling rate $m_{k}=\lfloor p^{-k}\rfloor$. Let
$\hat{p}\in(p,1)$, and define

$\displaystyle C(p,q)$
$\displaystyle\triangleq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\tfrac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}+\tfrac{4\mathtt{B}}{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(1-\bar{\alpha})}(1-\min\\{p/q,q/p\\})}\quad\text{if
}p\neq q,\text{ and }$ (4.39) $\displaystyle\hat{C}$
$\displaystyle\triangleq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\tfrac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}+\tfrac{4\mathtt{B}}{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(1-\bar{\alpha})}\exp(1)\ln(\hat{p}/q)}\quad\text{if
}p=q.$ (4.40)

Then, whenever $p\neq q$, we see that

$\mathbb{E}\left(\lVert X_{k+1}-\bar{x}\rVert^{2}\right)\leq
C(p,q)\max\\{p,q\\}^{k},$

and whenever $p=q$,

$\mathbb{E}\left(\lVert
X_{k+1}-\bar{x}\rVert^{2}\right)\leq\hat{C}\hat{p}^{k}.$

In particular, the stochastic process $(X_{k})_{k\in\mathbb{N}}$ converges
strongly and $\mathbb{P}$-a.s. to the unique solution $\bar{x}$ at a linear
rate.

###### Proof.

Departing from (4.36), ignoring the positive term $\tilde{b}_{k}$ from the
right-hand side, and taking expectations on both sides leads to

$\displaystyle\frac{1-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bar{\alpha}}}{2}\mathbb{E}(\lVert
X_{k+1}-\bar{x}\rVert^{2})\leq h_{k+1}\triangleq\mathbb{E}(H_{k+1})\leq
q\mathbb{E}(H_{k})+c_{k}=qh_{k}+c_{k},$ (4.41)

where the equality follows from $c_{k}$ being deterministic. The sequence
$(c_{k})_{k\in\mathbb{N}}$ is further upper bounded by the following
considerations: First, the relaxation sequence is bounded by
$\rho_{k}\leq\bar{\rho}=\frac{3-a}{2(1+\tilde{L}\lambda)}$; Second, the sample
rate is bounded by $m_{k}=\lfloor
p^{-k}\rfloor\geq\left\lceil\tfrac{1}{2}p^{-k}\right\rceil\geq\tfrac{1}{2}p^{-k}$.
Using these facts, eq. (4.37) yields

$c_{k}\leq\frac{\rho_{k}\mathtt{s}^{2}\kappa}{m_{k}}\leq
2\mathtt{B}p^{k}\qquad\forall k\geq 1,$ (4.42)

where
$\mathtt{B}=2\bar{\rho}\mathtt{s}^{2}\left(1+\frac{2(3-a)\lambda^{2}}{1+\tilde{L}\lambda}\right)$.
Iterating the recursion above, one readily sees that

$h_{k+1}\leq q^{k}h_{1}+\sum_{i=1}^{k}q^{k-i}c_{i}\quad\forall k\geq 1.$
(4.43)

Consequently, by recalling that $h_{1}=(1-\alpha_{1})\|X_{1}-\bar{x}\|^{2}$
and $h_{k}\geq\frac{1-\bar{\alpha}}{2}\mathbb{E}(\lVert
X_{k}-\bar{x}\rVert^{2})$, the bound (4.42) allows us to derive the recursion

$\mathbb{E}\left(\lVert X_{k+1}-\bar{x}\rVert^{2}\right)\leq
q^{k}\left(\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}\lVert
X_{1}-\bar{x}\rVert^{2}\right)+\frac{4\mathtt{B}}{1-\bar{\alpha}}\sum_{i=1}^{k}q^{k-i}p^{i}.$
(4.44)

We consider three cases.

(i) $0<q<p<1$: Defining
$\mathtt{c}_{1}\triangleq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}+\tfrac{4\mathtt{B}}{(1-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bar{\alpha}})(1-q/p)}$,
we obtain from (4.44)

$\mathbb{E}(\lVert X_{k+1}-\bar{x}\rVert^{2})\leq
q^{k}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}\right)+\frac{4\mathtt{B}}{1-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bar{\alpha}}}\sum_{i=1}^{k}(q/p)^{k-i}p^{k}\leq\mathtt{c}_{1}p^{k}.$

(ii) $0<p<q<1$. Akin to (i) and defining
$\mathtt{c}_{2}\triangleq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}+\tfrac{4\mathtt{B}}{(1-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bar{\alpha}})(1-p/q)}$,
we arrive as above at the bound $\mathbb{E}(\lVert
X_{k}-\bar{x}\rVert^{2})\leq q^{k}\mathtt{c}_{2}$.
(iii) $p=q<1$. Choose $\hat{p}\in(q,1)$ and
$\mathtt{c}_{3}\triangleq\tfrac{1}{\exp(1)\ln(\hat{p}/q)}$, so that Lemma A.3
yields $kq^{k}\leq\mathtt{c}_{3}\hat{p}^{k}$ for all $k\geq 1$. Therefore,
plugging this estimate in eq. (4.44), we see

$\displaystyle\mathbb{E}(\lVert X_{k}-\bar{x}\rVert^{2})$ $\displaystyle\leq
q^{k}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}\right)+\frac{4\mathtt{B}}{1-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bar{\alpha}}}\sum_{i=1}^{k}q^{k}$
$\displaystyle\leq\hat{p}^{k}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}\right)+\frac{4\mathtt{B}}{1-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bar{\alpha}}}\mathtt{c}_{3}\hat{p}^{k}$
$\displaystyle=\mathtt{c}_{4}\hat{p}^{k},$

after setting
$\mathtt{c}_{4}\triangleq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}+\frac{4\mathtt{B}\mathtt{c}_{3}}{1-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bar{\alpha}}}$.
Collecting these three cases together, verifies the first part of the
proposition. $\blacksquare$ $\blacksquare$

######  Proposition 4.9 (Oracle and Iteration Complexity under geometric
sampling).

Given $\epsilon>0$, define the stopping time $K_{\epsilon}$ as in eq. (4.38).
Define

$\tau_{\epsilon}(p,q)\triangleq\left\\{\begin{array}[]{ll}\lceil\frac{\ln(C(p,q)\epsilon^{-1})}{\ln(1/\max\\{p,q\\})}\rceil&\text{if
}p\neq q,\\\
\lceil\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\ln(\hat{C}\epsilon^{-1})}}{\ln(1/\hat{p})}\rceil&\text{if
}p=q\end{array}\right.$ (4.45)

and the same hypothesis as in Theorem 4.7 apply. Then,
$K_{\varepsilon}\leq\tau_{\epsilon}(p,q)=\mathcal{O}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\ln(\varepsilon^{-1})})$.
The corresponding oracle complexity of RISFBF is upper bounded as
$2\sum_{i=1}^{\tau_{\epsilon}(p,q)}m_{i}=\mathcal{O}\left((1/\epsilon)^{1+\delta(p,q)}\right)$,
where

$\displaystyle\delta(p,q)\triangleq\left\\{\begin{array}[]{ll}0&\text{if
}p>q,\\\ \frac{\ln(p)}{\ln(q)}-1&\text{if }p\in(0,q),\\\
\frac{\ln(p)}{\ln(\hat{p})}-1&\text{if }p=q.\end{array}\right.$

###### Proof.

First, let us recall that the total oracle complexity of the method is
assessed by

$\displaystyle
2\sum_{i=1}^{K_{\epsilon}}m_{i}=2\sum_{i=1}^{K_{\epsilon}}\lfloor
p^{-i}\rfloor\leq 2\sum_{i=1}^{K_{\epsilon}}p^{-i}.$

If $p\neq q$ define
$\tau_{\epsilon}\equiv\tau_{\epsilon}(p,q)=\lceil\frac{\ln(C(p,q)\epsilon^{-1})}{\ln(1/\max\\{p,q\\})}\rceil$.
Then, $\mathbb{E}(\lVert
X_{\tau_{\epsilon}+1}-\bar{x}\rVert^{2})\leq\epsilon$, and hence
$K_{\epsilon}\leq\tau_{\epsilon}$. We now compute

$\displaystyle\sum_{i=1}^{\tau_{\epsilon}}(1/p)^{i}$
$\displaystyle=\frac{1}{p}\frac{(1/p)^{\lceil\frac{\ln(C(p,q)\epsilon^{-1})}{\ln(1/\max\\{p,q\\})}\rceil}-1}{1/p-1}\leq\frac{1}{p^{2}}\frac{(1/p)^{\frac{\ln(C(p,q)\epsilon^{-1})}{\ln(1/\max\\{p,q\\})}}}{1/p-1}$
$\displaystyle=\frac{\left(\epsilon^{-1}C(p,q)\right)^{\ln(1/p)/\ln(1/\max\\{p,q\\})}}{p(1-p)}.$

This gives the oracle complexity bound

$2\sum_{i=1}^{\tau_{\epsilon}}m_{i}\leq
2\frac{\left(\epsilon^{-1}C(p,q)\right)^{\ln(1/p)/\ln(1/\max\\{p,q\\})}}{p(1-p)}.$

If $p=q$, we can replicate this calculation, after setting
$\tau_{\epsilon}=\lceil\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\ln(\epsilon^{-1}\hat{C})}}{\ln(1/\hat{p})}\rceil$.
After so many iterations, we can be ensured that $\mathbb{E}(\lVert
X_{\tau_{\epsilon}+1}-\bar{x}\rVert^{2})\leq\epsilon$, with an oracle
complexity

$2\sum_{i=1}^{\tau_{\epsilon}}m_{i}\leq\frac{2}{\hat{p}(1-\hat{p})}\left(\frac{\hat{C}}{\epsilon}\right)^{\ln(p)/\ln(\hat{p})}.$

$\blacksquare$ $\blacksquare$

To the best of our knowledge, the provided non-asymptotic linear convergence
guarantee appears to be amongst the first in relaxed and inertial splitting
algorithms. In particular, by leveraging the increasing nature of mini-
batches, this result no longer requires the unbiasedness assumption on the SO,
a crucial benefit of the proposed scheme.

There may be settings where geometric growth of $m_{k}$ is challenging to
adopt. To this end, we provide a result where the sampling rate is polynomial
rather than geometric. A polynomial sampling rate arises if
$m_{k}=\lceil{a_{k}(k+k_{0})^{\theta}+b_{k}\rceil}$ for some parameters
$a_{k},b_{k},\theta>0$. Such a regime has been adopted in related mini-batch
approaches [54, 55]. This allows for modulating the growth rate by changing
the exponent in the sampling rate. We begin by providing a supporting result.
We make the specific choice $a_{k}=b_{k}=1$ for all $k\geq 1$, and $k_{0}=0$,
leaving essentially the exponent $\theta>0$ as a free parameter in the design
of the stochastic oracle.

######  Proposition 4.10 (Polynomial rate of convergence under polynomially
increasing $m_{k}$).

Suppose the conditions of Theorem 4.7 hold. Choose the sampling rate
$m_{k}=\lfloor k^{\theta}\rfloor$ where $\theta>0$. Then, for any $k\geq 1$,

$\mathbb{E}(\lVert X_{k+1}-\bar{x}\rVert^{2})\leq
q^{k}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2}{1-\bar{\alpha}}}\frac{q^{-1}\exp(2\theta)-1}{1-q}\right)+\frac{4\mathtt{B}}{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(1-\bar{\alpha})}q\ln(1/q)}(k+1)^{-\theta}$
(4.46)

###### Proof.

From the relation (4.43), we obtain

$\displaystyle h_{k+1}$ $\displaystyle\leq
q^{k}h_{1}+\sum_{i=1}^{k}q^{k-i}c_{i}\leq
q^{k}h_{1}+\mathtt{B}\sum_{i=1}^{k}q^{k-i}i^{-\theta}$
$\displaystyle=q^{k}\left(h_{1}+\mathtt{B}\sum_{i=1}^{k}q^{-i}i^{-\theta}\right)$
$\displaystyle=q^{k}\left(h_{1}+\mathtt{B}\sum_{i=1}^{\lceil
2\theta/\ln(1/q)\rceil}q^{-i}i^{-\theta}+\mathtt{B}\sum_{i=\lceil
2\theta/\ln(1/q)\rceil+1}^{k}q^{-i}i^{-\theta}\right).$

A standard bound based on the integral criterion for series with non-negative
summands gives

$\sum_{i=\lceil 2\theta/\ln(1/q)\rceil+1}^{k}q^{-i}i^{-\theta}\leq\int_{\lceil
2\theta/\ln(1/q)\rceil}^{k+1}\frac{(1/q)^{t}}{t^{\theta}}\>dt.$

The upper bounding integral can be evaluated using integration-by-parts, as
follows:

$\int_{\lceil
2\theta/\ln(1/q)\rceil}^{k+1}\frac{(1/q)^{t}}{t^{\theta}}\>dt=t^{\theta}\frac{e^{t\ln(1/q)}}{\ln(1/q)}\Big{|}_{t=\lceil
2\theta/\ln(1/q)\rceil}^{t=k+1}+\int_{\lceil
2\theta/\ln(1/q)\rceil}^{k+1}\theta
t^{-(\theta+1)}\frac{e^{t\ln(1/q)}}{\ln(1/q)}\>dt.$

Note that $\frac{\theta}{t\ln(1/q)}\leq\frac{1}{2}$ when $t\geq\lceil
2\theta/\ln(1/q)\rceil$. Therefore, we can attain a simpler bound from the
above by

$\displaystyle\int_{\lceil
2\theta/\ln(1/q)\rceil}^{k+1}\frac{(1/q)^{t}}{t^{\theta}}\>dt\leq\frac{(1/q)^{k+1}}{\ln(1/q)(k+1)^{\theta}}+\frac{1}{2}\int_{\lceil
2\theta/\ln(1/q)\rceil}^{k+1}\frac{(1/q)^{t}}{t^{\theta}}\>dt$

Consequently,

$\int_{\lceil
2\theta/\ln(1/q)\rceil}^{k+1}\frac{(1/q)^{t}}{t^{\theta}}\>dt\leq\frac{2(1/q)^{k+1}(k+1)^{-\theta}}{\ln(1/q)}.$

Furthermore,

$\sum_{i=1}^{\lceil
2\theta/\ln(1/q)\rceil}q^{-i}i^{-\theta}\leq\sum_{i=1}^{\lceil
2\theta/\ln(1/q)\rceil}q^{-i}=\frac{1}{q}\frac{(1/q)^{\lceil
2\theta/\ln(1/q)\rceil}-1}{1/q-1}\leq\frac{1}{q}\frac{(1/q)^{2\theta/\ln(1/q)+1}-1}{1/q-1}.$

Note that
$(1/q)^{2\theta/\ln(1/q)}=\left(\exp(\ln(1/q))\right)^{2\theta/\ln(1/q)}=\exp(2\theta)$.
Hence,

$\sum_{i=1}^{\lceil
2\theta/\ln(1/q)\rceil}q^{-i}i^{-\theta}\leq\frac{1}{q}\frac{q^{-1}\exp(2\theta)-1}{1/q-1}=\frac{q^{-1}\exp(2\theta)-1}{1-q}.$

Plugging this into the opening string of inequalities shows

$\displaystyle h_{k+1}$ $\displaystyle\leq
q^{k}\left(h_{1}+\mathtt{B}\sum_{i=1}^{\lceil
2\theta/\ln(1/q)\rceil}q^{-i}+\frac{2\mathtt{B}(1/q)^{k+1}(k+1)^{-\theta}}{\ln(1/q)}\right)$
$\displaystyle\leq
q^{k}\left(h_{1}+\mathtt{B}\frac{q^{-1}\exp(2\theta)-1}{1-q}+\frac{2\mathtt{B}(1/q)^{k+1}(k+1)^{-\theta}}{\ln(1/q)}\right)$
$\displaystyle=q^{k}\left(h_{1}+\mathtt{B}\frac{q^{-1}\exp(2\theta)-1}{1-q}\right)+\frac{2\mathtt{B}/q}{\ln(1/q)}(k+1)^{-\theta}.$

Since
$h_{1}=(1-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\alpha_{1}})\lVert
X_{1}-\bar{x}\rVert^{2}$ and
$h_{k+1}\geq\frac{1-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bar{\alpha}}}{2}\mathbb{E}\left(\lVert
X_{k+1}-\bar{x}\rVert^{2}\right)$, we finally arrive at the desired expression
(4.46). $\blacksquare$ $\blacksquare$

######  Proposition 4.11 (Oracle and Iteration complexity under polynomial
sampling).

Let all Assumptions as in Theorem 4.7 hold. Given $\epsilon>0$, define
$K_{\epsilon}$ as in (4.38). Then the iteration and oracle complexity to
obtain an $\epsilon$-solution are $\mathcal{O}(\theta\varepsilon^{-1/\theta})$
and $\mathcal{O}(\exp(\theta)\theta^{\theta}(1/\epsilon)^{1+1/\theta})$,
respectively.

###### Proof.

We first note that $(k+1)^{-\theta}\leq k^{-\theta}$ for all $k\geq 1$. Hence,
the bound established in Proposition 4.10 yields

$\mathbb{E}(\lVert X_{k+1}-\bar{x}\rVert^{2})\leq
q^{k}\left(\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}\lVert
X_{1}-\bar{x}\rVert^{2}+\frac{2}{1-\bar{\alpha}}\frac{q^{-1}\exp(2\theta)-1}{1-q}\right)+\frac{4\mathtt{B}}{(1-\bar{\alpha})q\ln(1/q)}k^{-\theta}$

Consider the function $\psi(t)\triangleq t^{\theta}q^{t}$ for $t>0$. Then,
straightforward calculus shows that $\psi(t)$ is unimodal on $(0,\infty)$,
with unique maximum $t^{\ast}=\frac{\theta}{\ln(1/q)}$ and associated value
$\psi(t^{\ast})=\exp(-\theta)\left(\frac{\theta}{\ln(1/q)}\right)^{\theta}$.
Hence, for all $t>0$, we have
$t^{\theta}q^{t}\leq\exp(-\theta)\left(\frac{\theta}{\ln(1/q)}\right)^{\theta}$,
and consequently,
$q^{k}\leq\exp(-\theta)\left(\frac{\theta}{\ln(1/q)}\right)^{\theta}k^{-\theta}$
for all $k\geq 1$. This allows us to conclude

$\displaystyle\mathbb{E}(\lVert X_{k+1}-\bar{x}\rVert^{2})$
$\displaystyle\leq\exp(-\theta)\left(\frac{\theta}{\ln(1/q)}\right)^{\theta}k^{-\theta}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2}{1-\bar{\alpha}}}\frac{q^{-1}\exp(2\theta)-1}{1-q}\right)$
$\displaystyle+\frac{4\mathtt{B}}{(1-\bar{\alpha})q\ln(1/q)}k^{-\theta}=\mathtt{c}_{q,\theta}k^{-\theta},$

where

$\mathtt{c}_{q,\theta}\triangleq\exp(-\theta)\left(\frac{\theta}{\ln(1/q)}\right)^{\theta}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2(1-\alpha_{1})}{1-\bar{\alpha}}}\lVert
X_{1}-\bar{x}\rVert^{2}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{2}{1-\bar{\alpha}}}\frac{q^{-1}\exp(2\theta)-1}{1-q}\right)+\frac{4\mathtt{B}}{(1-\bar{\alpha})q\ln(1/q)}$
(4.47)

Then, for any $k\geq
K_{\epsilon}\triangleq\lceil(\mathtt{c}_{q,\theta}/\epsilon)^{1/\theta}\rceil$,
we are ensured that $\mathbb{E}(\lVert
X_{k+1}-\bar{x}\rVert^{2})\leq\varepsilon$. Since
$(\mathtt{c}_{q,\theta})^{1/\theta}=\mathcal{O}(\exp(-1)\theta)$, we conclude
that $K_{\epsilon}=\mathcal{O}(\theta\epsilon^{-1/\theta})$. The corresponding
oracle complexity is bounded as follows:

$2\sum_{i=1}^{K_{\epsilon}}m_{i}\leq 2\sum_{i=1}^{K_{\epsilon}}i^{\theta}\leq
2\int_{1}^{K_{\epsilon}+1}t^{\theta}\>dt\leq\frac{2}{1+\theta}\left(\lceil\frac{\mathtt{c}_{q,\theta}}{\epsilon}\rceil^{1/\theta}+1\right)^{1+\theta}=\mathcal{O}(\exp(\theta)\theta^{\theta}(1/\epsilon)^{1+1/\theta}).$

$\blacksquare$ $\blacksquare$

######  Remark 4.5.

It may be observed that if the $\theta=1$ or $m_{k}=k$, there is a worsening
of the rate and complexity statements from their counterparts when the
sampling rate is geometric; in particular, the iteration complexity worsens
from $\mathcal{O}(\ln(\tfrac{1}{\epsilon}))$ to
$\mathcal{O}(\tfrac{1}{\epsilon})$ while the oracle complexity degenerates
from the optimal level of $\mathcal{O}(\tfrac{1}{\epsilon})$ to
$\mathcal{O}(\tfrac{1}{\epsilon^{2}})$. But this deterioration comes with the
advantage that the sampling rate is far slower and this may be of signficant
consequence in some applications.

###  4.3 Rates in terms of merit functions

In this subsection we estimate the iteration and oracle complexity of RISFBF
with the help of a suitably defined _gap function_. Generally, a gap function
associated with the monotone inclusion problem (MI) is a function
$\mathsf{Gap}:\mathsf{H}\to\mathbb{R}$ such that (i) $\mathsf{Gap}$ is sign
restricted on $\mathsf{H}$; and (ii) $\mathsf{Gap}(x)=0$ if and only if
$x\in\mathsf{S}$. The _Fitzpatrick function_ [30, 77, 11, 9] is a useful tool
to construct gap functions associated with a set-valued operator
$F:\mathsf{H}\to 2^{\mathsf{H}}$. It is defined as the extended-valued
function $G_{F}:\mathsf{H}\times\mathsf{H}\to[-\infty,\infty]$ given by

$G_{F}(x,x^{\ast})=\langle
x,x^{\ast}\rangle-\inf_{(y,y^{\ast})\in\operatorname{gr}(F)}\langle
x-y,x^{\ast}-y^{\ast}\rangle.$ (4.48)

This function allows us to recover the operator $F$, by means of the following
result (cf. [9, Prop. 20.58]): If $F:\mathsf{H}\to 2^{\mathsf{H}}$ is
maximally monotone, then $G_{F}(x,x^{\ast})\geq\langle x,x^{\ast}\rangle$ for
all $(x,x^{\ast})\in\mathsf{H}\times\mathsf{H}$, with equality if and only if
$(x,x^{\ast})\in\operatorname{gr}(F)$. In particular,
$\operatorname{gr}(F)=\\{(x,x^{\ast})\in\mathsf{H}\times\mathsf{H}|\;G_{F}(x,x^{\ast})\geq\langle
x,x^{\ast}\rangle\\}$. In fact, it can be shown that the Fitzpatrick function
is minimal in the family of convex functions
$f:\mathsf{H}\times\mathsf{H}\to(-\infty,\infty]$ such that
$f(x,x^{\ast})\geq\langle x,x^{\ast}\rangle$ for all
$(x,x^{\ast})\in\mathsf{H}\times\mathsf{H}$, with equality if
$(x,x^{\ast})\in\operatorname{gr}(F)$ [11].

Our gap function for the structured monotone operator $F=V+T$ is derived from
its Fitzpatrick function by setting $\mathsf{Gap}(x)\triangleq G_{F}(x,0)$ for
$x\in\mathsf{H}$. This reads explicitly as

$\mathsf{Gap}(x)\triangleq\sup_{(y,y^{\ast})\in\operatorname{gr}(F)}\langle
y^{\ast},x-y\rangle=\sup_{p\in\operatorname{dom}T}\sup_{p^{\ast}\in
T(p)}\langle V(p)+p^{\ast},x-p\rangle\qquad\forall x\in\mathsf{H}.$ (4.49)

It immediately follows from the definition that $\mathsf{Gap}(x)\geq 0$ for
all $x\in\mathsf{H}$. It is also clear, that $x\mapsto\mathsf{Gap}(x)$ is
convex and lower semi-continuous and $\mathsf{Gap}(x)=0$ if and only if
$x\in\mathsf{S}=\mathsf{Zer}(F)$. Let us give some concrete formulae for the
gap function.

######  Example 4.2 (Variational Inequalities).

We reconsider the problem described in Example 1.2. Let
$V:\mathsf{H}\to\mathsf{H}$ be a maximally monotone and $L$-Lipschitz
continuous map, and $T(x)=\operatorname{\mathsf{N}}_{\mathsf{C}}(x)$ the
normal cone of a given closed convex set $\mathsf{C}\subset\mathsf{H}$. Then,
by [11, Prop. 3.3], the gap function (4.49) reduces to the well-known _dual
gap function_ , due to [6],

$\mathsf{Gap}(x)=\sup_{p\in\mathsf{C}}\ \langle V(p),x-p\rangle.$

######  Example 4.3 (Convex Optimization).

Reconsider the general non-smooth convex optimization problem in Example 1.1,
with primal objective function $\mathsf{H}_{1}\ni u\mapsto f(u)+g(Lu)+h(u)$.
Let us introduce the convex-concave function

$\mathcal{L}(u,v)\triangleq f(u)+h(u)-g^{\ast}(v)+\langle
Lu,v\rangle\qquad\forall(u,v)\in\mathsf{H}_{1}\times\mathsf{H}_{2}.$

Define

$\Gamma(x^{\prime})\triangleq\sup_{u\in\mathsf{H}_{1},v\in\mathsf{H}_{2}}\left(\mathcal{L}(u^{\prime},v)-\mathcal{L}(u,v^{\prime})\right)\qquad\forall
x^{\prime}=(u^{\prime},v^{\prime})\in\mathsf{H}=\mathsf{H}_{1}\times\mathsf{H}_{2}.$
(4.50)

It is easy to check that $\Gamma(x^{\prime})\geq 0$, and equality holds only
for a primal-dual pair (saddle-point) $\bar{x}\in\mathsf{S}$. Hence,
$\Gamma(\cdot)$ is a gap function for the monotone inclusion derived from the
Karush-Kuhn-Tucker conditions (1.5). In fact, the function (4.50) is a
standard merit function for saddle-point problems (see e.g. [19]). To relate
this gap function to the Fitzpatrick function, we exploit the maximally
monotone operators $V$ and $T$ introduced Example 1.1. In terms of these
mappings, first observe that for $p=(\tilde{u},\tilde{v}),x=(u,v)$ we have

$\langle V(p),x-p\rangle=\langle\nabla
h(\tilde{u}),u-\tilde{u}\rangle+\langle\tilde{v},Lu\rangle-\langle
L\tilde{u},v\rangle$

Since $h$ is convex differentiable, the classical gradient inequality reads as
$h(u)-h(\tilde{u})\geq\langle\nabla h(\tilde{u}),u-\tilde{u}\rangle$. Using
this estimate in the previous display shows

$\langle V(p),x-p\rangle\leq h(u)-h(\tilde{u})-\langle
L\tilde{u},v\rangle+\langle\tilde{v},Lu\rangle.$

For $p^{\ast}=(\tilde{u}^{\ast},\tilde{v}^{\ast})\in T(p)$, we again employ
convexity to get

$\displaystyle f(u)$ $\displaystyle\geq
f(\tilde{u})+\langle\tilde{u}^{\ast},u-\tilde{u}\rangle\qquad\forall
u\in\mathsf{H}_{1},$ $\displaystyle g^{\ast}(v)$ $\displaystyle\geq
g^{\ast}(\tilde{v})+\langle\tilde{v}^{\ast},v-\tilde{v}\rangle\qquad\forall
v\in\mathsf{H}_{2}.$

Hence,

$\langle\tilde{u}^{\ast},u-\tilde{u}\rangle+\langle\tilde{v}^{\ast},v-\tilde{v}\rangle\leq(f(u)-f(\tilde{u}))+(g^{\ast}(v)-g^{\ast}(\tilde{v})).$

Therefore, we see

$\displaystyle\langle V(p)+p^{\ast},x-p\rangle$
$\displaystyle\leq\left(f(u)+h(u)-g^{\ast}(\tilde{v})+\langle\tilde{v},Lu\rangle\right)-\left(f(\tilde{u})+h(\tilde{u})-g^{\ast}(v)+\langle
v,L\tilde{u}\rangle\right)$
$\displaystyle=\mathcal{L}(u,\tilde{v})-\mathcal{L}(\tilde{u},v).$

Hence,

$\displaystyle\mathsf{Gap}(x)=\sup_{(p,p^{\ast})\in\operatorname{gr}(T)}\langle
V(p)+p^{\ast},x-p\rangle$
$\displaystyle\leq\sup_{(\tilde{u},\tilde{v})\in\mathsf{H}_{1}\times\mathsf{H}_{2}}\left(\mathcal{L}(u,\tilde{v})-\mathcal{L}(\tilde{u},v)\right)=\Gamma(x).$

It is clear from the definition that a convex gap function can be extended-
valued and its domain is contingent on the boundedness properties of
$\operatorname{dom}T$. In the setting where $T(x)$ is bounded for all
$x\in\mathsf{H}$, the gap function is clearly globally defined. However, the
case where $\operatorname{dom}T$ is unbounded has to be handled with more
care. There are potentially two approaches to cope with such a situation: One
would be to introduce a perturbation-based termination criterion as defined in
[60], and recently used in [20] to solve a class of structured stochastic
variational inequality problems. The other solution strategy is based on the
notion of _restricted merit functions_ , first introduced in [65], and later
on adopted in [57]. We follow the latter strategy.

Let $x^{s}\in\operatorname{dom}T$ denote an arbitrary reference point and
$D>0$ a suitable constant. Define the closed set
$\mathsf{C}\triangleq\operatorname{dom}T\cap\\{x\in\mathsf{H}|\;\lVert
x-x^{s}\rVert\leq D\\}$, and the _restricted gap function_

$\mathsf{Gap}(x|\mathsf{C})\triangleq\sup\\{\langle
y^{\ast},x-y\rangle|y\in\mathsf{C},y^{\ast}\in F(y)\\}.$ (4.51)

Clearly, $\mathsf{Gap}(x|\operatorname{dom}T)=\mathsf{Gap}(x)$. The following
result explains in a precise way the meaning of the restricted gap function.
It extends the variational case in [65, Lemma 1] and [57, Lemma 3] to the
general monotone inclusion case.

######  Lemma 4.12.

Let $\mathsf{C}\subset\mathsf{H}$ be nonempty closed and convex. The function
$\mathsf{H}\ni x\mapsto\mathsf{Gap}(x|\mathsf{C})$ is well-defined and convex
on $\mathsf{H}$. For any $x\in\mathsf{C}$ we have
$\mathsf{Gap}(x|\mathsf{C})\geq 0$. Moreover, if $\bar{x}\in\mathsf{C}$ is a
solution to (MI), then $\mathsf{Gap}(\bar{x}|\mathsf{C})=0$. Moreover, if
$\mathsf{Gap}(\bar{x}|\mathsf{C})=0$ for some $\bar{x}\in\operatorname{dom}T$
such that $\lVert\bar{x}-x^{s}\rVert<D$, then $\bar{x}\in\mathsf{S}$.

###### Proof.

The convexity and non-negativity for $x\in\mathsf{C}$ of the restricted
function is clear. Since $\mathsf{Gap}(x|C)\leq\mathsf{Gap}(x)$ for all
$x\in\mathsf{H}$, we see

$\bar{x}\in\mathsf{S}\Leftrightarrow\mathsf{Gap}(\bar{x})=0\Rightarrow\mathsf{Gap}(\bar{x}|\mathsf{C})=0.$

To show the converse implication, suppose $\mathsf{Gap}(\bar{x}|\mathsf{C})=0$
for some $\bar{x}\in\mathsf{C}$ with $\lVert\bar{x}-x^{s}\rVert<D$. Without
loss of generality we can choose $\bar{x}\in\mathsf{C}$ in this particular
way, since we may choose the radius of the ball as large as desired. It
follows that $\langle y^{\ast},\bar{x}-y\rangle\leq 0$ for all
$y\in\mathsf{C},y^{\ast}\in F(y)$. Hence, $\bar{x}\in\mathsf{C}$ is a Minty
solution to the Generalized Variational inequality with maximally monotone
operator $F(x)+\operatorname{\mathsf{N}}_{\mathsf{C}}(x)$. Since $F$ is upper
semi-continuous and monotone, Minty solutions coincide with Stampacchia
solutions, implying that there exists $\bar{x}^{\ast}\in F(\bar{x})$ such that
$\langle\bar{x}^{\ast},y-\bar{x}\rangle\geq 0$ for all $y\in\mathsf{C}$ (see
e.g. [18]). Consider now the gap program

$\displaystyle
g_{\mathsf{C}}(\bar{x},\bar{x}^{\ast})\triangleq\inf\\{\langle\bar{x}^{\ast},y-\bar{x}\rangle|y\in\mathsf{C}\\}.$

This program is solved at $y=\bar{x}$, which is a point for which $\lVert
x-x^{s}\rVert<D$. Hence, the constraint can be removed, and we conclude
$\langle\bar{x}^{\ast},y-\bar{x}\rangle\geq 0$ for all
$y\in\operatorname{dom}(F)$. By monotonicity of $F$, it follows

$\langle
y^{\ast},y-\bar{x}\rangle\geq\langle\bar{x}^{\ast},y-\bar{x}\rangle\geq
0\quad\forall(y,y^{\ast})\in\operatorname{gr}(F).$

Hence, $\mathsf{Gap}(\bar{x})=0$ and we conclude $\bar{x}\in\mathsf{S}$.
$\blacksquare$ $\blacksquare$

We start with the first preliminary result.

######  Lemma 4.13.

Consider the sequence $(X_{k})_{k\in\mathbb{N}}$ generated by RISFBF with the
initial condition $X_{0}=X_{1}$. Suppose $\lambda_{k}=\lambda\in(0,1/(2L))$
for every $k\in\mathbb{N}$. Moreover, suppose $(\alpha_{k})_{k\in\mathbb{N}}$
is a non-decreasing sequence such that $0<\alpha_{k}\leq\bar{\alpha}<1$,
$\rho_{k}=\tfrac{3(1-\bar{\alpha})^{2}}{2(2\alpha_{k}^{2}-\alpha_{k}+1)(1+L\lambda)}$
for every $k\in\mathbb{N}$. Define

$\Delta
M_{k}\triangleq\frac{3\rho_{k}\lambda_{k}^{2}}{1+L\lambda_{k}}\lVert\mathtt{e}_{k}\rVert^{2}+\frac{\rho_{k}\lambda^{2}_{k}}{2}\lVert
U_{k}\rVert^{2}$ (4.52)

and for $(p,p^{\ast})\in\operatorname{gr}(F)$, we define $\Delta
N_{k}(p,p^{\ast})$ as in (4.4). Then, for all
$(p,p^{\ast})\in\operatorname{gr}(F)$, we have

$\sum_{k=1}^{K}2\rho_{k}\lambda\langle
p^{\ast},Y_{k}-p\rangle\leq(1-\alpha_{1})\lVert
X_{1}-p\rVert^{2}+\sum_{k=1}^{K}\Delta M_{k}+\sum_{k=1}^{K}\Delta N_{k}(p,0).$
(4.53)

###### Proof.

For $(p,p^{\ast})\in\operatorname{gr}(V+T)$, we know from eq. (4.6)

$\langle Z_{k}-R_{k},Y_{k}-p\rangle\geq\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle+\lambda_{k}\langle
V(Y_{k})-V(p),Y_{k}-p\rangle\geq\langle
p^{\ast},Y_{k}-p\rangle+\lambda_{k}\langle W_{k},Y_{k}-p\rangle,$

where the last inequality uses the monotonicity of $V$. We first derive a
recursion which is similar to the fundamental recursion in Lemma 4.3. Invoking
(4.8) and (4.9), we get

$\displaystyle\lVert X_{k+1}-p\rVert^{2}$ $\displaystyle\leq\lVert
Z_{k}-p\rVert^{2}-\frac{1-\rho_{k}}{\rho_{k}}\lVert
X_{k+1}-Z_{k}\rVert^{2}+2\lambda^{2}\rho_{k}\lVert\mathtt{e}_{k}\rVert^{2}-2\rho_{k}\lambda_{k}\langle
W_{k}+p^{\ast},Y_{k}-p\rangle$
$\displaystyle-\rho_{k}(1-2L^{2}\lambda^{2}_{k})\lVert
Y_{k}-Z_{k}\rVert^{2}+\frac{\rho_{k}\lambda^{2}_{k}}{2}\lVert
U_{k}\rVert^{2}+2\rho_{k}\lambda_{k}\langle V(Y_{k})-V(p),p-Y_{k}\rangle.$
(4.54)

Multiplying both sides of (4.11) and noting that
$(1-2L\lambda_{k})(1+L\lambda_{k})\leq 1-2L^{2}\lambda^{2}_{k}$, we obtain the
following inequality

$\displaystyle-\rho_{k}(1-2L^{2}\lambda^{2}_{k})\lVert
Y_{k}-Z_{k}\rVert^{2}\leq-\frac{1-2L\lambda_{k}}{2\rho_{k}(1+L\lambda_{k})}\lVert
X_{k+1}-Z_{k}\rVert^{2}+\frac{\rho_{k}\lambda^{2}_{k}(1-2L\lambda_{k})}{1+L\lambda_{k}}\lVert\mathtt{e}_{k}\rVert^{2}.$

Inserting the above inequality to (4.54) and using the same fashion in
deriving (4.16), we arrive at

$\displaystyle\lVert X_{k+1}-p\rVert^{2}$
$\displaystyle\leq(1+\alpha_{k})\lVert X_{k}-p\rVert^{2}-\alpha_{k}\lVert
X_{k-1}-p\rVert^{2}$ $\displaystyle+\Delta M_{k}+\Delta
N_{k}(p,p^{\ast})-2\rho_{k}\lambda_{k}\langle V(Y_{k})-V(p),Y_{k}-p\rangle$
$\displaystyle+\alpha_{k}\lVert
X_{k}-X_{k-1}\rVert^{2}\left(2\alpha_{k}+\frac{3(1-\alpha_{k})}{2\rho_{k}(1+L\lambda_{k})}\right)$
$\displaystyle-(1-\alpha_{k})\left(\frac{3}{2\rho_{k}(1+L\lambda_{k})}-1\right)\lVert
X_{k+1}-X_{k}\rVert^{2}.$ (4.55)

Invoking the monotonicity of $V$ and rearranging (4.55), it follows that