Stability Selection Setup - Structure Estimation with Lasso and Graphical Lasso

Summary

Structure estimation means recovering the support $S=\{k:{\beta }_k\ne 0\}$ of a sparse parameter: non-zero regression coefficients, non-zero precision-matrix entries (graph edges), or cluster structure. ${\ell }_1$ relaxations (Lasso, graphical Lasso) make this computationally feasible for $p\gg n$, but two problems remain. One is how much to regularise. The other is that recovering $S$ needs restrictive design conditions. Stability selection targets both with subsampling, giving finite-sample error control instead of asymptotic statements.

Overview

The paper opens (§1, pp. 1-2) by naming two obstacles in discrete structure estimation: computation (the problems are combinatorial) and “determining the right amount of regularisation”. Convex relaxations (${\ell }_1$ penalties) and greedy algorithms (boosting, matching pursuit) have largely solved the computational side. The regularisation side, picking a right-sized model, “has largely remained a problem with unsatisfactory solutions” (§1, p. 2).

The authors’ proposal is a generic subsampling approach (bootstrapping “would behave similarly”). It has three properties:

• it controls a familywise type-I error rate in finite samples;
• it is a new selection scheme in its own right;
• for the Lasso, it needs much weaker design assumptions for consistency, especially when extra randomisation is added to the selection step, in the spirit of Random Forests.

The paper stresses that subsampling had mostly been used for standard errors and confidence intervals. Here it is “of a very different nature” (§1, p. 2): it is used to select structure and to control errors.

Main Content

Generic notation (§1.1, p. 2)

Sparse structure, signal set and noise set (§1.1)

Let $\beta \in {\mathbb{R}}^p$ be sparse: $\Vert \beta {\Vert }_0=s<p$. Define

$$S=\{k:{\beta }_k\ne 0\},N=\{k:{\beta }_k=0\}.$$

The goal of structure estimation is to infer $S$ from noisy observations. Throughout, $S$ is the set of relevant variables and $N$ the noise variables, with $|S|+|N|=p$.

Example 1: variable selection in linear regression (eqs 1-2)

Data $(X^{(1)},Y^{(1)}),\dots ,(X^{(n)},Y^{(n)})$, typically i.i.d., with univariate $Y$ and $p$-dimensional $X$:

$$Y=X\beta +\epsilon ,\text{\hspace{1em}(1)}$$

where $Y=(Y_1,\dots ,Y_n)$, $X$ is the $n\times p$ design and $\epsilon$ has i.i.d. components.

The classical route penalises the negative log-likelihood by $\Vert \beta {\Vert }_0$. This is infeasible for large $p$ even with branch-and-bound. Its convex relaxation is the Lasso (Tibshirani 1996; Chen et al. 2001):

Lasso estimator and selected set (eq. 2)

$${\hat{\beta }}^{\lambda }=\arg \underset{\beta \in {\mathbb{R}}^p}{\min }\Vert Y-X\beta {\Vert }_2^2+\lambda \sum _{k=1}^p|{\beta }_k|,$$

with $\lambda \in {\mathbb{R}}^{+}$ and columns standardised, $\Vert X_k{\Vert }_2^2={\sum }_i(X_k^{(i)}{)}^2=1$. The estimated support is

$${\hat{S}}^{\lambda }=\{k:{\hat{\beta }}_k^{\lambda }\ne 0\}.$$

The problem is convex, so it is feasible for large $p$, and it sets coefficients exactly to zero.

The open issues (§1.1, p. 3) are choosing $\lambda$ for consistent selection, and the “restrictive design conditions” needed to recover $S$ asymptotically. Both are developed in Randomised Lasso and the Irrepresentable Condition.

Example 2: Gaussian graphical modelling (eqs 3-4)

$$X^{(1)},\dots ,X^{(n)}\text{i.i.d.}\sim {\mathcal{N}}_d(\mu ,\Sigma ).\text{\hspace{1em}(3)}$$

$X_j$ and $X_k$ are conditionally dependent given all other components iff $({\Sigma }^{-1}{)}_{jk}\ne 0$, and then the graph has an edge $j$-$k$ (Lauritzen 1996). The structure lives on the index set $G=\{(j,k):1\le j<k\le d\}$, with $p=\left(\genfrac{}{}{0ex}{}{d}{2}\right)$, and

$$S=\{(j,k)\in G:({\Sigma }^{-1}{)}_{jk}\ne 0\}.$$

Graphical Lasso (eq. 4; Friedman et al. 2008)

$${\hat{\Theta }}^{\lambda }=\arg \underset{\Theta \text{nonneg. def.}}{\min }\{-\log \det \Theta +\mathrm{tr}(S\Theta )+\lambda \sum _{j<k}|{\Theta }_{jk}|\},$$

where $S$ here denotes the empirical covariance. This is the ${\ell }_1$-penalised Gaussian log-likelihood, partially maximised over $\mu$. Estimated edge set: ${\hat{S}}^{\lambda }=\{(j,k)\in G:{\hat{\Theta }}_{jk}^{\lambda }\ne 0\}$.

Worked through in Stability Selection for Gaussian Graphical Models and Computational Cost.

Example 3: clustering (§1.1, p. 3)

Choosing the number of clusters is “notoriously difficult”. Clusters that are stable under subsampling or perturbation are more believable, which is the idea behind consensus clustering (Monti et al. 2003). The authors state that their false-discovery control “can be applied to consensus clustering” to tune a base clustering method. The paper does not develop this further.

Outline and positioning (§1.2, p. 4)

Resampling for validation “is certainly not new”. The paper’s contribution is to put it into a formal framework with empirical and theoretical guarantees. The sections are: §2 generic method, error control and examples; §3 asymptotics for Lasso and randomised Lasso; §4 numerical results; §5 discussion; Appendix proofs.

Examples

Mapping the setup to a marketing-analytics problem

Setup: A weekly regression of a sales KPI on 60 candidate drivers (media channels at several adstock lags, price, distribution, weather, macro indices) with $n=104$ weeks. $p<n$, but many drivers are highly collinear. Structure question: Which drivers have ${\beta }_k\ne 0$? This is $S$ in the paper’s notation, and the Lasso’s ${\hat{S}}^{\lambda }$ is one estimate. Why the paper applies: The answer changes with $\lambda$. It also changes across resamples when columns are correlated, which is the “restrictive design condition” problem. Stability selection asks which drivers are selected in most half-samples, and how many false drivers we expect for a given threshold.

Connections

• The Lasso’s shrinkage also biases coefficient estimates, a different problem from support recovery. See Regularization Bias and the Partially Linear Model and DML Estimators for ATE and the Interactive Model. Stability selection addresses which variables, not how large the effects are.
• Bayesian alternatives to ${\ell }_1$ selection: Spike-and-Slab Prior for Covariate Selection, Horseshoe and Regularized Horseshoe Priors.
• Graph-structure selection in another model class: Estimation and Structure Selection for Vines.

See Also

• Meinshausen Buhlmann 2010 - Stability Selection - Overview
• Stability Paths and the Stable-Variable Set
• Randomised Lasso and the Irrepresentable Condition