Abstract:
|
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 task to be executed heuristically, either by expensive trial-and-error or by comparing rough convergence bounds. Motivated by this, we develop a principled framework that produces sharp, iterate-by-iterate characterizations of solution quality for algorithms run with sample-splitting on a wide range of model-fitting problems. In particular, provided the data is normally distributed and each iteration can be written as the solution to a convex optimization problem satisfying some natural conditions, we leverage Gaussian comparison theorems to derive a deterministic, low-dimensional sequence that accurately captures both the convergence rate of the algorithm and the eventual error floor in the finite-sample regime. We illustrate consequences for multiple families of randomly initialized iterative algorithms run on canonical statistical models. Joint work with K. Chandrasekher and C. Thrampoulidis.
|