Generalization
The Methodology lecture described a classical U-curve: bias falls and variance rises as a model gains capacity, and their sum bottoms out before the model fits the training data exactly. The Linear Model lecture left open which solution an algorithm finds when a model has more parameters than data points and infinitely many hypotheses fit exactly. The selected solution helps determine whether the U-curve continues past the interpolation threshold.
A model with capacity to spare has many perfect fits, and its generalization depends on which one is selected. We can select among fits explicitly with a prior or implicitly through the optimizer’s trajectory.
Regularization as a Prior
Reducing the parameter count is one way to favor simple models. Regularization does so without changing the parameter count. Maximum likelihood selects the weights that make the data most probable. Maximum a posteriori (MAP) estimation adds a belief about the weights themselves, using Bayes’ rule from Unit 1: \[ \Pr(\mathbf{w} \mid \text{data}) \propto \Pr(\text{data} \mid \mathbf{w}) \cdot \Pr(\mathbf{w}). \] A zero-centered prior on a weight vector \(\mathbf{w} \in \mathbb{R}^d\) assigns higher probability to small entries.
Claim: Under a Gaussian prior \(\mathbf{w} \sim \mathcal{N}(\mathbf{0}, \tau^2 \mathbf{I})\), where \(\tau^2 > 0\) is the prior variance of each weight, and the Gaussian noise model of the Mean Squared Error lecture, maximizing the posterior is equivalent to minimizing mean squared error plus a penalty on the weights’ squared length, \(\mathcal{L}(\mathbf{w}) + \lambda\|\mathbf{w}\|_2^2\), with strength \(\lambda = \sigma^2/(n\tau^2)\).
Proof of Claim
Take logs of both sides of Bayes’ rule, dropping the normalizing constant, which does not depend on \(\mathbf{w}\): \[ \log \Pr(\mathbf{w}\mid\text{data}) = \log \Pr(\text{data}\mid\mathbf{w}) + \log \Pr(\mathbf{w}) + \text{const}. \] The Mean Squared Error lecture already computed the first term for a hypothesis \(f\) with weights \(\mathbf{w}\) and Gaussian noise of variance \(\sigma^2\): \[ \log\Pr(\text{data}\mid\mathbf{w}) = -\frac{1}{2\sigma^2}\sum_{i=1}^n\big(y^{(i)}-f(\mathbf{x}^{(i)})\big)^2 + \text{const}. \] The second term is that same Gaussian density formula applied to \(\mathbf{w}\) instead of the noise, with \(\tau^2\) in place of \(\sigma^2\). The prior treats the \(d\) coordinates of \(\mathbf{w}\) as independent, so their densities multiply and the logarithm turns that product into a sum of squares: \[ \log\Pr(\mathbf{w}) = -\sum_{j=1}^d \frac{w_j^2}{2\tau^2} + \text{const} = -\frac{1}{2\tau^2}\|\mathbf{w}\|_2^2 + \text{const}. \] Add the two and negate, since maximizing the posterior is the same as minimizing its negative: \[ \arg\max_\mathbf{w} \log\Pr(\mathbf{w}\mid\text{data}) = \arg\min_\mathbf{w} \left[\frac{1}{2\sigma^2}\sum_{i=1}^n\big(y^{(i)}-f(\mathbf{x}^{(i)})\big)^2 + \frac{1}{2\tau^2}\|\mathbf{w}\|_2^2\right]. \] Multiplying through by the positive constant \(2\sigma^2/n\) leaves the minimizer alone and turns the first term into the mean squared error \(\mathcal{L}(\mathbf{w}) = \frac1n\sum_i (y^{(i)} - f(\mathbf{x}^{(i)}))^2\): \[ \arg\min_\mathbf{w} \left[\mathcal{L}(\mathbf{w}) + \lambda\|\mathbf{w}\|_2^2\right], \qquad \lambda = \frac{\sigma^2}{n\tau^2}. \]The regularization strength \(\lambda\) is large when the noise variance \(\sigma^2\) is large (unreliable labels, so lean on the prior), when the prior variance \(\tau^2\) is small (a firm belief that weights are small), and when \(n\) is small. The dependence on \(n\) reflects that the prior is fixed while the likelihood accumulates one term per data point, so the equivalent penalty weakens as the dataset grows.
This is ridge regression, and in the gradient-descent form of the Gradient Descent lecture it is weight decay, since the penalty’s gradient \(2\lambda\mathbf{w}\) shrinks every weight toward zero at each step. Using a Laplace prior on each weight instead of a Gaussian prior produces an \(\ell_1\) penalty \(\lambda\|\mathbf{w}\|_1\), which is lasso. The Laplace density carries \(|w_j|\) in its exponent rather than \(w_j^2\), so the log-prior penalty keeps a constant slope right up to zero instead of flattening out there, and a coordinate whose evidence is weaker than that slope is pushed to exactly zero: \(\ell_1\) produces genuinely sparse weight vectors and \(\ell_2\) does not. Choosing a penalty corresponds to choosing a prior, just as choosing a loss corresponds to choosing a noise model. The final unit uses the same maximum-likelihood connection for policy gradients.
An explicit penalty is tuned on a validation set and can be set to zero. An optimizer can also impose an implicit preference even when the loss has no penalty.
The Classical U-Curve
Recall the decomposition the Methodology lecture built. Treat the training set itself as random, refit on each draw, and the expected squared error of the fitted hypothesis \(\hat f\) at a test point splits into three pieces: \[ \mathbb{E}\big[(y - \hat f(x))^2\big] = \underbrace{\big(\mathbb{E}[\hat f(x)] - f^*(x)\big)^2}_{\text{bias}^2} + \underbrace{\mathrm{Var}(\hat f(x))}_{\text{variance}} + \underbrace{\mathrm{Var}(y \mid x)}_{\text{noise}} . \] Bias is how far the average fit sits from the truth \(f^*\), variance is how much the fit swings from one training set to the next, and the noise term is the floor no model beats. As capacity grows, bias falls and variance rises, since a richer class can bend closer to the truth but has more room to chase this training set’s noise, and their sum traces the U.
Keep the number of training points \(n\) fixed and let \(d\) be the number of features the model uses, so the design matrix is \(\mathbf{X}\in\mathbb{R}^{n\times d}\). The Methodology lecture called \(d = n\) the interpolation threshold: there the model has exactly enough freedom to hit every training label, and training error drops to zero. The classical U describes models to the left of that line and predicts that variance and test error continue increasing to the right. Testing that extrapolation means building models with \(d > n\), the question the Linear Model lecture left open.
Which Interpolating Solution Do We Find?
When \(d > n\), the design matrix has more columns than rows and \(\mathbf{X}\mathbf{w}=\mathbf{y}\) has a subspace of exact solutions. All have zero training error, but they can generalize very differently. Gradient descent started from \(\mathbf{w}^{(0)}=\mathbf{0}\) and the closed-form pseudoinverse both return the same weights \(\hat{\mathbf{w}} \in \mathbb{R}^d\), the minimum-norm solution: \[ \hat{\mathbf{w}} = \arg\min\big\{\|\mathbf{w}\|_2 \;:\; \mathbf{X}\mathbf{w}=\mathbf{y}\big\} . \]
We find one by hand, as we will in class. Take the single equation \(w_1 + 2w_2 = 3\): one equation in two unknowns, with an entire line of exact solutions.
In the plot, the gray line is the set of exact fits, and the minimum-norm solution is the point on it closest to the origin, found the same way the Linear Model lecture found a projection: drop a perpendicular from \(\mathbf{0}\) onto the line. Write the constraint as \(\mathbf{a}^\top\mathbf{w}=3\) for \(\mathbf{a}=(1,2)\), and the foot of that perpendicular is: \[ \hat{\mathbf{w}} = \mathbf{a}\,(\mathbf{a}^\top\mathbf{a})^{-1}\cdot 3 = \frac{3}{1^2 + 2^2}\,(1,2) = \tfrac{3}{5}(1,2) = (0.6,\, 1.2) . \] It satisfies the constraint, since \(0.6 + 2.4 = 3\), and its norm \(\sqrt{0.6^2 + 1.2^2} = \sqrt{1.8} \approx 1.34\) is smaller than that of the equally exact fit \((0, 1.5)\), drawn in cardinal, whose norm is \(1.5\). That formula is the pseudoinverse from the Optimization lecture, applied to an underdetermined system: \(\hat{\mathbf{w}} = \mathbf{X}^+\mathbf{y}\), the same expression that solved least squares, now selecting the minimum-norm solution instead of the closest-fit one.
With no penalty or prior, gradient descent’s update directions determine which exact fit it reaches.
Claim: Gradient descent on mean squared error, started at \(\mathbf{w}^{(0)}=\mathbf{0}\), keeps every iterate in the span of the data points \(\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(n)}\) (the row space of \(\mathbf{X}\)).
Proof of Claim
The Optimization lecture computed the gradient of the mean squared error of a linear model. Writing \(\mathbf{r} = \mathbf{X}\mathbf{w} - \mathbf{y} \in \mathbb{R}^n\) for the residual vector, whose \(i\)th entry \(r^{(i)}\) is the error on data point \(i\), that gradient expands as a combination of the data points: \[ \nabla_\mathbf{w}\mathcal{L}(\mathbf{w}) = \frac{2}{n}\mathbf{X}^\top(\mathbf{X}\mathbf{w}-\mathbf{y}) = \frac{2}{n}\mathbf{X}^\top\mathbf{r} = \frac{2}{n}\sum_{i=1}^n r^{(i)}\,\mathbf{x}^{(i)}, \] where the last equality is the outer-product view of a matrix-vector product: \(\mathbf{X}^\top\) has the data points as its columns, so \(\mathbf{X}^\top\mathbf{r}\) weights each data point by its own residual and adds them up. Now induct on \(t\). The start \(\mathbf{w}^{(0)} = \mathbf{0}\) is in the span, and if \(\mathbf{w}^{(t)}\) is in the span then so is \(\mathbf{w}^{(t+1)} = \mathbf{w}^{(t)} - \alpha\nabla_\mathbf{w}\mathcal{L}(\mathbf{w}^{(t)})\), because we subtracted one more combination of the same \(n\) vectors.Now compare that against the set of exact fits. Moving from one exact fit to another means adding a vector \(\mathbf{z}\) with \(\mathbf{X}\mathbf{z}=\mathbf{0}\), so \(\langle\mathbf{x}^{(i)}, \mathbf{z}\rangle = 0\) for every data point. These null-space directions are perpendicular to the row space containing every gradient-descent iterate. The \(n\)-dimensional span therefore meets the \((d-n)\)-dimensional set of exact fits in exactly one point: the minimum-norm solution. Stochastic gradient descent inherits the whole argument, since a minibatch gradient is a combination of a subset of the same data points. This is implicit regularization: the optimizer’s own trajectory, rather than a term added to the loss, decides which of infinitely many perfect fits we end up with.
This implicit preference matches the minimum-norm preference from a zero-centered Gaussian prior. Near the interpolation threshold, however, that solution can have large test error.
Conditioning at the Interpolation Threshold
To pass the interpolation threshold, keep the true signal confined to a few of the \(d\) features, treat the rest as pure noise, and refit the minimum-norm solution as \(d\) grows toward and beyond \(n\). The test error spikes near \(d = n\), far above the error on either side, then falls again as \(d\) grows further. The class demo runs this sweep and measures the spike.
Past the threshold, every model fits the training set exactly, but different values of \(d\) produce interpolating weights of very different sizes. The singular values of \(\mathbf{X}\) determine those sizes.
The mechanism is the condition number from the Optimization lecture, applied to test error instead of to precision. Recall that the pseudoinverse builds the minimum-norm solution by inverting each singular value in place: \[ \mathbf{X}^+ = \sum_{i=1}^n \frac{1}{\sigma_i}\mathbf{v}_i\mathbf{u}_i^\top, \qquad \hat{\mathbf{w}} = \mathbf{X}^+\mathbf{y} , \] where \(\sigma_1 \geq \cdots \geq \sigma_n > 0\) are the singular values of \(\mathbf{X}\) (not the noise level \(\sigma^2\) from the prior section), and \(\mathbf{u}_i \in \mathbb{R}^n\) and \(\mathbf{v}_i \in \mathbb{R}^d\) are its left and right singular vectors. A small singular value \(\sigma_i\) corresponds to a direction along which the training features barely vary, so the corresponding weight is weakly constrained. Dividing by \(\sigma_i\) amplifies label noise into a large coefficient in \(\hat{\mathbf{w}}\), increasing error on test points that vary in that direction. A standard random-matrix approximation for the smallest singular value of \(\mathbf{X}\) with independent standard Gaussian entries is: \[ \sigma_{\min} \approx \big|\sqrt{d}-\sqrt{n}\big| . \] This edge approximation approaches zero as \(d\) approaches \(n\) and grows on either side. A finite square Gaussian matrix is almost surely nonsingular, but its smallest singular value is typically much smaller near \(d=n\) than away from the threshold. The factor \(1/\sigma_{\min}\) in the pseudoinverse, and therefore the condition number \(\kappa(\mathbf{X}) = \sigma_{\max}/\sigma_{\min}\), is consequently largest near the interpolation threshold.
For the Gaussian design above, increasing \(d\) past \(n\) moves the typical smallest singular value away from zero. The minimum-norm solution can then distribute an interpolating fit across more directions, reducing the largest coefficients. This produces the second descent. It does not continue forever: the fit still lies in the span of the \(n\) data points, an \(n\)-dimensional slice of the \(\mathbb{R}^d\) containing \(\mathbf{w}^*\), so it captures a fraction of the signal that shrinks like \(n/d\). Eventually the missed signal outweighs the falling noise, and the error increases again. The small model using only the informative features still has the lowest error in this example. The second descent makes very large models usable despite the monotone increase predicted by extrapolating the classical U-curve. Problem 14 replaces the hard inversion of each singular value by ridge regression’s soft spectral filter. It asks which part of the interpolation spike that filter suppresses and which signal it sacrifices.
This behavior is called double descent and extends the Methodology lecture’s U-curve past the interpolation threshold. Past the interpolation threshold, more parameters need not mean worse generalization. In the Gaussian design above, increasing \(d\) tends to improve conditioning, so the variance term follows the spectrum rather than parameter count alone.
The Structure of Learned Parameters
This closes the Neural Networks unit. Modern networks can have far more parameters than training points, placing them on the right side of this curve. Their implicit regularization and conditioning help explain their generalization.
The next lecture uses the SVD to study the structure of learned weights and representations. It finds the best rank-\(k\) approximation of a matrix by discarding its smallest singular values rather than dividing by them.
When several parameter vectors fit the training data perfectly, the optimizer’s implicit preference determines which one we get, so parameter count alone does not determine effective capacity.