Every loss you minimise is an expectation you cannot compute, estimated from a sample. Understanding what that sentence means — and how wrong the estimate can be — is the difference between running experiments and understanding them.
What we actually want to minimise is the true risk — the average loss over the whole data-generating distribution \(\mathcal{D}\):
\[R(\vt) = \E_{(\vx,y)\sim\mathcal{D}}\big[\ell\big(f_{\vt}(\vx),\,y\big)\big].\]
We cannot compute it. \(\mathcal{D}\) is unknown — it is the process that generates houses, or photographs, or sentences. All we have is a finite sample. So we minimise the empirical risk instead:
\[\hat R(\vt) = \frac1n\sum_{i=1}^{n}\ell\big(f_{\vt}(\vx_i),y_i\big).\]
Three questions follow immediately, and all of them are probability questions:
A probability space is a triple \((\Omega,\mathcal{F},P)\):
Everything else is a consequence. \(P(A^c)=1-P(A)\), because \(A\) and \(A^c\) are disjoint and their union is \(\Omega\). \(P(\emptyset)=0\). \(P(A\cup B)=P(A)+P(B)-P(A\cap B)\), the overlap subtracted once because it was counted twice. Three axioms, an entire subject.
Why is \(\mathcal{F}\) a "collection of subsets" rather than all subsets? Because for continuous \(\Omega\) it is impossible to assign a consistent probability to every subset — there are non-measurable sets. Handling this properly is measure theory, and it is genuinely deferred: it changes nothing about the calculations in Phases A and B, and it belongs after Phase C when you need it for stochastic processes and rigorous concentration arguments. Ask and we will do it, but not yet.
A random variable is a function \(X:\Omega\to\RR\). It is not a variable and it is not random — it is a deterministic function that assigns a number to each outcome. The randomness lives in which \(\omega\) occurs.
A density is not a probability. \(f(x)\) can exceed 1 — a uniform distribution on \([0,0.1]\) has \(f=10\) throughout. Only the area under it is a probability, which is why \(P(X=c)=0\) for any single point of a continuous distribution: the area over a point of zero width is zero. This is why continuous likelihoods can exceed 1 and log-likelihoods can be positive, which surprises people the first time a model reports a "probability" of 4.7.
\[ \E[X] = \sum_x x\,p(x) \quad\text{(discrete)}, \qquad \E[X] = \int_{-\infty}^{\infty} x f(x)\,dx \quad\text{(continuous)}. \]
It is the probability-weighted average value, and physically it is the centre of mass of the distribution.
LOTUS (the law of the unconscious statistician): for any function \(g\),
\[ \E[g(X)] = \sum_x g(x)\,p(x) \quad\text{— you do not need the distribution of } g(X).\]\[ \Var(X) = \E\big[(X-\E[X])^2\big], \qquad \Cov(X,Y) = \E\big[(X-\E X)(Y-\E Y)\big], \qquad \rho_{XY} = \frac{\Cov(X,Y)}{\sqrt{\Var X\,\Var Y}}. \]
The standard deviation is \(\sigma_X=\sqrt{\Var(X)}\), which has the same units as \(X\) — the reason it is reported rather than the variance.
The empirical risk is a sample mean. So the question "is \(\hat R\) close to \(R\)?" is the question "how close is a sample mean to the true mean?". Two inequalities answer it with no assumptions beyond finite moments.
Let \(X_1,\dots,X_n\) be independent with mean \(\mu\) and variance \(\sigma^2\), and \(\bar X_n=\frac1n\sum_i X_i\). Then for any \(\epsilon>0\),
\[ P\big(|\bar X_n-\mu|\ge\epsilon\big) \le \frac{\sigma^2}{n\epsilon^2} \;\xrightarrow[n\to\infty]{}\; 0. \]Proof. By linearity, \(\E[\bar X_n]=\frac1n\sum_i\E[X_i]=\mu\) — the sample mean is unbiased. By independence and the scaling rule,
\[ \Var(\bar X_n) = \frac{1}{n^2}\sum_{i=1}^n \Var(X_i) = \frac{n\sigma^2}{n^2} = \frac{\sigma^2}{n}. \]Apply Chebyshev to \(\bar X_n\) with \(k=\epsilon\). ∎
Note where each hypothesis was used: linearity needed nothing, but the variance step needed independence to kill the covariance terms.
The \(\sigma^2/n\) is the single most important formula in applied statistics. Error shrinks like \(\sigma/\sqrt n\), so quadrupling your data halves your error — an expensive exchange rate, and the reason benchmark differences of 0.2% on a 1000-example test set are noise.
Under the same conditions,
\[ \frac{\bar X_n - \mu}{\sigma/\sqrt{n}} \;\xrightarrow{\;d\;}\; \mathcal{N}(0,1) \quad\text{as } n\to\infty. \]Whatever the shape of the original distribution — skewed, discrete, bimodal — the sample mean becomes Gaussian. This is why the Gaussian is everywhere, and why confidence intervals are \(\pm 1.96\,\sigma/\sqrt n\). The proof needs characteristic functions and is deferred; the figure below is the empirical demonstration.
Now the result that makes modern deep learning possible. The full gradient over \(n\) examples costs \(O(n)\) per step, which is prohibitive. Instead we sample a batch \(\mathcal{B}\) of size \(B\) uniformly at random and use
\[\vg_{\mathcal{B}} = \frac{1}{B}\sum_{i\in\mathcal{B}}\grad_{\vt}\,\ell_i(\vt).\]
Gradient noise is not purely a cost. There is good evidence that it acts as an implicit regulariser: it lets the iterate escape sharp minima and saddle plateaus, and there is a persistent empirical finding that very large batches generalise worse unless the learning rate and schedule are adjusted. The mechanism is still debated, and this is an active research area rather than settled theory — I flag it as such rather than as a fact.
A fair six-sided die is rolled. Let \(X\) be the value shown.
1. \(\E[X]=\frac{1+2+\cdots+6}{6}=\frac{21}{6}=3.5\).
\(\E[X^2]=\frac{1+4+9+16+25+36}{6}=\frac{91}{6}\approx15.1667\).
\(\Var(X)=\frac{91}{6}-3.5^2 = 15.1667-12.25 = \frac{35}{12}\approx 2.9167\).
2. By the rules: \(\E[Y]=2(3.5)+3=10\), \(\Var(Y)=2^2\cdot\frac{35}{12}=\frac{35}{3}
\approx11.667\).
Directly: \(Y\) is uniform on \(\{5,7,9,11,13,15\}\), mean \(\frac{60}{6}=10\) ✓. And
\(\E[Y^2]=\frac{25+49+81+121+169+225}{6}=\frac{670}{6}\approx111.667\), so
\(\Var(Y)=111.667-100=11.667\) ✓.
3. \(\E[S]=3.5+3.5=7\) by linearity (which would hold even for loaded or correlated dice).
\(\Var(S)=\frac{35}{12}+\frac{35}{12}=\frac{35}{6}\approx5.833\) — this one does require independence.
Note \(\sigma_S=\sqrt{5.833}\approx2.415\), while \(\sigma_X\approx1.708\). The sum's spread grew by a
factor of \(\sqrt2\), not 2: independent noise adds in quadrature. That is the same \(\sqrt n\) that governs
everything in this lecture.
Prove that among all constants \(c\), the value minimising \(\E[(X-c)^2]\) is \(c=\E[X]\).
Then explain what this says about (a) why the mean is the "right" summary for squared-error problems, and (b) what a model trained with squared error is actually predicting when the target is noisy.
Define \(g(c)=\E[(X-c)^2]\). Expand using linearity:
\[g(c) = \E[X^2] - 2c\,\E[X] + c^2.\]This is a quadratic in \(c\) with positive leading coefficient, so Lecture 7's machinery applies directly:
\[g'(c) = -2\E[X]+2c = 0 \;\Longrightarrow\; c=\E[X], \qquad g''(c)=2>0,\]so it is the unique global minimum, and the minimum value is \(g(\E[X]) = \E[X^2]-(\E X)^2 = \Var(X)\). ∎
A neat corollary: the best constant predictor has squared error exactly equal to the variance. Variance is the irreducible error of the best constant model.
(a) Whenever your loss is squared error, the optimal single number to output is the mean. (Contrast: the optimal constant under absolute error is the median, and under 0–1 loss it is the mode. The loss function chooses the summary statistic, not your intuition.)
(b) This is the important one. Extend the argument conditionally: for each \(\vx\), the best prediction under squared error is \(\E[Y\mid \mX=\vx]\). So a model trained with MSE is estimating the conditional mean of the target, not a typical or plausible value of it.
Consequences you will actually meet: an MSE-trained image model produces blurry outputs, because the average of all plausible completions is blurry. An MSE-trained forecaster underestimates volatility. If you want a plausible sample rather than an average, you need a different objective — which is precisely the motivation for GANs, diffusion models, and likelihood-based generative models.
The sample variance is often defined with \(n-1\) in the denominator:
\[ s^2 = \frac{1}{n-1}\sum_{i=1}^n (X_i-\bar X)^2. \]Prove that \(\E[s^2]=\sigma^2\), and that using \(n\) instead would give \(\frac{n-1}{n}\sigma^2\) — biased low. Explain intuitively where the lost degree of freedom goes.
Write \(T=\sum_i (X_i-\bar X)^2\). The trick is to insert and remove \(\mu\):
\[X_i-\bar X = (X_i-\mu)-(\bar X-\mu).\]Square and sum, writing \(D_i = X_i-\mu\) and \(\bar D = \bar X - \mu\):
\[T = \sum_i D_i^2 - 2\bar D\sum_i D_i + n\bar D^2 = \sum_i D_i^2 - 2\bar D(n\bar D) + n\bar D^2 = \sum_i D_i^2 - n\bar D^2,\]using \(\sum_i D_i = n\bar D\). Now take expectations, using \(\E[D_i^2]=\sigma^2\) and \(\E[\bar D^2]=\Var(\bar X)=\sigma^2/n\):
\[\E[T] = n\sigma^2 - n\cdot\frac{\sigma^2}{n} = (n-1)\sigma^2.\]So \(\E\!\left[\frac{T}{n-1}\right]=\sigma^2\) ✓, while \(\E\!\left[\frac{T}{n}\right] =\frac{n-1}{n}\sigma^2<\sigma^2\). ∎
Where the degree of freedom goes. The deviations are measured from \(\bar X\), which was computed from the same data and is therefore pulled towards the sample. By the previous exercise, \(\bar X\) is the constant that minimises \(\sum(X_i-c)^2\), so \(\sum(X_i-\bar X)^2 \le \sum(X_i-\mu)^2\) always — the sum of squared deviations about the sample mean is systematically too small. Dividing by \(n-1\) corrects exactly for that.
The residuals also satisfy one linear constraint, \(\sum_i(X_i-\bar X)=0\): given any \(n-1\) of them the last is determined. Only \(n-1\) are free, hence the name.
Relevance. The same phenomenon is why training error underestimates test error: the parameters were fitted to the very data you are evaluating on. Least squares with \(d\) parameters has \(n-d\) residual degrees of freedom, and the unbiased noise estimate is \(\frac{\|\vr\|^2}{n-d}\), not \(\frac{\|\vr\|^2}{n}\). Overfitting is this bias taken to an extreme.
Coding + analysis. Investigate how gradient noise interacts with the learning rate.
lstsq.import numpy as np
rng = np.random.default_rng(0)
n, d = 4096, 10
X = rng.normal(size=(n, d)); w_true = rng.normal(size=d)
y = X @ w_true + 2.0*rng.normal(size=n)
w_star = np.linalg.lstsq(X, y, rcond=None)[0]
def sgd(B, eta, epochs=30, seed=1):
r = np.random.default_rng(seed); w = np.zeros(d)
for _ in range(epochs):
perm = r.permutation(n)
for s in range(0, n, B):
idx = perm[s:s+B]
g = 2 * X[idx].T @ (X[idx] @ w - y[idx]) / len(idx)
w = w - eta*g
if not np.isfinite(w).all(): return None
return w
print("--- fixed eta ---")
for B in (1, 8, 64, 512, 4096):
w = sgd(B, 0.002)
print(f"B={B:5d} dist to optimum = "
f"{'DIVERGED' if w is None else f'{np.linalg.norm(w-w_star):.5f}'}")
print("\\n--- linear scaling rule: eta proportional to B ---")
for B in (1, 8, 64, 512, 4096):
w = sgd(B, 0.002*B/8)
print(f"B={B:5d} eta={0.002*B/8:.5f} dist = "
f"{'DIVERGED' if w is None else f'{np.linalg.norm(w-w_star):.5f}'}")
print("\\n--- stationary noise floor at B=1 ---")
for eta in (0.0002, 0.0005, 0.001, 0.002):
w = sgd(1, eta, epochs=60)
if w is None: print(f"eta={eta}: DIVERGED"); continue
tail = []
r = np.random.default_rng(7)
for _ in range(4000): # keep stepping, record the wander
i = r.integers(0, n)
g = 2 * X[i] * (X[i] @ w - y[i])
w = w - eta*g; tail.append(w.copy())
tail = np.array(tail)
print(f"eta={eta:.4f} mean dist {np.linalg.norm(tail.mean(0)-w_star):.5f}"
f" stationary sd {np.sqrt(tail.var(0).sum()):.5f}")2. With a fixed \(\eta\), larger batches get closer to the optimum for the same number of epochs — the steps are less noisy — but they take far fewer steps, so per unit of compute the small batches usually make more progress early. Full batch (\(B=4096\)) with a small \(\eta\) barely moves in 30 epochs, because 30 epochs is only 30 steps.
3. Under linear scaling the large-batch runs improve dramatically and the final distances become comparable across \(B\) — until \(\eta\) approaches \(2/\lambda_{\max}\) of the Hessian \(2\mX^\top\mX/n\) (Lecture 11), at which point the largest-batch run diverges. That is precisely the documented failure of the linear scaling rule at very large batch: eventually stability, not noise, becomes the binding constraint.
4. With constant \(\eta\), SGD does not converge to a point. It reaches a stationary distribution around \(\vw^\star\): the mean of the iterates sits at the optimum (unbiased, as proved above) but the spread does not shrink. Measured, the stationary standard deviation scales roughly as \(\sqrt\eta\), which is what the Ornstein–Uhlenbeck approximation predicts — the noise injected per step is \(O(\eta^2\sigma^2)\) and the restoring force is \(O(\eta\lambda)\), giving a stationary variance of order \(\eta\sigma^2/\lambda\).
Consequence: constant-learning-rate SGD has a noise floor. To actually converge you must decay \(\eta\) — which is why every training recipe has a schedule, and why the Robbins–Monro conditions \(\sum\eta_t=\infty\), \(\sum\eta_t^2<\infty\) are the classical requirement for almost-sure convergence. The characteristic loss curve that plateaus and then drops sharply when the learning rate is cut is exactly this noise floor being lowered.
Next: the final lecture of Phase A. Conditional probability and Bayes' theorem, the distributions you will meet constantly, and maximum likelihood — which will let us finally derive squared error, cross-entropy, and ridge regression from a single principle.