Part II · Chapter 12

Model selection: regularization & cross-validation

ERM always prefers the more complex model. This chapter gives you two tools that push back — a penalty on complexity inside the objective, and held-out data outside it — and the recipe for choosing any hyperparameter honestly.

Essentials

ERM always prefers the richer model class, so complexity must be controlled from outside the training error: a penalty inside the objective, held-out data outside it.

Why ERM cannot choose $k$ — every degree-$k$ polynomial is a degree-$(k+1)$ polynomial with $\theta_{k+1}=0$, so training error can only fall as $k$ grows. The extra flexibility fits noise: overfitting.
Regularized ERM — $\theta^\star = \arg\min_{\theta} \frac1N\sum_i\bigl(\theta^\top\phi(x^{(i)}) - y^{(i)}\bigr)^2 + \lambda\, r(\theta)$, with $\lambda > 0$. A complex model is chosen only if its drop in empirical risk pays for its rise in $\lambda r(\theta)$.
$L_0$ — $r(\theta)=\sum_j \1\{\theta_j \ne 0\}$: sparse, but the arg min is combinatorially hard and there is no gradient to follow.
LASSO ($L_1$) — $\sum_j |\theta_j|$: sparse, with coefficients exactly $0$; convex and tractable, not differentiable at $0$.
Ridge ($L_2^2$) — $\sum_j \theta_j^2$: shrinks coefficients toward $0$, rarely exactly $0$.
Two rules — exclude the bias $\theta_0$ from the regularizer; standardize features first, or scale alone decides who gets penalized.
Hyperparameter — a choice about the model class or training procedure that ERM is biased on: degree $k$, $\lambda$, tree depth, learning rate, number of layers.
Holdout CV — split 80 : 20, score each candidate on the validation set, take the lowest, retrain on all the data. High variance when $N$ is small.
$k$-fold CV — partition into $k$ folds; CV error $= \frac1k\sum_{i=1}^{k}\text{error}_i$ with fold $i$ held out each time; $k=5$ or $10$; $k=N$ is LOOCV. Then retrain on everything.
Feature engineering vs feature learning — humans choose $\phi$ (interpretable) vs $\phi$ discovered from data (needs a lot of it).

Everything below is the explanation and the practice. If you are short on time, read this box, then go to the problems.

1. Where we are: polynomial features, and the question they leave open

The lecture opens with data that is plainly curved ($\mathcal X = \R$, $\mathcal Y = \R$). A line $y = wx + b$ won't fit it, but a quadratic $h(x) = \theta_2 x^2 + \theta_1 x + \theta_0$ will. Generalise: $h(x) = \theta_k x^k + \dots + \theta_1 x + \theta_0$, or more abstractly, any feature map $\phi : \mathcal X \to \R^{d'}$. The recipe, which you already know from chapter 10:

Transform the training set: $(x^{(i)}, y^{(i)}) \mapsto (\phi(x^{(i)}), y^{(i)})$.
Train an ordinary linear regressor $h : \R^{d'} \to \R$ on the transformed data.
Predict on a new point with $h(\phi(x^{\text{new}}))$.

$d'$ is the number of features after the transform — for a degree-$k$ polynomial, $\phi(x) = [x, x^2, \dots, x^k]$ plus the bias.

The open question: how do you choose $k$? "Use ERM — pick the $k$ with the lowest training error" is wrong, and wrong in a predictable direction.

Key idea — why ERM can't choose $k$

Every degree-$k$ polynomial is also a degree-$(k+1)$ polynomial (set $\theta_{k+1} = 0$). So the degree-$(k+1)$ model class contains the degree-$k$ class, and its best training error can only be equal or lower. ERM therefore always prefers higher $k$. Higher-degree polynomials bend to fit the noise in the data, not just the signal: overfitting.

Three responses. Get more data — effective, often expensive. The other two are this chapter: regularization (change the objective) and cross-validation (change how you evaluate).

2. Regularization: charge the model for complexity

Analogy

An expense policy. Without one, an employee (ERM) buys the most expensive tool for every job, because it is always at least as good. Charge them per purchase and they buy it only when it is enough better to justify the price. $\lambda$ is the price — a penalty in the same units as the loss, whose size you set by experiment (§5), not by accounting.

Definition — regularized ERM $$ \theta^\star \;=\; \arg\min_{\theta\in\R^{d'}} \;\underbrace{\frac{1}{N}\sum_{i=1}^{N}\Bigl(\theta^\top\phi(x^{(i)}) - y^{(i)}\Bigr)^2}_{\text{empirical risk}} \;+\; \lambda\,\underbrace{r(\theta)}_{\text{regularizer}} $$

$r : \R^{d'} \to \R$ is the regularizer: a number measuring how "complex" $\theta$ is. More complex → bigger.
$\lambda > 0$ is the regularization strength: how much weight the complexity penalty gets relative to the empirical risk.

A more complex model always has lower empirical risk, but it also has a larger $r(\theta)$. So a complex model is chosen only if its drop in empirical risk is big enough to pay for its increase in $\lambda r(\theta)$; otherwise the simpler model wins.

Three regularizers

Name	$r(\theta)$	What it encourages	Catch
"$L_0$" — count of non-zeros	$\sum_{j=1}^{d'} \1\{\theta_j \ne 0\}$	Sparsity: few features used at all	Finding the arg min is computationally hard (combinatorial: which subset of features?)
LASSO ($L_1$)	$\sum_{j=1}^{d'} \|\theta_j\|$	Also sparsity — many coefficients become exactly $0$	Not differentiable at $0$, but convex and efficiently solvable
Ridge ($L_2^2$)	$\sum_{j=1}^{d'} \theta_j^2$	Small coefficients, spread out	Rarely makes anything exactly $0$

Try itEvaluate the three penalties

For $\theta = [3,\ 0,\ -4]$ (bias already excluded), compute the $L_0$, LASSO and ridge penalties. Then: which penalty would be unchanged if the first entry went from $3$ to $0.001$?

Step 1 — Compute each

$L_0$: two entries are non-zero → $2$. LASSO: $|3| + |0| + |-4| = 7$. Ridge: $9 + 0 + 16 = 25$.

Answer & the takeaway

$L_0$ stays $2$ — it only cares whether an entry is non-zero, not how big. That's exactly why it's hard to optimize: shrinking a coefficient gradually gains nothing until it hits exactly $0$, so there's no gradient to follow. LASSO drops to $4.001$ and ridge to about $16$ — both reward shrinking, which is what makes them tractable.

Why LASSO gives exact zeros and ridge doesn't

The notes assert that LASSO encourages sparsity without saying why. Minimizing loss plus $\lambda r(\theta)$ is equivalent to minimizing the loss subject to $r(\theta) \le t$ for some budget $t$. The loss has elliptical contours around its unregularized minimum, and you want the lowest contour that touches the allowed region.

Figure 1 — the $L_1$ diamond has corners; the $L_2$ disc doesn't

Unregularized optimum $\theta_1$ $\theta_2$ Budget $t$

What to notice: at the starting position the LASSO solution sits exactly on the corner $(1, 0)$ — $\theta_2$ is zeroed — while ridge keeps a small non-zero $\theta_2$. Move the optimum around: for a whole range of positions the diamond's solution stays pinned to a corner; the disc's solution lands exactly on an axis only for special, knife-edge positions. Drag $\theta_2$ up to about $0.7$ and LASSO leaves the corner too — sparsity is likely, not guaranteed. The constrained optimum is found numerically by scanning the boundary.

Practical rules from the lecture

Common mistake 1 — penalizing the bias

Exclude $\theta_0$ from the regularizer. The bias just shifts predictions up or down to match the average $y$. Penalizing it drags every prediction toward $0$ — if all your targets are around $1000$, a penalized bias would systematically under-predict, which has nothing to do with complexity.

Common mistake 2 — mixing scales

Standardize features first: same units, same scale — subtract each feature's training mean and divide by its spread. The penalty treats every $\theta_j$ the same, but a feature measured in millimetres needs a coefficient 1000× larger than the same feature in metres, so it would get penalized far more for no reason. (The notes say "divide by the variance"; the standard choice is the standard deviation, which puts every feature on unit scale. Dividing by the variance would leave a feature with spread $\sigma$ at scale $1/\sigma$, not $1$.)

Two more regularizers are named but not covered: dropout and early stopping, both of which you meet with neural networks. How you choose $\lambda$ is §4–5.

3. Watch regularization work

Fifteen training points (orange) and fifteen separate validation points (teal), same curved function plus noise. Fit a degree-$k$ polynomial with a regularizer and watch the coefficients and both errors.

Figure 2 — polynomial degree × regularizer × $\lambda$

Degree $k$ $\log_{10}\lambda$ Regularizer

What to notice: at degree 10 with $\lambda$ near zero the curve wiggles to chase individual training points — lowest training error, but validation error about twice its best value, and large coefficients. Raise $\lambda$ and the curve calms down: training error rises a little, validation error falls a lot. Keep going and it underfits — both errors climb, and at the far end the curve flattens toward the mean. Switch to LASSO at a moderate $\lambda$ and watch coefficients hit exactly zero (grey bars). Features are standardized and the bias is unpenalized, as §2 recommends.

Guided problemRidge by hand, one parameter

Data: $(x, y) = (1, 2),\ (2, 4),\ (3, 7)$. Model $h(x) = \theta x$ (no bias, no features). Objective

$$ J(\theta) = \frac{1}{3}\sum_{i=1}^{3}(\theta x^{(i)} - y^{(i)})^2 + \lambda\theta^2 . $$

Find $\theta^\star$ as a function of $\lambda$, then evaluate at $\lambda = 0, 0.5, 1, 5$ together with the training MSE.

Step 1 — Differentiate and set to zero

$$ J'(\theta) = \frac{2}{N}\sum_i x^{(i)}(\theta x^{(i)} - y^{(i)}) + 2\lambda\theta = 0 $$ $$ \Longrightarrow\quad \theta^\star = \frac{\frac{1}{N}\sum_i x^{(i)}y^{(i)}}{\frac{1}{N}\sum_i (x^{(i)})^2 + \lambda}. $$

$J$ is a parabola in $\theta$ opening upward (the $\theta^2$ coefficient is $\frac1N\sum x^2 + \lambda > 0$), so this is the minimum.

Step 2 — Plug in the data

$\sum xy = 2 + 8 + 21 = 31$, $\sum x^2 = 1 + 4 + 9 = 14$, $N = 3$:

$$ \theta^\star(\lambda) = \frac{31/3}{14/3 + \lambda}. $$

Step 3 — Evaluate

$\lambda$	$\theta^\star$	training MSE
0	2.2143	0.1190
0.5	2.0000	0.3333
1	1.8235	0.8316
5	1.0690	6.2406

Answer & the takeaway

$\lambda$ appears only in the denominator, so it shrinks $\theta^\star$ toward $0$ smoothly — and training error must rise, because $\lambda = 0$ was by definition the training-error minimizer. Regularization always costs you training error; the bet is that it buys back more than that in validation error. Notice too that ridge never reaches exactly $0$ for any finite $\lambda$: that's the "rarely makes anything exactly zero" row of the table.

4. Hyperparameters: the things ERM can't choose

A second example of the same problem, from decision trees.

Figure 3 (reconstructed) — split again for one outlier, or stop?

Reconstructed from the notes' figure, which lost its points in extraction; only the split values $x_1 = 3.5$ and $x_2 = 4.5$ survived. The layout of the points is illustrative.

Should the tree keep splitting until the lone point in the top right is classified correctly? For: it may carry real information. Against: its label may be noise. Training error cannot settle this — the extra split always lowers it.

Definition

A hyperparameter is a choice about the model class or training procedure that ERM itself is biased on — it would always choose the more complex option. The lecture's examples: tree depth, $\lambda$, and polynomial degree $k$. (Learning rate and number of neural-network layers are hyperparameters too.)

The pivot: what if we had more labelled data? Evaluate both trees on it and keep the one with lower error. Data a model was not trained on cannot be overfitted by that model — that is the whole idea of cross-validation.

5. Cross-validation

Holdout cross-validation

Algorithm — holdout CV

Randomly split the training samples into a training set and a validation set (typically 80 : 20).
For each candidate value of the hyperparameter(s): train on the training set; compute the average error on the validation set.
Choose the value with the lowest validation error.
Retrain the model with the chosen value on the entire data.

Problem: with few samples the validation set is tiny, so the score depends heavily on which points landed in it. Re-split and you may choose a different $k$: high variance.

$k$-fold cross-validation

Algorithm — $k$-fold CV

Randomly partition the training data into $k$ equal-sized folds $F_1, \dots, F_k$. For each candidate hyperparameter value:

For each fold $i = 1, \dots, k$: train on the other $k-1$ folds $\bigcup_{j\ne i}F_j$; compute the error $\text{error}_i$ on $F_i$.
Cross-validation error $= \frac{1}{k}\sum_{i=1}^{k}\text{error}_i$.

Choose the value with the lowest CV error, then retrain on the full dataset with it.

Every point is validated exactly once and the $k$ estimates are averaged, so the choice is far less at the mercy of one lucky split. Common choices: $k = 5$ or $k = 10$. The extreme $k = N$ — each fold a single point — is leave-one-out cross-validation (LOOCV).

Name clash

This $k$ (number of folds) has nothing to do with the polynomial degree $k$ from §1 — the lecture reuses the letter. In the figure below they are labelled "folds" and "degree".

Figure 4 — choose the polynomial degree by $k$-fold CV

Folds

24 points from a curved function plus noise; unregularized polynomial fits of degree 1–10. What to notice: training error (orange) only goes down with degree — it would always pick the biggest model. CV error (teal) is U-shaped, and its minimum is the choice. Press "Reshuffle" a few times: with 5 or more folds the chosen degree is fairly stable; with "Holdout 80:20" it jumps around much more from split to split — the high variance the lecture warns about. Slide folds to 24 for LOOCV (reshuffling then changes nothing: there's only one way to leave one out).

Try itHow many models do you train?

$N = 100$ samples; you're choosing $\lambda$ from 4 candidate values. How many times do you train a model with (a) 5-fold CV, (b) LOOCV? Include the final retrain.

Step 1 — Count per candidate

$k$-fold trains once per fold per candidate: $4 \times k$.

Answer & the takeaway

(a) $4 \times 5 + 1 = 21$. (b) $4 \times 100 + 1 = 401$. LOOCV uses the data most thoroughly but costs $N$ trainings per candidate — fine for linear regression, painful for a large neural network. That cost is why $5$ and $10$ are the defaults.

After 5-fold CV picks $\lambda = 0.1$, what do you deploy?

Why: CV chooses the hyperparameter, not the parameters. The fold models were each trained on only 80% of the data; once $\lambda$ is chosen you retrain on 100%. Picking the best fold (A) just rewards the luckiest split.

You tune $\lambda$ with CV, then report the CV error of the chosen $\lambda$ as your model's expected error on new data. What's wrong?

Why: choosing the minimum of several noisy estimates selects in favour of a lucky one. beyond syllabus The clean fix is a separate test set that is never touched during model selection — or nested CV.

6. Feature engineering vs feature learning

A distinction the course revisits, and the bridge to the next chapter.

Feature engineering	Feature learning
Humans decide what features may be useful ($x^2$, $\log x$, …)	Useful features / representations are discovered automatically from data
Humans implement the feature-extraction algorithm	Typically needs large datasets
Higher interpretability	—

Everything so far has been feature engineering: you chose $\phi$. A neural network learns its own $\phi$ — its hidden layers are a feature map with trainable parameters — which is exactly why it needs more data and is harder to interpret.

7. Recap

The statements are all in the Essentials box at the top; three things are worth saying once more.

Regularization always costs training error. The bet is that it buys back more in validation error.
CV chooses the hyperparameter, not the parameters — so you always retrain on the full dataset afterwards.
The CV error of the winning candidate is an optimistically biased estimate of future error: you selected on it.