Why do we only see $L_1$ and $L_2$ regularization but not other norms?

Question

I am just curious why there are usually only $L_1$ and $L_2$ norms regularization. Are there proofs of why these are better?

Answer 1

In addition to @whuber's comments (*).

The book by Hastie et al Statistical learning with Sparsity discusses this. They also uses what is called the $L_0$ "norm" (quotation marks because this is not a norm in the strict mathematical sense (**)), which simply counts the number of nonzero components of a vector.

In that sense the $L_0$ norm is used for variable selection, but it together with the $l_q$ norms with $q<1$ is not convex, so difficult to optimize. They argue (an argument I think come from Donohoe in compressed sensing) that the $L_1$ norm, that is, the lasso, is the best convexification of the $L_0$ "norm" ("the closest convex relaxation of best subset selection"). That book also references some uses of other $L_q$ norms. The unit ball in the $l_q$-norm with $q<1$ looks like this

(image from wikipedia) while a pictorial explication of why the lasso can provide variable selection is

This image is from the above referenced book. You can see that in the lasso case (the unit ball drawn as a diamond) it is much more probable that the ellipsoidal (sum of squares) contours will first touch the diamond at one of the corners. In the non-convex case (first unit ball figure) it is even more likely that the first touch between the ellipsoid and the unit ball will be at one of the corners, so that case will emphasis variable selection even more than the lasso.

If you try this "lasso with non-convex penalty" in google you will get a lot of papers doing lasso-like problems with non-convex penalty like $l_q$ with $q < 1$.

(*) For completeness I copy in whuber's comments here:

I haven't investigated this question specifically, but experience with similar situations suggests there may be a nice qualitative answer: all norms that are second differentiable at the origin will be locally equivalent to each other, of which the $L_2$ norm is the standard. All other norms will not be differentiable at the origin and $L_1$ qualitatively reproduces their behavior. That covers the gamut. In effect, a linear combination of an $L_1$ and $L_2$ norm approximates any norm to second order at the origin--and this is what matters most in regression without outlying residuals.

(**) The $l_0$-"norm" lacks homogeneity, which is one of the axioms for norms. Homogeneity means for $\alpha \ge 0$ that $\| \alpha x \| = \alpha \| x \|$.

Answer 2

I think the answer to the question depends a lot on how you define "better." If I'm interpreting right, you want to know why it is that these norms appear so frequently as compared to other options. In this case, the answer is simplicity. The intuition behind regularization is that I have some vector, and I would like that vector to be "small" in some sense. How do you describe a vector's size? Well, you have choices:

• Do you count how many elements it has $(L_0)$?
• Do you add up all the elements $(L_1)$?
• Do you measure how "long" the "arrow" is $(L_2)$?
• Do you use the size of the biggest element $(L_\infty)$?

You could employ alternative norms like $L_3$, but they don't have friendly, physical interpretations like the ones above.

Within this list, the $L_2$ norm happens to have nice, closed-form analytic solutions for things like least squares problems. Before you had unlimited computing power, one wouldn't be able to make much headway otherwise. I would speculate that the "length of the arrow" visual is also more appealing to people than other measures of size. Even though the norm you choose for regularization impacts on the types of residuals you get with an optimal solution, I don't think most people are a) aware of that, or b) consider it deeply when formulating their problem. At this point, I expect most people keep using $L_2$ because it's "what everyone does."

An analogy would be the exponential function, $e^x$ - this shows up literally everywhere in physics, economics, stats, machine learning, or any other mathematically-driven field. I wondered forever why everything in life seemed to be described by exponentials, until I realized that we humans just don't have that many tricks up our sleeve. Exponentials have very handy properties for doing algebra and calculus, and so they end up being the #1 go-to function in any mathematician's toolbox when trying to model something in the real world. It may be that things like decoherence time are "better" described by a high-order polynomial, but those are relatively harder to do algebra with, and at the end of the day what matters is that your company is making money - the exponential is simpler and good enough.

Otherwise, the choice of norm has very subjective effects, and it is up to you as the person stating the problem to define what you prefer in an optimal solution. Do you care more that all of the components in your solution vector be similar in magnitude, or that the size of the biggest component be as small as possible? That choice will depend on the specific problem you're solving.

Answer 3

The main reason for seeing mostly $L_1$ and $L_2$ norms is that they cover the majority of current applications. For example, the norm $L_1$ also called the taxicab norm, a lattice rectilinear connecting norm, includes the absolute value norm.

$L_2$ norms are, in addition to least squares, Euclidean distances in $n$-space as well as the complex variable norm. Moreover, Tikhonov regularization and ridge regression, i.e., applications minimizing $\|A\mathbf{x}-\mathbf{b}\|^2+ \|\Gamma \mathbf{x}\|^2$, are often considered $L_2$ norms.

Wikipedia gives information about these and the other norms. Worth a mention are $L_0$. The generalized $L_p$ norm, the $L_\infty$ norm also called the uniform norm.

For higher dimensions, the L$_1$ norm or even fractional norms, e.g., L$_\frac{2}{3}$ may better discriminate between nearest neighbors than the $n$-space distance norm, L$_2$.