4.3 LASSO

An L1 penalty that can zero out coordinates.

These notes walk through the lecture slides. The original deck is unchanged; use (slides) on the course hub if you want that PDF.

The figures follow Deisenroth, Faisal, and Ong, Mathematics for Machine Learning, and Theodoridis, Machine Learning: A Bayesian and Optimization Perspective.

1. LASSO

Ridge’s penalty $λ \sum_{j} θ_{j}^{2}$ shrinks every coefficient toward zero but never sets one exactly to zero. That is not sparsity.

LASSO (least absolute shrinkage and selection operator) uses an $ℓ_{1}$ penalty instead:

\sum_{n = 1}^{N} (y_{n} - θ_{0} - \sum_{j = 1}^{l} θ_{j} x_{j})^{2} + λ \sum_{j = 1}^{l} | θ_{j} |,

where $\sum_{j = 1}^{l} | θ_{j} |$ is the $ℓ_{1}$ -norm of $(θ_{1}, \dots, θ_{l})^{⊤}$ .

2. Geometry

LASSO geometry: ellipse and diamond

The $ℓ_{1}$ constraint is a diamond. As $l$ grows, that diamond has more corners, so some coefficients land on an axis and become zero. LASSO therefore shrinks and does subset selection.

3. The objective

J (θ) = \frac{1}{2 N} ‖ 𝐲 - 𝐗 θ ‖_{2}^{2} + λ ‖ θ ‖_{1} .

Squared error plus $ℓ_{1}$ . The $ℓ_{1}$ term is not differentiable at $θ_{j} = 0$ , so ordinary gradients are not enough.

A subgradient generalizes the gradient. One subgradient of this $J$ is

g (θ, λ) = - \frac{1}{N} 𝐗^{⊤} (𝐲 - 𝐗 θ) + λ [\begin{matrix} s g n (θ_{1}) \\ s g n (θ_{2}) \\ ⋮ \\ s g n (θ_{l}) \end{matrix}],

with

s g n (θ_{j}) = {\begin{matrix} - 1 & if θ_{j} < 0, \\ any value in [- 1, 1] & if θ_{j} = 0, \\ 1 & if θ_{j} > 0 . \end{matrix}

Subgradient descent (or a cousin) iterates until $θ$ settles.

4. Comments

LASSO does variance reduction, gives accurate predictions, and is built for variable selection.
A little regularization is usually wise. Ridge is a safe default. Prefer LASSO if you believe only a few features matter.
If the columns of $𝐗$ are orthonormal, LASSO has the closed form

{\hat{θ}}_{j} = s g n ({\hat{θ}}_{L S}) (| {\hat{θ}}_{L S} | - λ / 2)_{+} .

That is soft thresholding: $(\cdot)_{+}$ is the positive part (the argument if it is nonnegative, otherwise zero). 4. In the same orthonormal case, ridge is a uniform shrink: ${\hat{θ}}_{R} = \frac{1}{1 + λ} {\hat{θ}}_{L S}$ .

5. Computational complexity

A closed form exists only in special cases (orthonormal columns). Otherwise use (sub)gradient descent, especially when there are many features or too many rows for memory.

Soft thresholding is one solver. Another is to approximate $ℓ_{1}$ by a family of smooth quadratics,

{lim}_{ϵ \to 0} \sum_{i = 0}^{l} \sqrt{θ_{i}^{2} + ϵ} .

6. Practice

What does soft thresholding do to a coordinate of the LASSO?
Why is the LASSO objective not differentiable at $θ_{j} = 0$ ?
When would you prefer LASSO to ridge?

Ahmad Mousavi