Les méthodes de gradient adaptatif convergent plus rapidement avec une surparamétrisation (et vous pouvez faire une recherche linéaire)

Résumé

Les méthodes de gradient adaptatif sont généralement utilisées pour former des modèles sur-paramétrés capables de s'adapter exactement aux données ; nous étudions donc leur convergence dans ce cadre d'interpolation. Sous une hypothèse d'interpolation, nous prouvons que AMSGrad avec une taille de pas et un momentum constants peut converger vers le minimiseur à la vitesse O(1/T) pour des fonctions lisses et convexes. De plus, dans ce contexte, nous montrons que AdaGrad peut atteindre un regret O(1) dans le cadre de l'optimisation convexe en ligne. Lorsque l'interpolation n'est qu'approximativement satisfaite, nous montrons que AMSGrad à pas constant converge vers un voisinage de la solution. D'autre part, nous prouvons qu'AdaGrad est robuste à la violation de l'interpolation et converge vers le minimiseur à la vitesse optimale. Cependant, nous démontrons que même pour des problèmes simples et convexes satisfaisant l'interpolation, la performance empirique de ces méthodes dépend fortement de la taille du pas et nécessite un réglage. Nous atténuons ce problème en utilisant la recherche linéaire stochastique (SLS) et les pas de Polyak (SPS) pour aider ces méthodes à s'adapter à la régularité locale de la fonction. En utilisant ces techniques, nous prouvons que AdaGrad et AMSGrad ne nécessitent pas la connaissance de constantes dépendantes du problème et conservent les garanties de convergence de leurs homologues à pas constant. Nous montrons expérimentalement que ces techniques permettent d'améliorer les performances de convergence et de généralisation pour différentes tâches, de la classification binaire avec des mappages de noyaux à la classification avec des réseaux neuronaux profonds.