Analysis of nonsmooth stochastic approximation: the differential inclusion approach

Introduction

Stochastic approximation algorithms are stochastic processes defined iteratively as

A powerful method to analyze stochastic gradient algorithm, introduced in the early works by and is the ordinary differential equation (ODE) method. The ODE method has led to an enormous literature; see for example , and the references therein. The ODE method can be informally summarized as follows: first we rewrite

The classical stochastic approximation algorithm update rule is replaced by a stochastic recursive inclusion:

where $F$ is a point-to-set map and $\eta_{k}$ is defined in (1). Such algorithms play an important role in game theory, as illustrated in where numerous examples of stochastic recursive inclusions are introduced.

have shown that the ”mean-limit” approach leading to the ODE method in the smooth case can be extended to the analysis of stochastic recursive inclusion. In this case, the limit ODE is replaced by a solution of the differential inclusion

In this paper, we will also consider proximal algorithms, which have become an important tool in nonsmooth optimization problems; the literature in this field is also huge, see for example ). Proximal algorithms with stochastic updates have been proposed and studied in recent years. One such algorithm is Proximal Stochastic Gradient Descent (proxSGD), that optimizes composite convex function $P=f+g$ where $f$ is a continuously differentiable function with Lipschitz-gradients and $g$ is a ”proximable” function (e.g. $g$ is lower semi-continuous and convex, but this notion can be extended to nonconvex functions). The proxSGD algorithm alternates between stochastic gradient update for $f$ and deterministic proximal step for $g$. This above optimization problem plays a fundamental role in many machine learning problems, ranging from convex optimization such as convex regression problem with sparsity inducing penalties like LASSO to highly nonconvex problem such as optimizing the weights of deep neural networks. Numerous papers have been devoted to the case when $f$ and $g$ are both convex, $f$ gradient Lipschitz and $g$ lower semi-continuous; see for example . Atchade et al. have extended these results in the Markovian noise case. In recent years, triggered by the surge deep learning, the nonconvex case has started to attract many research efforts, at least in the smooth case ($f$ gradient Lipschitz and $g\equiv 0$); see for example and the references therein. For the nonsmooth and nonconvex case, the results are still partial. Ghadimi et al. considered the case where $f$ is differentiable but possibly nonconvex and $g$ is non-differentiable but convex. They have analyzed the deterministic proximal gradient algorithm (where the full gradient is computed at each iteration). They have also extended their results to the stochastic case; Reddi et al. provides rates of convergence.

We consider in this paper nonconvex and nonsmooth minimization problems. We establish the convergence of stochastic inclusion equation generalizing (1) by allowing implicit steps and projections on a closed compact convex set at each iteration. Our results generalize . We also discuss the stability of the limit differential inclusion by means of locally Lipschitz continuous and regular Lyapunov functions (see Definition Definition). We in particular establish a characterization of the possible limit point of the stochastic approximation algorithm as the set of zeros of an upper-bound of the set-valued Lie derivative (see Definition Definition) of the Lyapunov function. We then apply our results to the analysis of the proximal stochastic gradient descent for the composite minimization problem $P=f+g$, under assumptions on the noise sequence analogous to those commonly used for the SGD in the smooth nonconvex case. We also show that $V=f+g$ can play the role of a Lyapunov function. We finally analyse a projected version of stochastic subgradient algorithm.

The paper is organized as follows. In Section 2, we introduce our main assumptions and notations and introduce the proximal stochastic gradient and projected subgradient algorithms. In Section 3, we state and prove our main convergence results under the assumption that the iterates are stable. In Section 4, we extend these convergence results to the case where the updates are projected on a compact convex set. In Section 5, we consider applications of our main results to ProxSGD and projected stochastic subgradient. Finally in Section 6 we present postponed proofs.

Assumptions and Notations

In this section we introduce definitions and notations.

By convention for a convex closed set $K$ and a given set $A$, by $\Pi_{K}(A)$ we denote the projection of $A$ onto $K$, defined as $\Pi_{K}(A)=\{\Pi_{K}(a)\;,a\in A\}$.

The condition $x_{k}\in\Pi_{K}\left(x_{k-1}+\gamma_{k}(F(y_{k})+\eta_{k})\right)$ is satisfied if and only if there exists $v_{k}\in F(y_{k})$ such that

[11, Definition III] deal with sequence satisfying a recursion of the form

We now show that the PAD and $K$-PPAD formalism cover the proximal stochastic gradient descent (ProxSGD) and the stochastic (sub)gradient algorithms for nonsmooth and nonconvex minimization problems. First we introduce some additional definitions and notations.

Similarly to subgradient, the Clarke generalized gradient is a set-valued generalization of the gradient. In particular, when function $f$ is continuously differentiable at some point $x_{0}$, then we have $\overline{\partial}f(x_{0})=\{\nabla f(x_{0})\}$. Furthermore, if the function $f$ is convex and locally Lipschitz and $x_{0}$ belongs to the interior of its domain, then the Clarke generalized gradient of $f$ coincides with the subgradient.

It is shown in [16, Propositions 2.1.2] that if $f$ is Lipschitz on a neighborhood of $x_{0}$ with Lipschitz constant $\|f\|_{\operatorname{Lip},x_{0}}$ then $\overline{\partial}f(x_{0})$ is a non-empty set, compact, convex, and for any $u\in\bar{\partial}f(x_{0})$, $\left\|u\right\|\leq\|f\|_{\operatorname{Lip},x_{0}}$. By [16, Proposition 2.1.5], $\bar{\partial}f$ is upper hemicontinuous at $x_{0}$. For any compact set $K\subset\mathsf{X}$, $\sup_{x\in K}\|f\|_{\operatorname{Lip},x}<\infty$ showing that $\bar{\partial}f$ is locally bounded. For proofs of those results and additional properties of Clarke generalized gradient, we refer the reader to .

where $f^{0}$ is the generalized directional derivatives (see Definition Definition). \proofbox

It may happen that the usual directional derivative exists, but does not coincide with the generalized directional derivative. The classical example is $f(x)=-|x|$. As shown in [16, Proposition 2.3.6] every convex locally Lipschitz function is regular. The same property obviously holds for any continuously differentiable function. Note finally that if the functions $f_{1},\dots,f_{p}$ are regular at $x_{0}$, then for any nonnegative weights $\alpha_{1},\dots,\alpha_{p}$, $\sum_{i=1}^{p}\alpha_{i}f_{i}$ is also regular at $x_{0}$, see [16, Proposition 2.3.6]. \proofbox

Now we are ready to discuss the proximal gradient descent and projected subgradient algorithms.

The characterization of the minimum by the Clarke generalized gradient (see [16, Proposition 2.3.2]) yields

We will analyse the convergence of PAD (see (3)) under the following assumptions:

Condition (A(A1)) is a rather mild regularity condition. Upper hemicontinuity replaces the continuity of the vector field which plays a key role in the classical theory of stochastic approximation . The requirement for $F$ to be convex-compact valued and locally bounded might be less obvious, but this assumption is commonly used in nonsmooth analysis. This is not a serious limitation for the minimization problems we have primarily in mind.

The assumptions (A(A2), A(A3)) are usual in stochastic approximation literature . It is worth noting, that condition (A(A3)) allows perturbations sequences which have random and deterministic components and hence our results can be used for proving almost sure convergence for ProxSGD for which the proximal operator is computed numerically and is therefore inexact (although in our framework the deterministic noise should vanish asymptotically faster than step size). The assumptions (A(A4)) allows to cover both explicit and implicit discretization of differential inclusions as illustrated in Example Example.

Convergence of Perturbed Approximate Discretisation

In this section, we state our main convergence results for PAD. First in Theorem Theorem we show that a translated and interpolated version of the PAD converges to a solution of a differential inclusion. Further in Theorem Theorem we combine these results with Lyapunov stability conditions to obtain convergence of the iterates to the set of stationary points of the differential inclusion.

Without loss of generality we can assume that $\sum_{k=1}^{\infty}\gamma_{k}e_{k}=0$ (if this is not true, we can just modify $r_{1}$ and $e_{1}$).

Therefore for $n\geq N^{\prime}$ we have $a_{n}^{t}\leq 3\epsilon$. Since $\epsilon$ was arbitrary positive number, we get that $\lim_{n\rightarrow\infty}a_{n}^{t}=0$. T Hence, for all $\epsilon>0$, there exists $N^{\prime\prime}>0$ such that

where $t_{n}$ is defined in (8). By assumption (A(A2)) $m(k,t)$ is well defined and converges to $\infty$ as $k\to\infty$.

Moreover, since $\lim_{k\rightarrow\infty}\gamma_{k}=0$ and $\lim_{k\rightarrow\infty}s_{k}=\infty$, by (15) we have

By assumption $s_{k}$ converges to $\infty$, so also $m(n_{k},t)$ goes to $\infty$ as $k\to\infty$. Therefore by assumption (A(A4)) the first part of the RHS of (18) converges to . By (16), the second term in the RHS of (18) is equal to

which goes to zero by uniform convergence of $X_{n_{k}}$ to $X_{\infty}$. Finally, continuity of $X_{\infty}$ implies that the last term of (18) also converges to . All together we have therefore established that

The limit $X_{\infty}$ is a solution of differential inclusion $\dot{x}(t)\in F(x(t))$. \proofbox

Combining Theorem Theorem with stability properties of underlying differential inclusion $\dot{x}\in F(x)$ we establish convergence of PADs. To state the result we need to define a set valued Lie derivative, introduced in .

where $\bar{\partial}V$ is the Clarke generalized gradient of $V$, cf. Definition Definition. \proofbox

The Lie derivative plays important role in analysis of stability of solution of differential inclusions. We in particular will used an important property stated in [6, Lemma 1].

where $\mathcal{L}_{F}V$ is the set-valued Lie derivative of $V$ with respect to $F$, cf. Definition Definition. \proofbox

and set $\mathcal{S}:=\{x\in\mathsf{X}:U(x)=0\}$.

The set $K\cap\mathcal{S}$ is nonempty. \proofbox

If the $K\cap\mathcal{S}=\emptyset$ by upper semicontinuity of $U(x)$ and compactness of $K$ we would have $\sup_{x\in K}U(x)=-\delta$ for some $\delta>0$. Therefore function $V\circ X$ must decrease at a rate at least $\delta$, and thus $\lim_{t\rightarrow\infty}V(X(t))=-\infty$. But this is a contradiction with the assumption that $V$ is bounded from below. \proofbox

Since $V$ is continuous and $K$ is compact,

and hence $X_{\infty}(t)\in\operatorname{B}(x_{*},r)$. By upper semicontinuity of $U$ and compactness of $\overline{\operatorname{B}}(x_{*},r)$ we get that there exists $\delta>0$ such that $\sup_{x\in\overline{B}(x_{*},r)}U(x)=-\delta$, and, using Lemma Lemma, we conclude that for almost every $t\in[0,\Delta t]$, $\frac{d}{dt}V(X_{\infty}(t))\leq-\delta$. This means, that

Convergence of Projected Perturbed Approximate Discretisation

As in the proof of Theorem Theorem, we assume $\sum_{k=1}^{\infty}\gamma_{k}e_{k}=0$. We denote by

and we define the functions for any $t\geq 0$

we get that $\sup_{k}\left\|p_{k}\right\|<\infty$. Next, since

and for every $s\geq 0$, $\left\|\hat{p}(s)\right\|\leq\sup_{k}\left\|p_{k}\right\|$ we get $\left\|\hat{P}_{k}(t)\right\|\leq\sup_{k}\left\|p_{k}\right\|t$.

Any limit $X_{\infty}$ of converging subsequence is a solution of the projected differential inclusion $\dot{x}\in\Pi_{{\operatorname{T}_{K}}(x)}(F(x))$. \proofbox

We use the following characterization of the solution of projected differential inclusion $\dot{x}\in\Pi_{{\operatorname{T}_{K}}(x)}(F(x))$ given in [5, Chapter 5, Section 6, Propositions 1 and 2]:

For all $t\geq 0$ we have $X_{\infty}(t)\in K$.

For almost every $t\geq 0$ there exists $w(X_{\infty}(t))\in F(X_{\infty}(t))$ such that,

Let $t\in[a,b]$ be such, that $\lim_{k\to\infty}(G^{w}_{n_{k}}(t),Q^{w}_{n_{k}}(t))=(G(t),Q(t))$. Since $Q_{n_{k}}(t)=p_{m(n_{k},t)}$, where $m(n_{k},t)$ is defined in (15), $Q(t)=\lim_{k\to\infty}p^{w}_{m(n_{k},t)}$.

we get $G^{w}_{n_{k}}(t)-Q^{w}_{n_{k}}(t)=v^{w}_{m(n_{k},t)}+r^{w}_{m(n_{k},t)}$.

and set $\mathcal{S}:=\{x\in\mathsf{X}:U(x)=0\}$.

The proof is along the same lines as the proof of Theorem Theorem. \proofbox

Applications

In this section we apply the result from previous sections to projected ProxSGDand projected subgradient descent algorithm.

Stochastic proximal gradient is a natural extension of Proximal Gradient algorithm to the case where the gradient cannot be computed exactly and is therefore affected by some errors. More specifically, we want to optimize a composite function of form

We consider two versions of the projected ProxSGD algorithm which are given by

Those two approaches to projection are not equivalent, and depending on $g$ and $K$ one might be easier to compute than the other. Consider the following assumptions:

To illustrate our derivations, we consider now two possible choices of sparsity inducing penalties $g$.

where $S(z,\lambda)=\operatorname{sign}(z)(|z|-\lambda)_{+}$ is the soft thresholding operator (here $(x)_{+}=x\vee 0$ is the positive part of $x$). The proximal operator for $g$ is given by (see [33, Section 2.1])

The SCAD penalty () can be handled along the same lines (the expression for the proximal function can be found in [14, Section 2]). \proofbox

We denote by $F$ the set-valued map $-\nabla f-\bar{\partial}g$. The Clarke gradient of a locally Lipschitz function is convex-compact valued and locally bounded (see [16, Proposition 2.1.2]) and is upper hemi-continuous (see [16, Proposition 2.1.5]. Since $\nabla f$ is continuous, this implies that $F$ satisfies (A(A1)). By [16, Corollary 2.3.2], $\overline{\partial}(-f-g)=-\nabla f-\overline{\partial}g$.

With this notation (31) can be written as

By [16, corollary of Proposition 2.4.3, p. 52], $0\in\gamma_{k}^{-1}(x_{k}-w_{k})+\bar{\partial}g(x_{k})+{\operatorname{N}_{K}}(x_{k})$. Therefore there exists

The normal cone to $K$ at $x_{k}$ consists of vectors $v_{c}$, such that for all $z\in K$ we have $\langle v_{c},x_{k}-z\rangle\geq 0$. Since $\gamma_{k}{\operatorname{N}_{K}}(x_{k})={\operatorname{N}_{K}}(x_{k})$ and using (34), (36) implies that for all $z\in K$,

where $u_{k}$ is defined in (35). Setting $v_{k}=-\nabla f(x_{k})-u_{k}\in F(x_{k})$ and $\eta_{k}=-\delta_{k}+(\nabla f(x_{k})-\nabla f(x_{k-1}))$ we get

it is enough to show that $\lim_{k\rightarrow\infty}\left\|\nabla f(x_{k-1})-\nabla f(x_{k})\right\|=0$. Plugging $z=x_{k-1}$ into (37), we get that:

and using the Cauchy-Schwartz and triangle inequalities and (34), we obtain

Denoting by $v_{k}=-\nabla f(y_{k})-u_{k}$ and by $\eta_{k}=-\delta_{k}-\nabla f(x_{k-1})+\nabla f(y_{k})$ we get that

We now chack (A(A3)). The perturbation $\eta_{k}$ may be decomposed as $\eta_{k}=e_{k}+r_{k}$ where $e_{k}=-e_{k}^{\delta}$ and $r_{k}=-r_{k}^{\delta}+\nabla f(y_{k})-\nabla f(x_{k-1})$. Since $\nabla f$ is continuous, Assumption (A(A3)) is satisfied if

Note that, since $g$ is Lipschitz, [16, Proposition 2.1.2-(a)] shows that for all $u\in\bar{\partial}{g}(y)$, $\left\|u\right\|\leq\|g\|_{\operatorname{Lip}}<\infty$. Boundedness of $\nabla f$ on the set $K$ and assumptions (P(P2)) and (P(P3)) implies that

Because $x_{k}$ is a projection of $y_{k}$ on the set $K$ we have

showing that (A(A4)) is satisfied. \proofbox

Applying our results from Section 4, we now show that both versions of the projected proximal gradient algorithms converge.

To apply Theorem Theorem, we show that $V=f+g$ is a Lyapunov function for $F_{K}(x):=\Pi_{\operatorname{T}_{K}(x)}(F(x))$, $x\in\mathsf{X}$. Under the stated assumptions, $V$ is locally Lipschitz regular and by [16, Corollary 2 of Proposition 2.3.3]

We now compute the Lie derivative of $V$ with respect to the field $F_{K}$ see Definition Definition). Let $x\in K$ . Suppose that there exists $a\in\mathcal{L}_{F_{K}}V(x)$. Then there exists $v\in\Pi_{{\operatorname{T}_{K}}(x)}(F(x))$, such that for all $w\in\bar{\partial}V(x)$, ${\langle v,w\rangle}=a$. Let $u\in F(x)$ be such that $\Pi_{{\operatorname{T}_{K}}(x)}(u)=v$. Note that $-u\in\bar{\partial}V(x)$, which implies ${\langle\Pi_{{\operatorname{T}_{K}}(x)}(u),-u\rangle}=a$ and

Applying [5, Proposition 0.6.2], we get that ${\langle\Pi_{{\operatorname{T}_{K}}(x)}(u),\Pi_{{\operatorname{T}_{K}}(x)}(u)-u\rangle}=0$. Therefore, if $a\in\mathcal{L}_{F_{K}}V(x)$, then $a=-\left\|\Pi_{{\operatorname{T}_{K}}(x)}(u)\right\|^{2}$ for some $u\in F(x)$. Hence, for any $x\in K$, $\mathcal{L}_{F_{K}}V(x)$ is either empty, or contains only non-positive elements.

For any $x\in\mathsf{X}$, [16, Proposition 2.1.2] shows that $F(x)$ is non-empty, convex and compact. Define $U$ for any $x\in K$ as follows

By [5, Proposition 0.6.4] we get for any $x\in K$,

Under (A(A1)), $F$ is upper hemicontinuous compact-convex valued. On the other hand, by [5, Chapter 5, Section 1, Theorem 1], ${\operatorname{N}_{K}}$ has closed graph. Hence, the map $F-N_{K}$ has closed graph by [5, Proposition 1.1.2, p. 41]. By Lemma Lemma the function $U$ is upper semicontinuous. Thus we have an upper semicontinuous function $U$, such that for all $x\in K$:

2 Online proximal stochastic gradient descent algorithm

In the online learning case, the gradient $\nabla f$ of the function $f$ cannot be computed but that a noisy version of the gradient is available To make the discussion simple, we assume that

We are considering the two following stochastic approximation procedures

3 Monte Carlo Proximal stochastic gradient descent algorithm

In this section, we still consider the composite minimization problem (42). We assume that $f$ is continuously differentiable and that for all $x\in K$ $\nabla f(x)$ satisfies

When sampling directly $\pi_{x}$ is doable, then an obvious choice is to use a naive Monte Carlo estimator which amounts to sample a batch $\{z_{k}^{(j)},1\leq j\leq m\}$ independently of the past values of the parameters $\{x_{j},j\leq k-1\}$ and of the past draws i.e. independently of the $\sigma$-algebra

Conditionally to $\mathcal{F}_{k-1}$, $Y_{k}$ is an unbiased estimator of $\nabla f(x_{k-1})$.

When direct sampling from $\pi_{x}$ is not an option, we may still construct a Markov kernel $P_{x}$ with invariant distribution $\pi_{x}$. Monte Carlo Markov Chains (MCMC) provide a set of principled tools to sample from complex distributions over large dimensional spaces. In such case, conditional to the past, $\{z_{k}^{(j)},1\leq j\leq m\}$ is a realization of a Markov chain with transition kernel $M_{x_{k-1}}$ and started from $z_{k-1}^{(m)}$ (the last sample draws in the previous minibatch).

We refer the reader to for the definitions and basic properties of Markov chains.

In this section, we assume that $Y_{k}$ is a Monte Carlo approximation of the expectation $\nabla f(x_{k-1})$ :

for all $k\geq 1$, conditionally to the past, $\{z_{k}^{(j)},1\leq j\leq m\}$ is a Markov chain started from $z_{k-1}^{(m)}$ and with transition kernel $M_{x_{k-1}}$ (we set $z_{0}^{(m)}=x_{\star}\in\mathsf{X}$), where for all $x\in\mathsf{X}$, $M_{x}$ is a Markov kernel with invariant distribution $\pi_{x}$.

From a mathematical standpoint, the Markovian setting is trickier than the fixed batch size, because $Y_{k}$ is no longer an unbiased estimator of $\nabla f(x_{k-1})$, i.e. the bias $B_{k}$ defined by

There exists $\lambda\in\left[0,1\right)$, $b<\infty$ and a measurable function $W\colon\mathsf{Z}\to[1,+\infty)$ such that

Sufficient conditions for the uniform-in-$x$ ergodic behavior are given e.g. in [22, Lemma 2.3], in terms of aperiodicity, irreducibility and minorization conditions on the kernels $\left\{M_{x}\,:\;x\in\mathsf{X}\right\}$. Examples of MCMC kernels $M_{x}$ satisfying this assumption can be found in [2, Proposition 12], [38, Proposition 15].

The kernels $M_{x}$ and the stationary distributions $\pi_{x}$ are locally Lipschitz with respect to $x$, i.e. for any compact set $K$ and any $x,x^{\prime}\in K$ there exists $C<\infty$ such that

The proof follows along the same lines as [30, Proof of Lemma 27]. However for completeness we give a detailed proof in Appendix A. \proofbox

4 Projected stochastic subgradient descent algorithm

The convergence of stochastic subgradient algorithm for regular functions $f$ can be easily deduced from Section 3. Here, we show that projected stochastic subgradient descent algorithm also fits into our framework and its convergence can be established based on the results of Section 4.

Applying our results from Section 4, we now show that projected stochastic subgradient algorithms converge.

The proof follows along the sime lines as proof of Theorem Theorem. \proofbox

Note, that adaptation of results from Section 5.2 and Section 5.3 to the case of projected stochastic subgradient descent algorithm is straightforward.

Proofs

In this section we introduce some notations and preliminary facts used in the proofs of results from Section 3 and Section 4, as well as some auxiliary definitions and theorems.

which means that $W$ is upper semicontinuous. \proofbox

By [16, Proposition 2.3.6] a finite linear combination (by nonnegative scalars) of functions regular at $x^{0}$ is regular at $x^{0}$. The proof then follows by noting that, for any $i\in\{1,\dots,d\}$, the function $p^{i}(x_{1},\dots,x_{d})=p_{i}(x_{i})$ is regular at $x^{0}$. \proofbox

Let $\partial_{D}f(x)$ be the D-subdifferential of $f$ at $x$ (see [17, chapter 3.4, subsection D-differential] for definition). Then according to [17, Proposition 4.10] , the inequality (51) is satisfied for $v$ if and only if $v\in\partial_{D}f(x)$. On the other hand, [17, Proposition 4.8, part (b)] implies that for a locally Lipschitz function we have $\bar{\partial}f(x)=\partial_{D}f(x)$ if and only if $f$ is regular. Combined, these two facts conclude the proof. \proofbox

References

Appendix A Proof of Proposition Proposition

Since $x_{k}$ is projection of $y_{k}$ on set $K$, by the triangle inequality we get

Note that, since $g$ is Lipschitz, [16, Proposition 2.1.2-(a)] shows that for all $u\in\bar{\partial}{g}(y)$, $\left\|u\right\|\leq\|g\|_{\operatorname{Lip}}<\infty$. Boundedness of $\nabla f$ on the set $K$ and assumption (B(B2)) concludes the proof. \proofbox

In this proof, $C$ is a constant whose value may change upon each appearance. Observe that it is enough to show $\sum_{k=1}^{\infty}\gamma_{k}\delta_{k}<\infty$ almost surely, where by construction

Geometric ergodicity (B(B1)) in turn implies the existence of a solution of the Poisson equation, and also provide bounds on the growth of this solution; see [3, Lemma 13]. For $z\in\mathsf{Z}$, we set $\Phi_{x}(z)=\Phi(x,z)$. For any $x\in K$ there exists a solution $\hat{\Phi}_{x}$ to the Poisson equation

and there exists a constant $C<\infty$ such that for any $x\in K$ and $z\in\mathsf{Z}$

Therefore, since $\sum_{k=1}^{\infty}\gamma_{k}^{2}<\infty$ we conclude that $\sum_{k}\gamma_{k}\delta M_{k}$ converges almost surely.

Decompose $\sum_{l=n}^{k}\gamma_{l}\kappa_{l}=R_{n,k}^{1}+R_{n,k}^{2}+R_{n,k}^{3}$ with

Finally, from (52), (P(P2)) and $\sum_{k}|\gamma_{k}-\gamma_{k-1}|<\infty$ we deduce that $R_{n,k}^{2}$ and $R_{n,k}^{3}$ also converges to zero almost surely and that completes the proof. \proofbox