Asymptotics for Sketching in Least Squares Regression
This work provides a fine-grained asymptotic analysis for sketching methods in regression, which is incremental but clarifies performance gaps for practitioners in machine learning and statistics.
The paper tackles the problem of understanding the fundamental differences between sketching methods like Subsampled Randomized Hadamard Transform (SRHT) and Gaussian projections in least squares regression, showing that SRHT outperforms Gaussian projections in terms of accuracy loss for estimation and test error, with theoretical results verified on real and synthetic data.
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.