Bias–Variance, Interpolation and Double Descent

The exact decomposition, the classical U-curve, the second descent past the interpolation threshold, and what is proved about each.

Learning TheoryGraduate⏱ 3 hours7 min readbias-variancedouble descentinterpolationoverparameterisationminimum norm

5 problems →

AssumesVC Dimension, Sauer's Lemma and Rademacher Complexity · Linear, Ridge and Lasso Regression

The identity

PropositionThe bias–variance decomposition is an identity

Let $y = f^\star(x)+\varepsilon$ with $\E[\varepsilon\mid x]=0$ and $\Var(\varepsilon\mid x)=\sigma^2$ , and let $\hat f_S$ be an estimator trained on a random sample $S$ . Then for each fixed $x$ ,

\E_{S,\varepsilon}\Big[\big(y - \hat f_S(x)\big)^2\Big] = \underbrace{\sigma^2}_{\text{noise}} + \underbrace{\big(\E_S\hat f_S(x) - f^\star(x)\big)^2}_{\text{bias}^2} + \underbrace{\Var_S\big(\hat f_S(x)\big)}_{\text{variance}} .

Run it: Bias–variance decompositionSquared bias, variance and total risk of polynomial regression as model capacity grows.

HeuristicThe bias–variance trade-off

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

The trade-off — that increasing model capacity necessarily decreases bias and increases variance, so that risk is U-shaped in capacity — is an empirical regularity of classical model families, not a consequence of the identity.

What this does not say

The identity says risk $=$ noise $+$ bias $^2$ $+$ variance. It says nothing about how either term moves with capacity. For polynomial regression with $p \le n$ , as in the experiment on this page, the U-curve is real and reproducible. For $p > n$ it is not, and the reason is specific: once the model interpolates, the fit is no longer determined by the loss alone and depends on which of the infinitely many zero-loss solutions the algorithm selects. The variance of that object is a different quantity with different behaviour.

Past the interpolation threshold

Consider least squares with $p$ features and $n$ samples. For $p<n$ the solution is the usual $\hat\beta = (X^\top X)^{-1}X^\top y$ . For $p>n$ the system is underdetermined and the natural choice is the minimum-norm interpolator

\hat\beta = \argmin\{\norm\beta_2 : X\beta = y\} = X^\dagger y = X^\top(XX^\top)^{-1}y ,

which is what gradient descent from $\beta_0 = 0$ converges to — see the implicit-bias discussion on the deep learning theory page.

PropositionWhy the risk blows up at the threshold

For the least-squares estimator with $p<n$ and fixed design $X$ , the variance term of the risk is

\Var = \sigma^2\,\tr\big((X^\top X)^{-1}\Sigma\big) \ \ge\ \frac{\sigma^2\lambda_{\min}(\Sigma)}{\lambda_{\min}(X^\top X)} ,

which diverges as $\lambda_{\min}(X^\top X)\to0$ . For i.i.d. Gaussian design, $\lambda_{\min}(X^\top X)/n \to (1-\sqrt{p/n})^2$ , which vanishes exactly at $p = n$ .

Key idea

The divergence at $p=n$ is not mysterious and not specific to machine learning: it is the conditioning of a square random matrix. At $p=n$ the design is square and nearly singular, so the fit must use enormous coefficients to interpolate, and those coefficients amplify the noise. For $p>n$ the matrix $XX^\top$ is $n\times n$ with aspect ratio $n/p<1$ , hence better conditioned again — and the minimum-norm constraint keeps the coefficients small. That is the mechanism behind the second descent, at least in the linear case.

TheoremDouble descent for minimum-norm linear regression

In the proportional asymptotic regime $p/n\to\gamma$ with isotropic Gaussian features and a well-specified linear model, the risk of the minimum-norm interpolator has an explicit limit $\mathcal{R}(\gamma)$ which

increases on $\gamma\in(0,1)$ and diverges as $\gamma\uparrow1$ ;
decreases on $\gamma\in(1,\infty)$ , approaching $\sigma^2 + \norm{\beta^\star}_2^2$ -dependent limits;
can be lower at some $\gamma>1$ than at every $\gamma<1$ , depending on the signal-to-noise ratio.

Quoted from Hastie, Montanari, Rosset and Tibshirani, who compute $\mathcal{R}(\gamma)$ exactly using random matrix theory. The companion result of Bartlett, Long, Lugosi and Tsigler characterises benign overfitting: the minimum-norm interpolator has small risk precisely when the spectrum of the feature covariance has a particular shape — a few large eigenvalues carrying the signal and a long tail of small ones that absorbs the noise without contributing to prediction. Their effective-rank conditions are the sharpest available statement of when interpolation is harmless.

Empirical observationDouble descent in deep networks

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

Nakkiran et al. report test-error curves with a clear second descent in deep networks, as a function of model width, of training set size (where more data can transiently hurt), and of training time (epoch-wise double descent).

What this does not say

The empirical phenomenon is robust and has been replicated. What is not established:

that the mechanism is the same as in the linear case. The linear analysis relies on the minimum- $\ell^2$ -norm characterisation of the interpolator; for a deep network trained by SGD the implicit bias is not known in closed form, so the analogy is suggestive rather than derived.
that "wider is better" in general. The curves depend on the noise level, the parameterisation, and the amount of explicit regularisation; adding optimal ridge regularisation removes the peak entirely in the linear case, and label noise is what makes the peak prominent in the deep case.
that double descent explains why deep learning generalises. It describes a shape of the risk curve; it does not identify the inductive bias that makes the interpolating solution good.

A fair summary: the linear theory is rigorous and complete; the deep learning phenomenon is well-documented and its explanation is open.

Problems

The bias–variance decomposition is an identityProof · Beginner · 15 min Gradient descent finds the minimum-norm interpolatorProof · Intermediate · 30 min The interpolation peak is a conditioning phenomenonProof · Advanced · 30 min Reproduce double descentCoding · Advanced · 3 hours

References

PaperMikhail Belkin, Daniel Hsu, Siyuan Ma and Soumik Mandal (2019). Reconciling modern machine learning practice and the bias-variance trade-off
PaperTrevor Hastie, Andrea Montanari, Saharon Rosset and Ryan J. Tibshirani (2022). Surprises in High-Dimensional Ridgeless Least Squares InterpolationThe precise asymptotic analysis of the linear case quoted here.
PaperPreetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak and Ilya Sutskever (2020). Deep Double Descent: Where Bigger Models and More Data Hurt
PaperPeter L. Bartlett, Philip M. Long, Gábor Lugosi and Alexander Tsigler (2020). Benign overfitting in linear regression

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionThe bias–variance decomposition is an identityproof includedFor squared loss the risk splits exactly into noise, squared bias and variance.
HeuristicThe bias–variance trade-offThe claim that increasing capacity must increase variance is a description of certain model families, not a theorem.
TheoremDouble descent for minimum-norm linear regressionIn an asymptotic random-design model the risk of the minimum-norm interpolator diverges at the interpolation threshold and decreases beyond it.
PropositionWhy the risk blows up at the thresholdproof includedThe variance of the minimum-norm solution is controlled by the inverse smallest eigenvalue of the sample covariance, which vanishes exactly when p equals n.
Empirical observationDouble descent in deep networksTest error curves with a second descent have been reported for networks across width, data size and training time; the mechanism is not established.

Experiments

Bias–variance decomposition
Squared bias, variance and total risk of polynomial regression as model capacity grows.

Problems (5)

All problems