# Continuous process vs Discrete process!

I encountered two statements in Tibshirani's article Regression Shrinkage and Selection via the Lasso, p.58 (pdf). 1. Subset selection is a "discrete process" which leads to unstable coefficients.
2. ridge regression is a "continuous process" leading to stable coefficients.

My question is, why ridge is called continuous process while subset selection is a discrete process. Also, why ridge leads to stability and the Subset selection to instability.

• 1. Do you have a particular book or something that says this? It might be useful to answerers to have context. 2. Are you asking "what makes it discrete or continuous?" or are you asking "why would subset selection be unstable while ridge regression is stable?" or are you asking "why would discreteness/continuity be described as stable or unstable?" – Glen_b Jul 25 '16 at 1:54
• @ Glen_b, my question is why ridge is called continuous process, and subset selection is discrete process, and why the first one leads to stability and the later to instability. – jeza Jul 25 '16 at 2:03
• You still need to provide some context / a quote. – gung Jul 25 '16 at 17:33
• @ gung, now, it is ok – jeza Jul 25 '16 at 18:42
• Selecting a subset of variables is a binary decision and in that sense discrete. Ridge regression, on the other hand, performs regularization by putting stronger emphasis on certain variables (without merely making the decision to include or remove them) as a result of a modified residual term. A more precise explanation can be found in Wikipedia. – Igor Jul 25 '16 at 21:18

## 1 Answer

Both subset selection and ridge regression are methods to estimate the coefficients of a linear model.

For subset selection, in its most general form, you pick some metric to optimize and try all possible subsets of variables to include in your linear regression model. Suppose you have $p$ covariates, then there are $2^p$ models, i.e. there are $2^p$ vectors $\beta$ to choose from. Hence, jumping from model to model is a discrete process. You cannot "interpolate" between models.

For ridge regression, you add an $l_2$ penalty to the coefficients, so that the model you choose is $$\min_\beta \| X\beta - y\|^2 + \frac{\lambda}{2}\|\beta\|^2$$ In this case, for any $\lambda \ge 0$ you get a different model (that is solution of $\beta(\lambda)$). In fact, $\beta$ will be a smooth function of $\lambda$: change $\lambda$ a little bit, and your fitted $\beta$ will change a little bit. Hence, there are an infinite number of possible models. Thus, this is a continuous process and you can smoothly go from one model to the other by changing $\lambda$.

This is also the reason why subset selection is unstable, and ridge regression is stable. Suppose you change the metric you use to fit the subset selection process a little bit, and you can end up with a very different model (here with different model I mean what elements of $\beta$ are non-zero). As I noted above, this is not true for ridge regression; a small change in $\lambda$ leads to a small change in $\beta$.

Also worth noting that in general all coefficients in Ridge regression are non-zero for all values of $\lambda$, but they converge monotonically to $0$ as $\lambda \to \infty$.