La descente de gradient

Descendre la pente

La descente de gradient répète un seul mouvement : avancer contre le gradient, $\mathbf w_{k+1}=\mathbf w_k-\eta\,\nabla f(\mathbf w_k)$ . Le nombre $\eta>0$ est le pas, souvent appelé taux d'apprentissage. Un petit $\eta$ est sûr mais lent. Un grand $\eta$ dépasse le fond de la vallée et les itérés peuvent s'éloigner à chaque fois.

f(w)=\tfrac12 a\,w^{2}\ \Rightarrow\ w_{k+1}=(1-\eta a)\,w_k,\qquad |1-\eta a|<1\iff 0<\eta<\frac{2}{a}

(1)

Sur la cuvette la plus simple, la mise à jour multiplie $w$ par $1-\eta a$ à chaque fois ; les itérés tendent vers zéro exactement quand $|1-\eta a|<1$ , c'est-à-dire $\eta<2/a$ . Le choix $\eta=1/a$ atteint le minimum en un pas, et tout $\eta$ entre $1/a$ et $2/a$ converge encore mais change de signe en chemin. Au-delà de $2/a$ le facteur dépasse un en valeur absolue et les itérés explosent.

Trois pas sur f = 3x²Ici

f'(x)=6x

, donc

a=6

. Partons de

x_0=4

avec

\eta=0.1

: le facteur vaut

1-0.6=0.4

, d'où

x_1=1.6

x_2=0.64

x_3=0.256

. La limite de stabilité est

2/6=0.333

. Avec

\eta=0.5

le facteur vaut

1-3=-2

: les itérés valent

4,-4,8,\dots

et doublent de taille à chaque pas.

En plusieurs variables la courbure change selon la direction. La plus grande valeur propre $L$ de la hessienne limite le pas utilisable ( $\eta<2/L$ ) et la plus petite $\mu$ fixe la lenteur avec laquelle on traverse la direction la plus plate. Leur rapport $\kappa=L/\mu$ est le conditionnement. Avec le meilleur pas fixe $\eta=2/(L+\mu)$ l'erreur est multipliée par environ $(\kappa-1)/(\kappa+1)$ à chaque pas ; un grand $\kappa$ donne donc un facteur proche de un et un lent zigzag dans une longue vallée étroite. Pour la matrice de covariance de douze grandes actions américaines depuis 2010, $\kappa$ vaut environ $33$ : le facteur est $0.941$ et réduire l'erreur 100 fois demande environ 76 pas.

\eta^{*}=\frac{2}{L+\mu},\qquad \lVert\mathbf w_k-\mathbf w^{*}\rVert\ \lesssim\ \Big(\frac{\kappa-1}{\kappa+1}\Big)^{k}\lVert\mathbf w_0-\mathbf w^{*}\rVert,\qquad \kappa=\frac{L}{\mu}

(2)

Pas sûr : $\eta<2/L$ , où $L$ est la plus grande valeur propre de la hessienne ; sinon les itérés divergent.
Vitesse : fixée par le conditionnement $\kappa=L/\mu$ ; plus il est grand, plus la descente est lente.
Arrêt : arrêter quand $\lVert\nabla f\rVert$ passe sous une tolérance, avec un plafond d'itérations.

Mettez les variables à l'échelleUn grand conditionnement vient souvent de variables d'échelles très différentes, par exemple un poids entre 0 et 1 à côté d'une volatilité en points de base. Remettre chaque variable à une taille voisine réduit

\kappa

et peut transformer des milliers d'itérations en quelques dizaines. Le préconditionnement est la forme générale de la même idée.

Lab : ce qui est noté

Le premier pas15 pts
Le deuxième pas10 pts
Le plus grand pas stable15 pts
Un pas trop grand15 pts
Un conditionnement15 pts
Le meilleur facteur de contraction15 pts
Pourquoi le mauvais conditionnement est lent15 pts

Descendre la pente

f(w)=\tfrac12 a\,w^{2}\ \Rightarrow\ w_{k+1}=(1-\eta a)\,w_k,\qquad |1-\eta a|<1\iff 0<\eta<\frac{2}{a}

(1)

Trois pas sur f = 3x²Ici

f'(x)=6x

, donc

a=6

. Partons de

x_0=4

avec

\eta=0.1

: le facteur vaut

1-0.6=0.4

, d'où

x_1=1.6

x_2=0.64

x_3=0.256

. La limite de stabilité est

2/6=0.333

. Avec

\eta=0.5

le facteur vaut

1-3=-2

: les itérés valent

4,-4,8,\dots

et doublent de taille à chaque pas.

\eta^{*}=\frac{2}{L+\mu},\qquad \lVert\mathbf w_k-\mathbf w^{*}\rVert\ \lesssim\ \Big(\frac{\kappa-1}{\kappa+1}\Big)^{k}\lVert\mathbf w_0-\mathbf w^{*}\rVert,\qquad \kappa=\frac{L}{\mu}

(2)

Pas sûr : $\eta<2/L$ , où $L$ est la plus grande valeur propre de la hessienne ; sinon les itérés divergent.
Vitesse : fixée par le conditionnement $\kappa=L/\mu$ ; plus il est grand, plus la descente est lente.
Arrêt : arrêter quand $\lVert\nabla f\rVert$ passe sous une tolérance, avec un plafond d'itérations.

\kappa

et peut transformer des milliers d'itérations en quelques dizaines. Le préconditionnement est la forme générale de la même idée.

Lab : ce qui est noté

Le premier pas15 pts
Le deuxième pas10 pts
Le plus grand pas stable15 pts
Un pas trop grand15 pts
Un conditionnement15 pts
Le meilleur facteur de contraction15 pts
Pourquoi le mauvais conditionnement est lent15 pts

Descendre la pente

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.

La descente de gradient

Descendre la pente

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.