---
title: A Machine-Learning Refresher
module: Foundations
moduleNumber: 1
lessonNumber: 2
order: 102
summary: >
  The statistical framework the networks live in: data drawn from an unknown
  distribution, a loss to minimize, and the central question of generalization:
  will it work on data we have not seen? We set up empirical risk, capacity,
  the bias–variance tradeoff, and maximum likelihood.
topics: [Foundations]
sources:
  - book: Goodfellow
    ref: "Ch. 5 — Machine Learning Basics"
  - book: Goodfellow
    ref: "§5.2 Capacity, Overfitting and Underfitting"
---

A learning algorithm has one job: **perform well on data it was not trained on.**
Risk, capacity, regularization, and validation are all machinery in service of
that single goal. This lesson sets up the statistical frame the
[networks](/deep-learning/neural-networks/the-multilayer-perceptron) inhabit.

## The supervised learning setup

Data is generated by a fixed but unknown distribution $p_{\text{data}}(x, y)$
over inputs $x \in \mathcal{X}$ and targets $y \in \mathcal{Y}$. We never observe
$p_{\text{data}}$; we observe only a finite i.i.d. sample,

$$
\mathcal{D} = \{(x_1, y_1), \dots, (x_n, y_n)\} \overset{\text{i.i.d.}}{\sim}
p_{\text{data}}.
$$

The **i.i.d. assumption** carries the whole theory. It splits into two clauses,
each providing a distinct guarantee:

- **Identically distributed:** train and test share one $p_{\text{data}}$, so
  fitting the past is informative about the future at all.
- **Independent:** no example leaks information about another beyond
  $p_{\text{data}}$, so the law of large numbers applies and the sample average
  converges to the expectation. This is what makes empirical risk a faithful
  stand-in for true risk.

> **Definition (Data-generating distribution).** The fixed but unknown joint
> distribution $p_{\text{data}}(x, y)$ from which all examples (training, test,
> and every future input) are drawn. It is never observed directly; the dataset
> $\mathcal{D}$ is the only window onto it, and every guarantee below is a
> statement about $p_{\text{data}}$ inferred through that window.

Break the identically-distributed clause and the guarantees evaporate. The
optimizer is not at fault; it minimized exactly the risk it was given, on exactly
the distribution it saw; $p_{\text{data}}$ simply moved. This failure mode is
**distribution shift**:

| Train distribution | Test distribution | Symptom |
| --- | --- | --- |
| daytime photographs | night photographs | object detector misses in low light |
| movie reviews | clinical notes | sentiment classifier mislabels |
| pre-shock market | post-shock market | pricing model misprices |

The i.i.d. assumption is a modelling choice, not a law of nature; we measure the
gap it opens once we have the tools, under
[robustness](/deep-learning/theory/generalization-theory).

> **Definition (Risk).** The **risk** (or _generalization error_) of a model
> $f_\theta$ is its expected loss on a fresh example from the true
> distribution:
> $$ R(\theta) = \mathbb{E}_{(x,y)\sim p_{\text{data}}}\,[\,\ell(f_\theta(x), y)\,]. $$

Risk is what we actually care about and exactly what we cannot compute — it is
an expectation over a distribution we do not have. So we substitute the average
over the data we _do_ have.

> **Definition (Empirical risk).** The average loss over the training set,
> $$ \hat{R}(\theta) = \frac{1}{n}\sum_{i=1}^{n} \ell(f_\theta(x_i), y_i). $$

**Empirical risk minimization** (ERM) is the strategy of choosing $\theta$ to
make $\hat{R}$ small and _hoping_ $R$ follows. The gap between the two, between
training performance and reality, is the central problem of the subject.[^gf-erm]

## Generalization, overfitting, underfitting

Split the data: train on one part, estimate the risk on a held-out **test set**
the model never touched. Two numbers result (training error $\hat{R}$ and test
error), and their relationship sorts every model into one of three regimes.

$$
% caption: Training error falls with capacity; generalization error is U-shaped —
% the gap between them is overfitting.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (0,0) -- (8.2,0) node[right, font=\footnotesize] {capacity};
  \draw[->, thick] (0,0) -- (0,4.4) node[above, font=\footnotesize] {error};
  % training error: monotone decreasing toward 0
  \draw[acc, very thick] (0.4,3.9) .. controls (2.5,1.4) and (4.5,0.55) .. (7.7,0.25);
  % generalization error: U-shaped
  \draw[red, very thick] (0.4,4.0) .. controls (2.6,1.7) and (3.6,1.05) .. (4.3,1.05)
                                   .. controls (5.6,1.05) and (6.8,2.4) .. (7.7,3.6);
  % optimal capacity marker
  \draw[green, dashed, thick] (4.3,0) -- (4.3,1.05);
  \fill[green] (4.3,1.05) circle (2.4pt);
  \node[green, font=\footnotesize] at (4.3,-0.32) {optimal};
  % zone labels
  \node[font=\footnotesize, align=center] at (2.15,3.55) {under-\\f\/itting};
  \node[font=\footnotesize, align=center] at (7.1,2.2) {over-\\f\/itting};
  % curve labels
  \node[acc, font=\footnotesize, anchor=west] at (5.9,0.5) {training error};
  \node[red, font=\footnotesize, anchor=west] at (0.7,0.75) {generalization error};
\end{tikzpicture}
$$

- **Underfitting** (left): the model lacks the capacity to capture the pattern,
  so _both_ errors are high. The remedy is a bigger model or better features.
- **Overfitting** (right): the model has memorized noise specific to the
  training sample. Training error is tiny but test error has climbed: the
  **generalization gap** has opened.
- The **sweet spot** sits where generalization error bottoms out.

For example, fit the same seven noisy points
with a line, a cubic, and a degree-9 curve: the three regimes are unmistakable.
The line is too rigid to follow the trend; the high-degree curve contorts to pass
through every point, noise included, and will lurch wildly between them.

$$
% caption: The same data fit three ways: underfit (too rigid a line), a good fit,
% and overfit (a high-degree curve chasing every noisy point).
\begin{tikzpicture}[font=\footnotesize, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % shared data points (gently wavy + noise)
  \def\pts{(0.2,0.45),(0.6,1.05),(1.0,0.72),(1.45,1.32),(1.85,0.98),(2.25,1.5),(2.6,1.22)}
  % --- Panel A: underfit (straight line) ---
  \begin{scope}
    \draw[black] (0,0) rectangle (2.9,2.1);
    \draw[red, very thick] (0.15,0.62) -- (2.7,1.3);
    \foreach \p in \pts \fill[black] \p circle (1.6pt);
    \node[anchor=north, font=\footnotesize] at (1.45,-0.18) {underf\/it};
  \end{scope}
  % --- Panel B: good fit (smooth curve) ---
  \begin{scope}[xshift=4cm]
    \draw[black] (0,0) rectangle (2.9,2.1);
    \draw[green, very thick] (0.15,0.5) .. controls (0.9,1.25) and (1.7,1.0) .. (2.7,1.4);
    \foreach \p in \pts \fill[black] \p circle (1.6pt);
    \node[anchor=north, font=\footnotesize] at (1.45,-0.18) {good f\/it};
  \end{scope}
  % --- Panel C: overfit (wiggly through every point) ---
  \begin{scope}[xshift=8cm]
    \draw[black] (0,0) rectangle (2.9,2.1);
    \draw[red, very thick] plot[smooth, tension=1.1] coordinates {(0.2,0.45)(0.6,1.05)(1.0,0.72)(1.45,1.32)(1.85,0.98)(2.25,1.5)(2.6,1.22)};
    \foreach \p in \pts \fill[black] \p circle (1.6pt);
    \node[anchor=north, font=\footnotesize] at (1.45,-0.18) {overf\/it};
  \end{scope}
\end{tikzpicture}
$$

> **Definition (Capacity).** A model's **capacity** is the richness of the set
> of functions it can represent. Low capacity forces underfitting; excess
> capacity _permits_ overfitting. Polynomial degree, network width and depth,
> and (effectively) training time all dial it.

Capacity sets what _can_ go wrong, not what _will_. The **no-free-lunch theorem**
makes this precise: averaged over _all_ data-generating distributions, every
learning algorithm has the same expected test error: there is no universally best
model. Real problems are not drawn uniformly from all worlds (images have local
structure, language has grammar), and a model wins exactly when its **inductive
bias** matches the structure present.[^gf-nfl]

## The curse of dimensionality

Structure is not optional: in high dimensions, naive learning is defeated by
geometry before capacity is even in question. The **curse of dimensionality** is
a cluster of effects tracing to one fact — _volume grows exponentially with
dimension._ Partition each axis of the $d$-dimensional unit cube into $b$ bins:

$$
\#\text{cells} = b^{\,d}, \qquad b = 10 :\;\; 10^1 = 10 \;\to\; 10^{10}\ \text{at}\ d = 10.
$$

To keep even one example per cell (the density nearest-neighbour quietly assumes),
the sample size must grow as $b^d$. No dataset does, so the consequences cascade:

| Effect | Statement | What fails |
| --- | --- | --- |
| Empty space | a fixed sample fills a vanishing fraction $n / b^d$ of cells | local density estimates |
| Distance concentration | $\max\norm{x_i - x_j} / \min\norm{x_i - x_j} \to 1$ as $d \to \infty$ | "nearest" neighbour is barely nearer than the farthest |
| Sample requirement | examples for fixed coverage grow as $b^d$ | brute-force tabulation, kernel density |

Smoothness-based methods ("points close together have similar labels") fail
because in high dimensions almost nothing is close to anything.[^gf-curse]

$$
% caption: The curse of dimensionality: binning each axis, the number of cells to
% populate grows exponentially, from a handful in 1D to far too many in 3D.
\begin{tikzpicture}[font=\footnotesize, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % --- 1D: a line of 4 bins ---
  \begin{scope}
    \foreach \i in {0,1,2,3} \draw[black] (\i*0.45,0) rectangle (\i*0.45+0.45,0.45);
    \fill[acc] (0.22,0.22) circle (1.5pt);
    \fill[acc] (1.12,0.22) circle (1.5pt);
    \node[anchor=north, align=center] at (0.9,-0.2) {1D\\4 cells};
  \end{scope}
  % --- 2D: a 4x4 grid ---
  \begin{scope}[xshift=3.2cm]
    \foreach \i in {0,1,2,3} \foreach \j in {0,1,2,3}
      \draw[black] (\i*0.45,\j*0.45) rectangle (\i*0.45+0.45,\j*0.45+0.45);
    \fill[acc] (0.22,1.12) circle (1.5pt);
    \fill[acc] (1.57,0.22) circle (1.5pt);
    \fill[acc] (1.12,1.57) circle (1.5pt);
    \node[anchor=north, align=center] at (0.9,-0.2) {2D\\16 cells};
  \end{scope}
  % --- 3D: a cube of cells (drawn as a 4x4 grid with an offset back face) ---
  \begin{scope}[xshift=6.6cm]
    \foreach \i in {0,1,2,3} \foreach \j in {0,1,2,3}
      \draw[black] (\i*0.45+0.5,\j*0.45+0.5) rectangle (\i*0.45+0.95,\j*0.45+0.95);
    \foreach \i in {0,1,2,3} \foreach \j in {0,1,2,3}
      \draw[black] (\i*0.45,\j*0.45) rectangle (\i*0.45+0.45,\j*0.45+0.45);
    \draw[black] (0,1.8) -- (0.5,2.3);
    \draw[black] (1.8,1.8) -- (2.3,2.3);
    \draw[black] (1.8,0) -- (2.3,0.5);
    \fill[acc] (0.22,0.67) circle (1.5pt);
    \fill[acc] (1.57,1.12) circle (1.5pt);
    \node[anchor=north, align=center] at (1.15,-0.2) {3D\\64 cells};
  \end{scope}
  % --- exponential arrow ---
  \draw[->, acc, thick] (-0.1,-1.15) -- (8.3,-1.15)
    node[midway, below, font=\scriptsize, text=acc] {cells grow as $4^{d}$ : exponential in dimension};
\end{tikzpicture}
$$

This is the rigorous reason for inductive bias: if you cannot fill the space, you
must _assume_ a shape for it and let that prior do the work the data cannot. Every
deep-learning prior is the same move: trade dense coverage for a structural
assumption:

| Prior | Structural assumption | Mechanism |
| --- | --- | --- |
| smoothness | nearby inputs $\to$ nearby outputs | $L^2$ penalty, small weights |
| locality | features depend on local patches | convolution, weight sharing |
| temporal structure | the same map applies at each step | recurrence |
| manifold hypothesis | data clusters near a low-dimensional surface | the assumption deep nets exploit most |

From this angle deep learning is the search for priors that make
high-dimensional problems tractable.

## The bias–variance tradeoff

Why is generalization error U-shaped? Decompose it. For squared-error
regression, the expected test error at a point, averaged over all the training
sets we _could_ have drawn, splits into three pieces:

$$
\mathbb{E}\brackets{(y - \hat{f}(x))^2} = \underbrace{\parens{\,\mathbb{E}[\hat{f}(x)] -
f(x)\,}^2}_{\text{bias}^2} + \underbrace{\Var\brackets{\hat{f}(x)}}_{\text{variance}}
+ \underbrace{\sigma^2}_{\text{noise}}.
$$

| Term | Formula | Meaning | Cause |
| --- | --- | --- | --- |
| Bias$^2$ | $\parens{\mathbb{E}[\hat f(x)] - f(x)}^2$ | error from wrong assumptions, on average | model too simple — _underfitting_ |
| Variance | $\Var[\hat f(x)]$ | sensitivity to the particular sample | model too flexible — _overfitting_ |
| Noise | $\sigma^2$ | irreducible — label noise in $p_{\text{data}}$ | the data, not the model |

> **Definition (Bias & variance).** **Bias** is the error from wrong assumptions,
> a model too simple to fit the truth on average. **Variance** is the error from
> sensitivity to the particular training sample. **Noise** $\sigma^2$ is
> irreducible; no model touches it.

Picture a dartboard: each dot is the model fit on a _different_ sample,
the bullseye is the truth. Bias is how far the _cluster_ sits from center;
variance is how _spread out_ it is.

$$
% caption: Bias vs. variance as dart throws: each dot is a model trained on a
% different sample, and low bias with low variance (top-left) is the goal.
\begin{tikzpicture}[font=\footnotesize, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % --- four targets at grid positions ---
  % helper: rings drawn per target center
  \foreach \cx/\cy in {0/0, 4.6/0, 0/-4.6, 4.6/-4.6} {
    \draw[black] (\cx,\cy) circle (1.15);
    \draw[black] (\cx,\cy) circle (0.7);
    \draw[red, thick, fill=red!15] (\cx,\cy) circle (0.22);
  }
  % top-left: low bias, low variance (tight, centred)
  \foreach \dx/\dy in {0.05/0.1, -0.1/-0.05, 0.12/-0.08, -0.04/0.13, 0.0/0.0}
    \fill[acc] (0+\dx,0+\dy) circle (1.7pt);
  % top-right: low bias, high variance (spread, centred)
  \foreach \dx/\dy in {0.55/0.35, -0.6/0.45, 0.25/-0.7, -0.45/-0.5, 0.7/-0.15, -0.2/0.65}
    \fill[acc] (4.6+\dx,0+\dy) circle (1.7pt);
  % bottom-left: high bias, low variance (tight, offset)
  \foreach \dx/\dy in {0.5/0.45, 0.6/0.55, 0.45/0.6, 0.58/0.4, 0.5/0.52}
    \fill[acc] (0+\dx,-4.6+\dy) circle (1.7pt);
  % bottom-right: high bias, high variance (spread, offset)
  \foreach \dx/\dy in {0.8/0.7, 0.15/0.85, 0.95/0.15, 0.35/0.35, 0.6/1.0, 1.0/0.55}
    \fill[acc] (4.6+\dx,-4.6+\dy) circle (1.7pt);
  % column headers
  \node at (0,1.7)   {low variance};
  \node at (4.6,1.7) {high variance};
  % row labels
  \node[align=center, anchor=east] at (-1.7,0)    {low\\bias};
  \node[align=center, anchor=east] at (-1.7,-4.6) {high\\bias};
\end{tikzpicture}
$$

Capacity trades one for the other: simple models are high-bias / low-variance
(underfit), complex models are low-bias / high-variance (overfit). The classical
U-curve is bias falling and variance rising, summed.

$$
% caption: The U-curve decomposed: bias-squared falls with capacity while
% variance rises; their sum (plus fixed noise) is the U-shaped test error, and
% its minimum is the tradeoff's sweet spot.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  \draw[->, thick] (0,0) -- (8.2,0) node[right, font=\footnotesize] {capacity};
  \draw[->, thick] (0,0) -- (0,4.4) node[above, font=\footnotesize] {error};
  % bias^2: falls
  \draw[acc, very thick] (0.4,3.8) .. controls (2.5,1.0) and (4.5,0.35) .. (7.7,0.2);
  \node[acc, font=\footnotesize, anchor=west] at (5.6,0.55) {bias$^2$};
  % variance: rises
  \draw[green!60!black, very thick] (0.4,0.2) .. controls (3.0,0.35) and (5.0,1.1) .. (7.7,3.6);
  \node[green!60!black, font=\footnotesize, anchor=south east] at (6.6,3.7) {variance};
  % total = U-shaped (sum + noise floor)
  \draw[red, very thick] (0.4,4.05) .. controls (3.0,1.55) and (4.0,1.35) .. (4.6,1.35)
                                    .. controls (5.6,1.35) and (6.8,2.6) .. (7.7,3.95);
  \node[red, font=\footnotesize] at (3.9,2.05) {total error};
  \draw[black, dashed] (4.6,0) -- (4.6,1.35);
  \node[font=\footnotesize, anchor=north] at (4.6,-0.05) {sweet spot};
\end{tikzpicture}
$$

(Deep networks
complicate this picture; we revisit _double descent_
[later](/deep-learning/theory/generalization-theory), but the tradeoff is the
right first picture.)

### Point estimation made precise

The dartboard is the theory of **point estimation**. Fed a random dataset
$\mathcal{D}$, a learning algorithm returns an **estimator** $\hat\theta =
\hat\theta(\mathcal{D})$, itself a random quantity. Four properties quantify its
quality:

| Property | Definition | Reads on the dartboard as |
| --- | --- | --- |
| Bias | $\bias(\hat\theta) = \mathbb{E}_{\mathcal{D}}[\hat\theta] - \theta$ | offset of the cluster from the bullseye |
| Unbiased | $\bias(\hat\theta) = 0$ | cluster centred on the bullseye |
| Variance | $\Var(\hat\theta) = \mathbb{E}_{\mathcal{D}}\brackets{(\hat\theta - \mathbb{E}[\hat\theta])^2}$ | spread of the cluster |
| Consistent | $\hat\theta \xrightarrow{p} \theta$ as $n \to \infty$ | cluster tightens onto centre with more darts |

> **Definition (Bias of an estimator).** The systematic part of an estimator's
> error, $\bias(\hat\theta) = \mathbb{E}_{\mathcal{D}}[\hat\theta] -
> \theta$, the expectation over datasets. An estimator is **unbiased** when it
> lands on the truth _on average_, however much a single fit misses.

> **Definition (Variance and consistency).** The variance $\Var(\hat\theta)$
> measures how the estimate jitters as $\mathcal{D}$ is redrawn. An estimator is
> **consistent** when it converges in probability to the truth as $n \to \infty$ —
> the guarantee that more data eventually wins.

Bias and variance are the dartboard's two axes; the decomposition drawn earlier
is a one-line consequence.

> **Theorem (Bias–variance decomposition).** For an estimator $\hat\theta$ of a
> fixed target $\theta$, the mean squared error splits exactly into squared bias
> plus variance,
> $$ \MSE(\hat\theta) = \mathbb{E}\brackets{(\hat\theta - \theta)^2} = \bias(\hat\theta)^2 + \Var(\hat\theta). $$

> **Proof.** Write $\mu = \mathbb{E}[\hat\theta]$ and insert $\pm\mu$ inside the
> square: $\mathbb{E}[(\hat\theta - \theta)^2] = \mathbb{E}[((\hat\theta - \mu) +
> (\mu - \theta))^2]$. Expanding gives three terms. The cross term
> $2(\mu-\theta)\,\mathbb{E}[\hat\theta - \mu]$ vanishes because
> $\mathbb{E}[\hat\theta - \mu] = 0$ by definition of $\mu$. What remains is
> $\mathbb{E}[(\hat\theta - \mu)^2] + (\mu - \theta)^2 = \Var(\hat\theta) +
> \bias(\hat\theta)^2$. $\qed$

Low error is not low bias. An unbiased estimator can be terrible if its variance
is large, and a _biased_ estimator can have strictly lower MSE than the best
unbiased one. This is precisely the trade regularization makes: accept a little bias
for a large drop in variance.

## Where the loss comes from: maximum likelihood

We used $\ell$ as if handed down from above. Most losses are **maximum likelihood
estimation** in disguise. Model the conditional $p_\theta(y \mid x)$ and make the
data as probable as possible:

$$
\theta_{\text{MLE}} = \arg\max_\theta \prod_{i=1}^n p_\theta(y_i \mid x_i)
= \arg\min_\theta \;\underbrace{-\sum_{i=1}^n \log p_\theta(y_i \mid x_i)}_{\text{NLL}}.
$$

The $\log$ turns an underflow-prone product into a stable sum, and maximizing
likelihood becomes minimizing the **negative log-likelihood**. The task chooses
the output distribution; the NLL _is_ the familiar loss:

| Task | $p_\theta(y \mid x)$ | NLL $=$ loss |
| --- | --- | --- |
| regression | $\mathcal{N}(y;\, f_\theta(x),\, \sigma^2)$ | mean squared error |
| binary classification | $\text{Bernoulli}(\sigma(f_\theta(x)))$ | binary cross-entropy |
| multiclass | $\text{Categorical}(\text{softmax}(f_\theta(x)))$ | cross-entropy |
| count | $\text{Poisson}(\exp f_\theta(x))$ | Poisson NLL |

The regression row is a short derivation. Model $p_\theta(y\mid x) =
\mathcal{N}(y; f_\theta(x), \sigma^2)$, substitute the Gaussian density, and drop
$\theta$-independent constants:

$$
-\log p_\theta(y_i\mid x_i) = \frac{(y_i - f_\theta(x_i))^2}{2\sigma^2} +
\tfrac12\log(2\pi\sigma^2) \;\;\propto\;\; (y_i - f_\theta(x_i))^2.
$$

Summed over the data, NLL _is_ the **mean squared error** — never arbitrary, but
the maximum-likelihood loss under Gaussian noise. Cross-entropy has a second
reading: minimizing it minimizes the **Kullback–Leibler divergence** from the
model to the data,

$$
D_{\text{KL}}(p_{\text{data}} \,\|\, p_\theta) = \mathbb{E}_{p_{\text{data}}}\!
\brackets{\log \frac{p_{\text{data}}(y\mid x)}{p_\theta(y\mid x)}},
$$

and since the first term is $\theta$-independent, driving cross-entropy down _is_
pulling the model's distribution toward the true one. Maximum likelihood is
distribution-matching.[^gf-mle]

> **Theorem (MLE is consistent).** Under regularity conditions, $\theta_{\text{MLE}}
> \to \theta$ as $n \to \infty$, and, by the Cramér–Rao bound, no consistent
> estimator has lower asymptotic variance. MLE is asymptotically the most
> data-efficient estimator there is.

We minimize cross-entropy rather than raw 0/1 error for two reasons: it is the
statistically principled objective, and, unlike the piecewise-constant 0/1 error
(whose gradient is zero almost everywhere), it is smooth, so descent has a slope.

## Priors as regularization: MAP versus MLE

MLE asks which parameters make the _data_ most probable, and with high capacity
and little data the answer is often absurd: the degree-9 polynomial threading
every noisy point is the MLE. The Bayesian fix encodes prior beliefs $p(\theta)$
and maximizes the posterior $p(\theta \mid \mathcal{D}) \propto
p(\mathcal{D}\mid\theta)\,p(\theta)$:

> **Definition (MAP estimate).** The mode of the posterior, $\theta_{\text{MAP}} =
> \arg\max_\theta\,\brackets{\log p(\mathcal{D}\mid\theta) + \log p(\theta)}$ —
> maximum likelihood plus a log-prior term pulling the estimate toward
> a priori plausible parameters.

The log-prior _is_ the regularizer. Put a zero-mean Gaussian prior on the weights,
$p(\theta) = \mathcal{N}(\theta; 0, \tau^2 I)$, so up to a constant $\log p(\theta)
= -\tfrac{1}{2\tau^2}\norm{\theta}^2$, and the MAP objective becomes

$$
\theta_{\text{MAP}}
= \arg\max_\theta \brackets{ \textstyle\sum_i \log p_\theta(y_i\mid x_i) - \tfrac{1}{2\tau^2}\norm{\theta}^2 }
= \arg\min_\theta\;\underbrace{-\textstyle\sum_{i} \log p_\theta(y_i\mid x_i)}_{\text{NLL (data term)}} + \underbrace{\frac{1}{2\tau^2}\norm{\theta}^2}_{\text{from the prior}}.
$$

The second term reproduces **$L^2$ regularization** (weight decay) with strength
$\lambda = 1/\tau^2$: a confident prior (small $\tau$) penalizes hard; the limit
$\tau \to \infty$ recovers plain MLE. Each penalty corresponds to a prior:

| Penalty | Prior $p(\theta)$ | Name | Effect |
| --- | --- | --- | --- |
| $\tfrac{\lambda}{2}\norm{\theta}_2^2$ | Gaussian $\mathcal{N}(0, \tau^2 I)$ | $L^2$ / weight decay / ridge | shrinks weights toward $0$ |
| $\lambda\norm{\theta}_1$ | Laplace | $L^1$ / lasso | drives weights to exactly $0$ (sparse) |
| none | uniform (improper) | plain MLE | no shrinkage |

**Every weight penalty is a prior, and every prior is a weight penalty.**[^gf-map] We
develop the mechanics, and why small weights generalize, under
[regularization](/deep-learning/regularization/regularization-overview).

## Hyperparameters and the validation set

Capacity, learning rate, and regularization strength are **hyperparameters**,
chosen by you, not learned by the optimizer. Tuning them on the test set
contaminates the one honest estimate of risk, so split the data three ways:[^chollet-val]

| Split | Tunes | Touched |
| --- | --- | --- |
| train | parameters $\theta$ (by the optimizer) | every step |
| validation | hyperparameters (by you) | each model-selection round |
| test | nothing — estimates final risk | exactly once, at the end |

$$
% caption: The three-way data split. Parameters are fit on train, hyperparameters
% chosen on validation, and the test set (touched once) gives the honest risk
% estimate.
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % a single bar split into three segments
  \fill[acc!18] (0,0) rectangle (7.0,0.9);
  \fill[green!18] (7.0,0) rectangle (9.1,0.9);
  \fill[red!16] (9.1,0) rectangle (10.5,0.9);
  \draw (0,0) rectangle (10.5,0.9);
  \draw (7.0,0) -- (7.0,0.9);
  \draw (9.1,0) -- (9.1,0.9);
  \node[acc] at (3.5,0.45) {train (f\/it parameters)};
  \node[green] at (8.05,0.45) {val.};
  \node[red] at (9.8,0.45) {test};
  % captions under each
  \node[font=\scriptsize, anchor=north] at (3.5,-0.12) {70\%};
  \node[font=\scriptsize, anchor=north] at (8.05,-0.12) {15\%};
  \node[font=\scriptsize, anchor=north] at (9.8,-0.12) {15\%};
\end{tikzpicture}
$$

The discipline matters: most "worked in the notebook, failed in
production" failures trace to a validation set quietly used as a test set, tuned
against until the number stopped being honest. When data is scarce, **$k$-fold
cross-validation** recovers it: partition into $k$ folds, train $k$ times each
holding out a different fold, average the scores, for a less noisy estimate at
$k\times$ the compute.

## How much the gap can be: generalization bounds

The validation set _measures_ the generalization gap; learning theory _bounds_ it
in advance. Every such bound has the same shape:

$$
\underbrace{R(\theta)}_{\text{true risk}} \;\le\; \underbrace{\hat R(\theta)}_{\text{training risk}} \;+\; O\!\parens{\sqrt{\frac{C}{n}}},
$$

where $C$ measures capacity (VC dimension, Rademacher complexity — formal cousins
of polynomial degree) and $n$ is the sample size.

> **Remark (Read the bound as one sentence).** The gap between training error and
> reality grows with capacity $C$ and shrinks with data $n$ — the formal
> counterpart of the U-curve. Push $C$ up without more data and the bound loosens: overfitting
> waiting to happen.

Classical bounds are famously loose for modern networks, whose capacity exceeds
$n$ yet which generalize anyway — a subtlety we take up under
[generalization theory](/deep-learning/theory/generalization-theory).

A way to _watch_ the gap is the **learning curve**: training and validation error
versus training-set size. With few examples the model fits trivially (low
training error, high validation error); as data accumulates, training error rises
toward a floor and validation error falls toward it. Reading the curve diagnoses
the bottleneck:

| Shape | Diagnosis | Remedy |
| --- | --- | --- |
| persistent gap between the curves | high variance — overfitting | more data, or regularize |
| high shared plateau, small gap | high bias — underfitting | more capacity, richer features |
| both low, small gap | well-fit | ship it |

$$
% caption: A learning curve: as the training set grows, training error rises and
% validation error falls, and the shrinking gap is the generalization gap closing.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (0,0) -- (8.2,0) node[right, font=\footnotesize] {training-set size};
  \draw[->, thick] (0,0) -- (0,4.4) node[above, font=\footnotesize] {error};
  % training error: rises from near 0 toward a floor
  \draw[acc, very thick] (0.4,0.35) .. controls (2.5,0.9) and (4.5,1.35) .. (7.7,1.55);
  % validation error: falls from high toward the same floor
  \draw[red, very thick] (0.4,4.0) .. controls (2.6,2.6) and (4.6,1.9) .. (7.7,1.75);
  % the gap bracket at the right
  \draw[green, thick] (7.95,1.55) -- (7.95,1.75);
  \draw[green, thick] (7.85,1.55) -- (8.05,1.55);
  \draw[green, thick] (7.85,1.75) -- (8.05,1.75);
  \node[green, font=\scriptsize, anchor=west] at (8.0,2.15) {gap};
  % curve labels
  \node[acc, font=\footnotesize, anchor=west] at (4.2,0.7) {training error};
  \node[red, font=\footnotesize, anchor=west] at (1.4,1.9) {validation error};
\end{tikzpicture}
$$

## A model-selection workflow

In practice, the theory becomes a procedure:

```algorithm
caption: $\textsc{ModelSelect}(\text{candidates}, \mathcal{D})$ — fit, validate, seal
split $\mathcal{D}$ into train / val / test; seal test
for each hyperparameter setting $h$ do
  fit $\theta_h$ on train by minimizing $\hat R$
  score $\hat R_{\text{val}}(\theta_h)$ on val // never on test
$h^\star \gets \arg\min_h \hat R_{\text{val}}(\theta_h)$
read learning + U-curves: gap $\Rightarrow$ regularize/add data; plateau $\Rightarrow$ add capacity
report $\hat R_{\text{test}}(\theta_{h^\star})$ // test touched exactly once
```

One capacity dial hides inside the loop itself. **Early stopping** (halting when
validation error stops improving) is _implicit_ capacity control: longer training
expresses more of the model's range, so stopping early chooses a smaller effective
capacity without changing the architecture. It is the cheapest regularizer there
is, treated alongside the
[explicit ones](/deep-learning/regularization/regularization-overview).

## Double descent and overparameterization

The U-curve is the right first picture and, for modern networks, an incomplete one.
The last few years overturned the textbook expectation that more capacity than data
must overfit.

**Double descent.** Belkin et al. (2019) and Nakkiran et al. (2019) documented that
as capacity grows _past_ the point where the model exactly fits (interpolates) the
training set, test error, having risen through the classical overfitting regime,
falls _again_ — often below its first minimum. The single U becomes a U followed by
a second descent, with a spike at the **interpolation threshold** where capacity
just equals the number of examples. Model size, data size, and even training time
each trace their own double-descent curve.

**Benign overfitting.** A network with far more parameters than examples can drive
training loss to zero and still generalize, seemingly violating the bias–variance
tradeoff. The resolution is that gradient descent on an overparameterized model does
not pick just any zero-training-loss solution; it is _implicitly biased_ toward
low-norm, smooth ones (Bartlett et al., 2020). The effective capacity that governs
generalization is set by this implicit regularization, not by the raw parameter
count the classical bound $O(\sqrt{C/n})$ uses — and that gap is why those bounds
are so loose for deep networks. The bias–variance tradeoff still holds for the
_effective_ capacity; the parameter count simply stopped being a good proxy for
it.[^doubledescent][^benign]

With the framework in place (data, risk, capacity, the generalization gap, and
the maximum-likelihood losses behind it), we turn to the models, starting with the
[linear model and its one fatal limitation](/deep-learning/foundations/linear-models-and-the-perceptron).

[^gf-erm]: **Goodfellow**, _Deep Learning_, §5.1; §8.1.1 — empirical risk minimization: minimizing average training loss as a surrogate for the inaccessible true risk, and the generalization gap this surrogate opens.
[^gf-nfl]: **Goodfellow**, _Deep Learning_, §5.2.1 — the No-Free-Lunch theorem: averaged over all data-generating distributions every learner ties, so performance comes entirely from an inductive bias matched to the problem.
[^gf-curse]: **Goodfellow**, _Deep Learning_, §5.11.1 — the curse of dimensionality and local-constancy priors: why volume growing as $b^d$ defeats neighbour-based smoothness assumptions in high dimensions.
[^gf-mle]: **Goodfellow**, _Deep Learning_, §5.5 — Maximum Likelihood Estimation: the NLL as the principled loss, its equivalence to minimizing $D_{\text{KL}}$ from model to data, and its asymptotic efficiency.
[^gf-map]: **Goodfellow**, _Deep Learning_, §5.6; §7.1 — MAP estimation and parameter norm penalties: a Gaussian weight prior reduces to $L^2$ weight decay, a Laplace prior to $L^1$ sparsity.
[^chollet-val]: **Chollet**, _Deep Learning with Python_, §4.2 — Evaluating models: the train / validation / test discipline, information leakage from tuning on the test set, and $k$-fold cross-validation when data is scarce.
[^doubledescent]: Belkin, Hsu, Ma, Mandal (2019), _Reconciling modern machine-learning practice and the classical bias–variance trade-off_, PNAS 116; and Nakkiran, Kaplun, Bansal, Yang, Barak, Sutskever (2019), _Deep Double Descent_, arXiv:1912.02292 — test error descending a second time past the interpolation threshold.
[^benign]: Bartlett, Long, Lugosi, Tsigler (2020), _Benign overfitting in linear regression_, PNAS 117 — overparameterized interpolators that generalize, explained by the implicit low-norm bias of the training procedure rather than raw parameter count.