A Machine-Learning Refresher

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 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,

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.

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:

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.

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.

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.¹

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.

• 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.

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.²

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:

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:

Smoothness-based methods (points close together have similar labels) fail because in high dimensions almost nothing is close to anything.³

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:

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:

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.

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.

(Deep networks complicate this picture; we revisit double descentlater, 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:

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

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:

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:

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:

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,

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.⁴

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 )$:

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 )=-\frac{1}{2{\tau }^2}\Vert \theta {\Vert }^2$, and the MAP objective becomes

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:

Every weight penalty is a prior, and every prior is a weight penalty.⁵ We develop the mechanics, and why small weights generalize, under regularization.

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:⁶

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:

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

Classical bounds are famously loose for modern networks, whose capacity exceeds $n$ yet which generalize anyway — a subtlety we take up under 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:

A model-selection workflow

In practice, the theory becomes a procedure:

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.

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.⁷⁸

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.