8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I've included the latex typesetting for you (and also included some minor clarification details). Do let me know if I have accidentally changed the meaning of your question $\endgroup$
    – jcken
    Jul 21, 2022 at 11:49
  • $\begingroup$ Thank you for your changes; the meaning of my question remains intact. I got rid of the strikethrough marks too to make it look neater. $\endgroup$
    – Dan
    Jul 21, 2022 at 11:55

2 Answers 2

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you for your reply! I do have one question however. In answer no 1, you said, "for every 𝜆, there is one 𝑠 such that the minimizer 𝛽 of (6.7) for 𝜆 is equal to the minimizer of (6.8)". Why is that particular s value of interest? $\endgroup$
    – Dan
    Jul 21, 2022 at 13:10
  • 1
    $\begingroup$ I don't think it's of much interest in itself. If you look at the original Tibshirani (1996) paper, the lasso is actually introduced by an analogue of equation (6.8), and this of course motivates the term "lasso": the coefficients are constrained in a hard way (through their 1-norm), not in a soft way (per 6.7, where coefficient size can be traded off against model fit). I think the (nowadays more common) formulation (6.7) simply came later. $\endgroup$ Jul 21, 2022 at 13:21
  • 1
    $\begingroup$ We can use the KKT conditions (Lagrange multiplier optimality conditions) from convex optimization to show that a minimizer for problem 2 (which has a hard constraint) is also a minimizer for problem 1, for a certain value of $\lambda$. The parameter $\lambda$ is a Lagrange multiplier. $\endgroup$
    – littleO
    Jul 26, 2022 at 19:52
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Nice, thank you! I was not aware of this relationship. $\endgroup$ Jul 22, 2022 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.