Bolasso: model consistent Lasso estimation through the bootstrap

By Francis R. Bach. 2008

474 citations recorded by the source corpus.

We consider the least-square linear regression problem with regularization by the l1-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, we compute asymptotic equivalents of the probability of correct model selection (i.e., variable selection). For a specific rate decay, we show that the Lasso selects 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 estimates leads to consistent model selection. This novel variable selection algorithm, referred to as the Bolasso, is compared favorably to other linear regression methods on synthetic data and datasets from the UCI machine learning repository.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Forward stability and model path selection (2021, neutral): “…on assessing consistency and establishing conditions under which it can be guaranteed that the estimated tuning parameter(s) cor-respondingtothechosen ˆ f m convergestotheirtrueoroptimal values [see e.g. Zhao and Yu (2006); Bach (2008); Zhang (2009) or Fan and Lv (2010) for a thorough overview].”
Stability selection (2008, background): “In related and very interesting work, Bach (2008) has proposed the ‘bolasso’ (for bootstrapped enhanced lasso) and shown that using a finite number of subsamples of the original lasso procedure and applying basically stability selection with πthr = 1 yield consistent variables selection under the…”
Nearly unbiased variable selection under minimax concave penalty (2010, methodology): “Post-LASSO selection [Meinshausen (2007)] or bootstrapped LASSO [Bach (2008)] may not recover false nondiscovery of the LASSO (Section 6.5). Adaptive LASSO [Zou (2006), Huang, Ma and Zhang (2008) and Zou and Li (2008)] requires an initial estimator of β based on which small penalty levels could be a”
Group Lasso with Overlaps: the Latent Group Lasso approach (2011, background): “The proof of consistency we present below follows a classical proof scheme (Bach, 2008a).”
Variable selection with error control: another look at stability selection (2011, background): “Work that is related more specifically to stability selection includes Bach (2008), who studied the ‘bolasso’ (short for bootstrapped enhanced lasso).”
Self-concordant analysis for logistic regression (2009, methodology): “Also, other regularization frameworks based on sparsity-induci ng norms could be applied to logistic regression with similar guarantees than for least-s quares regression, such as group Lasso for grouped variables [43] or non-parametric problem s [36], or resampling-based procedures [44, 45] that al”
Stable Feature Selection for Biomarker Discovery (2010, methodology): “Sampling Method Feature Selector Aggregation Method Davis et al [24] Random Subset Filter Method Linear Combination Bach [25] Boostrap Lasso [28] Linear Combination Meinshausen and Buhlmann [26] Random Subset Randomized Lasso Linear Combination Abeel et al [27] Random Subset SVM-REF [29] Linear…”
Differentially Private Model Selection via Stability Arguments and the Robustness of the Lasso (2013, methodology): “The notion of stability to subsampling or resampling from the training data set has also been studied (Shao, 1996; Bach, 2008; Meinshausen and Buehlmann, 2010; Meilă, 2006).”
High-Dimensional Feature Selection by Feature-Wise Kernelized Lasso (2012, background): “Another approach to deal with large sample size would be using stability selection which consists in running HSIC Lasso many times with subsampling and computing the number of times each feature is selected across the runs (Meinshausen and B¨uhlmann, 2010; Bach, 2008).”
Estimation Stability With Cross-Validation (ESCV) (2013, result): “This is in contrast to related work (Bach 2008; Meinshausen and B¨uhlmann 2010) which requires a much larger V .”
p-Values for High-Dimensional Regression (2008, methodology): “Bach (2008) and Meinshausen and Bühlmann (2008) showed that for the Lasso, this leads to a consistent model selection procedure under fewer restrictions than for the nonbootstrap case.”
Asymptotic Properties of Lasso+mLS and Lasso+Ridge in Sparse High-dimensional Linear Regression (2013, methodology): “ the sense that with probability converging to 1 d(G n,G∗) → 0. (3.7) Remark 3.2. In practice, if the Irrepresentable Condition does not hold, one needsto tryothermodel selection methods, e.g.,Bolasso[1] orstabilityselection. As stated before, as long as the probabilities ofselecting wrongmodels P(S”
TIGRESS: Trustful Inference of Gene REgulation using Stability Selection (2012, methodology): “It was shown that stability selection can reduce the sensitivity of LARS and Lasso to correlated features, and improve their ability to select correct features [3, 29].”
Tracking the flu pandemic by monitoring the social web (2010, methodology): “Flu detector is a tool we developed that uses an improved methodology (which includes the application of Bolasso [2], the bootstrap version of LASSO) to make live, daily predictions for the ILI rates in several UK regions based on the contents of Twitter (ECML PKDD 2010).”
Structured sparsity through convex optimization (2011, background): “For more details, see Bach (2008).”
Consistency of the group Lasso and multiple kernel learning (2007, unknown): “samples, computed by the algorithm of Bach et al. (2004b). We only plot the values of the estimated variables η̂ j, j = 1, .”