Sorbonne Université Année 2022/2023

M2 Statistique Deuxième semestre

Algorithmes stochastiques

Antoine Godichon-Baggioni
Table des matières

1 Introduction 5
1.1 Cadre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Fonctions fortement convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Fonctions strictement convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 M-estimateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Définition et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Un résultat de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Estimation en ligne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Algorithmes de gradient stochastiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1 Algorithmes de gradient stochastiques . . . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Approche non-asymptotique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.3 Exemple : regression lineaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2 Martingales 21
2.1 Martingales réelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.2 Théorème de Robbins-Siegmund . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.3 Lois des grands nombres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.4 Théorème limite centrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Martingales vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.2 Vitesses de convergence des martingales vectorielles . . . . . . . . . . . . . . 34
2.2.3 Théorème Central Limite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3 Vitesses de convergence des algorithmes de gradient stochastiques 37

3.1 Convergence presque sûre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.1 Approche directe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.2 Approche via le développement de Taylor de la fonction G . . . . . . . . . . . 39
3.1.3 Approche Lyapunov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.4 Application au modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.5 Application à la régréssion logistique . . . . . . . . . . . . . . . . . . . . . . . 42

3
4

3.2 Vitesses de convergence presque sûre . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2.1 Cadre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.2 Vitesses de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2.3 Application au modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.4 Application à la régression logistique . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.5 Remarques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4 Accélération des méthodes de gradient stochastiques 53

4.1 Algorithmes de gradient stochastiques moyennés . . . . . . . . . . . . . . . . . . . . 53
4.1.1 Vitesse de convergence presque sûre . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1.2 Normalité asymptotique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.3 Application au modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.4 Application à la régression logistique . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.5 Remarques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Algorithme de Newton stochastique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1 Idée de l’algorithme de Newton stochastique . . . . . . . . . . . . . . . . . . . 67
4.2.2 L’algorithme de Newton stochastique . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.3 Vitesses de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2.4 Normalité asymptotique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.2.5 Application au modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.2.6 Application à la régression logistique . . . . . . . . . . . . . . . . . . . . . . . 83

Bibliographie 87
Chapitre 1

Introduction

1.1 Cadre

Dans ce cours, on s’intéresse à l’estimation du minimiseur m d’une fonction convexe G : Rd −→ R

définie pour tout h ∈ Rd par
G (h) := E [ g ( X, h)]

avec g : X × Rd −→ R, et X un espace mesurable. On peut par exemple considérer X = R ou

0
X = Rd . Dans ce cours, on se concentrera sur deux catégories de fonctions : fortement convexes
et strictement convexes.

1.1.1 Fonctions fortement convexes

Moyenne d’une variable aléatoire : Soit X une variable aléatoire à valeurs dans Rd . On peut voir
la moyenne m de X comme le minimiseur de la fonction G définie pour tout h ∈ Rd par

1 h i
G (h) = E k X − h k2 − k X k2
2

A noter que le terme k X k2 dans la définition de la fonction G permet de ne pas avoir à faire
d’hypothèse sur l’existence du moment d’ordre 2 de X. De plus, on a

∇ G ( h ) = −E [ X − h ]

et donc m = E[ X ] est l’unique zéro du gradient de la fonction G. Enfin, on a

∇2 G (h) = Id

et la Hessienne est donc définie positive et uniformément minorée sur Rd . Ainsi, la fonction G est
fortement convexe et la moyenne m est bien son unique minimiseur.

Régression linéaire : Soit ( X, Y ) un couple de variables aléatoires à valeurs dans X = Rd × R tel

6 Introduction

que
Y = θ T X + e, (1.1)

où θ ∈ Rd et e est une variable aléatoire indépendante de X vérifiant E[e] = 0. On suppose que

X et e admettent des moments d’ordre 2 et que la matrice E XX T est définie positive. Alors le
 

paramètre θ est l’unique minimiseur de la fonction G : Rd −→ R+ définie pour tout h ∈ Rd par

 2 
1
G (h) = E Y − h X
T
.
2

En effet, comme X et e admettent un moment d’ordre 2, la fonction G est différentiable et

h  i
∇ G ( h ) = −E Y − hT X X

En particulier, on a
h  i
∇ G ( θ ) = −E Y − θ T X X = −E [eX ] = −E [E [e| X ] X ] = 0.

De plus, comme X admet un moment d’ordre 2, la fonction G est deux fois différentiable et pour
tout h ∈ Rd , h i
∇2 G (h) = E XX T .

Cette matrice étant (supposée) définie positive, la Hessienne est uniformément minorée sur Rd et
la fonction G est donc fortement convexe, ce qui fait de θ son unique minimiseur.

Remarque 1.1.1. Bien que la matrice XX T soit au plus de rang 1, la matrice E XX T peut être définie po-
 

sitive. En effet, si considère un vecteur aléatoire gaussien Z ∼ N (0, Id ), sa matrice de variance-covariance

h i
E ZZ T = Var [ Z ] = Id

est définie positive.

1.1.2 Fonctions strictement convexes

Régression logistique : On considère un couple de variables aléatoires ( X, Y ) à valeurs dans

Rd × {0, 1} tel que   
L(Y | X ) = B π θ T X , (1.2)

exp( x )
avec π ( x ) = 1+exp( x )
. On peut voir le paramètre θ comme un minimiseur de la fonction G : Rd −→
R définie pour tout h ∈ Rd par
h    i
G (h) = E log 1 + exp h T X − h T XY .
1.1 Cadre 7

En effet, si la variable aléatoire X admet un moment d’ordre 2, la fonction G est différentiable et

pour tout h ∈ Rd ,
" #
exp h T X

h   i
∇ G (h) = E X − XY = E π h T
X X − XY .
1 + exp (h T X )

En particulier, comme E [Y | X ] = π θ T X , on a

h    i h h    ii h    i
∇ G (θ ) = E π θ T X − Y X = E E π θ T X − Y X | X = E π θ T X − E [Y | X ] X = 0.

De plus, comme X admet un moment d’ordre 2, la fonction G est deux fois différentiable et
h     i
∇2 G (h) = E π hT X 1 − π hT X XX T

qui est au moins semi-définie positive. On supposera par la suite que la Hessienne en θ est définie
positive, et donc que la fonction G est strictement convexe et que θ est son unique minimiseur.

Médiane d’une variable aléatoire : Soit X ∈ R une variable aléatoire et on suppose que sa fonction
de répartition est strictement croissante et continue au voisinage de sa médiane notée m. Celle ci
est alors le minimiseur de la fonction G : R −→ R définie pour tout h ∈ R par

G (h) = E [| X − h|] .

En effet, on rappelle que pour toute variable aléatoire X, grâce au théorème de Fubini-Tonelli,
Z +∞ Z +∞ Z +∞
 Z Z

P [ Z ≥ t] dt = E [1 Z≥t ] dt = E 1t≤Z dt = E 1dt = E [ Z ] .
0 0 0 0

Ainsi, on peut réécrire, pour tout h ∈ R

Z +∞ Z +∞ Z +∞
G (h) = P [| X − h| ≥ t] dt = P [ X ≥ t + h] dt + P [ X ≤ h − t] dt
0 0 0
Z +∞ Z h
= (1 − F (t)) dt + F (t)dt
h −∞

Ainsi, pour tout h, on a G 0 (h) = 2F (h) − 1 et donc m est bien l’unique minimiseur de la fonction

G. A noter que pour ne pas avoir à faire d’hypothèse sur l’existence du moment d’ordre 1 de | X |,
on peut réécrire la fonction G comme

G (h) = E [| X − h| − | X |] .

Médiane géométrique : On considère une variable aléatoire X à valeurs dans Rd . La médiane

8 Introduction

géométrique de X est un minimum de la fonction G : Rd −→ R définie pour tout h ∈ Rd par

G (h) := E [k X − hk − k X k] ,

où k.k est la norme euclidienne de Rd . A noter que la fonction G est différentiable avec pour tout
h ∈ Rd ,
X−h
 
∇ G ( h ) = −E .
k X − hk
Sous certaines hypothèses, la fonction G est deux fois continûment différentiable avec pour tout
h ∈ Rd , " !#
1 ( X − h)( X − h)T
∇ G (h) = E
2
Id − .
k X − hk k X − h k2
La Hessienne de G est donc au moins semi-définie positive. On supposera par la suite qu’elle est
strictement positive en m, et donc que la fonction G est strictement convexe.

1.2 M-estimateurs

1.2.1 Définition et exemples

On rappelle que l’objectif est d’estimer le minimisieur m de la fonction G définie pour tout h ∈ Rd
par
G (h) = E [ g ( X, h)] .

Comme on ne sait généralement pas calculer explicitement G (ou son gradient), on ne peut géné-
ralement pas calculer (ou approcher) directement la solution. Pour pallier ce problème, on consi-
dère maintenant des variables aléatoires indépendantes et identiquement distribuées X1 , . . . , Xn
de même loi que X. Une possibilité pour estimer m est alors de considérer la fonction empirique
Gn définie pour tout h ∈ Rd par
1 n
n k∑
Gn (h) = g ( Xk , h )
=1

A noter que par la loi des grands nombres, si g( X, h) admet un moment d’ordre 1 (ce qui est la
condition sine qua none pour que la fonction G soit bien définie en h),

p.s
Gn (h) −−−−→ G (h).
n→+∞

Un M-estimateur de m est un minimiseur m̂n de la fonction empirique Gn . A noter que m̂n n’est
pas toujours explicite, mais il existe tout de même quelques exemples où on sait le calculer.

Exemple 1 : estimation de la moyenne. Dans le cas de l’estimation de la moyenne, la fonction

1.2 M-estimateurs 9

empirique est définie pour tout h ∈ Rd par

1 n
2n k∑
Gn (h) = k Xk − h k2 − k Xk k2 ,
=1

et on obtient donc m̂n = X n . A noter que si X admet un moment d’ordre 2, le TLC nous donne
√
L
n X n − m −−−−→ N (0, Var( X )) .
n→+∞

Remarque 1.2.1. En notant que H := ∇2 G (m) = Id et que

h i h i
Σ := E ∇h g ( X, m) ∇h g ( X, m)T = E ( X − m)( X − m)T = Var( X ),

où ∇h g( X, h) est le gradient de g par rapport à la deuxième variable, on peut réécrire le TLC précédent
comme
√ L
 
n (m̂n − m) −−−−→ N 0, H −1 ΣH −1 .
n→+∞

Exemple 2 : la régression linéaire. Dans le cas de l’estimation du paramètre de la régression

linéaire, on a
1 n  T 2
2n k∑
Gn (h) = X k h − Yk .
=1

Si la matrice X = ( X1 , . . . Xn )T est de rang plein, on rappelle que le minimiseur de la fonction Gn

est l’estimateur des moindres carrés défini par
  −1
θ̂n = XX T XT Y

avec Y = (Y1 , . . . , Yn )T .

Remarque 1.2.2. Sous certaines hypothèses, on peut montrer que si la matrice Hessienne H := E XX T
 

est définie positive (et donc inversible), on a la normalité asymptotique

√
L  
n θ̂n − θ −−−−→ N 0, Var [e] H −1 .
n→+∞

De plus, en remarquant que

h i h   i
Σ := E ∇h g ( X, θ ) ∇h g ( X, θ )T = E Y − X T θ XX T Y − X T θ
h i
= E e2 XX T
h  i
= E E e2 | X XX T


= Var [e] H,
10 Introduction

on peut réécrire la normalité asymptotique comme

√
L  
n θ̂n − θ −−−−→ N 0, H −1 ΣH −1 .
n→+∞

Exemple 3 : médiane d’une variable aléatoire réelle. Dans le cas de l’estimation de la médiane
d’une variable aléatoire X, la fonction empirique s’écrit

1 n
n k∑
Gn (h) = | Xk − h | − | Xk | ,
=1

et on rappelle qu’un minimiseur de Gn est la médiane empirique m̂n = X(d n e) .

2

Cependant, dans une grande majorité des cas tels que l’estimation de la médiane géométrique
ou l’estimation des paramètres de la régression logistique, on ne sait pas calculer explicitement le
minimum de la fonction Gn . On peut néanmoins utiliser les méthodes d’optimisation déterministes
usuelles pour approcher m̂n .
Exemple 1 : la régression logistique. Dans le cadre de la régression logistique, on a

1 n   
Gn (h) = ∑
n i =1
log 1 + exp h T Xi − hT Xi Yi ,

et il n’existe pas de solution explicite. Cependant, on peut, par exemple, utiliser un algorithme de
gradient pour approcher m̂n . Celui-ci est défini de manière itérative pour tout t ≥ 0 par

mn,t+1 = mn,t − ηt ∇ Gn (mn,t )

où ηt est une suite de pas positifs (cf cours d’optimisation pour plus de précisions).
Exemple 2 : estimation de la médiane géométrique. Dans le cas de la médiane géométrique, la
fonction empirique est définie pour tout h ∈ Rd par

1 n
n k∑
Gn (h) = k Xk − h k − k Xk k
=1

et un minimiseur de Gn est donc un zéro du gradient de Gn , i.e

1 n Xk − m̂n
n k∑
0=− .
X − m̂n k
=1 k k

Là encore, il n’existe pas de solution explicite, mais on peut réécrire l’égalité précédente comme

Xk
∑nk=1 k Xk −m̂n k
m̂n =
∑nk=1 kXk −1 m̂n k

et on peut donc approcher m̂n à l’aide d’un algorithme de point fixe, conduisant à l’algorithme
1.2 M-estimateurs 11

itératif suivant (algorithme de Weiszfeld [Wei37])

Xk
∑nk=1 k Xk −mn,t k
mn,t+1 =
∑nk=1 kXk −1mn,t k

Remarque 1.2.3. A noter que l’on peut réécrire l’algorithme de Weiszfeld comme

n 1 n Xk − mn,t n
n k∑
mn,t+1 = mn,t + = mn,t − n ∇ Gn (mn,t )
∑nk=1 kXk −1mn,t k =1 k X k − m n,t k ∑k=1 kXk −1mn,t k

et l’on peut donc voir l’algorithme de Weiszfeld comme un algorithme de gradient avec

n
ηt = .
∑nk=1 kXk −1mn,t k

1.2.2 Un résultat de convergence

Le théorème suivant généralise les résultats donnés dans les remarques 1.2.1 et 1.2.2. A noter que
les hypothèses présentées ne sont pas minimales mais rendent la preuve plus accessible.

Théorème 1.2.1. On suppose que les hypothèses suivantes sont vérifiées :

• m̂n converge en probabilité vers m.
• Pour presque tout x, la fonction g( x, .) est deux fois continûment différentiable.
• Pour presque tout x, la Hessienne ∇2h g( x, .) est L( x )-lipschitz, i.e pour tout h, h0 ∈ Rd ,

∇2h g ( x, h) − ∇2h g x, h0 ≤ L( x ) h − h0


op

où k.kop est la norme spectrale.

• L( X ) et ∇2h g( X, m) admettent des moments d’ordre 1.
• La Hessienne de G en m est inversible.
Alors
√ L
 
n (m̂n − m) −−−−→ N 0, H −1 ΣH −1
n→+∞

avec h i
H = ∇2 G ( m ) et Σ = E ∇h g ( X, m) ∇h g ( X, m)T .

Démonstration. Comme m̂n est un minimiseur local de Gn , on a

1 n
n k∑
0= ∇h g ( Xk , m̂n ) .
=1

Comme pour presque tout x, la fonction g( x, .) est deux fois continûment différentiable, à l’aide
12 Introduction

d’un développement de Taylor, on a presque sûrement

1 n 1 n 1 n
n k∑ n k∑ n k∑
0= ∇ h g ( X k , m̂ n ) − ∇ h g ( X k , m ) + ∇ h g ( Xk , m )
=1 =1 =1
1 n 1 n
Z 1

n k∑ n k∑
= ∇ h g ( X k , m ) + ∇2h g ( Xk , m + t (m̂n − m)) (m̂n − m) dt
=1 =1 0

On peut donc réécrire l’égalité précédente comme

1 n
n k∑
− ∇h g ( Xk , m) = Hn (m̂n − m)
=1

avec

1 n
Z 1
Hn = ∑ ∇2h g ( Xk , m + t (m̂n − m)) dt
n k =1 0

1 n
Z 1

n k∑
∇2h g ( Xk , m) + ∇2h g ( Xk , m + t (m̂n − m)) − ∇2h g ( Xk , m) dt


=
=1 0

Comme ∇h g ( X, m) admet un moment d’ordre 2 et comme E [∇h g ( X, m)] = ∇ G (m) = 0, on

obtient à l’aide d’un TLC
1 n L
√ ∑ ∇h g ( Xk , m) −−−−→ N (0, Σ)
n k =1 n →+ ∞
h i
avec Σ := Var [∇h g( X, m)] = E ∇h g ( Xk , m) ∇h g ( Xk , m)T , et donc

√ L
nHn (m̂n − m) −−−−→ N (0, Σ) .
n→+∞

De plus, comme m̂n converge en probabilité vers m, on a

1 n
Z 1

n k∑
∇2h g ( Xk , m + t (m̂n − m)) − ∇2h g ( Xk , m) dt


=1 0
op
n
1 n
Z 1
1 1 P
n k∑
∇2h g ( Xk , m + t (m̂n − m)) − ∇2h g ( Xk , m) km̂n − mk ∑ L ( Xk ) −−−−→ 0.


≤ op
dt ≤
0 2 n k =1 n→+∞
=1

De plus, par la loi des grands nombres,

1 n P
∑
n k =1
∇2h g ( Xk , m) −−−−→ ∇2 G (m),
n→+∞

et donc Hn converge en probabilité vers H = ∇2 G (m). Comme H est positive, l’application M 7−→
M−1 est continue en H, et par continuité, Hn−1 converge en probabilité vers H −1 (même si Hn−1
1.3 Estimation en ligne 13

n’est pas nécessairement définie). Ainsi, par le lemme de Slutsky,

√ L
 
n (m̂n − m) −−−−→ N 0, H −1 ΣH −1 .
n→+∞

Ainsi, sous une certaine forme de régularité du modèle, on a une certaine forme d’efficacité asymp-
totique, i.e un résultat optimal "bornant" les résultats possibles pour les estimateurs. De plus,
lorsque l’on ne sait pas calculer explicitement m̂n et que l’on doit donc l’approcher via mn,t , si
mn,t converge vers m̂n , on obtient la convergence en loi
√  
lim lim n (mn,t − m) = N 0, H −1 ΣH −1
n→+∞ t→+∞

Ainsi les méthodes itératives sont particulièrement efficaces, mais sous une certaine forme de ré-
gularité du modèle, on ne pourra pas avoir de meilleurs résultats que la normalité asymptotique,
problème que l’on rencontrera quel que soit le type d’estimateur choisi. Cependant, pour les mé-
thodes itératives, un gros problème peut être rencontré si l’on doit traiter des données en ligne : si
on a déjà traité 1000 données (avec le temps de calcul que cela implique), que devons-nous faire
si 1000 nouvelles données arrivent ? Une option serait de tout reprendre depuis le début, ce qui
nécessite fatalement plus de calculs. S’intéresser aux estimateurs en ligne permet entre autre de
régler ce problème.

1.3 Estimation en ligne

Dans ce qui suit, on considère des variables aléatoires X1 , . . . , Xn , Xn+1 , . . . arrivant de manière sé-
quentielle. L’objectif est de mettre en place des algorithmes permettant de mettre facilement à jours
les estimateurs. Un exemple simple est celui de la moyenne. Considérant que l’on a calculé X n et
qu’une nouvelle donnée arrive, comment obtenir X n+1 en faisant le moins de calculs possibles ?
Une version brutale serait de repasser sur toutes les données afin de calculer X n+1 , ce qui repré-
senterait O((n + 1)d) nouvelles opérations. Une version plus subtile est de calculer X n+1 comme
suit :
1

X n +1 = X n + X n +1 − X n ,
n+1
ce qui, quand n est grand, représente bien évidemment beaucoup moins de calculs (O (d)). Pour
l’estimateur de la variance Sn2 , il faut se casser un peu plus la tête. Il faut d’abord remarquer que
celui-ci peut s’écrire

n n T 1 n
n k∑
Sn2 = Σ2 − Xn Xn et Σ2n = Xk XkT
n−1 n n−1 =1
14 Introduction

Ainsi, on peut construire Sn2 de manière récursive comme suit

1

X n +1 = X n + X n +1 − X n
n+1
1  
Σ2n+1 = Σ2n + Xn+1 XnT+1 − Σ2n
n+1
n+1 n+1 T
Sn2 +1 = Σ n +1 − X n +1 X n +1 .
n n

A noter qu’en plus du fait que le temps de calcul pour mettre à jours les estimateurs est réduit,
l’estimation en ligne permet de ne pas avoir à garder en mémoire toutes les données, i.e on peut
"jeter" les données dès qu’elles ont été traitées, ce qui peut permettre de réduire les coûts en terme
de mémoire. Même si dans de nombreux cas, il n’est pas possible ou évident de construire des
estimateurs en ligne, dans le cas de la minimisation de la fonction G, on peut souvent construire
ce type d’estimateurs à l’aide d’algorithmes de gradient stochastiques.

1.4 Algorithmes de gradient stochastiques

On rappelle que l’on s’intéresse à l’estimation du minimiseur de la fonction G : Rd −→ R définie

pour tout h ∈ Rd par
G (h) = E [ g ( X, h)] .

et on considère des variables aléatoires indépendantes et identiquement distribuées X1 , . . . , Xn , Xn+1 , . . .

de même loi que X et arrivant de manière séquentielle. On rappelle qu’un algorithme de gradient
pour approcher m aurait été de la forme

m t +1 = m t − η t ∇ G ( m t ) .

Cependant, ici, on n’a pas accès au gradient de G (car sous forme d’espérance). Pour régler ce
problème, on a vu précédemment que l’on peut remplacer ∇ G par le gradient de la fonction em-
pirique, ce qui représente O(nd) opérations à chaque itération, et en notant T ce nombres d’itéra-
tions, on arrive donc à O(ndT ) opérations. De plus, on a vu que ces méthodes ne permettent pas
de traiter les données en ligne. Pour pallier ces problèmes, on s’intéresse à l’algorithme de gradient
stochastique, qui permet de traiter les données en ligne, et ce, avec seulement O(nd) opérations.

1.4.1 Algorithmes de gradient stochastiques

L’algorithme de gradient stochastique, introduit par [RM51], est défini de manière récursive pour
tout n ≥ 0 par
m n + 1 = m n − γn + 1 ∇ h g ( X n + 1 , m n )
1.4 Algorithmes de gradient stochastiques 15

avec m0 borné et (γn ) est une suite de pas positifs vérifiant

∑ γn = + ∞ et ∑ γn2 < +∞. (1.3)

n ≥1 n ≥1

A noter que l’on peut réécrire l’algorithme de gradient stochastique comme

m n + 1 = m n − γn + 1 ∇ G ( m n ) + γn + 1 ξ n + 1 (1.4)

avec ξ n+1 = ∇ G (mn ) − ∇h g ( Xn+1 , mn ). De plus, en considérant la filtration (notion que l’on dé-
finira par la suite) (Fn ) engendrée par l’échantillon, i.e Fn = σ ( X1 , . . . , Xn ), (ξ n+1 ) est une suite
de différences de martingale adaptée à la filtration (Fn ), i.e comme mn est Fn -mesurable, et par
indépendance,
E [ξ n+1 |Fn ] = ∇ G (mn ) − E [∇h g ( Xn+1 , mm ) |Fn ] = 0.

On peut donc voir l’algorithme comme un algorithme de gradient bruité (par γn+1 ξ n+1 ).

Exemple 1 : la régression linéaire. On se place dans le cadre de la régression linéaire et on consi-

dère des couples de variables aléatoires i.i.d ( X1 , Y1 ) , . . . , ( Xn , Yn ) , ( Xn+1 , Yn+1 ) , . . . à valeurs dans
Rd × R. L’algorithme de gradient stochastique est alors défini récursivement pour tout n ≥ 0 par
 
θ n + 1 = θ n + γn + 1 Yn+1 − θnT Xn+1 X n +1 . (1.5)

Exemple 2 : la régression logistique. On se place dans le cadre de la régression logistique et on

considère des couples de variables aléatoires i.i.d ( X1 , Y1 ) , . . . , ( Xn , Yn ) , ( Xn+1 , Yn+1 ) , . . . à valeurs
dans Rd × {0, 1}. L’algorithme de gradient stochastique est alors défini de manière récursive pour
tout n ≥ 0 par    
θn+1 = θn − γn+1 π θnT Xn+1 − Yn+1 Xn+1 (1.6)

exp( x )
avec π ( x ) = 1+exp( x )
.

Exemples 3 : la médiane géométrique. On considère des variables aléatoires i.i.d X1 , . . . , Xn , Xn+1 , . . .

à valeurs dans Rd . L’algorithme de gradient stochastique est défini de manière récursive pour tout
n ≥ 0 par
X n +1 − m n
m n + 1 = m n + γn + 1 .
k X n +1 − m n k

1.4.2 Approche non-asymptotique

On suppose à partir de maintenant que la suite de pas γn est de la forme γn = cγ n−α avec cγ > 0
et α ∈ (1/2, 1). On voit bien que cette suite de pas vérifie la condition (1.3). Le théorème suivant
nous donne la vitesse de convergence en moyenne quadratique des estimateurs obtenus à l’aide
de l’algorithme de gradient stochastique dans le cas où la fonction G est fortement convexe.

Théorème 1.4.1. On suppose que les hypothèses suivantes sont vérifiées :

16 Introduction

1. Il existe un minimiseur m de la fonction G.

2. La fonction G est µ-fortement convexe : pour tout h ∈ Rd ,

h∇ G (h), h − mi ≥ µ kh − mk2 .

De plus, on suppose que l’hypothèse suivante est vérifiée :

(PS0) Il existe une constante positive C telle que pour tout h ∈ Rd ,
h i  
E k∇h g ( X, h)k2 ≤ C 1 + k h − mk2

Alors pour tout n ≥ 1,

   2c C
h
2
i 2α  µc  h i
C 0 c2γ E k m0 − m k2 + 1 +
γ 1− α
E kmn − mk
γ
≤ 2 exp exp − n
2α − 1 4 µnα

avec C 0 = max C, 2µ2 .



1
En d’autres termes, les estimateurs convergent en moyenne quadratique à la vitesse nα .

Démonstration. On a

kmn+1 − mk2 = kmn − mk2 − 2γn+1 h∇h g ( Xn+1 , mn ) , mn − mi + γn2 +1 k∇h g ( Xn+1 , mn )k2 .

En passant à l’espérance conditionnelle et par linéarité, on obtient donc, comme mn est Fn -mesurable,
h i h i
E kmn+1 − mk2 |Fn = kmn − mk2 − 2γn+1 hE [∇h g ( Xn+1 , mn ) |Fn ] , mn − mi + γn2 +1 E k∇h g ( Xn+1 , mn )k2 |Fn
h i
≤ kmn − mk2 − 2γn+1 h∇ G (mn ) , mn − mi + γn2 +1 E k∇h g ( Xn+1 , mn )k2 |Fn

Grâce à l’hypothèse (PS0), il vient

h i
E kmn+1 − mk2 |Fn ≤ 1 + Cγn2 +1 kmn − mk2 − 2γn+1 h∇ G (mn ) , mn − mi + Cγn2 +1 .

Par forte convexité, on obtient donc

h i
E kmn+1 − mk2 |Fn ≤ 1 − 2µγn+1 + Cγn2 +1 kmn − mk2 + Cγn2 +1 .

En passant à l’espérance, on a
h i
h i
E kmn+1 − mk2 ≤ 1 − 2µγn+1 + Cγn2 +1 E kmn − mk2 + Cγn2 +1 ,

et on conclut la preuve à l’aide du lemme suivant [BM13]

1.4 Algorithmes de gradient stochastiques 17

Lemma 1.4.1. Soit (δn ) une suite positive vérifiant

δn+1 ≤ 1 − 2µγn+1 + 2L2 γn2 +1 δn + 2σ2 γn2 +1

avec γn = cγ n−α , cγ , L ≥ µ > 0, σ2 ≥ 0 et α ∈ (1/2, 1). Alors pour tout n ≥ 1,

σ2 4cγ σ2
  
 µ
1− α

2 2 2α
δn ≤ 2 exp − n exp 2L cγ δ0 + 2 +
4 2α − 1 L µnα
√
On admettra ce lemme. En prenant C 0 = max C, 2µ2 , il suffit de vérifier que C 0 /2 ≥ µ et que


l’on a également
h i
h i
E kmn+1 − mk2 ≤ 1 − 2µγn+1 + C 0 γn2 +1 E kmn − mk2 + Cγn2 +1 ,

et les hypothèses du lemme sont donc vérifiées, ce qui conclut la preuve.

Afin de simplifier les preuves par la suite, on donne maintenant une proposition (admise) que l’on
peut voir comme une généralisation du lemme précédent.

Proposition 1.4.1. Soit δn , γn deux suites positives telles que

• γn = cγ n−α avec cγ > 0 et α ∈ (1/2, 1).
• Il existe un rang n0 , une constante c0 ∈ 0, γn−01 et une suite positive vn telle que pour tout n ≥ n0 ,

δn+1 ≤ (1 − c0 γn+1 ) δn + γn+1 vn+1 .

Alors pour tout n ≥ 2n0 ,

!
 c c  n/2−1
∑
0 γ 1− α
δn ≤ exp − n δn0 + γk + 1 v k + 1 + max v k +1
4 k = n0 n/2≤k +1≤n−1

En particulier, si vn = Cv (ln n) β nv avec β ≥ 0 et v ∈ R, alors

δn = O (vn ) .

On donne maintenant un lemme qui sera très important pour établir les vitesses de convergence
preque sûre des algorithmes de gradient stochastiques. Ce lemme est une application directe de la
proposition précédente.

Lemma 1.4.2. Soient An , Bn , rn des suites de variables aléatoires positives telles que rn converge presque
sûrement vers 0 et
An+1 = (1 − cγn+1 ) An + γn+1 rn ( An + Bn )

avec γn = cγ n−α . De plus, on suppose

Bn = O (vn ) p.s
18 Introduction

avec vn = Cv nv (ln n) β avec v ∈ R et β ≥ 0. Alors

An = O (vn ) p.s.

Proof of Lemma 1.4.2. Afin de simplifier la preuve (et quitte a considérer n suffisamment grand),
on va supposer que pour tout n ≥ 0, cγn+1 ≤ 1. On considère maintenant l’évènement En,c =
{|rn | ≤ c/2}, et on a donc 1 En,c
C qui converge presque sûrement vers 0. On peut donc réécrire A n +1

comme
=:δn
c z }| {
A n +1 ≤ (1 − cγn+1 ) An + γn+1 ( An + Bn ) + γn+1 rn ( An + Bn ) 1 En,c
C
2
 c  c
≤ 1 − γn+1 An + γn+1 Bn + δn 1 En,c C
2 2

Par récurrence, on peut facilement montrer que pour tout n ≥ 0, on a

c n −1 n −1

2 k∑ ∑ β̃n,k+1 δk 1Ek,cC
An ≤ β̃ n,0 A0 + β̃ γ B
n,k +1 k +1 k +
=0 k =0
| {z } | {z }
=:A1,n =:A2,n

avec β̃ n,k = ∏nj=k+1 1 − 2c γ j et β̃ n,n = 1. Avec des calculs classiques, on peut facilement montrer


−1 −1
que β̃ n,0 converge à vitesse exponentielle. De plus, on peut réécrire A2,n = β̃ n,0 ∑nk= 0 β̃ k,0 δk 1 EC et
k,c
comme 1 En,c
C converge presque sûrement vers 0, la somme est presque sûrement finie et on obtient

donc


A2,n = O β̃ n,0 p.s

et ce terme converge donc à vitesse exponentielle. Enfin, il existe une variable aléatoire B telle que
pour tout n ≥ 1 on a Bn ≤ Bvn presque sûrement, et on obtient donc la relation de récurrence
 c  c  c  c
A1,n+1 = 1 − γn+1 A1,n + γn+1 Bn ≤ 1 − γn+1 A1,n + Bγn+1 vn
2 2 2 2

et en appliquant la proposition 1.4.1, on obtient

A1,n = O (vn ) p.s.

1.4.3 Exemple : regression lineaire

On se place dans le cadre du modèle linéaire défini par (1.1) et on rappelle que sous certaines
hypothèses, θ est l’unique minimiseur de la fonction G : Rd −→ R+ définie pour tout h ∈ Rd par
 2 
1
G (h) = E Y − X h
T
.
2
1.4 Algorithmes de gradient stochastiques 19

Théorème 1.4.2. On suppose que e admet un moment d’ordre 2 et que X admet un moment d’ordre 4. De
plus, on suppose que la matrice E XX T est définie positive et on note µ sa plus petite valeur propre. La
 

suite d’estimateurs du gradient (θn ) définie par (1.5) vérifie pour tout n ≥ 0,
   2c C
h
2
i 2α  µc  h i
E k m0 − m k2 + 1 +
γ 1− α
E kθn − θ k Cc2γ
γ
≤ 2 exp exp − n
2α − 1 4 µnα
n   h i h io
avec C = max 2E e2 E k X k2 , 2E k X k4 .

On admettra ce théorème. Dans la Figure 1.1, on s’intéresse à l’évolution de l’erreur quadratique

moyenne des estimateurs (obtenus à l’aide d’algorithmes de gradient stochastiques) du paramètre
de la régression linéaire en fonction de la taille d’échantillon n. Pour cela, on considère le modèle

θ = (−4, −3, −2, −1, 0, 1, 2, 3, 4, 5)T ∈ R10 , X ∼ N (0, I10 ) , e ∼ N (0, 1).

De plus, on choisit cγ = 1 et α = 0.5, 0.660.75 ou 1. Enfin, on a calculé l’erreur quadratique moyenne

des estimateurs en générant 50 échantillons de taille n = 1000. On voit bien que l’on a une décrois-
sance assez rapide de l’erreur quadratique moyenne, et lorsque l’on prend l’échelle logarithmique,
une heuristique de pente nous donne que pour n ≥ 100, on a bien une pente proche de −α.

1.00
Erreur quadratique moyenne

Valeur de α
0.5
0.66
0.10
0.75
1

0.01

1 10 100 1000
Taille de l'échantillon

F IGURE 1.1 – Evolution de l’erreur quadratique moyenne de θn en fonction de la taille d’échantillon

n dans le cadre de la régression linéaire.
20 Introduction
Chapitre 2

Martingales

On a vu que l’on peut considérer l’algorithme de gradient stochastique comme un algorithme

de gradient bruité par le terme γn+1 ξ n+1 , où (ξ n ) est une suite de différences de martingale par
rapport à une filtration (Fn ). L’objectif de ce chapitre est donc, dans un premier temps, de définir
les notions de filtration et de martingale. Dans un deuxième temps, on donnera des résultats de
convergence type loi des grands nombres et TLC pour les martingales, qu’elles soient réelles ou
vectorielles.

2.1 Martingales réelles

Cette section s’inspire très largement de [BC07] et [Duf90].

2.1.1 Définitions

Dans ce qui suit, on considère un espace probabilisé (Ω, A, P).

Definition 2.1.1. On appelle filtration (Fn )n≥0 de (Ω, A, P) une suite croissante de sous-tribus de A, i.e
une suite de tribus telle que
F0 ⊂ F1 ⊂ ... ⊂ A.

On dit qu’une suite de variables aléatoires ( Xn )n≥0 est adaptée à la filtration (Fn )n≥0 si pour tout n, Xn est
Fn -mesurable.

En considérant une suite de variables aléatoires ( Xn )n≥1 , un exemple classique de filtration est
de considérer la suite des tribus engendrée par les Xi . Plus précisément, pour tout n, on consi-
dère la plus petite tribu rendant ( X1 , . . . , Xn ) mesurable et on la note Fn = σ ( X1 . . . , Xn ). Alors,
F = (Fn ) est une filtration. Rappelons également au passage que par définition de l’espérance
conditionnelle, E [ Xn+1 |Fn ] est Fn -mesurable.

Definition 2.1.2. Soit M = ( Mn )n≥0 une suite de variables aléatoires adaptée à une filtration F = (Fn ).
22 Martingales

On dit que M est une martingale par rapport à la filtration F si pour tout n ≥ 0, Mn est intégrable et

E [ Mn+1 |Fn ] = Mn .

Exemple : On considère une suite de variables aléatoires indépendantes ( Xn )n≥1 et on note

n
Mn = ∑ Xk − E [ Xk ] .
k =1

Alors Mn est une martingale par rapport à la filtration engendrée par les Xi .

2.1.2 Théorème de Robbins-Siegmund

Le théorème de Robbins-Siegmund suivant est crucial pour démontrer la consistance des estima-
teurs obtenus à l’aides d’algorithmes stochastiques, et particulièrement pour les algorithmes de
gradient.

Théorème 2.1.1 (Robbins-Siegmund). Soit (Vn ) , ( An ) , ( Bn ) , (Cn ) trois suites de variables réelles posi-
tives adaptées à une filtration F . On suppose que

E [Vn+1 |Fn ] ≤ (1 + An ) Vn + Bn − Cn

et que les suites ( An ) , ( Bn ) vérifient

∑ An < +∞ p.s et ∑ Bn < +∞ p.s.

n ≥0 n ≥0

Alors Vn converge presque sûrement vers une variable aléatoire V∞ finie et

∑ Cn < +∞ p.s.
n ≥0

On admettra ce théorème mais sa preuve est disponible dans [Duf90] ou [BC07], ainsi que dans la
version longue.
Exemple : estimation en ligne des quantiles. Soit X1 , . . . , Xn+1 , . . . des variables aléatoires indé-
pendantes et identiquement distribuées. Soit p ∈ (0, 1), et on s’intéresse à l’estimation en ligne
du quantile d’ordre p, que l’on notera m. Pour cela, on considère l’estimateur obtenu à l’aide de
l’algorithme de Robbins-Monro [RM51], défini de manière récursive pour tout n ≥ 0 par


m n + 1 = m n − γn + 1 1 X n +1 ≤ m n − p .

avec
∑ γn + 1 = + ∞ et ∑ γn2 +1 < +∞.
n ≥0 n ≥0
2.1 Martingales réelles 23

On pose alors Vn = (mn+1 − m)2 , et on a

2
Vn+1 = Vn − 2γn+1 (mn − m) 1 Xn+1 ≤mn − p + γn2 +1 1 Xn+1 ≤mn − p

≤ Vn − 2γn+1 (mn − m) 1 Xn+1 ≤mn − p + γn2 +1

On considère la filtration (Fn ) engendrée par l’échantillon, i.e définie pour tout n ≥ 1 par Fn =
σ ( X1 , . . . , Xn ). Comme l’estimateur mn ne dépend que de X1 , . . . , Xn , il est Fn -mesurable, et on a
donc, en notant FX la fonction de répartition de X1 , et en remarquant que p = FX (m),

E [Vn+1 |Fn ] ≤ Vn − 2γn+1 (mn − m) E 1 Xn+1 ≤mn |Fn − p + γn2 +1

 

= Vn − 2γn+1 (mn − m) ( FX (mn ) − FX (m)) +γn2 +1

| {z }
=:An

Comme la fonction de répartition est croissante, on a An ≥ 0 et comme ∑n≥0 γn2 +1 < +∞, le
théorème de Robbins-Siegmund nous donne que Vn converge presque sûrement vers une variable
aléatoire finie et que
∑ An < +∞ p.s.
n ≥0

Or , comme la somme des γn diverge, cela implique que lim infn (mn − m) ( FX (mn ) − F (m)) = 0.
Si on suppose que la fonction F est strictement croissante sur un voisinage de F, on obtient

lim inf |mn − m| = 0,

n

et comme |mn − m| converge vers une variable aléatoire finie, cela implique que |mn − m| converge
presque sûrement vers 0, i.e que l’estimateur est fortement consistant.

Exemple : estimation des quantiles de la loi exponentielle. On considère X ∼ E (1) et on s’inté-

resse à l’estimation des quantiles d’ordre 0.25 et 0.75. Figure 2.1, on voit que dans les deux cas les
estimateurs convergent assez rapidement vers le quantile.

1.5

0.4

1.2
0.3
mn

mn

0.2 0.9

0.1
0.6

0.0

0.3
0 250 500 750 1000 0 250 500 750 1000
n n

F IGURE 2.1 – Evolution de l’estimation des quantiles d’ordre 0.25 (à gauche) et 0.75 à droite pour
la loi exponentielle de paramètre 1.
24 Martingales

2.1.3 Lois des grands nombres

Dans ce qui suit, on dit qu’une martingale ( Mn ) est de carré intégrable si pour tout n ≥ 0,
E Mn2 < +∞.
 

Definition 2.1.3. Soit ( Mn ) une martingale de carré intégrable. On appelle processus croissant associé à
( Mn ) la suite (h Min )n définie par h Mi0 = 0 et pour tout n ≥ 0 par
h i
h Min+1 = h Min + E ( Mn+1 − Mn )2 |Fn .

En d’autres termes, si pour tout k ≥ 0 on note ξ k+1 = Mk+1 − Mk la différence de martingale, on a

pour tout n ≥ 1
n
∑E ξ k2 |Fk−1 .
 
h M in =
k =1

Ainsi, on peut voir le processus croissant comme la somme des variances conditionnelles des dif-
férences de martingales. On peut maintenant introduire les lois des grands nombres pour les mar-
tingales de carré intégrable.

Théorème 2.1.2 (Première loi des grands nombres). Soit ( Mn ) une martingale de carré intégrable.

1. Si limn→+∞ h Min < +∞ presque sûrement, alors la suite ( Mn ) converge presque sûrement vers
une variable aléatoire M∞ .
 
Mn
2. Si limn→+∞ h M in = +∞ presque sûrement, alors la suite h M in
converge presque sûrement vers
0.

En d’autres termes, si le processus croissant converge presque sûrement, alors ( Mn ) = O(1)

presque sûrement, et si il diverge, alors

| Mn | = o (h Min ) p.s.

On admettra ce résultat. La preuve est disponible dans la version longue ainsi que dans [BC07] et
[Duf97].
Application au bandit à deux bras : Le problème du bandit à deux bras consiste à considérer
une machine à sous avec deux leviers (A et B). Pour chacun des leviers, le gain est de 1 avec
probabilité θ A ou θ B et de 0 avec probabilité 1 − θ A ou 1 − θ B . Dans ce qui suit, on suppose θ A , θ B ∈
(0, 1) et θ A 6= θ B . A chaque temps n, le joueur decide d’actionner le levier Un (et donc Un = A
ou B) par rapport à ce qu’il a pu observer avant. On note Xn son gain au temps n et on a donc
P [ Xn = 1|Un = A] = θ A ou P [ Xn = 1|Un = B] = θ B , i.e Xn |Un ∼ B (θUn ). L’objectif du joueur est
de trouver la stratégie (Un ) qui maximise son gain moyen asymptotique, i.e en notant

1 n
n k∑
Gn = Xk
=1
2.1 Martingales réelles 25

l’objectif est de trouver la stratégie (Un ) qui permette d’obtenir

p.s
Gn −−−−→ max {θ A , θ B } .
n→+∞

En effet, si θ A > θ B , par exemple, il faudrait toujours actionner le levier A, et on a donc Gn qui
convergerait presque sûrement vers θ A et inversement. Dans ce qui suit, on note NA,n et NB,n le
nombre de fois où chacun des leviers a été tiré au temps n, i.e

n n
NA,n = ∑ 1Uk = A , et NB,n = ∑ 1U = B
k
k =1 k =1

On note maintenant
n
Mn = ∑ Xk − θ A NA,n − θB NB,n
k =1

On considère la filtration (Fn ) définie pour tout n ≥ 0 par Fn = σ ( X1 , . . . , Xn , U1 , . . . , Un+1 ), et on

a
E [ Mn+1 |Fn ] = E [ Xn+1 |Fn ] − θ A 1Un+1 = A − θ B 1Un+1 = B + Mn


et comme Xn+1 |Un+1 ∼ B θUn+1 , Mn est une martingale, et elle est clairement de carré intégrable.
De plus, on a

n h i
h M in = ∑E ( Xk − θ A 1Uk = A − θ B 1Uk = B )2 |Fk−1
k =1
n h i
= ∑ E ( X k − θ Uk ) 2
| Uk
k =1
n
= ∑ V [Xk |Uk ]
k =1
n
= ∑ θ A (1 − θ A ) 1U = A + θ B (1 − θ B ) 1U = B
k k
k =1

= θ A (1 − θ A ) NA,n + θ B (1 − θ B ) NB,n .

Afin d’appliquer le 2ème point de la loi des grands nombres, on va montrer que le crochet diverge.
Pour cela, il suffit de remarquer que NA,n + NB,n = n, et donc soit NA,n ≥ n/2, soit NB,n ≥ n/2.
Ainsi,
n
h Min ≥ min {θ A (1 − θ A ) , θ B (1 − θ B )} −−−−→ +∞.
| {z } 2 n→+∞
>0

Mn p.s
Par la loi des grands nombres, −−−−→
h Min n→+∞
0. On suppose maintenant qu’il existe des constantes
l A , l B ∈ [0, 1] telles que
NA,n p.s NB,n p.s
−−−−→ l A et −−−−→ l B .
n n→+∞ n n→+∞
26 Martingales

On va maintenant montrer que Gn converge presque sûrement vers θ A l A + θ B l B . On a

1 NA,n N
Gn − θ A l A − θ B l B = Mn + θ A + θ B B,n − θ A l A − θ B lB
n n  n
h M i n Mn
  
NA,n NB,n
= + θA − l A + θB − lB
n h Mi n n
| {z n} | {z }
p.s p.s
−−−−
n→+∞
→0 −−−−
n→+∞
→0

h M in
et comme n ∈ [0, 1], on obtient
p.s
Gn −−−−→ θ A l A + θ B l B .
n→+∞

Ainsi, une bonne stratégie consiste à obtenir l A = 1 si θ A > θ B et inversement.

On peut remarquer que la différence avec la loi des grands nombres pour des variables aléatoires
i.i.d est que l’on se passe des hypothèses d’indépendance et d’identique distribution, mais le prix
à payer est que l’on doit faire des hypothèses sur le comportement du crochet h Min . A noter éga-
lement que dans les exemples précédents, on aurait pu s’attendre à obtenir une meilleure vitesse
de convergence, ce que nous donne la deuxième loi des grands nombres suivante.

Théorème 2.1.3 (Deuxième loi des grands nombres). Soit ( Mn ) une martingale de carré intégrable.
p.s
1. Si h Min −−−−→ +∞, alors
n→+∞

Mn2 = o (h M in ln (h M in ))1+δ p.s.

2. De plus, si il existe des constantes a > 2 et b > 0 telles que

 h i a/2
E | Mn+1 − Mn | a |Fn ≤ b E ( Mn+1 − Mn )2 |Fn
 
p.s

alors
Mn2 = O (h M in ln (h Min )) p.s.

On admettra ce résultat. La preuve est disponible dans la version longue ainsi que dans [BC07] et
[Duf97]. A noter que les hypothèses (notamment pour la deuxième partie du théorème) peuvent
sembler indigestes, mais on peut voir dans l’exemple suivant qu’elles sont généralement "facile-
ment" vérifiables.

Exemple : Soit Mn = ∑nk=1 ξ k avec E [ξ k |Fk−1 ] = 0. Si il existe une constante C telle que pour tout
k, E ξ k2 |Fk−1 ≤ C, alors pour tout δ > 0,
 

 
Mn2 = o n(ln n)1+δ p.s
2.1 Martingales réelles 27

ce que l’on peut réécrire comme

2
1 n (ln n)1+δ
 

n k∑
ξk =o p.s.
=1
n

Remarque 2.1.1. A noter que l’on aurait pu retrouver directement le premier point de cet exemple avec
une application directe du théorème de Robbins-Siegmund. En effet, pour tout δ > 0, on peut considérer la
2
variabe aléatoire Vn = 1
n(ln n)1+δ
| Mn | 2 = n
(ln n)1+δ
1
n Mn . Comme Mn est Fn -mesurable et par linéarité,
on a
h i h i
E | Mn+1 |2 |Fn = Mn2 + 2E [ξ n+1 |Fn ] Mn + E |ξ n+1 |2 |Fn
h i
= | Mn |2 + E |ξ n+1 |2 |Fn

Ainsi, on obtient

1 2 1 h
2
i
E [Vn+1 |Fn ] = | M n | + E | ξ n + 1 | |F n
(n + 1)(ln(n + 1))1+δ (n + 1)(ln(n + 1))1+δ
n(ln n)1+δ 1 h
2
i
= V n + E | ξ n + 1 | |F n
(n + 1)(ln(n + 1))1+δ (n + 1)(ln(n + 1))1+δ
1
≤ Vn + C.
(n + 1)(ln(n + 1))1+δ

En appliquant le théorème de Robbins-Siegmund, on a donc Vn qui converge presque sûrement vers une
variable aléatoire finie, ce que l’on peut réécrire comme

2
(ln n)1+δ
 
1
Mn =O a.s.
n n

La proposition suivante donne une encore meilleure vitesse de convergence, mais au prix d’hypo-
thèses un peu plus fortes.

Proposition 2.1.1. Soit (ξ n ) une suite de différences de martingales adaptée à une filtration (Fn )n . Sup-
posons qu’il existe des constantes a > 2 et Ca ≥ 0 telles que E |ξ k | a |Fk−1 ≤ Ca presque sûrement,
 

alors,
2
1 n
 
ln n
n k∑
ξk =O p.s.
=1
n

Application au bandit à deux bras : En reprenant les notations de l’exemple du bandit à deux
bras, on a
| Mn+1 − Mn | ≤ 1,
28 Martingales

et on peut donc appliquer la Proposition 2.1.1, on a

2  
1 ln n
Mn =O p.s
n n

NA,n NB,n
et si on a les vitesses de converges de n et n vers l A , l B , on obtient donc une meilleur vitesse
de convergence pour le gain moyen Gn .

A noter que pour ces exemples, avec des hypothèses un peu plus restrictives, on peut trouver une
meilleure vitesse grâce à la loi du log-itéré pour les martingales. Celle-ci est disponible dans la
verson longue ainsi que dans [DST90] et [Duf90] (page 31).

Estimation en ligne des quantiles : A l’aide de la loi du log-itéré, on peut montrer (cf version
longue) que l’estimateur en ligne des quantiles vérifie
 
2 ln n
|mn − m| = O p.s
nα

Exemple : estimation de la médiane de la loi exponentielle. On considère X ∼ E (1) et on s’in-

téresse à la vitesse de convergence des estimateurs de la médiane. Figure 2.2, on se concentre sur
l’erreur quadratique moyenne estimée à l’aide de 50 échantillons. On voit bien que les estimateurs
convergent très rapidement vers la médiane.

0.100
Erreur quadratique

0.010

0.001

1 10 100 1000
n

F IGURE 2.2 – Evolution de l’erreur quadratique moyenne des estimateurs en ligne de la médiane
d’une loi exponentielle de paramètre 1.

2.1.4 Théorème limite centrale

On s’intéresse ici à l’obtention d’un TLC pour les martingales de carré intégrable, i.e on cherche à
transposer le TLC usuel aux martingales.

Théorème 2.1.4. Soient ( Mn ) une martingale de carré intégrable et an une suite positive, croissante et
divergente. On suppose que les hypothèses suivantes sont vérifiées :
2.1 Martingales réelles 29

1. Il existe σ2 ≥ 0 telle que

h M in P
−−−−→ σ2 .
an n→+∞

2. La condition de Lindeberg est vérifiée, i.e pour tout e > 0,

n
1 h i
P
an ∑E ( Mk − Mk−1 )2 1| Mk − Mk−1 |≥e√an |Fk−1 −−−−→ 0.
n→+∞
k =1

Alors
1 L
√ Mn −−−−→ N 0, σ2 .


an n→+∞

A noter que l’on s’est débarrassé des conditions d’indépendance et d’identique distribution, mais
cela au prix de la condition (indigeste) de Lindeberg. Cependant, celle-ci est vérifiée dès que la
condition (relativement plus digeste) de Lyapunov est vérifiée, i.e elle est vérifiée si il existe a > 2
tel que
n
1  P
∑E | Mk − Mk−1 | a |Fk−1 −−−−→ 0.

a
2 n→+∞
an k =1

En effet, en notant ξ n+1 = Mn+1 − Mn , et comme a > 2

h i h i 2− a h i
E ξ k2 1|ξ k |≥e√an |Fk−1 ≤ E |ξ k | a |ξ k |2−a 1|ξ k |≥e√an |Fk−1 ≤ e2−a an 2 E |ξ k | a 1|ξ k |>e√an |Fk−1
2− a
≤ e2−a an 2 E |ξ k | a |Fk−1 .
 

On obtient donc
n n
1 h i
2− a 1
∑ E 2 √ |F
∑E |ξ k | a |Fk−1
 
( M k − M k −1 ) 1 | Mk − Mk−1 |≥e an k −1 ≤ e a
an k =1 an2 k =1

et on a donc bien que la condition de Lindeberg est vérifiée si la condition de Lyapunov l’est.
En pariculier, lorsque an = n, si il existe des constantes a > 2 et Ca telles que pour tout k ≥ 0,
E |ξ k+1 | a |Fk−1 ≤ Ca , alors la condition de Lindeberg est vérifiée.
 

Exemple : Soit Mn = ∑nk=1 ξ k avec E [ξ k |Fk−1 ] = 0 et telle qu’il existe σ2 vérifiant

1 n  P
∑ E ξ k2 |Fk−1 −−−−→ σ2 .

n k =1 n→+∞

Si il existe des constantes a > 2 et Ca ≥ 0 telles que E |ξ k | a |Fk−1 ≤ Ca , alors

 

1 L
√ Mn −−−−→ N 0, σ2 .


n n→+∞

Application au bandit à deux bras : On reprend les notations de l’exemple du bandit à deux bras,
30 Martingales

et on cherche maintenant à estimer θ A , θ B . Pour cela, on considère les estimateurs naturels

n n
1 1
θ A,n =
NA,n ∑ 1U = A,X =1
k k
et θ B,n =
NB,n ∑ 1U =B,X =1
k k
k =1 k =1

M A,n
On note M A,n = ∑nk=1 1Uk = A,Xk =1 − NA,n θ A , i.e on a θ A,n − θ A = NA,n . On remarque que

E [ M A,n+1 |Fn ] = M A,n + E 1 Xn+1 =1 |Un+1 1Un+1 = A − θ A 1Un+1 = A = M A,n

 

et M A,n est donc une martingale (de carré intégrable). De plus,

n h i n
h M A in = ∑ E ( 1 Xk =1 − θ A ) 2
| Uk 1Uk = A = ∑ V [Xk |Uk = A] 1U = A = θ A (1 − θ A ) NA,n
k
k =1 k =1

et par la première loi des grands nombres, si limn→+∞ NA,n < +∞ p.s, alors M A,n converge presque
sûrement vers une variable aléatoire finie, mais θ A,n ne converge pas nécéssairement vers θ A . Par
contre, si NA,n diverge presque sûrement, la loi des grands nombres nous donne que M A,n =
o (h M A in ) p.s, i.e θ A,n converge presque sûrement vers θ A . On peut bien évidemment faire le même
travail pour obtenir la convergence de θ B,n . On s’intéresse maintenant à la normalité asymptotique
NA,n p.s
de ces estimateurs. On suppose maintenant que n − −−−→ l A
n→+∞
> 0, et on a

1 p.s
h M A in −−−−→ θ A (1 − θ A ) l A .
n n→+∞

De plus, on remarque que | M A,k − M A,k−1 | ≤ 1, et la condition de Lindeberg est donc vérifiée. Le
TLC pour les martingales nous donne alors

1 L
√ M A,n −−−−→ N (0, θ A (1 − θ A ) l A )
n n→+∞

Ainsi, à l’aide du Théorème de Slutsky, on obtient

√ √ M A,n √ θ A (1 − θ A )
 
n L
n (θ A,n − θ ) = n = nM A,n −−−−→ N 0, .
NA,n NA,n n→+∞ lA
| {z }
p.s
−−−−
n→+∞
→l −A 1

Bandits à deux bras et efficacité asymptotique : On a vu que l’on peut avoir des estimateurs effi-
caces et asymptotiquement normaux de θ A , θ B . Se pose maintenant la question de savoir comment
obtenir une stratégie (Un ) permettant d’obtenir le meilleur gain moyen asymptotique ainsi que
d’obtenir son efficacité asymptotique. Une façon naturelle de choisir un levier au temps n serait de
prendre
Un = A1θ A,n ≥θB,n + B1θB,n >θ A,n ,

i.e on choisi le levier A si l’estimateur de θ A est "meilleur" que celui de θ B (et inversement). Bien
2.1 Martingales réelles 31

que cette stratégie soit naturelle, elle pose le problème quelle peut se faire piéger. Par exemple, si
on choisit U1 = A et que l’on perd le premier tirage, i.e X1 = 0, puis que l’on choisisse U2 = B et
que l’on obtienne X2 = 1, alors θ A,2 = 0 < θ B,2 = 1. Pour toute la suite, on aura θ B,n > 0 = θ A,n ,
i.e on ne choisira jamais le levier A. On a donc Gn qui converge presque sûrement vers θ B , et
si θ A > θ B , on ne peut donc pas converger vers la bonne solution. Une solution pour pallier ce
problème est de forcer le choix du levier de temps en temps. Plus précisément, on considère (cn )
une suite croissante de N, et note Ic = {cn , n ≥ 1} l’ensemble des valeurs de la suite (en d’autres
termes, on a pris un sous-ensemble de N). On adopte alors la stratégie suivante :




 A si θ A,n−1 ≥ θ B,n−1 et n ∈
/ Ic

B,n−1 > θ A,n−1 et n ∈
 B si θ / Ic
Un =


 A si ∃k ≥ 1, n = c2k

 B si ∃k ≥ 0, n = c
2k +1

A noter qu’avec cette stratégie, on choisit obligatoirement une infinité de fois A et B, et on a donc
NA,n et NB,n qui divergent presque sûrement, i.e θ A,n et θ B,n convergent presque sûrement vers θ A
et θ B . De plus, pour simplifier les notations, on suppose que θ A > θ B (l’autre cas étant analogue).
On suppose maintenant que n = o (cn ), et on remarque que

NB,n 1 1 n 1 1 n
= Card {k, c2k+1 ≤ n} + ∑ 1θB,k >θ A,k ≤ Card {k, ck ≤ n} + ∑ 1θB,k >θ A,k .
n n n k =1 n| {z } n k =1
=:Cn

Comme les deux estimateurs θ A,n et θ B,n sont consistants, on a 1θB,n >θ A,n qui converge presque sû-
rement vers 0 et donc ∑k≥0 1θB,k >θ A,k < +∞ p.s, i.e on a

1 n
 
1
n k∑
1θB,k >θ A,k = O p.s.
=1
n

Il reste à montrer que Cn = o (n). Pour cela, on suppose par l’absurde que ce n’est pas le cas, i.e
Cn
lim infn n > 0, i.e il existe η > 0, nη ≥ 0 tels que pour tout n ≥ nη , Cn ≥ dηne. On a alors pour
tout n ≥ nη

n
Cn = max {k, ck ≤ n} ≥ dηne ⇔ cdηne ≤ n ⇔ ≥1
cdηne

n n dηne
ce qui est contradictoire avec n = o (cn ) car pour tout n ≥ nη , cdηne ≤ dηne cdηne −
−−−→ 0. On obtient
n→+∞
NB,n NA,n
donc que n converge presque sûrement vers 0 et donc que n converge presque sûrement vers
1, i.e que l A = 1 et l B = 0. On obtient donc

p.s
Gn −−−−→ max {θ A , θ B } .
n→+∞

On s’intéresse maintenant à l’efficacité asymptotique de Gn . Pour cela, on suppose maintenant que

32 Martingales

n2 = o (cn ). On rappelle que l’on peut écrire

√ √ √
   
1 NA,n NB,n
n ( Gn − l A θ A − l B θ B ) = √ Mn − nθ A − lA − nθ B − lB
n n n

Ici, on a l A = 1, l B = 0 et on a donc

1 N N p.s
h Min = A,n θ A (1 − θ A ) + B,n θ B (1 − θ B ) −−−−→ θ A (1 − θ A ) .
n n n n →+ ∞

De plus, pour tout n ≥ 1, | Mn − Mn−1 | ≤ 1 et la condition de Lindeberg est donc vérifiée, et on

obtient
√ L
nMn −−−−→ N (0, θ A (1 − θ A )) .
n→+∞

Comme l A = 1 et l B = 0, on a

√ √ NA,n − n
   
NA,n NB,n N N
nθ A − lA + nθ B − lB = θA √ + θ B √B,n = √B,n (θ B − θ A )
n n n n n

et il suffit d’avoir la vitesse de convergence de NB,n pour conclure. Plus précisément, il suffit de
Cn √

montrer que √ −−−−→ 0, i.e Cn = o
n n→+∞
n . Supposons par l’absurde que ce n’est pas le cas, i.e il
√
existe η 0 > 0 et nη 0 tels que pour tout n ≥ nη 0 , Cn ≥ dη 0 ne, on a alors pour tout n ≥ nη 0 ,

√ n
Cn ≥ dη 0 ne ⇔ cdη 0 √ne ≤ n ⇔ ≥ 1,
cdη 0 √ne

Nn,B p.s
ce qui est en contradiction avec cn = o n2 et on a donc


√ − −−−→ 0. Avec des calculs analogues
n n→+∞
pour le cas où θ A < θ B , on obtient donc
√ L2


n ( Gn − max {θ A , θ B }) −−−−→ N 0, σA,B
n→+∞

2
avec σA,B = θ A (1 − θ A ) 1 θ A > θ B + θ B (1 − θ B ) 1 θ B > θ A .

Application à l’estimation en ligne des quantiles : On reprend le cadre de l’estimation en ligne

du quantile m d’ordre p. A l’aide du TLC pour les martingales, on peut montrer que (cf version
longue)
p (1 − p )
 
1 L
√ Mn −−−−→ N 0,
γn n→+∞ 2cγ f (m)
et on obtient la loi asymptotique asymptotique des estimateurs, i.e

p (1 − p )
 
1 L
√ (mn − m) −−−−→ N 0, ,
γn n→+∞ 2 f (m)
2.2 Martingales vectorielles 33

ce que l’on peut réécrire

p
2 f (m) L
Qn := nα/2 (mn − m) −−−−→ N (0, 1)
n→+∞
p
cγ p (1 − p )

En effet, Figure 2.3, on s’intéresse à la densité de Qn que l’on compare à celle d’une loi normale
centrée réduite. La densité de Qn est estimée à l’aide de 500 échantillons. On voit bien que les deux
densités sont de plus en plus proches lorsque la taille d’échantillon n augmente.

n=500 n=5000

0.4

0.3
f(x)

0.2 Loi normale

Qn

0.1

0.0

−5.0 −2.5 0.0 2.5 5.0 −5.0 −2.5 0.0 2.5 5.0
x

F IGURE 2.3 – Comparaison de la densité de Qn , pour n = 500 (à gauche) et n = 5000 (à droite), et

de la densité d’une loi normal centrée réduite.

2.2 Martingales vectorielles

Dans cette section, on s’intéresse aux vitesses de convergence des martingales vectorielles. Plus
précisément, on établit, sous certaines conditions, les vitesses de convergence presque sûre ainsi
que la normalité asymptotique des martingales.

2.2.1 Définition
h i
Dans ce qui suit, on suppose que Mn ∈ Rd est de carré intégrable, i.e E k Mn k2 < +∞, où k.k est
la norme euclidienne.

Definition 2.2.1. Soit F = (Fn ) une filtration, et ( Mn ) une suite adaptée à F .

— ( Mn ) est une martingale de carré intégrable adaptée à F si

E [ Mn+1 |Fn ] = Mn .

— La variation quadratique prévisible de ( Mn ), aussi appelée crochet, est le processus h Mi = (h M in )n

34 Martingales

défini par h Mi0 = M0 M0T et pour tout n ≥ 1, par h M in = h Min−1 + ∆n , avec

h i h i
∆n = E ( Mn − Mn−1 ) ( Mn − Mn−1 )T |Fn−1 = E Mn MnT − Mn−1 MnT−1 |Fn−1

Remarquons que l’on peut réécrire le crochet comme

n h i
h M i n = h M i0 + ∑E ( Mn − Mn−1 ) ( Mn − Mn−1 )T |Fn−1 .
k =1

En d’autres termes, en notant ξ n = Mn − Mn−1 la différence de martingale (on peut remarquer que
E [ξ n |Fn−1 ] = 0), on a
n h i
h M i n = h M i0 + ∑ E ξ n ξ T
n |F n − 1
k =1

et on peut donc voir le crochet, à division par n près, comme la moyenne des variances condition-
nelles des différences de martingale, i.e comme la moyenne des variances conditionnelles entre les
Mk et Mk−1 .

2.2.2 Vitesses de convergence des martingales vectorielles

Le théorème suivant donne un premier résultat sur les vitesses de convergence des martingales
vectorielles.

Théorème 2.2.1. On considère Mn = ∑nk=1 ξ k avec pour tout k ≥ 1, E [ξ k |Fk−h1 ] = 0. Onisuppose

également qu’il existe une variable aléatoire positive C telle que pour tout k ≥ 1, E kξ k k2 |Fk−1 ≤ C.
On a alors pour tout δ > 0,
2
(ln n)1+δ
 
1
Mn =o p.s.
n n

Démonstration. On pose Vn = 1
(ln n)1+δ n
k Mn k2 , et comme Mn est une martingale on a

h i 1 1 h i
E kVn+1 k2 |Fn = k M n k 2
+ E k ξ n + 1 k 2
|F n
(n + 1) ln(n + 1)1+δ (n + 1) ln(n + 1)1+δ
n(ln n)1+δ 1
≤ +
Vn + C
(n + 1) ln(n + 1) 1 δ (n + 1) ln(n + 1)1+δ

et on obtient le résultat en appliquant le théorème de Robbins-Siegmund.

On peut encore faire un peu mieux avec des hypothèses légèrement plus restrictives grâce au
théorème de suivant (admis, voir la preuve du Théorème 4.3.16 dans [Duf97]).

Théorème 2.2.2. Soit Mn = ∑nk=1 ξ k , avec ξ k adapté à la filtration, de carré intégrable et E [ξ k |Fk−1 ] = 0.
Si il existe une matrice symétrique semi-définie positive Γ telle que

1 1 n h i p.s
h Min = ∑ E ξ k ξ kT |Fk−1 −−−−→ Γ,
n n k =1 n→+∞
2.2 Martingales vectorielles 35

h i
et si il existe η > 0 tel que pour tout supk E kξ k k2+η |Fk−1 < +∞, alors

2  
1 ln n
Mn =O p.s.
n n

On peut même faire encore mieux en terme de vitesse de convergence en utilisant la loi du log-itéré
pour les martingales (cf version longue, ou bien [DST90, Duf90]).

2.2.3 Théorème Central Limite

On commence par donner une version relativement indigeste mais générale du théorème central
limite pour les martingales vectorielles.

Théorème 2.2.3 (Théorème Limite Centrale). Soit ( Mn ) une martingale de carré intégrable et on suppose
qu’il existe une suite croissante et divergente an et une matrice Γ telles que
P
1. an−1 h Min −−−−→ Γ,
n→+∞
2. la condition de Lindeberg est satisfaite, i.e pour tout e > 0,

n
P
h i
a−
n
1
∑E k Mk − Mk−1 k2 1k Mk − Mk−1 k≥ea1/2
n
−−−−→ 0.
n→+∞
k =1

Alors
L
an−1/2 Mn −−−−→ N (0, Γ) .
n→+∞

Là encore, l’énoncé du TLC est plutôt indigeste (notamment la condition de Lindeberg), et on

s’intéressera donc plutôt à la version plus "soft" mais plus restrictive suivante :

Corollaire 2.2.1. Soit Mn = ∑nk=1 ξ k , où (ξ n ) est une suite de différences de martingale adaptée à la
filtration. On suppose que les hypothèses suivantes sont vérifiées :
1. Il existe une matrice Γ telle que

1 n h i
P
∑
n k =1
E ξ k ξ kT |Fk−1 −−−−→ Γ
n →+ ∞

2. Il existe des constantes positives a > 2 et Ca telles que E kξ k k a |Fk−1 ≤ Ca .

 

Alors
1 L
√ Mn −−−−→ N (0, Γ) .
n n →+ ∞

La preuve est disponible dans la version longue.

36 Martingales
Chapitre 3

Vitesses de convergence des algorithmes

de gradient stochastiques

3.1 Convergence presque sûre

On rappelle que l’on cherche à estimer le minimiseur m de la fonction convexe G : Rd −→ R

définie pour tout h ∈ Rd par
G (h) = E [ g( X, h)]

avec g : X × Rd −→ R, et X une variable aléatoire à valeurs dans un espace mesurable X . On

suppose également que pour presque tout x, la fonction g( x, .) est différentiable et considérant des
variables aléatoires i.i.d X1 , . . . , Xn , Xn+1 , . . . de même loi que X et arrivant de manière séquentielle,
l’algorithme de gradient stochastique est défini de manière récursive pour tout n ≥ 0 par

m n + 1 = m n − γn + 1 ∇ h g ( X n + 1 , m n )

avec γn une suite de pas positifs vérifiant

∑ γn + 1 = + ∞ et ∑ γn2 +1 < +∞.

n ≥0 n ≥0

3.1.1 Approche directe

L’approche directe repose sur l’écriture récursive de kmn − mk2 . Celle-ci nous permet, à l’aide du
théorème de Robbins-Siegmund, d’obtenir la forte consistance des estimateurs.

Théorème 3.1.1 (Approche directe). On suppose que la fonction G est strictement convexe, i.e que pour
tout h ∈ Rd tel que h 6= m
h∇ G (h) , h − mi > 0 (3.1)
38 Vitesses de convergence des algorithmes de gradient stochastiques

et qu’il existe une constante C telle que pour tout h ∈ Rd ,

h i  
E k∇h g ( X, h)k2 ≤ C 1 + k h − mk2 , (3.2)

alors
p.s
mn −−−−→ m.
n→+∞

Démonstration. On a

kmn+1 − mk2 ≤ kmn − mk2 − 2γn+1 h∇h g ( Xn+1 , mn ) , mn − mi + γn2 +1 k∇h g ( Xn+1 , mn )k2 .

On considère la filtration (Fn ) engendrée par l’échantillon, i.e Fn = σ ( X1 , . . . , Xn ). En passant à

l’espérance conditionnelle, on obtient, comme mn est Fn -mesurable et par linéarité de l’espérance,
h i h i
E kmn+1 − mk2 |Fn = kmn − mk2 − 2γn+1 hE [∇h g ( Xn+1 , mn ) |Fn ] , mn − mi + γn2 +1 E k∇h g ( Xn+1 , mn )k2 |Fn
h i
= kmn − mk2 − 2γn h∇ G (mn ) , mn − mi + γn2 +1 E k∇h g ( Xn+1 , mn )k2 |Fn .

Grâce à l’inégalité (3.2), on obtient

h i
E kmn+1 − mk2 |Fn ≤ 1 + Cγn2 +1 kmn − mk2 − 2γn+1 h∇ G (mn ) , mn − mi + Cγn2 +1 .

Comme ∑n≥0 γn2 +1 C < +∞, en appliquant le théorème de Robbins-Siegmund, kmn − mk2 converge
presque sûrement vers une variable aléatoire finie et

∑ γn+1 h∇G (mn ) , mn − mi < +∞ p.s.

n ≥0

Comme ∑n≥1 γn = +∞, on a lim infn h∇ G (mn ) , mn − mi = 0 presque sûrement, et comme la

fonction G est strictement convexe, cela implique que lim infn kmn − mk = 0 presque sûrement.
Ainsi, kmn − mk converge presque sûrement vers une variable aléatoire finie et sa limite inférieure
est 0, donc cette suite converge presque sûrement vers 0.

A noter que l’on a choisi une suite de pas déterministe. Cependant, la preuve précédente reste
vraie si on prend une suite de pas aléatoires. Plus précisément, le théorème précédent reste vrai si
on prend une suite de variables aléatoires Γn+1 vérifiant

∑ Γ n +1 = + ∞ p.s et ∑ Γ2n+1 < +∞ p.s,

n ≥0 n ≥0

et telle que pour tout n ≥ 0, Γn+1 est Fn -mesurable.

3.1 Convergence presque sûre 39

3.1.2 Approche via le développement de Taylor de la fonction G

On peut également utiliser une approche basée sur le développement de Taylor de la fonction G.
Bien que cette approche nécessite des hypothèses beaucoup plus restrictives, on verra par la suite
qu’elle est cruciale pour obtenir la convergence des algorithmes de Newton stochastiques.

Théorème 3.1.2. On suppose que m est l’unique minimiseur de G et l’unique zéro du gradient. On suppose
également qu’il existe des constantes C, C 0 telles que pour tout h ∈ Rd ,
h i
∇2 G ( h ) op
≤C et E k∇h g ( X, h)k2 ≤ C 0 (1 + G (h) − G (m)) .

Alors mn converge presque sûrement vers m.

Démonstration. A l’aide d’un développement de Taylor de la fonction G, il existe h ∈ [mn , mn+1 ] tel
que

1
G (θn+1 ) = G (θn ) + h∇ G (mn ) , mn+1 − mn i + m n +1 − m n , ∇ 2 G ( h ) ( m n +1 − m n )
2
1
= G (θn ) − γn+1 h∇ G (mn ) , ∇h g ( Xn+1 , mn )i + γn2 +1 ∇h g ( Xn+1 , mn ) , ∇2 G (h)∇h g ( Xn+1 , mn )
2

De plus, comme ∇2 G (h) op

≤ C, on obtient

1
G (mn+1 ) ≤ G (mn ) − γn+1 h∇ G (mn ) , ∇h g ( Xn+1 , mn )i + γn2 +1 ∇2 G (h) op k∇h g ( Xn+1 , mn )k2
2
1
≤ G (mn ) − γn+1 h∇ G (mn ) , ∇h g ( Xn+1 , mn )i + γn2 +1 C k∇h g ( Xn+1 , mn )k2
2

Attention ! On n’a pas supposé que la fonction G est positive, et on ne peut pas espérer appliquer
directement le théorème de Robbins-Siegmund. Cependant, on peut réécrire l’inégalité précédente
comme

1
G (mn+1 ) − G (m) ≤ G (mn ) − G (m) − γn+1 h∇ G (mn ) , ∇h g ( Xn+1 , mn )i + Cγn2 +1 k∇h g ( Xn+1 , mn )k2
2

Pour tout n ≥ 0, on note Vn = G (mn ) − G (m) et Fn = σ ( X1 , . . . , Xn ). En passant à l’espérance

conditionnelle, on obtient, comme mn est Fn -mesurable,

1 h i
E [Vn+1 |Fn ] ≤ Vn − h∇ G (mn ) , E [∇h g ( Xn+1 , mn ) |Fn ]i + Cγn2 +1 E k∇h g ( Xn+1 , mn )k2 |Fn
  2
1 1
≤ 1 + CC 0 γn2 +1 Vn − γn+1 k∇ G (mn )k2 + CC 0 γn2 +1
2 2

Comme par définition de m, Vn est positif et grâce au théorème de Robbins-Siegmund, Vn converge

40 Vitesses de convergence des algorithmes de gradient stochastiques

presque sûrement vers une variable aléatoire finie et

∑ γn+1 k∇G (mn )k2 < +∞ p.s.

n ≥1

Comme ∑n≥1 γn+1 = +∞, on a lim infn k∇ G (mn )k = 0 presque sûrement, et comme m est
l’unique zéro du gradient, lim infn kmn − mk = 0 presque sûrement. Ainsi, lim infn Vn = 0 presque
sûrement et donc Vn converge presque sûrement vers 0, ce qui implique, comme m est l’unique
minimiseur de la fonction G, que mn converge presque sûrement vers m.

3.1.3 Approche Lyapunov

En réalité, les approches précédentes peuvent être "généralisées" aux fonctions Lyapunov V :
Rd −→ R+ .

Théorème 3.1.3. On suppose qu’il existe une fonction V : Rd −→ R vérifiant

• V (m) = 0 et pour tout h 6= m, V (m) > 0.
• V est continument différentiable et à gradient L-lipschitz, i.e pour tout h, h0 ∈ Rd ,

∇V ( h ) − ∇V ( h 0 ) ≤ L h − h 0 .

• Il existe une constante positive C telle que pour tout h ∈ Rd ,

h i
E k∇h g ( X, h)k2 ≤ C (1 + V (h))

• Il existe α > 0 tel que pour tout h ∈ Rd ,

h∇ G (h), ∇V (h)i ≥ αV (h),

alors
p.s
mn −−−−→ m.
n→+∞

Démonstration. En regardant le développement de Taylor de la fonction V à l’ordre 1, on obtient

1
Z 
V ( m n +1 ) = V ( m n ) + ∇V (mn+1 + t (mn − mn+1 )) dt, mn+1 − mn
0
Z 1 
= V (mn ) + h∇V (mn ) , mn+1 − mn i + ∇V (mn+1 + t (mn − mn+1 )) − ∇V (mn ) dt, mn+1 − mn
0
3.1 Convergence presque sûre 41

En utilisant l’inégalité de Cauchy-Schwarz et comme le gradient de V est L-lipschitz, on obtient

Z 1
V (mn+1 ) ≤ V (mn ) + h∇V (mn ) , mn+1 − mn i + k∇V (mn+1 + t (mn − mn+1 )) − ∇V (mn )k dt kmn+1 − mn k
0
Z 1
≤ V (mn ) + h∇V (mn ) , mn+1 − mn i + L (1 − t)dt kmn+1 − mn k2
0
L
= V (mn ) + h∇V (mn ) , mn+1 − mn i + k m n +1 − m n k 2
2

Ainsi, en remplaçant mn+1 et en passant à l’espérance conditionnelle, on obtient

L h i
E [V (mn+1 ) |Fn ] ≤ V (mn ) − γn+1 h∇V (mn ) , ∇ G (mn )i + γn2 +1 E k∇h g ( Xn+1 , mn )k2 |Fn
  2
LC 2 LC 2
≤ 1+ γn+1 V (mn ) − γn+1 αV (mn ) + γ .
2 2 n

En appliquant le théorème de Robbins-Siegmund on obtient que V (mn ) converge presque sûre-

ment vers une variable aléatoire finie et que

∑ γn + 1 V ( m n ) < + ∞ p.s
n ≥0

et on peut alors conclure de la même façon que pour les théorèmes précédents.

3.1.4 Application au modèle linéaire

On se place dans le cadre du modèle linéaire défini par (1.1), et on rappelle que l’on cherche à
minimiser la fonction G : Rd −→ R définie pour tout h ∈ Rd ,
 2 
1
G (h) = E Y − h X
T
.
2

Le théorème suivant nous donne la forte consistance des estimateurs de gradient dans le cas du
modèle linéaire.

Théorème 3.1.4. On suppose que X admet un moment d’ordre 4, que e admet un moment d’ordre 2 et que
la matrice E XX T est définie positive. Alors, les estimateurs de gradient stochastiques définis par (1.5)
 

vérifient
p.s
θn −−−−→ θ.
n→+∞

Démonstration. On rappelle que pour tout h ∈ Rd , on a ∇2 G (h) = E XX T qui est supposée

 

définie positive. De plus, pour tout h ∈ Rd tel que h 6= θ, on a, à l’aide d’un développement de
Taylor du gradient,
Z 1 h i
∇ G (h) = ∇ G (θ + t(h − θ )dt (h − θ ) = E XX
2 T
(h − θ )
0
42 Vitesses de convergence des algorithmes de gradient stochastiques

et on a donc, comme E XX T est définie positive,

 

h i
h∇ G (h), h − θ i = (h − θ )T E XX T (h − θ ) > 0.

De plus, on a pour tout h ∈ Rd ,

 2
  2  
k∇h g( X, Y, h)k2 = Y − XT h X =  Y − X T θ + X T ( θ − h )  k X k2
 
| {z }
=e

≤ 2e k X k + 2 k X k4 kθ − hk2
2 2

Et donc comme X admet un moment d’ordre 4, que e admet un moment d’ordre 2, et comme X, e
sont indépendants, on a
h i   h i h i
2
E k∇h g( X, Y, h)k ≤ 2E e2 E k X k2 + 2E k X k4 k h − θ k2

et les hypothèses du Théorème 3.1.1 sont donc vérifiées, i.e θn converge presque sûrement vers
θ.

3.1.5 Application à la régréssion logistique

On se place dans le cadre de la régression logistique (1.2), et on rappelle que l’on cherche à mini-
miser h    i
G (h) = E log 1 + exp h T X − h T XY .

Le théorème suivant donne la forte consistance des estimateurs de gradient stochastique dans le
cadre de la régression logistique.

Théorème 3.1.5. On suppose que la variable aléatoire X admet un moment d’ordre 2 et que la Hessienne
de G en θ est positive. Alors, les estimateurs (θn ) de gradient stochastiques définis par (1.6) vérifient

p.s
θn −−−−→ θ.
n→+∞

Démonstration. Pour tout h ∈ Rd , on a

     
T T
k∇h g ( X, Y, h)k = π h X − Y X ≤ π h X − Y k X k ≤ k X k.

On a donc h i h i
2
E k∇h g( X, Y, h)k ≤ E k X k2 .

De plus, à l’aide d’un développement de Taylor, on a pour tout h

Z 1
∇ G (h) = ∇2 G (θ + t(h − θ )) dt (h − θ ) .
0
3.2 Vitesses de convergence presque sûre 43

De plus, la fonction π est continue et comme X admet un moment d’ordre 2, l’application

h     i
h 7−→ ∇2 G (h) = E π h T X 1 − π h T X XX T

est continue. De plus, comme la Hessienne de G est positive en θ, en notant λmin sa plus petite
valeurs propre, il existe rθ > 0 tel que pour tout h ∈ B (θ, rθ ),

λmin
λmin ∇2 G (h) ≥


.
2

Comme la Hessienne de G est au moins semi-définie positive, pour tout h 6= m,

1
Z 
2
h∇ G (h), h − θ i = ∇ G (θ + t(θ − h))dt(h − θ ), h − θ
0
Z 1
= ∇2 G (θ + t(h − θ ))(h − θ ), h − θ dt
0
Z 1
λmin ∇2 G (θ + t(h − θ )) k h − θ k2 dt


≥
0

Si h ∈ B (θ, rθ ), on a
Z 1
λmin λmin
h∇ G (h), h − θ i ≥ kh − θ k2 dt = k h − θ k2 .
0 2 2

Si k h − θ k ≥ rθ , on a
rθ rθ
r λmin
Z Z
kh−θ k 2 kh−θ k λmin
2
kh − θ k2 dt = θ


h∇ G (h), h − θ i ≥ λmin ∇ G (θ + t(h − θ )) k h − θ k dt ≥ kh − θ k .
0 0 2 2

Ainsi, si h 6= θ,
h∇ G (h), h − θ i > 0

et les hypothèses du théorème sont donc vérifiées.

3.2 Vitesses de convergence presque sûre

On s’intéresse maintenant à la vitesse de convergence des estimateurs obtenus à l’aide de l’algo-

rithme de gradient stochastique. Pour cela, on suppose maintenant que la suite de pas (γn ) vérifie
γn = cγ n−α avec cγ > 0 et α ∈ (1/2, 1).

3.2.1 Cadre

Afin d’obtenir les vitesses de convergence presque sûre des estimateurs, on suppose maintenant
que la fonction G que l’on cherche à minimiser est différentiable, convexe, et qu’il existe m qui soit
44 Vitesses de convergence des algorithmes de gradient stochastiques

un zéro du gradient. De plus, on suppose que les hypothèses suivantes sont vérifiées :
(PS1) Il existes des constantes positives ν > 1
α − 1 et Cν telles que pour tout h ∈ Rd ,
h i  
E k∇h g ( X, h)k2+2ν ≤ Cν 1 + kh − mk2+2ν

(PS2) La fonction G est deux fois continûment différentiable sur un voisinage de m et

λmin := λmin ∇2 G (m) > 0.

A noter que l’hypothèse (PS1) est vérifiée, par exemple, dès que ∇h g( X, .) admet un moment
d’ordre 4 tandis que l’hypothèse (PS2) implique la stricte convexité (et même forte convexité locale)
de la fonction G. A noter que les hypothèses pour obtenir les vitesses de convergence presque sûre
sont beaucoup moins restrictives (de manière générale) que celles pour obtenir la convergence en
moyenne quadratique.

3.2.2 Vitesses de convergence

Le théorème suivant nous donne alors la vitesse de convergence presque sûre des estimateurs.

Théorème 3.2.1. On suppose que les hypothèses (PS1) et (PS2) sont vérifiées. Alors
 
2 ln n
kmn − mk = O p.s.
nα

Démonstration. A noter que les hypothèses du Théorème 3.1.1 sont vérifiées et que l’on a donc

p.s
mn −−−−→ m.
n→+∞

N’ayant pas forte convexité de la fonction G, on ne peut pas utiliser l’approche brutale de la preuve
du Théorème 1.4.1, mais on va s’en approcher en linéarisant le gradient. Plus précisément, rappe-
lons que l’on peut réécrire l’algorithme comme

m n + 1 − m = m n − m − γn + 1 ∇ G ( m n ) + γn + 1 ξ n + 1

avec ξ n+1 = ∇ G (mn ) − ∇h g ( Xn+1 , mn ). Rappelons également que considérant la filtration F =

(Fn ), (ξ n ) est une suite de différences de martingale. En linéarisant le gradient, on obtient

m n + 1 − m = m n − m − γn + 1 ∇ 2 G ( m ) ( m n − m ) + γn + 1 ξ n + 1 + γn + 1 ∇ 2 G ( m ) ( m n − m ) − γn + 1 ∇ G ( m n )
= Id − γn+1 ∇2 G (m) (mn − m) + γn+1 ξ n+1 − γn+1 δn


(3.3)

où δn = ∇ G (mn ) − ∇2 G (m) (mn − m) est le terme de reste dans la décomposition de Taylor du

gradient. De plus, grâce à l’hypothèse (PS2), il existe un voisinage Vm de m telle que G soit deux
3.2 Vitesses de convergence presque sûre 45

fois continûment différentiable sur Vm et donc, pour tout h ∈ Vm

Z 1
2
∇ G (h) − ∇ G (m) (h − m) = ∇2 G (m + t(h − m)) dt (h − m) + ∇2 G (m)(h − m)
0
Z 1
≤ ∇2 G (m + t(h − m)) − ∇2 G (m) op
dt kh − mk
0

Par continuité et comme mn converge presque sûrement vers m, on a donc

kδn k = o (kmn − mk) p.s.

De plus, grâce à la décomposition (3.3) on peut montrer par récurrence que l’on peut réécrire
mn − m comme

n −1 n −1
mn − m = β n,0 (m0 − m) + ∑ βn,k+1 γk+1 ξ k+1 − ∑ βn,k+1 γk+1 δk (3.4)
k =0 k =0

avec pour tout k, n ≥ 0 tel que k ≤ n,

n
∏ Id − γ j ∇2 G (m)


β n,k = et β n,n = Id .
j = k +1

Cette décomposition est clairement vérifiée pour n = 0. De plus, pour n + 1, en utilisant la décom-
position (3.3) et par hypothèse de récurrence, on a

mn+1 − m = Id − γn+1 ∇2 G (m) (mn − m) + γn+1 ξ n+1 − γn+1 δn

!
n −1 n −1
= Id − γn+1 ∇2 G (m) ∑ βn,k+1 γk+1 ξ k+1 − ∑ βn,k+1 γk+1 δk


β n,0 (m0 − m) + + γn+1 ξ n+1 − γn+1 δn .
k =0 k =0

En remarquant que que pour tout k ≤ n − 1, Id − γn+1 ∇2 G (m) β n,k+1 = β n+1,k+1 , on obtient

n −1 n −1
mn+1 − m = β n+1,0 (m0 − m) + ∑ β n+1,k+1 γk+1 ξ k+1 − ∑ βn+1,k+1 γk+1 δk + γn+1 ξ n+1 − γn+1 δn
k =0 k =0

Comme γn+1 ξ n+1 = β n+1,n+1 γn+1 ξ n+1 et que l’on peut faire de même pour δn , on obtient

n −1 n −1
mn+1 − m = β n+1,0 (m0 − m) + ∑ β n+1,k+1 γk+1 ξ k+1 − ∑ βn+1,k+1 γk+1 δk + γn+1 βn+1,n+1 ξ n+1
k =0 k =0

− γn+1 β n+1,n+1 δn
n n
= β n+1,0 (m0 − m) + ∑ βn+1,k+1 γk+1 ξ k+1 − ∑ βn+1,k+1 γk+1 δk
k =0 k =0

et la décomposition (3.4) est donc exacte. De plus, en remarquant que l’on peut réécrire β n,k =
46 Vitesses de convergence des algorithmes de gradient stochastiques

β n,0 β− 1
k,0 , on peut réécrire

n −1 n −1
∑ βn,k+1 γk+1 ξ k+1 = βn ∑ β−k+11 ξ k+1 =: βn Mn
k =0 k =0

et Mn est alors un terme de martingale. Cependant, il est compliqué d’utiliser directement la loi des
grands nombres ou la loi du log itéré pour les martingales vectorielles directement pour ce terme.
On peut par contre réécrire la martingale dans la base orthonormée de la Hessienne et d’utiliser
la loi des grands nombres pour les martingales réelles à chacune de ces coordonnées (approche
développée dans [Pel98] par exemple)ce qui conduit au lemme suivant :

Lemma 3.2.1. On suppose que les hypothèses (PS1) et (PS2) sont vérifiées. Alors

2
n −1  
ln n
∑ βn,k+1 γk+1 ξ k+1 =O
nα
p.s.
k =0

On admettra ce lemme. Cependant, la preuve basée sur la loi du log itérée développée dans [Pel98],
ainsi qu’une autre preuve basée sur l’obtention d’inégalités exponentielles sont disponible dans la
version longue. Revenons maintenant à la preuve du théorème. Maintenant que l’on a donné la
vitesse de convergence du terme de martingale, on peut s’intéresser à la vitesse de convergence
du terme dû à l’erreur d’initialisation, i.e du terme β n,0 (m0 − m). Rappelons qu’il existe n0 tel que
pour tout n ≥ n0 , k Id − γn+1 H kop ≤ 1 − λmin γn+1 . On a donc, comme 1 + x ≤ exp( x ),

n n0 n
k β n,0 kop ≤ ∏ k Id − γk H kop ≤ ∏ k Id − γk H kop ∏ (1 − γk λmin )
k =1 k =1 k = n0 +1
!
n0 n
≤ ∏ k Id − γk H kop exp −λmin ∑ γk
k =1 k = n0 +1

et ce terme converge donc à vitesse exponentielle, et en particulier, couplé avec le Lemme 3.2.1, il
vient
2
n −1
β n,0 (m0 − m) + ∑ βn,k+1 γk+1 ξ k+1 = O (γn+1 ln n) p.s
k =0

et il existe donc une variable aléatoire A telle que pour tout n ≥ 0,

2
n −1
β n,0 (m0 − m) + ∑ βn,k+1 γk+1 ξ k+1 ≤ Aγn+1 ln(n + 1) p.s.
k =0

On va maintenant se concentrer sur le dernier terme, i.e sur

n −1
∆n = ∑ βn,k+1 γk+1 δk .
k =0
3.2 Vitesses de convergence presque sûre 47

Rappelons que l’on a vu que pour tout n ≥ 0, kδn k = o (kmn − mk) p.s. On a donc

k∆n+1 k = k( Id − γn+1 H ) ∆n + γn+1 δn k ≤ (1 − λmin γn+1 ) k∆n k + γn+1 kδn k

≤ (1 − λmin γn+1 ) k∆n k + γn+1 rn kmn − mk (3.5)

kδn k
avec rn := 1
kmn −mk kmn −mk6=0
qui converge presque sûrement vers 0. De plus, par inégalité triangu-
−1
laire, kmn − mk ≤ β n,0 (m0 − m) + ∑nk= 0 β n,k +1 γk +1 ξ k +1 + k ∆n k. On peut donc réécrire l’inéga-
lité (3.5), pour tout n ≥ n0 , comme
!
n −1
k∆n+1 k ≤ (1 − λmin γn+1 ) k∆n k + rn γn+1 β n,0 (m0 − m) + ∑ βn,k+1 γk+1 ξ k+1 + k∆n k
k =0

−1
√ √
Comme β n,0 (m0 − m) + ∑nk= 0 β n,k +1 γk +1 ξ k+1 ≤ A ln n
nα/2
presque sûrement et en appliquant le
Lemme 1.4.2, on obtient donc √ !
ln n
k∆n k = O p.s,
nα/2

ce qui conclut la preuve.

3.2.3 Application au modèle linéaire

On se place dans le cadre du modèle linéaire défini par (1.1). Le théorème suivant donne la vitesse
de convergence presque sûre des estimateurs obtenus grâce à l’algorithme de gradient stochas-
tique.
1
Théorème 3.2.2. Soit η > α − 1 tel que que X admette un moment d’ordre 4 + 4η et tel que e admette
un moment d’ordre 2 + 2η. On suppose également que la matrice E XX T est définie positive. Alors les
 

estimateurs de gradient définis par (1.5) vérifient

 
2 ln n
kθn − θ k = O p.s.
nα

Démonstration. On a vu dans la preuve du Théorème 3.1.4 que l’hypothèse (PS2) est vérifiée. De
plus, comme (voir la preuve du Théorème 3.1.4 pour plus de détails)

k∇h g ( X, Y, h)k ≤ |e| k X k + k X k2 kh − θ k

on a donc
h i h i h i h i
E k∇h g ( X, Y, h)k2+2η = 21+2η E |e|2+2η E k X k2+2η + E k X k4+4η k h − θ k2+2η

et l’hypothèse (PS1) est donc vérifée, ce qui conclut la preuve.

Dans la Figure 3.1, on s’intéresse à l’évolution de l’erreur quadratique des estimateurs de gradient
48 Vitesses de convergence des algorithmes de gradient stochastiques

du paramètre de la régression linéaire en fonction de la taille d’échantillon n. Pour cela, on consi-

dère θ = (−4, −3, −2, −1, 0, 1, 2, 3, 4, 5)T ∈ R10 , et on prend X ∼ N (0, I10 ) et e ∼ N (0, 1). De
plus, on a choisi cγ = 1 et α = 0.5, 0.66, 0.75 ou 1. On voit bien que l’on a une décroissance assez
rapide de l’erreur quadratique, et lorsque l’on prend l’échelle logarithmique, une heuristique de
pente nous donne que pour n suffisamment grand, on a bien une pente proche de −α. Enfin, on
peut remarquer que plus α est grand, plus l’erreur semble stable.

1.000
Erreur quadratique

Valeur de α
0.100 0.5
0.66
0.75
1
0.010

0.001
1 10 100 1000
Taille de l'échantillon

F IGURE 3.1 – Evolution de l’erreur quadratique de θn en fonction de la taille d’échantillon n dans

le cadre de la régression linéaire.

Dans la figure 3.2, afin de mieux visualiser les pentes, on considère l’erreur quadratique moyenne
des estimateurs en générant 50 échantillons de taille n = 5000. A noter que bien que l’erreur
quadratique moyenne est meilleure pour α = 1, les estimateurs semblent dans ce cas beaucoup
plus sensibles à une possible mauvaise initialisation.

1.00
Erreur quadratique moyenne

Valeur de α
0.5
0.66
0.10
0.75
1

0.01

1 10 100 1000
Taille de l'échantillon

F IGURE 3.2 – Evolution de l’erreur quadratique moyenne de θn en fonction de la taille d’échantillon

n et du choix de α dans le cadre de la régression linéaire.
3.2 Vitesses de convergence presque sûre 49

3.2.4 Application à la régression logistique

On se replace dans le cadre de la régression logistique défini par (1.2). On rappelle que le paramètre
θ est un minimiseur de la fonction G : Rd −→ R définie pour tout h ∈ Rd par
h    i
G (h) = E log 1 + exp h T X − h T XY =: E [ g ( X, Y, h)] .

Le théorème suivant donne la vitesse de convergence des estimateurs obtenus via l’algorithme de
gradient stochastique dans le cadre de la régression logistique.

Théorème 3.2.3. On suppose qu’il existe η > 0 tel que X admette un moment d’ordre 2 + 2η. On suppose
également que ∇2 G (θ ) est inversible. Alors les estimateurs de gradient définis par (1.6) vérifient
 
2 ln n
kθn − θ k = O p.s.
nα

Démonstration. Il faut montrer que les hypothèses (PS1) et (PS2) sont vérifiées.
Vérification de (PS2). A noter que θ est bien un zéro du gradient. De plus comme la fonction
x 7−→ π ( x )(1 − π ( x )) est continue et bornée, et comme X admet un moment d’ordre 2, la fonction
G est bien deux fois continument différentiable sur Rd (et donc au voisinage de θ). Enfin, comme
∇2 G (θ ) est inversible, on a bien λmin > 0, et l’hypothèse (PS2) est vérifiée.
Vérification de (PS1). Comme k∇h g ( X, Y, h)k ≤ k X k et comme X admet un moment d’ordre
2 + 2η, l’hypothèse (PS1) est vérifiée.

Dans la Figure 3.3, on considère θ = (1, 1, 1, 1, 1)T ∈ R5 , et on prend X ∼ N (0, I5 ). De plus, on

a pris cγ = 1 et α = 0.5, 0.66, 0.75 ou 1. On voit bien que l’on a une décroissance assez rapide de
l’erreur quadratique, sauf pour α = 1.

1.000
Erreur quadratique

0.100 Valeur de α
0.5
0.66
0.75
0.010
1

0.001

1 10 100 1000
Taille de l'échantillon

F IGURE 3.3 – Evolution de l’erreur quadratique de θn en fonction de la taille de l’échantillon n

dans le cadre de la régression logistique.
50 Vitesses de convergence des algorithmes de gradient stochastiques

Dans la figure 3.4, on s’intéresse à l’évolution de l’erreur quadratique moyenne afin de mieux
visualiser les pentes. Cela semble confirmer que choisir α = 1 n’est pas une très bonne option. Les
estimateurs ne semblent pas du tout converger à la vitesse 1/n. Pour les autres choix, on voit bien
que plus α est grand, plus la convergence est rapide.

1.00
Erreur quadratique moyenne

Valeur de α
0.5

0.10 0.66
0.75
1

0.01

1 10 100 1000
Taille de l'échantillon

F IGURE 3.4 – Evolution de l’erreur quadratique moyenne de θn en fonction de la taille de l’échan-

tillon n et du choix du paramètre α dans le cadre de la régression logistique.

3.2.5 Remarques

On a vu que sous des hypothèses faibles et en prenant un pas de la forme cγ n−α , avec α ∈ (1/2, 1),
1
on obtient une vitesse de convergence de l’ordre nα (à un terme logarithmique près). Cependant,
comme on a prit α < 1, on ne peut pas avoir une vitesse "optimale", c’est à dire une vitesse de
l’ordre de 1/n. On peut alors se dire naïvement que l’on peut prendre α = 1. Cependant, pour
assurer une vitesse en 1/n, cela implique de prendre cγ > 2λ1min , avec λmin = λmin ∇2 G (m) .

Dans la Figure 3.2, cette hypothèse était vérifiée et on voit bien que les estimateurs convergent à la
bonne vitesse. Cependant, dans la Figure 3.4, cette hypothèse n’était pas vérifiée et on a pu remar-
quer que l’on ne convergeait pas du tout à la vitesse 1/n. Cette approche a donc deux principaux
inconvénients. Le premier, c’est qu’il faut calibrer le pas par rapport à la plus petite valeur propre
de la Hessienne alors que l’on ne la connait pas. Dans certains cas, on est capable de la minorer
1
par une certaine valeur λinf et peut alors choisir cγ > 2λinf et ainsi obtenir une vitesse en 1/n (à un
terme logarithmique près). On peut même montrer, sous certaines hypothèses,
√ L
n (mn − m) −−−−→ N (0, Σ RM ) ,
n→+∞

où Z +∞    
−s H − 2c1γ Id −s H − 2c1γ Id
Σ RM = cγ e Σe ds
0
 
avec Σ = E ∇h g ( X, m) ∇h g( X, m)T . A noter que H − 1 1
 
2cγ Id < est définie positive car 2cγ
λmin ( H ), et donc Σ RM est bien définie. Cependant, si on s’intéresse aux M-estimateur m̂n , on a
3.2 Vitesses de convergence presque sûre 51

vu que sous certaines hypothèses de régularité

√ L
 
n (m̂n − m) −−−−→ N 0, H −1 ΣH −1 ,
n→+∞

et si Σ 6= 0, on peut montrer que l’on a ainsi une meilleur variance, i.e on peut montrer que la
matrice H −1 ΣH −1 − Σ RM est au moins semi-définie négative. En d’autres termes, on ne peut pas
avoir, généralement, un comportement asymptotique optimal pour les estimateurs obtenus à l’aide
d’algorithmes de gradient stochastiques. Pour s’en convaincre, on peut considérer l’exemple de la
régression linéaire. On rappelle que dans ce cas, on a Σ = σ2 H, et en écrivant Σ RM dans la base
orthonormée de H, et en notant λ1 , . . . , λd ses valeurs propres, on a
Z +∞    
−sdiag λ1 − 2c1γ ,...,λd − 2c1γ −sdiag λ1 − 2c1γ ,...,λd − 2c1γ
Σ RM = σ cγ
2
e diag (λ1 , . . . , λd ) e ds
0
!
σ2 c γ λ1 cγ λd
= diag 1
,...,
2 λ1 − 2cγ λd − 2c1γ
!
σ2 c γ λ1 1 cγ λd
= diag λ1−1 1
, . . . , λ−
d
2 1 − 2cγ λ1 1 − 2cγ1λd
 
> σ2 diag λ1−1 , . . . , λ−d
1
.

car pour tout x ∈ (0, 1), on a x

1
1− 2x
> 2. On a donc H −1 ΣH −1 − Σ RM qui est définie négative.
52 Vitesses de convergence des algorithmes de gradient stochastiques
Chapitre 4

Accélération des méthodes de gradient

stochastiques

On a vu dans le chapitre précédent qu’il n’est pas possible, généralement, d’obtenir un comporte-
ment asymptotique optimal pour les estimateurs obtenus à l’aide d’algorithmes de gradient sto-
chastiques. On propose dans ce chapitre des transformations de ces derniers afin d’accélérer la
convergence et obtenir des estimateurs asmptotiquement efficaces.

4.1 Algorithmes de gradient stochastiques moyennés

Une méthode usuelle pour accélérer la converge, introduite par [Rup88] et [PJ92], est de considérer
un algorithme de gradient stochastique moyenné. Celui-ci consiste à considérer la moyenne de
tous les estimateurs de gradient obtenus au temps n, i.e l’estimateur moyenné mn est défini pour
tout n ≥ 0 par
n
1
mn = ∑ m .
n + 1 k =0 k

On reste ici sur des estimateurs en ligne dans le sens où on peut écrire la procédure de manière
récursive pour tout n ≥ 0 comme

m n + 1 = m n − γn + 1 ∇ h g ( X n + 1 , m n )
1
m n +1 = m n + ( m n +1 − m n ) ,
n+2

avec m0 = m0 borné. A noter que la mise à jour de l’estimateur reste très peu couteuse en terme
de temps de calcul. En effet, l’étape de moyennisation ne représente, à chaque itération, que O(d)
opérations supplémentaires. On s’intéresse maintenant aux vitesses de convergence des estima-
teurs moyennés. Pour cela, dans ce qui suit, on considère une suite de pas de la forme γn = cγ n−α
avec cγ > 0 et α ∈ (1/2, 1).
54 Accélération des méthodes de gradient stochastiques

4.1.1 Vitesse de convergence presque sûre

Avant de donner les vitesses de convergence, on introduit le Lemme de Toeplitz, qui sera très utile
dans les preuves.

Lemma 4.1.1 (Toeplitz). Soit an une suite positive telle que ∑n≥0 an = +∞ et Xn une suite de variables
convergeant presque sûrement vers une variable aléatoire X. Alors

n
1 p.s
n ∑
∑ k =0 a k k =0
ak Xk −−−−→
n→+∞
X.

En particulier, le lemme de Toeplitz nous dit que si mn converge presque sûrement vers m, alors
mn converge aussi.
Afin de donner la vitesse de convergence des estimateurs moyennés, on introduit maintenant une
nouvelle hypothèse, qui permet notamment de donner la vitesse de convergence du terme induit
par le terme de reste dans la décomposition de Taylor du gradient.
(PS3) Il existe des constantes η > 0 et Cη telles que pour tout h ∈ Bη := B (m, η ),

∇ G (h) − ∇2 G (m)(h − m) ≤ Cη kh − mk2 .

L’hypothèse (PS3) est vérifiée, par exemple, dès que la Hessienne de G est Cη Lipschitz sur le
voisinage de m, i.e si pour tout h ∈ Bη ,

∇2 G ( m ) − ∇2 G ( h ) op
≤ Cη kh − mk .

En effet, comme ∇ G (m) = 0, la décomposition de Taylor du gradient nous donne que pour tout
h ∈ Bη ,
Z 1
∇ G (h) = ∇2 G (m + t(h − m)) dt(h − m)
0

et on obtient donc
Z 1
∇ G (h) − ∇2 G (m)(h − m) = ∇2 G (m + t(h − m))dt(h − m) − ∇2 G (m)(h − m)
0
Z 1
∇2 G (m + t(h − m)) − ∇2 G (m) dt(h − m)


=
0
Z 1
≤ ∇2 G (m + t(h − m)) − ∇2 G (m) op
dt kh − mk
0

Comme la Hessienne est Cη -Lipschitz sur Bη et comme pour tout h ∈ Bη et t ∈ [0, 1], on a m +
t(h − m) ∈ Bη , on obtient que l’hypothèse (PS3) est bien vérifiée. On peut maintenant revenir à la
vitesse de convergence presque sûre des estimateurs moyennés, ce que nous donne le théorème
suivant.
4.1 Algorithmes de gradient stochastiques moyennés 55

Théorème 4.1.1. On suppose que les hypothèses (PS1) à (PS3) sont vérifiées. Alors pour tout δ > 0,

(ln n)1+δ
 
2
kmn − mk = o p.s.
n

On obtient donc une vitesse (à un terme log près) une vitesse de convergence en 1/n.

Démonstration. Au vu du terme log, on se doute qu’il va falloir utiliser une loi des grands nombres
pour les martingales vectorielles, et il faut donc faire apparaitre ce terme de martingale. Rappelons
que l’on a la décomposition suivante pour mn+1 :

mn+1 − m = ( Id − γn+1 H ) (mn − m) + γn+1 ξ n+1 − γn+1 δn

avec H = ∇2 G (m), δn = ∇ G (mn ) − H (mn − m), et ξ n+1 = ∇ G (mn ) − ∇h g ( Xn+1 , mn ). Rappelons

également que (ξ n ) est une suite de différences de martingales par rapport à la filtration générée
par l’échantillon. Cette décomposition de mn+1 peut se réécrire,

γn+1 H (mn − m) = (mn − m) − (mn+1 − m) + γn+1 ξ n+1 − γn+1 δn

et en divisant par γn+1 , on obtient donc

( m n − m ) − ( m n +1 − m )
H (mn − m) = + ξ n+1 − δn .
γn + 1

En sommant ces inégalités et par linéarité, on obtient

n n n n
( m k − m ) − ( m k +1 − m )
H ∑ (mk − m) = ∑ γk + 1
+ ∑ ξ k+1 − ∑ δk
k =0 k =0 k =0 k =0
| {z }
: = Mn

A noter que Mn est une martingale par rapport à la filtration. Enfin, en divisant par n + 1, on
obtient (par définition de mn ),

n n n
1 ( m k − m ) − ( m k +1 − m ) 1 1
n + 1 k∑ n + 1 k∑ n + 1 k∑
H (mn − m) = + ξ k +1 − δk (4.1)
=0
γk + 1 =0 =0
| {z } | {z }
:= R1,n := R2,n

et il ne reste plus qu’à donner les vitesses de convergence de chacun des termes à droite de l’égalité
(4.1)

1
Vitesse de convergence de n+1 Mn+1 . Rappelons que pour appliquer le Théorème 2.2.2, il faut
vérifier qu’il existe ν > 0 tel que les moments conditionnels d’ordre 2 + 2ν soit uniformément
56 Accélération des méthodes de gradient stochastiques

bornés, ce qui n’est pas exactement le cas pour nous. En effet, on a à l’aide de l’hypothèse (PS1),
h i h i
E kξ k+1 k2+2ν |Fk ≤ E k∇h g ( Xn+1 , mn ) + E [∇h g ( Xn+1 , mn ) |Fn ]k2+2ν |Fn
h i
≤ 21+2ν E k∇h g ( Xn+1 , mn )k2+2ν |Fn
 
≤ 21+2ν Cν 1 + kmk − mk2+2ν .

Cependant, comme mn converge presque sûrement vers m, on va utiliser un argument de tron-

cature. Plus précisément, on introduit l’évènement An = {kmn − mk ≤ 1} et on peut réécrire la
martingale comme
n n
Mn = ∑ ξ k +1 1 A k
+ ∑ ξ k +1 1 A C
k
k =0 k =0

Comme 1 An est Fn -mesurable, (ξ n+1 1 An ) est toujours une suite de différences de martingales, et
elle vérifie h i
E kξ n+1 k2+2ν 1 An |Fn ≤ 22+2ν Cν

et en appliquant le Théorème 2.2.1, on obtient pour tout δ > 0,

2
n
(ln n)1+δ
 
1
( n + 1)2 ∑ ξ k +1 1 A k
=o
n
p.s.
k =0

De plus comme 1 ACn converge presque sûrement vers 0, on a

∑ k ξ n +1 k 1 A C
n
< +∞ p.s
n ≥0

et en particulier,
2
n  
1 1
( n + 1)2 ∑ ξ k +1 1 A C
k
=O
n2
p.s.
k =0

et donc pour tout δ > 0,

 
2 2
n n
(ln n)1+δ
 
1 2
( n + 1)2
k Mn k 2 ≤
( n + 1)2
 ∑ ξ k +1 1 A k + ∑ ξ k +1 1 A C
k
=o
n
p.s.
k =0 k =0

Vitesse de convergence de R1,n . Afin de simplifier les notations, notons uk = mk − m. On peut

4.1 Algorithmes de gradient stochastiques moyennés 57

réécrire (n + 1) R1,n comme

n
(n + 1) R1,n = ∑ (uk − uk+1 ) γk−+11
k =0
n n
= ∑ uk γk−+11 − ∑ uk+1 γk−+11
k =0 k =0
n n
= ∑ uk γk−+11 + u0 γ1−1 − ∑ uk+1 γk−+11
k =1 k =0
n   n n
= ∑ uk γk−+11 − γk−1 + u0 γ1−1 + ∑ uk γk−1 − ∑ uk+1 γk−+11 .
k =1 k =1 k =0

En faisant le changement d’indice k0 = k + 1 dans la dernière somme, on obtient

n   n n +1
(n + 1) R1,n = ∑ uk γk−+11 − γk−1 + u0 γ1−1 + ∑ uk γk−1 − ∑
0
uk0 γk−0 1
k =1 k =1 k =1
n  
= ∑ uk γk−+11 − γk−1 + u0 γ1−1 − un+1 γn−+1 1
k =1

On a clairement  
1 1
km0 − mk γ1−1 = O p.s.
( n + 1) n+1
et ce terme est donc négligeable. De plus, grâce au Théorème 3.2.1, on a
p !
1 ln(n + 1)
kmn+1 − mk γn−+1 1 = O p.s
n+1 (n + 1)1−α/2

et comme α < 1, ce terme est négligeable. Il reste donc à donner la vitesse de convergence du
−1 −1
dernier terme. A noter que la fonction f : t 7−→ c− 1 α
γ t est dérivable, que γk +1 − γk = f ( k + 1) −
f (k ), et que
f 0 (t) = c− 1 α −1
γ αt .

On obtient donc γk−+11 − γk−1 ≤ c− 1 α−1 et

γ αk

n   n
∑ k
( m − m ) γ −1
k +1 − γ −1
k ≤ ∑ kmk − mk c−γ 1 αkα−1
k =1 k =1

De plus, d’après le Théorème 3.2.1, on a pour tout δ > 0,

kα/2 p.s
k 1− α 1/2 +
kmk − mk kα−1 −−−→ 0,
ln(k + 1) δ k →+∞
58 Accélération des méthodes de gradient stochastiques

et on a donc, d’après le Lemme de Toeplitz,

n n
k1−α/2
 
∑ kmk − mk k α −1
= ∑k α/2−1
ln(k + 1) 1/2+δ
ln(k + 1)1/2+δ
k m k − m k k α −1
k =1 k =1
!
n
=o ∑ kα/2−1 ln(k + 1)1/2+δ p.s.
k =1

et comme ∑nk=1 k1−α/2 ln(k + 1)1/2+δ = O nα/2 ln(n + 1)1/2+δ , il vient

n
(ln n)1+δ
 
1  
n+1 ∑ (mk − m) γk−+11 − γk−1 =o
n1−α/2
p.s
k =1

et comme α < 1, ce terme est négligeable, et donc R1,n est négligeable par rapport au terme de
martingale.

 R2,n . Comme
Vitesse de convergence de  mn converge presque sûrement vers m et d’après l’hypo-
2
thèse (PS3), on a δn = O kmn − mk presque sûrement, et donc, pour tout δ > 0,

( n + 1) α p.s
kδn k −−−−→ 0.
ln(n + 1)1+δ n→+∞

Ainsi, en appliquant le lemme de Toeplitz, on obtient

!
n n n
ln(k + 1)1+δ ln(k + 1)1+δ
 
( k + 1) α
(n + 1) k R2,n k ≤ ∑ kδk k = ∑ kδk k =o ∑ ( k + 1) α p.s
k =0 k =0
( k + 1) α ln(k + 1)1+δ k =0

ln(k +1)1+δ
et comme ∑nk=0 = O ln(n + 1)1+δ n1−α , on obtient


( k +1) α

 
R2,n = o ln(n + 1)1+δ (n + 1)−α p.s

ce qui est négligeable car α > 1/2, et on a donc

 
2 ln n
k H (mn − m)k = O p.s.
n

En particulier  
2 −2 2 ln n
k(mn − m)k ≤ λmin k H (mn − m)k = O p.s.
λ2min n

Remarquons que l’on pourrait alléger l’hypothèse (PS3). En effet, on peut la remplacer par
(PS3’) Il existe des constantes positives A > 0, a > 1 et C A,a telles que pour tout h ∈ B(m, A),

∇ G (h) − ∇2 G (m)(h − m) ≤ C A,a kh − mk a .

4.1 Algorithmes de gradient stochastiques moyennés 59

Ainsi, en prenant α > 1a , le terme R2,n resterait un terme négligeable, et on conserverait la même
vitesse de convergence pour l’estimateur moyenné.

4.1.2 Normalité asymptotique

Afin d’obtenir la normalité asymptotique de l’estimateur moyenné, on a besoin d’une nouvelle hy-
pothèse sur le gradient de g. Plus précisément, on supposera que l’hypothèse suivante est vérifiée :
(PS4) La fonction Σ : Rd −→ Md (R) définie pour tout h ∈ Rd par
h i
Σ(h) = E ∇h g ( X, h) ∇h g ( X, h)T

est continue en m.
On peut maintenant obtenir la normalité asymptotique.

Théorème 4.1.2. On suppose que les hypothèses (PS1) à (PS4) sont vérifiées. Alors
√ L
 
n (mn − m) −−−−→ N 0, H −1 ΣH −1
n→+∞

h i
avec H := ∇2 G (m) et Σ := E ∇h g ( X, m) ∇h g ( X, m)T .

On obtient donc un comportement asymptotique des estimateurs moyennés identique à celui des
M-estimateurs.

Démonstration. On a vu dans la preuve du Théorème 4.1.1 que l’on pouvait écrire H (mn − m)
comme
1
H (mn − m) = R1,n + R2,n + Mn
n+1
   
avec k R1,n k = o √1n et k R1,n k = o √1n presque sûrement et Mn = ∑nk=0 ξ k+1 est un terme de
martingale. En particulier, il vient
√ p.s √ p.s
n k R1,n k −−−−→ 0 et n k R2,n k −−−−→ 0
n→+∞ n→+∞

Il ne reste donc plus qu’à appliquer le TLC au terme de martingale. Attention, pour pouvoir vérifier
les conditions du TLC, il faut que la martingale soit a minima de carré intégrable, ce qui n’a pas
été vérifié. On va donc réécrire le terme de martingale comme

n n
Mn = ∑ ξ k+1 1kmk −mk≤1 + ∑ ξ k+1 1km −mk>1 =: M1,n + M2,n .
k
k =0 k =1

Comme mn converge presque sûrement vers m, 1kmn −mk>1 converge presque sûrement vers 0, et
donc
∑ kξ n+1 k 1km −mk>1 < +∞
n
p.s
n ≥0
60 Accélération des méthodes de gradient stochastiques

et en particulier
1 p.s
√ k M2,n k −−−−→ 0 p.s
n n→+∞

i.e ce terme est négligeable. Pour appliquer le TLC au terme de martingale, calculons le crochet :
on a
n h i
h M1 in = ∑ E ξ ξ T
1
k+1 k +1 kmk −mk≤1 |F k
k =0
n h i
= ∑ E (∇ G ( m k ) − ∇ h g ( X k +1 , m k )) (∇ G ( m k ) − ∇ h g ( X k +1 , m k )) T
1 |F
kmk −mk≤1 k
k =0

Comme mk est Fk -mesurable, il vient

n
∑ ∇G (mk ) ∇G (mk )T 1km −mk≤1 − ∇G (mk ) (E [∇h g (Xk+1 , mk ) |Fk ])
T
h M1 in = k
1kmk −mk≤1
k =0
n h i
− ∑ E [∇ h g ( X k + 1 , m k ) |F k ] ∇ G ( m k ) T
1 kmk −mk≤1 + E ∇ h g ( X k + 1 , m k ) ∇ h g ( X k + 1 , m k ) T
|F k 1kmk −mk≤1
k =0
n h i n
= ∑ E ∇ h g ( X k +1 , m k ) ∇ h g ( X k +1 , m k ) T
|F k 1kmk −mk≤1 − ∑ ∇G (mk ) ∇G (mk )T 1km −mk≤1 k
k =0 k =0

L’hypothèse (PS2) nous donne que G est deux fois continument différentiable sur un voisinage V
de m. Il existe donc un constante positive CV telle que pour tout h ∈ V, ∇2 G (h) op
≤ CV et donc
pour tout h ∈ V,
Z 1
k∇ G (h)k = ∇2 G (m + t(h − m))dt(h − m) ≤ CV kh − mk .
0

De plus, pour tout h ∈ V, on a

∇ G (h)∇ G (h)T ≤ k∇ G (h)k2 ≤ CV2 kh − mk2 .

op

Ainsi, comme mn converge presque sûrement vers m et d’après le Théorème 3.2.1, on a pour tout
δ > 0,
( n + 1) α p.s
∇ G (h)∇ G (h)T −−−−→ 0
ln(n + 1)1+δ op n→+∞

et en appliquant le lemme de Toeplitz, on obtient

n n
ln(k + 1)1+δ
 
( k + 1) α
∑ ∇ G (mk ) ∇ G (mk ) T
1kmk −mk≤1 ≤∑
( k + 1) α ln(k + 1)1+δ
k∇ G (mk )k2
k =0 op k =0
!
n
ln(k + 1)1+δ
=o ∑ ( k + 1) α
p.s
k =0
4.1 Algorithmes de gradient stochastiques moyennés 61

et donc
n
ln(n + 1)1+δ
 
1
n+1 ∑ ∇ G (mk ) ∇ G (mk ) T
1kmk −mk≤1 =o
( n + 1) α
p.s.
k =0 op

Enfin, comme mn converge presque sûrement vers m et d’après l’hypothèse (PS4), on a

h i p.s
E ∇h g ( Xn+1 , mn ) ∇h g ( Xn+1 , mn )T 1kmn −mk≤1 |Fn −−−−→ Σ
n→+∞

et en appliquant le lemme de Toeplitz, on obtient

n
1 h i p.s
n + 1 k∑
T
E ∇ h g ( X k +1 , m k ) ∇ h g ( X k +1 , m k ) 1 kmk −mk≤1 k −
|F −−−→ Σ.
n→+∞
=0

p.s
h i
Ainsi, h M1 in −−−−→ Σ. De plus, comme E kξ n+1 k2+2η 1kmn −mk≤1 |Fn ≤ 22+2ν Cν , la condition
1
n +1 n→+∞
de Lindeberg est vérifiée. On peut donc appliquer le TLC pour les martingales et on obtient

1 L
√ M1,n −−−−→ N (0, Σ) .
n n→+∞

ce qui conclut la preuve.

4.1.3 Application au modèle linéaire

On se place dans le cadre de la régression linéaire (1.1). On peut donc écrire l’algorithme de gra-
dient stochastique moyenné comme
 
θn+1 = θn + γn+1 Yn+1 − XnT+1 θn Xn+1
1

θ n +1 = θ n + θ n +1 − θ n ,
n+2

avec θ 0 = θ0 borné. Le théorème suivant donne la vitesse de convergence presque sûre ainsi que
la normalité asymptotique des estimateurs moyennés.
1
Théorème 4.1.3. On suppose qu’il existe η > α − 1 tel que X et e admettent respectivement des moments
d’ordre 4 + 4η et 2 + 2η. Alors pour tout δ > 0,

(ln n)1+δ √
 
2
L  
θn − θ =o p.s et n θ n − θ −−−−→ N 0, σ2 H −1 .
n n→+∞

Démonstration. On a vu dans la preuve du Théorème 3.2.2 que les hypothèses (PS1) et (PS2) sont
vérifiées. De plus, comme pour tout h ∈ Rd
Z 1 h i
∇ G (h) = ∇2 G (θ + t(h − θ )) dt(h − θ ) = E XX T (h − θ )
0

l’hypothèse (PS3) est vérifiée et on a même ∇ G (h) − ∇2 G (θ )(h − θ ) = 0. Il reste donc à vérifier
62 Accélération des méthodes de gradient stochastiques

que (PS4) l’est. A noter que pour tout h ∈ Rd , comme Y − X T θ = e, on peut écrire Σ(h) comme
 2  h i h i  2 
Σ(h) = E Y−X h T
XX T
= E e XX 2
− 2E eX (h − θ ) XX + E
T T T T
X (h − θ ) XX T

h i  2 
= E e XX + E X (h − θ ) XX
2 T T T

et comme X admet un moment d’ordre 4, la fonction Σ est bien continue en θ. De plus, on a

Σ(θ ) = σ2 E XX T = σ2 H, ce qui conclut la preuve.
 

Dans la Figure 4.1, on s’intéresse à l’évolution de l’erreur quadratique moyenne des estimateurs
de gradient et de leur version moyennée, dans le cadre de la régression linéaire, en fonction de la
taille d’échantillon n. Pour cela, on considère le modèle

θ = (−4, −3, −2, −1, 0, 1, 2, 3, 4, 5)T ∈ R10 , X ∼ N (0, I10 ) , et e ∼ N (0, 1)

De plus, on a choisi cγ = 1 et α = 0.66 ou 0.75. Enfin, on a calculé l’erreur quadratique moyenne des
estimateurs en générant 50 échantillons de taille n = 5000. On peut voir que dès que l’algorithme
de gradient arrive à convergence (n ' 200), la moyennisation permet une réelle accélération, et à
échelle logarithmique, la pente avoisine −1. De plus, on peut noter que pour α = 0.66, l’algorithme
de gradient arrive plus vite à convergence, ce qui permet à l’étape de moyennisation d’accéler la
convergence plus rapidement.

1.00
Erreur quadratique moyenne

SGD avec α = 0.66

0.10 SGD avec α = 0.75
ASGD avec α = 0.66
ASGD avec α = 0.75

0.01

1 10 100 1000
Taille d'échantillon

F IGURE 4.1 – Evolution de l’erreur quadratique moyenne de l’estimateur de gradient θn (SGD)

et de sa version moyennée θ n (ASGD) en fonction de la taille d’échantillon n dans le cadre de la
régression linéaire.

De plus, pour tout x0 ∈ Rd , on a

√  T 
L
 
n x0 θ n − x0T θ −−−−→ N 0, σ2 x0T H −1 x0
n→+∞
4.1 Algorithmes de gradient stochastiques moyennés 63

ce que l’on peut réécrire comme

√ x T θ n − x0T θ N
n q0 −−−−→ (0, 1) .
T n →+ ∞
σ 2 x 0 H −1 x 0

Ainsi, en connaissant un estimateur en ligne de H −1 , on pourrait construire un intervalle de

confiance et un test en ligne pour x0T θ. Un estimateur récursif de H serait défini pour tout n ≥ 0
par
1  
H n +1 = H n + Xn+1 XnT+1 − H n
n+2
avec H 0 symétrique et définie positive. En effet, on peut réécrire H n comme
!
n
1
Hn =
n+1
H0 + ∑ Xk XkT
k =1

et par la loi des grands nombres, c’est un estimateur consistant. Cependant, inverser H n à chaque
itération pourrait s’avérer coûteux en terme de temps de calculs, et on ne peut pas, pour le moment
construire ce type d’intervalles en ligne. On verra cependant comment inverser cette matrice à
chaque itération et ce, à moindre cout. Remarquons maintenant que l’on peut écrire le TLC comme

√ H 1/2 θ n − θ


L
n −−−−→ N (0, 1),
σ n→+∞

et on obtient, par le théorème de continuité,

2
T
√ H 1/2 θ n − θ



n θn − θ H θn − θ L
n = −−−−→ χ2d
σ σ2 n→+∞

et grâce au théorème de Slutsky, on obtient

T

n θn − θ Hn θn − θ L
2
−−−−→ χ2d .
σ n→+∞

Il ne reste plus qu’à construire un estimateur récursif de σ2 pour pouvoir tester en ligne θ = θ0 .
Un estimateur en ligne "naturel" de σ2 est de considérer la moyenne des erreurs quadratiques des
prévisions, i.e de considérer l’estimateur σ̂n2 défini récursivement pour tout n ≥ 1 par
 
1 2
σ̂n2+1 = σ̂n2 + Yn+1 − XnT+1 θ n − σ̂n2
n+2

avec σ02 = 0. On peut réécrire l’estimateur comme

n 
1 2
σ̂n2 = ∑
n + 1 k =1
Yk − XkT θ k−1 .
64 Accélération des méthodes de gradient stochastiques

On admettra pour le moment la consistance de cet estimateur, mais on l’établira par la suite pour
les estimateurs obtenus à l’aide d’algorithmes de Newton stochastiques. On a donc, par le théo-
rème de Slutsky,

T

n θn − θ Hn θn − θ L
Cn := 2
−−−−→ χ2d .
σ̂n n→+∞

Dans la Figure 4.2, on prend une taille d’échantillon n = 5000 et on compare la fonction de répar-
tition d’une Chi-deux à 10 degrés de liberté, et celle de Cn avec α = 0.66 ou α = 0.75. On voit que
dans les deux cas, la fonction de répartition de Cn s’approche de celle de la Chi-deux.Cela fait de
la variable aléatoire Cn un bon candidat pour construire des tests asymptotiques en ligne.

1.00

0.75

Cn avec α = 0.66
F(x)

0.50 Cn avec α = 0.75

Chi deux

0.25

0.00

0 5 10 15 20 25
x

F IGURE 4.2 – Comparaison de la fonction de répartition de Cn avec n = 5000, pour α = 0.66 et

α = 0.75, et de celle d’une Chi 2 à 10 degrés de liberté dans le cadre du modèle linéaire.

4.1.4 Application à la régression logistique

On se place dans le cadre de la régression logistique (1.2). On peut écrire l’algorithme de gradient
stochastique moyenné comme
   
θn+1 = θn − γn+1 π XnT+1 θn − Yn+1 Xn+1
1

θ n +1 = θ n + θ n +1 − θ n ,
n+2
exp( x )
avec π ( x ) = 1+exp( x )
et θ0 = θ 0 borné. Le théorème suivant donne la vitesse de convergence
presque sûre ainsi que la normalité asymptotique des estimateurs moyennés.

Théorème 4.1.4. On suppose que X admet un moment d’ordre 3 et que ∇2 G (θ ) est inversible. Alors pour
tout δ > 0,

(ln n)1+δ √
 
2
L  
θn − θ =o p.s et n θ n − θ −−−−→ N 0, H −1
n n→+∞
4.1 Algorithmes de gradient stochastiques moyennés 65

avec h     i
H = E π θ T X 1 − π θ T X XX T .

On admettra ce théorème mais la preuve est disponible dans la version longue. Dans la Figure 4.3,
on considère le modèle θ = (1, 1, 1, 1, 1)T ∈ R5 et X ∼ N (0, I5 ). De plus, on a choisi cγ = 5 et
α = 0.66 ou 0.75. Enfin, on a calculé l’erreur quadratique moyenne des estimateurs en générant 50
échantillons de taille n = 20000. On voit bien qu’au bout d’un certain temps (n = 5000), les estima-
teurs obtenus à l’aide de l’algorithme de gradient stochastique arrivent à convergence. Arrivé à ce
moment, l’étape de moyennisation permet bel et bien d’accélérer la convergence. Cependant, on
voit également que les estimateurs moyennés souffrent beaucoup en cas de mauvaise initialisation.

10.00
Erreur quadratique moyenne

1.00
SGD avec α = 0.66
SGD avec α = 0.75
ASGD avec α = 0.66
0.10 ASGD avec α = 0.75

0.01

1 10 100 1000 10000

Taille de l'échantillon

F IGURE 4.3 – Evolution de l’erreur quadratique moyenne par rapport à la taille de l’échantillon
des estimateurs de gradients θn (SGD) et de leurs versions moyennées θ n (ASGD) dans le cadre de
la régression logistique.

De la même façon que pour le modèle linéaire, pour tout x0 ∈ Rd , on a

√  T 
L
 
n x0 θ n − x0T θ −−−−→ N 0, x0T H −1 x0
n→+∞

ce que l’on peut réécrire comme

√ x0T θ n − x0T θ
nq −−−−→ N (0, 1)
n→+∞
x0T H −1 x0

et ainsi, si on connaissait un estimateur en ligne de H −1 , on pourrait construire un intervalle

confiance et un test en ligne pour x0T θ. Un estimateur récursif en ligne de H serait pour tout n ≥ 0

1   T    
H n +1 = H n + π Xn+1 θ n 1 − π XnT+1 θ n Xn+1 XnT+1 − H n
n+2
66 Accélération des méthodes de gradient stochastiques

ce que l’on peut réécrire comme

n
1    
n + 1 k∑
T T
Hn = π X θ
k +1 k 1 − π X θ
k +1 k Xk+1 XkT+1
=0

Cependant, inverser cette matrice à chaque itération peut être très coûteux en terme de temps
de calculs si on s’y prend mal (on verra par la suite qu’en s’y prenant bien, cela ne représente
"que" O(d2 ) opérations). Cependant, on peut d’ores et déjà remarquer que l’on peut réécrire le
TLC comme
√
L
nH 1/2 θ n − θ −−−−→ N (0, Id )
n→+∞

et en appliquant le Théorème de continuité, on obtient

√ 2
T
L
nH 1/2 θ n − θ H θ n − θ −−−−→ χ2d


= n θn − θ
n→+∞

et on obtient, via le Théorème de Slutsky,

√ 1/2 2
T
L
H n θ n − θ −−−−→ χ2d


Cn := nH n θn − θ = n θn − θ
n→+∞

et on peut ainsi construire un test asymptotique pour tester θ = θ0 . En effet, Figure 4.4, on voit que
lorsque la taille d’échantillon augmente, on voit que la fonction de répartition de Cn s’approche
de celle d’une Chi 2 à 5 degrés de liberté. A noter cependant que si α est trop grand, il semble
que l’agorithme de gradient met trop de temps avant d’arriver à convergence, ce qui implique une
moins bonne performance de l’algorithme moyenné dans ce cas, et donc également de l’estima-
teur de la Hessienne. Ceci peut expliquer en partie le fait que les résultats de la Figure 4.4 soient
légèrement moins bon qu’attendu.

1.00

0.75

α = 0.66
F(x)

0.50 α = 0.75
Chi deux

0.25

0.00

0 5 10 15 20 25
x

F IGURE 4.4 – Comparaison de la fonction de répartition de Cn , avec n = 20000 et α = 0.66 ou

α = 0.75, et de la fonction de répartition d’une Chi deux à 5 degrés de liberté dans le cadre de la
régression logistique.
4.2 Algorithme de Newton stochastique 67

4.1.5 Remarques

On a vu que l’algorithme moyenné permet d’accélérer les méthodes de gradient stochastiques,

notamment lorsque celles ci arrivent à convergence. Cependant, on a également vu qu’elles sont
assez sensibles à une mauvaise initialisation. Pour pallier ce problème, une solution peut être de
considérer une version pondérée de la moyennisation (voir [MP11]). Cette pondération permet
de donner plus de poids aux derniers estimateurs obtenus à l’aide de l’algorithme de gradient
stochastique (qui sont censés être les meilleurs). On peut par exemple considérer un algorithme
pondéré de la forme [BGB20]

n
1
mn = n
∑k=1 log(k + 1)w
∑ log(k + 1)w mk
k =1

avec w > 0. Le terme log(k + 1) permet donc de mettre plus de poids aux derniers estimateurs de
gradient. Dans la Figure 4.5 on peut voir que dans le cas de la régression logistique où la mauvaise
initialisation pouvait conduire à des résultats moyens en pratique, la pondération permet de pallier
partiellement ce problème.

10.00
Erreur quadratique moyenne

1.00 SGD avec α = 0.66

SGD avec α = 0.75
ASGD avec α = 0.66
ASGD avec α = 0.75
0.10
WASGD avec α = 0.66
WASGD avec α = 0.75

0.01

1 10 100 1000 10000

Taille de l'échantillon

F IGURE 4.5 – Evolution de l’erreur quadratique moyenne par rapport à la taille de l’échantillon
des estimateurs de gradients θn (SGD) et de leurs versions moyennées θ n (ASGD) dans le cadre de
la régression logistique.

4.2 Algorithme de Newton stochastique

4.2.1 Idée de l’algorithme de Newton stochastique

Contrairement à ce que l’on peut faire en optimisation déterministe, on ne peut pas penser utiliser
l’algorithme de Newton stochastique pour améliorer la vitesse de convergence par rapport aux
estimateurs de gradient stochastiques moyennés. En effet, on a vu que sous certains critères de
régularité, ceux-ci ont un comportement asymptotique optimal. L’idée est plutôt de créer une suite
68 Accélération des méthodes de gradient stochastiques

de pas adaptée à toutes les directions du gradient, permettant de mieux traiter certains cas en
pratique. En effet, rappelons que les estimateurs de gradient stochastique (mn )n vérifient

E [mn+1 |Fn ] = mn − γn+1 ∇ G (mn ) .

Ainsi, lorsque mn ' m, on a ∇ G (mn ) ' ∇2 G (m) (mn − m), et on a alors

E [mn+1 − m|Fn ] ' mn − m − γn+1 ∇2 G (m) (mn − m) = Id − γn+1 ∇2 G (m) (mn − m) .

Dans le cas où les valeurs propres de ∇2 G (m) sont à des échelles très différentes, il n’est pas
possible de régler le paramètre cγ pour que le pas soit adapté à toutes les directions. Prenons
l’exemple simple de la régression linéaire. Posons le modèle

Y = XT θ + e

avec e ∼ N (0, 1), θ ∈ R2 et !!

10−2 0
X∼N 0,
0 102
Il vient immédiatement que pour tout h,
!
h i 10−2 0
∇2 G (h) = E XX T = .
0 102

Ainsi, comme dans ce cadre on a exactement ∇ G (mn ) = ∇2 G (m) (θn − θ ), il vient, en notant θ (1)
et θ (2) les premières coordonnées de θ, et en prenant les même notations pour θn ,

cγ 10−2  (1)
h i   
(1)
E θ n +1 (1)
− θ |Fn = 1 − θ n − θ (1)
( n + 1) α
cγ 102
h i    
(2) (2)
E θn+1 − θ (2) |Fn = 1 − θ n − θ (2)
( n + 1) α

Ainsi, choisir cγ proche de 102 permettrait d’avoir un pas adapté pour la première coordonnée
mais ferait "exploser" la deuxième cordonnée, dans le sens où pour les premiers pas, on aurait des
pas de l’ordre de 104 . Faire l’inverse, i.e prendre cγ = 10−2 , permettrait cette fois-ci d’avoir un pas
adapté à la seconde coordonnée, mais on aurait un pas très petit pour la première coordonnée, et les
estimateurs risqueraient de "ne pas bouger". Prendre un entre deux, i.e cγ proche de 1, apporterait
les deux problèmes, ce que semble indiquer la figure 4.6. A noter que pour la Figure 4.6, on a pris
un cas normalement plus simple que le précédent, i.e on a pris des valeurs propres égales à 0.1 et
10.
4.2 Algorithme de Newton stochastique 69

1 2 3
0.5 60

0.4 40
1e+44
0.3 20

0.2 0 0e+00
0.1 −20
0.0 −40 −1e+44
0 250 500 750 1000 0 250 500 750 1000 0 250 500 750 1000 SGD

4 5 6 ASGD
500
0.0 5.0e+44 θ

−0.2 0 0.0e+00

−5.0e+44
−0.4 −500
−1.0e+45
−0.6 −1000 −1.5e+45

0 250 500 750 1000 0 250 500 750 1000 0 250 500 750 1000
Sample size

F IGURE 4.6 – Evolution des estimateurs de la première coordonnée (en haut) et de la deuxième (en
bas) pour, de gauche à droite, cγ = 0.1, cγ = 1 et cγ = 10.

Ainsi, une solution pour régler ce problème serait de supposer que ∇2 G (m) est inversible et de
considérer un algorithme de Newton stochastique, i.e un algorithme de la forme

1
m n +1 = m n − ∇ 2 G ( m ) −1 ∇ h g ( X n +1 , m n ) .
n+1

Dans le cas de la régression linéaire, on aurait alors

 
1 1
E [θn+1 − θ |Fn ] = θn − θ − ∇ 2 G ( θ ) −1 ∇ 2 G ( θ ) ( θ n − θ ) = 1− (θn − θ ) .
n+1 n+1

On aurait alors un biais E [θn − θ ] = 1

(θ0 − θ ), et ce, quelles que soient les différences d’échelles
n +1
entre les valeurs propres (tant qu’elles sont strictement positives). En effet, dans la figure 4.7, on
voit bien que les estimateurs des deux coordonnées arrivent rapidement à convergence.

1 2

0.0

2
−0.2

1 −0.4 θ
Newton

−0.6

−0.8
0 250 500 750 1000 0 250 500 750 1000
Sample size

F IGURE 4.7 – Evolution des estimateurs de la première coordonnée (à gauche) et de la deuxième

coordonnée (à droite) pour l’algorithme de Newton stochastique.

Cependant, on n’a généralement pas accès à la matrice Hessienne de G en m, et encore moins à son
70 Accélération des méthodes de gradient stochastiques

inverse. On va donc remplacer ∇2 G (m) par un estimateur.

4.2.2 L’algorithme de Newton stochastique

Dans tout ce qui suit, on note H := ∇2 G (m) et on suppose que l’hypothèse (PS2) est vérifiée, i.e
que H est inversible. L’algorithme de Newton stochastique est défini de manière récursive pour
tout n ≥ 0 par [BGB20]
1 −1
m̃n+1 = m̃n − H ∇h g ( Xn+1 , m̃n ) (4.2)
n+1 n
−1
avec m̃0 borné. De plus, H n est un estimateur récursif de H −1 , symétrique et défini positif, et il
existe une filtration (Fn ) telle que
−1
• H n et m̃n soient Fn -mesurable.
• Xn+1 est indépendant de Fn .
−1
A noter que si on considère la filtration générée par l’échantillon et si H n ne dépend que de
X1 , . . . , Xn et m̃0 , . . . , m̃n , alors les hypothèses sur la filtration sont vérifiées. On verra dans les
Sections 4.2.5 et 4.2.6 comment construire de tels estimateurs en ligne de l’inverse de la Hessienne
pour les régressions linéaires et logistiques. Afin d’assurer la convergence des estimateurs obtenus
à l’aide de l’algorithme de Newton stochastique, on suppose maintenant que l’hypothèse suivante
est vérifiée :
(PS5) La Hessienne de G est uniformément bornée, i.e il existe une constante L∇G telle que
pour tout h ∈ Rd ,
∇2 G ( h ) op
≤ L∇G .

Cas avec gradient et estimateurs de la Hessienne bornés

Afin d’obtenir "facilement" la convergence des estimateurs obtenus à l’aide de l’algorithme de

Newton stochastique, on fait d’abord l’hypothèse que l’on a un gradient "borné", i.e :
(PS0’) On suppose qu’il existe une constante positive C telle que pour tout h ∈ Rd :
h i
E k∇h g ( X, h)k2 ≤ C.

De la même façon, pour simplifier les preuves et afin d’assurer la consistance des estimateurs, on
supposera que les valeurs propres de l’estimateur de la Hessienne sont uniformément bornées, i.e :
(H0) Il existe des constantes strictement positives λinf , λsup telles que pour tout n ≥ 0,

−1 −1
   
λmin H n ≥ λinf et λmax H n ≤ λsup .

A noter que cette hypothèse est extrêmement restrictive. Cependant, on donne ce cadre de travail
afin d’obtenir une première preuve assez simple de la consistance de m̃n .
4.2 Algorithme de Newton stochastique 71

Théorème 4.2.1. On suppose que les hypothèse (PS0’), (PS2), (PS5) et (H0) sont vérifiées. Alors

p.s
m̃n −−−−→ m.
n→+∞

Démonstration. A l’aide d’un développement de Taylor de la fonction G et grâce à l’hypothèse

(PS5),

G (m̃n+1 )
Z 1
= G (m̃n ) + ∇ G (m̃n )T (m̃n+1 − m̃n ) + (m̃n+1 − m̃n )T (1 − t)∇2 G (m̃n+1 + t (m̃n − m̃n+1 )) dt (m̃n+1 − m̃n )
0
Z 1
T
≤ G (m̃n ) + ∇ G (m̃n ) (m̃n+1 − m̃n ) + (1 − t) ∇2 G (m̃n+1 + t (m̃n − m̃n+1 )) op
dt km̃n+1 − m̃n k2
0
L
≤ G (m̃n ) + ∇ G (m̃n ) (m̃n+1 − m̃n ) + ∇G km̃n+1 − m̃n k2
T
2

1 −1
Alors, comme m̃n+1 − m̃n = − n+ 1 H n ∇ h g ( Xn+1 , m̃n ),

1 −1 L 1 −1 2
G (m̃n+1 ) = G (m̃n ) − ∇ G (m̃n )T H n ∇h g ( Xn+1 , m̃n ) + ∇G H n ∇ h g ( X n + 1 , m̃ n )
n+1 2 ( n + 1)2
1 −1 L 1 −1 2
≤ G (m̃n ) − ∇ G (m̃n )T H n ∇h g ( Xn+1 , m̃n ) + ∇G 2
Hn k∇h g ( Xn+1 , m̃n )k2
n+1 2 ( n + 1) op

On note maintenant Vn = G (m̃n ) − G (m). On peut alors réécrire l’inégalité précédente comme

1 −1 L 1 −1 2
Vn+1 ≤ Vn − ∇ G (m̃n )T H n ∇h g ( Xn+1 , m̃n ) + ∇G Hn k∇h g ( Xn+1 , m̃n )k2
n+1 2 ( n + 1)2 op

−1
et en prenant l’espérance conditionnelle, comme m̃n et H n sont Fn -mesurables,

1 −1 L 1 −1 2 h i
E [Vn+1 |Fn ] ≤ Vn − ∇ G (m̃n )T H n ∇ G (m̃n ) + ∇G Hn E k∇h g ( Xn+1 , m̃n )k2 |Fn .
n+1 2 ( n + 1)2 op
(4.3)

Alors, grâce à l’hypothèse (PS0’), il vient

1 
−1
 CL∇G 1 −1 2
E [Vn+1 |Fn ] ≤ Vn − λmin H n k∇ G (m̃n )k2 + 2
Hn
n+1 2 ( n + 1) op

Remarquons que grâce à l’hypothèse (H0), on peut réécrire l’inégalité précédente comme

1 CL∇G 1
E [Vn+1 |Fn ] ≤ Vn − λ k∇ G (m̃n )k2 + λ2 .
n + 1 inf 2 (n + 1)2 sup

De plus, on a
1 1
∑ ( n + 1 ) 2 2
CL∇G λ2sup < +∞ p.s.
n ≥0
72 Accélération des méthodes de gradient stochastiques

et grâce au théorème de Robbins-Siegmund, Vn converge presque sûrement vers une variable aléa-
toire finie et
1
∑ λinf k∇ G (m̃n )k2 < +∞ p.s.
n ≥0 n + 1

Cela implique nécessairement que lim infn k∇ G (m̃n )k = 0 presque sûrement. Comme G est stric-
tement convexe, cela implique aussi que

lim inf km̃n − mk = 0 p.s et lim inf Vn = lim inf G (m̃n ) − G (m) = 0 p.s,
n n n

et comme Vn converge presque sûrement vers une variable aléatoire, cela implique que G (m̃n )
converge presque sûrement vers G (m) et par stricte convexité, que m̃n converge presque sûrement
vers m.

Cas général

On peut obtenir la convergence des estimateurs en faisant des hypothèses moins fortes sur les
valeurs propres de l’estimateur de H −1 . Plus précisément, on peut remplacer l’hypothèse (H0)
par :
−1
(H1) On peut contrôler les plus grandes valeurs propres de H n et H n : il existe β ∈ (0, 1/2)
tel que
−1

   
λmax H n = O(1) p.s. et λmax H n = O nβ p.s.

Cette hypothèse implique que, sans même savoir si m̃n converge, on doit pouvoir contrôler le
comportement des valeurs propres (plus petite et plus grande) de l’estimateur de la Hessienne.
On verra Section 4.2.6 comment modifier les estimateurs récursifs naturels de la Hessienne afin
que cette hypothèse soit vérifiée. De plus, on peut remplacer l’hypothèse (PS0’) par l’hypothèse
suivante :
(PS0”) Il existe des constantes positives C, C 0 telles que pour tout h ∈ Rd , on ait
h i
E k∇h g ( X, h)k2 ≤ C + C 0 ( G (h) − G (m)) .

A noter que l’hypothèse (PS0”) n’est pas beaucoup plus restrictive que (PS0). En effet, dans le
cas de la régression logistique, on peut voir qu’elles sont toutes les deux vérifiées avec un mini-
mum d’hypothèses sur la variable explicative X. De plus, si la fonction est µ-fortement convexe,
on a pour tout h ∈ Rd , kh − mk2 ≤ 2
− G (m)), et l’hypothèse (PS0) implique l’hypothèse
µ ( G (h)
(PS0”). De la même façon, si les hypothèses (PS0”) et (PS5) sont vérifiées, on a G (h) − G (m) ≤
L∇G 2
2 k h − m k , et l’hypothèse (PS0) est alors vérifiée. On peut maintenant montrer la forte consis-
tance des estimateurs.

Théorème 4.2.2. On suppose que les hypothèse (PS0”), (PS2), (PS5) et (H1) sont vérifiées. Alors

p.s
m̃n −−−−→ m.
n→+∞
4.2 Algorithme de Newton stochastique 73

On admettra ce théorème mais la preuve est disponible dans [BGB20] ainsi que dans la version
longue.

4.2.3 Vitesses de convergence

Afin de d’obtenir les vitesses de convergence, on est "obligé" d’avoir la forte consistance de l’esti-
mateur de la Hessienne et de son inverse. Dans ce but, on introduit l’hypothèse suivante :
(H2) Si les hypothèses (PS0”), (PS2),(PS5) et (H1) sont vérifiées, alors

p.s −1 p.s
H n −−−−→ H et H n −−−−→ H −1 .
n→+∞ n→+∞

Cette hypothèse veut tout simplement dire que si l’on a la convergence de m̃n , on a également la
convergence de l’estimateur de la Hessienne. On peut maintenant donner la vitesse de convergence
de l’algorithme de Newton stochastique.

Théorème 4.2.3. On suppose que les hypothèses (PS0”), (PS2), (PS4), (PS5), (H1) et (H2) sont vérifiées.
Alors pour tout δ > 0,
(ln n)1+δ
 
2
km̃n − mk = o p.s..
n
De plus, si l’hypothèse (PS1) est vérifiée, alors
 
2 ln n
km̃n − mk = O p.s.
n

Démonstration. Remarquons d’abord que l’on peut écrire l’algorithme de Newton comme

1 −1 1 −1
m̃n+1 − m = m̃n − m − H n ∇ G (m̃n ) + H n ξ̃ n+1 , (4.4)
n+1 n+1


avec ξ̃ n+1 := ∇h g ( Xn+1 , m̃n ) − ∇ G (m̃n ). On a donc que ξ̃ n est une suite de différences de mar-
tingale par rapport à la filtration (Fn ). En linéarisant le gradient, on a alors

1 −1 1 −1 1 −1
m̃n+1 − m = m̃n − m − H n H (m̃n − m) − H n δ̃n + H ξ̃ n+1
n+1 n+1 n+1 n

où δ̃n := ∇ G (m̃n ) − H (m̃n − m) est le terme de reste dans la décomposition de Taylor du gradient.
De plus, on peut réécrire l’égalité précédente comme

1 1  −1  1 −1 1 −1
m̃n+1 − m = m̃n − m − H −1 H (m̃n − m) − H n − H −1 H (m̃n − m) − H n δ̃n + H n ξ̃ n+1
 n+ 1 n + 1 n + 1 n + 1
1 1  −1  1 −1 1 −1
= 1− (m̃n − m) − H n − H −1 H (m̃n − m) − H δ̃n + H ξ̃ n+1 .
n+1 n+1 n+1 n n+1 n
(4.5)
74 Accélération des méthodes de gradient stochastiques

On peut donc montrer (récurrence immédiate) que pour tout n ≥ 1,

1 n −1  −1  1 n −1 −1 1 n −1 −1
n k∑ n k∑ n k∑
−1
m̃n − m = − H k − H H ( m̃ k − m ) − H k δ̃k + H k ξ̃ k+1 . (4.6)
=0 =0 =0
| {z } | {z }
=:∆˜ n =: M̃n

A noter que M̃n est une martingale par rapport à la filtration (Fn ). A noter que grâce aux hypo-
thèses (PS0”) et (PS5), on a
h
2
i h i L C0
E ξ̃ n+1 |Fn ≤ E k∇h g ( Xn+1 , m̃n )k2 |Fn ≤ C + C 0 ( G (m̃n ) − G (m)) ≤ C + ∇G km̃n − mk2 .
2

Vitesse de convergence de M̃n . A noter que M̃n est une martingale mais pas nécéssairement de
carré intégrable. Cependant, on peut considérer la suite d’évènements ( An )n≥0 définie pour tout
 
−1 2
n par An := Hn ≤ λmin , kmn − mk ≤ 1 . Comme mn converge presque sûrement vers m et
op
−1 −1
comme Hn converge presque sûrement vers H −1 (et que H −1 = λmin ), 1 An converge presque
sûrement vers 1. On peut maintenant réécrire M̃n comme

n −1 n −1
M̃n = ∑ H k ξ̃ k+1 1 A k
+ ∑ H k ξ̃ k+1 1 A C
k
k =0 k =0
| {z } | {z }
=: M̃1,n =: M̃2,n

et comme 1 ACn converge presque sûrement vers 0, on a

 
1 1
M̃2,n = O p.s.
n n

et ce terme est donc négligeable. Afin d’obtenir la vitesse de convergence du terme de martingale
M̃1,n , on va calculer son crochet. Par linéarité de l’espérance, on a pour tout n ≥ 1,

n −1  T 
−1 −1

M̃1 n
= ∑E H k ξ̃ k+1 H k ξ̃ k+1 |Fk 1 Ak
k =0
n −1
−1 −1
h i
= ∑ H k E ξ̃ k+1 ξ̃ kT+1 |Fk H k 1 Ak
k =0
n −1 n −1
−1 −1 −1 −1
h i
= ∑ k H E ∇ h g ( X k +1 , m̃ k ) ∇ h g ( X k +1 , m̃ k ) T
|F k H k 1 A k
− ∑ H k ∇G (m̃k ) ∇G (m̃k )T H k 1 Ak
k =0 | {z } k =0
=Σ(m̃k )

−1
Comme H k , m̃k , 1 Ak convergent presque sûrement vers H −1 , m, 1, et par continuité de Σ (hypo-
thèse (PS4)), on a

−1 −1 p.s
h i
H k E ∇h g ( Xk+1 , m̃k ) ∇h g ( Xk+1 , m̃k )T |Fk H k 1 Ak −−−−→ H −1 Σ(m) H −1 .
n→+∞
4.2 Algorithme de Newton stochastique 75

Ainsi, en appliquant le lemme de Toeplitz,

1 n −1 −1 h i
−1 p.s
n k∑
T
H k E ∇ h g ( X k +1 , m̃ k ) ∇ h g ( X k +1 , m̃ k ) |F −−−→ H −1 Σ(m) H −1 .
k H k 1 Ak −
n→+∞
=1

De plus, comme ∇ G est L∇G -lipschitz, et comme m̃k converge presque sûrement vers m et comme
−1
H n converge vers H −1 , on a

−1 −1 −1 2 −1 2 p.s
H k ∇ G (m̃k ) ∇ G (m̃k )T H k ≤ Hk k∇ G (m̃k )k2 ≤ L2∇G H k km̃k − mk2 −−−−→ 0.
op op op n→+∞

En particulier, en appliquant le lemme de Toeplitz, on obtient

1 n −1 −1 −1 p.s
‘ ∑
n k =0
H k ∇ G (m̃k ) ∇ G (m̃k )T H k 1 Ak −−−−→ 0
n→+∞

et donc
1 p.s
M̃1 −−−−→
n n→+∞
H −1 Σ ( m ) H −1 ,
n
et en appliquant une loi des grands nombres pour les martingales vectorielles, on a pour tout δ > 0

2
(ln n)1+δ
 
1
M̃n =o p.s
n+1 n

De plus, si (PS1) est vérifiée, on a

2  
1 ln n
M̃n =O p.s
n+1 n

˜ n . Remarquons d’abord que grâce aux hypothèses (PS3) et (PS5), et

Vitesse de convergence de ∆
−1
comme m̃k et H n convergent presque sûrement vers m et H −1 , on a

−1 −1
 
H k − H −1 H (m̃k − m) = o (km̃k − mk) p.s et H k δ̃k = o (km̃k − mk) p.s.

Soit c ∈ (0, 1). On introduit maintenant la suite d’évènement ( Ak,c ) définie pour tout k ≥ 1 par

−1 −1
n   o
Ak,c = H k − H −1 H ∇ G (m̃k ) + H k δ̃k ≤ c km̃k − mk .

˜ n +1
D’après ce qui précède, 1 AC converge presque sûrement vers 0. On peut alors réécrire ∆
k,c
comme
 
1 ˜n + 1

−1
 1 −1
˜ n +1 =
∆ 1− ∆ H n − H −1 H ∇ G (m̃n ) + H δ̃n
n+1 n+1 n+1 n
 
1 ˜ n + c km̃n − mk 1 A + 1 −1 −1
 
−1
≤ 1− ∆ n
H n − H H ∇ G (m̃n ) + H n δ̃n 1 ACn,c
n+1 n+1 n+1
76 Accélération des méthodes de gradient stochastiques

˜ n + 1 M̃n , on obtient
Comme km̃n − mk ≤ ∆ n

(1 − c )
 
c 1 
−1

−1
˜ n +1 ≤
∆ 1− ˜n +
∆ M̃n + H n − H −1 H ∇ G (m̃n ) + H n δ̃n 1 ACn,c
n+1 ( n + 1) n n+1

En notant c̃ = 1 − c, comme 1 + x ≤ e x et à l’aide d’une comparaison série intégrale,

! c̃
n   n 
c̃ 1 k+1
∏ 1−
j
≤ exp −c̃ ∑
j
≤ exp (−c̃ (ln(n + 1) − ln(k + 1))) ≤
n+1
j = k +1 j = k +1

Ainsi, on peut montrer à l’aide d’une récurrence que pour tout n ≥ 0,

n −1 n −1
1 1 1 (k + 1)c̃  −1 
−1
˜n ≤
∆
(n + 1)c̃ ∑ (k + 1) (k + 1)k M̃k + (n + 1)c̃
c̃
∑ k+1
Hk − H −1
H ∇ G (m̃k ) + H n δ̃k 1 AC
k,c
k =1 k =0
| {z } | {z }
:= R3,n := R4,n

(4.7)

Vitesse de convergence de R4,n . Comme 1CAk,c converge presque sûrement vers 0, on a

n −1
(k + 1)c̃  −1 
−1
∑ k+1
H k − H −1 H ∇ G (m̃k ) + H n δ̃k 1 AC < +∞
k,c
p.s.
k =0

et on obtient donc  
1
R4,n = O p.s
(n + 1)c̃
qui est négligeable dès que c̃ > 1/2, i.e dès que c < 1/2.

Vitesse de convergence de R3,n . Comme on a la vitesse de convergence de M̃n , pour tout δ ≥ 0 (le
cas δ = 0 correspondant au cas où le gradient admet un moment conditionnel d’ordre strictement
plus grand que 2), il existe une variable aléatoire positive Bδ telle que pour tout k ≥ 1,
√
M̃k ≤ Bδ ln(k + 1)1/2+δ k + 1 p.s.

Ainsi, on a
  1/2+δ

Bδ n −1
1 √  O ln(n+1) c̃ p.s si c̃ < 1/2
∑ (k + 1)c̃ (k + 1)k ln(k + 1)  (n+11/2
1/2+δ )
R3,n ≤ k+1 = +

(n + 1)c̃
δ
k =1
 O ln(n√+1) p.s si c̃ > 1/2
n +1

et on conclut la preuve en prenant c̃ > 1/2, i.e en prenant c < 1/2.

4.2.4 Normalité asymptotique

Afin d’obtenir la normalité asymptotique des estimateurs, on est obligé d’avoir une vitesse de
convergence de l’estimateur de la Hessienne. Pour ce faire, on introduit l’hypothèse suivante :
4.2 Algorithme de Newton stochastique 77

(H3) Si les hypothèses (PS0”), (PS2), (PS3), (PS4), (PS5), (H1) et (H2) sont vérifiées, alors il
existe p H > 0 tel que  
2 1
Hn − H =O p.s.
op n pH
Cette hypothèse signifie juste que obtenir une vitesse de convergence presque sûre de l’estimateur
m̃n permet d’obtenir une vitesse de convergence presque sûre de H n . Le théorème suivant nous
donne la normalité asymptotique des estimateurs obtenus à l’aide d’algorithmes de Newton sto-
chastiques. En particulier, il nous indique que ces estimateurs ont un comportement asymptotique
optimal, dans le sens où ils ont le même comportement asymptotique que les M-estimateurs.

Théorème 4.2.4. On suppose que les hypothèses (PS0”), (PS1), (PS2), (PS3), (PS4), (PS5) (H1), (H2) et
(H3) sont vérifiées. Alors
√ L
 
n (m̃n − θ ) −−−−→ N 0, H −1 ΣH −1
n→+∞
h i
avec Σ = Σ(m) = E ∇h g ( X, m) ∇h g ( X, m)T .

Démonstration. On rappelle que l’on a

1 n −1  −1  1 n −1 −1 1 n −1 −1
n k∑ n k∑ n k∑
−1
m̃n − m = − H k − H H ( m̃ k − m ) − H k δ̃k + H k ξ̃ k+1 .
=0 =0 =0
| {z } | {z }
=:∆˜ n =: M̃n

et on va donc donner les vitesses de convergence de ces termes pour montrer que c’est bien le
terme de martingale qui "porte" la convergence.

˜ n . Comme m̃n converge presque sûrement vers m et grâce à l’hypo-

Vitesse de convergence de ∆
thèse (PS3), on a  
δ̃n = O km̃n − mk2 p.s.
−1
et donc, comme H n converge presque sûrement vers H −1 , en appliquant le lemme de Toeplitz et
grâce au Théorème 4.2.3, on obtient que pour tout δ > 0,
!
n −1 n −1 n −1
(ln(k + 1))1+δ ln(k + 1)2+δ
 
−1 −1 k+1
∑ H k δ̃k ≤ ∑ k+1
Hk
op ln(k + 1)1+δ
δ̃k =o ∑ k+1
p.s
k =0 k =0 k =0

et donc,
1 n −1 −1 (ln n)1+δ
 

n k∑
H k δ̃k = o p.s.
=0
n

Ce terme est donc négligeable. De la même façon, en appliquant le lemme de Toeplitz, grâce au
78 Accélération des méthodes de gradient stochastiques

Théorème 4.2.3 et à l’hypothèse (H3), on a

n −1 
−1

∑ H k − H −1 H (m̃k − m)
k =0
n −1 1 √ !
ln(k + 1) 2 +δ
 
pH −1 k+1
≤ ∑ 1+ p H H op
( k + 1) 2 Hk − H −1 1 km̃k − mk
k =0 ( k + 1) 2 op ln(k + 1) 2 +δ
!
n −1
ln(k + 1)1/2+δ
=o ∑ (k + 1)1/2+ p H /2
p.s
k =0

et on obtient donc

1 n −1  −1 (ln n)1/2+δ
  

n k∑
−1
H k − H H (m̃k − m) = o p.s
=0 n1/2+ p H

et ce comme p H > 0, ce terme est négligeable.

Vitesse de convergence de M̃n . On a déjà montré que M̃n = M̃1,n + M̃2,n où M̃2,n est négligeable
et M̃1,n est une martingale dont le crochet vérifie

1 p.s
M̃1 −−−−→
n n→+∞
H −1 ΣH −1 .
n

Il faut donc montrer que la condition de Lindeberg est vérifiée. Pour cela, il suffit de voir que grâce
à l’hypothèse (PS1), et comme ξ̃ k+1 ≤ k∇h g ( Xk+1 , m̃k )k + kE [∇h g ( Xk+1 , m̃k ) |Fk ]k, on a
 
−1 2+2η  
−1 2
E H k ξ̃ k+1 1 Ak |Fk ≤ 21+2η Cη 1 + km̃k − mk1+2η H k −2
1 Ak ≤ 24+2η λmin .
op

Le TLC pour les martingales vectorielles nous donne donc

√ L

−1 −1

n M̃1,n −−−−→ N 0, H ΣH
n→+∞

ce qui conclut la preuve.

4.2.5 Application au modèle linéaire

On se place maintenant dans le cadre de la régression linéaire défini par (1.1). On rappelle que la
Hessienne de la fonction à minimiser G est définie pour tout h ∈ Rd par ∇2 G (h) = E XX T , et on
 

supposera que cette matrice est définie positive. Un estimateur naturel de H = ∇2 G (θ ) est donc
!
n
1
Hn =
n+1 ∑ Xk XkT + H0
k =1
4.2 Algorithme de Newton stochastique 79

où H0 est une matrice symétrique définie positive (on peut prendre H0 = Id par exemple). A noter
que l’on peut écrire H n de manière récursive comme

1  
H n +1 = H n + Xn+1 XnT+1 − H n .
n+2

On va maintenant s’intéresser à l’inversion de la matrice H n . Pour cela, on va introduire la matrice

Hn = (n + 1) H n que l’on peut écrire comme

Hn+1 = Hn + Xn+1 XnT+1 .

Afin de réduire le temps de calcul, on ne va pas inverser directement cette matrice à chaque ité-
ration, mais plutôt utiliser la formule d’inversion de Ricatti (aussi appelée formule de Sherman-
Morrison) suivante :

Théorème 4.2.5 (Formule de Riccati). Soit A ∈ Md (R) une matrice inversible et u, v ∈ Rd . Si 1 +

v T A−1 u 6= 0, alors A + uv T est inversible et
  −1   −1
A + uv T = A −1 − 1 + v T A −1 u A−1 uv T A−1 .

La preuve est évidente et est disponible dans la version longue. En particulier, si A est une matrice
définie positive, pour tout u ∈ Rd on a 1 + u T A−1 u ≥ 1 et donc
    −1
−1 −1
A + uu T
=A − 1+u AT
u A−1 uu T A−1 .

A noter que cette opération ne représente "que" O d2 opérations. On peut donc mettre à jour

l’estimateur de l’inverse de la Hessienne comme suit :

  −1
Hn−+11 = Hn−1 − 1 + XnT+1 Hn−1 Xn+1 Hn−1 Xn+1 XnT+1 Hn−1

−1
et H n+1 = (n + 2) Hn−+11 . Ainsi, une fois que l’on a H0−1 , on peut facilement mettre à jours nos
estimateurs, ce qui conduit à l’algorithme de Newton stochastique suivant :

1 −1
 
θ̃n+1 = θ̃n + H n Yn+1 − θ̃nT Xn+1 Xn+1
n+1
  −1
Hn−+11 = Hn−1 − 1 + XnT+1 Hn−1 Xn+1 Hn−1 Xn+1 XnT+1 Hn−1

−1
avec H n = (n + 1) Hn−1 . A noter que l’on pourrait réécrire l’algorithme comme
 
θ̃n+1 = θ̃n + Hn−1 Yn+1 − θ̃nT Xn+1 Xn+1
  −1
Hn−+11 = Hn−1 − 1 + XnT+1 Hn−1 Xn+1 Hn−1 Xn+1 XnT+1 Hn−1 .
80 Accélération des méthodes de gradient stochastiques

On peut alors obtenir les vitesses de convergence des estimateurs, et ce, avec des hypothèses assez
faibles.

Théorème 4.2.6. Si il existe η > 0 tel que X et e admettent des moments d’ordre 4 + 4η et 2 + 2η, et si
E XX T est définie positive, alors
 

√
 
2 ln n
L  
θ̃n − θ =O p.s. et n θ̃n − θ −−−−→ N 0, σ2 H −1 .
n n→+∞

Démonstration. On a déjà vu que sous ces hypothèses, les hypothèses (PS1) à (PS4) sont vérifiées
et l’hypothèse (PS0”) est clairement vérifiée. De plus pour tout h ∈ Rd , on a
h i h i
∇2 G ( h ) op
= E XX T ≤ E k X k2
op

et l’hypothèse (PS5) est donc vérifiée. De plus, comme X admet un moment d’ordre 4, on a par la
loi du log-itéré  
2 ln ln n
Hn − H =O p.s
n
et les hypothèses (H1) à (H3) sont vérifiées, ce qui conclut la preuve.

Dans la Figure 4.8, on considère le modèle

θ = (−4, −3, −2, −1, 0, 1, 2, 3, 4, 5)T ∈ R10 , X ∼ N 0, diag σi2

, et e ∼ N (0, 1)

i2
avec pour tout i = 1, . . . , d, σi2 = d2
. On a donc la plus grande valeur propre de la Hessienne
qui est 100 fois plus grande que la plus petite. On voit bien Figure 4.8 que les estimateurs de
gradient peinent à arriver à convergence, et donc, que les estimateurs moyennés ne permettent pas
d’accélérer la convergence. A contrario, on voit bien que malgré ces différences d’échelles entre les
valeurs propres de la Hessienne, l’algorithme de Newton stochastique converge très rapidement.

100.0
Quadratic mean error

10.0
ASGD
SGD
1.0
SN

0.1

1 10 100 1000
Sample size

F IGURE 4.8 – Evolution de l’erreur quadratique moyenne des estimateurs de gradient θn (SGD), de
leur version moyennée θ n (ASGD) et des estimateurs de Newton stochastique θ̃n (SN) en fonction
de la taille de l’échantilon dans le cadre du modèle linéaire.
4.2 Algorithme de Newton stochastique 81

De plus, on vu que pour l’algorithme de gradient stochastique moyenné, on a

1
T
L
Cn := n θ n − θ H n θ n − θ −−−−→ χ2d ,
σ2 n→+∞

et de la même façon, on a

1
T
L
Kn : = 2
n θ̃n − θ H n θ̃n − θ −−−−→ χ2d ,
σ n→+∞

et on peut ainsi construire un test asymptotique pour tester θ = θ0 . En effet, Figure 4.9, on s’inté-
resse aux fonctions de répartitions de Cn et Kn estimées à l’aide de 5000 échantillons. On voit que
la fonction de répartition de Kn s’approche de celle d’une Chi 2 à 10 degrés de liberté, tandis que
celle de Cn en est très loin. En effet, l’algorithme de gradient n’étant pas arrivé à convergence, la
moyennisation n’accelère pas du tout la convergence, voire la dessert.

1.00

0.75

Cn
F(x)

0.50 Kn

Chi Square

0.25

0.00
0 10 20 30
x

F IGURE 4.9 – Comparaison des fonctions de répartition de Cn et Kn , pour n = 5000 ), et de la

fonction de répartition d’une Chi 2 à 10 degrés de liberté dans le cadre du modèle linéaire.

De plus, on peut remarquer que pour tout x0 ∈ Rd on peut réécrire le TLC comme
√  T 
L
 
n x0 θ̃n − x0T θ −−−−→ N 0, σ2 x0T H −1 x0
n→+∞

ce que l’on peut réécrire comme

√ x T θ̃n − x0T θ L
n q0 −−−−→ N (0, 1) .
n→+∞
σ2 x0T H −1 x0

Ainsi, comme on dispose d’un estimateur en ligne de H −1 , il ne reste qu’à avoir un estimateur
récursif de σ2 pour obtenir des intervalles de confiance en ligne de x0T θ. Une façon pour estimer σ2
est de considérer l’erreur quadratique moyenne des prévisions,

1 n  2
n k∑
T
σn2 = Yk − X θ̃
k k −1
=1
82 Accélération des méthodes de gradient stochastiques

ce que l’on peut réécrire de manière récursive comme

1 
2 
σn2+1 = σn2 + Yn+1 − Xn+1 θ̃n − σn2 .
n+1

En effet, le théorème suivant nous confirme que cet estimateur converge rapidement vers σ2 .

Théorème 4.2.7. Si il existe η > 0 tel que X et e admettent des moments d’ordre 4 + 4e et 2 + 2η et que
E XX T est inversible, alors pour tout δ > 0,
 

(ln n)1+δ
 
2 2
σn2 −σ =o p.s.
n

On admettra ce théorème. Grâce au théorème de Slutsky,

√ x T θ̃n − x0 θ L
Cx0 = nq 0 −−−−→ N (0, 1) .
− 1 n →+ ∞
σn2 x0T H n x0T

En effet, Figure 4.10, on s’intéresse à la densité de Ce1 , i.e on prend x0 = e1 = (1, 0, . . . , 0)T et on
compare sa densité à celle d’une loi normale centrée réduite. La densité de Ce1 est estimée à l’aide
de 1000 échantillons.

n=1000 n=5000

0.4 0.4

0.3 0.3
f(x)

0.2 0.2 Loi normale

Newton

0.1 0.1

0.0 0.0

−5.0 −2.5 0.0 2.5 5.0 −5.0 −2.5 0.0 2.5 5.0
x

F IGURE 4.10 – Comparaison de la densité de Ce1 , pour n = 1000 (à gauche) et n = 5000 (à droite),
et de la densité d’une loi normal centrée réduite dans le cadre de la régression linéaire.

On voit que l’estimation est plutôt bonne et que lorsque la taille d’échantillon augmente, la densité
de Ce1 s’approche de celle de la loi normale centrée réduite, ce qui légitime l’usage de Cx0 pour
l’obtention d’intervalles de confiance. En effet, on peut ainsi construire les intervalles de confiance
asymptotiques en ligne
 q 
−1
σn2 x0T H n x0
ICn,1−α (θ ) =  x0T θ̃n ± Φ−1 (1 − α/2) √ 
n
4.2 Algorithme de Newton stochastique 83

où Φ−1 (1 − α/2) est le quantile d’ordre 1 − α/2 de la loi normale centrée réduite. On parle d’in-
tervalles de confiance en ligne dans le sens où on peut mettre à jours ces intervalles avec un cout
assez réduit en terme de temps de calculs. On peut également construire un rectangle de confiance
de niveau asymptotique au moins 1 − α. En effet, en considérant B = {e1 , . . . , ed } la base canonique
de Rd , on a  q 
d σ 2 eT H e
 α  n i n i
R1−α (θ ) = ∏ eiT θ̃n ± Φ−1 1 − √ 
i =1
2d n

où Φ−1 (1 − α/2d) est le quantile d’ordre 1 − α/2d de la loi normale centrée réduite.

4.2.6 Application à la régression logistique

On se place maintenant dans le cadre de la régression logistique défini par (1.2). On rappelle éga-
lement que la Hessienne de la fonction que l’on cherche à minimiser G est définie pour tout h ∈ Rd
par h     i
∇2 G (h) = E π hT X 1 − π hT X XX T ,
ex
avec π ( x ) = 1+ e x . Un estimateur naturel de la Hessienne serait donc
!
n
1    
Sn =
n+1
S0 + ∑π θ T Xk 1 − π θ T Xk Xk XkT .
k =1

Cependant, on ne connait généralement pas θ, et il va donc falloir le remplacer par un estimateur

en ligne de θ, conduisant à un premier algorithme de Newton stochastique

1 −1
  
θ̂n+1 = θ̂n + Sn Yn+1 − π θ̂nT Xn+1 Xn+1
n+1
1   T    
S n +1 = S n + π θ̂n Xn+1 1 − π θ̂nT Xn+1 Xn+1 XnT+1 − Sn
n+2
1 n T
1 S0 + ∑k =1 π Xk θ̂k −1 1 − π XkT θ̂k−1 Xk XkT . Se pose





i.e cela reviendrait à considérer Sn = n+
−1
alors deux questions. La première est de savoir comment mettre à jour Sn+1 . Cela peut se faire en
utilisant encore une fois la formule de Riccati. De plus, est-ce que notre estimateur de la Hessienne
vérifie (H1) ? On est malheureusement incapable de suffisamment contrôler la plus petite valeur
propre de Sn et on est donc obligé de proposer une version tronquée de l’algorithme de Newton
stochastique, i.e on va considérer [BGBP19]
   
αn+1 = π θ̃nT Xn+1 1 − π θ̃nT Xn+1
1 −1
  
θ̃n+1 = θ̃n + H n Yn+1 − π θ̃nT Xn+1 Xn+1
n+1
  −1
Hn+1 = Hn − an+1 1 + an+1 XnT+1 Hn−1 Xn+1
−1 −1
Hn−1 Xn+1 XnT+1 Hn−1
84 Accélération des méthodes de gradient stochastiques

−1
n o
c
avec H0−1 symétrique et définie positive, θ̃0 borné, H n = (n + 1) Hn , et an+1 = max αn+1 , (n+β1)β
avec c β > 0 et β ∈ (0, 1/2). A noter que grâce à la formule de Riccati, on peut montrer que

n
Hn = H0 + ∑ ak Xk XkT .
k =1

Le terme de troncature an permet de contrôler le comportement asymptotique de la plus petite

valeurs propre de Hn . En effet, si X admet un moment d’ordre 2, on a

n cβ
1 p.s
h i
cβ ∑ β k k n→+∞
X X T
−
−−− → E XX T
∑nk=1 kβ k =1 k

et en d’autres termes, si E XX T est inversible, on a

 

 ! −1 
cβ n  
λmax  H0 + ∑ β Xk XkT  = O n β −1 p.s,
k =1 k

ce qui nous permet d’obtenir la convergence des estimateurs [BGBP19, BGB20].

Théorème 4.2.8. On suppose que X admet un moment d’ordre 2 et que H := ∇2 G (θ ) est inversible. Alors
θ̃n converge presque sûrement vers θ. De plus, si X admet un moment d’ordre 4, alors

√
 
2 ln n
L  
θ̃n − θ =O p.s. et n θ̃n − θ −−−−→ N 0, H −1 .
n n→+∞

On admettra ce théorème mais la preuve est disponible dans la version longue. Figure 4.11, on
considère le modèle

θ = (1, . . . , 1)T ∈ R5 X ∼ N 0, diag σi2

et

i2
avec pour tout i = 1, . . . , d, σi2 = d2
. On s’attend donc à ce que la plus grande valeur propre de la
Hessienne soit à peu près 25 fois plus grande que la plus petite. On voit bien Figure 4.11 que les
estimateurs de gradient peinent à arriver à convergence, et donc, que les estimateurs moyennés
ne permettent pas d’accélérer la convergence. A contrario, on voit bien que malgré ces différences
d’échelles entre les valeurs propres de la Hessienne, l’algorithme de Newton stochastique converge
très rapidement.
4.2 Algorithme de Newton stochastique 85

3.0

Quadratic mean error

1.0

ASGD

0.3 SGD
SN

0.1

1 10 100 1000
Sample size

F IGURE 4.11 – Evolution de l’erreur quadratique moyenne des estimateurs de gradient θn (SGD),
de leur version moyennée θ n (ASGD) et des estimateurs de Newton stochastique (SN) en fonction
de la taille de l’échantillon dans le cadre de la régression logistique.

A noter que l’on a vu que l’on a, grâce au théorème de continuité,

T
L
n θ̃n − θ H θ̃n − θ −−−−→ χ2d .
n→+∞

Ainsi, comme H n converge presque sûrement vers H, en appliquant le théorème de Slutsky, on

obtient

T
L
Kn := n θ̃n − θ H n θ̃n − θ −−−−→ χ2d .
n→+∞

En effet, Figure 4.12, on s’intéresse à la fonction de répartition de Kn estimée à l’aide de 1000

échantillons. On voit que même pour une relativement petite taille d’échantillon (n = 5000), la
fonction de répartition de Kn s’approche de celle d’une Chi 2 à 10 degrés de liberté.

1.00

0.75
F(x)

Kn
0.50
Chi Square

0.25

0.00
0 10 20 30
x

F IGURE 4.12 – Comparaison de la fonction de répartition de Kn , pour n = 5000 , et de la fonction

de répartition d’une Chi 2 à 10 degrés de liberté.
86 Accélération des méthodes de gradient stochastiques

A noter également que l’on peut réécrire la normalité asymptotique comme

√ x0T θ̃n − x0T θ L

nq −−−−→ N (0, 1)
T − 1 n→+∞
x0 H x0

et grâce au théorème de Slutsky, on obtient

√ x T θ̃n − x0T θ L
Cx0 n q0 −−−−→ N (0, 1).
−1 n→+∞
x0T H n x0

En effet, Figure 4.10, on s’intéresse à la densité de Ce1 , i.e on prend x0 = e1 = (1, 0, . . . , 0)T et on
compare sa densité à celle d’une loi normale centrée réduite.

n=1000 n=5000

0.4 0.4

0.3 0.3
f(x)

0.2 0.2 Loi normale

Newton

0.1 0.1

0.0 0.0

−5.0 −2.5 0.0 2.5 5.0 −5.0 −2.5 0.0 2.5 5.0
x

F IGURE 4.13 – Comparaison de la densité de Ce1 , pour n = 1000 (à gauche) et n = 5000 (à droite),
et de la densité d’une loi normal centrée réduite.

On voit que l’estimation est plutôt bonne et ce, même pour une taille d’échantillon raisonnable
(n = 1000). Ceci légitime donc l’usage de Cx0 pour l’obtention d’intervalles de confiance, i.e on
considère les intervalles de confiance asymptotiques en ligne suivant
  q 
−1
x0T H n x0
P  x0T θ ∈  x0T θ̃n ± Φ−1 (1 − α/2) √  −−−−→ 1 − α
n n→+∞

où Φ−1 (1 − α/2) est le quantile d’ordre 1 − α/2 de la loi normale centrée réduite. On peut éga-
lement construire un rectangle de confiance de niveau asymptotique au moins 1 − α. En effet, en
considérant B = {e1 , . . . , ed } la base canonique de Rd , on a
 q 
d  α eiT H n ei
R 1− α ( θ ) = ∏ eiT θ̃n ± Φ−1 1−
2d
√
n

i =1

où Φ−1 (1 − α/2d) est le quantile d’ordre 1 − α/2d de la loi normale centrée réduite.
Bibliographie

[BC07] Bernard Bercu and Djalil Chafaï. Modélisation stochastique et simulation-Cours et applica-
tions. 2007.

[BGB20] Claire Boyer and Antoine Godichon-Baggioni. On the asymptotic rate of convergence
of stochastic newton algorithms and their weighted averaged versions. arXiv preprint
arXiv :2011.09706, 2020.

[BGBP19] Bernard Bercu, Antoine Godichon-Baggioni, and Bruno Portier. An efficient stochas-
tic newton algorithm for parameter estimation in logistic regressions. arXiv preprint
arXiv :1904.07908, 2019.

[BM13] Francis Bach and Eric Moulines. Non-strongly-convex smooth stochastic approxima-
tion with convergence rate O (1/n). In Advances in Neural Information Processing Systems,
pages 773–781, 2013.

[CGBP20] Peggy Cénac, Antoine Godichon-Baggioni, and Bruno Portier. An efficient averaged
stochastic gauss-newtwon algorithm for estimating parameters of non linear regres-
sions models. arXiv preprint arXiv :2006.12920, 2020.

[DST90] M Duflo, R Senoussi, and A Touati. Sur la loi des grands nombres pour les martingales
vectorielles et l’estimateur des moindres carrés d’un modèle de régression. In Annales
de l’IHP Probabilités et statistiques, volume 26, pages 549–566, 1990.

[Duf90] Marie Duflo. Méthodes récursives aléatoires. Masson, 1990.

[Duf97] Marie Duflo. Random iterative models, volume 34 of Applications of Mathematics (New
York). Springer-Verlag, Berlin, 1997. Translated from the 1990 French original by Ste-
phen S. Wilson and revised by the author.

[MP11] Abdelkader Mokkadem and Mariane Pelletier. A generalization of the averaging proce-
dure : The use of two-time-scale algorithms. SIAM Journal on Control and Optimization,
49(4) :1523–1543, 2011.

[Pel98] Mariane Pelletier. On the almost sure asymptotic behaviour of stochastic algorithms.
Stochastic processes and their applications, 78(2) :217–244, 1998.
88 BIBLIOGRAPHIE

[PJ92] Boris Polyak and Anatoli Juditsky. Acceleration of stochastic approximation. SIAM J.
Control and Optimization, 30 :838–855, 1992.

[RM51] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of
mathematical statistics, pages 400–407, 1951.

[Rup88] David Ruppert. Efficient estimations from a slowly convergent robbins-monro process.
Technical report, Cornell University Operations Research and Industrial Engineering,
1988.

[Wei37] Endre Weiszfeld. Sur le point pour lequel la somme des distances de n points donnés
est minimum. Tohoku Math. J, 43(355-386) :2, 1937.