Source-linked AI summary
Stability Selection
Nicolai Meinshausen, Peter Buehlmann
TL;DR
High-dimensional structure estimation is difficult because selecting an appropriate regularisation level and avoiding false selections are challenging. The paper combines subsampling with high-dimensional selection algorithms, obtaining finite-sample error control and improved structure estimation. For randomised Lasso, it proves consistency even when the original Lasso’s consistency conditions are violated, with demonstrations on simulated and real data.
Problem
High-dimensional structure estimation requires choosing regularisation while controlling false selections, but the correct model and regularisation level are difficult to determine.
Method
Stability selection combines subsampling with high-dimensional selection algorithms and retains variables with high selection probabilities.
Results
Stability selection provides finite-sample familywise error control and markedly improves structure estimation; randomised Lasso remains variable-selection consistent when the original Lasso’s conditions are violated.
Takeaways & Limitations
The method offers a general principle for choosing regularisation in structure estimation and variable selection, with results demonstrated on simulated and real data.
Takeaways & Limitations
The randomised Lasso discussion identifies a tradeoff in the weakness α: low α can worsen conditioning of the weighted design matrix despite reducing selection of irrelevant variables.
Abstract
from arXiv · showhide
Estimation of structure, such as in variable selection, graphical modelling or cluster analysis is notoriously difficult, especially for high-dimensional data. We introduce stability selection. It is based on subsampling in combination with (high-dimensional) selection algorithms. As such, the method is extremely general and has a very wide range of applicability. Stability selection provides finite sample control for some error rates of false discoveries and hence a transparent principle to choose a proper amount of regularisation for structure estimation. Variable selection and structure estimation improve markedly for a range of selection methods if stability selection is applied. We prove for randomised Lasso that stability selection will be variable selection consistent even if the necessary conditions needed for consistency of the original Lasso method are violated. We demonstrate stability selection for variable selection and Gaussian graphical modelling, using real and simulated data.
1 Introduction
High-dimensional structure estimation and variable selection remain difficult because classical results often do not apply, optimisation can be computationally hard, and choosing regularisation is unresolved. The paper introduces stability selection to address these challenges across regression, graphical modelling, and clustering.
- Motivation: High-dimensional data expose limits of classical results for estimating graphs, clusters, and selected variables.The paper motivates stability selection primarily in settings where the number of variables or nodes can exceed the sample size.
- Motivation: Selecting a proper regularisation level remains difficult even for computationally tractable procedures with statistical guarantees.The desired level should recover a right-sized structure or model, but existing solutions are described as unsatisfactory.
- Proposed approach: Stability selection combines subsampling with selection algorithms to choose regularisation, control finite-sample false discoveries, and improve structure estimation.The paper applies the approach to variable selection and Gaussian graphical modelling and discusses clustering as another application area.
- Variable selection: In linear regression, Lasso is computationally feasible for large p, but consistent recovery of the relevant set requires restrictive design conditions and an appropriate λ.The method selects variables by shrinking some estimated coefficients exactly to zero.
- Graphical modelling: Graphical modelling uses sparse precision structure to infer conditional dependencies, while ℓ1-penalised estimators make large problems computationally feasible.The graphical Lasso obtains graph estimates through convex optimisation over nonnegative definite symmetric matrices.
2 Stability selection
Stability selection combines subsampling with existing selection procedures to identify variables or structures that are selected consistently across regularisation choices. It reduces sensitivity to tuning parameters and supports finite-sample control of false selections in high-dimensional settings.
- Stability selection: Stability selection enhances existing structure-estimation methods rather than replacing them.It applies broadly to procedures with a regularisation or tuning parameter.
- Stability paths: Selection probabilities form stability paths by recording how often each variable is selected across random subsamples.Subsamples contain floor(n/2) observations, and selection probabilities can also be defined for sets of variables.
- Example I: Variable selection in regression: In the vitamin dataset, stability selection separated relevant genes from noise more clearly than the original Lasso path.The first four selected variables were non-permuted, while randomised Lasso selected all six non-permuted variables before any noise variable.
- Example I: Variable selection in regression: Cross-validation selected 14 permuted variables, whereas stability paths made the regularisation choice less critical and improved the chance of selecting relevant variables.The supplied example contrasts the original path with stability-based selection in a high-dimensional gene-expression problem.
- Stability selection: Stable variables are those whose maximum selection probability across Λ exceeds the cutoff πthr.Results vary surprisingly little across sensible cutoff choices and across reasonable regularisation regions.
- Choice of regularisation and error control: Stability selection can provide finite-sample control of the expected number of falsely selected variables, while requiring assumptions for exact control.Reducing the selected-variable count or increasing πthr lowers the expected false-selection count; the error-control assumption may be stronger than desired.
- Example II: Graphical modelling: With independently permuted gene expressions, stability selection selected very few or no graph edges, unlike graphical Lasso.The empty graph was the true model in this experiment.
3 Consistent variable selection
Stability selection combines subsampling with selection procedures to make high-dimensional variable selection less sensitive to regularisation and consistent under weaker design conditions. For randomised Lasso, it can avoid false selections and retain consistency even when the irrepresentable condition is violated, while weakness tuning introduces a conditioning–false-selection tradeoff.
- Motivation: Stability selection makes variable-selection results much less sensitive to the regularisation parameter and provides guidance for choosing it.The paper motivates this advantage because the noise level is unknown and regularisation choice is notoriously difficult.
- Lasso and randomised Lasso: Additional random weight perturbations weaken the conditions needed for consistent variable selection, while subsampling alone often already yields large improvements.The authors recommend combining random weight perturbations with subsampling based on competitive empirical results.
- Lasso and randomised Lasso: Randomised Lasso with stability selection requires only a sparse-eigenvalue condition, rather than the irrepresentable condition required by original Lasso consistency.The paper states that this weaker requirement supports consistent variable selection even when the irrepresentable condition is violated.
- Lasso and randomised Lasso: For all sufficiently large λ, stability selection with randomised Lasso selects no noise variables, although variables with coefficients too small may be missed.The guarantee holds under the theorem’s sparse-eigenvalue assumptions and sufficiently high selection threshold.
- Lasso and randomised Lasso: Choosing a lower weakness parameter α reduces selection of irrelevant variables but can worsen conditioning by bringing the weighted design closer to singularity.The paper reports useful practical results for α in the range (0.2, 0.8).
- Example: In a p = n = 200 simulation where ρ > 0.5 violates the irrepresentable condition, randomised Lasso selected the two relevant variables with probability close to 1 and the irrelevant third variable much less often.Ordinary Lasso always included the third variable in this setting, whereas randomised Lasso separated relevant and irrelevant variables under stability selection.
4 Numerical Results
Numerical experiments evaluate stability selection with Lasso and OMP across regression, classification, simulated designs, and real datasets. Stability selection generally matches or improves variable recovery, often substantially, while reducing false selections relative to cross-validation.
- Experimental setup: Stability selection was evaluated with Lasso and OMP for regression and with Lasso for classification across simulated and real-data settings.The experiments used subsampling, with additional randomisation for randomised Lasso and randomised OMP.
- Real-data evaluation: Figure 7 compares cross-validated standard Lasso with randomised-Lasso stability selection on motif-regression and vitamin-gene-expression datasets.The evaluation varied signal-to-noise ratio and active-set size across 72 settings, each repeated 20 times.
- Real-data evaluation: On the real datasets, stability selection retained a proportion of correctly identified variables very close to cross-validation while dramatically reducing false selections.The comparison controls the expected number of wrong selections at E(V) ≤ 2.5.
- Experimental setup: The study evaluated 64 scenarios 100 times each, totaling about 20,000 simulations per method.Each scenario compared the standard procedure, subsampling-based stability selection, and stability selection with additional randomisation.
- Variable-selection performance: Across nearly all scenarios, stability selection identified at least as many correct variables as the underlying selection method.The sole exception was scenario (A), where performance was approximately equivalent because the design was nearly orthogonal.
- Variable-selection performance: Stability selection often produced substantial gains regardless of signal sparsity or signal-to-noise ratio.Additional randomisation was especially helpful when many variables violated the irrepresentable condition, such as in setting (E).
5 Discussion
The discussion presents stability selection as a general combination of subsampling and high-dimensional selection algorithms for difficult structure-estimation problems. It provides finite-sample false-discovery control and can improve selection consistency beyond the underlying method, including when Lasso conditions fail.
- Scope and method: Stability selection combines subsampling with high-dimensional selection algorithms and applies to variable selection and Gaussian graphical modelling.The paper characterizes the method as extremely general and demonstrates it on these structure-estimation tasks.
- Error control: Stability selection provides finite-sample familywise multiple-testing error control and a transparent principle for choosing regularisation.The discussion also reports that its solution depends surprisingly little on the initial regularisation choice.
- Consistency: For randomised Lasso, stability selection is variable-selection consistent even when conditions required by the original Lasso are violated.The paper therefore reports asymptotic recovery of the right model in scenarios where Lasso fails.
- Overall conclusion: Simulated and real data demonstrate both finite-sample familywise error control and markedly improved structure estimation.These are presented as the two main properties of stability selection.
6 Appendix
The appendix develops the sample-splitting machinery behind stability-selection bounds and establishes supporting results for randomized Lasso selection probabilities. It also analyzes how random predictor weights affect the design and conditions under which relevant variables are selected with probability one.
- Simultaneous selection: Sample splitting selects variables appearing in both fits on two disjoint subsets of size floor(n/2).The simultaneous selection set is the intersection of the two selected sets.
- Simultaneous selection: Simultaneous selection probabilities are defined over random sample splits and any additional randomness in the selection algorithm.A lemma converts subsampling-based selection probabilities into simultaneous-selection probabilities for the proof of Theorem 1.
- Error-control argument: The appendix formalizes a lower-bound lemma linking ordinary selection probabilities to simultaneous selection probabilities under sample splitting.The proof accounts for dependence between the two split-based selection events because both arise from splitting one fixed dataset.
- Error-control argument: The proof bounds simultaneous selection of noise variables using the expected size qΛ of the union of selected sets across regularisation values.The resulting probability bound scales as (qΛ/p)^2/ξ for threshold ξ, and yields a bound involving (qΛ/p)^2/(2πthr − 1).
- Randomized Lasso: Randomized Lasso is analyzed through an equivalent standard-Lasso formulation with variables rescaled by random weights.The transformation preserves the number of nonzero coefficients while changing the quadratic form through the weight matrix.
- Randomized Lasso: A weakness parameter α < 1 can distort design singular values, so the appendix derives lower bounds on α ensuring the required eigenvalue conditions.Under these conditions, the relevant variables outside Ssmall;λ have selection probability 1 on the high-probability event established in the theorem proof.