The estimation error of general first order methods
This work addresses the gap between optimization and statistical optimality for large-scale models, providing foundational insights for researchers in machine learning and statistics, though it is incremental in extending existing theory to broader algorithm classes.
The paper tackles the fundamental limits of first-order methods for high-dimensional parameter estimation, deriving optimal lower bounds on estimation error in high-dimensional asymptotics for problems like sparse phase retrieval and sparse PCA, with algorithms matching these bounds up to negligible terms.
Modern large-scale statistical models require to estimate thousands to millions of parameters. This is often accomplished by iterative algorithms such as gradient descent, projected gradient descent or their accelerated versions. What are the fundamental limits to these approaches? This question is well understood from an optimization viewpoint when the underlying objective is convex. Work in this area characterizes the gap to global optimality as a function of the number of iterations. However, these results have only indirect implications in terms of the gap to statistical optimality. Here we consider two families of high-dimensional estimation problems: high-dimensional regression and low-rank matrix estimation, and introduce a class of `general first order methods' that aim at efficiently estimating the underlying parameters. This class of algorithms is broad enough to include classical first order optimization (for convex and non-convex objectives), but also other types of algorithms. Under a random design assumption, we derive lower bounds on the estimation error that hold in the high-dimensional asymptotics in which both the number of observations and the number of parameters diverge. These lower bounds are optimal in the sense that there exist algorithms whose estimation error matches the lower bounds up to asymptotically negligible terms. We illustrate our general results through applications to sparse phase retrieval and sparse principal component analysis.