Asymptotics for Sketching in Least Squares Regression

Abstract

We consider a least squares regression problem where the data has been generated from a linear model, and we are interested to learn the unknown regression parameters. We consider "sketch-and-solve" methods that randomly project the data first, and do regression after. Previous works have analyzed the statistical and computational performance of such methods. However, the existing analysis is not fine-grained enough to show the fundamental differences between various methods, such as the Subsampled Randomized Hadamard Transform (SRHT) and Gaussian projections. In this paper, we make progress on this problem, working in an asymptotic framework where the number of datapoints and dimension of features goes to infinity. We find the limits of the accuracy loss (for estimation and test error) incurred by popular sketching methods. We show separation between different methods, so that SRHT is better than Gaussian projections. Our theoretical results are verified on both real and synthetic data. The analysis of SRHT relies on novel methods from random matrix theory that may be of independent interest.

Cited by in corpus (12)

• Faster Least Squares Optimization
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Optimal Randomized First-Order Methods for Least-Squares Problems
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization
• Learning Augmentation Distributions using Transformed Risk Minimization
• Error Estimation for Sketched SVD via the Bootstrap
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
• Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality
• STORM: Foundations of End-to-End Empirical Risk Minimization on the Edge
• Effective and Sparse Count-Sketch via k-means clustering
• Random projection of Linear and Semidefinite problem with linear inequalities
• Precise expressions for random projections: Low-rank approximation and randomized Newton