Lasso regression Mathematical intuition

Question

I do not fully understand lasso regression. I am able to code a LASSO regression model of the form $y = \beta_0 + \beta_1 x_1 + \ldots \beta_p x_p$ with sklearn, but I do not understand the Mathematical intuition behind the model, which I believe is important. In ISLR (Introduction to Statistical Learning in R), it is explained that the equation for the model coefficients in lasso regression is $$\hat{\beta} = \text{argmin}_{\beta \in \mathbb{R}^{p+1}}\left(RSS + \lambda \sum_{i=1}^p|\beta_i|\right)$$ and $RSS = \sum_{j = 1}^n(y_j - \hat{y}_j)^2$ is the residual sum of squares. So, although I do not understand where exactly the hyperparameter comes from or what its actual purpose is, I do understand that the algorithm seeks to minimise that equation and reduce overfitting by introducing a little bias into the training fit.

However, it is shown later that the lasso regression equation can be rewritten as $$\hat{\beta} = \text{arg min}_{\beta \in \mathbb{R}^{p+1}} (RSS) \text{ subject to } \sum_{i = 1}^p |\beta_i| \leq s$$

which is where my confusion lies. Firstly, how can the original lasso regression equation be rewritten as that? Also, what is this s term? I get that it means sum, but I do not understand what sum this equation refers to or why it has to be less than or equal to the sum of the absolute beta values.

Answer 1

You have three different questions. Let's tackle them in a somewhat different order. I'll refer to ISLR 2nd edition.

First off, here are the two different formulations of the lasso:

$$ \text{minimize } ||\mathbf{y}-\mathbf{X}\mathbf{\beta}||_2+\lambda||\mathbf{\beta}||_1\text{ with respect to }\mathbf{\beta}\text{ for a given }\lambda\geq 0 \quad (6.7)$$ and $$ \text{minimize } ||\mathbf{y}-\mathbf{X}\mathbf{\beta}||_2\text{ with respect to }\mathbf{\beta}\text{ subject to }||\mathbf{\beta}||_1\leq s\text{ for a given }s\geq0\quad (6.8) $$

The 2-norm $||\cdot||_2$ of a vector is the sum of squared entries, the 1-norm $||\cdot||_1$ is the sum of absolute entries.

On to your questions:

1. How do $\lambda$ and $s$ hang together?

   There is a one-to-one relationship between the two, in the following sense: for every $\lambda$, there is one $s$ such that the minimizer $\mathbf{\beta}$ of (6.7) for $\lambda$ is equal to the minimizer of (6.8). And vice versa. (Note that the relationship is not unique, see below.)

   One interesting boundary case is that $\lambda=0$ (no lasso penalty), which leads to the OLS estimate of $\mathbf{\beta}$ (assuming your design matrix $\mathbf{X}$ is of full rank), corresponds to $s=\infty$ (no constraint on the parameter estimates). If you are uncomfortable with $s=\infty$, just take $s$ to be any number larger than the 1-norm of the OLS estimate of $\mathbf{\beta}$.

2. Why are the two formulations equivalent?

   This derivation is usually not given in standard statistics/data science textbooks. Most people just accept this fact. I don't think it is formally proven even in the original lasso paper by Tibshirani (1996), but it does not seem to be very hard. Starting with (6.7), pick a $\lambda$, find the optimal $\mathbf{\beta}$ in (6.7), use the 1-norm of this estimate for $s$ in (6.8) and argue that you won't find a better solution to (6.8) with smaller 1-norm. And vice versa. A rigorous proof would probably be a nice exercise for an undergraduate math student.

3. How do we choose $\lambda$ (or equivalently $s$)?

   The algorithm usually used to fit a lasso model will give you an entire sequence of parameter coefficient vectors, one for each one of multiple values of $\lambda$ (e.g., Figure 6.6 in ISLR). You can then choose one. This is often done via cross-validation using some accuracy measure, and in fact, your software may already perform this cross-validation internally and just report the optimal $\lambda$.

Answer 2

The other answer here covers the specific transformation issues you have asked about, so I'll focus solely on the intuition of the LASSO regression. One useful way to look at LASSO regression is that it is equivalent to Bayesian maximum-posterior (MAP) estimation when you use an IID Laplace prior for the coefficient vector. This prior has density given by:

$$\pi(\boldsymbol{\beta}|\lambda) = \prod_{i=1}^p \text{Laplace} \Big( \beta_i \Big| 0, \frac{2}{\lambda} \Big) = \prod_{i=1}^p \frac{\lambda}{4} \cdot \exp \bigg( -\frac{\lambda}{2} |\beta_i| \bigg),$$

Taking $\text{RSS}_{\mathbf{x}, \mathbf{y}}(\boldsymbol{\beta})$ as the residual-sum-of-squares (taken as a function of the coefficient vector), the log-likelihood for the regression model is:

$$\ell_{\mathbf{x}, \mathbf{y}}(\boldsymbol{\beta}) = \text{const} - \frac{1}{2} \cdot \text{RSS}_{\mathbf{x}, \mathbf{y}}(\boldsymbol{\beta}).$$

Consequently, the MAP estimator is is the argument that maximises the log-posterior for the model, which is:

$$\begin{align} \hat{\boldsymbol{\beta}}_\text{MAP} &= \underset{\boldsymbol{\beta}}{\text{arg max}} \log p(\boldsymbol{\beta}|\mathbf{x}, \mathbf{y}, \lambda) \\[6pt] &= \underset{\boldsymbol{\beta}}{\text{arg max}} \bigg[ \ell_{\mathbf{x}, \mathbf{y}}(\boldsymbol{\beta}) + \log \pi(\boldsymbol{\beta}|\lambda) \bigg] \\[6pt] &= \underset{\boldsymbol{\beta}}{\text{arg max}} \bigg[ \text{const} - \frac{1}{2} \cdot \text{RSS}_{\mathbf{x}, \mathbf{y}}(\boldsymbol{\beta}) - \frac{\lambda}{2} \sum_{i=1}^p |\beta_i| \bigg] \\[6pt] &= \underset{\boldsymbol{\beta}}{\text{arg max}} \bigg[ - \frac{1}{2} \cdot \text{RSS}_{\mathbf{x}, \mathbf{y}}(\boldsymbol{\beta}) - \frac{\lambda}{2} \sum_{i=1}^p |\beta_i| \bigg] \\[6pt] &= \underset{\boldsymbol{\beta}}{\text{arg min}} \bigg[ \text{RSS}_{\mathbf{x}, \mathbf{y}}(\boldsymbol{\beta}) + \lambda \sum_{i=1}^p |\beta_i| \bigg] \\[6pt] \end{align}$$

If you have a look at the Laplace distribution you will see that, in this case, it gives a density with a peak at $\beta_i=0$ and with exponential decay in prior density as we move away from this point in either direction. The estimator above is the one that maximises the posterior density under this prior. You can read more about this in this related question.