Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees

Tianbao Yang; Lijun Zhang; Qihang Lin; Rong Jin

doi:10.48550/arxiv.1507.05185

Back

Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees

Preprint

Open access

Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees

Tianbao Yang, Lijun Zhang, Qihang Lin and Rong Jin

ArXiv.org

07/18/2015

DOI: 10.48550/arxiv.1507.05185

Files and links (1)

url

https://doi.org/10.48550/arxiv.1507.05185View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

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.

Details

Title: Subtitle: Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees
Creators: Tianbao Yang
Lijun Zhang
Qihang Lin
Rong Jin
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.1507.05185
ISSN: 2331-8422
Language: English
Date posted: 07/18/2015
Academic Unit: Business Analytics; Computer Science
Record Identifier: 9984380581102771

Metrics

7 Record Views