5
$\begingroup$

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

The instability property of the method of least absolute deviations means that, for a small horizontal adjustment of a datum, the regression line may jump a large amount. The method has continuous solutions for some data configurations; however, by moving a datum a small amount, one could “jump past” a configuration which has multiple solutions that span a region. After passing this region of solutions, the least absolute deviations line has a slope that may differ greatly from that of the previous line. In contrast, the least squares solutions is stable in that, for any small adjustment of a data point, the regression line will always move only slightly; that is, the regression parameters are continuous functions of the data.

For some reason, I can't find anything online describing this 'stability' phenomenon. Is it known under a different name?

Stability seems to refer to something like, for (x,y) dataset, "slightly nudge a single input x_i. For the L1 objective function, the slope of the prediction line changes massively, so the L1 objective is unstable."

I would really like a theory explanation for this picture included in that post: http://www.chioka.in/wp-content/uploads/2013/12/programmatic-L1-vs-L2-visualization.png

$\endgroup$
  • 1
    $\begingroup$ The concept seems closely related to the breakdown point of robust statistics. $\endgroup$ – whuber Aug 21 '18 at 14:01
  • $\begingroup$ The terms "robustness" and "sensitivity analysis" (between inputs and outputs) come to mind. $\endgroup$ – Earlien Feb 20 at 4:09
3
+25
$\begingroup$

This is generally called "sensitivity analysis" or "stability". An excellent paper deriving bounds based on this is Stability and Generalization. The bounds of course aren't necessarily tight!

If you look at Definition 19 and the follow-up Theorems and Lemmas you can see that if something is $\sigma$-admissable then there is a bound that is linear in $\sigma$ generally. For $L_1$ it's fairly simple to show that it is $1$-admissable (indeed, they state this for the $\epsilon$-insensitive $L_1$ loss for SVM - example 1, bottom of page 17 in the pdf (515 is the printed page number)), while $L_2$ requires the space $\mathcal{Y}$ to be bound - if one does the math this is basically because one can derive $$\sigma \geq \frac{|y_1^2 - y_2^2 - 2y'(y_1-y_2)|}{|y_1 - y_2|} = |y_1+y_2 - 2y'|$$. Thus, generally, one should expect the $L_1$ to actually have a better bound here. I don't think this completely addresses your question but it hopefully does give you a starting point for a more formal approach to analyzing your specifics.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ One thing I want to point out here is that bounds are given in terms of regression performance - this is generally what is of interest. This is different of course than "how much" the solution changes. $\endgroup$ – MotiN Feb 20 at 19:20
2
$\begingroup$

L1 norm is based on minimising Least Absolute Deviation, with absolute deviation being calculated:

$$ AD = \Sigma^n_{i=1} |y_i-f(x_i)| $$

L2 norm is based on least squared deviation, with squared deviation being calculated:

$$ LSD = \Sigma^n_{i=1} (y_i-f(x_i))^2 $$

So what is the difference for small vs large nudges?

From the perspective of $AD$, if we think about it in terms of its proportion of mean difference then the nudge in $x_i$ will account for less than 1 proportion of the mean difference. if it is smaller than the mean difference. It will be greater than 1 if the nudge is large. The amount it influences the sum is linearly dependent on the magnitude of the nudge.

From the perspective of $LSD$, if we think about it in terms of its proportion of mean variance then the nudge in $x_i$ will be <1 if it is smaller than the mean variance. The amount it influences the sum is dependent on the square magnitude of the nudge. It will be greater than 1 if the nudge is large. Note that if we square number less than 1 it becomes smaller, which means L2 de-emphasises any small nudges.

I don't think the figure covers enough range, if the variance of the nudge is larger than the mean variance then L2 norm errors will in fact grow quicker than L1 error.

There is a range of nudges over which L2 is expected to be more stable (where the variance of the nudge is less than the mean variance) and a region where it is less stable (where the nudge is large). In between there is a region where the two will be more comparable in terms of error, based on the interaction of $AD$ and $LSD$. This rapid escalation as nudge grows is covered by @MotiN in his answer, if the bounds are loose, L2 can weaken dramatically as the nudges grow.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice point on the fact that $L_1$ grows faster than $L_2$ for small changes - obvious in hindsight. $\endgroup$ – MotiN Feb 24 at 11:50

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.