Convergence of sequences: a survey

Introduction

Why Are Convergence Theorems Necessary? The answer to this “naive” question is not simple. cit. Boris T. Polyak, 1987 [1, Section 1.6.2].

While the answer may have become clearer through the years, since many problems in applied mathematics rely on convergence theorems, it is still not simple. Besides the theoretical investigation, in fact, one fundamental aspect is how convergence theorems can be of practical use, i.e., if the assumptions are plausible for a variety of applications, for instance, in systems theory. Moreover, convergence theorems may also give qualitative information, e.g., if convergence is guaranteed for any initial point and in what sense (strongly, weakly, almost surely, in probability), which affects the range of application. The aim of this paper is to collect these results towards a complete overview, thus to be able to find the one that most suits the application at hand. In fact, many convergence results find their use in theoretical applications, such as Lyapunov stability analysis , variational analysis and game equilibrium seeking , in automatic control, such as model predictive control and network control problems , as well as in other engineering areas, e.g., training and learning in generative adversarial networks , vehicle flow control in traffic networks and in modeling the prosumer behavior in smart power grids .

In the mathematical literature, many convergence results hold for sequences of numbers while in system and control theory, the state and decision variables are usually vectors of real numbers. It is therefore important to understand the deep connection between the two theories. The bridging idea is to associate a real number to the state vector, i.e., via a function, and then prove convergence exploiting the properties of such a function. The most common example of this approach is that of Lyapunov theory where a suitable Lyapunov function is shown to be decreasing along the evolution of the state variable, thus obtaining convergence of the state vector to a target set . An alternative approach is to consider the distance from a target set and show that such a distance vanishes eventually via a suitable technical result on the convergence of the distance-valued sequence of real numbers.

In this work, we focus mostly on the latter methodology. To explain our choice, let us note that solving an optimization problem consist of designing a sequence of vectors that converge to the solution, the minimum of a given cost function. Similarly, in algorithmic game theory, one usually aims at constructing a sequence that converge to an equilibrium, e.g., a Nash equilibrium, the optimum for each player given the actions of the other players. The key point here is that, in general, the target set is not known a priori, yet the distance of the constructed sequence from such set can be analyzed anyways. On the contrary, in Lyapunov stability analysis, the target set is usually known a priori.

By exploiting the relation between the iterations and a suitable distance-like function, we show in this paper that convergence theorems represent a key ingredient for a wide variety of system-theoretic problems in fixed-point theory, game theory and optimization . In many cases, the study of iterative algorithms allows for a systematic analysis that follows from the concept of Féjer monotone sequence. The basic idea behind Féjer monotonicity is that at each step, each iterate is closer to the target set than the previous one. In a sense, the distance used for Féjer sequences can be seen as a specific class of Lyapunov function and Féjer monotonicity shows that it is decreasing along the iterates. The concept was first introduced in 1922 , but the term Féjer monotone sequence was first used thirty years later in 1954 and a huge part of the studies on its properties was made in the 60s and still continues .

Unfortunately, Féjer monotonicity is hard to obtain, therefore the concept is typically relaxed to a quasi-Féjer property, where a vanishing error must be considered. Such an error term in the distance inequality is common in many equilibrium problems , especially in the stochastic case where the concept of quasi-Féjer monotone sequence was first introduced . However, these properties are not necessarily enough to ensure convergence, hence, (quasi) Féjer monotonicity is often used in combination with convergence results on sequences of real numbers. These technical results have been used in many theoretical and computational applications that range from stochastic Nash equilibrium seeking to machine learning .

2 What this survey is about

In this survey, we present a number of convergence theorems for sequences of real (random) numbers. We show how they can be used in combination with (quasi) Féjer monotone sequences or Lyapunov functions to obtain convergence of an iterative algorithm, essentially a discrete-time dynamical system, to a desired solution. Moreover, we present some applications to show how they can be adopted in a variety of settings. Specifically, we present convergence results for both deterministic and stochastic sequences of real numbers and we also include some results on Féjer monotone sequences and with variable metric. We show that these results help proving not only convergence of an iterative algorithm but also the Law of Large Numbers, with applications in model predictive control and opinion dynamics among others.

We report in Tables 1 and 2 the results for deterministic and stochastic sequences respectively, with the corresponding bibliographic source and application.

The paper is organized as follows. In the next section, we recall some preliminary notions on the concept of “convergence” and of random variables. Section 3 is devoted to deterministic convergence results while the stochastic case is discussed in Section 4. An extension with variable metric is considered in Section 5. Sections 6, 7 and 8 propose applications of the convergence lemmas for deterministic, stochastic, and variable metric sequences, respectively.

3 What this survey is not about

This is not a survey on solution algorithms for optimization problems and variational inequalities. Some relevant references on iterative methods include and the references therein.

We also remark that, despite the notion of Féjer sequence is used throughout the paper, this is not a survey on the properties of Féjer monotone sequences. The interested reader may refer to .

Notation and Preliminaries

We use the nomenclature and notation from .

With reference to the application sections, we use Standing Assumptions to state technical conditions that implicitly hold throughout the paper, while Assumptions are postulated only when explicitly used.

More notation and definitions related to monotone operator theory, functional to the application sections, are postponed to Appendix A.

Let us first recall some definitions related to the notion of convergence itself.

In general, strong convergence implies weak convergence. In finite dimension, the two notions are equivalent [23, Lemma 2.51], hence, in this paper, we generally talk about convergence.

Given the definition of convergence, let us define the concept of cluster point.

Let us conclude this section with some preliminary results related to the convergence properties of a given sequence. We consider these results common knowledge and we refer to them throughout the paper, even without a specific reference.

2 Probability theory

From now on, results involving random variables are supposed to hold almost surely, even if it is not explicitly mentioned.

Let us recall some probabilistic and stochastic definitions that will be useful later on. We start with the definition of filtration.

In words, a filtration is a family of $\sigma$-algebras non-decreasingly ordered that collects the history of $\xi^{k}$. Given a filtration, a subsequent important concept is that of martingale [59, Chapter 7], [62, Section 1.9], [63, Section 4.1].

These notions are the stochastic generalization of the notion of monotone (decreasing or increasing) sequences. Moreover, we note that every martingale is a submartingale and a supermartingale, while every sequence which is both a submartingale and a supermartingale is also a martingale.

We conclude this section with the following result, due to Doob [59, Theorem 7.4.1], [1, Lemma 2.2.7], [65, Theorem 3.3.1].

3 Distance from a target set

The basic idea for proving convergence of a sequence is that the distance from the solution should vanish or at least decrease at each iteration. This is particularly important when we consider vectors, i.e., when convergence results for sequences of real numbers cannot be applied directly.

The most used concept in this direction is that of Féjer monotone sequence. The term was coined in but the concept was first proposed by Féjer in . These processes have been widely studied in the literature since they can be applied in solving classical problems as systems of equations or inequalities, operator equations with a priori information, equilibrium problems, and many others . The key point is that one can take the target set to be the solution set of the problem of interest (even if it is unknown). Then, since the distance from the target decreases, the sequence will eventually reach (a point close to) the solution.

In words, Definition 2.6 states that the distance between the iterates and any point $\bar{x}\in S$ does not increase.

Let us consider the sequence $v^{k}=\frac{(-1)^{k}}{k}$. Though the sequence is oscillating, it is convergent to $\bar{v}=0$ and it is Féjer monotone with respect to $\mathcal{S}=\{0\}$.

An example of a Féjer monotone sequence is the one generated by the projection (Definition A.1) onto a nonempty, closed and convex set $\mathcal{C}$ , i.e.,

The claim follows immediately from the fact that the projection operator is firmly nonexpansive [23, Proposition 4.16], hence nonexpansive (Definition A.3). In fact, any sequence generated by an iteration of the form $x^{k+1}=T(x^{k})$ where $T$ is a nonexpansive operator is a Féjer monotone sequence [33, Equation (2)].

The notion of Féjer monotonicity can be extended in various directions . Here we recall only the concept of quasi-Féjer monotone sequence, first introduced in the stochastic case (see also Definition 2.8) and later in several (deterministic) variants .

Definition 2.7 is perhaps the most general definition of quasi-Féjer monotone sequence, as there are no restrictions on the function $\phi$. However, besides some general results (see, e.g., Proposition 5.30 and Theorem 5.31), many convergence theorems hold for a given choice of the function, i.e., $\phi=|\cdot|$ or $\phi=|\cdot|^{2}$. For details, see Section 3.1 or .

Next, we give a definition of Féjer monotone sequence in the stochastic case. Stochastic quasi-Féjer monotone sequences were first introduced in and later discussed in . The interpretation is that the expected value of the distance from the target set is non-increasing, which reminds the definition of (super)martingale .

Definitions 2.7 and 2.8 hold true for any norm of choice, yet other metrics can be considered (see Remark 2.2). Moreover, variable metrics have been considered as well .

There are many results on (stochastic, quasi) Féjer monotone sequences but they lie outside the scope of this survey. For a deeper insight on this topic we refer to .

An important generalization of Féjer monotonicity is that of Bregman monotonicity . The concept has received a rising interest recently in the system and control community . For the sake of completeness, we report here the definition, and later on we recall when some results hold also with the Bregman distance.

and it has the following geometric interpretation: $D_{f}(x,y)$ is the difference between $f(x)$ and the value at $x$ of the linearized approximation of $f(x)$ at $y$. $D_{f}(x,y)$ is nonnegative and it is zero if and only if $x=y$.

We note that in general the Bregman distance is not a “real” distance, since it may fail to satisfy, for instance, the triangular inequality.

An example of a Bregman function is $f=\left\|\cdot\right\|^{2}$ whose associated distance is $D_{f}(x,y)=\|x-y\|^{2}/2$. Another example is given by $g(x)=\sum_{i=1}^{n}x_{i}\log x_{i}$ with the convention that $0\log 0=0$. The associated distance is $D_{g}(x,y)=\sum_{i=1}^{n}(x_{i}\log\frac{x_{i}}{y_{i}}+y_{i}-x_{i})$ [13, Example 12.7.4], i.e., the Kullback–Leibler divergence , widely used in machine learning and generative adversarial networks .

$\mathcal{S}\cap\mathcal{C}\neq\varnothing$,

Convergence of deterministic sequences

In this section, we walk through a number of convergence results for deterministic sequences of real numbers. When possible, we propose first the most general result and then show its consequences. We start with some results on Féjer monotone sequences and then move to general sequences of real numbers.

The first result we present is related to the concept of Féjer monotone sequences and it was originally proposed in . Parts of this result are also in [61, Theorems 2.7 and 2.10] while in [33, Propositions 1–4] a distinction between strong and weak convergence is made. Other properties of Féjer monotone sequences can be found in and reference therein.

The statements follow from the definition of Féjer monotone sequence (Definition 2.6). ∎

A similar result holds also for quasi-Féjer sequences [24, Proposition 3.3], [48, Proposition 1]. However, in such a case it is not possible to prove that the distance from the target set is decreasing as in Proposition 3.5(iii).

Necessity is straightforward. Sufficiency follows from Remark 3.1 (specifically from [24, Proposition 3.3]). ∎

Under suitable conditions, convergence results as in Proposition 3.5 and Theorem 3.6 can be obtained also for Bregman monotone sequences [66, Proposition 4.1 and Theorem 4.11].

The following result is known as the Opial Lemma and it can be found in many works and with different applications , since it often relate to convergence of sequences generated by nonexpansive operators (see also Example 2.8). We here show a proof which follows from some results in and we report the discrete time formulation , but it can be found also in continuous time . For a different proof see .

for all $z\in\mathcal{X}$ $\lim_{k\to\infty}||x^{k}-z||$ exists;

Therefore, $\langle x^{k},\bar{x}-\bar{y}\rangle$ converges to some point $w$. Taking the limit along $x_{k_{n}}$ and $x_{k_{l}}$ we have

It follows that $\left\|\bar{x}-\bar{y}\right\|^{2}=0$ hence $\bar{x}=\bar{y}$. ∎

The Opial Lemma provides a powerful tool to derive convergence of an iterative process. In fact, condition 2. has been already mentioned in many previous results in this survey. Interestingly, similar results can be extended to the Bregman distance .

2 Convergent sequences of real numbers

We now introduce a number of results on sequences of real numbers. We note that even if the following results are for general sequences of real numbers, their importance for system theory lies on the fact that they can be paired with (quasi) Féjer monotonicity (see Remark 3.5). In Table 3, we summarize the results presented in this section, with emphasis on the auxiliary sequences that may affect convergence.

Let us note that, in the first line of Table 3, $C^{k}$ is a coefficient which, depending on the form, represents the level of expansion or contraction, $\varepsilon^{k}$ can be seen as an additive noise and $\theta^{k}$ is a “negative term”, because of the minus sign, which decreases the value of the sequence $v^{k}$. For a graphical interpretation of the effects of those sequences, we also refer to Figure 4 later on, which is specifically related to Lemma 3.9.

The first lemma that we report is widely used and it has a number of consequences that are widely used as well. We do not include the proof since it is very similar to the proof of the forthcoming Lemma 3.13.

If $\gamma\neq 1$, then $\sum_{k=0}^{\infty}v^{k}<\infty$.

Ffor a specific choice of the noise term, the following result can be proven [41, Lemma 3.3]. Suppose

The next lemma is a consequence and a generalization of Lemma 3.8. It has its stochastic counterpart in the well know Robbins–Siegmund Lemma (Lemma 4.23) . It is taken from yet here we provide a different proof. For a graphical interpretation, we refer to Figure 4.

We note that there is a slight difference between Lemma 3.8 and Lemma 3.9. Specifically, in the former, the sequence converges if the coefficient $\gamma$ is in the interval $(0,1]$ while in Lemma 3.9 the coefficient can be taken larger than 1 and time varying.

The following results are immediate consequences of Lemmas 3.8 and 3.9. Let us start with removing the noise term.

It follows from Lemmas 3.8 and 3.9 by taking $\delta^{k}$ and $\varepsilon^{k}$ equal to 0. ∎

Similarly, this result from can be obtained as a consequence of Lemma 3.9 by removing the negative term.

and $\sum_{k=0}^{\infty}\delta^{k}<\infty$, $\sum_{k=0}^{\infty}\varepsilon^{k}<\infty$. Then $v^{k}$ converges to some $\bar{v}\geq 0$.

Concerning the coefficient sequence, other options can be considered. In the next result, the coefficient should be strictly smaller than 1, compared to Lemma 3.9, but need not be constant as in Lemma 3.8.

$\sum_{k=0}^{\infty}\left(1-\gamma_{k}\right)=\infty,$

$\lim_{k\to\infty}\frac{\varepsilon^{k}}{1-\gamma_{k}}=0$.

Then, $lim_{k\to\infty}v^{k}=\bar{v}\leq 0$. Moreover, if $v^{k}>0$ then $\lim_{k\to\infty}v^{k}=0$.

Note that $\sum_{k=0}^{\infty}\left(1-\gamma_{k}\right)=\infty$ implies that $\prod_{k=0}^{\infty}\gamma_{k}=0$ therefore taking the $\limsup$ as $k\to\infty$ leads to $\limsup v^{k}\leq\varepsilon$, which proves the claim. ∎

In [41, Lemma 2.1], the result in Lemma 3.12 is proven also for a different condition than 1., i.e.,

The proof follows considering the shifted process starting from $\bar{k}$ and using Lemma 3.12 on the resulting sequence.

Many of the previous results have the coefficient $(1+\delta^{k})$, therefore, we now consider what happens if we change it to $(1-\delta^{k})$ (see also Figure 5 for a graphical interpretation). This might be a special case of Lemma 3.8 but, in some cases, it allows to study convergence to zero (see Remark 3.8), which relates to the standard Lyapunov based approach for stability analysis. In fact, we have already had a glimpse of the effect of a coefficient smaller than 1 in Lemma 3.8(iv) and Lemma 3.12 and its connection with Lyapunov analysis (Remark 3.5).

The first result of this type extends the previous lemmas to this case. This result is new as we provide a proof that does not follow from previous results.

The following lemmas are taken from various works and they are quite similar to each other. We here establish the relations and difference between them. Let us remark that in the following results, the sequence $\delta^{k}$ in the coefficient is not summable, i.e., from now on $\sum_{k=1}^{\infty}\delta^{k}=\infty$. The advantage of this choice is that convergence to zero can be obtained, as shown in Figure 5.

The first result considers real (not only positive) noise sequences $\varepsilon^{k}$ and it also provides two alternative conditions on the auxiliary sequences.

$\delta^{k}\in$ and $\sum_{k=0}^{\infty}\delta_{k}=\infty$, or equivalently, $\prod_{k=0}^{\infty}\left(1-\delta^{k}\right)=0$,

$\sum_{k=0}^{\infty}\delta^{k}\beta^{k}<\infty$.

If $1.$ and $2a.$ hold, then the result can be proven with the same arguments as the proof of Lemma 3.12 by setting $\varepsilon^{k}=\delta^{k}\beta^{k}$. On the other hand, if $1.$ and $2b.$ hold, we have for all $k>m$

Taking the limit for $k\to\infty$ and $m\to\infty$ we have $\limsup v^{k}\leq 0$. ∎

We note that if we set $\gamma_{k}=1-\delta^{k}$ and $\varepsilon^{k}=\delta^{k}\beta^{k}$, we obtain the same statement as Lemma 3.12. Moreover, condition $2b.$ provides an alternative assumption, similar to most results in the literature.

Assumption $2a.$ in Lemma 3.14 is used in a previous paper by the same authors [43, Lemma 2.5]. Since also Assumption $2b.$ in Lemma 3.14 can be used to prove the following result, let us extend [43, Lemma 2.5] next.

$\delta^{k}\in$, $\sum_{k=0}^{\infty}\delta^{k}=\infty$, or equivalently, $\prod_{k=1}^{\infty}(1-\delta^{k})=0$,

$\sum_{k=0}^{\infty}\delta^{k}\beta^{k}<\infty$,

$\varepsilon^{k}\geq 0$ and $\sum_{k=0}^{\infty}\varepsilon^{k}<\infty$.

A particular case of Lemma 3.15 is proposed in as a consequence of [95, Theorem 3.3.1]. Let us note that the assumptions in the following result imply those in Lemma 3.15 which is, in turn, more general.

$\sum_{k=1}^{\infty}\delta^{k}=\infty$ and $\lim_{k\to\infty}\delta^{k}=0$

$\sum_{k=1}^{\infty}\delta^{k}\eta^{k}<\infty$

The sequence satisfies the assumptions of Lemma 3.15, hence the result holds. ∎

A very recent result of this type is a consequence of both Lemma 3.12 and Lemma 3.14.

$\delta^{k}\in(0,1)$ and $\sum_{k=1}^{\infty}\delta^{k}=\infty$,

$\lim\sup_{k\to\infty}\frac{\varepsilon^{k}}{\delta^{k}}\leq 0$ ,

$\sum_{k=1}^{\infty}|\varepsilon^{k}|<\infty$.

Suppose that $2a.$ holds. Then, the proof follows from Lemma 3.12 by setting $\gamma_{k}=(1-\delta^{k})$. When $2b.$ holds instead, the proof follows applying Lemma 3.14 by defining $\varepsilon^{k}=\delta^{k}\frac{\varepsilon^{k}}{\delta^{k}}=\delta^{k}\beta^{k}$. ∎

A consequence of Corollary 3.17 is the following result that presents a slightly different notation.

$\delta^{k}\in$ and $\sum_{k=0}^{\infty}\delta^{k}=\infty$,

Then, $\lim_{k\rightarrow\infty}v^{k}=0.$

We note that $\varepsilon^{k}=o(\delta^{k})$ is equivalent to $\lim_{k\to\infty}\varepsilon^{k}/\delta^{k}=0$. Then, the result follows by applying Corollary 3.17 and Lemma 3.15. ∎

If $\varepsilon^{k}\leq\delta^{k}M$ for some $M\geq 0$, then $(v^{k})$ is a bounded sequence.

If $\sum_{k=1}^{\infty}\delta^{k}=\infty$ and $\lim\sup_{n\rightarrow\infty}\frac{\varepsilon^{k}}{\delta^{k}}\leq 0$, then $\lim_{n\rightarrow\infty}v^{k}=0$.

We note that (ii) is a consequence of Lemma 3.15 or Corollaries 3.17 and 3.18.

We now consider three results whose conditions for convergence are more involved than the results proposed until now . The first one is proposed in . It allows for non-summable additive noise but requires a condition that couple the sequences involved.

Moreover, if there exists $a>0$ such that

Both claims can be proven by contradiction. See for more details. ∎

In the next result, the sequence should satisfy two interdependent inequalities .

$\lim_{k\rightarrow\infty}\varepsilon^{k}=0$

$\lim_{k\rightarrow\infty}\eta^{k_{n}}=0$ implies that $\lim\sup_{k\rightarrow\infty}\gamma^{k_{n}}\leq 0$ for any subsequence $(k_{n})\subset(k)$

$\lim\sup_{n\rightarrow\infty}\frac{\beta^{k}}{\delta^{k}}\leq 0$.

Then, $\lim_{n\rightarrow\infty}v^{k}=0$.

and $\operatorname{limsup}_{k\to\infty}v^{\tau(k)}\leq 0$. Hence, $\lim_{k\to\infty}v^{k}=0$. For more details we refer to . ∎

By removing $\beta^{k}$ in Equation (3.3), the result holds as a particular case of Lemma 3.20 and can be proven similarly, using Lemma 3.14 instead of Lemma 3.15.

The next result, instead, uses the sequence at two steps backwards.

$\sum_{k=1}^{\infty}\varepsilon^{k}<\infty$

$(\delta^{k})\subset[0,\delta]$, where $\delta\in[0,1)$.

The result can be extended to the case with a negative term, namely, Equation (3.4) becomes

where $\theta^{k}$ is a nonnegative sequence. The conclusions are the same as Lemma 3.21 and, moreover, it holds that $\sum_{k=1}^{\infty}\theta^{k}<\infty$ [89, Lemma 2].

The inequality in Equation (3.4) can be rewritten as

which is similar to the form of the results presented until now. However, we note that in Lemma 3.21, the sequence $v^{k}$ need not be nonnegative.

We conclude this section with the following result on the convergence rate which guarantees convergence to zero. However, the study of the convergence rates lays outside the scopes of this survey. For similar results, we refer to [5, Lemma 2.9], [97, Lemma 3] and, more generally, to .

Convergence of stochastic sequences

Firstly, we recall some results on convergent random sequences. We start with a result by Robbins and Siegmund, first appeared in , which is the most used in the stochastic literature. In Figure 6, we provide a graphical interpretation.

The proof follows by rewriting the sequence as in Lemma 3.9. Then, it is possible to show that the sequence

is a supermartingale. The claim then follows by the Martingale Convergence Theorem (Theorem 2.4). See for technical details. ∎

The following results are consequences of Robbins–Siegmund Lemma. The first one is attributed to Gladyshev . In fact, it came implicitly in a work by Gladyshev in which the author provides a proof of the convergence of Robbins–Monro algorithm . Even if it was published prior than the result by Robbins-Siegmund, it is a particular case of Lemma 4.23 [53, Application 2].

Then $\lim_{k\to\infty}v^{k}=\bar{v}\geq 0$ a.s. where $\bar{v}$ is a random variable.

It follows from Lemma 4.23 letting $\theta_{k}=0$. Different proofs can be found in [53, Application 2], [1, Lemma 2.2.9] or [65, Theorem 3.3.6]. ∎

Similarly to Lemma 3.8 and Lemma 3.9 in the deterministic case, many results can be obtained removing or changing the sequences in (4.1). In fact, the next corollary is straightforward from Lemma 4.23.

It follows from Robbins–Siegmund Lemma by taking $\varepsilon^{k}=0$. For a different proof, see . ∎

Interestingly, we note that besides convergence of the sequence, there is additional information to be derived from Robbins–Siegmund Lemma. For instance, the next corollary is used in to prove the Law of Large Numbers for martingales [37, Theorem 1.3.15] (see also Section 7).

Then, if $\sum_{k=1}^{\infty}a_{k}^{-1}\varepsilon^{k}<\infty$ the following hold a.s.:

$\sum_{k=1}^{\infty}a_{k}^{-1}(v^{k+1}-v^{k})$ converges and $\sum_{k=1}^{\infty}a_{k}\theta^{k}<\infty$;

Then we can apply Robbins–Siegmund Lemma to the inequality

and conclude the proof. For technical details, we refer to . ∎

The following proposition explicitly connects stochastic quasi-Féjer monotone sequences to Robbins–Siegmund Lemma.

$\sum_{k=1}^{\infty}\theta^{k}<\infty$ a.s.;

Therefore, $\bar{x}=\bar{y}$ and $\lim_{k\to\infty}x^{k}=\bar{x}$. ∎

A specific case of Proposition 4.27 was also presented in [70, Lemma 2.3] without the negative term $\theta^{k}$, using $\phi=|\cdot|^{2}$ and setting $\delta^{k}=0$. More generally, an analogous result holds with $\phi=|\cdot|^{p}$, $p>0$ [56, Lemma 2.2].

Analogously to the deterministic case, also for sequences of random variables, we can find results for sequences with a coefficient strictly smaller than 1. This is the case of the following results.

The proof follows with arguments similar to Lemma 3.15 and Lemma 3.13 but it can be proven also as a consequence of Lemma 4.23. For technical details we refer to . ∎

We conclude this section with a lemma that is quite popular in the literature and cited along with Robbins–Siegmund Lemma. It is the stochastic counterpart of Lemma 3.12 even if it has a slightly different notation.

The proof follows by applying Lemma 3.12 to

is a supermartingale. Then, the claim follows by the Martingale Convergence Theorem (Theorem 2.4). See for technical details. ∎

Convergence to zero in Lemma 4.29 can also be derived from Lemma 4.23 by exploiting the properties of the negative term in Equation (4.3). In fact, from Lemma 4.23 and Equation (4.3) we have that $\sum_{k=1}^{\infty}\delta^{k}v^{k}<\infty$ and since $\delta^{k}$ is not summable, it must be $\lim_{k\to\infty}v^{k}=0$.

Convergence with variable metric

Let us consider in this section the more general setting with variable metric, i.e., cases in which the metric is allowed to change at each iteration. Applications of these results involve theoretical problems as monotone inclusions , as well as inverse problems , convex feasibility problems and constrained convex minimization . All the results in this section concern Féjer properties and we consider mostly the deterministic case. The first result that we propose is an extension of Proposition 3.5.

A similar result holds also for quasi-Bregman monotone sequences and it can be proven analogously by applying Corollary 3.11 .

Analogously to Section 3, under stronger assumptions, we can obtain stronger convergence results. In fact, the next result is a generalization of Theorem 3.6.

Necessity is straightforward while sufficiency follows by Proposition 5.30 and Lemma 2.2. ∎

Let us conclude this section with a result that is particularly interesting for the conditions on the sequence that induce the metric.

It follows from Corollary 3.11 and Proposition 5.30. For technical details we refer to . ∎

The condition in (5.1) is not hard to check on the problem data and it can be helpful for application purposes.

We conclude this section with an adaptation of Proposition 4.27 to the variable metric setup, i.e., an extension of Robbins-Siegmund Lemma (Lemma 4.23) to variable metric quasi-Fejer monotone sequences.

Suppose that $\phi$ is strictly increasing and $\lim_{t\rightarrow\infty}\phi(t)=+\infty.$ Then, the following hold.

(i) follows from Lemma 4.23 and by the fact the $\phi$ is strictly increasing. (ii) Necessity is straightforward while sufficiency follows from the properties of a cluster point and Lemma 2.2. For more details we refer to . ∎

Applications of convergent deterministic sequences

Since variational inequalities are the mathematical foundations of optimization-related problems, such as Nash equilibrium seeking , convex optimization and machine learning , many works in the literature rely on the results presented in the previous sections to prove convergence of a given algorithm to a solution of a variational equilibrium problem. Specifically, they are applied to prove that a given algorithm converges to the solution of a variational inequality or to a zero of the sum of (monotone) operators. Thus, let us first describe the variational problem, starting by the definition of variational inequality .

The set of solutions to this problem is denoted by $\operatorname{SOL}(\mathcal{X},F).$

The geometric interpretation of (6.1) is that a point $x^{*}\in\mathcal{X}$ is a solution of $\operatorname{VI}(\mathcal{X},F)$ if and only if $F(x^{*})$ forms an acute angle with every vector of the form $y-x^{*}$ for all $y\in\mathcal{X}$. In other words, (6.1) also says that a vector $x\in\mathcal{X}$ solves $\operatorname{VI}(\mathcal{X},F)$ if and only if $-F(x^{*})$ is a vector in the normal cone of $\mathcal{X}$ at $x^{*}$ (see Appendix A for the definition), i.e.,

Sometimes, instead of problem (6.1), a more general definition is proposed:

where $g$ is a proper lower semi-continuous and convex function. Examples for the function $g$ are indicator functions to enforce the set constraints, or penalty functions that promote sparsity, or other desirable structure.

Similarly to (6.1) and (6.2), the problem in (6.3) can be rewritten as

where $\partial g$ is the subdifferential of $g$ (definition in Appendix A). In fact, if in (6.3) we take $g$ as the indicator function, i.e., $g(x)=\iota_{\mathcal{X}}(x)$, we obtain the standard variation inequality (6.1), and instead of (6.4) we obtain the inclusion in (6.2) since $\partial g=\partial\iota_{\mathcal{X}}=\operatorname{N}_{\mathcal{X}}$ [58, Equation (14)].

where $\partial g$ denotes the subdifferential of $g$ and $\nabla f$ is the gradient of $f$. Equation (6.7) is a monotone inclusion and it is equivalent to the generalized VI in (6.3) with $F=\nabla f$.

We are now ready to present some algorithms where the lemmas of Section 3 are used. The algorithms often rely on the monotonicity properties of the operators involved (see Definitions A.2 and A.3) and, unless otherwise mentioned, we suppose the following assumption to hold.

The solution set of $\operatorname{VI}(\mathcal{X},F)$ is not empty, i.e., $\operatorname{SOL}(\mathcal{X},F)\neq\varnothing$, and $x_{0}\in\mathcal{X}$, i.e., the sequence starts in the set $\mathcal{X}$ which is closed and convex.

For every algorithm, we also propose a sketch of the convergence proof to show how the lemmas are used. A schematic representation of the necessary steps is provided in Figure 7. The main idea to prove convergence of an algorithm is to obtain a (quasi) Féjer inequality with respect to the solution set and then apply one of the lemmas to the sequence $v^{k}=\|x^{k}-x^{*}\|^{2}$ where $x^{*}\in\operatorname{SOL}(\mathcal{X},F)$ (see also Remark 3.8). Analogously, one can show that a suitable Lyapunov function asymptotically goes to zero.

We list the application depending on the type of problem but we name them after the convergence result that is used. We start with monotone inclusions, then move to VIs and Nash equilibrium problems, and finally consider an example of Lyapunov decrease.

Lemma 3.7 is used in to prove convergence in the inclusion problem:

where $J_{\alpha_{k}A}=(I+\alpha_{k}A)^{-1}$ is the resolvent of A (Definition A.1). The algorithm is named forward - reflected - backward splitting and it is proven to converge to a zero of $A+B$.

Let $x^{*}\in(A+B)^{-1}(0)$. It is possible to show, by using monotonicity and some norm properties, that the following inequality holds:

Then, by doing a telescopic sum, using Lipschitz continuity and the properties of the parameters involved, the inequality in (6.9) can be rewritten as

Similarly to the proof of Theorem 6.34 but using strong monotonicity, one obtains the inequality

Application of Corollary 3.18

As an application of Corollary 3.18, let us consider the inertial forward-backward algorithm proposed in for approximating a zero of an inclusion problem $x\in(A+B)^{-1}(0)$:

where $J_{\alpha_{k}A}$ is the resolvent of $A$ (Definition A.1) and $e^{k}$ is an error vector. By using Corollary 3.18 the authors prove the following result.

Let $B$ be $\alpha$-cocoercive and let $A$ be maximally monotone. Let $\nu_{k},\beta_{k},\gamma_{k}\in(0,1)$ be such that $\nu_{k}+\beta_{k}+\gamma_{k}=1$ and

$\lim_{k\rightarrow\infty}\gamma_{k}=0,$ and $\sum_{k=1}^{\infty}\gamma_{k}=\infty$,

$0<a\leq\nu_{k}\leq b<1$ and $0<c\leq\beta_{k}\leq d<1$,

$0<c\leq\alpha_{k}<2\alpha$ and $\lim_{k\rightarrow\infty}\left(\alpha_{k}-\alpha_{k+1}\right)=0$.

where $\delta^{k}$ is a quantity depending on the error $e_{k}$ and on $x^{*}$ and such that the assumption of Lemma 3.18 are satisfied. Therefore, convergence holds. ∎

2 Applications to Variational Inequalities

where $\varphi=\frac{\sqrt{5}+1}{2}$ is the golden ratio, i.e., $\varphi^{2}=1+\varphi.$ To prove convergence, they use Lemma 3.7 and Lemma 3.9.

Using the fact that $F$ is Lipschitz continuous and monotone and that the proximal operator is firmly nonexpansive, it holds that

In , the authors prove convergence of the explicit GRAAL which is a variation of algorithm in (6.12) with an adaptive step size rule. In this case, they only use locally Lipschitz continuity and conclude convergence via Lemma 3.7 [6, Theorem 2].

The algorithm has been recently extended tot he stochastic case and for stochastic generalized Nash equilibrium problems and generative adversarial networks with a proof that relies on Lemma 4.23 on the same line of Section 7.1.

Application of Corollary 3.10

Corollary 3.10 is used in to prove convergence of the projected reflected gradient method for variational inequalities as in (6.1). In details, the algorithm reads as

and they show that the following result holds.

where $x^{*}\in\operatorname{SOL}(\mathcal{X},F)$. Now, by letting

This algorithm has been recently extended to the stochastic case and proved similarly, by exploiting Lemma 4.29.

3 Applications to Nash equilibrium problems

The fact that Lemma 3.15 guarantees convergence to zero (Remark 3.8) is used in to compute a Nash equilibrium in traffic networks. In a dynamic traffic assignment problem, travelers participate in a non-cooperative Nash game choosing a departure time and a route. The author propose a forward-backward-forward algorithm (inspired by ), given by

to solve the associated variational problem. The convergence result is stated next and it shows convergence to the solution of the VI associated to the Nash equilibrium problem [13, Proposition 1.4.2].

Using the definition of the algorithm in (6.15) and some preliminary inequalities [20, Lemma 4.1], it holds that [20, Lemma 4.3]

Application of Lemma 3.12

An instance of how Lemma 3.12 can be used to prove convergence is given in where the authors propose a Nash equilibrium seeking algorithm via a Tikhonov regularization. The iterations, for each agent $i\in\mathcal{I}=\{1,\dots,N\}$, read as

where $\gamma_{k}=(\gamma_{i}^{k})_{i=1}^{N}$ and $\epsilon_{k}=(\epsilon_{i}^{k})_{i=1}^{N}$ are the step size and regularization sequences, respectively, and $\mathcal{C}_{i}$ is the local feasible set for each player $i$. Then, the following result holds.

$\sum_{k=1}^{\infty}\gamma_{j}^{k}\epsilon_{j}^{k}=\infty$

$\lim_{k\rightarrow\infty}\frac{(\gamma_{\max}^{k})^{2}}{\gamma_{\min}^{k}\epsilon_{\min}^{k}}=0$

$\sum_{k=1}^{\infty}(\gamma_{j}^{k})^{2}<\infty$

$\sum_{k=1}^{\infty}(\epsilon_{j}^{k}\gamma_{j}^{k})^{2}<\infty$

$\lim_{k\rightarrow\infty}\frac{\epsilon_{\max}^{k-1}-\epsilon_{\min}^{k}}{\epsilon_{\min}^{k}(\gamma_{\min}^{k})^{2}}=0$

$\lim_{k\rightarrow\infty}\frac{\gamma_{\max}^{k}\epsilon_{\max}^{k}-\gamma_{\min}^{k}\epsilon_{\min}^{k}}{\gamma_{\min}^{k}\epsilon_{\min}^{k}}=0$

$\lim_{k\rightarrow\infty}\epsilon_{j}^{k}=0$ for all $j=1,\ldots,N$.

Since the classic Tikhonov relaxation, i.e., the iterative process where $y^{k+1}$ solves $\operatorname{VI}(\mathcal{X},F^{k})$ and $F^{k}(y)=F(y)+\epsilon^{k}y$, is convergent , the authors first show that [41, Proposition 2.3]

4 Application to Lyapunov decrease

In this application, we show how the convergence results can be used in combination with a Lyapunov function. Let us consider the classic gradient method

Using differentiability and Lipschitz continuity, we obtain

Then, applying Corollary 3.10 the claim follows. ∎

5 Other applications

Opial Lemma (Lemma 3.7) is widely used for deterministic problems, in discrete and continuous time . Moreover, another application of Lemma 3.7 can be found in where the authors propose a forward-backward-forward algorithm with an application to generative adversarial networks .

Concerning inclusion problems, the interested reader may find an application of Lemma 3.21 in while, for a different iterative scheme, Corollary 3.17 is used in ; finally, an application of Lemma 3.20 can be found in . Lemma 3.20 is used also for a variational problem in , along with Lemma 3.14. Moving to Nash equilibrium problems, Lemma 3.12 is used in while Lemma 3.15 is used in .

Applications of convergent stochastic sequences

Similarly to the deterministic case, many applications of the lemmas for random sequences concern the study of convergent algorithms for stochastic variational inequalities. Most of the literature relies on Robbins–Siegmund Lemma and on the monotone and Lipschitz properties of the operator (see Definitions A.2 and A.3 in Appendix A.2).

and analogously to the deterministic case, we can consider the general variational inequality as in (6.3)

The batch size sequence $(\mathcal{N}_{k})_{k\geq 1}$ is such that, for some $c,k_{0},a>0$,

It follows from Standing Assumption 7.1 that the batch size sequence is summable and this is fundamental to control the error committed in the approximation (see also Lemma A.51).

From now on, whenever we refer to an approximation without specifying the type, we use the symbol $\hat{F}$, while if it is one of the two schemes we explicitly use $F^{\textup{SA}}$ or $F^{\textup{VR}}$.

Since we study an approximation (independently on the scheme), let us indicate the stochastic error, that is, the distance between the expected value and its approximation, with

Standard assumptions on the stochastic error $\epsilon^{k}$ are that it has zero mean and bounded variance .

Moreover, for all $x\in\mathcal{X}$ and $p\geq 1$ let

In the following, for ease of reading, we use a stronger condition than that in (7.5), namely,

While Condition (7.5) is known in the literature as variance reduction, the stronger formulation (7.6) is called uniform bounded variance. Assumption (7.5) is more realistic in those cases where the feasible set $\mathcal{X}$ is unbounded, and it is always satisfied when the mapping $f$ is Carathéodory and random Lipschitz continuous [54, Example 1]. Since in many realistic examples the feasible set is bounded, we use (7.6) as a variance control assumption. We also remark that many of the following results hold also in the more general case given by Assumption 7.2 and using the $L_{p}$ norm for any $p\geq 2$. We refer to and references therein for a more detailed insight on this general case.

When we use the SA scheme with variance reduction, the following relation between the stochastic error and the batch size sequence holds (see Lemma A.51): for all $k\geq 0$, $c>0$, $\sigma$ as in (7.6) and $\mathcal{N}_{k}$ as in (7.4),

Essentially, Lemma A.51 says that the second moment of the error decreases with the increasing number of samples of the random variable. Sometimes more general results hold for the bound in (7.7) (see, e.g., ) but they lie outside the scopes of the survey.

We are now ready to describe how the lemmas are used. The first applications that we present are all related to Robbins–Siegmund Lemma (Lemma 4.23). We differentiate the applications on how the negative term $-\theta_{k}$ is exploited (Remark 4.1). Nonetheless, in all of them, the summability of the term is used differently to obtain convergence. For the first application we also provide a scheme (inspired by Figure 7) of the step that should be taken to use a lemma for sequences of random numbers (Figure 8). The section ends with an application of Lemma 4.29. As the reader may note, the forthcoming applications rely on the existence of a martingale, associated to the process, that the lemmas prove to be convergent .

In , the residual ($r_{\alpha}(x)$) is used to prove convergence (see Appendix A for a definition and Remark A.1). Specifically, in , the authors formulate a stochastic forward-backward-forward algorithm, inspired by , given by the following updating rule:

where $\xi_{n}$ and $\eta^{k}$ are i.i.d. random variables and $F^{\textup{VR}}$ is as in (7.3).

The use of the residual to prove convergence to the solution of the SVI in (7.1) was previously introduced in where the authors propose a stochastic extragradient method inspired by . The iterations are given by

Application of Lemma 4.23 with strict monotonicity

Robbins–Siegmund Lemma can also be used to prove the convergence of the partially coordinated iterative proximal point scheme to a Nash equilibrium . The possibility to reach a Nash equilibrium in a game theoretic framework is related to the fact that they can be obtained as the solution of a suitable (S)VI [13, Proposition 1.4.2]. The updating rule of the algorithm is given by:

$\lim_{k\rightarrow\infty}\frac{\alpha_{k,\max}^{2}\mu_{k,\min}^{2}}{\alpha_{k,\min}\mu_{k,\min}}=c$ with $c\in\left[0,\frac{1}{2}\right)$;

$\sum_{k=0}^{\infty}\alpha_{k,i}=\infty\text{ and }\sum_{k=0}^{\infty}\alpha_{k,i}^{2}<\infty$ for all $i\leq n$;

$\sum_{k=0}^{\infty}\left(\alpha_{k,\max}-\alpha_{k,\min}\right)<\infty$;

Using the nonexpansiveness of the projection and some norm properties, one can obtain

2 Applications of Robbins-Siegmund Lemma to specific problems

An interesting application of Robbins-Siegmund Lemma is provided in , where the authors propose the gossip-based random projections (GRP) algorithm for distributed robust model predictive control (MPC). In their problem, $m$ private facilities aim at finding an optimal control law $u=\operatorname{col}(u(1),\dots,u(T))$ of a dynamic system such that the resulting trajectory $x(t)$, for $t=1,\dots,T$, remains close to the locally known facilities and the terminal state $x(T)$ is inside some uncertain box with minimum control effort. Formally, the distributed MPC optimization problem is given by

where $u\in\mathcal{X}$ represent the uncertain input constraint and the last inequality describe the random terminal constraint ($\mathcal{T}$ from now on). We refer to for a specific choice of $f$, $A$ and $B$. The algorithm is based on random projections and a gossip communication protocol inspired by . At each time $k$, only an agent $I_{k}\in\mathcal{I}$ and its neighbor $J_{k}\in\mathcal{I}$ wake up. They draw a sample of one of the linear inequality terminal constraints and they update their estimate while the other agents do nothing. Then, they project their current iterate on the selected constraint $\mathcal{T}$ and on $\mathcal{X}$. The GRP algorithm reads, for $i\in\{I_{k},J_{k}\}$, as

Application of Corollary 4.26 to the Law of Large Numbers

Remarkably, the convergence results for sequences can be used also for others scopes beside convergence of an algorithm. This is the case of Corollary 4.26 which is used to prove the Law of Large Numbers. To introduce this application, let us define the notion of increasing process associated to a martingale .

To apply Corollary 4.26, let $v_{k}=y_{k}^{2}$, $\varepsilon_{k}=\langle y\rangle_{k+1}-\langle y\rangle_{k}$ and $a_{k}=\langle y\rangle_{k+1}(\operatorname{ln}(\langle y\rangle_{k+1}))^{1+\gamma}$. Then, if $\langle y\rangle_{k_{0}}>1$, $\sum_{k=k_{0}}^{\infty}a_{k}^{-1}\varepsilon_{k}<\infty$, $\lim_{k\to\infty}a_{k}^{-1}v_{k}=0$ and the claim follows. ∎

3 Applications of Lemma 4.29

In , a smoothing extragradient scheme with stochastic approximation, similar to (7.10), is proposed. The iterations read as

Using the assumptions, from [10, Lemma 4] the following inequality holds:

where $q$ is a constant that depends on the constant $C$ and on the variance of the stochastic error and $M$ is the bound on the set $\mathcal{X}$. Then, convergence follows applying Lemma 4.29 to $v^{k}=\left\|x^{k}-x^{*}\right\|^{2}$, $\epsilon^{k}=q\gamma_{k}^{2}$ and $\delta^{k}=\frac{\alpha\gamma_{k}}{M}$. ∎

Application of Lemma 4.29 to opinion dynamics

The fact the Lemma 4.29 provides convergence to zero is used in to prove agreement in an opinion dynamics model. Let us consider the spreading of true or false information over a communication network or faults propagations in large scale control systems. In these models, there are $n$ nodes and each of them (node $i$) activates with a probability $1/n$, then it picks a neighbor $j$ with probability $a_{ij}$. The probabilities are collected in the interaction matrix $A=[a_{ij}]_{i,j=1}^{n}$. The dynamics is described as follows, given $\alpha+\beta+\gamma=1$:

(Attraction) With probability $\alpha$, node $i$ updates its opinion toward that of its neighbor $j$,

where $0<T_{k}\leq 1$ is the trust level;

(Neglect) With probability $\beta$, node $i$ keeps its own opinion,

(Repulsion) With probability $\gamma$, node $i$ moves away from $j$, i.e., it updates with a negative coefficient,

The authors propose in some conditions on the quantities involved under which agreement or disagreement can be obtained with a time-invariant trust level. As a measure of disagreement, let $L^{k}=\sum_{i=1}^{n}\left\|x_{i}^{k}-x_{\text{ave}}\right\|^{2}$, where $x_{\text{ave }}=\sum_{i=1}^{n}\frac{x_{i}^{0}}{n}$ is the average of the initial values. Then, the following result holds.

[16, Theorem 5] Let the communication graph be weakly connected and suppose that the updates are symmetric. Let $\lambda_{2}^{*}$ be the second smallest eigenvalue of $D-(A+A^{\top})$ with $D=\operatorname{diag}\left(d_{1}\ldots d_{n}\right),d_{i}=\sum_{j=1}^{n}\left(a_{ij}+a_{ji}\right)$. Let $T_{k}\equiv T^{*}\in$ and $S_{k}\equiv S^{*}>0$. Then

Given some preliminary results [16, Proposition 3], it holds that

4 Other applications

Other applications of Robbins-Siegmund Lemma (Lemma 4.23) can be found in for variational problems and monotone inclusions. Concerning Nash equilibrium problems, it is used in . In the specific case of generative adversarial networks, Lemma 4.23 is used in . For an application of this stochastic result to a deterministic problem, we refer to . Regarding dynamic systems and Lyapunov analysis, other utilizations of Robbins-Siegmund Lemma are in [3, Section 3], [98, Section I.1] and . For other applications of Lemma 4.29 instead, the interested reader may refer to .

Application of convergent sequences with variable metric

The variable metric framework is not studied as much as the classic setup. Therefore, we propose only the following application. For other references see .

A study of the forward-backward-forward algorithm with variable metric is considered in . There, the authors consider the splitting of a sum of a maximally monotone operator $A$ and a monotone, Lipschitz continuous operator $B$ of the form (6.5) and they suppose that multiple errors (sequences $a^{k}$, $b^{k}$ and $c^{k}$) can be made at each iteration. Formally, their proposed algorithm reads as

$\sum_{k=1}^{\infty}\|x^{k}-v^{k}\|^{2}<+\infty$,

After using some results from to guarantee that the sequences are well defined and that the monotonicity properties of the operators $W_{k}A$ and $W_{k}B$ hold, a quasi-Féjer inequality can be proven, i.e.,

Conclusion

In this survey, we tried to answer the question posed by Polyak in 1987. We show that the importance of convergence theorems for mathematical system theory lays on their connection to Lyapunov analysis and Féjer monotonicity and in the variety of areas and applications where they are used.

Thanks to the notions of (quasi) Féjer monotonicity and Lyapunov decrease, results showing the convergence of sequences of (random) real numbers can be exploited in Nash equilibrium problems, machine learning and optimization. In these contexts, these results are fundamental to analyze and design convergent learning processes.

Appendix A Auxiliary notions

In this section, we recall some notions from operator theory . Let us start with some notation.

Let us now provide the definition of projection, proximal operator and resolvent which are used in many algorithms.

The projection operator onto $\mathcal{C}$ is the operator defined as

The point $\operatorname{proj}_{\mathcal{C}}(x)$ is the closest point to x in $\mathcal{C}$. It always exists and it is unique.

where $\operatorname{Id}$ is the identity function.

The notions discussed until now are related by the following example.

where $\operatorname{N}_{\mathcal{C}}$ is the normal cone of $\mathcal{C}$.

A.2 Operator Theory

The convergence properties of the algorithms proposed for VIs or monotone inclusions are strictly related to the properties of the operators, to its monotonicity in particular. For this reason, here we recall some definition that are useful for the applications.

pseudomonotone on $\mathcal{X}$ if $\langle F(y),x-y\rangle\geq 0\Rightarrow\langle F(x),x-y\rangle\geq 0\text{ for all }x,y\in\mathcal{X};$

monotone on $\mathcal{X}$ if $\langle F(x)-F(y),x-y\rangle\geq 0,\text{ for all }x,y\in\mathcal{X};$

strictly monotone on $\mathcal{X}$ if $\langle F(x)-F(y),x-y\rangle>0,\text{ for all }x,y\in\mathcal{X}\text{ and }x\neq y;$

$\mu$-strongly monotone on $\mathcal{X}$ if there exists a constant $\mu>0$ such that $\langle F(x)-F(y),x-y\rangle\geq\mu\|x-y\|^{2},\text{ for all }x,y\in\mathcal{X};$

The weakest assumption is pseudomonotonicity while strong monotonicity implies all the other notions. Strictly monotone operators are widely used in variational inequalities problems since this is the weaker assumption that guarantees uniqueness of the solution [13, Theorem 2.3.3]. It implies monotonicity that, in turn, implies pseudomonotonicity.

Many results are also related to the Lipschitz and cocoercivity constants of the operator.

nonexpansive if it is $1$-Lipschitz continuous, i.e., $\|F(x)-F(y)\|\leq\|x-y\|$ for all $x,y\in\mathcal{X}$;

$\beta$-cocoercive on $\mathcal{X}$ if there exists a constant $\beta>0$ such that $\langle F(x)-F(y),x-y\rangle\geq\beta\left\|F(x)-F(y)\right\|^{2},$ for all $x,y\in\mathcal{X}.$

It follows (using Cauchy-Schwartz inequality) that if a map is $\beta$-cocoercive, it is also $1/\beta$-Lipschitz continuous. Moreover, cocoercivity implies monotonicity.

Sometimes, in the stochastic case, we mention that the map is Carathéodory.

A.3 Auxiliary results

Let us recall some results on martingales as this property for $L_{p}$ norms, known as Burkholder-Davis-Gundy inequality .

When combined with the Burkholder-Davis-Gundy inequality, it leads to the fact that for all $p\geq 2$, there exists a constant $c_{p}>0$ such that, for every $k\geq 1$,

The following result is presented for uniformly bounded variance but holds also for more general assumptions. For similar results, one can refer to .

Let $c>0$. Let $\sigma$ be as in Equation (7.6) and $\mathcal{N}_{k}$ as in Standing Assumption 7.1. Then, it holds a.s. that

then the claim follows immediately. To this aim, let us first notice that $F^{\textup{VR}}(x,\xi)=\frac{1}{\mathcal{N}}\sum_{k=1}^{\mathcal{N}}F^{\textup{SA}}(x,\xi^{k})$. Then, let us define the process $\{M_{S}^{S}(x)\}_{i=0}^{S}$ as $M_{0}(x)=0$ and for $1\leq i\leq S$

Let $\mathcal{F}_{i}=\sigma(\xi_{1},\dots,\xi_{i})$. Then $\{M_{i}^{S}(x),\mathcal{F}_{i}\}_{i=1}^{S}$ is a martingale starting at . Let

We note that $M_{S}^{S}(x^{k})=\epsilon^{k}$, hence by taking the square we conclude that

References

References