# Why L1 norm for sparse models

I am reading books about linear regression. There are some sentences about the L1 and L2 norm. I know the formulas, but I don't understand why the L1 norm enforces sparsity in models. Can someone 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 Jun 30 '15 at 12:24
• There a blog article on the same chioka.in/… May 12 '17 at 11:19
• Check the following post of Medium. It might help medium.com/@vamsi149/… 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. 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. 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). 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/…). Feb 23 '14 at 2:58
• great answer i've been wondering around for a while until i found this. 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. 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 Jul 5 '17 at 10:07
• Why dL2(w)/dw is 'module' and not just linear? 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. Sep 15 '17 at 10:08
• @KentMuntheCaspersen Amazing explanation! Thank you for the graphs and the effort you invested to make this intuitive! May 10 '18 at 9:34

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? Oct 19 '16 at 16:21
• 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. Dec 16 '17 at 15:50
• It comes from property of Lagrange multipiers. At optima the tangent to the loss and constraint should be shared. Because at non differtiable point you have infinite tangents it's more likely to have those as solutions. Mar 25 '20 at 3:52
• Is there any proof? Why can't this figure simply be an artifact? Dec 20 '20 at 22:47
• I agree with @wabbit. Why should the contours intersect at the corner of the pyramid constraint region? I could easily re-draw the figure such that the contours touched the edge of this pyramid.
– gwg
Jun 10 at 13:22

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. 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... Dec 11 '12 at 16:05
• The book is good, but it never explains where it came from and the math behind it. Jul 10 '13 at 19:56 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!)
– runr
Feb 6 '19 at 0:19
• Hi, May I check why should it intersect? Why are we making sure to pick the new estimate (from the point where it interacts)? Feb 10 at 11:52

I suggest you read some more about the theory of convex optimization. An answer to why the $$\ell_1$$ regularization achieves sparsity can be found if you examine implementations of models employing it, for example LASSO. One such method to solve the convex optimization problem with $$\ell_1$$ norm is by using the proximal gradient method, as $$\ell_1$$ norm is not differentiable. I found Ryan Tibshirani's slides for his convex optimization course to be quite helpful on this topic, even though my mathematical background is limited.

You can find the derivation of the soft-thresholding operator $$S_\lambda$$ used in the slides in the first answer to the mathematics StackExchange question on deriving the soft-thresholding operator. It is not too hard to follow, even without great knowledge of subgradients, and its result clearly shows why you get sparsity--for some $$\lambda > 0$$, for the $$i$$th component $$w_t^i$$ of the weight vector at time $$t$$, the proximal gradient step is $$w_{t + 1}^i = w_t^i - \lambda$$ if $$|w_t^i| > \lambda$$, $$w_{t + 1}^i = 0$$ when $$|w_t^i| \le \lambda$$. In ISTA (iterative soft-thresholding algorithm) described in Tibshirani's slides for LASSO, you would see that the weight vector update is

$$\mathbf{w}_{t + 1} = S_\lambda(\mathbf{w}_t + \eta\mathbf{X}^\top(\mathbf{y} - \mathbf{X}\mathbf{w}))$$

That is, after the least-squares gradient update with step $$\eta > 0$$, you perform soft-thresholding. This achieves sparsity, as the vector components with magnitude less than $$\lambda$$ are set to 0.

You can replace $$-\mathbf{X}^\top(\mathbf{y} - \mathbf{Xw})$$ with a general objective function gradient as well.

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.

• Not very convincing to me. Nov 5 '18 at 8:15
• @CyberPlayerOne This is just another way of stating the same as in the accepted answer Aug 13 at 19:35

l2 regularizer does not change the value of weight vector from one iteration to another iteration because of the slope of l2 norm is reducing all the time where as l1 regularizer constantly reduce the value of weight vector towards optimal W* which is 0 because of the slopeod L1 norm is constant