AdaGrad

AdaGrad est un algorithme de gradient adaptatif qui ajuste le taux d'apprentissage par paramètre, en mettant à l'échelle les mises à jour de manière inversement proportionnelle à la racine carrée des gradients au carré accumulés, introduit par Duchi et al. en 2011.

AdaGrad (abréviation de Adaptive Gradient) est un algorithme d'optimisation utilisé en apprentissage automatique et en apprentissage profond qui adapte le taux d'apprentissage pour chaque paramètre individuellement. Contrairement à la descente de gradient stochastique standard, qui applique un taux d'apprentissage unique à tous les paramètres, AdaGrad ajuste la mise à jour de chaque paramètre en fonction des gradients quadratiques historiques de ce paramètre. Cette adaptation par paramètre permet à l'algorithme d'effectuer des mises à jour plus importantes pour les paramètres peu fréquents et des mises à jour plus petites pour les paramètres fréquents, ce qui est particulièrement utile dans les contextes de données éparses. AdaGrad a été introduit par John Duchi, Elad Hazan et Yoram Singer en 2011 et est devenu une méthode fondatrice dans le développement d'optimiseurs adaptatifs ultérieurs tels que RMSProp et Adam.

L'idée centrale d'AdaGrad est de maintenir une somme cumulée des carrés des gradients passés pour chaque paramètre. À chaque itération, le taux d'apprentissage d'un paramètre est divisé par la racine carrée de cette somme accumulée. Cela signifie que les paramètres avec de grands gradients historiques reçoivent des taux d'apprentissage effectifs plus petits, tandis que les paramètres avec des gradients petits ou peu fréquents reçoivent des taux d'apprentissage effectifs plus grands. L'accumulation des gradients quadratiques est monotone croissante, ce qui entraîne une décroissance du taux d'apprentissage effectif au fil du temps. Cette propriété peut être bénéfique pour la convergence dans les contextes convexes, mais peut aussi conduire à une décroissance trop agressive dans les problèmes non convexes, une limitation qui a motivé les algorithmes ultérieurs.

Background

L'optimisation en apprentissage automatique implique souvent la minimisation d'une fonction objectif qui est une somme de fonctions de perte par exemple. Pour un ensemble d'entraînement de n exemples, le risque empirique est donné par Q(w) = (1/n) Σ Q_i(w), où w est le vecteur de paramètres et Q_i est la perte pour le i-ème exemple. La descente de gradient standard calcule le gradient de la somme complète à chaque étape, ce qui peut être coûteux en calcul lorsque n est grand. La descente de gradient stochastique (SGD) approxime plutôt le gradient en utilisant un seul échantillon ou un mini-lot, réduisant le coût de calcul par itération mais introduisant du bruit. L'algorithme de Robbins-Monro des années 1950 a posé les bases de l'approximation stochastique, et SGD est devenu un pilier de l'apprentissage automatique en raison de son efficacité sur les grands ensembles de données.

Dans SGD, la règle de mise à jour est w := w - η ∇Q_i(w), où η est le taux d'apprentissage. Choisir un taux d'apprentissage fixe est souvent sous-optimal : un taux trop grand peut provoquer une divergence, tandis qu'un taux trop petit ralentit la convergence. Les méthodes adaptatives comme AdaGrad visent à résoudre ce problème en ajustant le taux d'apprentissage en fonction de la géométrie du paysage d'optimisation. La motivation d'AdaGrad est venue de l'observation que différents paramètres peuvent nécessiter des tailles de pas différentes, en particulier dans les problèmes avec des caractéristiques éparses où certains paramètres sont mis à jour rarement.

Algorithm

AdaGrad modifie la mise à jour de SGD en maintenant une matrice diagonale G_t, où chaque élément diagonal est la somme des carrés des gradients passés pour le paramètre correspondant. À l'étape temporelle t, la mise à jour pour le paramètre w_i est :

w_i := w_i - (η / sqrt(G_{t,ii} + ε)) ∇Q_i(w_i),

où ε est une petite constante (par exemple, 1e-8) pour éviter la division par zéro. Les gradients quadratiques accumulés G_{t,ii} = Σ_{τ=1}^{t} (∇Q_i(w_τ))^2. Cela peut être écrit sous forme vectorielle comme :

w := w - η * diag(G_t + εI)^{-1/2} ∇Q(w).

En pratique, l'algorithme est souvent appliqué à des mini-lots, où le gradient est calculé sur un sous-ensemble d'exemples d'entraînement. Le taux d'apprentissage par paramètre est donc η_t,i = η / sqrt(G_{t,ii} + ε). Parce que G_t croît au fil du temps, le taux d'apprentissage effectif diminue, garantissant que l'algorithme prend des pas plus petits à mesure qu'il progresse. Cela contraste avec SGD avec momentum, qui accumule les gradients pour accélérer dans des directions cohérentes.

Mathematical Properties

AdaGrad a été initialement analysé dans le contexte de l'optimisation convexe. Les auteurs ont montré que pour les fonctions convexes, AdaGrad atteint une borne de regret asymptotiquement optimale pour l'apprentissage en ligne. Spécifiquement, le regret, qui mesure la différence cumulative entre la perte de l'algorithme et le meilleur paramètre fixe rétrospectivement, croît comme O(√T) pour AdaGrad, correspondant à la borne inférieure pour l'optimisation convexe en ligne. C'est une amélioration par rapport à SGD standard avec un taux d'apprentissage fixe, qui peut nécessiter un réglage minutieux du calendrier du taux d'apprentissage.

L'idée clé est qu'AdaGrad s'adapte automatiquement à la géométrie de l'espace des caractéristiques. Dans les contextes épars, où de nombreuses caractéristiques sont nulles pour la plupart des exemples, les gradients accumulés pour ces caractéristiques restent petits, permettant des mises à jour plus importantes lorsqu'elles apparaissent. Cela rend AdaGrad particulièrement efficace pour le traitement du langage naturel et d'autres domaines avec des entrées éparses de haute dimension.

Cependant, l'accumulation des gradients quadratiques est monotone croissante, ce qui signifie que le taux d'apprentissage décroît vers zéro au fil du temps. Dans les problèmes non convexes, comme l'entraînement de réseaux neuronaux profonds, cela peut provoquer un arrêt prématuré de l'apprentissage. Cette limitation a conduit au développement de variantes comme RMSProp, qui utilise une moyenne mobile des gradients quadratiques au lieu d'une somme, et Adam, qui combine des taux d'apprentissage adaptatifs avec le momentum.

Applications

AdaGrad a été appliqué dans diverses tâches d'apprentissage automatique, en particulier celles impliquant des données éparses. En traitement du langage naturel, il a été utilisé pour entraîner des modèles sur des caractéristiques de sac de mots, où chaque document est représenté par un vecteur épars de comptes de mots. L'adaptation par paramètre permet aux mots rares de recevoir des mises à jour plus importantes, améliorant la capacité du modèle à apprendre à partir de caractéristiques peu fréquentes mais informatives.

Dans les systèmes de recommandation, AdaGrad a été utilisé pour optimiser les modèles de factorisation matricielle, où les plongements d'utilisateurs et d'articles sont mis à jour en fonction de données d'interaction éparses. La capacité de l'algorithme à gérer des fréquences variées de paires utilisateur-article le rend adapté à ces contextes. De plus, AdaGrad a été employé dans des scénarios d'apprentissage en ligne, où les données arrivent séquentiellement et le modèle doit s'adapter rapidement.

Bien qu'il soit supplanté par des optimiseurs plus avancés dans de nombreuses applications d'apprentissage profond, AdaGrad reste une référence pour la comparaison et est encore utilisé dans certains domaines où ses propriétés sont avantageuses. Son influence est évidente dans la conception des méthodes adaptatives ultérieures, qui s'appuient sur l'idée de taux d'apprentissage par paramètre.

Limitations and Extensions

La principale limitation d'AdaGrad est le taux d'apprentissage décroissant de manière monotone. En apprentissage profond, où le paysage de perte est non convexe, cela peut conduire à une convergence lente ou à rester bloqué dans de mauvais minima locaux. Pour résoudre ce problème, les chercheurs ont proposé plusieurs extensions :

RMSProp : Introduit par Geoffrey Hinton dans ses notes de cours, RMSProp utilise une moyenne à décroissance exponentielle des gradients quadratiques, permettant au taux d'apprentissage de s'adapter plus flexiblement.
Adam : Proposé par Diederik Kingma et Jimmy Ba en 2014, Adam combine la moyenne mobile de RMSProp avec le momentum, fournissant à la fois des taux d'apprentissage adaptatifs et du momentum.
AdaDelta : Développé par Matthew Zeiler, AdaDelta élimine le besoin d'un hyperparamètre de taux d'apprentissage en utilisant une fenêtre de gradients passés.

Ces algorithmes sont devenus les choix par défaut pour l'entraînement des réseaux neuronaux profonds, mais ils trouvent tous leurs racines dans le concept de gradient adaptatif introduit par AdaGrad.

Impact and Legacy

AdaGrad a eu un impact durable sur le domaine de l'optimisation en apprentissage automatique. Il a été l'un des premiers algorithmes largement adoptés à utiliser des taux d'apprentissage par paramètre, ouvrant la voie à une famille d'optimiseurs adaptatifs. Ses garanties théoriques dans les contextes convexes ont fourni une base solide pour comprendre les méthodes adaptatives. L'algorithme est souvent cité dans les manuels et les articles de recherche comme un développement clé dans l'histoire de l'optimisation.

En pratique, AdaGrad est moins couramment utilisé aujourd'hui pour l'entraînement de modèles d'apprentissage profond à grande échelle, car Adam et ses variantes tendent à mieux performer. Cependant, il reste un outil utile pour des problèmes spécifiques, comme ceux avec des caractéristiques éparses, et il est encore enseigné dans les cours d'apprentissage automatique comme une étape conceptuelle importante.