# Why does the L2 norm loss have a unique solution and the L1 norm loss have possibly multiple solutions?

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.

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

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|$$ (a sum of absolute value functions with different x-offsets) often doesn't. Consider $$x_1=1$$ and $$x_2=3$$:

(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)