Ashwin Pananjady (Georgia Tech)
Sharply predicting the behavior of iterative algorithms in random nonconvex optimization problems
Iterative algorithms are the workhorses of modern statistical learning, and are widely used to fit large-scale, complex models to random data. While the choice of an algorithm and its hyperparameters determines both the speed and fidelity of the learning pipeline, it is common for this choice to be made heuristically, either by expensive trial-and-error or by comparing upper bounds on convergence rates of various candidate algorithms. Motivated by this, we develop a principled framework that produces sharp, iterate-by-iterate characterizations of solution quality for a wide variety of algorithms on several nonconvex model-fitting problems with random data. I will present the general framework and then some concrete consequences, showcasing how sharp predictions can provide precise separations between families of algorithms while also revealing some nonstandard convergence phenomena. The talk will be based on joint work with Kabir Chandrasekher, Mengqi Lou, and Christos Thrampoulidis.