gradient descent algorithm

Imaginez un paysage dont l’altitude représente la valeur d’une fonction. Depuis un point donné, le gradient indique la pente qui monte le plus vite. Pour descendre, on part donc dans le sens opposé, puis on recommence depuis la nouvelle position.

La longueur de chaque déplacement, appelée pas, est décisive : trop grande, elle peut faire dépasser la vallée ; trop petite, elle ralentit la progression. L’algorithme s’arrête lorsque la pente devient assez faible selon la tolérance choisie.

Un algorithme du gradient minimise une fonction réelle différentiable par approximations successives. La fonction, notée $ff$, est définie sur ℝⁿ ou, plus généralement, sur un espace hilbertien. Lorsqu’elle est différentiable au sens de Fréchet, sa différentielle au point courant est une forme linéaire continue. Dans un espace hilbertien, le gradient est l’unique vecteur qui la représente par le produit scalaire, conformément au théorème de Riesz ; dans ℝⁿ muni de sa structure euclidienne, ses coordonnées sont les dérivées partielles. Il indique la direction de croissance la plus rapide, et son opposé fournit donc une direction de descente lorsqu’il n’est pas nul.

À partir d’un point initial x₀, l’algorithme construit des estimés x₁, x₂, etc. À l’itération d’indice k, il choisit un nombre positif α_k, appelé pas, puis effectue la mise à jour suivante : $x_{k+1}=x_k-{\alpha }_k\mathrm{\nabla }f(x_k)x\_\{k+1\}=x\_k-\backslash alpha\_k\backslash nabla\; f(x\_k)$. Une recherche linéaire peut choisir ce pas en examinant la fonction le long de la direction de descente.

Pour une tolérance ε positive ou nulle, le test d’arrêt compare la norme du gradient à ε. Un gradient faible indique un point presque stationnaire, mais ne suffit pas à garantir qu’il s’agit d’un minimum global.

Soit une fonction différentiable f, un point initial x₀ et une tolérance ε > 0. À l’itération k, on calcule le gradient au point x_k. Si sa norme est strictement inférieure à ε, on s’arrête. Sinon, on choisit par recherche linéaire un pas α_k > 0 dans la direction opposée au gradient, puis on pose : $x_{k+1}=x_k-{\alpha }_k\mathrm{\nabla }f(x_k)x\_\{k+1\}=x\_k-\backslash alpha\_k\backslash nabla\; f(x\_k)$. Les mêmes opérations sont répétées au nouveau point.

La fonction à minimiser doit être réelle et différentiable sur le domaine parcouru, afin que son gradient existe aux points examinés. Il faut aussi fixer un point initial, une tolérance et une règle donnant un pas strictement positif. La recherche linéaire doit retenir un déplacement qui fait effectivement progresser la minimisation.

Si la fonction présente un angle, comme la valeur absolue en zéro, le gradient ordinaire n’y existe pas et la procédure se bloque sous cette forme. Une méthode fondée sur un sous-gradient peut alors être envisagée. Si le domaine impose des contraintes, la mise à jour peut aussi sortir de la zone admissible ; une méthode adaptée aux contraintes est nécessaire.

On minimise la fonction $f(x)=(x-3{)}^{2}f(x)=(x-3)^2$. Le point initial vaut x₀ = 0, le pas constant vaut 0,25 et la tolérance vaut ε = 1. La dérivée, qui joue ici le rôle du gradient, est $f^{\mathrm{\prime }}(x)=2(x-3)f\text{'}(x)=2(x-3)$.

1. Au point x₀ = 0, le gradient vaut −6. Sa norme vaut 6, donc l’algorithme continue et donne x₁ = 0 − 0,25 × (−6) = 1,5.

2. Au point x₁ = 1,5, le gradient vaut −3. On obtient x₂ = 1,5 − 0,25 × (−3) = 2,25.

3. Au point x₂ = 2,25, le gradient vaut −1,5. On obtient x₃ = 2,25 − 0,25 × (−1,5) = 2,625.

4. Au point x₃ = 2,625, la norme du gradient vaut 0,75. Comme 0,75 < 1, le test impose l’arrêt avant une nouvelle mise à jour.

Le résultat renvoyé est donc x₃ = 2,625. Le minimum exact de cette fonction est atteint en x = 3 : l’écart vaut 3 − 2,625 = 0,375, ce qui confirme que le point obtenu est proche du fond sans lui être égal.

Pour ajuster les paramètres d’un modèle, on définit une fonction qui mesure son erreur. Le gradient indique comment modifier simultanément les paramètres afin de réduire cette erreur. Lorsque le calcul du gradient complet devient trop coûteux sur beaucoup de données, une variante utilisant seulement une partie des observations peut être préférée.

Dans un problème numérique de réglage, on surveille la valeur de la fonction et la norme du gradient à chaque itération. Si la valeur oscille ou augmente, le pas est probablement trop grand ; une recherche linéaire est alors préférable à un pas fixe mal calibré.

Si les variables doivent respecter des bornes ou des égalités, une descente sans correction peut produire un point interdit. On choisit alors une méthode projetée ou une autre procédure d’optimisation sous contraintes.

Gradient et algorithme du gradient. Le gradient est un vecteur calculé en un point ; l’algorithme est la procédure qui utilise ce vecteur à plusieurs reprises. Pour $f(x)=(x-3{)}^{2}f(x)=(x-3)^2$, −6 est le gradient en 0, tandis que la suite 0, 1,5, 2,25, 2,625 provient de l’algorithme.

Descente de gradient et gradient conjugué. La première avance dans l’opposé du gradient courant. Le second construit des directions conjuguées pour certains problèmes, notamment quadratiques. Une direction qui combine l’information des étapes précédentes signale que l’on n’applique pas la descente de gradient élémentaire décrite ici.

Gradient nul. Le test peut arrêter l’algorithme sur un maximum ou un point selle, et pas seulement sur un minimum. Le symptôme est une norme nulle sans comportement minimal dans les directions voisines ; il faut examiner la fonction autour du point ou utiliser des informations de courbure.

Pas mal choisi. Dans l’exemple, un pas de 0,25 rapproche les estimés de 3. Avec un pas constant égal à 1, la même mise à jour alterne exactement entre 0 et 6 : la fonction reste à la valeur 9. Il faut réduire le pas ou employer une recherche linéaire.

Minimum local. Pour une fonction possédant plusieurs vallées, deux points initiaux peuvent mener à deux points stationnaires différents. Une petite norme du gradient ne prouve donc pas que la meilleure valeur sur tout le domaine a été trouvée ; plusieurs initialisations ou une méthode globale peuvent être nécessaires.

Tolérance nulle. Avec ε = 0 et le test strict donné, une norme est toujours supérieure ou égale à zéro : même un gradient nul ne satisfait jamais la condition d’arrêt. Il faut adopter une tolérance positive ou prévoir explicitement l’arrêt lorsque le gradient est nul.

Le Sous-gradient prolonge l’idée de direction exploitable lorsque la fonction convexe n’est pas différentiable en certains points.

L’étude de la convergence conduit ensuite à relier la régularité de la fonction, le choix des pas et la vitesse à laquelle les estimés se rapprochent d’un minimum.