Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 38 · Applications in Machine Learning

The Lasso and Sparsity

Understand why the L1 penalty zeroes out coefficients, compute the smallest penalty that kills all weights, trace a lasso path, and compare it with ridge.

Ridge regression shrinks weights but never makes them exactly zero. Often you want a model that picks a few important features and ignores the rest. The lasso achieves this by replacing the squared L2 penalty with the L1 norm:

Text
minimize over w    ½ ‖X w − y‖² + λ ‖w‖₁       where ‖w‖₁ = Σ |w_j|

Because |w| has a corner at 0, the optimum often lands exactly on the corner for many coordinates. The result is a sparse weight vector, which is easier to interpret and cheaper to use. The lasso is convex but not smooth, so we solve it with the proximal gradient method (ISTA) from the earlier lesson.

Why L1 gives exact zeros

Look at one coordinate in the simplest case where the columns of X are orthonormal (XᵀX = I). The lasso then separates by coordinate, and the solution is the soft threshold of the ordinary least-squares estimate:

Text
w_j = sign(z_j) · max(|z_j| − λ, 0)        with z = Xᵀ y

Any coefficient whose magnitude is at most λ becomes exactly 0. Ridge in the same setting gives w_j = z_j / (1 + λ): shrunk, never zero.

A geometric view: in constraint form, the L1 ball ‖w‖₁ ≤ r is a diamond (in 2D) with corners on the axes. The elliptical level sets of the error are likely to touch the diamond first at a corner, where some coordinates are zero. The L2 ball is round and has no corners.

The smallest penalty that zeroes everything

At w = 0, the optimality condition is: 0 ∈ −Xᵀy + λ·∂‖0‖₁, which means |X_jᵀ y| ≤ λ for every j. So:

Text
λ_max = max_j |X_jᵀ y| = ‖Xᵀ y‖_∞

For λ ≥ λ_max, the solution is exactly w = 0. For smaller λ, features enter the model one by one, in order of their correlation with y. The set of solutions as λ decreases from λ_max to 0 is called the lasso path.

Python Lasso path with ISTA

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At λ = λ_max the support is empty. As λ drops, the three truly important features (0, 3, 7) typically join first, and the irrelevant ones sneak in only at small λ. Warm starting (starting each solve from the previous solution) is the standard trick to compute a whole path cheaply.

Lasso versus ridge

The next example fits both models to the same data and counts exact zeros. We pick the strengths so that both models are reasonably regularized: the point is the pattern of the coefficients, not the specific numbers.

Python Sparse lasso, dense ridge

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Ridge assigns small non-zero weights to every feature; lasso removes most of the irrelevant ones entirely.

Practical points

  • Bias. Lasso shrinks the kept coefficients toward zero. A common fix is to refit an ordinary least-squares model on the selected features.
  • Correlated features. If two features are almost identical, lasso tends to pick one of them (somewhat arbitrarily). Ridge shares the weight between them. The elastic net, which mixes λ₁‖w‖₁ + (λ₂/2)‖w‖², keeps both advantages.
  • Choosing λ. Use cross-validation: fit the path, compare validation error for each λ, and pick the best, or the sparsest model within one standard error of the best.
  • Scaling. Standardize features first, because the L1 penalty treats all coordinates the same.

The lasso is exactly the problem class that motivated proximal methods. A smooth term (squared error) plus a simple non-smooth term (L1 norm) is the canonical case where the prox is one line of code.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Why does the L1 penalty produce exact zeros?

    The prox of the L1 norm is the soft threshold, which maps every value of magnitude at most the threshold to exactly 0.
  2. 2. What is λ_max, the smallest λ for which the lasso solution is all zeros?

    At w = 0 the subgradient condition requires |X_jᵀy| ≤ λ for all j.
  3. 3. In an orthonormal design, how does ridge treat a coefficient compared with lasso?

    Ridge shrinks proportionally; lasso subtracts λ in magnitude and clips at zero.
  4. 4. What is warm starting along a lasso path?

    Neighboring λ values have similar solutions, so reusing the last one makes each solve very cheap.

Summary

  • The lasso minimizes ½‖Xw − y‖² + λ‖w‖₁; its solutions are sparse.
  • With orthonormal columns the solution is a soft threshold; ridge only rescales.
  • For λ ≥ ‖Xᵀy‖_∞, the solution is exactly zero; decreasing λ lets features enter one by one (the lasso path).
  • Lasso is biased and unstable with correlated features; refitting and the elastic net help.

Next: Logistic Regression as a Convex Problem