Source-linked AI summary
Bolasso: model consistent Lasso estimation through the bootstrap
Francis Bach
TL;DR
The paper analyzes Lasso variable-selection consistency across regularization-parameter decay rates. It shows that intersecting supports from bootstrapped Lasso fits yields the consistent Bolasso procedure under general assumptions.
Problem
The paper studies model consistency and variable-selection probabilities for least-square linear regression regularized by the l1-norm.
Method
It derives asymptotic selection results for the Lasso and uses bootstrap samples to replicate datasets, intersecting the supports of the resulting estimates.
Results
With µ_n proportional to n^-1/2, the Lasso selects relevant variables with probability tending to one exponentially fast while selecting irrelevant variables with strictly positive probability; the Bolasso is provably consistent.
Takeaways & Limitations
Bootstrap resampling and support intersection can enhance poor Lasso variable-selection results through a simple parameter-free procedure.
Takeaways & Limitations
The analysis focuses on a fixed total number of variables, so extending it to growing dimensionality remains important.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies whether Lasso sparsity produces consistent variable selection and introduces an asymptotic and bootstrap-based approach to address its limitations.
- Lasso regularization produces sparse solutions and therefore performs model selection.The paper frames model consistency as whether Lasso recovers a sparse generating pattern as observations grow.
- Model consistency depends on the generating covariance structure: Lasso is consistent under low correlations but can fail under strong correlations.
- The paper derives asymptotic model-selection results for Lasso under different regularization-parameter decay rates.
- For decay proportional to n^-1/2, Lasso selects relevant variables with probability approaching one exponentially fast, while irrelevant variables remain selected with strictly positive probability.
- The study uses bootstrap resampling to mimic multiple datasets and intersects Lasso supports to improve model selection consistency.The paper presents this procedure alongside asymptotic analysis and evaluations on synthetic and UCI datasets.
2 Asymptotic Analysis of Model Selection for the Lasso
The paper characterizes how Lasso model selection behaves across regularization-parameter decay regimes, then focuses on root-n decay, where relevant variables are recovered reliably but irrelevant-variable patterns remain random. This motivates intersecting supports across bootstrap replications to obtain consistent selection.
- Asymptotic regimes: The analysis examines five mutually exclusive asymptotic regimes for the Lasso regularization parameter.These regimes cover the regularization path under assumptions (A1-3).
- Asymptotic regimes: If µn tends to infinity, the Lasso estimate equals zero with probability tending to one.
- Asymptotic regimes: If µn tends to a positive constant, the estimate converges to a penalized population minimizer rather than w.Its limiting sign pattern may or may not match the population sign pattern.
- Asymptotic regimes: If µn tends to zero slower than n^-1/2, the estimate is norm-consistent, but correct sign recovery requires the stated consistency condition.When the condition fails, the probability of correct sign estimation tends to zero.
- Exact root-n decay: For µn = µ0n^-1/2, relevant-variable signs are recovered with probability tending to one, while every compatible irrelevant-variable pattern has a strictly positive limiting probability.This pattern holds under assumptions (A1-3), with limits ρ(s, µ0) in (0, 1) for compatible sign patterns.
- Asymptotic regimes: If µn decays faster than n^-1/2, the estimate is norm-consistent but selects all variables with probability tending to one.Thus the ℓ1-norm has no sparsifying effect in this regime.
- Motivation for Bolasso: Intersecting supports from repeated root-n Lasso fits isolates exactly J because every fit asymptotically includes J while irrelevant variables vary across fits.Bootstrap samples are used because multiple independent copies of the original data are normally unavailable.
3 Bolasso: Bootstrapped Lasso
Bolasso repeatedly fits the Lasso on bootstrap samples and intersects the resulting supports. Under root-n regularization, this procedure is proved to select the correct active variables with overwhelming probability when the bootstrap count grows suitably slowly.
- Bootstrap procedure: Each bootstrap replicate samples n observations with replacement from the original data and independently produces a Lasso estimate.
- Support intersection: Bolasso defines each replicate support as the nonzero coordinates of its Lasso estimate and intersects all m supports.After selection, it fits unregularized least squares restricted to the intersected variables.
- Algorithm: The algorithm adds only the number of bootstrap samples m as an extra parameter.In simulations, m = 128 except when studying the influence of m.
- Computation: The Bolasso has computational complexity O(m(p^3 + p^2n)).Lars can compute many regularization parameters through the full empirical regularization path.
- Consistency guarantee: Under (A1-3) and µn = µ0n^-1/2, the probability of incorrect model selection admits an explicit upper bound.The bound uses strictly positive constants A1, A2, A3, and A4.
- Consistency guarantee: If log(m) grows slower than n, Bolasso selects the correct active variables with overwhelming probability and recovers the correct sign pattern through restricted least squares.The guarantee holds whether or not the Lasso consistency condition in Eq. (2) is satisfied.
4 Simulations
Synthetic and benchmark experiments compare Lasso, Bolasso, and alternative variable-selection or regression methods under conditions where Lasso consistency is satisfied or violated. Across these settings, Bolasso expands or creates consistency regions, improves support recovery, and performs especially well when the generating model is sparse.
- 4.1 Synthetic examples: The synthetic setup samples correlated Gaussian covariates with p variables, selects r relevant variables, and adds Gaussian noise scaled to the signal.The generated distributions satisfy assumptions (A1–3) with probability one.
- 4.1 Synthetic examples: In the Lasso-inconsistent setting, no regularization value achieves perfect selection, although a range selects every relevant variable while selecting irrelevant variables with probabilities strictly between zero and one.This behavior is shown for p = 16, r = 8, n = 1000, and 256 replications.
- 4.1 Synthetic examples: With m = 128 bootstrap replications, Bolasso widens the Lasso consistency region when the condition holds and creates one when it does not.Figure 2 uses the same synthetic conditions as Figure 1.
- 4.1 Synthetic examples: Increasing the number of bootstrap replications improves exact-support recovery for Bolasso in the Lasso-inconsistent case.Figure 3 compares m ∈ {2, 4, 8, 16, 32, 64, 128, 256} over 256 experiments.
- 4.1 Synthetic examples: Bolasso outperforms the other variable-selection methods in simulations with p = 64, r = 8, and varying n, including settings where n is comparable to p.The comparison includes Lasso, forward greedy, thresholded least squares, adaptive Lasso, and bagged least-square regression with thresholding.
- 4.2 UCI datasets: On generated sparse data, Bolasso outperforms the compared regression models, whereas on other datasets its strict intersection can make Bolasso-S more competitive.The regression comparison uses mean squared prediction error, multiplied by 100, with cross-validated regularization parameters.
5 Conclusion
The paper shows that bootstrap resampling can make Lasso variable selection consistent through a simple parameter-free procedure. It also identifies extensions involving growing variable counts and related regularizers or losses.
- The Bolasso is a bootstrapped Lasso procedure with provable model consistency under general assumptions.It analyzes variable-selection properties of a resampled version of the Lasso.
- Bootstrap resampling can enhance poor Lasso variable-selection results through a simple parameter-free procedure.
- The analysis focuses on a fixed total number of variables, leaving growing-dimensional settings as an important extension.
- The same technique could extend to block ℓ1-norm regularization and other losses, including general convex classification losses.
A Proof of Model Consistency Results
The proof sketches rely on a standard Lasso property: once the solution’s sign pattern is known, the optimization solution can be written in closed form.
- The appendix sketches proofs for the asymptotic results on Lasso and Bolasso model consistency.
- Knowing the Lasso solution’s sign pattern permits obtaining the solution in closed form.
- This sign-pattern property underpins the proof strategy for the reported asymptotic results.
A.1 Optimality Conditions
The proof characterizes Lasso optimality through sign and sparsity patterns, then connects those patterns to random quantities governed asymptotically by laws of large numbers and central limit behavior.
- The optimality conditions are expressed using the solution’s sign pattern s and sparsity pattern J.Here, s records coefficient signs and J indexes nonzero coefficients.
- The analysis sets the regularization parameter to µ_n = µ_0n^-1/2 and studies limiting behavior of Q and n^1/2q.Q converges almost surely to Q, while n^1/2q is asymptotically normal with covariance σ^2Q.
- Under suitable conditions, a mismatch between estimated and true active-sign patterns implies a lower bound on ∥Q^-1/2q∥2.
- A candidate sign pattern containing the true active set can be used to establish equality between estimated and true sign patterns.
- The lemmas connect sign-pattern optimality to quantities for which concentration inequalities can be derived.
A.2 Concentration Inequalities
The concentration analysis bounds deviations of empirical quantities and approximates normalized random vectors with Gaussian probabilities over convex sets.
- The proofs bound P(∥Q^-1/2q∥2 > α) and P(∥Q − Q∥2 > η) using standard concentration arguments.The bounds apply when α and η are below specified positive constants.
- Multivariate Berry-Esseen inequalities approximate P(n^1/2q ∈ C) by the probability that a normal vector lies in C.The approximation is uniformly bounded over convex sets C.
- The comparison normal distribution has mean zero and covariance matrix σ^2Q.
A.3 Proof of Proposition 1
The proof bounds the Lasso’s sign-recovery probability by a strictly positive limiting quantity, with an error that vanishes at rate O((log n)n^-1/2).
- The sign-error probability is upperbounded for sufficiently large n using Lemma 2.
- P(sign(ŵ) = sign(w)) is at least ρ(s, µ0) + O((log n)n^-1/2).Here ρ(s, µ0) = P{t ∈ C(s, µ0)}.
- ρ(s, µ0) lies strictly between 0 and 1 because C(s, µ0) and its complement have nonempty interiors.The normal distribution involved has positive definite covariance matrix σ2Q.
- The same type of bound applies in the opposite direction, yielding a matching asymptotic characterization.
A.4 Proof of Proposition 2
The proof controls failure to select relevant variables through concentration bounds for the transformed noise and empirical covariance.
- The probability of selecting none of the variables in J is bounded by two concentration-event probabilities.These involve Q^-1/2q and the empirical covariance Q̂.
- The first event controls the norm of Q^-1/2q relative to C1 − µnC2.
- The second event controls deviation of Q̂ from Q relative to λmin(Q)/2.
A.5 Proof of Proposition 3
The proof establishes exponentially small failure probabilities for bootstrap selection of relevant variables, while analyzing over-selection through concentration and Gaussian bounds.
- Assumptions and concentration: Compact support assumptions permit concentration control, while extending the proof to assumption (A1) requires only minor changes.
- Bootstrap selection: The proof separates bootstrap failure into missing at least one relevant variable and failing to obtain the exact relevant-variable set.
- Bootstrap selection: The argument relates ghost-sample quantities to original-sample quantities through deviations such as q∗ − q and Q∗ − Q.
- Bootstrap selection: The probability that one bootstrap replication fails to select a relevant variable is at most Be^-Cn, with B and C strictly positive.Across m replications, this contribution is bounded by mBe^-Cn.
- Bootstrap selection: The exact-set analysis is deliberately loose because different extra variables can cancel under support intersection.
- Assumptions and concentration: Gaussian tail control bounds P(n^1/2q + y ∉ C(µ0) | q), and truncation combines this with a Hoeffding bound on ∥n^1/2q∥2.Choosing α by minimizing the resulting bound produces the stated rate form.