Generalization

In Model Evaluation, we measured success by predictions on new examples. Training error alone could not tell us how well a model would perform there. When several models fit the same training labels, we also need to understand how choosing among those fits affects new predictions.

A training dataset contains both signal, the pattern we want to learn, and noise, unpredictable variation in its labels. We will study linear models so that we can calculate how this noise changes the fitted weights and the predictions they produce. The features may already be nonlinear transformations of the original inputs, as in the preceding readings.

How can fitting noisy training data lead to good predictions on new examples?

We will examine which fit is selected and how strongly it responds to label noise, then use those calculations to understand regularization and the effect of adding features.

Choosing a Fit

Let \(\mathbf X\in\mathbb R^{n\times d}\) contain \(d\) features for each of \(n\) training examples, and let \(\mathbf y\in\mathbb R^n\) contain their labels. We predict \(\mathbf X\mathbf w\) using weights \(\mathbf w\in\mathbb R^d\). As in Least Squares, the features may be nonlinear functions of the original inputs.

We assume full rank \(r=\min(n,d)\) here, with positive singular values \(\sigma_1\ge\cdots\ge\sigma_r>0\). For \(i=1,\ldots,r\), the orthonormal vectors \(\mathbf v_i\in\mathbb R^d\) give directions in parameter space, and \(\mathbf u_i\in\mathbb R^n\) give directions in training-prediction space. With this notation, the singular value decomposition is \[ \mathbf X=\sum_{i=1}^r\sigma_i\mathbf u_i\mathbf v_i^\top. \]

Decompose the labels into the directions our model can fit and a perpendicular remainder: \[ \mathbf y=\sum_{i=1}^r(\mathbf u_i^\top\mathbf y)\mathbf u_i+\mathbf y_\perp. \] Here \(\mathbf y_\perp\) is perpendicular to every \(\mathbf u_i\). The sum lies in the column space of \(\mathbf X\). The component \(\mathbf y_\perp\) lies outside that space, so it remains as residual error for every least-squares fit.

Similarly, let \(c_i=\mathbf v_i^\top\mathbf w\) for \(i=1,\ldots,r\) and let \(\mathbf w_\perp\) be the weight component perpendicular to every \(\mathbf v_i\). Then \[ \mathbf w=\sum_{i=1}^r c_i\mathbf v_i+\mathbf w_\perp. \] Since \(\mathbf X\mathbf v_i=\sigma_i\mathbf u_i\) and \(\mathbf X\mathbf w_\perp=\mathbf0\), the training predictions are \[ \mathbf X\mathbf w=\sum_{i=1}^r\sigma_i c_i\mathbf u_i. \] Subtracting the label decomposition and applying the Pythagorean theorem gives \[ \|\mathbf X\mathbf w-\mathbf y\|_2^2 =\sum_{i=1}^r(\sigma_i c_i-\mathbf u_i^\top\mathbf y)^2 +\|\mathbf y_\perp\|_2^2. \] We minimize this error by setting each \(c_i=(\mathbf u_i^\top\mathbf y)/\sigma_i\). The remaining training error is \(\|\mathbf y_\perp\|_2^2\); the component \(\mathbf w_\perp\) is free because it leaves the predictions unchanged. Setting \(\mathbf w_\perp=\mathbf0\) gives the minimum-norm fit \[ \widehat{\mathbf w}=\mathbf X^+\mathbf y =\sum_{i=1}^r\frac{\mathbf u_i^\top\mathbf y}{\sigma_i}\mathbf v_i. \] Every least-squares minimizer has the form \[ \mathbf w=\widehat{\mathbf w}+\mathbf w_\perp, \qquad \mathbf X\mathbf w_\perp=\mathbf0. \] The two perpendicular components explain the three cases under our full-rank assumption:

• If \(d<n\), then \(\mathbf w_\perp=\mathbf0\) and the fit is unique, but \(\mathbf y_\perp\) may leave positive training error.
• If \(d=n\), both perpendicular components are zero: the fit is unique and exact.
• If \(d>n\), then \(\mathbf y_\perp=\mathbf0\), so every label can be fitted exactly, while the free null-space component \(\mathbf w_\perp\) gives infinitely many fits.

In the plot, the horizontal coefficient is fixed by the training labels. Changing the vertical null-space component moves along the line of equally good fits. The segment from the origin shows the weight norm.

All equally good fits lie on a vertical line in parameter space. The closest point to the origin has zero null-space component. Moving up or down increases the weight norm while training error stays zero.

Why choose small weights?

When the data cannot distinguish among these fits, how should we choose? The training examples give us no information about the true weights in the null-space directions. A conservative choice is to set these undetermined components to zero.

There is also a reason to associate small weights with simpler predictions. For a linear prediction \(f_{\mathbf w}(\mathbf x)=\mathbf x^\top\mathbf w\), changing the feature vector by \(\mathbf h\) changes the prediction by at most

\[ \begin{aligned} |f_{\mathbf w}(\mathbf x+\mathbf h)-f_{\mathbf w}(\mathbf x)| &=|\mathbf w^\top\mathbf h|\\ &\le\|\mathbf w\|_2\|\mathbf h\|_2. \end{aligned} \]

Thus smaller weights limit sensitivity to changes in the features. This does not guarantee good predictions: the true pattern could depend on a direction missing from the training examples. But it gives us a meaningful notion of simplicity when the features have comparable scales. For nonlinear feature maps, the bound concerns distances between feature vectors, not necessarily distances between the original inputs.

The minimum-norm least-squares fit \(\widehat{\mathbf w}=\mathbf X^+\mathbf y\) sets \(\mathbf w_\perp=\mathbf0\). The orthogonality calculation from Least Squares gives \[ \|\widehat{\mathbf w}+\mathbf w_\perp\|_2^2 =\|\widehat{\mathbf w}\|_2^2+\|\mathbf w_\perp\|_2^2. \] Every nonzero null-space component increases the weight norm while keeping the training fit fixed.

Minimum norm removes weight that does not help fit the observed labels. But the remaining weights still have to respond to the labels we observed, including their noise. We will now calculate how much noise changes the fitted weights.

Fitting Noise

Suppose the training labels contain a linear signal with true weights \(\mathbf w^\star\) and additive noise \(\boldsymbol\varepsilon\):

\[ \mathbf y=\mathbf X\mathbf w^\star+\boldsymbol\varepsilon. \]

We hold \(\mathbf X\) fixed and assume the noise has mean zero and covariance \(\tau^2\mathbf I\):

\[ \mathbb E[\boldsymbol\varepsilon]=\mathbf0, \qquad \mathbb E[\boldsymbol\varepsilon\boldsymbol\varepsilon^\top] =\tau^2\mathbf I. \]

Here \(\tau\) is the noise standard deviation. The noise need not be Gaussian for the calculations below.

Before calculating the error in the fitted weights, we need to connect it to predictions. For a new feature vector \(\mathbf x\), the prediction error relative to the underlying signal is \(\mathbf x^\top(\widehat{\mathbf w}-\mathbf w^\star)\). Its size depends on which weight directions occur in new inputs. If the new feature vector \(\mathbf x\) is independent of the training noise and has \(\mathbb E[\mathbf x\mathbf x^\top]=\mathbf I\), then for fixed fitted weights

\[ \begin{aligned} \mathbb E_{\mathbf x} \bigl[(\mathbf x^\top\widehat{\mathbf w} -\mathbf x^\top\mathbf w^\star)^2\bigr] &=(\widehat{\mathbf w}-\mathbf w^\star)^\top \mathbb E[\mathbf x\mathbf x^\top] (\widehat{\mathbf w}-\mathbf w^\star)\\ &=\|\widehat{\mathbf w}-\mathbf w^\star\|_2^2. \end{aligned} \]

Under this isotropic test-feature assumption, squared weight error equals expected error in predicting the noiseless signal. Averaging over the training noise will preserve this equality. For other test-feature distributions, the second-moment matrix \(\mathbb E[\mathbf x\mathbf x^\top]\) weights the errors by their effect on new predictions. We can now calculate weight error by separating the effect of the signal from the effect of label noise. Substituting the noisy labels into our formula for minimum-norm least squares gives

\[ \begin{aligned} \widehat{\mathbf w} &=\sum_{i=1}^r \frac{\mathbf u_i^\top(\mathbf X\mathbf w^\star+\boldsymbol\varepsilon)} {\sigma_i}\mathbf v_i\\ &=\sum_{i=1}^r \left( \mathbf v_i^\top\mathbf w^\star +\frac{\mathbf u_i^\top\boldsymbol\varepsilon}{\sigma_i} \right)\mathbf v_i. \end{aligned} \]

Let \(\mathbf w_\perp^\star\) be the component of the true weights perpendicular to the row space of \(\mathbf X\). Subtracting the true weights yields

\[ \widehat{\mathbf w}-\mathbf w^\star =-\mathbf w_\perp^\star +\sum_{i=1}^r \frac{\mathbf u_i^\top\boldsymbol\varepsilon}{\sigma_i}\mathbf v_i. \]

There are two different ways the weights can be wrong. The component \(\mathbf w_\perp^\star\) of the true signal cannot be identified from the training features. The other term is noise in the observed labels, amplified along the singular directions.

To understand the noise term, compare the fitted and true weights along a single direction \(\mathbf v_i\). The labels contain the corresponding signal plus noise: \[ \mathbf u_i^\top\mathbf y =\sigma_i\mathbf v_i^\top\mathbf w^\star +\mathbf u_i^\top\boldsymbol\varepsilon. \] Least squares matches this label component, so \(\sigma_i\mathbf v_i^\top\widehat{\mathbf w}=\mathbf u_i^\top\mathbf y\). Subtracting the signal gives \[ \underbrace{\mathbf v_i^\top(\widehat{\mathbf w}-\mathbf w^\star)}_{\text{weight error}} =\frac1{\sigma_i} \underbrace{\mathbf u_i^\top\boldsymbol\varepsilon}_{\text{label noise}}. \] A weight change along \(\mathbf v_i\) changes the training predictions by only \(\sigma_i\) times as much along \(\mathbf u_i\). When \(\sigma_i\) is small, matching a given label error therefore requires a large weight error. The same amount of label noise produces more variable fitted weights.

The figure compares these two errors on the same horizontal scale. Each dot represents one draw of the label noise: the top row shows \(\mathbf u_i^\top\boldsymbol\varepsilon\), and the bottom row shows the resulting \(\mathbf v_i^\top(\widehat{\mathbf w}-\mathbf w^\star)\). Zero means no error. The label noise stays fixed as \(\sigma_i\) changes; the weight errors are divided by \(\sigma_i\). For the figure, the noise is Gaussian with standard deviation \(\tau=0.2\).

The top row shows label noise along one prediction direction. The bottom row shows the resulting weight error on the same scale: each label-noise component is divided by the singular value. Smaller singular values spread the weight errors farther from zero.

Claim: The expected squared weight error of minimum-norm least squares is \[ \mathbb E\|\widehat{\mathbf w}-\mathbf w^\star\|_2^2 =\|\mathbf w_\perp^\star\|_2^2 +\tau^2\sum_{i=1}^r\frac1{\sigma_i^2}. \]

Proof

The vectors \(\mathbf v_1,\ldots,\mathbf v_r\) are orthonormal and perpendicular to \(\mathbf w_\perp^\star\). By the Pythagorean theorem,

\[ \|\widehat{\mathbf w}-\mathbf w^\star\|_2^2 =\|\mathbf w_\perp^\star\|_2^2 +\sum_{i=1}^r \frac{(\mathbf u_i^\top\boldsymbol\varepsilon)^2}{\sigma_i^2}. \]

The expected squared noise component in each unit direction is

\[ \begin{aligned} \mathbb E[(\mathbf u_i^\top\boldsymbol\varepsilon)^2] &=\mathbf u_i^\top \mathbb E[\boldsymbol\varepsilon\boldsymbol\varepsilon^\top] \mathbf u_i\\ &=\tau^2\mathbf u_i^\top\mathbf u_i\\ &=\tau^2. \end{aligned} \]

Taking expectations proves the claim.

The first term, missing signal, is zero when \(d\le n\) under our full-rank assumption. When \(d>n\), it need not be zero: minimum norm cannot recover a true null-space component without additional information. The second term, fitted noise, grows when singular values are small.

Under the isotropic test-feature assumption established above, this formula also gives the expected error in predicting the noiseless signal.

So far, we chose the smallest weights among the best training fits. But the best training fit can still demand enormous weights to explain tiny changes in noisy labels. Can we allow a little more training error to reduce this sensitivity?

Regularization

Ridge regression makes the preference for small weights explicit. For \(\lambda>0\), it chooses

\[ \widehat{\mathbf w}_\lambda =\arg\min_{\mathbf w} \underbrace{\frac1n\|\mathbf X\mathbf w-\mathbf y\|_2^2}_{\text{training error}} +\underbrace{\lambda\|\mathbf w\|_2^2}_{\text{penalty}}. \]

Unlike minimum-norm least squares, ridge allows the training error to increase if doing so reduces the weight norm. The parameter \(\lambda\) controls this tradeoff.

Our SVD decomposition makes the optimization simple. Recall that

\[ \mathbf w=\sum_{i=1}^r c_i\mathbf v_i+\mathbf w_\perp. \]

Using the training-error decomposition above, the ridge objective becomes

\[ \frac1n\sum_{i=1}^r (\sigma_i c_i-\mathbf u_i^\top\mathbf y)^2 +\frac1n\|\mathbf y_\perp\|_2^2 +\lambda\sum_{i=1}^r c_i^2 +\lambda\|\mathbf w_\perp\|_2^2. \]

The null-space term is minimized at \(\mathbf w_\perp=\mathbf0\). For each \(c_i\), differentiating and setting the result to zero gives

\[ \frac2n\sigma_i(\sigma_i c_i-\mathbf u_i^\top\mathbf y) +2\lambda c_i=0. \]

Therefore,

\[ \widehat{\mathbf w}_\lambda =\sum_{i=1}^r \frac{\sigma_i}{\sigma_i^2+n\lambda} (\mathbf u_i^\top\mathbf y)\mathbf v_i. \]

Compare the coefficient with minimum-norm least squares:

\[ \underbrace{\frac{\sigma_i}{\sigma_i^2+n\lambda}}_{\text{ridge response}} = \underbrace{\frac1{\sigma_i}}_{\text{least-squares response}} \underbrace{\frac{\sigma_i^2}{\sigma_i^2+n\lambda}}_{\text{shrinkage factor}}. \]

Ridge suppresses directions with small singular values most strongly. As \(\lambda\) approaches zero, the ridge solution approaches \(\mathbf X^+\mathbf y\).

The figure keeps the same label noise, error scale, and singular direction. Gray crosses show the least-squares weight errors; teal dots show the ridge weight errors. Here the true weight component \(\mathbf v_i^\top\mathbf w^\star\) is \(1\). Shrinking that component toward zero makes the mean error negative, while reducing the spread caused by noise.

The top row shows the same label noise. The bottom row compares ridge weight errors with least-squares weight errors on the same scale. Ridge reduces their spread, while its mean error becomes negative as the true weight component of one is shrunk toward zero. Gray crosses show least squares.

Smaller weights reduce sensitivity to noise, but shrinking weights also moves the average fitted weights away from the true signal. We can calculate both effects.

Claim: The expected squared weight error of ridge regression is \[ \mathbb E\|\widehat{\mathbf w}_\lambda-\mathbf w^\star\|_2^2 =\|\mathbf w_\perp^\star\|_2^2 +\sum_{i=1}^r \frac{ (n\lambda)^2(\mathbf v_i^\top\mathbf w^\star)^2 +\tau^2\sigma_i^2 }{ (\sigma_i^2+n\lambda)^2 }. \]

Proof

For each direction \(i=1,\ldots,r\), we already proved that the least-squares coefficient \(\mathbf v_i^\top\widehat{\mathbf w}\) is unbiased for \(\mathbf v_i^\top\mathbf w^\star\) and has variance \(\tau^2/\sigma_i^2\). Ridge multiplies this coefficient by the shrinkage factor \(s_i=\sigma_i^2/(\sigma_i^2+n\lambda)\). Its bias is therefore \(-(1-s_i)\mathbf v_i^\top\mathbf w^\star\), and its variance is \(s_i^2\tau^2/\sigma_i^2\).

The bias–variance identity gives each coordinate’s expected squared error relative to its fixed true value as squared bias plus variance. The directions are orthonormal, so adding these errors and the unchanged missing-signal term gives \[ \mathbb E\|\widehat{\mathbf w}_\lambda-\mathbf w^\star\|_2^2 =\|\mathbf w_\perp^\star\|_2^2 +\sum_{i=1}^r\left[ (1-s_i)^2(\mathbf v_i^\top\mathbf w^\star)^2 +s_i^2\frac{\tau^2}{\sigma_i^2} \right]. \] Substituting \(s_i=\sigma_i^2/(\sigma_i^2+n\lambda)\) proves the formula.

In each row-space direction, ridge trades squared bias

\[ \frac{(n\lambda)^2(\mathbf v_i^\top\mathbf w^\star)^2} {(\sigma_i^2+n\lambda)^2} \]

against variance

\[ \frac{\tau^2\sigma_i^2}{(\sigma_i^2+n\lambda)^2}. \]

Increasing \(\lambda\) increases the former and decreases the latter. The missing null-space signal remains unchanged.

Near \(\lambda=0\), the squared shrinkage bias grows quadratically in \(\lambda\), while the variance decreases to first order. With nonzero label noise, a sufficiently small positive penalty therefore reduces expected squared weight error. To check this, write \(R(\lambda)=\mathbb E\|\widehat{\mathbf w}_\lambda-\mathbf w^\star\|_2^2\) and differentiate at zero:

\[ R'(0)=-2n\tau^2\sum_{i=1}^r\frac1{\sigma_i^4}<0. \]

The derivative is negative when \(\tau>0\). For larger penalties, the increase in squared bias can outweigh the reduction in variance, so we choose \(\lambda\) with validation data. Because weight norms depend on the units of the features, we also typically standardize comparable numeric features before penalizing them.

So far, we have specified a preferred fit and studied its sensitivity to noise. When training with gradient descent, the initialization and updates determine which fit we reach. We will now show that starting at zero selects the minimum-norm least-squares fit whenever the updates converge.

Implicit Regularization

Suppose we minimize the unregularized squared training error

\[ \mathcal L(\mathbf w)=\frac1n\|\mathbf X\mathbf w-\mathbf y\|_2^2 \]

using gradient descent. The update is

\[ \mathbf w^{(t+1)} =\mathbf w^{(t)} -\frac{2\eta}{n} \mathbf X^\top(\mathbf X\mathbf w^{(t)}-\mathbf y). \]

Every update is a linear combination of the rows of \(\mathbf X\), so it lies in the row space. If we initialize at \(\mathbf w^{(0)}=\mathbf0\), every iterate stays in that space. In particular, gradient descent never introduces a null-space component. In the plot of equally good fits, this means every iterate stays on the horizontal axis.

The gradient descent analysis gives convergence to a least-squares minimizer when the constant step size satisfies \(0<\eta<n/\sigma_1^2\). The minimum-norm fit \(\widehat{\mathbf w}=\mathbf X^+\mathbf y\) is the only least-squares minimizer in the row space. Consequently,

\[ \lim_{t\to\infty}\mathbf w^{(t)}=\mathbf X^+\mathbf y. \]

This is implicit regularization: the optimization algorithm selects small weights even though the objective has no explicit penalty. When infinitely many weights achieve the same training error, zero initialization and the row-space updates determine which one we reach.

At convergence, these unregularized updates select the minimum-norm least-squares fit. Ridge changes the training objective and shrinks its row-space coefficients by the factors derived above. Stopping gradient descent early can also reduce the contribution of small-singular-value directions, because the updates learn those directions more slowly.

Problem 14 asks you to prove that each gradient descent iterate lies in the input span and has the smallest norm among weights with the same training predictions.

The noise contribution depends on the singular values of the feature matrix. Adding features changes those singular values, so it can change sensitivity to label noise even when the training error is already zero.

Double Descent

Adding features expands the class of functions we can represent. Since the old feature columns are preserved, the best possible training error can never increase. But test error need not follow the same pattern.

With relatively few features, a model may miss important parts of the signal. As we add features, its predictions can improve. Near the point where the model first becomes able to fit every training label, however, the fit may become extremely sensitive to noise. Beyond that point, adding features can improve test error again. To understand how, we will distinguish adding a new direction in training-prediction space from adding another way to fit a direction already available.

The resulting fall, rise, and second fall of test error is called double descent.

An experiment

We use \(n=100\) training examples with five independent inputs, each uniform on \([-1,1]\), and labels

\[ y=\sin(3x_1)+\sin(3x_2)+x_3^2+\varepsilon, \qquad \varepsilon\sim N(0,0.05^2). \]

We construct \(d\) fixed random cosine features and fit their output weights with minimum-norm least squares. Each larger model preserves all existing feature columns. The lines show median training and test errors over 16 repetitions; shading spans the 25th to 75th percentiles. The vertical axis is logarithmic above \(10^{-4}\) and linear below it so that zero training error is visible.

We can understand the three regimes using the singular values of the feature matrix.

Before interpolation: \(d<n\)

The matrix has \(r=d\) positive singular values. Adding an independent feature column opens another direction in training-prediction space. This can help fit previously unrepresented signal, reducing test error.

But the new direction may be very weak: its associated singular value can be small. The formula

\[ \tau^2\sum_{i=1}^r\frac1{\sigma_i^2} \]

is the expected squared weight error contributed by label noise. A small singular value adds a potentially large term. If new inputs are sensitive to the affected weight directions, this can raise test error as the model approaches interpolation.

At interpolation: \(d\approx n\)

When the feature matrix first reaches full row rank, its column space spans all of \(\mathbb R^n\), so every training label vector can be fitted exactly. But a matrix can have full rank while still possessing tiny singular values. Near this threshold, exact fitting may require enormous weights to match small components of label noise.

This explains why training error can reach zero at the same time that test error becomes especially large.

Beyond interpolation: \(d>n\)

Once \(\mathbf X\) has full row rank, adding another feature does not create a new direction in training-prediction space: all \(n\) directions are already available. Instead, the new feature gives us another way to produce predictions in those existing directions.

Append a feature column \(\mathbf c\in\mathbb R^n\):

\[ \mathbf X_{\mathrm{new}}=[\,\mathbf X\ \mathbf c\,]. \]

Then

\[ \mathbf X_{\mathrm{new}}\mathbf X_{\mathrm{new}}^\top =\mathbf X\mathbf X^\top+\mathbf c\mathbf c^\top. \]

For any unit prediction-space direction \(\mathbf a\),

\[ \|\mathbf X_{\mathrm{new}}^\top\mathbf a\|_2^2 =\|\mathbf X^\top\mathbf a\|_2^2 +(\mathbf c^\top\mathbf a)^2 \ge\|\mathbf X^\top\mathbf a\|_2^2. \]

Thus the ability of a fixed amount of weight to produce predictions in any given direction cannot decrease. Since \(\mathbf X\) already has full row rank, the smallest singular value cannot decrease as we append columns. In fact, all \(n\) singular values are nondecreasing, because the eigenvalues of \(\mathbf X\mathbf X^\top\) are increased by adding the positive semidefinite matrix \(\mathbf c\mathbf c^\top\).

We can bound the total noise contribution directly by comparing the weights needed to fit the same noise vector before and after adding features. For either full-row-rank matrix \(\mathbf M\), write \(\sigma_i(\mathbf M)\) for its \(i\)th largest singular value, with \(i=1,\ldots,n\).

Claim: If \(\mathbf X\) has full row rank and \(\mathbf X_{\mathrm{new}}\) appends feature columns while preserving the existing columns, then \[ \tau^2\sum_{i=1}^n\frac1{\sigma_i(\mathbf X_{\mathrm{new}})^2} \le \tau^2\sum_{i=1}^n\frac1{\sigma_i(\mathbf X)^2}. \]

Proof

Fix any noise vector \(\boldsymbol\varepsilon\in\mathbb R^n\). Because \(\mathbf X\) has full row rank, the old minimum-norm weights \(\mathbf X^+\boldsymbol\varepsilon\) fit this noise vector exactly:

\[ \mathbf X\mathbf X^+\boldsymbol\varepsilon =\boldsymbol\varepsilon. \]

Appending zero weights for the new features gives another exact fit:

\[ \mathbf X_{\mathrm{new}} \begin{bmatrix} \mathbf X^+\boldsymbol\varepsilon\\ \mathbf0 \end{bmatrix} =\boldsymbol\varepsilon. \]

The new minimum-norm fit can be no larger than this available choice. Therefore,

\[ \begin{aligned} \|\mathbf X_{\mathrm{new}}^+\boldsymbol\varepsilon\|_2^2 &\le \left\| \begin{bmatrix} \mathbf X^+\boldsymbol\varepsilon\\ \mathbf0 \end{bmatrix} \right\|_2^2\\ &=\|\mathbf X^+\boldsymbol\varepsilon\|_2^2. \end{aligned} \]

Taking expectations over the noise and applying our formula from the previous section to both sides gives the claimed inequality.

The two regimes differ in which training-prediction directions are available:

• Before full row rank, a new feature can introduce a new, weakly represented prediction direction that amplifies noise.
• After full row rank, no new prediction directions remain to be introduced. The existing directions can only become easier to fit, reducing or preserving the noise-induced squared weight error.

The proved decrease concerns the noise-induced squared weight error. Its effect on test error depends on the test-feature distribution and the signal the enlarged model can represent. The cosine-feature experiment also includes approximation error: its nonlinear target need not be represented exactly by a finite set of random features. The calculation identifies a mechanism that can contribute to the second descent by making an interpolating fit less sensitive to label noise.

In this experiment, training error stays at zero after \(d=100\) while test error eventually falls below its best value among models with fewer than 100 features. At \(d=400\), the median test error is lower than for every tested model with \(d<100\). The demo reproduces the experiment and plots the smallest singular value alongside the errors.

The phenomenon extends beyond this linear setting. Double descent has also been observed in nonlinear neural networks, although the exact formulas above do not automatically carry over to them. See the double-descent paper and the analysis of minimum-norm regression for further examples and theory.

An exact training fit can make good new predictions when its response to label noise is controlled and its features represent the signal needed on new inputs. The choice of fit and the geometry of the feature matrix determine that response. For minimum-norm least squares, small singular values amplify label noise. Ridge reduces this amplification by allowing additional training error, and additional features can reduce noise-induced weight error once every training-prediction direction is available.