Bolasso model consistent Lasso estimation through the bootstrap.pdf

arXiv: [] 8 Apr 2008 Bolasso: Model Consistent Lasso Estimation through the Bootstrap Francis R. Bach @ INRIA - WILLOWProject-Team Laboratoire d’Informatique de l’Ecole Normale Sup′erieure (CNRS/ENS/INRIA UMR 8548) 45 rue d’Ulm, 75230 Paris, France April 9, 2008 Abstract We consider the least-square linear regression problem with regular- ization by the? 1-norm, a problem usually referred to as the Lasso. In this paper, we present a detailed asymptotic analysis of model consistency of the Lasso. For various decays of the regularization parameter, pute asymptotic equivalents of the probability of correct modelselection (., variable selection). For a speci?c rate decay, we show that the Lasso se- lects all the variables that should enter the model with probability tending to one exponentially fast, while it selects all other variables with strictly positive probability. We show that this property implies that if we run the Lasso for several bootstrapped replications of a given sample, then intersecting the supports of the Lasso bootstrap estimatesleads to consis- tent model selection. This novel variable selection algorithm, referred to as the Bolasso, pared favorably to other linear regression methods on synthetic data and datasets from the UCI machine learningrepository. 1 Introduction Regularization by the? 1-norm has attracted a lot of interest in recent years in machine learning, statistics and signal processing. In thecontext of least-square linear regression, the problem is usually referred to as theLasso(Tibshirani, 1994). Much of the early e?ort has been dedicated to algorithms to solve the optimization probleme?ciently. In particular, theLarsalgorithmof Efron et al. (2004) allows to ?nd the entire regularization path (., the set of solutions for all values of the regularization parameters) at the cost of a single matrix inversion. Moreover, a well-known justi?cation of the regularizationby the? 1-norm is that it leads tos