Chapter 15

15Choosing the Penalty

The penalty \(\lambda\) from the last chapter is a knob, and this chapter is about which way to turn it. Turn it to zero and you fit the data as hard as you can — all variance, an overfit model that has memorized the noise. Turn it up and you crush the coefficients toward zero — all bias, an underfit model too stiff to see the signal. Somewhere between sits the setting that minimizes prediction error, the bottom of the bias-variance U from Chapter 12. The trouble is that you cannot find it by looking at how well you fit the data you trained on, because that number always votes for \(\lambda = 0\). You need an honest estimate of how the model does on data it has not seen, and a way to read \(\lambda\) as an amount of complexity rather than a bare number.

If you take one idea from this chapter, take this: choosing the penalty is choosing model complexity, and cross-validation is how you let the data choose it honestly.

15.1Letting the data choose

Start with the temptation and why it fails. You have a family of fits, one per value of \(\lambda\), and you want the best one. The obvious score is training error — the average loss on the very data you fit — so why not pick the \(\lambda\) that minimizes it? Because training error is not a measure of how good the model is; it is a measure of how hard the model tried. A model fit with \(\lambda = 0\) bends all the way to the data, driving training error down toward zero, and every increase in \(\lambda\) only stiffens the fit and raises training error. Minimizing it therefore always lands on \(\lambda = 0\): the most overfit model in the family.

Common trap

You cannot choose \(\lambda\) on the training set. Training error slides down monotonically as you weaken the penalty, so it will always crown the least-regularized, most-overfit model. The quantity you actually care about — error on new data — first falls and then rises, and the gap between the two curves is exactly the overfitting the training score cannot see.

What you actually care about is generalization error: the loss you would incur on a fresh observation drawn from the same process. You do not have fresh observations to spare, so you manufacture them by hiding some of your data from the fit and scoring on the part you hid. That is cross-validation: a way to estimate out-of-sample error using only the sample you have. In \(k\)-fold cross-validation you split the data into \(k\) roughly equal folds, then for each fold in turn you train on the other \(k-1\) and score on the one you held out, and finally you average the \(k\) held-out scores. Every observation is predicted exactly once, by a model that never saw it.

A data bar divided into five equal folds. Five rows below it show the rotation: in each row four folds are shaded as training data and a different single fold is highlighted as the held-out validation fold, so each fold is held out exactly once. An arrow on the right averages the five held-out scores into one CV estimate.
Figure 15.1Five-fold cross-validation. Each round trains on four folds and scores on the fifth; rotating the held-out fold means every point is predicted once by a model that never saw it. Averaging the five held-out scores gives one honest error estimate — for one value of the penalty.

Run that whole procedure at each candidate \(\lambda\) and you trace out a curve. Write \(k(i)\) for the fold that holds observation \(i\), and \(\hat f^{-k(i)}_\lambda\) for the model fit at penalty \(\lambda\) on all folds except that one. The cross-validation error is the average held-out loss:

\[\text{CV}(\lambda) = \frac{1}{n} \sum_{i=1}^{n} L\big(y_i,\, \hat f^{-k(i)}_\lambda(x_i)\big).\]

Plotted against \(\lambda\) this is a U (or a hockey-stick when the noise is mild): high on the left where the unpenalized fit overfits, high on the right where the heavy penalty underfits, with a dip in between. Pick the \(\lambda\) at the bottom and you have let the data tell you how much to shrink.

Two curves against the log of the penalty lambda. The training-error curve slides down monotonically from left to right, approaching zero as lambda shrinks. The cross-validation error curve is U-shaped: high on the left where the model overfits, dipping to a minimum in the middle, and rising on the right where the model underfits. A vertical marker sits at the CV minimum; a second marker one standard error to its right shows the one-standard-error choice. A shaded band around the CV curve shows its fold-to-fold uncertainty.
Figure 15.2Why the training curve cannot choose for you. Training error (grey) falls without limit as the penalty weakens, so it always prefers the overfit extreme. The cross-validation curve (blue) is the honest one: it turns up once the model starts fitting noise. Its minimum marks the best penalty; the one-standard-error rule steps right to the simplest model still within a standard error of that minimum.

Intuition

Training error asks "how well did I fit what I have already seen?" — and the answer improves the harder you fit, which is no test at all. Cross-validation asks "how well would I do on something I have not seen?", and that answer gets worse once you start fitting noise. Only the second question has a wrong answer, which is exactly why it can guide you.

The minimum is not the only sensible choice. The CV curve is itself estimated from a finite sample, so its exact location jitters; the folds disagree, and that disagreement has a size. The one-standard-error rule takes the standard error of the CV score across folds at the best \(\lambda\), then picks the largest \(\lambda\) — the simplest, most regularized model — whose CV error is still within one standard error of the minimum. You give up a hair of estimated accuracy for a simpler, more stable model, on the theory that differences smaller than the noise in the curve are not worth chasing (Hastie et al., 2009).

Analogy

Cross-validation is like grading a student on held-back exam questions instead of the practice set they studied from. Score them on the practice problems and a memorizer looks brilliant; score them on questions they have not seen and you learn whether they understood anything. The analogy leaks in that exam questions are genuinely independent, whereas your folds are carved from one dataset and share its quirks — which is why CV estimates generalization error rather than measuring it exactly.

Common trap

If you tune \(\lambda\) by cross-validation, the tuned model must still be judged on data used nowhere in the tuning. The moment you pick \(\lambda\) by its CV score, that score stops being an unbiased estimate of error — you optimized against it, so it is optimistic. Any preprocessing that peeks at the whole dataset (standardizing features, selecting variables) has to happen inside each fold, not before the split; doing it once up front leaks the held-out data into the fit and quietly inflates your results. Keep a final test set the tuning never touches.

A sharper question

Why not just use leave-one-out — set \(k = n\), holding out a single point each time — so the training sets are as large as possible? Leave-one-out nearly eliminates the bias from training on less than the full data, but its folds are almost identical to each other, so their scores are highly correlated and the variance of the average can be large. It is also \(n\) times the compute unless a shortcut exists — and for linear smoothers one does, since leave-one-out error has a closed form in terms of the diagonal of the hat matrix you will meet in the next section. Five- or ten-fold CV is the usual compromise: enough training data to keep bias small, folds different enough to keep variance in check.

15.2Complexity as a dial

Cross-validation tells you which \(\lambda\) to use, but not what you bought with it. For that, translate the penalty into a complexity you can read off — and the surprise is that complexity need not be a whole number.

Without a penalty, a model's complexity is just its parameter count: fit \(p\) coefficients and you have spent \(p\) degrees of freedom, the number of independent directions in which the fit is free to chase the data. Regularization changes this. A penalized fit still has \(p\) coefficients, but it is not free to move each one as far as it likes — the penalty tethers them — so it behaves like a model with fewer parameters. The effective degrees of freedom make this precise: they measure how many parameters the fit effectively spends, and unlike a raw count they slide continuously.

The clean way to see it is through the hat matrix, the matrix \(H_\lambda\) that maps the observed responses to the fitted values, \(\hat y = H_\lambda y\) — so called because it "puts the hat on \(y\)." Its trace counts how sensitive the fitted values are to the observations, and that is the effective degrees of freedom. For ridge regression the trace has a beautiful closed form. Write the design matrix's singular values — the intrinsic scales of its directions — as \(d_1, \dots, d_p\). Then

\[\text{df}(\lambda) = \operatorname{tr}(H_\lambda) = \sum_{j=1}^{p} \frac{d_j^2}{d_j^2 + \lambda}.\]

Read the summand as a dimmer switch on each direction. When \(\lambda = 0\) every term is \(1\) and the sum is \(p\): full complexity, the ordinary least-squares fit. As \(\lambda \to \infty\) every term goes to \(0\) and so does the sum: the fit collapses to a constant, zero effective parameters. In between, a direction contributes near \(1\) when its scale \(d_j^2\) dwarfs the penalty (that direction is well-determined, so ridge leaves it alone) and near \(0\) when the penalty dwarfs it (that direction is shaky, so ridge all but discards it). The penalty spends your parameter budget preferentially on the directions the data actually pins down.

A curve of effective degrees of freedom against the log of the penalty lambda. On the left, at small lambda, the curve sits flat at its maximum value p, the full parameter count. As lambda increases the curve descends smoothly, passing through intermediate non-integer values, and flattens toward zero on the right at large lambda. Faint horizontal guide lines mark the integer levels the continuous curve slides past.
Figure 15.3Complexity as a dial, not an integer. Ridge's effective degrees of freedom slide smoothly from the full parameter count p at zero penalty down to zero as the penalty grows, passing through every value between. The penalty does not delete parameters; it fractionally spends them, keeping the well-determined directions and fading out the shaky ones.

Intuition

Regularization does not turn parameters off one at a time; it turns them down. Effective degrees of freedom count the fractional total that survives — a model with \(p = 50\) nominal coefficients and a moderate penalty might have the complexity of, say, \(7.3\) genuine parameters. That fractional number, not the raw count, is what sits on the horizontal axis of the bias-variance U.

This is the payoff that ties the chapter together. The bias-variance curve of Chapter 12 has "model complexity" on its horizontal axis, and effective degrees of freedom are what that axis really means once you regularize. Sliding \(\lambda\) from \(\infty\) down to \(0\) walks the effective complexity from \(0\) up to \(p\), carrying you from the underfit right shoulder of the U, through its minimum, to the overfit left shoulder. Cross-validation, meanwhile, is estimating the height of that same U at each point. Choosing the penalty is choosing where on the complexity axis to stand, and the two tools work as a pair: effective degrees of freedom name the position, cross-validation tells you which position is lowest.

Note

Effective degrees of freedom generalize past ridge. Any linear smoother — a method whose fitted values are a fixed linear map of the responses, \(\hat y = Hy\) — has effective degrees of freedom \(\operatorname{tr}(H)\), which is why smoothing splines and \(k\)-nearest-neighbors can be placed on the same complexity axis and compared. The lasso is not a linear smoother, but a useful analogue holds: its effective degrees of freedom are well approximated by the number of nonzero coefficients it selects.

A sharper question

If cross-validation already scores every \(\lambda\), why bother computing effective degrees of freedom at all? Because CV gives you a black-box score with no interpretation — it says "this \(\lambda\) predicts best" without saying what kind of model that is. Effective degrees of freedom convert the penalty into a currency you understand and can compare across methods: a ridge fit with \(\text{df} = 7\) and a spline with \(\text{df} = 7\) are spending the same complexity, whatever their machinery. They also feed analytic model-selection criteria — AIC, generalized cross-validation — that estimate prediction error from the training fit plus a complexity charge of \(\text{df}(\lambda)\), giving you a cheaper, if more assumption-laden, alternative to running the folds. This complexity accounting becomes essential when \(p\) approaches or exceeds \(n\), the regime Chapter 21 takes up.

References

Check yourself

A few questions to test the ideas from this chapter. Pick an answer to see whether it holds up.

  1. Why can training error never be used to choose the penalty λ?

  2. In k-fold cross-validation, what is each observation's contribution to CV(λ) computed from?

  3. For ridge regression, the effective degrees of freedom equal the sum over the design's singular values of d_j^2 / (d_j^2 + λ). As λ grows from 0 to infinity, this quantity does what?

  4. What does the one-standard-error rule prescribe?

  5. You standardize all features and select variables using the full dataset, then run cross-validation to tune λ. What is wrong?

  6. Compared with five- or ten-fold CV, what is the characteristic drawback of leave-one-out cross-validation?