Understanding the difference between Ridge and LASSO

Question

I'll start by presenting my current understanding of regularized loss minimization.

In the context of ML, generally we are trying to minimize directly an empirical loss, something of the form $$\underset{h\in\mathcal{H}}{\arg\min}\sum_{i=1}^{m}L\left(y_{i},h\left(x_{i}\right)\right)$$

where there are $m$ samples $x_{1},\ldots,x_{m}$ labeled by $y_{1},\ldots,y_{m}$ and $L$ is some loss function.

In regularized loss minimization we are trying to minimize $$\underset{h\in\mathcal{H}}{\arg\min}\sum_{i=1}^{m}L\left(y_{i},h\left(x_{i}\right)\right)+\lambda\mathcal{R}\left(h\right)$$

where $\mathcal{R}:\mathcal{H}\to\mathbb{R}$ is some regularizer, which penalizes a hypothesis $h$ for it's complexity, and $\lambda$ is a parameter controlling the severity of this penalty.

In the context of linear regression, where in general we'd like to minimize $$\underset{\vec{w}\in\mathbb{R}^{d}}{\arg\min}\left\Vert \vec{y}-X^{T}\vec{w}\right\Vert _{2}^{2}$$

with ridge regularization we add the regularizer $\left\Vert \vec{w}\right\Vert _{2}^{2}$ to obtain $$\left\Vert \vec{y}-X^{T}\vec{w}\right\Vert _{2}^{2}+\lambda\left\Vert \vec{w}\right\Vert _{2}^{2}$$ And with LASSO, we use $$\left\Vert \vec{y}-X^{T}\vec{w}\right\Vert _{2}^{2}+\lambda\left\Vert \vec{w}\right\Vert _{1}$$

The LASSO solution is supposed to result in a sparse solution vector $\vec{w}$ rather then one with small entries, as is expected to happen in Ridge.

As an explanation for this last statement, I've seen the following (From "Elements of Statistical Learning"):

The ellipses are the contours of the least squares loss function and the blue shapes are the respective norm balls. The explanation (from my lecture notes)

“Since the $\ell_{1}$ ball has corners on the main axes, it is “more likely” that the Lasso solution will occur on a sparse vector”

So my questions are

1. Why is solving these problems equivalent to finding a point on the smallest possible contour that intersects the respective norm ball?

2. Why is it more likely that this will happen on a “corner” for the $\ell_{1}$ norm?

Answer 1

I think it's more clear to first consider the optimization problem \begin{align} \text{minimize} &\quad \| w \|_1 \\ \text{subject to } &\quad \| y - X^T w \| \leq \delta. \end{align} The red curves in your picture are level curves of the function $\|y-X^T w\|$ and the outermost red curve is $\|y-X^Tx\|=\delta$. We imagine shrinking the $\ell_1$-norm ball (shown in blue) until it is as small as possible while still intersecting the constraint set. You can see in the 2D case it appears to be very likely that the point of intersection will be one of the corners of the $\ell_1$-norm ball. So the solution to this optimization problem is likely to be sparse.

We can use Lagrange multipliers to replace the constraint $\|y- X^Tw\| \leq \delta$ with a penalty term in the objective function. There exists a Lagrange multiplier $\lambda \geq 0$ such that any minimizer for the problem I wrote above is also a minimizer for the problem $$ \text{minimize} \quad \lambda (\| y-X^Tw\|-\delta) + \|w\|_1. $$ But this is equivalent to a standard Lasso problem. So, solutions to a Lasso problem are likely to be sparse.

Answer 2

1. The unit ball is here as an example, it is not a generality. But the shape of the unit ball is important. Since we penalize to avoid $\vec{w}$ having a large norm, we will keep, amongst the $\vec{w}$ on the same contour, the one with the smallest norm.

2. Knowing that, from one contour, we take the point with the smallest norm, can you imagine a case where, on the first drawing, you have $\beta_1$ and $\beta_2$ different from $0$ at the same time ? Conversely, try to imagine a situation where $\beta_1$ and $\beta_2$ are different to $0$ for the second drawing. Which situation seems to be the more frequent ?

Answer 3

1. Why is solving these problems equivalent to finding a point on the smallest possible contour that intersects the respective unit ball?

You can apply basic tools from multivariate calculus to show it. Let us take the Ridge regression. You want to minimize the following sum of squares $$ \sum ( y_i-w_0-w_1x_i)^2, $$
subject to $\|w\|_2^2 \le k$, namely your restriction is $\|w\|_2^2 =w_0^2+w_1^2 \le k$, that is a circle with radius $k > 0$ and its interior. Now, you can use Lagrange multiplier(s) to solve this problem, namely minimize $$ \sum ( y_i-w_0-w_1x_i)^2 - \lambda(w_0^2 + w_1^2 - k), $$ as $k$ is independent of the weights $w_i$ you can write
$$ \sum ( y_i-w_0-w_1x_i)^2 - \lambda(w_0^2 + w_1^2 ), $$ or in a fancy way $$ \|y - X'w\|_2^2 - \lambda \| w\|_2^2. $$ Note that this formulation basically assumes that the minima of $\|y - X'w\|$ lies outside the circle, hence the resulted weights will be biased downwards w.r.t. the unconstrained weights. Other implication of the method is the fact that you will always have unique non-entirely zero solution. Namely, even if the true minima is $(0,0)$ or there are infinitely many vectors, e.g., $(w_0, kw_0)$, that solve the unconstrained problem, thanks to the $l_2$-norm constrain you will will always get a unique non-zero solution.

2. Why is it more likely that this will happen on an “edge” for the ℓ1 norm? Nothing special happens for $l_1$. Same logic/geometry holds for any $l_p$, $0 < p\le 1$.

Intuitively - draw that contours and unit circles for different $p$s, $p\in (0, \infty)$. You can see geometrically that the "convex" shape of $l_p$, $p\le 1$ unit circles, induce "sparse" solutions such that the tangent point of the contours and the unit circle is more likely to be at one of the edges as $p$ gets smaller, and vice versa - for $p = \infty$ you will almost never get a sparse solution.