# Why is Laplace prior producing sparse solutions?

I was looking through the literature on regularization, and often see paragraphs that links L2 regulatization with Gaussian prior, and L1 with Laplace centered on zero.

I know how these priors look like, but I don't understand, how it translates to, for example, weights in linear model. In L1, if I understand correctly, we expect sparse solutions, i.e. some weights will be pushed to exactly zero. And in L2 we get small weights but not zero weights.

But why does it happen?

• – amoeba says Reinstate Monica Nov 20 '15 at 17:48
• A really simple intuitive explanation is that the penalty decreases when using an L2 norm but not when using an L1 norm. So if you can keep the model part of the loss function about equal and you can do so by decreasing one of two variables it's better to decrease the variable with a high absolute value in the L2 case but not in the L1 case. – testuser Aug 12 '16 at 0:05

The relation of Laplace distribution prior with median (or L1 norm) was found by Laplace himself, who found that using such prior you estimate median rather than mean as with Normal distribution (see Stingler, 1986 or Wikipedia). This means that regression with Laplace errors distribution estimates the median (like e.g. quantile regression), while Normal errors refer to OLS estimate.

The robust priors you asked about were described also by Tibshirani (1996) who noticed that robust Lasso regression in Bayesian setting is equivalent to using Laplace prior. Such prior for coefficients are centered around zero (with centered variables) and has wide tails - so most regression coefficients estimated using it end up being exactly zero. This is clear if you look closely at the picture below, Laplace distribution has a peak around zero (there is a greater distribution mass), while Normal distribution is more diffuse around zero, so non-zero values have greater probability mass. Other possibilities for robust priors are Cauchy or $t$- distributions.

Using such priors you are more prone to end up with many zero-valued coefficients, some moderate-sized and some large-sized (long tail), while with Normal prior you get more moderate-sized coefficients that are rather not exactly zero, but also not that far from zero.

(image source Tibshirani, 1996)

Stigler, S.M. (1986). The History of Statistics: The Measurement of Uncertainty Before 1900. Cambridge, MA: Belknap Press of Harvard University Press.

Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), 267-288.

Gelman, A., Jakulin, A., Pittau, G.M., and Su, Y.-S. (2008). A weakly informative default prior distribution for logistic and other regression models. The Annals of Applied Statistics, 2(4), 1360-1383.

Norton, R.M. (1984). The Double Exponential Distribution: Using Calculus to Find a Maximum Likelihood Estimator. The American Statistician, 38(2): 135-136.

• Wow, this is very good explanation, and also special thanks for linked question where the regularization norms are intuitively linked to mode, meadian and mean, this really clarifies a lot for me! – Dmitry Smirnov Oct 16 '15 at 11:09
• @Tim, The Cauchy Distribution has Heavy Tail yet the probability for Zero is less than the Normal Distribution. So how come it induce sparse solution? – Royi Nov 9 '16 at 11:41

# Frequentist view 👀

In one sense, we can think of both regularizations as "shrinking the weights"; L2 minimizes the Euclidean norm of the weights, while L1 minimizes the Manhattan norm. Following this line of thinking, we can reason that the equipotentials of L1 and L2 are spherical and diamond-shaped respectively, so L1 is more likely to lead to sparse solutions, as illustrated in Bishop's Pattern Recognition and Machine Learning:

# Bayesian view 👀

However, in order to understand how priors relate to the linear model, we need to understand the Bayesian interpretation of ordinary linear regression. Katherine Bailey's blogpost is an excellent read for this. In a nutshell, we assume normally-distributed i.i.d. errors in our linear model

$$\mathbf{y} = \mathbf{\theta}^\top\mathbf{X} + \mathbf\epsilon$$

i.e. each of our $$N$$ measurements $$y_i, i = 1, 2, \ldots, N$$ have a noise $$\epsilon_k\sim \mathcal{N}(0,\sigma)$$.

Then we can say that our linear model has a Gaussian likelihood too! The likelihood of $$\mathbf{y}$$ is $$$$p(\mathbf{y}|\mathbf{X}, \mathbf{\theta}; \mathbf{\epsilon}) = \mathcal{N}(\mathbf{\theta}^\top\mathbf{X}, \mathbf{\sigma})$$$$

As it turns out... The maximum likelihood estimator is identical to minimizing the squared error between predicted and actual output values under the normality assumption for the error.

\begin{align*} {\bf \hat{\theta}_{\text{MLE}}} &= \arg\max_{\bf \theta} \log P(y | \theta) \\ &=\underset{\theta}{\arg\min} \sum_{i=1}^n(y_i - \theta^\top{\mathbf{x}_i})^2 \end{align*}

## Regularization as putting priors on weights

If we were to place a non-uniform prior on the weights of linear regression, the maximum a posteriori probability (MAP) estimate would be:

$$\begin{equation*} {\bf \hat{\theta}_{\text{MAP}}} = \arg\max_{\bf \theta} \log P(y | \theta) + \log P(\theta) \end{equation*}$$

As derived in Brian Keng's blogpost, if $$P(\theta)$$ is a Laplace distribution it's equivalent to L1 regularization on $$\theta$$.

Similarly, if $$P(\theta)$$ is a Gaussian distribution, it's equivalent to L2 regularization on $$\theta$$.

Now we have another view into why putting a Laplace prior on the weights is more likely to induce sparsity: because the Laplace distribution is more concentrated around zero, our weights are more likely to be zero.