Exact Sparsity

The L-one Subgradient

The absolute-value penalty has a corner at zero. This lesson names the exact subgradient cases without pretending the zero case has one scalar slope.

highlighted = computed this step

Away from zero

For w greater than 0, the absolute-value slope is 1. For w less than 0, the slope is -1. Those are exact sign cases.

w>0⇒+ 1,w<0⇒−1w>0\Rightarrow +\,1,\quad w<0\Rightarrow -1
L1 subgradientExact sign cases and zero set.L1 subgradientcasesubgradientw>0+1w<0-1w=0[-1,1]at zero this is a set, not a fake scalarthrough-origin lasso fit; λ is chosen before the solve; L1 can hit exact zero; NOTconvergence; NOT general feature selection; NOT generalization

At zero, use a set

At w=0, |w| has a corner, so there is no single slope. The subdifferential is the exact set [-1,1]. The diagram names the set instead of pretending it is one scalar.

∂∣w∣∣w=0=[−1,1]\partial |w|\big|_{w=0}=[-1,1]
L1 subgradientExact sign cases and zero set.L1 subgradientcasesubgradientw>0+1w<0-1w=0[-1,1]at zero this is a set, not a fake scalarthrough-origin lasso fit; λ is chosen before the solve; L1 can hit exact zero; NOTconvergence; NOT general feature selection; NOT generalization

Summary

This corner is the mechanism behind exact sparsity. Lasso can stop at w=zero because the zero point has a whole exact set of valid subgradients.

subgradient at zero is a set\text{subgradient at zero is a set}
L1 subgradientExact sign cases and zero set.L1 subgradientcasesubgradientw>0+1w<0-1w=0[-1,1]at zero this is a set, not a fake scalarthrough-origin lasso fit; λ is chosen before the solve; L1 can hit exact zero; NOTconvergence; NOT general feature selection; NOT generalization