Some sharp performance bounds for least squares regression with $L_1$ regularization

Abstract

We derive sharp performance bounds for least squares regression with $L_1$ regularization from parameter estimation accuracy and feature selection quality perspectives. The main result proved for $L_1$ regularization extends a similar result in [Ann. Statist. 35 (2007) 2313--2351] for the Dantzig selector. It gives an affirmative answer to an open question in [Ann. Statist. 35 (2007) 2358--2364]. Moreover, the result leads to an extended view of feature selection that allows less restrictive conditions than some recent work. Based on the theoretical insights, a novel two-stage $L_1$-regularization procedure with selective penalization is analyzed. It is shown that if the target parameter vector can be decomposed as the sum of a sparse parameter vector with large coefficients and another less sparse vector with relatively small coefficients, then the two-stage procedure can lead to improved performance.

Published in at http://dx.doi.org/10.1214/08-AOS659 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (11)

• High-dimensional graphs and variable selection with the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• 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 generalized linear models and the lasso
• Near-ideal model selection by ${\ell }_1$ minimization
• Sparsity oracle inequalities for the Lasso
• Aggregation for Gaussian regression
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• The Dantzig selector and sparsity oracle inequalities
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$

Cited by in corpus (19)

• On the conditions used to prove oracle results for the Lasso
• Strong oracle optimality of folded concave penalized estimation
• A Selective Review of Group Selection in High-Dimensional Models
• Asymptotic normality and optimalities in estimation of large Gaussian graphical models
• L1-Penalization for Mixture Regression Models
• Sparse recovery under matrix uncertainty
• On the Prediction Performance of the Lasso
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
• Dynamic Filtering of Time-Varying Sparse Signals via l1 Minimization
• Group Sparse Recovery via the ${\ell }^0({\ell }^2)$ Penalty: Theory and Algorithm
• Discrete and Continuous-time Soft-Thresholding with Dynamic Inputs
• Mirror averaging with sparsity priors
• Linearly-involved Moreau-Enhanced-over-Subspace Model: Debiased Sparse Modeling and Stable Outlier-Robust Regression
• Iterative Soft/Hard Thresholding with Homotopy Continuation for Sparse Recovery
• Accuracy guarantees for L1-recovery
• General nonexact oracle inequalities for classes with a subexponential envelope
• Monotone Lipschitz-Gradient Denoiser: Explainability of Operator Regularization Approaches Free From Lipschitz Constant Control
• Continuous Relaxation of Discontinuous Shrinkage Operator: Proximal Inclusion and Conversion
• KL-BSS: Rethinking optimality for neighbourhood selection in structural equation models