# Does L1 regularization always generate a sparse solution?

Following is a plot in Bishop's Pattern Recognition and Machine Learning explaining why $L_1$ regularization would lead to sparse solution, and I understand that in this case $w_1$ would be automatically constrained to be 0. However, it seems to me that it is not always true that the corner point is closest to the optimal unconstrained solution. For instance, if the optimal unconstrained solution is at the red cross, then there exists some point on the side that is closer to the red cross than corner points. In this case, do we still have sparse solutions?

• Good question. It depends on how much regularization you use. In this example, it is such that the amount used is not enough to make the solution to your modified minimum sparse. However, if you turn up the regularization by shrinking the constraint region (remember the Lagrange duality), the optimal solution will eventually be sparse unless $w_1=w_2$! Welcome to the site. – Emre Apr 13 '18 at 4:33
• @Emre Thanks! Could you clarify what you mean by "turn up the regularization by shrinking the constraint region (remember the Lagrange duality)"? – user3326682 Apr 13 '18 at 16:53
• Stronger regularization -- using a greater regularization coefficient -- is equivalent to shrinking the shaded region; cf. Sparsity and the Lasso, eqs. 1-4, ("The smaller the value of the tuning parameter t, the more shrinkage.") Read about duality. – Emre Apr 13 '18 at 17:28

I think with your red cross you have in mind the case where $w_1 = w_2$. You are right that in this scenario the solution will not be sparse, since you will also get $w^*_1 = w^*_2$.

However, whenever the coordinates of the red cross are off the line $y=x$ ($w_1\neq w_2$), you can shrink the regularization region so much that eventually you will end up with a similar picture as Figure 3.4 above.

Say your red cross has the coordinates $w_1=r_1$ and $w_2=r_2$ and say your regularization strength is such that $||w||_1 = |w_1|+|w_2| \leq C$ where $C$ defines the size of the shaded region.

Then, for the circular contours, the optimal solution will be where the line $w^*_2 = C- w^*_1$ (for the boundary region) and the line through the red cross at $(r_1,r_2)$ running orthogonal to the boundary region intersect. You can see that the latter has the form $w_2 = f(w_1) = 1\cdot w_1 + r_2 - r_1$. (Orthogonality gives you slope +1 because the boundary region has slope -1.) Setting them equal gives you the intersection at coordinates $w^*_1 = \frac{C+r_1-r_2}{2}$ and $w^*_2 = \frac{C-r_1+r_2}{2}$.

Now, if $r_2=r_1$ you have $w^*_1=w^*_2$ independent of $C$ and the solution won't be sparse.

If $r_1>r_2$ (i.e. you are below the first diagonal) shrinking $C$ to $r_1-r_2>0$ yields $w^*_2=0$ but $w^*_1>0$. You end up in the right corner of the regularization region. (Similar to my image.)

If $r_2>r_1$ (i.e. you are above the first diagonal) shrinking $C$ to $r_2-r_1>0$ yields $w^*_1=0$ but $w^*_2>0$. You end up in the top corner of the regularization region. (Similar to your image.)

As Emre mentioned in the comments, this holds in general and you can "see" this from the Kuhn-Tucker conditions of the optimization problem.

Note that the plot only depicts two dimensions. In that example the $w_1$ coefficient is 0 while $w_2$ is something different from 0. Thus, you could say that the sparsity is 50% since half of your coefficients are 0.

Having said that, you could have problems where the optimal solution has a 0% sparsity and problems where the sparsity is 100%, even with $L_1$ regularization. It depends on the data and the amount of regularization.

Thus, the short answer is that with $L_1$ is just easier for the coefficients to be exactly $0$ than with $L_2$, where it is almost impossible. In fact, it is easy to compute the exact $\lambda_1$ for which all the coefficients of the solution are $0$. If you decrease that value you start observing that some of them are different from $0$.

• The OP references the red X in the second plot as indicating the new minimum, and asks why the new constrained solution is not sparse. – Emre Apr 13 '18 at 16:25