La direction la plus lente impose le rythme

Ajustez une courbe quadratique à cent points par descente de gradient. Rien d’exotique : la matrice de plan a pour colonnes $1$, $t$ et $t^2$ pour $t$ régulièrement réparti sur $[0, 1]$, la perte est l’erreur quadratique, le pas est le meilleur pas constant pour ce problème, et l’exécution s’arrête quand la perte est à $10^{-6}$ près de son minimum, relativement à son point de départ.

Il faut 1742 pas.

Centrez et réduisez maintenant les deux colonnes non constantes. Mêmes données, même ajustement, même minimum. 147 pas.

Remplacez maintenant les trois colonnes par une base orthonormée du même sous-espace, qu’une factorisation QR produit en un appel. 1 pas.

Les trois aboutissent à la même réponse. Les sommes des carrés des résidus coïncident à dix décimales, à $0.1936196358$, et les valeurs ajustées à $1.8 \times 10^{-15}$ près, parce que les trois bases engendrent le même espace et que les moindres carrés se moquent de celle qu’on leur remet. L’optimiseur, lui, non.

A. D’où vient le rapport

Pour une perte quadratique de hessienne $H$, tout est fixé par deux valeurs propres : la plus grande, $L$, et la plus petite, $m$.

$L$ limite le pas. Prenez un pas plus grand que $2/L$ le long du vecteur propre le plus raide et l’itéré dépasse jusqu’à un point pire que son point de départ ; l’exécution diverge.

$m$ limite le progrès. Le long du vecteur propre le plus plat le gradient est petit, donc un pas de la taille autorisée vous déplace très peu.

Vous êtes contraint à un pas fixé par la direction la plus raide, puis vous devez traverser la plus plate avec. Avec le pas constant optimal $\alpha = 2 / (L + m)$, l’erreur est divisée par un facteur

$$\frac{\kappa - 1}{\kappa + 1}, \qquad \kappa = \frac{L}{m},$$

à chaque pas, de sorte que le nombre de pas pour une précision donnée est proportionnel à $\kappa$, le conditionnement. La profondeur du bol n’apparaît nulle part. Une perte peut être énorme et facile, ou minuscule et difficile.

Pour une vérification nette, prenez une quadratique en deux dimensions de valeurs propres 1 et 100. La formule prédit $\lceil \log 10^{-6} / \log(99/101) \rceil = 691$ pas pour diviser par $10^{-6}$ la distance à l’optimum. L’exécution en demande 691. (Comptez sur la perte et vous en obtenez la moitié, puisque la perte est le carré de la distance. Le taux décrit la distance.)

B. Les trois bases, mesurées

Le conditionnement des trois plans ci-dessus, et ce que chacun coûte :

La première ligne n’est pas un plan pathologique. C’est la façon évidente d’écrire un ajustement quadratique, sur un intervalle propre, sans valeur aberrante ni colinéarité digne de ce nom. Les colonnes $1$, $t$ et $t^2$ pointent simplement dans des directions voisines sur $[0,1]$ : toutes trois sont positives et croissantes sur l’essentiel de la plage, si bien que la hessienne est loin d’être un multiple de l’identité.

La dernière ligne est le cas limite à retenir. Quand $\kappa = 1$, le pas autorisé convient exactement à toutes les directions à la fois, et la descente de gradient avec $\alpha = 1/L$ atteint le minimum d’une quadratique en un seul pas. Toute l’itération de la première ligne, c’est l’optimiseur qui contourne un choix de coordonnées.

C. Ce que l’inertie achète, et ce qu’elle n’achète pas

L’inertie de type boule pesante ajoute la mise à jour précédente à la mise à jour courante. Sur une quadratique, réglée au mieux, son taux asymptotique est

$$\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1},$$

ce qui remplace $\kappa$ par $\sqrt{\kappa}$ dans le décompte des pas. Sur le problème à $\kappa = 100$ ci-dessus, cela prédit 69 pas contre 691 pour la descente de gradient, et une exécution en mesure 93 - plus lent que la borne asymptotique, parce que la borne décrit la queue plutôt que le régime transitoire, mais tout de même un facteur 7,43 sur le même problème avec la même règle d’arrêt.

La figure s’ouvre sur un conditionnement de 23,841. Portez-le à 100 : la descente de gradient simple demande 691 pas, comme ci-dessus, tandis que l’inertie en demande 90 depuis le point de départ de la figure contre 93 depuis celui utilisé ici ; le nombre de pas dépend du point de départ, les taux de convergence non.

La racine carrée est tout le bénéfice, et il vaut la peine d’être précis sur ce que cela signifie. L’inertie ne corrige pas le conditionnement ; elle fait passer le coût de $\kappa$ à $\sqrt{\kappa}$. Sur $\kappa = 10^4$, c’est la différence entre désespéré et lent, non entre lent et rapide. Elle introduit aussi un second hyperparamètre dont la valeur optimale dépend de $\kappa$, que vous ne connaissez pas.

La remise à l’échelle, quand elle est possible, est strictement meilleure : elle change $\kappa$ lui-même, coûte un passage sur les données et ne se règle pas.

D. Pourquoi cela se retrouve partout

Dès qu’on cherche le rapport plutôt que la profondeur, beaucoup de pratiques courantes cessent de ressembler à du folklore.

• Standardiser les entrées est un travail de conditionnement. Réécrire une variable des kilomètres vers les millimètres multiplie sa colonne par $10^6$ et son entrée dans $X^{\top}X$ par $10^{12}$, et ce facteur atterrit directement dans $\kappa$.
• Les méthodes adaptatives comme RMSProp et Adam entretiennent un pas par coordonnée, ce qui est un préconditionneur diagonal : une tentative d’égaliser les valeurs propres à bon marché, avec la seule information qu’une diagonale peut porter.
• Les couches de normalisation maintiennent les activations à une échelle comparable pendant l’entraînement, ce qui empêche la hessienne de dériver vers un mauvais rapport en cours de route.
• Les connexions résiduelles raccourcissent le chemin parcouru par un gradient, ce qui empêche l’étalement de la courbure de se composer avec la profondeur.

Aucune de ces techniques ne rend la perte plus petite. Toutes rendent la même perte moins chère à descendre, ce qui est autre chose et, au vu du tableau ci-dessus, souvent le facteur de loin le plus grand.