L1 vs L2 stability?

Question

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

Answer 1

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.

Answer 2

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.