# Why L1 norm for sparse models

I am reading the books about linear regression. There are some sentences about the L1 and L2 norm. I know them, just don't understand why L1 norm for sparse models. Can someone use give a simple explanation?

• Basically, sparsity is induced by sharp edges lying on the axis of an isosurface. The best graphical explanation I've found so far is in this video: youtube.com/watch?v=sO4ZirJh9ds – felipeduque Jun 30 '15 at 12:24
• There a blog article on the same chioka.in/… – prashanth May 12 '17 at 11:19
• Check the following post of Medium. It might help medium.com/@vamsi149/… – solver149 Aug 30 '18 at 6:11

Consider the vector $\vec{x}=(1,\varepsilon)\in\mathbb{R}^2$ where $\varepsilon>0$ is small. The $l_1$ and $l_2$ norms of $\vec{x}$, respectively, are given by

$$||\vec{x}||_1 = 1+\varepsilon,\ \ ||\vec{x}||_2^2 = 1+\varepsilon^2$$

Now say that, as part of some regularization procedure, we are going to reduce the magnitude of one of the elements of $\vec{x}$ by $\delta\leq\varepsilon$. If we change $x_1$ to $1-\delta$, the resulting norms are

$$||\vec{x}-(\delta,0)||_1 = 1-\delta+\varepsilon,\ \ ||\vec{x}-(\delta,0)||_2^2 = 1-2\delta+\delta^2+\varepsilon^2$$

On the other hand, reducing $x_2$ by $\delta$ gives norms

$$||\vec{x}-(0,\delta)||_1 = 1-\delta+\varepsilon,\ \ ||\vec{x}-(0,\delta)||_2^2 = 1-2\varepsilon\delta+\delta^2+\varepsilon^2$$

The thing to notice here is that, for an $l_2$ penalty, regularizing the larger term $x_1$ results in a much greater reduction in norm than doing so to the smaller term $x_2\approx 0$. For the $l_1$ penalty, however, the reduction is the same. Thus, when penalizing a model using the $l_2$ norm, it is highly unlikely that anything will ever be set to zero, since the reduction in $l_2$ norm going from $\varepsilon$ to $0$ is almost nonexistent when $\varepsilon$ is small. On the other hand, the reduction in $l_1$ norm is always equal to $\delta$, regardless of the quantity being penalized.

Another way to think of it: it's not so much that $l_1$ penalties encourage sparsity, but that $l_2$ penalties in some sense discourage sparsity by yielding diminishing returns as elements are moved closer to zero.

• Thanks for your answer! I'm not convinced by the last point, though. If you run un-penalized linear regression, you will hardly ever get sparse solutions (whereas adding an L1 penalty will often give you sparsity). So L1 penalties do in fact encourage sparsity by sending coefficients that start off close to zero to zero exactly. – Stefan Wager Feb 20 '14 at 21:27
• @StefanWager maybe it's a bit of an overstatement, but I do think it's true that there's nothing special about the $l_1$ penalty here: an $l_\alpha$ penalty for any $\alpha\leq1$ will also induce sparsity, but you see those less often in practice (probably because they're non-convex). If you really just want sparsity then an $l_0$ penalty (proportional to the number of non-zero entries) is the way to go, it just so happens that it's a bit of a nightmare to work with. – bnaul Feb 20 '14 at 21:50
• Yes - that's correct. There are many norms that lead to sparsity (e.g., as you mentioned, any Lp norm with p <= 1). In general, any norm with a sharp corner at zero induces sparsity. So, going back to the original question - the L1 norm induces sparsity by having a discontinuous gradient at zero (and any other penalty with this property will do so too). – Stefan Wager Feb 23 '14 at 2:55
• In case anyone wants to read more, there's an active literature about non-convex penalty functions that are alternatives to the L1 norm (e.g., recently, papers.nips.cc/paper/…). – Stefan Wager Feb 23 '14 at 2:58
• great answer i've been wondering around for a while until i found this. – Hady Elsahar Jan 16 '15 at 20:33

With a sparse model, we think of a model where many of the weights are 0. Let us therefore reason about how L1-regularization is more likely to create 0-weights.

Consider a model consisting of the weights $(w_1, w_2, \dots, w_m)$.

With L1 regularization, you penalize the model by a loss function $L_1(w)$ = $\Sigma_i |w_i|$.

With L2-regularization, you penalize the model by a loss function $L_2(w)$ = $\frac{1}{2} \Sigma_i w_i^2$

If using gradient descent, you will iteratively make the weights change in the opposite direction of the gradient with a step size $\eta$ multiplied with the gradient. This means that a more steep gradient will make us take a larger step, while a more flat gradient will make us take a smaller step. Let us look at the gradients (subgradient in case of L1):

$\frac{dL_1(w)}{dw} = sign(w)$, where $sign(w) = (\frac{w_1}{|w_1|}, \frac{w_2}{|w_2|}, \dots, \frac{w_m}{|w_m|})$

$\frac{dL_2(w)}{dw} = w$

If we plot the loss function and it's derivative for a model consisting of just a single parameter, it looks like this for L1:

And like this for L2:

Notice that for $L_1$, the gradient is either 1 or -1, except for when $w_1 = 0$. That means that L1-regularization will move any weight towards 0 with the same step size, regardless the weight's value. In contrast, you can see that the $L_2$ gradient is linearly decreasing towards 0 as the weight goes towards 0. Therefore, L2-regularization will also move any weight towards 0, but it will take smaller and smaller steps as a weight approaches 0.

Try to imagine that you start with a model with $w_1 = 5$ and using $\eta = \frac{1}{2}$. In the following picture, you can see how gradient descent using L1-regularization makes 10 of the updates $w_1 := w_1 - \eta \cdot \frac{dL_1(w)}{dw} = w_1 - \frac{1}{2} \cdot 1$, until reaching a model with $w_1 = 0$:

In constrast, with L2-regularization where $\eta = \frac{1}{2}$, the gradient is $w_1$, causing every step to be only halfway towards 0. That is, we make the update $w_1 := w_1 - \eta \cdot \frac{dL_2(w)}{dw} = w_1 - \frac{1}{2} \cdot w_1$ Therefore, the model never reaches a weight of 0, regardless of how many steps we take:

Note that L2-regularization can make a weight reach zero if the step size $\eta$ is so high that it reaches zero in a single step. Even if L2-regularization on its own over or undershoots 0, it can still reach a weight of 0 when used together with an objective function that tries to minimize the error of the model with respect to the weights. In that case, finding the best weights of the model is a trade-off between regularizing (having small weights) and minimizing loss (fitting the training data), and the result of that trade-off can be that the best value for some weights are 0.

• Could some one explain me, why we won't get into an infinite loop when we take start weight w1 = 5.1 instead of 5. $$\eta = 0.5$$ Let w = 0.1, w > 0 hence our partial derivative is equal to 1 $$w_{first\text{ }step} = 0.1 - 0.5*(+1) => w = -0.4$$ then take second step, now w < 0 => derivative = -1: $$w_{second step} = -0.4 - 0.5*(-1) = 0.1.$$ So we will endless oscillate near 0. – Alex Yashin Jul 4 '17 at 14:43
• @AlexYashin that is correct - if we only updated the weights based on L1 regularization, we might end up having weights that oscillate near 0. But we never use regularization alone to adjust the weights. We use the regularization in combination with optimizing a loss function. In that way, the regularization pushes the weights towards zero while we at the same time try to push the weights to a value that optimize the predictions. A second aspect is the learning rate. With a smaller learning rate, we can get so close to the value that regularization may oscillate around that we can neglect it – Kent Munthe Caspersen Jul 5 '17 at 10:07
• Why dL2(w)/dw is 'module' and not just linear? – mrgloom Aug 15 '17 at 12:16
• @mrgloom dL2(w)/dw can be read as the change of L2(w) per change in weight. Since the L2-regularization squares the weights, L2(w) will change much more for the same change of weights when we have higher weights. This is why the function is convex when you plot it. For L1 however, the change of L1(w) per change of weights are the same regardless of what your weights are - this leads to a linear function. – Kent Munthe Caspersen Sep 15 '17 at 10:08
• The diagram for dl2(w)/dw on the left seems wrong. The derivative of $x^2$ is $x$ - a straight line through the origin, with negative values for $x<0$? – Frank Feb 8 '18 at 1:47

The Figure 3.11 from Elements of Statistical Learning by Hastie, Tibshirani, and Friedman is very illustrative:

Explanations: The $\hat{\beta}$ is the unconstrained least squares estimate. The red ellipses are (as explained in the caption of this Figure) the contours of the least squares error function, in terms of parameters $\beta_1$ and $\beta_2$. Without constraints, the error function is minimized at the MLE $\hat{\beta}$, and its value increases as the red ellipses out expand. The diamond and disk regions are feasible regions for lasso ($L_1$) regression and ridge ($L_2$) regression respectively. Heuristically, for each method, we are looking for the intersection of the red ellipses and the blue region as the objective is to minimize the error function while maintaining the feasibility.

That being said, it is clear to see that the $L_1$ constraint, which corresponds to the diamond feasible region, is more likely to produce an intersection that has one component of the solution is zero (i.e., the sparse model) due to the geometric properties of ellipses, disks, and diamonds. It is simply because diamonds have corners (of which one component is zero) that are easier to intersect with the ellipses that extending diagonally.

• The illustration is not very convincing without additional information. E.g. why should the contours of the error be located where they are in the figure? – wabbit Oct 19 '16 at 16:21
• @HrishikeshGanu Eventually got some time to edit the post. – Zhanxiong Dec 3 '17 at 17:03
• All the contours will have the same form ... – kjetil b halvorsen Dec 3 '17 at 17:18
• Note that with L1 edges are only preferred when $\hat{\beta}$ has different variances over $\beta_1$ and $\beta_2$ axis. In other words when redline distribution is not symmetrical on diagonal $\beta_1 = \beta_2$ axis. If it is symmetrical then the whole edge has the same distance/value/cost. – Tautvydas Dec 16 '17 at 15:50

Have a look on figure 3.11 (page 71) of The elements of statistical learning. It shows the position of a unconstrained $\hat \beta$ that minimizes the squared error function, the ellipses showing the levels of the square error function, and where are the $\hat \beta$ subject to constraints $\ell_1 (\hat \beta) < t$ and $\ell_2 (\hat \beta) < t$.

This will allow you to understand very geometrically that subject to the $\ell_1$ constraint, you get some null components. This is basically because the $\ell_1$ ball $\{ x : \ell_1(x) \le 1\}$ has "edges" on the axes.

More generally, this book is a good reference on this subject: both rigorous and well illustrated, great explanations.

• I think your second paragraph is a key... at least for my intuition: an l1 "ball" is more like a diamond that's spikey along the axes, which means that a hyperplane constrained to hit it is more likely to have a zero on the axes. – Wayne Dec 11 '12 at 14:52
• Yes, I use to imagine the optimization process as the movement of a point submitted to two forces : attraction towards the unconstrained $\hat \beta$ thanks to the squared error function, attraction towards 0 thaks to the $\ell_1$ or $\ell_2$ norm. Here, the "geometry" of this attraction force changes the behavior of the point. If you fix a small $\ell_1$ or $\ell_2$ ball in which it can freely move, it will slide on the border of the ball, in order to go near to $\hat \beta$. The result is shown on the illustration in the aforementionned book... – Elvis Dec 11 '12 at 16:05
• The book is good, but it never explains where it came from and the math behind it. – user13985 Jul 10 '13 at 19:56

A simple non mathematical answer wold be:

For L2: Penalty term is squared,so squaring a small value will make it smaller. We don't have to make it zero to achieve our aim to get minimum square error, we will get it before that.

For L1: Penalty term is absolute,we might need to go to zero as there are no catalyst to make small smaller.

This my point of view.

The image shows the shapes of area occupied by L1 and L2 Norm. The second image consists of various Gradient Descent contours for various regression problems. In all the contour plots, observe the red circle which intersects the Ridge or L2 Norm. the intersection is not on the axes. The black circle in all the contours represents the one which interesects the L1 Norm or Lasso. It intersects relatively close to axes. This results in making coefficients to 0 and hence feature selection. Hence L1 norm make the model sparse.

More Detailed explanation at the following link: Click Post on Towards Data Science

• This is a good explanation, but additional comment on the expression of example cost functions would be useful too. I.e., the circular shape of $\ell_2$-norm errors seems intuitive, however, the narrow-elongated shape, (used in most other examples too), does not seem trivial and self-explanatory. (Here I'm talking about the top left cost-function on the fig.8 (b): why is its principal direction facing towards the $\beta_1 = 1$ point, and not, say, $\beta_1 = 0$? The contours would be different, and the $L_1$ minimizing point would not be at 0!) – Nutle Feb 6 at 0:19