Compressed and Penalized Linear Regression

Modern applications require methods that are computationally feasible on large datasets while retaining good statistical properties. Recent work has focused on developing fast and randomized approximations for solving least squares problems when the data are too large to fit into memory easily or when computations are at a premium. Many of these techniques rely on data-driven subsampling or random compression. In this article, we provide new approximate algorithms for solving penalized least squares problems which have improved statistical performance relative to existing methods. We provide the first efficient methods for tuning parameter selection, compare our methods with current approaches via simulation and application, and provide theoretical intuition which makes explicit the impact of approximation on statistical efficiency and demonstrates the necessity of careful parameter tuning. Supplementary materials for this article are available online.