L p and almost sure rates of convergence of averaged
stochastic gradient algorithms: locally strongly convex

arXiv:1609.05479v2 [] 4 Jul 2017

objective
Antoine Godichon-Baggioni
Institut de Mathématiques de Toulouse,
Université Paul Sabatier, Toulouse, France
email: godichon@insa-toulouse.fr
July 5, 2017

Abstract
An usual problem in statistics consists in estimating the minimizer of a convex function. When we have to deal with large samples taking values in high dimensional
spaces, stochastic gradient algorithms and their averaged versions are efficient candidates. Indeed, (1) they do not need too much computational efforts, (2) they do not
need to store all the data, which is crucial when we deal with big data, (3) they allow to
simply update the estimates, which is important when data arrive sequentially. The aim
of this work is to give asymptotic and non asymptotic rates of convergence of stochastic
gradient estimates as well as of their averaged versions when the function we would
like to minimize is only locally strongly convex.

Keywords: Stochastic optimization; Stochastic gradient algorithm; averaging; Robust statistics

1

Introduction

With the development of automatic sensors, it is more and more important to think about
methods able to deal with large samples of observations taking values in high dimensional
spaces such as functional spaces. We focus here on an usual stochastic optimization problem which consists in estimating
m := arg min E [ g( X, h)] ,
h∈ H

(1)

where H is a Hilbert space and X is a random variable supposed to be taking value in a
space X and g : X × H −→ R. One usual method, given a sample X1 , ..., Xn , is to consider

the empirical problem generated by this sample, i.e to consider the M-estimates (see the

1

books of Huber and Ronchetti (2009) and Maronna et al. (2006) among others)
n

b n := arg min ∑ g ( Xk , h) ,
m
h∈ H

k=1

b n using deterministic optimization methods (see Boyd and Vandenberghe
and to approximate m

(2004) for instance). Nevertheless, one of the most important problem of such methods is
that they become computationally expensive when we deal with large samples taking val-

ues in high dimensional spaces. Thus, in order to overcome this, stochastic gradient algorithms introduced by Robbins and Monro (1951) are efficient candidates. Indeed, they do
not need too much computational efforts, do not require to store all the data and can be
simply updated, which represents a real interest when the data arrive sequentially.
The literature is very large on this domain (see the books of Duflo (1997), Kushner and Yin
(2003) among others) and on the method to improve their convergence which consists in averaging the Robbins-Monro estimates, which was introduced by Ruppert (1988) and whose
first convergence results were given by Polyak and Juditsky (1992). Many asymptotic results exist in the literature when data lies in finite dimensional spaces (see Duflo (1997),
Pelletier (1998), or Pelletier (2000) for instance) but the proofs can not be directly adapted
for infinite dimensional spaces. Moreover, an asymptotic result such as a Central Limit Theorem does not give any clue of how far the distribution of the estimate is from its asymptotic law for a fixed sample size n. Then, non asymptotic properties are always desirable
for statisticians who deal with real data (see the nice arguments of Rudelson (2014) for example). As a consequence, these last few years, statisticans have more and more focused
on non asymptotic rates of convergence. For example, Moulines and Bach (2011) and Bach
(2014) give some general conditions to get the rate of convergence in quadratic mean of
averaged stochastic gradient algorithms, while Ghadimi and Lan (2012), for instance, focus
on non asymptotic rates for strongly convex stochastic composite optimization.
The aim of this work is to seek inspiration in the demonstration methods introduced by
Cardot et al. (2017) and improved by Godichon-Baggioni (2016) and Cardot and Godichon-Baggioni
(2015) to give convergence results for stochastic gradient algorithms and their averaged versions when the function we would like to minimize is only locally strongly convex. First,
we establish almost sure rates of convergence of the estimates in general Hilbert spaces.
Furthermore, as mentioned above, asymptotic results are often non sufficient, and L p rates
of convergence of the algorithms are so given.
The paper is organized as follows. Section 2 introduces the framework, assumptions,
the algorithms and some convexity properties on the function we would like to minimize.
Two examples of application are given in Section 3: we first focus on the estimation of geometric quantiles, which are a generalization of the real quantiles introduced by Chaudhuri
(1996). They are robust indicators which can be useful in statistical depth and outliers detection (see Serfling (2006), Chen et al. (2009) or Hallin and Paindaveine (2006)). In a second time, stochastic gradient algorithms can be applied in several regressions (Bach (2014),

2

Cohen et al. (2016)) and we focus on robust logistic regression. In Section 4, the almost sure
and L p rates of convergence of the estimates are given. Finally, the proofs are postponed in
Section 5 and in Appendix.

2
2.1

The algorithms and assumptions
Assumptions and general framework

Let H be a separable Hilbert space such as R d or L2 ( I ) for some closed interval I ⊂ R. We
denote by h., .i its inner product and by k.k the associated norm. Let X be a random variable

taking values in a space X , and let G : H −→ R be the function we would like to minimize,
defined for all h ∈ H by

G (h) := E [ g( X, h)] ,

(2)

where g : X × H −→ R. Moreover, let us suppose that the functional G is convex. We
consider from now that the following assumptions are fulfilled:

(A1) The functional g is Frechet-differentiable for the second variable almost everywhere.
Moreover, G is differentiable and denoting by Φ(.) its gradient, there exists m ∈ H
such that

Φ(m) := ∇ G (m) = 0.
(A2) The functional G is twice continuously differentiable almost everywhere and for all
positive constant A, there is a positive constant C A such that for all h ∈ B (m, A),

kΓh kop ≤ C A ,
where Γh is the Hessian of the functional G at h and k.kop is the usual spectral norm
for linear operators.
(A3) There exists a positive constant ǫ such that for all h ∈ B (m, ǫ), there is a basis of
H composed of eigenvectors of Γh . Moreover, let us denote by λmin the limit inf of

the eigenvalues of Γm , then λmin is positive. Finally, for all h ∈ B (m, ǫ), and for all

eigenvalue λh of Γh , we have λh ≥

λmin
2

> 0.

(A4) There are positive constants ǫ, Cǫ such that for all h ∈ B (m, ǫ),

k∇ G (h) − Γm (h − m)k ≤ Cǫ kh − mk2 .
(A5) Let f : X × H −→ R + and let C be a positive constant such that for almost every
x ∈ X and for all h ∈ H, k∇h g( x, h)k ≤ f ( x, h) + C kh − mk almost surely.
(a) There is a positive constant L1 such that for all h ∈ H,


E f ( X, h)2 ≤ L1 .
3

(b) For all integer q, there is a positive constant Lq such that for all h ∈ H,


E f ( X, h)2q ≤ Lq .
Note that for the sake of simplicity, we often denote by the same way the different constants. We now make some comments on the assumptions. First, note that no convexity
assumption on the functional g is required.
Assumptions (A2) and (A3) give some properties on the spectrum of the Hessian and
ensure that the functional G is locally strongly convex. Note that assumption (A3) can be
resumed as λmin (Γm ) > 0, where λmin (.) is the function which gives the smallest eigenvalue
(or the lim inf of the eigenvalues in infinite dimensional spaces) of a linear operator, if the
functional h 7→ λmin (Γh ) is continuous on a neighborhood of m.
Moreover, assumption (A4) allows to bound the remainder term in the Taylor’s expansion of the gradient. Note that since the functional G is twice continuously differentiable
R1
and since Φ(m) = 0, it comes Φ(h) = 0 Γm+t(h−m) (h − m)dt, and in a particular case,

R1
Φ(h) − Γm (h − m) = 0 Γm+t(h−m)(h − m) − Γm (h − m) dt. Thus, assumption (A4) can
be verified by giving a neighborhood of m for each there is a positive constant Cǫ such for
all h in this neighborhood, if we consider the functional ϕh : [0, 1] −→ H defined for all
t ∈ [0, 1] by ϕh (t) := Γm+t(h − m) (h − m), then for all t ∈ [0, 1],
ϕ′h (t) ≤ Cǫ kh − mk2 .
Assumption (A5) enables us to bound the gradient under conditions on the functional f .
More precisely, (A5a) is sufficient to get the almost sure rates of convergence while we need
to assume (A5b) to obtain the L p rates of convergence. This still represents a significant
relaxation of the usual conditions needed to get non asymptotic results. For example, a
main difference with Bach (2014) is that, instead of having a bounded gradient, we split
this bound into two parts: one which admits q-th moments, and one which depends on the
estimation error. Moreover, note that it is possible to replace assumption (A5) by
(A5a’) There is a positive constant L1 such that for all h ∈ H,

i
h

E k∇h g ( X, h)k2 ≤ L1 1 + kh − mk2 .

(A5b’) For all integer q, there is a positive constant Lq such that for all h ∈ H,
i
h

E k∇h g ( X, h)k2q ≤ Lq 1 + kh − mk2q .

Remark 2.1. These assumptions are analogous to the usual ones in finite dimension (Pelletier
(1998), Pelletier (2000)) but in our case, the proofs remain true in infinite dimension.
Remark 2.2. Note that the Hessian of the functional G is not supposed to be compact. Then, if
4

H = R d , its smallest eigenvalue λmin (Γm ) does not necessarily converge to 0 when the dimension
d tends to infinity.

2.2

The algorithms

Let X1 , ..., Xn , ... be independent random variables with the same law as X. The stochastic
gradient algorithm is defined recursively by
Zn + 1 = Zn − γ n ∇ h g ( X n + 1 , Zn )

(3)

= : Z n − γ n Un + 1 ,
where Z1 is chosen bounded and Un+1 := ∇h g ( Xn+1 , Zn ). The step sequence (γn ) is a de-

creasing sequence of positive real numbers which verifies the following usual assumptions
(see Duflo (1997))

∑ γn = ∞,

∑ γ2n < ∞.

n ≥1

n ≥1

The term Un+1 can be considered as a random perturbation of the gradient Φ at Zn . Indeed, let (Fn ) be the sequence of σ-algebra defined for all n ≥ 1 by Fn := σ ( X1 , ..., Xn ) =
σ ( Z1 , ..., Zn ), then
E [ Un+1 |Fn ] = ∇ G ( Zn ) =: Φ ( Zn ) .
In order to improve the convergence, we now introduce the averaged algorithm (Ruppert
(1988), Polyak and Juditsky (1992)) defined recursively by
Z n +1 = Z n +


1
Zn + 1 − Z n ,
n+1

(4)

with Z1 = Z1 . This can also be written as follows
Zn =

2.3

1
n

n

∑ Zk .
k=1

Some convexity properties

We now give some convexity properties of the functional G. The proofs are given in Appendix. First, since ∇ G (m) = 0 and since G is twice continuously differentiable, note that
for all h ∈ H,

∇ G ( h) = ∇ G ( h) − ∇ G ( m ) =

Z 1
0

Γm+t(h−m)(h − m)dt.

The first proposition gives the local strong convexity of the functional G.
Proposition 2.1. Assume (A1) to (A3) and (A5a) hold. For all positive constant A and for all
h ∈ B (m, A),

h∇ G (h), h − mi ≥ c A kh − mk2 ,
5

with c A := min

n

λmin λmin ǫ
2 , 2A

o

. Moreover, there is a positive constant C such that for all h ∈ H,

|h∇ G (h), h − mi| ≤ C kh − mk2 .
This result remains true replacing assumption (A5a) by (A5a’).
The following corollary ensures that m is the unique solution of the problem defined by
(1).
Corollary 2.1. Assume (A1) to (A3) and (A5a) hold. Then, m is the unique solution of the equation

∇ G (h) = 0,
and in a particular case, m is the unique minimizer of the functional G.
Remark 2.3. Assumption (A3) and Proposition 2.1 enable us to invert the Hessian at m and to have
a control on the "loss" of strong convexity. More precisely, assumption (A3) could be replaced by
(A3’) There is a basis composed of eigenvectors of Γm and its smallest eigenvalue λmin (or the lim inf
of the eigenvalues in the case of infinite dimensional spaces) is positive. Moreover there are
positive constant c, c′ such that for all A > 0 and for all h ∈ B (m, A),


c′
h∇ G (h), h − mi ≥ min c,
A



k h − m k2 .

Finally, the last proposition gives an uniform bound of the remainder term in the Taylor’s expansion of the gradient.
Proposition 2.2. Assume (A1), (A2), (A4) and (A5a) hold. Then, for all h ∈ H, there is a positive
constant Cm such that for all h ∈ H,

k∇ G (h) − Γm (h − m)k ≤ Cm kh − mk2 .
This result remains true replacing assumption (A5a) by (A5a’).

3
3.1

Applications
An application in general separable Hilbert spaces: the geometric quantiles

Let H be a separable Hilbert space and let X be a random variable taking values in H. The
geometric quantile mv of X corresponding to a direction v, where v ∈ H and kvk < 1, is
defined by
mv := arg min E [kX − hk − kX k] − hh, vi .
h∈ H

Note that if v = 0, the geometric quantile m0 corresponds to the geometric median (Haldane
(1948), Kemperman (1987)). Let Gv be the function we would like to minimize, defined for
6

all h ∈ H by Gv := E [kX − hk + h X − h, vi]. Since kvk < 1, it comes
lim Gv (h) = +∞,

k hk→∞

and Gv admits so a minimizer mv , which is also a solution of the following equation



X−h
∇ Gv ( h ) = − E
− v = 0.
k X − hk
Then, assumption (A1) is fulfilled and the stochastic gradient algorithm and its averaged
version are defined recursively for all n ≥ 1 by
mvn+1

=

mvn

+ γn

mvn+1 = mvn +




Xn+1 − mvn
+v ,
k Xn+1 − mvn k

1
(mvn+1 − mvn ) ,
n+1

with m1v = m1v chosen bounded (choosing a positive constant M, one can take m1v of the
form m1v : = X1 1 kX1 k≤ M for example). In order to ensure the uniqueness of the geometric

quantiles and the convergence of these estimates, we consider from now that the following
assumptions are fulfilled:
(B1) The random variable X is not concentrated on a straight line: for all h ∈ H, there is
h′ ∈ H such that hh, h′ i = 0 and

Var

X, h′



> 0.

(B2) The random variable X is not concentrated around single points: for all positive constant A, there is a positive constant C A such that for all h ∈ H,



1
E
≤ CA ,
k X − hk

E

"

1

k X − hk 2

#

≤ CA.

Note that assumption (B2) is not restrictive when we deal with a high dimensional space.
For example, if H = R d with d ≥ 3, as discussed in Chaudhuri (1992) and Cardot et al.

(2013), this condition is satisfied since X admits a density which is bounded on every compact subset of R d . Finally, this assumption ensures the existence of the Hessian of Gv , which
is defined for all h ∈ H by



1
∇ Gv ( h ) = E
X
−
hk
k
2



X−h
X−h
⊗
IH −
X
−
h
k
k k X − hk



,

where for all h, h′ , h′′ ∈ H, h ⊗ h′ (h′′ ) := hh, h′′ i h′ . Moreover, Corollary 2.1 in Cardot et al.
(2017) ensures that if assumptions (B1) and (B2) are fulfilled, assumptions (A2) and (A3) are
verified, while Lemma 5.1 in Cardot et al. (2017) ensures that assumption (A4) is fulfilled.

7

Finally, for all positive integer p ≥ 1 and for all h ∈ H,
E

"

X−h
+v
k X − hk

2p

#

≤ 22p ,

and assumptions (A5a) and (A5b) are so verified.

3.2

An application in a finite dimensional space: a robust logistic regression

Let d ≥ 1 and H = R d . Let ( X, Y ) be a couple of random variables taking values in
H × {−1, 1}. The aim is to minimize the functional Gr defined for all h ∈ R d by (see
Bach (2014))

Gr (h) := E [log (cosh (Y − h X, hi))] .
In order to ensure the existence and uniqueness of the solution, we consider from now that
the following assumptions are fulfilled:
(B1’) There exists mr such that ∇ Gr (mr ) = 0.
(B2’) The Hessian of the functional Gr at mr is positive.
(B3’a) The random variable X admits a 2-nd moment.
(B3’b) For all integer p, the random variable X admits a p-th moment.
Assumption (B1’) ensures the existence of a solution while (B2’) gives its uniqueness. Assumption (B3a) ensures that the functional Gr is twice Fréchet-differentiable and its gradient
and Hessian are defined for all h ∈ R d by

∇ Gr (h) = E
∇2 Gr (h) = E



"


− sinh (Y − h X, hi)
X ,
cosh (Y − h X, hi)
1

(cosh (Y − h X, hi))2

#

X⊗X .

Note that assumption (B2’) is verified, for example, since there are positive constants


M, M ′ such that the matrix E X ⊗ X1 {kX k≤ M} 1 {kYk≤ M′ } is positive. Then, the solution mr

can be estimated recursively as follows:

sinh (Yn+1 − h Xn+1 , mrn i)
Xn +1 ,
cosh (Yn+1 − h Xn+1 , mrn i)
1
= mrn +
(mrn+1 − mrn ) ,
n+1

mrn+1 = mrn + γn
mrn+1

with mr1 = mr1 bounded. Under assumptions (B1’) to (B3’a), hypothesis (A1) to (A5a) are
satisfied, while under additional assumption (B3’b), hypothesis (A5b) is satisfied.
Remark 3.1. Remark that these results remain true for several cases of regression. For example, one

8

can consider the logistic regression
ml := arg min E [log (1 + exp (−Y h X, hi))] ,
h ∈R d

with ( X, Y ) taking values in R d × {−1, 1}. Then, one can consider estimates of the form
mln+1
mln+1

4


exp −Yn+1 Xn+1 , mln
=
+ γn
Yn+1 Xn+1 ,
1 + exp (−Yn+1 h Xn+1 , mln i)

1  l
= mln +
mn+1 − mln .
n+1
mln

Rates of convergence

In this section, we consider a learning rate sequence (γn )n≥1 of the form γn := cγ n−α with
cγ > 0 and α ∈ (1/2, 1). Note that taking α = 1 could be possible with a good choice
1
λmin

of the value of the constant cγ (taking cγ >

for instance). Nevertheless, the averag-

ing step enables us to get the optimal rate of convergence with a smaller variance than
the stochastic gradient algorithm with a fastly decreasing step sequence γn = cγ n−1 (see
Polyak and Juditsky (1992), Pelletier (1998) and Pelletier (2000) for more details).

4.1

Almost sure rates of convergence

In this section, we focus on the almost sure rates of convergence of the algorithms defined
in (3) and (4). First, the following theorem gives the consistency of the algorithms.
Theorem 4.1. Suppose (A1) to (A3) and (A5a) hold. Then,
lim kZn − mk = 0

a.s,

lim Z n − m = 0

a.s.

n→∞

n→∞

This result remains true replacing assumptions (A3) and/or (A5a) by (A3’) and/or (A5a’).
The following theorem gives the almost sure rates of convergence of the stochastic gradient algorithm as well as of its averaged version under the additional assumption (A4).
Theorem 4.2. Suppose (A1) to (A5a) hold. For all δ, δ′ > 0,

k Zn − m k 2 = o
Zn − m

2

=o



(ln n)δ
nα



(ln n)1+δ
n

a.s,
!
′

a.s.

This result remains true replacing assumptions (A3) and/or (A5a) by (A3’) and/or (A5a’).
Note that similar results are given in Pelletier (1998), but only in finite dimension. More
precisely, the given proofs cannot be directly extended to the case where H is an infinite
9

dimensional space. For example, these methods rely on the fact that the Hessian of the
functional G admits finite dimensional eigenspaces, which is not necessarily true for general
Hilbert spaces. Another problem is that norms are not equivalent in infinite dimensional
spaces, and consequently, the Hilbert-Schmidt (or Frobenius) norm for linear operators is
not necessarily finite even if the spectral norm is. For example, under assumption (A3), if
H is an infinite dimensional space,

kΓm kop ≤ Ckmk ,

kΓm k H −S = +∞,

and

where k.k H −S is the Hilbert-Schmidt norm.

4.2

L p rates of convergence

In this section, we focus on the L p rates of convergence of the algorithms. The proofs are
postponed in Section 5. The idea is to give non asymptotic results without focusing only on
the rate of convergence in quadratic mean. Indeed, recent works (see Cardot and Godichon-Baggioni
(2015) and Godichon-Baggioni (2016) for instance), confirm that having L p rates of convergence can be very useful to establish rates of convergence of more complex estimates.
Theorem 4.3. Assume (A1) to (A5b) hold. Then, for all integer p, there is a positive constant K p
such that for all n ≥ 1,

i
h
Kp
E k Zn − mk2p ≤ pα .
n

(5)

This result remains true replacing assumptions (A3) and/or (A5b) by (A3’) and/or (A5b’).
Finally, the last theorem gives the L p rates of convergence of the averaged estimates.
Theorem 4.4. Assume (A1) to (A5b) hold. Then, for all integer p, there is a positive constant K ′p
such that for all n ≥ 1,
E

h

Zn − m

2p

i

≤

K ′p
np

.

This result remains true replacing assumptions (A3) and/or (A5b) by (A3’) and/or (A5b’).
As done in Cardot et al. (2017) and Godichon-Baggioni (2016), one can check that, under
assumptions, these rates of convergence are the optimal ones for Robbins-Monro algorithms
and their averaged versions, i.e one can prove that there are positive constants c, c′ such that
for all n ≥ 1,
i
h
c
E k Zn − m k 2 ≥ α ,
n

E

h

Zn − m

2

i

≥

c′
.
n

Remark 4.1. One can obtain the same L p and almost sure rates of convergence for the stochastic
gradient algorithm replacing assumption (A4) by
(A4’) There are positive constants ǫ > 0 and β ∈ (1, 2] such that for all h ∈ B (m, ǫ)

k∇ G (h) − Γm (h − m)k ≤ Cβ kh − mk β .
10

Moreover, one can get the same L p and almost sure rates of convergence for the averaged algorithm
replacing (A4) by (A4’) and taking a step sequence of the form γn := cγ n−α with α ∈ ( β−1 , 1).
Remark 4.2. Let p be a positive integer, it is possible to get the L2p rates of convergence of the
Robbins-Monro algorithm just supposing

i is a positive integer q such that q > 2p + 2
h that there
2q
≤ Lq (or such that E [∇h g ( X, h)] ≤ Lq 1 + kh − mk2q )
and a positive constant Lq such that E f ( X, h)


q
and taking a step sequence of the form γn := cγ n−α with α ∈ 21 , p+2+q .

5

Proofs

5.1

Some decompositions of the algorithms

In order to simplify the proofs thereafter, we introduce some usual decompositions of the
algorithms. First, let us recall that the Robbins-Monro algorithm is defined by
Z n + 1 = Z n − γ n Un + 1 ,

(6)

with Un+1 := ∇h g ( Xn+1 , Zn ). Then, let ξ n+1 := Φ( Zn ) − Un+1 , equality (6) can be written
as

Zn + 1 − m = Zn − m − γ n Φ ( Zn ) + γ n ξ n + 1 .

(7)

Note that (ξ n ) is a martingale differences sequence adapted to the filtration (Fn ). Furthermore, linearizing the gradient, equation (7) can be written as
Zn+1 − m = ( I H − γn Γm ) ( Zn − m) + γn ξ n+1 − γn δn ,

(8)

where δn := Φ( Zn ) − Γm ( Zn − m) is the remainder term in the Taylor’s expansion of the

gradient. Note that thanks to Proposition 2.2, there is a positive constant Cm such that
for all n ≥ 1, kδn k ≤ Cm kZn − mk2 . Finally, by induction, we have the following usual
decomposition
Zn − m = β n−1 ( Z1 − m) + β n−1 Mn − β n−1 Rn ,

(9)

with
β n −1 : =

n −1

∏ ( I H − γk Γ m ) ,

Mn : =

n −1

∑ γk β−k 1 ξ k+1 ,

k=1
n −1

k=1

β0 := IH ,

Rn :=

∑ γk β−k 1 δk .

k=1

In the same way, in order to get the rates of convergence, we need to exhibit a new
decomposition of the averaged algorithm. In this aim, equality (8) can be written as
Γ m ( Zn − m ) =

Zn − m Zn + 1 − m
−
+ ξ n+1 − δn .
γn
γn

As in Pelletier (2000), summing these equalities, applying Abel’s transform and dividing by
11

n, we have
Γm

5.2



1
Zn − m =
n

n
Z1 − m Zn+1 − m
−
+∑
γ1
γn
k=2



1
1
−
γk
γk−1



n

( Zk − m ) −

∑ δk
k=1

!

+

1
n

n

∑ ξ k+1 .
k=1

(10)

Proof of Section 4.1

Proof of Theorem 4.1. Using decomposition (7) and since (ξ n ) is a sequence of martingale
differences adapted to the filtration (Fn ),
i
i
h
h
2
E k Zn+1 − mk2 |Fn = kZn − mk2 − 2γn h Zn − m, Φ( Zn )i + γ2n kΦ( Zn )k + γ2n E kξ n+1 k2 |Fn .
Moreover, with Assumption (A5a),
i
i
h
h
E kξ n+1 k2 |Fn = E kUn+1 k2 |Fn − 2 hE [Un+1 |Fn ] , Φ( Zn )i + kΦ( Zn )k2
i
h
≤ E ( f ( Xn+1 , Zn ) + C k Zn − mk)2 |Fn − kΦ( Zn )k2


≤ 2E f ( Xn+1 , Zn )2 |Fn + 2C2 k Zn − mk2 − kΦ( Zn )k2

≤ 2L1 + 2C2 kZn − mk2 − kΦ( Zn )k2 .

Thus,
i
h

E k Zn+1 − mk2 |Fn ≤ 1 + 2C2 γ2n kZn − mk2 − 2γn hΦ( Zn ), Zn − mi + 2γ2n L1 .

Since hΦ( Zn ), Zn − mi ≥ 0 and ∑n≥1 γ2n < +∞, Robbins-Siegmund theorem (see Duflo
(1997) for example) ensures that kZn − mk converges almost surely to a finite random variable and that

∑ γ n h Φ ( Zn ) , Zn − m i < + ∞

a.s.

n ≥1

Moreover, since hΦ ( Zn ) , Zn − mi ≥ 0, by induction, there is a positive constant M such
that for all n ≥ 1,
i
i
h
 h
E k Zn+1 − mk2 ≤ 1 + 2C2 γ2n E k Zn − mk2 + 2γ2n L1
!
i
h

2 2
≤ ∏ 1 + 2C γk E kZ1 − mk2 + 2L1
k≥1

≤ M.

∏
k≥1

1 + 2C2 γ2k



!

∑ γ2k
k≥1

Thus, one can conclude the proof in the same way as in the proof of Theorem 3.1 in Cardot et al.
(2013) for instance. Finally, one can apply Toeplitz’s lemma (see Duflo (1997), Lemma 2.2.13)
to get the strong consistency of the averaged algorithm.

In order to get the almost sure rates of convergence of the Robbins-Monro algorithm,
12

we now introduce a technical lemma which gives the rate of convergence of the martingale
term β n−1 Mn in decomposition (9).
Lemma 5.1. Suppose assumptions (A1) to (A3) and (A5a) hold. Then, for all δ > 0,
2

k β n −1 Mn k = o



(ln n)δ
nα



a.s.

Proof of Lemma 5.1. Since (ξ n ) is a sequence of martingale differences adapted to the filtra1
tion (Fn ), and since Mn+1 = Mn + γn β−
n ξ n +1 ,
i
h
i
h
E k β n Mn+1 k2 |Fn = k β n Mn k2 + 2γn h β n Mn , E [ ξ n+1 |Fn ]i + γ2n E kξ n+1 k2 |Fn
i
h
= k β n Mn k2 + γ2n E kξ n+1 k2 |Fn
i
h
≤ k IH − γn Γm k2op k β n−1 Mn k2 + γ2n E kξ n+1 k2 |Fn .
Since each eigenvalue λ of Γm verifies 0 < λmin ≤ λ ≤ C and since (γn ) converges to 0,
there is a rank n0 such that for all n ≥ n0 , k IH − γn Γm kop ≤ 1 − λmin γn . Thus, for all n ≥ n0 ,
i
h
i
h
E k β n Mn+1 k2 |Fn ≤ (1 − λmin γn )2 k β n−1 Mn k2 + γ2n E kξ n+1 k2 |Fn .
Let δ > 0, for all n ≥ 1, let Vn :=

n2α−1
(ln n)1+δ

k β n−1 Mn k2 , then for all n ≥ n0 ,

i
(n + 1)2α−1 2 h
(n + 1)2α−1
2
2
ξ
|F
β
M
+
γ
E
k
k
k
k
n
n
n
+
1
n
−
1
(ln(n + 1))1+δ
(ln(n + 1))1+δ n
2α−1 
 1+ δ

i
(n + 1)2α−1 2 h
ln n
n+1
2
Vn +
ξ
|F
γ
E
= (1 − λmin γn )2
k
k
n .
n +1
n
ln(n + 1)
(ln(n + 1))1+δ n

E [ Vn+1 |Fn ] ≤ (1 − λmin γn )2

Moreover, there are a positive constant c and a rank n0′ (let us take n0′ ≥ n0 ) such that for all
n ≥ n0′ ,
1 − λmin cγ n

−α





n+1
n

2α−1 

ln n
ln(n + 1)

 1+ δ

≤ 1 − cn−α .

α −1

Furthermore, cn−α Vn = c (lnnn)1+δ k β n−1 Mn k2 . Thus, for all n ≥ n0′ ,
E [Vn+1 |Fn ] ≤ Vn +

i
(n + 1)2α−1 2 h
n α −1
2
−
c
ξ
|F
γ
E
k
k
k β n −1 Mn k 2 .
n
n +1
(ln(n + 1))1+δ n
(ln n)1+δ

(11)

i
h
Finally, since E kξ n+1 k2 |Fn ≤ 2L1 + 2C k Zn − mk2 and since kZn − mk converges almost
surely to 0, the application of the Robbins-Siegmund theorem ensures that (Vn ) converges
almost surely to a finite random variable and ensures that

∑
n ≥ n0′

n α −1
k β n −1 Mn k 2 < ∞
(ln n)1+δ

13

a.s.

Previous inequality can also be written as

∑
n ≥ n0′

1
n ln n



nα
k β n − 1 M n k2
(ln n)δ



< ∞ a.s,

so that we necessarily have, applying Toeplitz’s lemma,
nα
a.s
k β n−1 Mn k2 −−−→ 0.
n→∞
(ln n)δ

(12)

Remark 5.1. Note that this proof is the main difference with Pelletier (2000). Indeed, in order to
prove the same result, many methods were used but they cannot be directly applied if H is a infinite
dimensional space. For example, it is based on the fact that the Hessian of the function we would like
to minimize admits finite dimensional eigenspaces, which is not automatically verified in our case.
Proof of Theorem 4.2. Rate of convergence of the Robbins-Monro algorithm: Applying decomposition (9), as in Pelletier (1998), let
∆n = β n−1 ( Z1 − m) − β n−1 Rn = ( Zn − m) − β n−1 Mn .
We have
∆ n + 1 = Zn + 1 − m − β n M n + 1

= ( IH − γn Γm ) ( Zn − m) + γn ξ n+1 − γn δn − γn ξ n+1 − ( IH − γn Γm ) β n−1 Mn
= ( IH − γn Γm ) ∆n − γn δn .

Thus, applying a lemma of stabilization (see Duflo (1996) Lemma 4.1.1 for instance), and
since kδn k ≤ Cm k Zn − mk2 ,



k∆n k = O (kδn k) = O k Zn − mk2

a.s.

Finally, since ( Zn ) converges almost surely to m, k∆n k = o (k Zn − mk) almost surely and

k Zn − m k ≤ k β n − 1 M n k + k ∆ n k


(ln n)δ/2
+ o (kZn − mk)
=o
nα/2
which concludes the proof.

14

a.s,

Rate of convergence of the averaged algorithm: With the help of decomposition (10),
Zn − m

2

2

n
− m k2
5 kZ
5
k Z − m k2
+ 2 2 n +1 2
+ 2 2 ∑ δk
≤ 2 2 1 2
γn
λmin n
γ1
λmin n
λmin n k=1
2

 2
n
n
5
1
1
5
+ 2 2 ∑ ( Zk − m )
−
+ 2 2 ∑ ξ k+1 .
γk
γk−1
λmin n k=2
λmin n k=1

5

As in Godichon-Baggioni (2016), thanks to the almost sure rate of convergence of the RobbinsMonro algorithm, one can check that
 
1
n
 
2
1
1 k Zn + 1 − m k
=o
2
2
n
γn
n
2




n
1
1
1
=o
∑ ( Zk − m ) γ k − γ k − 1
n
k=2
2
 
n
1
∑ δk = o n
k=1
1 k Z1 − mk
=o
n2
γ1

1
n2

Let δ > 0 and Mn′ := √

√

n
(ln n)1+δ

1
n

∑nk=1 ξ k+1

= √

1
n (ln n )1+δ

a.s,
a.s,
a.s,

a.s.

k∑nk=1 ξ k+1 k. Since (ξ n ) is a

martingale differences sequence adapted to the filtration (Fn ), and since

i
h


E kξ n+2 k2 |Fn+1 ≤ 2E f ( Xn+2 , Zn+1 )2 |Fn+1 + 2C2 k Zn+1 − mk2

≤ 2L1 + 2C2 k Zn+1 − mk2 ,

we have
i
h
1
n(ln n)1+δ
2
′2
ξ
|F
M
+
E
k
k
n +2
n +1
(n + 1)(ln(n + 1))1+δ n
(n + 1)(ln(n + 1))1+δ


1
2
2
.
Z
−
m
2L
+
2C
≤ Mn′2 +
k
k
n
+
1
1
(n + 1)(ln(n + 1))1+δ



E Mn′2+1 |Fn+1 =

Since k Zn+1 − mk converges almost surely to 0, applying Robbins-Siegmund theorem, Mn′2
converges almost surely to a finite random variable, which concludes the proof.

5.3

Proof of Theorem 4.3

In order to prove Theorem 4.3 with the help of a strong induction on p, we have to introduce
some technical lemmas (the proofs are given in Appendix). Note that these lemmas remain
true replacing assumptions (A3) and/or (A5b) by (A3’) and/or (A5b’) but the proofs are
only given for the first assumptions.
The first lemma gives a bound of the 2p-th moment when inequality (5) is verified for
15

all integer from 0 to p − 1.
Lemma 5.2. Assume (A1) to (A5b) hold. Let p be a positive integer, and suppose that for all
k ≤ p − 1, there is a positive constant Kk such that for all n ≥ 1,
i
h
K
E k Zn − mk2k ≤ kαk .
n

(13)

Thus, there are positive constants c0 , C1 , C2 and a rank nα such that for all n ≥ nα ,
i
h
i
h
E kZn+1 − mk2p ≤ (1 − c0 γn ) E kZn − mk2p +

C1
n ( p + 1) α

i
h
+ C2 γn E kZn − mk2p+2 .

Then, the second lemma gives an upper bound of the (2p + 2)-th moment when inequality (5) is verified for all integer from 0 to p − 1.
Lemma 5.3. Assume (A1) to (A3) and (A5b) hold. Let p be a positive integer, and suppose that for
all k ≤ p − 1, there is a positive constant Kk such that for all n ≥ 1,
i
h
K
E k Zn − mk2k ≤ kαk .
n

Thus, there are positive constants C1′ , C2′ and a rank nα such that for all n ≥ nα ,
h

E k Zn + 1 − m k

2p+2

i

≤



2
1−
n

 p +1

i
h
E k Zn − mk2p+2 +

C1′
n ( p + 2) α

i
h
+ C2′ γ2n E k Zn − mk2p .

Finally, the last lemma enables us to give a bound of the probability for the RobbinsMonro algorithm to go far away from m, which is crucial in order to prove Lemma 5.3.
Lemma 5.4. Assume (A1) to (A3) and (A5b) hold. Then, for all integer p ≥ 1, there is a positive
constant M p such that for all n ≥ 1,

i
h
E kZn − mk2p ≤ M p .

Proof of Theorem 4.3. As in Godichon-Baggioni (2016),we will prove
 with the help of a strong

induction that for all integer p ≥ 1, and for all β ∈

α,

p +2
p α

stants K p , Cβ,p such that for all n ≥ 1,

−

1
p

, there are positive con-

i
h
Kp
E k Zn − mk2p ≤ pα ,
n
i
h
Cβ,p
E kZn − mk2p+2 ≤ βp .
n
Applying Lemma 5.4, Lemma 5.2 and Lemma 5.3, as soon as the initialization is satisfied,
the proof is strictly analogous to the proof of Theorem 4.1 in Godichon-Baggioni (2016).
Thus, we will just prove that for p = 1 and for all β ∈ (α, 3α − 1), there are positive con-

16

stants K1 , Cβ,1 such that for all n ≥ 1,
i
h
K1
E k Zn − m k 2 ≤ α ,
n
i
h
C
β,1
E k Zn − m k 4 ≤ β .
n
We now split the end of the proof into two steps.
Step 1: Calibration of the constants. In order to simplify the demonstration there′ be positive constants such that K ′ ≥
after, we now introduce some notations. Let K1′ , Cβ,1
1

′
′
′
1
21+α C1 c0−1 c−
γ , (c0 , C1 are defined in Lemma 5.2), and 2K1 ≥ C β,1 ≥ K1 ≥ 1. By definition of

β, there is a rank n β ≥ nα (nα is defined in Lemma 5.2 and in Lemma 5.3) such that for all

n ≥ nβ,




2α+ β+1 cγ C2
n+1 α 1
≤ 1,
+ c0 γ n +
(1 − c0 γ n )
n
2
( n + 1) β
 



1
2 2 n+1 β
+ C1′ + C2′ c2γ 23α
1−
≤ 1,
n
n
(n + 1)3α− β

with C2 defined in Lemma 5.2 and C1′ , C2′ defined in Lemma 5.3. The rank n β exists because
since β > α,

(1 − c0 γ n )



n+1
n

α

2α+ β+1 cγ C2
1
α 1
+ c0 γ n +
= 1 − c0 γ n + + c0 γ n + O
β
2
n 2
( n + 1)
 
1
1
.
= 1 − c0 γ n + o
2
nα



1
nβ



Moreover, since β < 3α − 1, we have β < 2, and


1−

2
n

2 

n+1
n

β


+ C1′ + C2′ c2γ 23α


 

1
1
1
1
=
1
−
(
4
−
2β
)
+
o
+
O
n
n
(n + 1)3α− β
n3α− β
 
1
1
= 1 − (4 − 2β) + o
.
n
n

io
n
h
Step 2: The induction on n. Let us take K1′ ≥ max1≤k≤n β kα E k Zk − mk2 and
io
n
h
4
βE
′ ≥ max
. We now prove by induction that for all n ≥ n β ,
Z
−
m
k
Cβ,1
k
k
k
1≤ k ≤ n β
i
h
K′
E k Zn − mk2 ≤ α1 ,
n
i
h
Cβ,1
4
E k Zn − m k ≤ β .
n

17

′ ≥ K ′ ≥ 1,
Applying Lemma 5.2 and by induction, since 2K1′ ≥ Cβ,1
1

i
h
i
h
i
h
C1
E k Zn+1 − mk2 ≤ (1 − c0 γn ) E kZn − mk2p + 2α + C2 γn E k Zn − mk2p+2
n
′
C
K1′
C
β,1
≤ (1 − c0 γn ) α + 2α1 + C2 γn β
n
n
n
′
K
K′
C
≤ (1 − c0 γn ) α1 + 2α1 + 2C2 γn β1 .
n
n
n
Factorizing by

K1′
( n + 1) α ,

h

E k Zn + 1 − m k

2

i




K1′
n+1 α
1
n+1 α
C1
+
≤ (1 − c0 γ n )
α
n
( n + 1)
n
( n + 1) α n α


K1′
n + 1 α+ β
+ 2cγ C2
n
( n + 1) α + β

α
1
2α C1 c−
2α+ β+1 cγ C2
K1′
K1′
n+1
γ γn
≤ (1 − c0 γ n )
+
+
.
n
( n + 1) α
( n + 1) α
( n + 1) β ( n + 1) α


1 −1
Taking K1′ ≥ 21+α C1 c−
γ c0 ,

h

E k Zn + 1 − m k

2

i


K1′
K1′
2α+ β+1 cγ C2
K1′
1
n+1 α
+
γ
c
+
≤ (1 − c0 γ n )
n
0
n
( n + 1) α 2
( n + 1) α
( n + 1) β ( n + 1) α
!

α
2α+ β+1 cγ C2
K1′
n+1
1
≤ (1 − c0 γ n )
+ c0 γ n +
.
n
2
( n + 1) α
( n + 1) β


By definition of n β ,

i
h
E k Zn + 1 − m k 2 ≤

K1′
.
( n + 1) α

(14)

In the same way, one can check by induction and applying Lemma 5.3 that
h

i

E k Zn + 1 − m k 4 ≤
By definition of n β ,



2
1−
n

2 

n+1
n

β

+ 23α

′
i
h
Cβ,1
E k Zn + 1 − m k 4 ≤ β ,
n

C1′ + C2′ c2γ

(n + 1)3α− β

!

′
Cβ,1

( n + 1) β

.

(15)

which concludes the induction on n, and one can conclude the induction on p and the proof
in a similar way as in Godichon-Baggioni (2016).

18

5.4

Proof of Theorem 4.4

Proof of Theorem 4.4. Let λmin be the smallest eigenvalue of Γm , with the help of decomposition (10), for all integer p ≥ 1,
E

h

Zn − m

2p

i

≤
+

52p−1
2p

λmin n2p
52p−1

i
h
E kZ1 − mk2p
2p



E

2p
λmin n2p

γ1

+

n

∑ ( Zk − m )

k=2

52p−1
2p

λmin n2p



i
h
E k Zn+1 − mk2p
2p

1
1
−
γk
γk−1



2p

γn


+

+

52p−1
2p

λmin n2p

52p−1
2p

λmin n2p


E

n



E

∑ ξ k+1

k=1

n

∑ δk
k=1
2p



.

As in Godichon-Baggioni (2016), applying Theorem 4.3 and Lemma 4.1 in Godichon-Baggioni
(2016), one can check that there are positive constants R1,p , R2,p , R3,p , R4,p such that for all
n ≥ 1,

h

2p

i

R1,p
1 E k Z1 − mk
≤ 2p ,
2p
2p
n
n
γ1
i
h
2p
R2,p
1 E k Zn + 1 − m k
≤ ( 2− α ) p ,
2p
2p
n
n
γn



1  n
1
1
−
Z
−
m
E
∑ ( k ) γk γk−1
n2p
k=2


2p
R4,p
1  n
δk  ≤ 2αp .
E
∑
2p
n
n
k=1

2p



≤

R3,p
n ( 2− α ) p

,

We now prove with the help of a strong induction that for all integer p ≥ 1, there is a
positive constant C p such that



E

2p

n

∑ ξ k+1
k=1



 ≤ Cpn p.

Step 1: Initialization of the induction. Since (ξ n ) is martingale differences sequence
adapted to the filtration (Fn ),


E

2

n

∑
k=1

ξ k+1



=

=

i
h
n
2
+
2
ξ
E
k
k
k+1
∑
∑
n

n

k=1
n

=

∑

k=1 k′ = k+1

k=1

∑E

n

h

i
n
k ξ k+1 k 2 + 2 ∑

i
h
2
.
ξ
E
k
k
k+1
∑

k=1

19

E [hξ k+1 , ξ k′ +1 i]

n

∑
′

k=1 k = k+1

E [hξ k+1 , E [ ξ k′ +1 |Fk′ ]i]

2p




h

i

h

i



Moreover, since E kξ n+1 k |Fn ≤ E kUn+1 k |Fn ≤ 2E f ( Xn+1 , Zn )2 |Fn + 2C2 k Zn − mk2 ,
applying Theorem 4.3, there is a positive constant C1 such that for all n ≥ 1,


E

2

2

n

∑ ξ k+1
k=1



2

n


 ≤ 2 ∑ E f ( Xk+1 , Zk )2 |Fk + 2C2
k=1
n

≤ 2 ∑ L1 + 2C2 K1
k=1

n

n

∑E
k=1

h

k Zk − m k 2

i

1

∑ kα

k=1

≤ C1 n.
Step 2: the induction. Let p ≥ 2, we suppose from now that for all p′ ≤ p − 1, there is
a positive constant C p′ such that for all n ≥ 1,


E

2p′

n



 ≤ C p′ n p′ .

∑ ξ k+1
k=1

First, note that
n +1

∑ ξ k+1

k=1

2

n

=

∑ ξ k+1
k=1

2

+2

*

n

∑ ξ k+1 , ξ n +2
k=1

+

+ k ξ n + 2 k2 .

Thus, let Mn := ∑nk=1 ξ k+1 , with the help of previous equality and applying Cauchy-Schwarz’s
inequality,
 p −1
p


k Mn+1 k2p ≤ k Mn k2 + kξ n+2 k2 + 2 h Mn , ξ n+2 i k Mn k2 + kξ n+2 k2
p  
 p−k

p k
.
+∑
2 k Mn k k k ξ n +2 k k k Mn k 2 + k ξ n +2 k 2
k
k=2
We now bound the expectation of the three terms on the right-hand side of previous inequality. First, since

we have

k Un + 1 k ≤ f ( X n + 1 , Z n ) + C k Z n − m k ,
p
kΦ( Zn )k ≤ L1 + C kZn − mk ,


 h
i
i
h
E kξ n+2 k2k |Fn+1 ≤ 32k−1 E f ( Xn+2 , Zn )2k |Fn+1 + 22k C2k k Zn+1 − mk2k + L1k


≤ 32k−1 Lk + L1k + 22k C2k k Zn+1 − mk2k .

20

Then, since Mn is Fn+1 -measurable,
E

h

2

k Mn k + k ξ n +2 k

2

 pi

  h h
i
i
p
E E kξ n+2 k2k |Fn k Mn k2p−2k
≤ E k Mn k + ∑
k
k=1
p  
i
i
h
 h
p 2k−1 
2p
2p−2k
k
≤ E k Mn k + ∑
L k + L1 E k Mn k
3
k
k=1
p  
i
p 2k−1 2k 2k h
+∑
3
2 C E k Zn+1 − mk2k k Mn k2p−2k
k
k=1
h

2p

i

p

By induction,
 
i
 h

p
2p−2k
≤
∑ k 32k−1 Lk + L1k E k Mn k
k=1
p

 




p
∑ k 32k−1 Lk + L1k C p−k n p−k = O n p−1 .
k=1
p

Moreover, since for all positive real number a and for all positive integer q, a ≤ 1 + aq ,

applying Hölder’s inequality and by induction, let

 
i
p 2k−1 2k 2k h
(⋆) : = ∑
3
2 C E k Zn+1 − mk2k k Mn k2p−2k
k
k=1


p
p  
i
i
p 2k−1 2k 2k h
p 2k−1 2k 2k h
2p−2k
≤∑
+∑
3
2 C E k Mn k
3
2 C E k Zn+1 − mk2qk k Mn k2p−2k
k
k
k=1
k=1


p
i 2p2p−2k


i pk  h
p 2k−1 2k 2k  h
E k Mn k2p
+ O n p −1 .
≤∑
E k Zn+1 − mk2qp
3
2 C
k
k=1
p

i 2p2p−2k
 h
i
h
Note that E k Mn k2p
≤ 1 + E k Mn k2p . Thus, taking q ≥ 2 and applying Theo-

rem 4.3, there are positive constants C0 , C1′ such that

 

i

h
k 1 
p 2k−1 2k 2k
(⋆) ≤ ∑
3
2 C Kqp p qkα 1 + E k Mn k2p + O n p−1
k
n
k=1
i
h
≤ C0 γ2n E k Mn k2p + C1′ n p−1.
p

Finally, there are positive constants C0 , C1 such that
E

h

k M n k2 + k ξ n + 2 k2

pi

i
 h
≤ 1 + C0 γ2n E k Mn k2p + C1 n p−1.

(16)

Moreover, since (ξ n ) is a martingale differences sequence adapted to the filtration (Fn ) and

21

applying Lemma A.1 in Godichon-Baggioni (2016),

 h
p −1 
 p −1 
i

p−1
2E h Mn , ξ n+2 i k Mn k2 + kξ n+2 k2
=2∑
E h Mn , ξ n+2 i kξ n+2 k2k k Mn k2p−2−2k
k
k=1
 h
p −1 
i
p−1
2p−2−2k
2k+2
≤ ∑
E k ξ n +2 k
k Mn k
k
k=1
 h
p −1 
i
p−1
+∑
E kξ n+2 k2k k Mn k2p−2k
k
k=1
Since p ≥ 2 and by induction, as for (⋆), one can check that there are positive constants
C0′ , C1′ such that for all n ≥ 1,




2

2E h Mn , ξ n+2 i k Mn k + kξ n+2 k

2

 p −1 

i
h
≤ C0′ γ2n E k Mn k2p + C1′ n p−1.

(17)

Moreover, let
 

 p−k 

p k
2
2
k
k
(⋆⋆) : = ∑
2 E k Mn k k ξ n +2 k k Mn k + k ξ n +2 k
k
k=2
p  
i

p p −1 h
≤ ∑
2 E k Mn kk kξ n+2 kk k Mn k2p−2k + kξ n+2 k2p−2k
k
k=2


p  
p
i
i
p p −1 h
p p −1 h
2p− k
k
2 E k Mn kk kξ n+2 k2p−k .
+∑
2 E k ξ n +2 k k Mn k
≤ ∑
k
k
k=2
k=2
p

We now bound the two terms on the right-hand side of previous inequality. First, let
 
i
p p −1 h
2 E k Mn kk kξ n+2 k2p−k
(⋆⋆ ) := ∑
k
k=2
p  
i

p p−3 h
≤∑
2 E k Mn k2 + k Mn k2k−2 kξ n+2 k2p−2k+2 + kξ n+2 k2p−2
k
k=2
p

′

As for (⋆), one can check that there are positive constants C0′′ , C1′′ such that for all n ≥ 1,
i
h
(⋆⋆′ ) ≤ C0′′ γ2n E k Mn k2p + C1′′ n p−1.

In the same way, let
 
i
p p −1 h
(⋆⋆ ) := ∑
2 E kξ n+2 kk k Mn k2p−k
k
k=2


p
i

p p−3 h
≤∑
2 E kξ n+2 k2 + kξ n+2 k2k−2 k Mn k2p−2k+2 + k Mn k2
k
k=2
p

′′

As for (⋆), there are positive constants C0′′′ , C1′′′ such that
i
h
(⋆⋆′′ ) ≤ C0′′′ γ2n E k Mn k2p + C1′′′ n p−1,
22

and in a particular case
i
h


(⋆⋆) ≤ C0′′ + C0′′′ γ2n E k Mn k2p + C1′′ + C1′′′ n p−1.

(18)

Thus, thanks to inequalities (16) to (18), there are positive constants B0 , B1 such that for all
n ≥ 1,

h

E k Mn +1 k

2p

i

≤ 1+
∞

≤

∏
k=1
∞

≤

∏

h



2p

i

+ B1 n p−1
E k Mn k
!
i
h

E k M1 k2p +
1 + B0 γ2k

B0 γ2n

1 + B0 γ2k

k=1



!

h

i

E k M1 k2p +

∞

∏


2

1 + B0 γk

k=1
∞

∏

1 + B0 γ2k

k=1



!

!

n

∑ B1 k p−1
k=1

B1 n p ,

which concludes the induction and the proof.

A

Proofs of Propositions 2.1 and 2.2 and recall on the decomposition of the Robbins-Monro algorithm

A.1 Proofs of Propositions 2.1 and 2.2
Proof of Proposition 2.1. If h ∈ B (m, ǫ), under assumptions (A2) and (A3) and by dominated

convergence,

h Φ( h), h − m i =
=

Z

1
0

Z 1D
0

Γm+t(h−m) (h − m)dt, h − m



E
Γm+t(h−m)(h − m), h − m dt

λ
≥ min kh − mk2 .
2

In the same way, if kh − mk > ǫ, since G is convex, under assumptions (A2) and (A3) and
by dominated convergence,

h Φ( h), h − m i =
=
≥
≥

Z

1
0

Z 1D
Z

Z

0

Γm+t(h−m)(h − m)dt, h − m

E
Γm+t(h−m) (h − m), h − m dt

ǫ
kh − m k

0
ǫ
kh − m k

0



D

E
Γm+t(h−m) (h − m), h − m dt

λmin
kh − mk2 dt
2

λmin ǫ
=
kh − mk .
2

23

Thus, let A be a positive constant and h ∈ B (m, A),

with c A := min

n

λmin λmin ǫ
2 , 2A

o

h Φ( h), h − m i ≥ c A k h − m k 2 ,
. We now give an upper bound of this term. First, thanks to

assumption (A2), let A be a positive constant, for all h ∈ B (m, A),

h Φ( h), h − m i =
≤
≤

Z 1D
0

Z 1

E
Γm+t(h−m) (h − m), h − m dt

0

Γm+t(h−m) (h − m) kh − mk dt

0

Γ m+t(h−m)

Z 1

op

kh − mk2 dt

≤ C A k h − m k2 .
Moreover, applying Cauchy-Schwarz’s inequality and thanks to assumption (A5a), for all
h ∈ H such that kh − mk ≥ A,

|hΦ(h), h − mi| ≤ kΦ(h)k kh − mk

≤ (E [ f ( X, h)] + C kh − mk) kh − mk
p
≤ L1 k h − m k + C k h − m k2
√

L1
≤
+ C k h − m k2 ,
A

which concludes the proof.
Proof of Proposition 2.2. Let us recall that there are positive constants ǫ, Cǫ such that for all
h ∈ B (m, ǫ),

kΦ(h) − Γm (h − m)k ≤ Cǫ kh − mk2 .

Let h ∈ H such that kh − mk ≥ ǫ. Then, thanks to assumptions (A2) and (A3),

kΦ(h) − Γm (h − m)k ≤ kΦ(h)k + kΓm kop kh − mk
≤ (E [ f ( X, h)] + C kh − mk) + C0 kh − mk
√

L1 C C0
≤
+ +
k h − m k2 ,
ǫ2
ǫ
ǫ
which concludes the proof.

A.2 Decomposition of the Robbins-Monro algorithm
Let us recall that the Robbins-Monro algorithm can be written as
Zn + 1 − m = Zn − m − γ n Φ ( Zn ) + γ n ξ n + 1 ,

24

(A–19)

where Φ( Zn ) is the gradient of the function G at Zn , and ξ n+1 := Φ( Zn ) − ∇h g ( Xn+1 , Zn ).

Moreover, let us recall that denoting by (Fn )n≥1 the sequence of σ-algebra defined for all
n ≥ 1 by σn := σ ( X1 , ..., Xn ), then (ξ n ) is a sequence of martingale differences adapted to

this filtration. Finally, linearizing the gradient, the Robbins-Monro algorithm can be written
as
Zn+1 − m = ( I H − γn Γm ) ( Zn − m) + γn ξ n+1 − γn δn ,

(A–20)

where δn := Φ( Zn ) − Γm ( Zn − m) is the remainder term in the Taylor’s expansion of the

gradient.

B

Proof of Lemma 5.4

Proof of Lemma 5.4. We prove Lemma 5.4 with the help of a strong induction on p. The case
p = 1 is already done in the proof of Theorem 3.1. We suppose from now that p ≥ 2 and

that for all k ≤ p − 1, there is a positive constant Mk such that for all n ≥ 1,
i
h
E kZn − mk2k ≤ Mk .

Let Vn := Zn − m − γn Φ( Zn ), and with the help of decomposition (A–19)

k Zn+1 − mk2 = kVn k2 + γ2n kξ n+1 k2 + 2γn hVn , ξ n+1 i

≤ kVn k2 + γ2n kUn+1 k2 + 2γn h Zn − m, ξ n+1 i .

Thus, applying Cauchy-Schwarz’s inequaltiy
p
 p −1


k Zn+1 − mk2p ≤ kVn k2 + γ2n kUn+1 k2 + 2pγn h Zn − m, ξ n+1 i kVn k2 + γ2n kUn+1k2
p  
 p−k

p k k
.
(B–21)
+∑
2 γn k Zn − mkk kξ n+1 kk kVn k2 + γ2n kUn+1 k2
k
k=2
Moreover, since kUn+1 k ≤ f ( Xn+1 , Zn ) + C k Zn − mk, it comes kΦ ( Zn )k ≤ C k Zn − mk +
and

kξ n+1 k ≤ kUn+1 k + kΦ( Zn )k

≤ f ( Xn+1 , Zn ) + 2C k Zn − mk +

p

√

L1 .

Applying Lemma A.1 in Godichon-Baggioni (2016), for all positive integer k,

k Un + 1 k k ≤ 2 k − 1 f ( X n + 1 , Z n ) + 2 k − 1 C k k Z n − m k k

a.s,

(B–22)
k
2

k ξ n + 1 k k ≤ 3 k − 1 f ( X n + 1 , Zn ) k + 3 k − 1 2 k C k k Zn − m k k + 3 k − 1 L 1

25

a.s.

(B–23)

L1 ,

Moreover, since hΦ ( Zn ) , Zn − mi ≥ 0 and since kΦ( Zn )k ≤ C kZn − mk +

√

L1 ,


kVn k2 ≤ 1 + 2C2 γ2n k Zn − mk2 + 2γ2n L1 ,

kVn k2 ≤ 1 + 2C2 c2γ k Zn − mk2 + 2γ2n L1 .

We now bound each term on the right-hand side of inequality (B–21).
 pi
h
. Applying previous inequality and inequality (B–22),
Bounding E kVn k2 + γ2n kUn+1 k2

let

pi
kVn k2 + γ2n kUn+1 k2
p  
ii
i
h
h
p 2k h
2p
= E kVn k + ∑
γn E kVn k2p−2k E kUn+1 k2k |Fn
k
k=1


p
i
i
i
h
p 2p 2p−2 p−k h h
2p
γn 2
L1 E E f ( Xn+1 , Zn )2k |Fn + C2k kZn − mk2k
≤ E kVn k + ∑
k
k=1
p  
i
i
 h
 p−k h
p 2k p+k−2
+∑
γn 2
1 + 2C2 c2γ
E kZn − mk2p−2k E f ( Xn+1 , Zn )2k |Fn + C2k kZn − mk2k .
k
k=1

(∗) : = E

h



Moreover, since E f ( Xn+1 , Zn )2k |Fn ≤ Lk and by induction, there are positive constants
A0 , A1 such that
h

(∗) ≤ E kVn k

2p

i

2p
+ γn 22p−2 L p

2p
+ γn 22p−2

+

p −1 

∑

k=1



2p

h

L p + C E k Zn − m k

2p

i

+

p −1 

∑

k=1


 p−k
p p+k−2 2k
2
γn 1 + 2C2 c2γ
L k M p−k
k
i
 p−k h
1 + 2C2 c2γ
E k Zn − mk2p



p 2p 2p−2 p−k 
γn 2
L1
Lk + C2k Mk
k

 
p p+k−2 2k
+∑
2
γn
k
k=1
i
i
h
h
≤ E kVn k2p + A0 γ2n E k Zn − mk2p + A1 γ2n .
p

(B–24)


Since kVn k2 ≤ 1 + 2C2 γ2n kZn − mk2 + 2L1 γ2n and by induction,
h

E kVn k

2p

i

 
i
 p−k k k 2k h
p
≤
1 + 2C2 γ2n
2 L1 γn E k Zn − mk2p−2k
k Zn − m k + ∑
k
k=1


p
i
h

 p−k k k 2k
p
2p
2 2 p
= 1 + 2C γn E kZn − mk + ∑
1 + 2C2 γ2n
2 L1 γn M p− k
k
k=1
i

p h
≤ 1 + 2C2 γ2n E kZn − mk2p + O γ2n .
p
1 + 2C2 γ2n E

h

2p

i

p

Then, there are positive constants A2 , A3 such that

i
 h
(∗) ≤ 1 + A2 γ2n E k Zn − mk2p + A3 γ2n .

(B–25)


 p −1 

Bounding 2pγn E hξ n+1 , Zn − mi kVn k2 + γ2n kUn+1 k2
. Since (ξ n ) is a martingale
26

differences sequence adapted to the filtration (Fn ), and since Vn is Fn -measurable, let


 p −1 

(∗∗) : = γn E hξ n+1 , Zn − mi kVn k2 + γ2n kUn+1 k2
"
#

p −1 
i
h
p
−
1
2p−2−2k
= γn E hE [ξ n+1 |Fn ] , Zn − mi kVn k2 + γn E hξ n+1 , Zn − mi ∑
γ2k
kUn+1k2k
n kVn k
k
k=1
"
#

p −1 
p − 1 2k
= γ n E h ξ n + 1 , Zn − m i ∑
γn kVn k2p−2−2k kUn+1 k2k .
k
k=1

Since |hξ n+1 , Zn − mi| ≤
1
(∗∗) ≤
2

+

1
2

+

1
2

p −1 

1
2





kξ n+1 k2 + k Zn − mk2 and kVn k2 ≤ 1 + 2c2γ C2 kZn − mk2 + 2L1 γ2n ,


i
 p − 1− k h
p − 1 2k+1 p−2−k
1 + 2C2 c2γ
E kZn − mk2p−2−2k kUn+1 k2k kξ n+1 k2
∑ k γn 2
k=1

p −1 
i
 p − 1− k h
p − 1 2k+1 p−2−k
1 + C2 c2γ
E k Zn − mk2p−2k kUn+1 k2k
∑ k γn 2
k=1

p −1 
i
i
h
p − 1 2p−1 2p−3−2k p−1−k  h
L1
E kUn+1 k2k kξ n+1 k2 + E kUn+1 k2k k Zn − mk2 .
∑ k γn 2
k=1

Moreover, since p ≥ 2, applying inequalities (B–22) and (B–23) and by induction, as for (∗),
one can check that there are positive constants A1′ , A2′ such that

i
h
(∗∗) ≤ A1′ γ3n E k Zn − mk2p + A2′ γ3n .
p
Bounding ∑k=2 ( pk)2k γnk E



k

k Zn − m k k ξ n + 1 k

k



2

+ γ2n

(B–26)
2

 p−k 

. Applying Lemma A.1
k Un + 1 k


in Godichon-Baggioni (2016), and since kZn − mkk kξ n+1 kk ≤ 12 k Zn − mk2k + kξ n+1 k2k ,
let

p  
 p−k 

p k k
2
2
k
k
2
(∗ ∗ ∗) : = ∑
2 γn E k Zn − mk kξ n+1 k kVn k + γn kUn+1 k
k
k=2
p  
i
p p −2 k h
2p−2k
≤∑
2 γn E kVn k2p−2k kZn − mk2k + γn
k Zn − mk2k kUn+1 k2p−2k
k
k=2


p
i
p p −2 k h
2p−2k
+∑
2 γn E kVn k2p−2k kξ n+1 k2k + γn
kUn+1 k2p−2k kξ n+1 k2k
k
k=2

kVn k

Applying inequalities (B–22) and (B–23) and by induction, as for (∗), one can check that
there are positive constants A1′′ , A2′′ such that
i
h
(∗ ∗ ∗) ≤ A1′′ γ2n E k Zn − mk2p + A2′′ γ2n .

(B–27)

Conclusion. Applying inequalities (B–25) to (B–27) and by induction, there are positive

27

constants B1 , B2 such that
i
i
h
 h
E k Zn+1 − mk2p ≤ 1 + B1 γ2n E k Zn − mk2p + B2 γ2n
!
i
h
∞

≤ ∏ 1 + B1 γ2k E kZ1 − mk2p + B2
k=1

∞

∏


2

1 + B1 γk

k=1

≤ Mp,

!

∞

∑ γ2k
k=1

which concludes the induction and the proof.

C

Proof of Lemma 5.3

Proof of Lemma 5.3. Let p ≥ 1, we suppose from now that for all integer k < p, there is a
positive constant Kk such that for all n ≥ 1,

i
h
K
E k Zn − mk2k ≤ kαk .
n

(C–28)

As in previous proof, let us recall that
 p +1
p


+ 2( p + 1)γn h Zn − m, ξ n+1 i kVn k2 + γ2n kUn+1 k2
k Zn+1 − mk2p+2 ≤ kVn k2 + γ2n kUn+1 k2

p +1 
 p + 1− k

p+1 k k
,
+∑
2 γn kZn − mkk kξ n+1 kk kVn k2 + γ2n kUn+1 k2
k
k=2
(C–29)

with Vn := Zn − m − γn Φ( Zn ). We now bound the expectation of each term on the right-

hand side of previous inequality.

 p +1 
2
2
2
. As in the proof of Lemma 5.4, we
Bounding (∗) := E kVn k + γn kUn+1 k
have

h

(∗) ≤ E kVn k
p +1 

2p+2

i

+

p +1 

∑

k=1


i
h

p + 1 p+k−1 2k
2p+2
2 2 p+1− k 2k
2
γn 1 + 2C cγ
C E k Zn − m k
k


i
h
 p + 1− k
p + 1 p+k−1 2k
+∑
2
γn 1 + 2C2 c2γ
Lk E kZn − mk2p+2−2k
k
k=1


p +1
i p + 1  p + 1
p + 1 2p p+1−k 2p+2 2k h
p+1− k 2p+2
2k
+∑
γn L k
22p L1
2 L1
γ n C E k Zn − m k + ∑
k
k
k=1
k=1
Since
k ≤ p − 1, there is a positive constant Kk such that for all n ≥ 1,
i
h for all integer
2k
≤ Kk n−kα , there are positive constants A0 , A0′ , A0′′ such that
E k Zn − m k
i
i
h
i
h
h
(∗) ≤ E kVn k2p+2 + A0 γ2n E kZn − mk2p+2 + A0′ γ2n E kZn − mk2p +
28

A0′′

n ( p + 2) α

. (C–30)

 pi
h

. As in the
Bounding (∗∗) := E 2( p + 1)γn h Zn − m, ξ n+1 i kVn k2 + γ2n kUn+1 k2

proof of Lemma 5.4, since (ξ n ) is a sequence of martingale differences adapted to the filtration (Fn ),

 
p 2k
(∗∗) = 2( p + 1)γn ∑
γn h Zn − m, ξ n+1 i kVn k2p−2k kUn+1 k2k
k
k=1
p  
i
 p−k h
p 2k p−k−1
≤ ( p + 1) γ n ∑
γn 2
1 + 2C2 c2γ
E kZn − mk2p−2k kUn+1 k2k kξ n+1 k2
k
k=1


p
i
 p−k h
p 2k p−k−1
+ ( p + 1) γ n ∑
γn 2
1 + 2C2 c2γ
E kZn − mk2p+2−2k kUn+1 k2k
k
k=1
p  
i
i
h
p 2p 2p−2k−1 p−k  h
+ ( p + 1) γ n ∑
γn 2
L1
E kUn+1 k2k kξ n+1 k2 + E kUn+1 k2k kZn − mk2 .
k
k=1
p

Moreover, applying inequalities (B–22) and (B–23), let
 
i
h

p p−k−1 2k
2
2k
2p−2k
2 2 p−k
2
γ
ξ
−
m
U
Z
1
+
2C
c
E
k
k
k
k
k
k
n
n +1
n +1
∑ k
n
γ
k=1
p  
 p−k
p p+k−2 2k+1
≤∑
2
3γn
1 + 2C2 c2γ
k
k=1

i
h
E k Zn − mk2p−2k f ( Xn+1 , Zn )2 f ( Xn+1 , Zn )2k + C2k k Zn − mk2k
p  
i

 p−k 2 h
p p+k−1 2k+1
+∑
2
3γn
1 + 2C2 c2γ
C E k Zn − mk2p−2k+2 f ( Xn+1 , Zn )2k + C2k kZn − mk2k
k
k=1
p  
i

h
 p−k
p p+k−2 2k+1
+∑
2
3γn
1 + 2C2 c2γ
L1 E kZn − mk2p−2k f ( Xn+1 , Zn )2k + C2k k Zn − mk2k .
k
k=1
p

(⋆) : = γn

i
i
h
h
Since E f ( Xn+1 , Zn )2k+2 Fn ≤ Lk+1 , and since for all k ≤ p − 1, E kZn − mk2k ≤ Kk n−kα ,
there are positive constants A1 , A2 , A3 such that

i
i
h
h
(⋆) ≤ A1 γ3n E k Zn − mk2p+2 + A2 γ3n E k Zn − mk2p +

A3
.
(
p
n + 2) α

With analogous calculus, one can check that there are positive constants A1′ , A2′ , A3′ such
that

i
i
h
h
(∗∗) ≤ A1′ γ3n E k Zn − mk2p+2 + A2′ γ3n E k Zn − mk2p +

Bounding (∗ ∗ ∗) :=

p +1 p +1
∑k=2 ( k )2k γnk E



k

k Zn − m k k ξ n + 1 k

29

k



A3′
n ( p + 2) α

kVn k

2

+ γ2n

.

k Un + 1 k

(C–31)
2

 p + 1− k 

.

First, thanks to inequality (B–23),


k Zn − mkk kξ n+1 kk ≤ 3k−1 k Zn − mkk f ( Xn+1 , Zn )k + 2k C k kZn − mkk + L1k/2
 3k − 1

≤ 6k−1 2C k k Zn − mk2k + 3k−1 kZn − mk2 f ( Xn+1 , Zn )2k + L1k +
kZn − mk2k−2 .
2
Then,

(∗ ∗ ∗) ≤
p +1 

p +1 

∑

k=2


i

p + 1 p + k k−1 k k h
2p+2−2k
2 3 γn C E k Zn − mk2k kVn k2p+2−2k + γn
kUn+1k2p+2k−2k
k


i


p + 1 p k−1 k h
2p+2−2k
+∑
2 3 γn E kZn − mk2 f ( Xn+1 , Zn )2k + L1k kVn k2p+2−2k + γn
kUn+1 k2p+2k−2k
k
k=2


p +1
i

p + 1 p −1 k−1 k h
2p+2−2k
+∑
2 3 γn E k Zn − mk2k−2 kVn k2p+2−2k + γn
kUn+1k2p+2k−2k
k
k=2
With analogous calculus to the previous ones, one can check that there are positive constants A1′′ , A2′′ , A3′′ such that
i
h
i
h
(∗ ∗ ∗) ≤ A1′′ γ2n E kZn − mk2p+2 + A2′′ γ2n E k Zn − mk2p +

A3′′
n ( p + 2) α

.

(C–32)

Thus, applying inequalities (C–30) to (C–32), there are positive constants B0 , B1 , B2 such that
i
i
h
i
h
i
h
h
B2
E k Zn+1 − mk2p+2 ≤ E kVn k2p+2 + B0 γ2n E k Zn − mk2p+2 + B1 γ2n E k Zn − mk2p + ( p+2)α .
n
(C–33)
i
h
Then, in order to conclude the proof, we just have to bound E kVn k2p .

i
h
Bounding E kVn k2p+2 . As in Cardot et al. (2017) (see Lemma 5.2), applying Proposition 2.1, one can check that there is a positive constant c and a rank n′α such that for all
n ≥ n′α ,
C k Zn − mk2 1 {kZn −mk≤cn1−α} ≥ hΦ( Zn ), Zn − mi 1 {kZn −mk≤cn1−α } ≥

4
k Zn − mk2 1 {kZn −mk≤cn1−α } .
1
−
α
cγ n

Then, since kΦ( Zn )k2 ≤ 2C2 k Zn − mk2 + 2L1 γ2n , there is a rank n′′α such that for all n ≥ n′′α ,
2

k Zn − m − γn Φ ( Zn )k 1 {kZn −mk≤cn1−α} ≤



3
1−
n

30



k Zn − mk2 1 {kZn −mk≤cn1−α } + 2L1 γ2n .

Then, one can check that there are positive constants A1′′′ , A2′′′ such that
i
h
E kZn − m − γn Φ( Zn )k2p+2 1 {k Zn −mk≤cn1−α }



p +1 
i
p + 1 p + 1− k p + 1− k 2( p + 1− k )
3 k h
≤ ∑
2
L1
γn
1−
E k Zn − mk2k
k
n
k=0
 p +1 h

i
h
i
A′′′
3
E kZn − mk2p+2 + A1′′′ γ2n E kZn − mk2p + ( p+22)α .
≤ 1−
n
n
Moreover, applying Cauchy-Schwarz’s inequality, Markov’s inequality and Lemma 5.4, for
all positive integer q,
h

E k Zn − m k

2p+2

1 {kZn −mk≥cn1−α }

i

r h
iq
≤ E k Zn − mk4p+4 P [k Zn − mk ≥ cn1−α ]
r h
i
2q
Z
−
m
E
k
k
n
q
≤ M2p+2
c q n q ( 1− α )
p
q
Mq
≤ M2p+2 q q(1−α) ,
c n
( p + 2) α

and one can conclude the proof applying inequality (C–33), taking q ≥ 1−α and taking a
 p +1
 p +1
+ ( B0 + A1′′′ ) γ2n ≤ 1 − n2
.
rank nα such that for all n ≥ nα , 1 − n3
Remark C.1. Note that in order to get the rate of convergence in quadratic mean of the RobbinsMonro algorithm, i.e in the case where p = 1, we just have to suppose
that there
are a positive integer
i
h
q≥

D

3α
1− α

and a positive constant Lq such that for all h ∈ H, E f ( X, h)2q ≤ Lq .

Proof of Lemma 5.2

Proof of Lemma 5.2. Using decomposition (A–20) and Cauchy-Schwarz’s inequality, there
are a positive constant c′ and a rank n′α such that for all n ≥ n′α ,

k Zn+1 − mk2 ≤ k IH − γn Γm k2op k Zn − mk2 + γ2n kξ n+1 k2 + 2γn h Zn − m − γn Φ( Zn ), ξ n+1 i + 2γn h Zn − m, δn i
2
≤ 1 − c′ γn kZn − mk2 + γ2n kUn+1 k2 + 2γn h Zn − m, ξ n+1 i + 2γn k Zn − mk kδn k .

If p = 1, since there is a positive constant Cm such that for all n ≥ 1, kδn k ≤ Cm kZn − mk2 ,
we have

2 kδn k kZn − mk ≤

c′
C2
γ n k Zn − m k 2 + 2 m
k Zn − m k 4 ,
′
2
c

31

and since (ξ n ) is a martingale differences sequence adapted to the filtration (Fn ), applying
inequality (B–22), for all n ≥ n′α ,

i
i
h
i
i
h h
 h
E k Zn+1 − mk2 1 − c′ γn E kZn − mk2 + 2γ2n E E f ( Xn+1 , Zn ))2 |Fn + C2 kZn − mk2
i
i
h
c′
C2 h
4
+ γn E k Zn − mk2 + 2γn m
Z
−
m
E
k
k
n
2
c′
 h

i
i
′
C2 h
c
4
,
Z
−
m
E
≤ 1 − γn + 2C2 γ2n E k Zn − mk2 + 2γ2n L1 + 2γn m
k
k
n
2
c′
and one can conclude the proof for p = 1 taking a rank nα and a positive constant c such
′

that for all n ≥ nα , 1 − c2 γn + 2C2 γ2n ≤ 1 − cγn .
We suppose from now that p ≥ 2. For all n ≥ n′α ,

i
i
i
h
h
 h
E k Zn+1 − mk2p ≤ 1 − c′ γn E k Zn − mk2 k Zn+1 − mk2p−2 + 2γn E kZn − mk kδn k k Zn+1 − mk2p−2
i
i
h
h
+ γ2n E kUn+1 k2 k Zn+1 − mk2p−2 + 2γn E h Zn − m, ξ n+1 i kZn+1 − mk2p−2 .
(D–34)

Moreover, let us recall
 p −2
 p −1


+ 2( p − 1)γn h Zn − m, ξ n+1 i kVn k2 + γ2n kUn+1 k2
k Zn+1 − mk2p−2 ≤ kVn k2 + γ2n kUn+1 k2

p −1 
 p − 1− k

p−1 k k
2
2
k
k
2
+∑
,
2 γn kZn − mk kξ n+1 k kVn k + γn kUn+1 k
k
k=2
with Vn := Zn − m − γn Φ( Zn ).
We now bound each term on the right-hand side of inequality (D–34).
i
h

Bounding (1 − c′ γn ) E k Zn − mk2 kZn+1 − mk2p+2 . First, since kVn k2 ≤ 1 + 2C2 γ2n k Zn − mk2 +

2L1 γ2n , let

′





2



2

γ2n

2

 p −1 

(∗) : = 1 − c γn E kZn − mk kVn k + kUn+1 k


 p −1 


2
2
2
2 2
2
2
′
1 + 2C γn k Zn − mk + 2L1 γn + γn kUn+1 k
≤ 1 − c γ n E k Zn − m k
i

 p −1 h
E k Zn − mk2p
≤ 1 − c′ γn 1 + 2C2 γ2n


p −2 
 p − 1− k 

k
 2( p − 1− k )
p−1
+∑
.
1 + 2C2 c2γ E k Zn − mk2k+2 2L1 + kUn+1 k2
1 − c ′ γn γn
k
k=0



Applying inequality (B–22), 2L1 + kUn+1 k2 ≤ 2 L1 + C2 k Zn − mk2 + f ( Xn+1 , Zn )2 , and

32

since for all n ≥ nα we have 1 − c′ γn ≤ 1,

i

 p −1 h
(∗) ≤ 1 − c′ γn 1 + 2C2 γ2n
E kZn − mk2p

p −2 
i
i
k h h
p − 1 2( p − 1− k ) p − k − 1 − 1
+∑
γn
6
3
1 + 2C2 c2γ E E f ( Xn+1 , Zn )2( p−1−k) |Fn k Zn − mk2k+2
k
k=0


p −2
i
h
k
p − 1 2( p − 1− k ) p − k − 1 − 1
γn
6
3
1 + 2C2 c2γ C2( p−1−k) E k Zn − mk2p
+∑
k
k=0

p −2 
i
 k p − 1− k h
p − 1 2( p − 1− k ) p − k − 1 − 1
+∑
γn
6
3
1 + 2C2 c2γ L1
E kZn − mk2k+2 .
k
k=0

Applying inequality (C–28), since p ≥ 2 and since for all k ≤ p − 2, we have 2p − 1 − k ≥ p + 1,

one can check that there is a positive constant A1 such that
′

(∗) ≤ 1 − c γn +

A1 γ2n



h

E k Zn − m k

2p

i

+O



1
n ( p + 1) α



.

(D–35)

In the same way, applying Cauchy-Schwarz’s inequality, let
′

′





2



2

+ γ2n

2

 p −2 

(∗) : = 2( p − 1) 1 − c γn γn E kZn − mk h Zn − m, ξ n+1 i kVn k
k Un + 1 k
i
h

≤ 2( p − 1) 1 − c′ γn γn E kZn − mk2 h Zn − m, ξ n+1 i kVn k2( p−2)


i
 p−2 p − 2 2k+1 h
+ 2( p − 1) 1 − c ′ γ n ∑
γn E kZn − mk3 kξ n+1 k kVn k2( p−2−k) kUn+1 k2k
k
k=1
Note that the last term on the right-hand side of previous inequality is equal to 0 if p = 2.
Since (ξ n ) is a martingale differences sequence adapted to the filtration (Fn ),
i
h

2( p − 1) 1 − c′ γn γn E kZn − mk2 hVn , ξ n+1 i kVn k2( p−2) = 0.


Moreover, since kVn k2 ≤ 1 + 2C2 c2γ kZn − mk2 + 2L1 γ2n , and since

k Zn − m k 3 k ξ n + 1 k ≤

1
1
k Zn − m k 4 + k Zn − m k 2 k ξ n + 1 k 2 ,
2
2

we have
p −2 


i
 p−2−k 2k+1 h
p − 2 p − 3− k
(∗) ≤ ( p − 1) ∑
2
1 + 2C2 c2γ
γn E k Zn − mk2( p−k) kUn+1 k2k
k
k=1


p −2
i
 p−2−k 2k+1 h
p − 2 p − 3− k
+ ( p − 1) ∑
2
1 + 2C2 c2γ
γn E kZn − mk2( p−1−k) kUn+1 k2k kξ n+1 k2
k
k=1

p −2 
i
p − 2 2p−5−2k 2p−1 p−2−k h
+ ( p − 1) ∑
2
γn L1
E k Zn − mk4 kUn+1 k2k + k Zn − mk2 kUn+1 k2k kξ n+1 k2 .
k
k=1
′

As for (∗), applying inequalities (C–28), (B–22) and (B–23), one can check that there is a

33

positive constant A2 such that

i
h
(∗)′ ≤ A2 γ2n E k Zn − mk2p + O

1
n ( p + 1) α



.

(D–36)


In the same way, since kVn k ≤ 1 + 2c2γ C2 k Zn − mk2 + 2L1 γ2n and since

k Zn − m k k k ξ n + 1 k k ≤

1
1
kZn − mk2k−2 + k Zn − mk2 kξ n+1 k2k ,
2
2

we have



 p − 1− k 

 p −1 p − 1 k k
2
2
k
2
k
2
(∗) : = 1 − c γn ∑
2 γn E kZn − mk kξ n+1 k k Zn − mk kVn k + γn kUn+1 k
k
k=2


p −1 

 p − 1− k 

1
p−1 k k
2k
2
2
2 2
2
2
≤ ∑
2 γ n E k Zn − m k
1 + 2C cγ k Zn − mk + 2L1 γn + γn kUn+1 k
2 k=2
k


p −1 

 p − 1− k 

p−1 k k
1
2k
4
2
2
2 2
2
2
1 + 2C cγ k Zn − mk + 2L1 γn + γn kUn+1 k
2 γ n E k Zn − m k k ξ n + 1 k
.
+ ∑
2 k=2
k
′′

′

With analogous calculus to the previous ones, applying inequality (C–28), one can check
that there are positive constants A3 , A4 such that
′′

(∗) ≤

A3 γ2n E

h

k Zn − m k

2p

i

+

A4 γ2n E

h

k Zn − m k

2p+2

i

+O



1
n ( p + 1) α



.

(D–37)

Finally, applying inequalities (D–35) to (D–37), there are positive constants B0 , B1 , B2 such
that
E

h

i
i
h
i

 h
1 − c′ γn k Zn − mk2 k Zn+1 − mk2p−2 ≤ 1 − c′ γn + B0 γ2n E k Zn − mk2p + + B2 γ2n E k Zn − mk2p+2

+

B1

n ( p + 1) α

.

i
h
Bounding 2γn E k Zn − mk kδn k k Zn+1 − mk2p−2 . First, let


 p −1 

(∗) : = 2γn E kZn − mk kδn k kVn k2 + γ2n kUn+1k2
i
i
h
h
2p−1
≤ 2 p−1 γn E k Zn − mk kδn k kVn k2p−2 + 2 p−1 γn E kZn − mk kδn k kUn+1k2p−2 .


Moreover, since kδn k ≤ Cm k Zn − mk2 and since kVn k2 ≤ 1 + 2C2 c2γ k Zn − mk2 + 2L1 γ2n ,

34

let
i
h
(⋆) := 2 p−1 γn E k Zn − mk kδn k kVn k2p−2
i
i
h
h
 p −1
2p−1
p −1
≤ 22p−3 Cm 1 + 2C2 c2γ
γn E k Zn − mk2p+1 + 23p−4 L1 Cm γn E k Zn − mk3

2 1 + 2C 2 c2 2p−2
i
i 1
h
h
24p−6 Cm
γ
2p
2p+2
′
≤
Z
−
m
Z
−
m
+
c
γ
E
γ
E
k
k
k
k
n
n
n
n
c′
4
i
i
h
h
p−1 2p−1
p−1 2p−1
+ 23p−5 Cm L1 γn E k Zn − mk2 + 23p−5 Cm L1 γn E k Zn − mk4 .
Then, since p ≥ 2, there are positive constants B1 , B2 such that
2

p −1

h

γn E k Zn − mk kδn k kVn k

2p−2

i



 h
i
i
h
c′
2
≤
γn + B1 γn E k Zn − mk2p + B2 γn E k Zn − mk2p+2
4


1
+O
.
n ( p + 1) α

In the same way, since kδn k ≤ Cm kZn − mk2 , and applying inequality (B–22), let

i
h
E k Zn − mk kδn k kUn+1 k2p−2
i
i
h
h 

2p−1
2p−1
≤ 23p−5 Cm γn E E f ( Xn+1 )2p−2 |Fn k Zn − mk2 + 23p−5 C2p−2 Cm γn E k Zn − mk2p
h 
i
i
h

2p−1
2p−1
+ 23p−5 Cm γn E E f ( Xn+1 )2p−2 |Fn k Zn − mk4 + 23p−5 C2p−2 Cm γn E k Zn − mk2p+2 .
2p−1

(⋆⋆) := 2 p−1 γn

Since p ≥ 2, applying inequality (C–28), there are positive constant A1 , A2 , A3 such that




2

2γn E kZn − mk kδn k kVn k +

γ2n

k Un + 1 k

2

 p −1 



 h
i
c′
2p
2
γ n + A 1 γ n E k Zn − m k
≤
4
i
h
A3
+ A2 γn E kZn − mk2p+2 + ( p+1)α .
n
(D–38)

In a similar way, since (ξ n ) is a martingale differences sequence adapted to the filtration
(Fn ) and since Zn is Fn -measurable, let

 p −2 

(∗)′ : = 4( p − 1)γ2n E k Zn − mk kδn k h Zn − m, ξ n+1 i kVn k2 + γ2n kUn+1k2

≤ 4( p − 1)

p −2 

∑

k=1


i
p − 2 2k+2 h
γn E k Zn − mk kδn k h Zn − m, ξ n+1 i kVn k2( p−2−k) kUn+1 k2k .
k

Note that this term is equal to 0 if p = 2. Moreover, since kδn k ≤ Cm k Zn − mk2 , applying

Cauchy-Schwarz’s inequality,

k Zn − mk kδn k |h Zn − m, ξ n+1 i| ≤ Cm k Zn − mk4 kξ n+1 k


C
≤ m k Zn − m k 4 1 + k ξ n + 1 k 2 .
2
35

Then,
p −2 


i
p − 2 2k+2 h
(∗) ≤ 2Cm ( p − 1) ∑
γn E kVn k2( p−2−k) kZn − mk4 kUn+1 k2k
k
k=1


p −2
i
p − 2 2k+2 h
+ 2Cm ( p − 1) ∑
γn E kVn k2( p−2−k) kZn − mk4 kUn+1 k2k kξ n+1 k2 .
k
k=1
′

Thus, applying inequalities (C–28), (B–22) and (B–23), one can check that there are positive
constants A1′ , A2′ , A3′ such that
i
i
h
h
(∗)′ ≤ A1′ γ2n E k Zn − mk2p + A2′ γ2n E k Zn − mk2p+2 +

A3′
n ( p + 1) α

.

(D–39)

Finally, with similar calculus, let
"

#

 p − 1− k

p−1 k k
2
2
k
k
2
(∗) : = 2γn E kZn − mk kδn k ∑
2 γn kZn − mk kξ n+1 k kVn k + γn kUn+1 k
k
k=2


p −1 
 p − 1− k 

p − 1 k−1 k+1
≤ Cm ∑
2 γn E k Zn − mk2k+2 kVn k2 + γ2n kUn+1 k2
k
k=2


p −1 
 p − 1− k 

p − 1 k−1 k+1
2
2
2k
2
2
+ Cm ∑
2 γ n E k Zn − m k k ξ n + 1 k
kVn k + γn kUn+1 k
k
k=2


p −1 
 p − 1− k 

p − 1 k−1 k+1
2
2
2k+4
2
+ Cm ∑
2 γ n E k Zn − m k
kVn k + γn kUn+1k
k
k=2


p −1 
 p − 1− k 

p − 1 k−1 k+1
2
2
2k
4
2
+ Cm ∑
.
2 γ n E k Zn − m k k ξ n + 1 k
kVn k + γn kUn+1 k
k
k=2
′′

p −1 

Thus, applying inequalities (C–28), (B–22) and (B–23), one can check that there are positive
constants A0′′ , A1′′ , A2′′ such that
i
i
h
h
(∗)′′ ≤ A0′′ γ2n E k Zn − mk2p + A1′′ γ2n E k Zn − mk2p+2 +

A2′′
n ( p + 1) α

.

(D–40)

Finally, applying inequalities (D–38) to (D–40), there are positive constants B0′ , B1′ , B2′ such
that
h

2γn E k Zn − mk kδn k k Zn+1 − mk

2p−2

i



 h
i
1 ′
′ 2
≤
c γn + B0 γn E kZn − mk2p
4
i
h
B′
+ B1′ γn E k Zn − mk2p+2 + ( p+21)α .
n

i
h

Bounding γ2n E kUn+1 k2 k Zn+1 − mk2p−2 . First, since kVn k2 ≤ 1 + 2c2γ C2 k Zn − mk2 + 2L1 γ2n ,

36

let

(⋆) :=

γ2n E



k Un + 1 k

2



2

kVn k +

γ2n

k Un + 1 k

2

 p −1 

i
i
h
2p
γ2n E kUn+1 k2 k Zn − mk2p−2 + 3 p−2 γn E kUn+1 k2p
i
h
p−1 2p
+ 3 p − 2 2 p − 1 L 1 γ n E k Un + 1 k 2 .

≤ 3 p−2 1 + 2C2 c2γ

 p −1

h

Thus, applying inequalities (C–28), (B–22) and (B–23), there are positive constants A0 , A1
such that

 p −1 
i
h

2
2
2
2
2
≤ A0 γ2n E kZn − mk2p +
γn E kUn+1 k kVn k + γn kUn+1 k

A1
.
(
p
n + 1) α

(D–41)

In the same way, let

(∗) : = 2( p
≤

− 1)γ3n E

( p − 1)γ3n E







2

2

kUn+1k h Zn − m, ξ n+1 i kVn k +
2

2

γ2n

k Un + 1 k

2

k Un + 1 k k Z n − m k + k Un + 1 k k ξ n + 1 k

2



2

 p −2 
2

kVn k +

γ2n

k Un + 1 k

2

 p −2 

.

Thus, applying inequalities (C–28), (B–22) and (B–23), one can check that there are positive
constants A0′ , A1′ such that
2( p

− 1)γ3n E



2



kUn+1k h Zn − m, ξ n+1 i kVn k

2

+ γ2n

k Un + 1 k

2

 p −2 

i
h
≤ A0′ γ2n E k Zn − mk2p +
(D–42)

A1′
n ( p + 1) α

Finally, let
p −1 



 p − 1− k 

p − 1 k+2
2
2
k
2
k
2
(∗) : = ∑
γn E kUn+1 k k Zn − mk kξ n+1 k kVn k + γn kUn+1 k
k
k=2


p −1 
 p − 1− k 


1
p − 1 k+2
2
2
2k
2k
2
2
≤ ∑
.
γ n E k Un + 1 k k Z n − m k + k ξ n + 1 k
kVn k + γn kUn+1 k
2 k=2
k
′

Applying inequalities (C–28), (B–22) and (B–23), there are positive constants A0′′ , A1′′ such
that

i
h
(∗)′ ≤ A0′′ γ2n E k Zn − mk2p +

A1′′
n ( p + 1) α

.

(D–43)

Thus, applying inequalities (D–42) and (D–43), there are positive constants B0′′ , B1′′ such that
i
i
h
h
γ2n E kUn+1 k2 kZn+1 − mk2p−2 ≤ B0′′ γ2n E k Zn − mk2p +

B1′′
n ( p + 1) α

.

i
h
Bounding 2γn E h Zn − m, ξ n+1 i k Zn+1 − mk2p−2 . First, since (ξ n ) is a martingale dif-

37

.

ferences sequence adapted to the filtration (Fn ), let

 p −1 

(∗) : = 2γn E hξ n+1 , Zn − mi kVn k2 + γ2n kUn+1 k2
p −1 


i
p − 1 2k+1 h
=2∑
γn E hξ n+1 , Zn − mi kVn k2( p−1−k) kUn+1 k2k
k
k=1


p −1
i

p − 1 2k+1 h
≤ ∑
γn E kξ n+1 k2 + kZn − mk2 kVn k2( p−1−k) kUn+1 k2k .
k
k=1

Thus, applying inequalities (C–28), (B–22) and (B–23), one can check that there are positive
constants A0 , A1 such that




2

2γn E hξ n+1 , Vn i kVn k +

γ2n

k Un + 1 k

2

 p −1 

i
h
≤ A0 γ2n E k Zn − mk2p +

A1
.
(
p
n + 1) α

(D–44)

In the same way, applying Cauchy-Schwarz’s inequality, let

 p −2 

(∗)′ : = 4( p − 1)γ2n E h Zn − m, ξ n+1 i2 kVn k2 + γ2n kUn+1k2
i

h
2p−4
≤ 2 p−1 ( p − 1)γ2n E kZn − mk2 kξ n+1 k2 kVn k2p−4 + γn
kUn+1k2p−4
Thus, since p ≥ 2, applying inequalities (C–28), (B–22) and (B–23), one can check that there

are positive constants A0′ , A1′ such that
4( p − 1)γ2n E



h Zn − m, ξ n+1 i

2



2

kVn k +

γ2n

k Un + 1 k

2

 p −2 

i
h
≤ A0′ γ2n E k Zn − mk2p +

A1′
n ( p + 1) α
(D–45)

.

Finally, let
p −1 



 p−k 

p − 1 k+1
2
2
k
k
2
(∗) : = 2 ∑
γn E h Zn − m, ξ n+1 i k Zn − mk kξ n+1 k kVn k + γn kUn+1 k
k
k=2

p −1 
p − 1 p − k−2 k+1
≤ ∑
2
γn
k
k=2
i


h
2p−2k
E k Zn − mk2 + kξ n+1 k2 k Zn − mk2k + kξ n+1 k2k kVn k2p−2k + γn
kUn+1k2p−2k
′′

Thus, applying inequalities (C–28), (B–22) and (B–23), one can check that there are positive
constants A0′′ , A1′′ , A2′′ such that
i
h
i
h
(∗)′′ ≤ A0′′ γ2n E k Zn − mk2p + A1′′ γ2n E k Zn − mk2p+2 +

A2′′
n ( p + 1) α

.

(D–46)

Thus, applying inequalities (D–44) to (D–46), there are positive constants B0′′′ , B1′′′ , B2′′′ such
that
i
i
h
i
h
h
2γn E h Zn − m, ξ n+1 i k Zn+1 − mk2p−2 ≤ B0′′′ γ2n E k Zn − mk2p + B1′′′ γ2n E kZn − mk2p+2 +
38

B2′′′
n ( p + 1) α

.

Conclusion
We have proved that there are positive constants c0 , C1 , C2 such that for all n ≥ n′α ;
h

E k Zn + 1 − m k

2p

i

≤



 h
i
i
h
c′
C2
2
1 − γn + c0 γn E k Zn − mk2p + C1 γn E k Zn − mk2p+2 + ( p+1)α .
2
n

Thus, there are a positive constant c and a rank nα ≥ n′α such that for all n ≥ nα ,
1 −

c′
2 γn

+ c0 γ2n ≤ 1 − cγn , and in a particular case, for all n ≥ nα ,

i
i
h
h
i
h
E k Zn+1 − mk2p ≤ (1 − cγn ) E k Zn − mk2p + C1 γn E kZn − mk2p+2 +

C2
.
(
p
n + 1) α

(D–47)

References
Bach, F. (2014). Adaptivity of averaged stochastic gradient descent to local strong convexity
for logistic regression. The Journal of Machine Learning Research, 15(1):595–627.
Boyd, S. and Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
Cardot, H., Cénac, P., Godichon-Baggioni, A., et al. (2017). Online estimation of the geometric median in hilbert spaces: Non asymptotic confidence balls. The Annals of Statistics,
45(2):591–614.
Cardot, H., Cénac, P., and Zitt, P.-A. (2013). Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm. Bernoulli,
19(1):18–43.
Cardot, H. and Godichon-Baggioni, A. (2015). Fast estimation of the median covariation
matrix with application to online robust principal components analysis. TEST, pages
1–20.
Chaudhuri, P. (1992).

Multivariate location estimation using extension of R-estimates

through U-statistics type approach. Ann. Statist., 20:897–916.
Chaudhuri, P. (1996). On a geometric notion of quantiles for multivariate data. J. Amer.
Statist. Assoc., 91(434):862–872.
Chen, Y., Dang, X., Peng, H., and Bart, H. L. (2009). Outlier detection with the kernelized
spatial depth function. Pattern Analysis and Machine Intelligence, IEEE Transactions on,
31(2):288–305.
Cohen, K., Nedic, A., and Srikant, R. (2016). On projected stochastic gradient descent algorithm with weighted averaging for least squares regression. In 2016 IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2314–2318. IEEE.
39

Duflo, M. (1996). Algorithmes stochastiques. Springer Berlin.
Duflo, M. (1997). Random iterative models, volume 34 of Applications of Mathematics (New
York). Springer-Verlag, Berlin. Translated from the 1990 French original by Stephen S.
Wilson and revised by the author.
Ghadimi, S. and Lan, G. (2012). Optimal stochastic approximation algorithms for strongly
convex stochastic composite optimization i: A generic algorithmic framework. SIAM
Journal on Optimization, 22(4):1469–1492.
Godichon-Baggioni, A. (2016). Estimating the geometric median in hilbert spaces with
stochastic gradient algorithms: Lp and almost sure rates of convergence. Journal of Multivariate Analysis, 146:209–222.
Haldane, J. B. S. (1948). Note on the median of a multivariate distribution. Biometrika,
35(3-4):414–417.
Hallin, M. and Paindaveine, D. (2006). Semiparametrically efficient rank-based inference for
shape. i. optimal rank-based tests for sphericity. The Annals of Statistics, 34(6):2707–2756.
Huber, P. and Ronchetti, E. (2009). Robust Statistics. John Wiley and Sons, second edition.
Kemperman, J. (1987). The median of a finite measure on a Banach space. In Statistical data
analysis based on the L1 -norm and related methods (Neuchâtel, 1987), pages 217–230. NorthHolland, Amsterdam.
Kushner, H. J. and Yin, G. G. (2003). Stochastic approximation and recursive algorithms and
applications, volume 35 of Applications of Mathematics (New York). Springer-Verlag, New
York, second edition. Stochastic Modelling and Applied Probability.
Maronna, R. A., Martin, R. D., and Yohai, V. J. (2006). Robust statistics. Wiley Series in
Probability and Statistics. John Wiley & Sons, Ltd., Chichester. Theory and methods.
Moulines, E. and Bach, F. R. (2011). Non-asymptotic analysis of stochastic approximation
algorithms for machine learning. In Advances in Neural Information Processing Systems,
pages 451–459.
Pelletier, M. (1998). On the almost sure asymptotic behaviour of stochastic algorithms.
Stochastic processes and their applications, 78(2):217–244.
Pelletier, M. (2000). Asymptotic almost sure efficiency of averaged stochastic algorithms.
SIAM J. Control Optim., 39(1):49–72.
Polyak, B. and Juditsky, A. (1992). Acceleration of stochastic approximation. SIAM J. Control
and Optimization, 30:838–855.
Robbins, H. and Monro, S. (1951). A stochastic approximation method. The annals of mathematical statistics, pages 400–407.
40

Rudelson, M. (2014). Recent developments in non-asymptotic theory of random matrices.
Modern Aspects of Random Matrix Theory, 72:83.
Ruppert, D. (1988). Efficient estimations from a slowly convergent robbins-monro process.
Technical report, Cornell University Operations Research and Industrial Engineering.
Serfling, R. (2006). Depth functions in nonparametric multivariate inference. DIMACS Series
in Discrete Mathematics and Theoretical Computer Science, 72:1.

41

