Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees
This work provides a fast approximation method for sparse regression in high-dimensional settings, but it is incremental as it builds on existing JL transform techniques with theoretical refinements.
The authors tackled the problem of large-scale high-dimensional sparse least-squares regression by using Johnson-Lindenstrauss transforms to compress data and solve with a larger regularization parameter, establishing non-asymptotic optimization error bounds for elastic net and ℓ1 norm regularizers.
In this paper, we study a fast approximation method for {\it large-scale high-dimensional} sparse least-squares regression problem by exploiting the Johnson-Lindenstrauss (JL) transforms, which embed a set of high-dimensional vectors into a low-dimensional space. In particular, we propose to apply the JL transforms to the data matrix and the target vector and then to solve a sparse least-squares problem on the compressed data with a {\it slightly larger regularization parameter}. Theoretically, we establish the optimization error bound of the learned model for two different sparsity-inducing regularizers, i.e., the elastic net and the $\ell_1$ norm. Compared with previous relevant work, our analysis is {\it non-asymptotic and exhibits more insights} on the bound, the sample complexity and the regularization. As an illustration, we also provide an error bound of the {\it Dantzig selector} under JL transforms.