Machine Learning 2026 · Week 07University of Bern · Interactive lab

Chapter 9 · Regularization and model selection

Regularization and model selection

A model that fits the training data perfectly can still predict badly. Regularization adds a penalty \(\lambda R(\theta)\) that prefers simpler parameters; cross validation chooses how much. Explore the \(\ell_2\) and \(\ell_1\) penalties, see why the lasso produces exact zeros, watch gradient descent pick one of many perfect fits, and connect it all to a Bayesian prior.

9.1 · Regularization

Shrinking an overfit polynomial

A degree-9 polynomial on 12 noisy points interpolates the noise. The \(\ell_2\) penalty pulls the coefficients towards zero. Move \(\lambda\) and watch the curve calm down; the right panel shows the training error (always rising with \(\lambda\)) and the error on fresh validation points, which first falls and then rises.

\[J_\lambda(\theta)=J(\theta)+\frac\lambda2\|\theta\|_2^2\]Eqs. (9.1)–(9.2)
Presets
What to look for

Model

\(J\) is the mean squared error on the 12 training points. Validation error uses 200 fresh points from the same curve.

Fit, coefficients and errors training pointfittrue curve
Error against log₁₀ λ

Check yourself

Discussion questions

Try each question on paper first. Then open the worked answer: it has a derivation, a live calculation you can change, and a one-line takeaway.

R1Show that \(\ell_2\) regularization is weight decay for gradient descent.Derive the update (9.2) for \(J_\lambda(\theta)=J(\theta)+\frac\lambda2\|\theta\|_2^2\) with step size \(\eta\).Worked answer
  1. The gradient of the penalty is \(\nabla\frac\lambda2\|\theta\|_2^2=\lambda\theta\), so \(\nabla J_\lambda(\theta)=\nabla J(\theta)+\lambda\theta\).
  2. One gradient step: \(\theta_{t+1}=\theta_t-\eta\nabla J(\theta_t)-\eta\lambda\theta_t=(1-\eta\lambda)\theta_t-\eta\nabla J(\theta_t)\).
  3. Before the usual step, every weight is multiplied by \(1-\eta\lambda<1\): it decays towards zero.
  4. With adaptive optimizers (e.g. Adam) the gradient is rescaled per coordinate, so the two are no longer equal; AdamW applies the decay separately (“decoupled”).
Current result
TakeawayAn ℓ₂ penalty shrinks every weight by a constant factor per step; the data gradient has to keep pushing to hold a weight away from zero.
R2Why does ℓ₁ produce exact zeros while ℓ₂ does not?Solve the one-dimensional problems \(\min_\theta\frac12(\theta-a)^2+\lambda|\theta|\) and \(\min_\theta\frac12(\theta-a)^2+\frac\lambda2\theta^2\).Worked answer
  1. Ridge: setting the derivative \(\theta-a+\lambda\theta\) to zero gives \(\theta^*=a/(1+\lambda)\). It is zero only if \(a=0\).
  2. Lasso for \(\theta>0\): \(\theta-a+\lambda=0\Rightarrow\theta=a-\lambda\), valid when \(a>\lambda\). Symmetrically \(\theta=a+\lambda\) when \(a<-\lambda\).
  3. If \(|a|\le\lambda\), neither works; at \(\theta=0\) the subgradient \(-a+\lambda[-1,1]\) contains 0, so \(\theta^*=0\).
  4. Together: \(\theta^*=\operatorname{sign}(a)\max(|a|-\lambda,0)\), the soft threshold. Small coefficients become exactly zero; large ones are shifted by \(\lambda\).
Current result
TakeawayThe kink of |θ| at zero creates a whole interval of values that map to exactly 0; the smooth θ² has no such interval.
R3Why is selecting a model by its training error a bad idea?Consider polynomial models of degree \(k=0,1,\dots,10\) fitted by least squares.Worked answer
  1. The models are nested: every degree-\(k\) polynomial is also a degree-\((k+1)\) polynomial with \(\theta_{k+1}=0\).
  2. Least squares minimizes training error over the model class, so a larger class can never do worse: training error is non-increasing in \(k\).
  3. The rule therefore always picks the most complex model, which has the highest variance and typically the worst error on new data.
  4. Validation data, not used for fitting, give an estimate of the error on unseen data and break the tie towards complexity.
Current result from Experiment 5
TakeawayTraining error measures how well a model memorizes, not how well it generalizes.
R4What does k-fold cross validation cost, and when is leave-one-out worth it?Count the model fits for \(|\mathcal M|\) candidate models.Worked answer
  1. Hold-out: each model is fitted once on about \(0.7n\) examples: \(|\mathcal M|\) fits, plus one refit of the winner.
  2. \(k\)-fold: each model is fitted once per fold on \((1-1/k)n\) examples: \(k|\mathcal M|\) fits, plus one refit.
  3. Leave-one-out is \(k=n\): \(n|\mathcal M|\) fits, each on \(n-1\) examples, so the selection uses nearly all data each time.
  4. LOO is worth its cost when data are scarce (each held-out example matters) and fitting is cheap; \(k=10\) is the usual compromise.
Current result
TakeawayMore folds mean less data wasted per fit and more fits to pay for.
R5Show that MAP with a Gaussian prior is ridge regression.Model \(y^{(i)}=\theta^\top x^{(i)}+\varepsilon^{(i)}\), \(\varepsilon^{(i)}\sim\mathcal N(0,\sigma^2)\), prior \(\theta\sim\mathcal N(0,\tau^2I)\).Worked answer
  1. MAP maximizes \(\prod_ip(y^{(i)}\mid x^{(i)},\theta)\,p(\theta)\), equivalently minimizes its negative logarithm (9.5).
  2. \(-\log p(y^{(i)}\mid x^{(i)},\theta)=\frac1{2\sigma^2}(y^{(i)}-\theta^\top x^{(i)})^2+\text{const}\) and \(-\log p(\theta)=\frac1{2\tau^2}\|\theta\|_2^2+\text{const}\).
  3. Multiplying by \(2\sigma^2>0\) does not change the minimizer: \(\theta_{\mathrm{MAP}}=\arg\min_\theta\sum_i(y^{(i)}-\theta^\top x^{(i)})^2+\frac{\sigma^2}{\tau^2}\|\theta\|_2^2\).
  4. This is ridge regression with \(\lambda=\sigma^2/\tau^2\): noisy data or a tight prior mean strong regularization. The closed form is \(\theta_{\mathrm{MAP}}=(X^\top X+\lambda I)^{-1}X^\top\vec y\).
Current result from Experiment 6
TakeawayA Gaussian prior centred at zero is an ℓ₂ penalty; its strength is the ratio of noise variance to prior variance.
R6Why does gradient descent from \(\theta_0=0\) find the minimum-norm interpolant?Least squares \(J(\theta)=\frac1n\|\Phi\theta-\vec y\|^2\) with \(\Phi\in\mathbb R^{n\times d}\), \(d>n\), full row rank.Worked answer
  1. The gradient \(\frac2n\Phi^\top(\Phi\theta-\vec y)\) always lies in the row space of \(\Phi\), \(\operatorname{span}(\Phi^\top)\).
  2. Starting at \(\theta_0=0\), every iterate is a sum of such vectors, so \(\theta_t\in\operatorname{span}(\Phi^\top)\) for all \(t\).
  3. The interpolants are \(\{\theta:\Phi\theta=\vec y\}=\theta^\dagger+\operatorname{null}(\Phi)\). Exactly one of them lies in the row space: \(\theta^\dagger=\Phi^\top(\Phi\Phi^\top)^{-1}\vec y\).
  4. Since row space and null space are orthogonal, \(\|\theta^\dagger+v\|^2=\|\theta^\dagger\|^2+\|v\|^2\): \(\theta^\dagger\) has the smallest norm. A nonzero \(\theta_0\) keeps its null-space component forever.
Current result from Experiment 4
TakeawayThe optimizer and its starting point act as a regularizer even when the loss has none.