Entrywise dynamics and universality of general first order methods

原文摘要

General first-order methods (GFOMs), including many variants of gradient descent and approximate message passing algorithms, constitute a broad class of iterative algorithms widely applied in modern statistical learning problems. Some GFOMs also serve as constructive proof devices, iteratively characterizing the empirical distributions of statistical estimators in the asymptotic regime of large system limits for any fixed number of iterations. This paper develops a nonasymptotic, entrywise characterization of the dynamics for a general class of GFOMs. Our characterizations capture the precise stochastic behavior of each coordinate of the GFOM iterates, and more importantly, hold universally across a broad class of heterogeneous random matrix models. As a corollary, we provide the first nonasymptotic description of the empirical distributions of the GFOM iterates beyond Gaussian ensembles. We demonstrate the utility of our general GFOM theory through two sets of applications. In the first application, we develop a new algorithmic approach to prove universality for general empirical risk minimizers. Specifically, we establish new entrywise universality for a broad class of regularized least squares estimators in the linear model, by controlling the entrywise error relative to a suitably constructed GFOM iterate. This algorithmic proof method also systematically improves averaged universality results for general regularized regression estimators in the linear model, and resolves the universality conjecture for (regularized) maximum likelihood estimators in the logistic regression model. In the second application, we obtain entrywise Gaussian approximations for a general class of gradient descent algorithms. Our approach provides nonasymptotic state evolution for the bias and variance of the algorithm along the iteration path, applicable even to nonconvex loss functions. The proof relies on a new recursive leave-k-out method that provides “almost” delocalization for the GFOM iterates, and their higher-order derivatives with respect to the underlying random matrix ensembles. Crucially, our method ensures the validity of entrywise universality for up to poly-logarithmic many iterations, which facilitates effective ℓ2/ℓ∞ control between certain GFOM iterates and statistical estimators in applications.

摘要来源：Crossref