Sparsity oracle inequalities for the Lasso

Abstract

This paper studies oracle properties of ${\ell }_1$-penalized least squares in nonparametric regression setting with random design. We show that the penalized least squares estimator satisfies sparsity oracle inequalities, i.e., bounds in terms of the number of non-zero components of the oracle vector. The results are valid even when the dimension of the model is (much) larger than the sample size and the regression matrix is not positive definite. They can be applied to high-dimensional linear regression, to nonparametric adaptive regression estimation and to the problem of aggregation of arbitrary estimators.

Published at http://dx.doi.org/10.1214/07-EJS008 in the Electronic Journal of Statistics (http://www.i-journals.org/ejs/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• High-dimensional generalized linear models and the lasso

Cited by in corpus (55)

• 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
• Variable selection in nonparametric additive models
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• Lasso-type recovery of sparse representations for high-dimensional data
• High-dimensional additive modeling
• Performance guarantees for individualized treatment rules
• High-dimensional generalized linear models and the lasso
• Near-ideal model selection by ${\ell }_1$ minimization
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Bayesian linear regression with sparse priors
• 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
• On the Prediction Performance of the Lasso
• Regularization for Cox's proportional hazards model with NP-dimensionality
• Lasso and probabilistic inequalities for multivariate point processes
• Pivotal estimation via square-root Lasso in nonparametric regression
• The Dantzig selector and sparsity oracle inequalities
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Feature Selection with Annealing for Computer Vision and Big Data Learning
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• The Lasso for High-Dimensional Regression with a Possible Change-Point
• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• Oracle inequalities for the lasso in the Cox model
• A new perspective on least squares under convex constraint
• Honest variable selection in linear and logistic regression models via ${\ell }_1$ and ${\ell }_1+{\ell }_2$ penalization
• Rates of convergence of the Adaptive LASSO estimators to the Oracle distribution and higher order refinements by the bootstrap
• Rejoinder: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• High dimensional thresholded regression and shrinkage effect
• Discussion: A tale of three cousins: Lasso, L2Boosting and Dantzig
• Ridge regression and asymptotic minimax estimation over spheres of growing dimension
• Asymptotic equivalence of regularization methods in thresholded parameter space
• Mirror averaging with sparsity priors
• SPADES and mixture models
• Sparse recovery in convex hulls via entropy penalization
• Pac-bayesian bounds for sparse regression estimation with exponential weights
• Accuracy guarantees for L1-recovery
• Quasi-Likelihood and/or Robust Estimation in High Dimensions
• Exact Localization and Superresolution with Noisy Data and Random Illumination
• Greedy algorithms for prediction
• On the Sensitivity of the Lasso to the Number of Predictor Variables
• Structured Estimation in Nonparameteric Cox Model
• General nonexact oracle inequalities for classes with a subexponential envelope
• Parallel integrative learning for large-scale multi-response regression with incomplete outcomes
• A study on tuning parameter selection for the high-dimensional lasso
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• Structured, sparse regression with application to HIV drug resistance
• Decomposable Norm Minimization with Proximal-Gradient Homotopy Algorithm
• Regularity Properties for Sparse Regression