http://www.chioka.in/differences-between-l1-and-l2-as-loss-function-and-regularization/

If you look at the top of this post, the writer mentions that L2 norm has a unique solution and L1 norm has possibly many solutions. I understand this in terms of regularization, but not in terms of using L1 norm or L2 norm in the loss function.

If you look at graphs of functions of scalar x (x^2 and |x|), you can easily see both have one unique solution.

  • 2
    "fnx"? ... Please edit to make this clearer. Do you mean "functions"? – Glen_b Aug 21 at 2:04
up vote 18 down vote accepted

Let's consider a one-dimensional problem for the simplest possible exposition. (Higher dimensional cases have similar properties.)

While both $|x-\mu|$ and $(x-\mu)^2$ each have a unique minimum, $\sum_i |x_i-\mu|$ often doesn't. Consider $x_1=1$ and $x_2=3$:

Plot of sum_i |x_i - mu|

(NB in spite of the label on the x-axis, this is really a function of $\mu$; I should have modified the label but I'll just leave it as is)

In higher dimensions, you can get regions of constant minimum with the $L_1$-norm. There's an example in the case of fitting lines here.

Sums of quadratics are still quadratic, so $\sum_i (x_i-\mu)^2 = n(\bar{x}-\mu)^2+k(\mathbf{x})$ will have a unique solution. In higher dimensions (multiple regression say) the quadratic problem may not automatically have a unique minimum -- you may have multicollinearity leading to a lower-dimensional ridge in the negative of the loss in the parameter space; that's a somewhat different issue than the one presented here.


A warning. The page you link to claims that $L_1$-norm regression is robust. I'd have to say I don't completely agree. It's robust against large deviations in the y-direction, as long as they aren't influential points (discrepant in x-space). It can be arbitrarily-badly screwed up by even a single influential outlier. There's an example here.

Since (outside some specific circumstances) you don't usually have any such guarantee of no highly influential observations, I wouldn't call L1-regression robust.


R code for plot:

 fi <- function(x,i=0) abs(x-i)
 f <- function(x) fi(x,1)+fi(x,3)
 plot(f,-1,5,ylim=c(0,6),col="blue",lwd=2)
 curve(fi(x,1),-1,5,lty=3,col="dimgrey",add=TRUE)
 curve(fi(x,3),-1,5,lty=3,col="dimgrey",add=TRUE)
  • This is great. What software did you use to make the graph? – user3180 Aug 21 at 2:20
  • 2
    R. This is just done in base graphics. I have added the code to the end of my answer. – Glen_b Aug 21 at 2:23
  • Woah, never realised you could supply a function to plot. Mind is blown. – JAD Aug 21 at 6:52

Minimizing the L2 loss corresponds to calculating the arithmetic mean, which is unambiguous, while minimizing the L1 loss corresponds to calculating the median, which is ambiguous if an even number of elements are included in the median calculation (see Central tendency: Solutions to variational problems).

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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