Thresholded Lasso for high dimensional variable selection and statistical estimation

Abstract

Given $n$ noisy samples with $p$ dimensions, where $n\ll p$, we show that the multi-step thresholding procedure based on the Lasso -- we call it the {\it Thresholded Lasso}, can accurately estimate a sparse vector $\beta \in {\mathbb{R}}^p$ in a linear model $Y=X\beta +\epsilon$, where $X_{n\times p}$ is a design matrix normalized to have column ${\ell }_2$ norm $\sqrt{n}$, and $\epsilon \sim N(0,{\sigma }^2{I}_n)$. We show that under the restricted eigenvalue (RE) condition (Bickel-Ritov-Tsybakov 09), it is possible to achieve the ${\ell }_2$ loss within a logarithmic factor of the ideal mean square error one would achieve with an {\em oracle} while selecting a sufficiently sparse model -- hence achieving {\it sparse oracle inequalities}; the oracle would supply perfect information about which coordinates are non-zero and which are above the noise level. In some sense, the Thresholded Lasso recovers the choices that would have been made by the ${\ell }_0$ penalized least squares estimators, in that it selects a sufficiently sparse model without sacrificing the accuracy in estimating $\beta$ and in predicting $X\beta$. We also show for the Gauss-Dantzig selector (Candès-Tao 07), if $X$ obeys a uniform uncertainty principle and if the true parameter is sufficiently sparse, one will achieve the sparse oracle inequalities as above, while allowing at most $s_0$ irrelevant variables in the model in the worst case, where $s_0\le s$ is the smallest integer such that for $\lambda =\sqrt{2\log p/n}$, ${\sum }_{i=1}^p\min ({\beta }_i^2,{\lambda }^2{\sigma }^2)\le s_0{\lambda }^2{\sigma }^2$. Our simulation results on the Thresholded Lasso match our theoretical analysis excellently.

37 Pages, 4 Figures; Parts of the paper have appeared in Proceedings of Advances in Neural Information Processing Systems 22, December, 2009 (NIPS 2009)

References in corpus (17)

• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Simultaneous analysis of Lasso and Dantzig selector
• On the conditions used to prove oracle results for the Lasso
• The Dantzig selector and sparsity oracle inequalities
• Adaptive Lasso for High Dimensional Regression and Gaussian Graphical Modeling
• Restricted Eigenvalue Conditions on Subgaussian Random Matrices
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• The adaptive and the thresholded Lasso for potentially misspecified models

Cited by in corpus (14)

• Regularized estimation in sparse high-dimensional time series models
• Calibrating nonconvex penalized regression in ultra-high dimension
• High-dimensional covariance estimation based on Gaussian graphical models
• UPS delivers optimal phase diagram in high-dimensional variable selection
• Network Granger Causality with Inherent Grouping Structure
• Model Selection for High-Dimensional Regression under the Generalized Irrepresentability Condition
• Combined l_1 and greedy l_0 penalized least squares for linear model selection
• The adaptive and the thresholded Lasso for potentially misspecified models
• No penalty no tears: Least squares in high-dimensional linear models
• Thresholded Lasso Bandit
• Variable Selection with Second-Generation P-Values
• Reducing bias and alleviating the influence of excess of zeros with multioutcome adaptive LAD-lasso
• Rapid mixing of a Markov chain for an exponentially weighted aggregation estimator
• Tensor models for linguistics pitch curve data of native speakers of Afrikaans