Stochastic Algorithms in the Large
Résumé
In this talk, I will present a framework, inspired by random matrix theory, for analyzing the dynamics of stochastic optimization algorithms (e.g., stochastic gradient descent (SGD) and momentum (SGD + M)) when both the number of samples and dimensions are large. Using this new framework, we show that the dynamics of optimization algorithms on a least squares problem with random data become deterministic in the large sample and dimensional limit. In particular, the limiting dynamics for stochastic algorithms are governed by a Volterra equation. From this model, we identify a stability measurement, the implicit conditioning ratio (ICR), which regulates the ability of SGD+M to accelerate the algorithm. When the batch size exceeds this ICR, SGD+M converges linearly at a rate of
Biographie
Courtney Paquette est professeur adjointe à l’université McGill et détentrice d’une chaire en IA Canada. La recherche de Dr. Paquette est grossièrement centrée sur le devis et l’analyse d’algorithmes pour les problèmes d’optimisation à grande échelle, motivés par des applications en science des données. Courtney Paquette a obtenu un doctorat en mathématiques de l’Université de Washington en 2017, avant d’entreprendre un stage postdoctoral à l’Université Lehigh et l’Université de Waterloo, cette fois en qualité de chercheuse NSF. Elle a également occupé un poste de scientifique chez Google Research, Brain Montreal (2019-2020). Sa recherche est financée par le biais de sa chaire CIFAR, par le MILA, le CRSNG et le FRQNT.