Statistically Optimal First Order Algorithms: A Proof via Orthogonalization

Understand

We consider a class of statistical estimation problems in which we are given a random data matrix ${\boldsymbol X}\in {\mathbb R}^{n\times d}$ (and possibly some labels ${\boldsymbol y}\in{\mathbb R}^n$) and would like to estimate a coefficient vector ${\boldsymbol \theta}\in{\mathbb R}^d$ (or possibly a constant number of such vectors).

• Special cases include low-rank matrix estimation and regularized estimation in generalized linear models (e.g., sparse regression).
• First order methods proceed by iteratively multiplying current estimates by ${\boldsymbol X}$ or its transpose.
• Examples include gradient descent or its accelerated variants.