Why Does L1 Regularization Lead to Sparse Solutions Unlike L2?

[newphysist]

I am trying to understand the difference between L1 vs. L2 regularization in OLS. I understand the concept of center of ellipsoid being the optimal solution and ellipse itself being contours of constant squared errors. And when we use L2 regularization we introduce a spherical constraint on coefficient and when we use L1 the constraints are rectangle in R² representation.

In all corresponding pictorial representation of the above in literature,etc, the representation in R² always shows ellipsoid intersecting the circle in first quadrant but the square on one of the axis i.e at corners. How come in L1 regularization the ellipsoid intersects the square only on corners but in case of L2 any point on the sphere. Wouldn't we get a sparse solution for L2 as well if ellipse intersects the circle (R² representation) at axis.

Thanks

 

[Nick Alger]

The best intuition I've found comes from considering a special case, the 1D minimization problem
argmin_x |x| + a/2(x-1)^2.

The absolute value term tries to put the minimum at x=0, and the quadratic term tries to put the minimum at x=1. The constant 'a' determines the relative influence of the quadratic term compared to the absolute value term, and so as you change 'a', the minimum will move between 0 and 1.

However a really interesting "thresholding" phenomenon occurs. The minimum stays at exact zero for 'a' < 1, and only when 'a'=1 does the minimum start increasing. Draw some pictures to convince yourself this is true. This is because the absolute value function has many "subderivatives" (tangent lines lying beneath the function) at zero, and so it can absorb changes to other terms derivatives, but only up to a certain limit. It is convenient, since it says that 'x' should be exactly zero unless there is a really good reason for it to not be, and the threshold for letting it be nonzero is determined by the parameter 'a'.

On the other hand, if the first term was differentiable instead of absolute value, even for a very small 'a', the minimum would be slightly positive (recall that the minimum is where the derivative of quantity to be minimized is zero). Thus there is no thresholding effect if both terms are differentiable.

l1 regularization is basically a multidimensional generalization of this principle.