Rédige par ARSENE TAYO
1 Les méthodes Quasi-Newtoniennes
Les méthodes quasi-newtoniennes sont une classe de méthodes itératives utilisées pour ré-
soudre des problèmes d’optimisation sans contrainte, typiquement de la forme :
min f (x)
x∈Rn
où f : Rn → R est une fonction différentiable. Ces méthodes visent à approcher le minimum
local d’une fonction en utilisant une approximation de la matrice hessienne inverse, sans la calculer
explicitement, contrairement à la méthode de Newton classique.
Principe général
À chaque itération k, on effectue une mise à jour du vecteur xk selon :
xk+1 = xk + αk dk
où :
— dk = −Hk ∇f (xk ) est la direction de descente,
— Hk est une approximation de l’inverse de la hessienne ∇2 f (xk )
— αk est un pas (ou learning rate) déterminé par une stratégie de recherche linéaire(comme le
backtracking).
L’objectif est de mettre à jour Hk à chaque étape de manière efficace, sans calculer la vraie hessienne.
Idée fondamentale
La méthode repose sur la condition de secante qui provient du développement de Taylor du
gradient :
xk+1 − xk = Hk+1 (∇f (xk+1 ) − ∇f (xk ))
Soit sk = xk+1 − xk et yk = ∇f (xk+1 ) − ∇f (xk ), la condition devient :
sk = Hk+1 yk
Cette équation est utilisée pour mettre à jour Hk+1 , généralement en imposant que la mise à jour
soit symétrique et positive définie si possible.
1.1 Les algorithmes de BFGS ET DFP
NB Dans la pratique l’algorithme BFGS est plus utilisé.
Tp inf342 1 Info-L3
Rédige par ARSENE TAYO 1.2 L’algorithmes SR1
Algorithm 1 méthode DFP
Require: x0 point de départ, ϵ > 0 la tolérance, H0 l’approximation du hessien inverse
1: k ← 0 ;
2: while ∥∇fk ∥ > ϵ do
3: pk ← −Hk ∇fk ; \\ Calcul de la direction de descente
4: αk ← Backtracking(f, ∇fk , pk , xk )
5: xk+1 = xk + αk pk ;
6: sk ← xk+1 − xk ;
7: yk ← ∇fk+1 − ∇fk ;
1
8: ρk ← T ;
yk sk
Hk yk y T Hk sk sTk
9: Hk+1 ← Hk − T k + T ;
yk Hk yk y k sk
10: end while
Algorithm 2 méthode BFGS
Require: x0 point de départ, ϵ > 0 la tolérance, H0 l’approximation du hessien inverse
1: k ← 0 ;
2: while ∥∇fk ∥ > ϵ do
3: pk ← −Hk ∇fk ; \\ Calcul de la direction de descente
4: αk ← Backtracking(f, ∇fk , pk , xk )
5: xk+1 = xk + αk pk ;
6: sk ← xk+1 − xk ;
7: yk ← ∇fk+1 − ∇fk ;
1
8: ρk ← T ;
yk sk
9: Hk+1 ← (I − ρk sk ykT )Hk (I − ρk yk sTk ) + ρk sk sTk ;
10: end while
1.2 L’algorithmes SR1
Cette algorithme a la forme générale des algorithmes de région de confiance, et le sous-problème
d’optimisation de la ligne 3 est résolu par la méthode du point de Cauchy ou bien celle du dogleg.
Tp inf342 2 Info-L3
Rédige par ARSENE TAYO 1.3 LBFGS
Algorithm 3 méthode SR-1
Require: x0 point de départ, ϵ > 0 la tolérance, B0 l’approximation du hessien, ∆0 rayon de conver-
gence, ϵ > 0 tolerance, parametre η ∈ (0, 10−3 ) et r ∈ (0, 1) ;
1: k ← 0 ;
2: while ∥∇fk ∥ > ϵ do
3: \\ Calcul de sk en resolvant le sous-probleme
1
min ∇fkT s + sT Bk s tel que ∥s∥ ≤ ∆k ;
s 2
4: Calcul
yk = ∇f (xk + sk ) − ∇fk
ared = fk − f (xk + sk ) \ \ reduction actuel
1
pred = −(∇fkT sk + sTk Bk sk ) \ \reduction predite
2
5: if ared/pred>η then
6: xk+1 = sk + xk ;
7: else
8: xk+1 = xk ;
9: end if
10: if ared/pred>0.75 then
11: if ∥sk ∥ ≤ 0.8∆k then
12: ∆k+1 = ∆k ;
13: else
14: ∆k+1 = 2∆k ;
15: end if
16: else if 0.1 ≤ ared/pred ≤ 0.75 then
17: ∆k+1 = ∆k ;
18: else
19: ∆k+1 = ∆k ;
20: end if
21: if |sTk (yk − Bk sk )| ≥ r∥sk ∥∥yk − Bk sk ∥ then
(yk − Bk sk )(yk − Bk sk )T
22: Bk+1 = Bk +
(yk − Bk sk )T sk
23: else
24: Bk+1 ← Bk ;
25: end if
26: k ← k + 1;
27: end while
1.3 LBFGS
La méthode de quasi-Newton à mémoire limitée est utilisée pour résoudre de gros problèmes dont
les matrices hessiennes ne peuvent pas être calculées à un coût raisonnable ou ne sont pas éparses.
Ces méthodes conservent des approximations simples et compactes des matrices hessiennes : Au
Tp inf342 3 Info-L3
Rédige par ARSENE TAYO 1.3 LBFGS
lieu de stocker des approximations n × n entièrement denses, elles ne sauvegardent que quelques
vecteurs de longueur n qui représentent implicitement les approximations. Malgrés ses exigences
modestes en matière de stockage, elles permettent souvent d’obtenir un taux de convergence accep-
table (bien que linéaire). L’idée principale de cette méthode est d’utiliser les informations de courbure
provenant uniquement des itérations les plus récentes pour construire l’approximation du hessien.
Les informations de courbure des itérations antérieures, qui sont moins susceptibles d’être perti-
nentes pour le comportement réel de la hessienne à l’itération actuelle, sont rejetées dans l’intérêt
de l’économie d’espace de stockage. Des implémentations de schémas à mémoire limitée qui utilisent
une représentation compacte de l’information approximative du Hessien. Ces techniques peuvent
être appliquées non seulement à la L-BFGS mais aussi aux versions à mémoire limitée d’autres pro-
cédures de quasi-Newton telles que SR1.
Description Étant donné que l’approximation du hessien inverse Hk est généralement dense, le
coût de son stockage et de sa manipulation est prohibitif lorsque le nombre de variables est élevé.
Pour contourner ce problème, nous stockons une version modifiée de Hk de manière implicite, en
stockant un certain nombre (disons m) de paires de vecteurs {si , yi } utilisées dans les formules de la
methode de BFGS. Le produit Hk ∇fk peut être obtenu en effectuant une séquence de produits inté-
rieurs et de sommations vectorielles impliquant ∇fk et les paires {si , yi }. Après le calcul du nouvel
itéré, la paire de vecteurs la plus ancienne dans l’ensemble des paires {si , yi } est remplacée par la
nouvelle paire {sk , yk } obtenue à l’étape actuelle. De cette manière, l’ensemble des paires de vecteurs
comprend les informations de courbure des m itérations les plus récentes. L’expérience pratique a
montré que des valeurs modestes de m (entre 3 et 20, par e Une méthode efficace de choisir Hk0 est
Algorithm 4 SlopeCalculus
Require: ∇fk , les paires {si , yi }
1: q ← ∇fk ;
2: for i = k − 1 à k − m do
3: αi ← ρi sTi q ;
4: q ← q − αi y i
5: end for
6: r ← Hk0 q ;
7: for i = k − m à k − 1 do
8: β ← ρi yiT r ;
9: r ← r + si (αi − β);
10: end for
11: resultat Hk ∇fk = r.
sTk−1 yk−1
de choisir Hk0 = γk I ou γk = T
yk−1 yk−1
Tp inf342 4 Info-L3
Rédige par ARSENE TAYO 1.4 Stochastic Quasi-Newton(SQN)
Algorithm 5 L-BFGS
Require: Choisir un point de depart x0 , l’entier m > 0
1: k ← 0
2: choisir Hk0 ;
3: repeat
4: pk ← −SlopeCalculus(∇fk , {si , yi }) ;
5: Calcul xk+1 ← xk + αk pk ; où αk Satisfaisant aux conditions de Wolfs
6: if k > m then
7: Enlever la paire de vecteur {sk−m , yk−m } du stockage
8: end if
9: Calcul et sauvegarde de sk ← xk+1 − xk , yk = ∇fk+1 − ∇fk
10: k ←k+1
11: until convergence
1.4 Stochastic Quasi-Newton(SQN)
Considerons le probleme d’optimisation sans contrainte d’une fonction stochastique convexe
suivant :
min F (w) = E[f (w, ε)] (1)
w∈Rn
Ou ε désigne une variable aléatoire.
Nous supposerons que ε est une variable aléatoire constituée d’une paire entrée-sortie (x, z). Dans
le domaine du machine learning le vecteur x fait réference a l’entrée, et le vecteur z fait réference a
la sortie, nous pouvons f comme suit :
f (w, ε) = f (w, xi , zi ) = l(h(w, xi ), zi ) (2)
Ou l est considérée comme la fonction de perte a valeur R+ , et h est un modelé de prédiction para-
mètre w. ainsi notre fonction objective (1) est défini par la moyenne empirique :
N
1 X
F (w) = f (w, xi , zi ) (3)
N i=1
Dans les applications au machine learning avec de très grande quantité de données, il est commun
d’utiliser les mini-batch de taille b = |S| ≪ N d’instance d’entrée-sortie donnant l’estimation
suivante :
N
1X
∇F (w) =
b ∇f (w, xi , zi ) (4)
b i∈S
Le sous-espace S ⊂ {1, 2, . . . , N } est choisi de façon aléatoire, donc la mise a jour des itérations est
de la forme :
wk+1 = wk − αk Hk ∇F
b (wk ) (5)
Une approche efficace pour obtenir une approximation stable du hessien consiste a découpler le
calcul du gradient stochastique et de la courbure. Cela permet d’utiliser un échantillon différent
pour définir y et d’ajouter nouvelle estimation de la courbure a des intervalles réguliers plutôt qu’a
Tp inf342 5 Info-L3
Rédige par ARSENE TAYO 1.4 Stochastic Quasi-Newton(SQN)
chaque itération. Afin de souligner que les estimations de courbure soient mises a jour a des instants
différents de celui des gradients, nous utiliserons l’indice t pour dénoter le nombre de fois qu’un
nouvelle paire (s, y) est calcule, qui diffère de l’exposant k qui désigne le nombre de calcul de gradient
et de mises a jour de variables.
k
X
st = w̄t − w̄t−1 ou w̄t = wi (6)
i=k−L
Pour eviter les potentiels effets negatifs de la différentiation du gradient quand ∥st ∥ est petit, nous
choisissons de calculer yt via un produit Hessien vecteur
b 2 F (w̄t )st
yt = ∇ (7)
Soit SH ⊂ {1, . . . , N } un echantillon choisi aleatoirement et soit :
b 2 F (w) = 1
X
∇ ∇2 f (w, xi , zi ) ou bH = card(SH ) (8)
bH i∈S
H
Algorithm 6 Stochastic Quasi-Newton Method (SQN)
Require: Parametre initiale w1 , Entiers positifs M,L et suite de pas αk > 0
1: t=-1 ;
2: w̄t = 0 ;
3: for k = 1 . . . do
4: Choisir l’echantillon S ⊂ {1, 2, . . . , N } ;
5: Calcul du gradient stochastique ∇F b (wk ) defini par (4) ;
6: w̄t = w̄t + wk ;
7: if k ≤ 2L then
8: wk+1 = wk − αk ∇F b (wk )
9: else
10: wk+1 = wk − αk Ht ∇F b (wk )
b (wk ) est defini par l’algorithme mise a jour a deux phases vue dans la version LBFGS.
Ht ∇F
11: end if
12: if mod(k, L) = 0 then
13: t=t+1
14: w̄t = w̄t /L
15: if t > 0 then
16: Choisi un echantillon SH ⊂ {1, . . . , N } pour definir ∇b 2 F (w̄t ) par (8)
17: b 2 F (wt )(w̄t − w̄t−1 )
calcul st = w̄t − w̄t−1 , yt = ∇
18: end if
19: w̄t = 0
20: end if
21: end for
Tp inf342 6 Info-L3
Rédige par ARSENE TAYO RÉFÉRENCES
Références
[Byrd et al.( ? ? ? ?)Byrd, Hansen, Nocedal, and Singer] Byrd, R H, S L Hansen, Jorge Nocedal, Y Singer. ? ? ? ? A Stochastic Quasi-Newton Method for
Large-Scale Optimization .
[Nocedal and Wright(2006)] Nocedal, Jorge, Stephen J. Wright. 2006. Numerical optimization. 2nd ed. Springer series in operations research, Springer,
New York. OCLC : ocm68629100.
Tp inf342 7 Info-L3