The bias–variance trade-off and the curse of dimensionality

Every model sits somewhere between memorising the data and ignoring it. Getting that position right is most of the job, and it is where most backtests go wrong.

Bias and variance

Think of bias as how much a model’s assumptions force it to be wrong, and variance as how much its answer would change if you gave it a different sample of training data. For squared error, the expected test error at a point splits exactly into three parts:

You can’t reduce the noise. You can only trade the other two against each other. More flexible models (more parameters, more degrees of freedom) have lower bias and higher variance. One-nearest-neighbour is the extreme: no assumptions, zero training error, and a decision boundary that jumps whenever one data point moves. Linear regression assumes a straight line: stable, but stuck if the truth bends (though you can add $x^2$, $\sin x$ and so on as new features).

The U-shaped test curve is the picture to remember: training error always rewards complexity; test error punishes too much of it.

The curse of dimensionality

Nearest neighbours relies on having close neighbours. In high dimensions there aren’t any.

• Suppose data are spread uniformly in a unit cube in $p$ dimensions. To capture a fraction $r$ of the data in a sub-cube around a point, its edge must be $e_p(r) = r^{1/p}$. In 10 dimensions, catching 10% of the data needs a cube spanning 80% of every axis: the “neighbourhood” is most of the space.
• Points crowd the boundary. The share of points within 5% of some face is $1 - 0.9^p$: 41% in 5 dimensions, 99.5% in 50. Predictions near a boundary are extrapolations, not interpolations.

So nearest neighbours wins when data are low-dimensional and plentiful; linear models win as dimension grows, because their strong assumption is exactly the defence they need. Add regularisation (lesson 11) and they cope with thousands of features.

In code

import numpy as np
from numpy.polynomial import chebyshev as C
rng = np.random.default_rng(7)

f = lambda x: np.sin(2 * np.pi * x)
x = np.sort(rng.random(18)); y = f(x) + 0.3 * rng.standard_normal(18)
xt = np.linspace(0, 1, 400)

for deg in (1, 3, 9, 14):
    coef = C.chebfit(2 * x - 1, y, deg)
    train = np.mean((C.chebval(2 * x - 1, coef) - y) ** 2)
    test = np.mean((C.chebval(2 * xt - 1, coef) - f(xt)) ** 2) + 0.3 ** 2
    print(deg, round(train, 3), round(test, 3))

# Edge length for 10% of the data in p dimensions
for p in (1, 2, 10, 50):
    print(p, round(0.1 ** (1 / p), 2))     # 0.1, 0.32, 0.79, 0.95