I am trying to develop an intuition for why L1 regression is more expensive than L2 regression. Can somebody point me to some material that explains why this is the case
$\begingroup$
$\endgroup$
11
-
5$\begingroup$ Because this doesn't point to material, it isn't an answer, but it may give you some insight: L1 regression of $n$ values against a constant fits a median (which might not be unique), whereas L2 regression fits the mean. Finding the mean is obviously a $O(n)$ computation needing only $O(1)$ local storage. Finding a median naively takes $O(n^2)$, requires $O(n\log(n))$ with the best available sorting algorithms, and actually needs only $O(n)$ time and $O(n)$ storage provided a clever algorithm is used. That algorithm is considerably harder to code than one for the mean. $\endgroup$– whuber ♦Oct 18, 2011 at 18:53
-
$\begingroup$ Related: stats.stackexchange.com/questions/12546/… $\endgroup$– cardinalOct 18, 2011 at 19:12
-
1$\begingroup$ @whuber: A very simple randomized linear-time algorithm exists for finding a median. It can probably be written in a handful of lines of code in a modern programming language and is a very popular implementation of this in numerical-algorithm libraries, particularly because it is fully general (i.e., the same algorithm works for all order statistics). :) $\endgroup$– cardinalOct 18, 2011 at 19:18
-
1$\begingroup$ @cardinal Yes, I'm aware of those algorithms. But do you really think they are comparable in ease of coding and understanding to the simple loop that computes a mean? And then consider the online problem: when you are fed a stream of numbers and need to update a running mean or median (or quantile), the difficulty of re-computing a median (compared to the mean) becomes apparent. But I'm not claiming either problem is hard in any absolute sense... $\endgroup$– whuber ♦Oct 18, 2011 at 19:40
-
$\begingroup$ @whuber: I agree that in an online situation, the difficulties mount. Viewing the L1 regression as an LP makes somewhat clearer why it might be more "expensive" than standard regression in many cases. $\endgroup$– cardinalOct 18, 2011 at 19:49
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
L1 regularisation results in a penalised loss function with discontinuities in the derivatives, whereas L2 regularisation does not introduce discontinuities. This means that when you perform gradient descent optimisation of the penalised loss there needs to be checks to see if a step goes over one of these discontinuities to make sure it is handled properly (hopefully the solution will lie on one of these discontinuities as this is what gives rise to the sparsity). With L2 regularisation there are no such (additional) discontinuities, so there is no need to check for them, so it is generallly faster. In the case of [kernel] ridge regression, you only need to solve a system of linear equations, which is why I normally use those methods rather than L1 regularisation these days.
answered Feb 15, 2012 at 8:14