Une méthode itérative d'optimisation qui met à jour les variables en se déplaçant dans la direction opposée au gradient d'une fonction objectif pour réduire sa valeur, en contrôlant typiquement la taille des pas (taux d'apprentissage).

Principe

L'idée organisatrice est que le gradient négatif est la direction de plus forte décroissance locale d'une fonction différentiable ; des déplacements successifs le long de −∇f réduisent la valeur de la fonction jusqu'à atteindre un point stationnaire sous des conditions appropriées.

Démonstration

Minimiser un quadratique convexe f(x)=1/2 x^T A x − b^T x avec A symétrique définie positive en itérant x_{k+1} = x_k − α ∇f(x_k) = x_k − α(Ax_k − b) ; avec α choisi dans (0,2/λ_max(A)) la méthode converge linéairement vers le minimiseur.

Mauvaise application

Utiliser une taille de pas fixe excessivement grande peut provoquer divergence ou oscillation ; appliquer la descente de gradient brute à des problèmes mal conditionnés entraîne une convergence très lente ; ignorer la nonconvexité peut piéger les itérés aux points selles ou minima locaux médiocres.

Conséquence

Appliquée avec une sélection de pas appropriée et une régularité du problème, la descente par gradient converge vers des points stationnaires et fournit un algorithme simple et extensible pour l'optimisation à grande échelle et l'apprentissage automatique.

Inversion

La notion opposée est l'ascension par gradient, qui suit le gradient pour augmenter l'objectif ; plus radicalement, des méthodes du second ordre ou quasi-Newton substituent à la direction de plus forte pente des directions informées par la courbure.

Limite

Exige la différentiabilité (ou des généralisations en sous-gradient) de l'objectif et des conditions de Lipschitz ou de convexité pour des garanties globales ; exclut les problèmes à variables discrètes sauf en relaxation.

Tension sémantique

Concurrence avec la descente par coordonnées, les méthodes stochastiques et les méthodes de Newton : la descente par gradient est simple et peu gourmande en mémoire mais peut être plus lente que les méthodes tenant compte de la courbure ou que des variantes stochastiques plus rapides dans les grands jeux de données.

Synthèse

La descente par gradient est l'algorithme prototype de premier ordre : calculer le gradient local, choisir une longueur de pas compatible avec stabilité et progrès, et itérer pour diminuer l'objectif, au prix d'une possible lenteur sur des paysages mal conditionnés ou non convexes.