The estimation error of general first order methods
  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.
