What causes lasso to be unstable for feature selection?

Question

In compressed sensing, there is a theorem guarantee that $$\text{argmin} \Vert c \Vert_1\\ \text{subject to } y = Xc $$ has a unique sparse solution $c$ (See appendix for more details).

Is there a similar theorem for lasso? If there is such a theorem, not only will it guarantee the stability of lasso, but it will also provide lasso with a more meaningful interpretation:

lasso can uncover the sparse regression coefficient vector $c$ that is used to generate the response $y$ by $y = Xc$.

There are two reasons that I ask this question:

1. I think 'lasso favors a sparse solution' is not an answer to why use lasso for feature selection since we can't even tell what the advantage of the features we select is.

2. I learned lasso is notorious for being unstable for feature selection. In practice, we have to run bootstrap samples to evaluate its stability. What is the most crucial reason that causes this instability?

---

Appendix:

Given $X_{N \times M} = (x_1, \cdots, x_M)$. $c$ is a $\Omega$-sparse vector ($\Omega \leqslant M$). The process $y = Xc$ generates the response $y$. If $X$ has the NSP (null space property) of order $\Omega$ and covariance matrix of $X$ has no eigenvalue close to zero, there will be a unique solution to $$\text{argmin} \Vert c \Vert_1\\ \text{subject to } y = Xc $$ which is exactly the $c$ that gives $y$.

What this theorem also tells is also if $X$ has not the NSP of order $\Omega$, it is simply hopeless to solve $\text{argmin}_{c: y = Xc} \Vert c \Vert_1$.

---

EDIT:

After receiving these great answers, I realized I was confused when I was asking this question.

Why this question is confusing:

I read a research paper in which we have to decide how many features (columns) the design matrix $X_{N \times M}$ is going to have (auxiliary features are created from primary features). Since it is a typical $n < p$ problem, $D$ is expected to be well constructed so that the solution to lasso can be a good approximation of the real sparse solution.

The reasoning is made from the theorem that I mentioned in the appendix: If we aim to find a $\Omega$-sparse solution $c$, $X$ has better to have the NSP of order $\Omega$.

For a general $N \times M$ matrix, if $N > C \Omega \ln M$ is violated, then

no stable and robust recovery of $c$ from $D$ and $P$ is possible

$D$ corresponds to $X$, $P$ corresponds to $y$

...as expected from the $N = C \Omega \ln M$ relationship, the selection of the descriptor becomes more unstable, i.e., for different training sets, the selected descriptor often differs...

The second quote is the part that confuses me. It seems to me when the inequality is violated it is not just the solution maybe non-unique(not mentioned), but the descriptor will also become more unstable.

Answer 1

UPDATE

See this second post for McDonald's feedback on my answer where the notion of risk consistency is related to stability.

---

1) Uniqueness vs Stability

Your question is difficult to answer because it mentions two very different topics: uniqueness and stability.

• Intuitively, a solution is unique if given a fixed data set, the algorithm always produces the same results. Martin's answer cover's this point in great detail.

• Stability on the other hand can be intuitively understood as one for which the prediction does not change much when the training data is modified slightly.

Stability applies to your question because Lasso feature selection is (often) performed via Cross Validation, hence the Lasso algorithm is performed on different folds of data and may yield different results each time.

Stability and the No Free Lunch Theorem

Using the definition from here if we define Uniform stability as:

An algorithm has uniform stability $\beta$ with respect to the loss function $V$ if the following holds:

$$\forall S \in Z^m \ \ \forall i \in \{ 1,...,m\}, \ \ \sup | > V(f_s,z) - V(f_{S^{|i},z}) |\ \ \leq \beta$$

Considered as a function of $m$, the term $\beta$ can be written as $\beta_m$. We say the algorithm is stable when $\beta_m$ decreases as $\frac{1}{m}$.

then the "No Free Lunch Theorem, Xu and Caramis (2012)" states that

If an algorithm is sparse, in the sense that it identifies redundant features, then that algorithm is not stable (and the uniform stability bound $\beta$ does not go to zero). [...] If an algorithm is stable, then there is no hope that it will be sparse. (pages 3 and 4)

For instance, $L_2$ regularized regression is stable and does not identify redundant features, while $L_1$ regularized regression (Lasso) is unstable.

An attempt at answering your question

I think 'lasso favors a sparse solution' is not an answer to why use lasso for feature selection

• I disagree, the reason Lasso is used for feature selection is that it yields a sparse solution and can be shown to have the IRF property, i.e. Identifies Redundant Features.

What is the most crucial reason that causes this instability

• The No Free Lunch Theorem

Going further

This is not to say that the combination of Cross Validation and Lasso doesn't work... in fact it has been shown experimentally (and with much supporting theory) to work very well under various conditions. The main keywords here are consistency, risk, oracle inequalities etc..

The following slides and paper by McDonald and Homrighausen (2013) describe some conditions under which Lasso feature selection works well: slides and paper: "The lasso, persistence, and cross-validation, McDonald and Homrighausen (2013)". Tibshirani himself also posted an great set of notes on sparcity, linear regression

The various conditions for consistency and their impact on Lasso is an active topic of research and is definitely not a trivial question. I can point you towards some research papers which are relevant:

• Video lectures on the No free lunch theorem, by Xu
• H.M. Bøvelstad et all, A comparison of feature selection approaches for gene selection, (2007)
• The lasso, persistence, and cross-validation, McDonald and Homrighausen (2013)
• Huang and Bowick, Summary and discussion of: “Stability Selection”
• Lim and Yu, Estimation Stability with Cross Validation, (2015)
• A talk by Peter Buhlmann: Stability Selection for High-Dimensional Data, (2008) and the accompanying paper
• Wang, Nan et all, Random Lasso, (2011)
• Stackexchange post: Model stability when dealing with large $p$, small $n$ problem
• Roberts, Nowakm Stabilizing the lasso against cross-validation variability, (2014) which argue that "percentile-lasso, can result in large reductions in both model-selection instability and model-selection error, compared to the lasso"
• An awesome set of notes by Tibshirani and Wasserman on sparcity, linear regression

Answer 2

Comments from Daniel J. McDonald

Assistant professor at Indiana University Bloomington, author of the two papers mentioned in the original response from Xavier Bourret Sicotte.

Your explanation is, generally, quite correct. A few things I would point out:

1. Our goal in the series of papers about CV and lasso was to prove that "Lasso + Cross Validation (CV)" does as well as "Lasso + optimal $\lambda$". In particular, we wanted to show that the predictions do as well (model-free). In order to make statements about correct recovery of coefficients (finding the right non-sparse ones), one needs to assume a sparse truth, which we didn’t want to do.

2. Algorithmic stability implies risk consistency (first proved by Bousquet and Elisseeff, I believe). By risk consistency, I mean that the $||\hat{f}(X) - f(X)||$ goes to zero where f is either $E[Y|X]$ or the best predictor within some class if the class is misspecified. This is only a sufficient condition however. It is mentioned on the slides you linked to as, essentially, “a possible proof technique that won’t work, since lasso isn’t stable”.

3. Stability is only sufficient but not necessary. We were able to show, that under some conditions, “lasso + CV” predicts as well as “lasso+optimal $\lambda$”. The paper you cite gives the weakest possible assumptions (those on slide 16, which allow $p>n$), but uses the constrained form of lasso rather than the more common Lagrangian version. Another paper (http://www3.stat.sinica.edu.tw/statistica/J27N3/J27N34/J27N34.html) uses the Lagrangian version. It also shows that under much stronger conditions, model selection will also work. A more recent paper (https://arxiv.org/abs/1605.02214) by other people claims to improve on these results (I haven’t read it carefully).

4. In general, because lasso (or any selection algorithm) is not stable, one needs more careful analysis and/or strong assumptions to show that “algorithm+CV” will select the correct model. I’m not aware of necessary conditions, though this would be extremely interesting generally. It’s not too hard to show that for fixed lambda, the lasso predictor is locally Lipschitz in the vector $Y$ (I believe that one or more of Ryan Tibshirani’s papers does this). If one could also argue that this holds true in $X_i$, this would be very interesting, and relevant here.

The main takeaway that I would add to your response: “stability” implies "risk-consistency” or “prediction accuracy”. It can also imply “parameter estimation consistency” under more assumptions. But the no free lunch theorem means “selection” $\rightarrow$ “not stable”. Lasso isn’t stable even with fixed lambda. It’s certainly unstable therefore when combined with CV (of any type). However, despite the lack of stability, it is still risk-consistent and selection consistent with or without CV. Uniqueness is immaterial here.

Answer 3

The Lasso, unlike Ridge regression (see e.g. Hoerl and Kennard, 1970; Hastie et al., 2009) does not always have a unique solution, although it typically has. It depends on the number of parameters in the model, the whether or not the variables are continuous or discrete, and the rank of your design matrix. Conditions for uniqueness can be found in Tibshirani (2013).

References:

Hastie, T., Tibshirani, R., and Friedman, J. (2009). The elements of statistical learning. Springer series in statistics. Springer, New York, 11th printing, 2nd edition.

Hoerl, A. E., and Kennard, R. W. (1970). Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1), 55-67.

Tibshirani, R. J. (2013). The lasso problem and uniqueness. Electronic Journal of Statistics, 7, 1456-1490.

Answer 4

What causes non-uniqueness.

For the vectors $s_ix_i$ (where $s_i$ is a sign denoting whether the change of $c_i$ will increase or decrease $\Vert c \Vert_1$), whenever they are affinely dependent :

$$\sum \alpha_i s_i x_i = 0 \qquad \text{and} \qquad \sum \alpha_i =0$$

then there are an infinite number of combinations $c_i + \gamma\alpha_i$ that do not change the solution $Xc$ and the norm $\Vert c\Vert_1$.

For example:

$$y = \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix}= Xc $$

has for $\Vert c \Vert_1 = 1$ the solutions:

$$\begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix}= \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} + \gamma \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix} $$

with $0\leq \gamma \leq \frac{1}{2}$

We can sort of replace the vector $x_2$ by using $x_2 = 0.5 x_1 + 0.5 x_3 $

---

Situations without this condition

In the article from Tibshirani (from Phil's answer) three sufficient conditions are described for lasso to have an unique solution.

1. Linearly independent When the null space $X$ is null or equivalently when the rank of $X$ is equal to the number of columns (M). In that case you do not have linear combinations like above.

2. Affinely independent When the columns $Xs$ are in general position.

   That is, no $k$ columns represent points in a $k-2$ dimensional plane. A k-2 dimensional plane can be parameterized by any $k-1$ points as $\sum \alpha_i s_ix_i$ with $\sum \alpha_i = 1$. With a $k$-th point $s_jx_j$ in this same plane you would have the conditions $\sum \alpha_i s_ix_i$ with $\sum \alpha_i = 0$

   Note that in the example the columns $x_1$, $x_2$ and $x_3$ are on a single line. (It is however a bit awkward here because the signs can be negative, e.g. the matrix $\left[ [2 \, 1] \, [1 \, 1] \, [-0 \, -1] \right]$ has just as well no unique solution)

3. When the columns $X$ are from a continuous distribution then it is unlikely (probability almost zero) that you will have columns of $X$ not in general position.

   Contrasting with this, if the columns $X$ are a categorical variable then this probability is not neccesarily almost zero. The probability for a continuous variable to be equal to some set of numbers (ie the planes corresponding to the affine span of the other vectors) is 'almost' zero. But, this is not the case for discrete variables.