Lasso

Definition

$w_{n,\lambda }={\mathrm{argmin}}_w\frac{1}{n}\Vert Y-Xw{\Vert }_2^2+\lambda \Vert w{\Vert }_1$ (least absolute shrinkage and selection operator, Tibshirani 1996). Convex, no closed form.

Formula

Orthogonal design ($X^{t}X=nI$, OLS solution $\hat{w}$):

$$w_j=\mathrm{sign}({\hat{w}}_j)\max (|{\hat{w}}_j|-\lambda /2,0)$$

• $\Vert w{\Vert }_0$ (number of non-zeros) is NP hard to optimize; $\Vert w{\Vert }_1$ is the closest convex norm ($\Vert \cdot {\Vert }_p$ is convex iff $p\ge 1$).
• Sparse because the $L_1$ ball has corners on the axes; $L_2$ penalizes large weights quadratically and prefers many small ones.
• Rate for $k$-sparse ${\theta }^{\ast }$: $\sigma k\sqrt{\log d}/\sqrt{n}$ (only $\log d$); $L_0$: ${\sigma }^{2}k\log d/n$.

Appears in

• Lecture 5, sparsity and Ω₀
• Lecture 5, p-norms
• Lecture 5, why L1 is sparse
• Lecture 5, the lasso
• Lecture 5, soft thresholding task
• Lecture 5, Proposition 10 (excess risk of the lasso) and Theorem 11 (excess risk with L0)

Related concepts

• Ridge Regression
• Regularization