Why is Lasso penalty equivalent to the double exponential (Laplace) prior?

I have read in a number of references that the Lasso estimate for the regression parameter vector $B$ is equivalent to the posterior mode of $B$ in which the prior distribution for each $B_i$ is a double exponential distribution (also known as Laplace distribution).

I have been trying to prove this, can someone flesh out the details?

• @user777 I was thumbing through that book for a while today. Could not find anything relevant. Nov 17 '15 at 1:29
• – Tim
Nov 17 '15 at 8:12

For simplicity let's just consider a single observation of a variable $Y$ such that $$Y|\mu, \sigma^2 \sim N(\mu, \sigma^2),$$

$\mu \sim \mbox{Laplace}(\lambda)$ and the improper prior $f(\sigma) \propto \mathbb{1}_{\sigma>0}$.

Then the joint density of $Y, \mu, \sigma^2$ is proportional to $$f(Y, \mu, \sigma^2 | \lambda) \propto \frac{1}{\sigma}\exp \left(-\frac{(y-\mu)^2}{\sigma^2} \right) \times 2\lambda e^{-\lambda \vert \mu \vert}.$$

Taking a log and discarding terms that do not involve $\mu$, $$\log f(Y, \mu, \sigma^2) = -\frac{1}{\sigma^2} \Vert y-\mu\Vert_2^2 -\lambda \vert \mu \vert. \quad (1)$$

Thus the maximum of (1) will be a MAP estimate and is indeed the Lasso problem after we reparametrize $\tilde \lambda = \lambda \sigma^2$.

The extension to regression is clear--replace $\mu$ with $X\beta$ in the Normal likelihood, and set the prior on $\beta$ to be a sequence of independent laplace$(\lambda)$ distributions.

This is obvious by inspection of the quantity the LASSO is optimizing.

Take the prior for $\beta_i$ to be independent Laplace with mean zero and some scale $\tau$.

So $p(\beta|\tau) \propto e^{-\frac{1}{2\tau} \sum_i|\beta_i|}$.

The model for the data is the usual regression assumption $y \stackrel{\text{iid}}{\sim}N(X\beta,\sigma^2)$.

$f(\mathbf{y}|\mathbf{X},\boldsymbol\beta,\sigma^{2}) \propto (\sigma^{2})^{-n/2} \exp\left(-\frac{1}{2{\sigma}^{2}}(\mathbf{y}- \mathbf{X} \boldsymbol\beta)^{\rm T}(\mathbf{y}- \mathbf{X} \boldsymbol\beta)\right)$

Now minus twice the log of the posterior is of the form

$k(\sigma^2,\tau,n,p)+$ $\frac{1}{{\sigma}^{2}} (\mathbf{y}- \mathbf{X} \boldsymbol\beta)^{\rm T}(\mathbf{y}- \mathbf{X} \boldsymbol\beta)+ \frac{1}{\tau} \sum_i|\beta_i|$

Let $\lambda=\sigma^2/\tau$ and we get $-2\log$-posterior of

$k(\sigma^2,\lambda,n,p)+$ $\frac{1}{{\sigma}^{2}}\left[ (\mathbf{y}- \mathbf{X} \boldsymbol\beta)^{\rm T}(\mathbf{y}- \mathbf{X} \boldsymbol\beta)+ \lambda \sum_i|\beta_i|\right]$

The MAP estimator for $\beta$ minimizes the above, which minimizes

$S=(\mathbf{y}- \mathbf{X} \boldsymbol\beta)^{\rm T}(\mathbf{y}- \mathbf{X} \boldsymbol\beta)+ \lambda \sum_i|\beta_i|$

So the MAP estimator for $\beta$ is LASSO.

(Here I treated $\sigma^2$ as effectively fixed but you can do other things with it and still get LASSO coming out.)

Edit: That's what I get for composing an answer off line; I didn't see a good answer was already posted by Andrew. Mine really doesn't do anything his doesn't do already. I'll leave mine for now because it gives a couple more details of the development in terms of $\beta$.

• There seems to be a difference in your answer and Andrew's. Your answer has the correct form of the regularizer: $\lambda \|\beta\|_1$, whereas Andrew has $\lambda |\mu|$, where in linear regression, we get $\mu=X\beta$. Nov 20 '15 at 18:47
• @AlexR I think you're misinterpreting the μ in Andrew's answer. The μ there corresponds to a $\beta_0$ in a regression with only an intercept, not to $X\beta$ in a multiple regression; the same argument follows for the larger case (note the parallels with my answer) but it's easier to follow in the simple case. Andrew's answer is essentially right but doesn't connect all the dots to the original question, leaving a small amount for the reader to fill in. I think our answers are consistent (up to some minor differences relating to σ that can be accounted for) and that he fully deserved the tick Nov 20 '15 at 22:53