# What causes lasso to be unstable for feature selection?

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.

• Just for the context, the optimization problem you write down in the beginning of your Q is called "basis pursuit". If you replace equality $y=Xc$ by approximate equality $y\approx Xc$ (up to some L2 error) then it's called "basis pursuit denoising". Basis pursuit denoising is mathematically equivalent to lasso. – amoeba says Reinstate Monica Sep 11 '18 at 12:01
• A useful set of slides (but not an easy one) found here: pages.iu.edu/~dajmcdon/research/talks/lasso.pdf and the no free lunch theorem users.ece.utexas.edu/~cmcaram/pubs/XuCaramanisMannor.NFL.pdf – Xavier Bourret Sicotte Sep 11 '18 at 14:32
• The Theorem that you cite is about uniqueness. Your question is confusing because uniqueness is not necessarily related to stability. – amoeba says Reinstate Monica Sep 11 '18 at 14:40
• Yes i believe the OP is somewhat confused and the question not clear, hence the different possible answers... Uniqueness is for a single set of data points, stability applies for cross validation, or bootstrap, or new data points – Xavier Bourret Sicotte Sep 11 '18 at 14:42

## 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.

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:

• Thank you for your comprehensive answer! The set of slides you provide is just excellent! – meTchaikovsky Sep 12 '18 at 4:36
• I am still trying to process this definition of stability. My translation is that "an algorithm is stable if the change of the error/loss-function in leave one out cross-validation has an upper bound $\beta$ that decreases as $\frac{1}{m}$" when we increase the number of folds/test-sets", I hope I got that correct. I wonder why it is a desirable property in order to make lasso work well (or more precisely I wonder whether it is a necessary property). – Sextus Empiricus Sep 12 '18 at 10:56
• Yes, except m is the number of data points. look here page 7 for a probabilistic bound: math.arizona.edu/~hzhang/math574m/Read/LOOtheory.pdf – the point is that there is no bound on tability provided by increasing the data set size, which means the algorithm can jump to far away hypothesis functions depending on a particular data set. This is why alternative conditions are proposed, which relate to the underlying distribution and correlation structure (i think) - but would need help making those clearer – Xavier Bourret Sicotte Sep 12 '18 at 11:43
• Another important notion is that of consistency as explained here for example: stat.ethz.ch/~nicolai/stability.pdf - how stability and consistency are linked is unclear but seems to be subject of active research e.g. cbcl.mit.edu/publications/ps/mukherjee-AImemoOctNov.pdf – Xavier Bourret Sicotte Sep 12 '18 at 12:12
• Nice answer! Could you also update some links with more detailed descriptions in case the links themselves go dead in the future? (I did one for you already.) – Richard Hardy Sep 12 '18 at 14:35

# 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.

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.

• @ Thank you! Can you add a brief summary of those references that you provide? – meTchaikovsky Sep 10 '18 at 13:43
• Hasite et al. (2009) is book that covers a lot of topics, Lasso and Ridge regression among them. It's well worth a read and can be downloaded from Hastie's homepage: web.stanford.edu/~hastie/ElemStatLearn/download.html Hoerl & Kennard (1970) is a classic Ridge regression reference and likely not that relevant for your question directly, other than to read about Ridge Regression. Tibshirani (2013) contains information about when the Lasso has an unique solution (and when it has an infinite amount of solutions). – Phil Sep 10 '18 at 14:34

### 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.

• +1 but i think that what is meant by unstable in recent discussions is related to feature selection via cross validation in presence of correlated features – Xavier Bourret Sicotte Sep 11 '18 at 13:54
• @XavierBourretSicotte do you mean that even when there is a unique solution the selection process can be unstable due to correlated features adding troubles to (numerically) finding that unique solution? It is a bit confusing because the question asks on the one hand about stability and on the other hand about uniqueness. – Sextus Empiricus Sep 11 '18 at 14:05
• Yes that is what I mean, not necessarily because of numerical instability but because of inherent differences in the folds of the data (during CV) which lead to different solutions for different $\lambda$ values across the folds. In could be even worse when bootstrapping – Xavier Bourret Sicotte Sep 11 '18 at 14:10
• @XavierBourretSicotte I have currently no clear intuitive picture why this (different solutions for different $\lambda$ and training sets) is supposed to be unstable. I guess you could post this as an answer and explain it. – Sextus Empiricus Sep 11 '18 at 14:15
• @Martijn Weterings Thank you! I still have three questions: 1. how do I detect affinely dependency? Should I find out whether $\{v_1 - v_0, v_2 - v_0, \cdots, v_k - v_0\}$ are independent (math.stackexchange.com/q/82189)? 2. how should I determine $s_i$ in practice? 3. what does it mean of a 'general position' of $X$? – meTchaikovsky Sep 12 '18 at 4:36