The sparsity and bias of the Lasso selection in high-dimensional linear regression

Abstract

Meinshausen and Buhlmann [Ann. Statist. 34 (2006) 1436--1462] showed that, for neighborhood selection in Gaussian graphical models, under a neighborhood stability condition, the LASSO is consistent, even when the number of variables is of greater order than the sample size. Zhao and Yu [(2006) J. Machine Learning Research 7 2541--2567] formalized the neighborhood stability condition in the context of linear regression as a strong irrepresentable condition. That paper showed that under this condition, the LASSO selects exactly the set of nonzero regression coefficients, provided that these coefficients are bounded away from zero at a certain rate. In this paper, the regression coefficients outside an ideal model are assumed to be small, but not necessarily zero. Under a sparse Riesz condition on the correlation of design variables, we prove that the LASSO selects a model of the correct order of dimensionality, controls the bias of the selected model at a level determined by the contributions of small regression coefficients and threshold bias, and selects all coefficients of greater order than the bias of the selected model. Moreover, as a consequence of this rate consistency of the LASSO in model selection, it is proved that the sum of error squares for the mean response and the ${\ell }_{\alpha }$-loss for the regression coefficients converge at the best possible rates under the given conditions. An interesting aspect of our results is that the logarithm of the number of variables can be of the same order as the sample size for certain random dependent designs.

arXiv commentPublished in at http://dx.doi.org/10.1214/07-AOS520 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (16)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "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
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• High-dimensional graphs and variable selection with the Lasso
• Lasso-type recovery of sparse representations for high-dimensional data
• High-dimensional generalized linear models and the lasso
• Sparsity oracle inequalities for the Lasso
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$

Cited by in corpus (69)

• Nearly unbiased variable selection under minimax concave penalty
• Simultaneous analysis of Lasso and Dantzig selector
• On asymptotically optimal confidence regions and tests for high-dimensional models
• On the conditions used to prove oracle results for the Lasso
• Least squares after model selection in high-dimensional sparse models
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• Controlling the false discovery rate via knockoffs
• Variable selection in nonparametric additive models
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Lasso-type recovery of sparse representations for high-dimensional data
• High-dimensional additive modeling
• Performance guarantees for individualized treatment rules
• The Emerging Trends of Multi-Label Learning
• High-dimensional variable selection
• Optimal rates of convergence for covariance matrix estimation
• A Selective Review of Group Selection in High-Dimensional Models
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Bayesian linear regression with sparse priors
• Needles and Straw in a Haystack: Posterior concentration for possibly sparse sequences
• Two sample tests for high-dimensional covariance matrices
• CAM: Causal additive models, high-dimensional order search and penalized regression
• Asymptotic normality and optimalities in estimation of large Gaussian graphical models
• Statistical significance in high-dimensional linear models
• Least angle and ${\ell }_1$ penalized regression: A review
• L1-Penalization for Mixture Regression Models
• Sparse recovery under matrix uncertainty
• SCAD-penalized regression in high-dimensional partially linear models
• Correlated variables in regression: clustering and sparse estimation
• Variable selection and regression analysis for graph-structured covariates with an application to genomics
• Regularization for Cox's proportional hazards model with NP-dimensionality
• Calibrating nonconvex penalized regression in ultra-high dimension
• Estimation for High-Dimensional Linear Mixed-Effects Models Using ${\ell }_1$-Penalization
• Pivotal estimation via square-root Lasso in nonparametric regression
• Variable selection in high-dimensional linear models: partially faithful distributions and the PC-simple algorithm
• Endogeneity in high dimensions
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• Oracle inequalities for the lasso in the Cox model
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
• High-dimensional variable selection via tilting
• The sparse Laplacian shrinkage estimator for high-dimensional regression
• Consistent group selection in high-dimensional linear regression
• Rates of convergence of the Adaptive LASSO estimators to the Oracle distribution and higher order refinements by the bootstrap
• Empirical Bayes posterior concentration in sparse high-dimensional linear models
• Discussion: One-step sparse estimates in nonconcave penalized likelihood models
• Minimax-optimal nonparametric regression in high dimensions
• Estimation in high-dimensional linear models with deterministic design matrices
• A Primal Dual Active Set Algorithm with Continuation for Compressed Sensing
• Vector-Valued Graph Trend Filtering with Non-Convex Penalties
• Parametric or nonparametric? A parametricness index for model selection
• High-dimensional regression in practice: an empirical study of finite-sample prediction, variable selection and ranking
• Mirror averaging with sparsity priors
• Asymptotic equivalence of regularization methods in thresholded parameter space
• SPADES and mixture models
• Model selection and structure specification in ultra-high dimensional generalised semi-varying coefficient models
• Discussion: One-step sparse estimates in nonconcave penalized likelihood models
• Group Iterative Spectrum Thresholding for Super-Resolution Sparse Spectral Selection
• Sparse regression algorithm for activity estimation in $\gamma$ spectrometry
• A general theory of regression adjustment for covariate-adaptive randomization: OLS, Lasso, and beyond
• Accuracy guarantees for L1-recovery
• Ultrahigh-dimensional Robust and Efficient Sparse Regression using Non-Concave Penalized Density Power Divergence
• Robust Information Criterion for Model Selection in Sparse High-Dimensional Linear Regression Models
• Monte Carlo Simulation for Lasso-Type Problems by Estimator Augmentation
• An analysis of penalized interaction models
• Culling the herd of moments with penalized empirical likelihood
• Smoothing the Edges: Smooth Optimization for Sparse Regularization using Hadamard Overparametrization
• Honest confidence sets for high-dimensional regression by projection and shrinkage
• Weighted residual empirical processes, martingale transformations, and model specification tests for regressions with diverging number of parameters
• KL-BSS: Rethinking optimality for neighbourhood selection in structural equation models