Gradient stochastique indolore : Interpolation, recherche linéaire et taux de convergence

Des travaux récents ont montré que la descente de gradient stochastique (SGD) atteint les taux de convergence rapides de la descente de gradient en lots complets pour des modèles sur-paramétrés satisfaisant certaines conditions d'interpolation. Cependant, la taille de pas utilisée dans ces travaux dépend de quantités inconnues et les performances pratiques de la SGD dépendent fortement du choix de cette taille de pas. Nous proposons d'utiliser des techniques de recherche linéaire pour définir automatiquement la taille du pas lors de la formation de modèles capables d'interpoler les données. Dans le cadre de l'interpolation, nous prouvons que la SGD avec une variante stochastique de la recherche linéaire classique d'Armijo atteint les taux de convergence déterministes pour les fonctions convexes et fortement convexes. Sous des hypothèses supplémentaires, nous montrons que la SGD avec la recherche linéaire d'Armijo atteint une convergence rapide pour les fonctions non convexes. De plus, nous montrons que l'extra-gradient stochastique avec une recherche linéaire de Lipschitz atteint une convergence linéaire pour une classe importante de fonctions non convexes et de problèmes de points selle satisfaisant l'interpolation. Pour améliorer les performances pratiques des méthodes proposées, nous donnons des heuristiques pour utiliser des pas plus grands et l'accélération. Nous comparons les algorithmes proposés à de nombreuses méthodes d'optimisation sur des tâches de classification standard utilisant à la fois des méthodes à noyau et des réseaux profonds. Les méthodes proposées offrent des performances compétitives pour tous les modèles et ensembles de données, tout en étant robustes aux choix précis des hyperparamètres. Pour la classification multi-classes utilisant des réseaux profonds, la SGD avec la recherche linéaire d'Armijo permet une convergence plus rapide et une meilleure généralisation.