Sharply predicting the behavior of complex iterative algorithms with random data, Ashwin Pananjady

Abstract: Iterative algorithms are the workhorses of modern signal processing and statistical learning, and are widely used to fit 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 these issues, we develop a principled framework that produces sharp, iterate-by-iterate characterizations of solution quality for complex iterative algorithms on several nonconvex model-fitting problems with random data. Such sharp predictions can provide precise separations between families of algorithms while also revealing nonstandard convergence phenomena. We will showcase the general framework on several canonical models in statistical machine learning.