module 01

Linear Regression, Ridge and Lasso

paywalled

Ridge Regression: Biased Estimation for Nonorthogonal Problems

Arthur E. Hoerl & Robert W. Kennard

When two inputs carry almost the same information, ordinary least squares can't decide how to split the credit, so the weights swing wildly. This paper adds a small penalty on the size of the weights. The answer becomes a tiny bit biased but far more stable, and the authors prove a small penalty always helps on average.

free pdf

Regression Shrinkage and Selection via the Lasso

Robert Tibshirani

Ridge shrinks every weight but never switches any off. The lasso changes the penalty from squares to absolute values, and that small change pushes many weights to exactly zero. You get a model that is both stable and easy to read, because it keeps only the inputs that matter.

the starting point

Draw the straight line (or flat plane) that best fits the data: y ≈ w·x + b. "Best" means the squared differences between the line and the points are as small as possible. This has an exact answer, the normal equations:

X⊤X w=X⊤yX^\top X\, w = X^\top y

So why add anything? The two papers on this page each found a problem with that exact answer.

ridge: when the answer is too jumpy

If two inputs are almost copies of each other, the exact answer can't tell them apart. It might give one a weight of +50 and the other −47, which fits the data just as well as +1.5 and +1.5. Change the data slightly and the weights swing wildly.

Ridge adds a small penalty on the size of the weights:

min⁡w  12n∥y−Xw∥2+α2∥w∥2\min_w\; \tfrac{1}{2n}\|y - Xw\|^2 + \tfrac{\alpha}{2}\|w\|^2

The weights get a little smaller than the "true" answer (a bit of bias) but become far more stable (much less variance). Hoerl and Kennard proved a small penalty always lowers the total error on average.

lasso: shrink and also choose

Ridge shrinks every weight but never switches one off. Tibshirani changed the penalty from squares to absolute values:

min⁡w  12n∥y−Xw∥2+α∥w∥1\min_w\; \tfrac{1}{2n}\|y - Xw\|^2 + \alpha\|w\|_1

That small change pushes many weights to exactly zero, so the model keeps only the inputs that matter. The figure shows the difference. Watch what happens to the two near-copy inputs x0 and x1.

how the weights change as the penalty grows

10^-310^-210^-110^010^100.511.52penalty (log scale) →weight
x0x1x2x3x4
ridge: as the penalty grows (to the right), every weight shrinks smoothly toward zero, but none of them reaches exactly zero. the two near-copy inputs (x0, x1) end up sharing the weight.

Why absolute values give zeros: picture the allowed region for the weights. For ridge it's a circle; for lasso it's a diamond with corners sitting on the axes. The best fit usually touches the diamond at a corner, and at a corner some weights are exactly zero.

solving it: three ways

solver used for why
closed form plain regression and ridge exact in one step
gradient descent all of them keeps every step, so we can draw the path
coordinate descent lasso fixes one weight at a time with a simple "shrink toward zero and stop at zero" rule, which produces exact zeros

Gradient descent rolls downhill on the loss surface. How big each step is matters a lot:

gradient descent on the loss surface

final loss 0.1306
-101234-3-2-1012weight 1weight 2×
a step close to the limit moves fast across the steep direction, then crawls along the flat valley floor.

When inputs are strongly related, the loss surface is a long narrow valley. Gradient descent quickly reaches the valley floor, then crawls along it. That narrow valley is the same problem ridge fixes.

how the code works

  • The intercept is never penalised. The code centres X and y first, solves for w, then works out b. Shrinking b would make the answer depend on where zero happens to be.
  • The "shrink toward zero" rule is soft_threshold(x, t): move x toward zero by t, stopping at zero.
  • lasso_alpha_max is the penalty at which every lasso weight becomes zero, so a path can start there.
  • Scaling note if you compare with sklearn: l1 matches sklearn's Lasso. sklearn's Ridge(alpha) equals our ridge with alpha / n.

what the demo checks

Run uv run python examples/01_linear.py.

  • Gradient descent matches the exact answer to 4 × 10⁻¹⁵ when inputs are unrelated, but still hasn't arrived after 20,000 steps when two inputs are near copies.
  • Refit on random resamples: plain regression's weights on the near-copy pair swing by about ±5.7; ridge's by about ±0.05.
  • The lasso solution passes the exact optimality test (the KKT conditions), so it's really the best answer, not just close.
  • Gradient descent blows up as soon as the step size passes its predicted limit.

when it goes wrong

  • Step size too big: the loss shoots up instead of down.
  • Lasso with related inputs: it keeps one somewhat arbitrarily. Using both penalties together (elastic net) helps.
  • Inputs on different scales: both penalties treat a feature in millimetres differently from the same feature in metres. Rescale first.