The estimation error of general first order methods

Abstract

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.

49 pages

References in corpus (9)

• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Generalized power method for sparse principal component analysis
• Sparse principal component analysis and iterative thresholding
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Optimal detection of sparse principal components in high dimension
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• A generalization of the Lindeberg principle
• Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

Cited by in corpus (5)

• Disordered Systems Insights on Computational Hardness
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Learning curves for the multi-class teacher-student perceptron
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery