Descente de gradient : intuition, choix du pas et cas concrets en R

Imaginez que vous êtes perdu au milieu d'une chaîne de montagnes, les yeux bandés, et que votre seul objectif est d'atteindre la vallée la plus basse. Votre instinct vous dirait de tâter le sol, de sentir la pente, et de faire un pas dans la direction où la descente est la plus raide.

C'est le principe de la descente de gradient, l'algorithme d'optimisation au cœur de l'apprentissage automatique. L'image a pourtant une limite importante : elle dit dans quelle direction marcher, pas quelle longueur donner au pas. Or c'est ce choix qui décide si l'on arrive en bas en quelques pas, en quelques milliers, ou jamais.

Le problème : un seul pas pour toutes les directions

Tout l'article suit le même exemple, une vallée allongée :

Le minimum est en $(0,0)$, mais la pente est sept fois plus forte selon $y$ que selon $x$. Avec un pas fixe $\alpha =0,1$, chaque itération multiplie $y$ par $1-7\alpha =0,3$ et $x$ seulement par $1-\alpha =0,9$ :

Pas fixe de 0,1 depuis (5, 5) : y s'effondre, x rampeFigure de l'auteur

En trois pas, on passe de $(5;5)$ à $(3,65;0,14)$ : la direction raide est réglée, l'autre avance de 10 % par pas. Augmenter le pas pour aller plus vite selon $x$ ne marche pas : au-delà de $\alpha =2/7\approx 0,29$, le facteur $|1-7\alpha |$ dépasse 1 et $y$ diverge. Le bon pas dépend de l'endroit où l'on se trouve, d'où l'idée de le recalculer à chaque itération.

Trois façons de choisir le pas

Pas exact pour une fonction quadratique

Notons $\phi (\alpha )=f(\mathbf{x}-\alpha \mathbf{g})$ la valeur de f après un pas de longueur $\alpha$. Pour une quadratique $f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^{\top }A\mathbf{x}$, $\phi$ est une parabole en $\alpha$, et son minimum se calcule directement :

Ici $A=\mathrm{diag}(1,7)$ et $\mathbf{g}=(x,7y)$, donc :

f          <- function(x, y) x^2/2 + 7*y^2/2
grad_f     <- function(x, y) c(x, 7*y)
step_exact <- function(x, y) (x^2 + 49*y^2) / (x^2 + 343*y^2)
 
gd_exact <- function(x0, y0, iters = 200, tol = 1e-10) {
  x <- x0; y <- y0
  for (i in 1:iters) {
    g <- grad_f(x, y)
    if (sqrt(sum(g^2)) < tol) break   # gradient nul : minimum atteint
    a <- step_exact(x, y)
    x <- x - a*g[1]; y <- y - a*g[2]
  }
  c(x = x, y = y)
}

Depuis $(5,5)$, 23 itérations suffisent pour ramener la norme du gradient sous $10^{-10}$. La méthode est idéale quand elle s'applique, mais elle suppose de connaître $A$ : pour une fonction quelconque, il n'existe pas de formule.

Les conditions d'Armijo et de Wolfe

Sans formule, on cherche un pas acceptable plutôt qu'optimal. Deux conditions suffisent : si f est bornée inférieurement et que son gradient est lipschitzien, tout pas qui les vérifie fait tendre le gradient vers zéro (Nocedal et Wright, chapitre 3, théorème de Zoutendijk) :

1. Condition d'Armijo (décroissance suffisante)

   Le pas doit faire baisser f d'au moins une fraction de ce que promet la pente de départ. Elle refuse les pas trop longs, ceux qui franchissent le fond de la vallée et remontent de l'autre côté :

   $$f(\mathbf{x}-\alpha \mathbf{g})\le f(\mathbf{x})-c_1\alpha \Vert \mathbf{g}{\Vert }^2$$

2. Condition de courbure (Wolfe)

   Armijo seul accepte des pas minuscules : ils font toujours baisser f un peu. La condition de courbure les refuse en exigeant qu'après le pas, la descente soit devenue nettement moins raide :

   $$\nabla f(\mathbf{x}-\alpha \mathbf{g}{)}^{\top }\mathbf{g}\le c_2\Vert \mathbf{g}{\Vert }^2,0<c_1<c_2<1$$

   Si le pas est trop court, le gradient n'a presque pas changé : le produit reste proche de $\Vert \mathbf{g}{\Vert }^2$, la condition échoue, et il faut allonger le pas.

Pas acceptés par Armijo et Wolfe depuis (5, 5)

Sur notre exemple, avec $c_1=10^{-4}$ et $c_2=0,9$, les pas acceptés vont d'environ 0,015 à 0,29. Le pas exact (0,145) en fait partie, mais n'importe quel pas de la bande garantit un progrès suffisant. Ces deux valeurs sont celles que recommandent Nocedal et Wright pour les méthodes de type Newton.

Trouver un pas acceptable par dichotomie

Les deux conditions encadrent le bon pas : si Armijo échoue, le pas est trop long ; si la courbure échoue, il est trop court. On part d'un intervalle $[0,{\alpha }_{\max }]$ et on le coupe en deux jusqu'à tomber dans la bande :

line_search_bisection <- function(x, y, g, c1 = 1e-4, c2 = 0.9, a_max = 1, max_iter = 50) {
  gg <- sum(g^2)
  armijo_ok   <- function(a) f(x - a*g[1], y - a*g[2]) <= f(x, y) - c1*a*gg
  courbure_ok <- function(a) sum(grad_f(x - a*g[1], y - a*g[2]) * g) <= c2*gg
  lo <- 0; hi <- a_max; a <- (lo + hi)/2
  for (j in 1:max_iter) {
    if (!armijo_ok(a)) hi <- a          # trop long : on garde la moitié gauche
    else if (!courbure_ok(a)) lo <- a   # trop court : on garde la moitié droite
    else break                          # les deux conditions sont vérifiées
    a <- (lo + hi)/2
  }
  a
}
 
gd_wolfe <- function(x0, y0, iters = 200, tol = 1e-10) {
  x <- x0; y <- y0
  for (i in 1:iters) {
    g <- grad_f(x, y)
    if (sqrt(sum(g^2)) < tol) break
    a <- line_search_bisection(x, y, g)
    x <- x - a*g[1]; y <- y - a*g[2]
  }
  c(x = x, y = y)
}

Depuis $(5,5)$, gd_wolfe converge vers $(0,0)$ en 93 itérations, et chaque recherche trouve un pas valide. C'est plus lent que le pas exact (23 itérations), c'est le prix de la généralité : cette version ne suppose rien sur la forme de f, seulement qu'on sait calculer f et son gradient.

Un deuxième cas : backtracking d'Armijo seul

La version la plus courante en pratique est encore plus simple : on part de $\alpha =1$ et on divise par deux tant qu'Armijo n'est pas satisfait. Sur la quadratique bien conditionnée $f(x,y)=x^2+y^2+xy-x-2y$, dont le minimum est en $(0,1)$, cela suffit :

f_q    <- function(x, y) x^2 + y^2 + x*y - x - 2*y
grad_q <- function(x, y) c(2*x + y - 1, 2*y + x - 2)
 
pas_armijo <- function(x, y, c1 = 1e-4, shrink = 0.5) {
  g <- grad_q(x, y); a <- 1
  while (f_q(x - a*g[1], y - a*g[2]) > f_q(x, y) - c1*a*sum(g^2)) a <- a*shrink
  c(x - a*g[1], y - a*g[2])
}

Backtracking d'Armijo depuis (−5, 5)Figure de l'auteur

Le premier pas complet ($\alpha =1$) est accepté et mène directement en $(1,2)$ ; les suivants oscillent autour du minimum en se resserrant. Quand la fonction est bien conditionnée, rien de plus n'est nécessaire.

Ce qu'il faut surveiller

Les codes de cet article ont été vérifiés numériquement (itérations, point d'arrivée, pas acceptés) par une transcription ligne à ligne ; les deux figures de trajectoire proviennent de la version originale de l'article.

Références

1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2e éd.), chapitre 3 : Line Search Methods. Springer.
2. Conditions de Wolfe, Wikipédia (en anglais) : énoncé, variante forte et valeurs usuelles de c₁ et c₂.