3
$\begingroup$

This question already has an answer here:

I'm aware there is a very relevant explanation on L1 regularization's effect on feature selection at here: Why L1 norm for sparse models [Ref. 1].

To better understand it I'm reading Google's tutorial on Regularization for Sparsity: L₁ Regularization [Ref. 2]. When it comes to the following part, there's some statements I emphasized that I do not understand:

You can think of the derivative of L1 as a force that subtracts some constant from the weight every time. However, thanks to absolute values, L1 has a discontinuity at 0, which causes subtraction results that cross 0 to become zeroed out. For example, if subtraction would have forced a weight from +0.1 to -0.2, L1 will set the weight to exactly 0. Eureka, L1 zeroed out the weight.

I imagine when it says "L1 has a discontinuity at 0" it means the loss of the L1 like in the following figure [Ref. 1]:

enter image description here

But why it will "cause subtraction results that cross 0 to become zeroed out"? Why "if subtraction would have forced a weight from +0.1 to -0.2, L1 will set the weight to exactly 0"?

Is it related to that L1 is not differentiable at $w = 0$?

$\endgroup$

marked as duplicate by jbowman, kjetil b halvorsen, Juho Kokkala, Ferdi, Xavier Bourret Sicotte Nov 7 '18 at 2:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

Consider their metaphor whereby L1 regularization is "a force that subtracts some constant from the weight every time".

First of all, it's only analogous to a physical force if the friction term is very high since forces induce acceleration, and acceleration is integrated to form velocity, which is integrated to form position. If friction is high, then the velocity never persists and the integral of the force over time is roughly the total change in position.

So, consider that every time step, the position $x$ (weight or whatever you're regularizing) experiences a force that applies a total acceleration over that time step of $-k\, \textrm{sgn}(x)$.

Suppose $x$ is smaller than $k$. It seems like applying the force would make $x$ overshoot zero. However, if you subdivide the time step into smaller time steps and $k$ into smaller total accelerations (since the force is integrated over smaller periods), in the limit of subdivision $x$ simply goes to zero.

If this were the L2 norm, you could ask the same question about overshooting. Only now there is a simple physical metaphor: an overdamped pendulum (in mud), which does not overshoot.

$\endgroup$

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