Convergence of Stochastic Gradient Descent with Mini-Batching and Infinite Variance
This paper studies stochastic gradient descent (SGD) with mini-batching in the presence of heavy-tailed gradient noise with infinite variance, belonging to the domain of attraction of an α-stable law. We consider non-decreasing batch-size schedules and show that batching significantly improves convergence. In particular, we derive L^p moment bounds for the SGD error and prove that increasing batch sizes yield faster convergence rates and ensure convergence in probability even with a constant stepsize. Furthermore, we show that the properly normalized SGD iterates converge in distribution to the stationary law of an Ornstein–Uhlenbeck process driven by an α-stable Lévy process. For Polyak averaging, we obtain a stable limit theorem with a normalization that explicitly depends on the batch-size sequence.
Convergence de la descente de gradient stochastique avec mini-lots et variance infinie
Cet article étudie la descente de gradient stochastique (SGD) avec mini-lots en présence d’un bruit de gradient à queues lourdes de variance infinie, appartenant au domaine d’attraction d’une loi α-stable. Nous considérons des tailles de lots non décroissantes et montrons que le mini-batching améliore significativement la convergence. En particulier, nous établissons des bornes sur les moments L^p de l’erreur de l’algorithme SGD et prouvons que l’augmentation de la taille des lots conduit à des vitesses de convergence plus rapides et assure la convergence en probabilité même avec un pas d’apprentissage constant. De plus, nous montrons que les itérés de SGD correctement normalisés convergent en loi vers la distribution stationnaire d’un processus d’Ornstein–Uhlenbeck entraîné par un processus de Lévy α-stable. Enfin, pour la moyennisation de Polyak, nous obtenons un théorème limite stable avec une normalisation dépendant explicitement de la suite des tailles de lots.
Date and Time
-
Language of Oral Presentation
English
Language of Visual Aids
English