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?

A figure from Pattern Recognition and Machine Learning

  • 2
    $\begingroup$ 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. $\endgroup$ – Emre Apr 13 '18 at 4:33
  • $\begingroup$ @Emre Thanks! Could you clarify what you mean by "turn up the regularization by shrinking the constraint region (remember the Lagrange duality)"? $\endgroup$ – user3326682 Apr 13 '18 at 16:53
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

enter image description here

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.

| improve this answer | |

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$.

| improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Emre Apr 13 '18 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.