Title:

Stochastic Algorithms in the Large: Exact Dynamics, Average-case Analysis, and Stepsize Criticality

Abstract: 

In this talk, I will present a framework, inspired by random matrix theory, for analyzing the dynamics of stochastic algorithms (e.g., stochastic gradient descent (SGD) and momentum) when both the number of samples and dimensions are large. Using this new framework, we show that the dynamics of stochastic algorithms on a least squares problem with random data become deterministic in the large sample and dimensional limit. Furthermore, the limiting dynamics are governed by a Volterra integral equation. This model predicts that SGD undergoes a phase transition at an explicitly given critical stepsize that ultimately affects its convergence rate, which we also verify experimentally. Finally, when input data is isotropic, we provide explicit expressions for the dynamics and average-case convergence rates. These rates show significant improvement over the worst-case complexities.

Bio: 

Courtney Paquette is an assistant professor at McGill University and a CIFAR Canada AI chair. Paquette’s research broadly focuses on designing and analyzing algorithms for large-scale optimization problems, motivated by applications in data science. She received her PhD from the mathematics department at the University of Washington (2017), held postdoctoral positions at Lehigh University (2017-2018) and University of Waterloo (NSF postdoctoral fellowship, 2018-2019), and was a research scientist at Google Research, Brain Montreal (2019-2020).