The Curse of Dimensionality

The Curse of Dimensionality

Add a column to a table and you have added information — that is the intuition, and it is wrong often enough to be worth a page of its own.

In high dimensions, geometry stops behaving the way two- and three-dimensional intuition expects. Volume runs to the surface of a ball, the inscribed ball all but vanishes inside its cube, random directions become almost perpendicular, and — the one that actually breaks machine learning — pairwise distances concentrate, so "nearest neighbour" gradually stops meaning anything.

Where you actually meet this

Before the geometry, the places it shows up — because the phenomenon is abstract and the consequences are not.

The reason kNN still works acceptably on MNIST at 784 columns is the same idea from the other side: the intrinsic dimension of handwritten digits is estimated at around 12 to 15, not 784. The ambient count is not what governs.

A0 · Anchoring in 3-D

Everything below only happens in high dimension, where there is no way to draw it. This panel does the opposite: it shows in 3-D — where intuition still works — the beginning of each effect, and puts the closed-form number for the \(d\) you choose next to it. Rotate the figure and watch the gap between the two grow.

How to read the panel

The panel has three scenes, and the slider means something different in each:

• In cube and shell, the picture is always the 3-D one — it cannot be anything else. The slider picks a reference dimension \(d\), and only the number cards change: the left cards are what the 3-D sample measures, the right ones are the closed form evaluated at your \(d\). The lesson is the gap between the two columns.
• In clusters drowned by noise, the slider picks how many noise columns \(m\) are added (0, 3, 10, 30, 100 or 250), and the picture itself changes, because what you see is a projection of a genuinely high-dimensional cloud.
• Drag to rotate; untick rotate to stop the spin. A card turns red once the effect has taken over — a ball below 0.1% of the cube, or clusters whose ratio has dropped under 1.5.

Scene 1 · The cube, its inscribed ball, and the corners

What is drawn. The edges of the cube \([-1,1]^3\), the ball of radius 1 inside it (three great circles, in orange), and 1 100 points drawn uniformly in the cube: blue if they fall inside the ball, red if they fall outside it — in the corners.

What to see. The sample measures about 53% inside; the closed form says \(\pi/6 = 52.4\%\). With 1 100 points the standard error is about 1.5 percentage points, so the two agree. Even in 3-D, half the cube is already corners.

Why the ball empties. The fraction of the cube taken by the inscribed ball is

but a one-line argument explains it better than the formula. For a point uniform in the cube, each coordinate \(x_j\) is uniform on \([-1,1]\) and \(\mathbb E[x_j^2] = 1/3\). So

The point is inside the ball only if \(\lVert x\rVert^2 \le 1\). At \(d = 3\) the typical squared norm is exactly 1, which is why about half the points land inside. From there on the typical point sits at a squared norm of \(d/3 > 1\), and being inside the ball demands that every coordinate be small at the same time, which becomes exponentially unlikely. The corners are \(\sqrt d\) from the centre, while the ball never grows past radius 1.

Try it. Move the slider to 10 and then 20 while the cube keeps spinning. The picture cannot follow; the cards can.

Scene 2 · The shell: where the points are

What is drawn. 900 points uniform inside the ball, the outer sphere (grey circles) and an inner sphere at 80% of the radius (dashed orange). Points in the outer 20% of the radius — the shell — are orange; the interior points are blue.

How the points are drawn. A uniform direction (a normalized gaussian vector) times a radius \(U^{1/3}\), with \(U\) uniform on \([0,1]\). The cube root is what makes the points uniform by volume: the volume inside radius \(r\) grows as \(r^3\), so there must be fewer points near the centre than near the surface. Drawing the radius uniformly would pile the points at the centre.

Why the shell wins. Volume scales as \(r^d\), so the inner ball of radius \(1-\varepsilon\) holds a fraction \((1-\varepsilon)^d\) of the volume, and the shell holds the rest:

The sample measures about 47% against 48.8%, which is again within sampling error.

Scene 3 · Three clusters drowned by noise

What is drawn. 270 points in three clusters (90 each). The clusters live in the first three columns, with centres 2.8 to 2.9 apart and a spread of 0.55 around each. Then \(m\) columns of pure \(\mathcal N(0,1)\) noise are appended. The panel computes the first three principal components of the full \((3+m)\)-column table and plots the points in them.

The number on the card is the between/within ratio in the view: the mean distance between cluster centroids divided by the mean distance from each point to its own centroid. Roughly: above 2 the clusters are clearly apart; below 1 they overlap.

What actually happens, measured on this exact scene:

The third column of the table is the whole point: the clusters never moved. Measured in the three columns that define them, the separation stays around 3.3 at every \(m\). What collapses is the view, in three stages:

1. At \(m = 3\) the third axis is lost at once. The three signal columns do not carry equal variance: two have about 1.6, but the third has only 0.48, which is less than the variance of 1 in each noise column. PCA ranks directions by variance, so the third principal component immediately becomes a noise direction (its share in the true columns drops to 2%) and the ratio falls from 3.5 to 2.4.
2. Up to \(m \approx 30\) the first two axes resist. Their variance of 1.6 still beats the noise, so PC1 and PC2 remain mostly signal, and the three clusters stay visible in the plane they span. This resistance is exactly why running PCA before t-SNE works: PCA keeps the high-variance signal directions and discards most of the noise.
3. Around \(m \approx 100\) the resistance breaks. With a finite sample, the noise does not look like variance 1 in every direction: some random directions of the noise happen to have more sample variance, and the more noise columns there are, the larger the largest of them gets. For \(n\) points and \(m\) noise columns, the largest spurious variance grows to about \((1+\sqrt{m/n})^2\) — 1.4 at \(m = 10\), 2.6 at \(m = 100\), 3.9 at \(m = 250\). A signal direction whose variance exceeds the noise by \(\theta\) is only recovered while \(\theta > \sqrt{m/n}\). Here \(\theta \approx 0.6\) and \(n = 270\), so the threshold is \(m \approx 0.6^2 \times 270 \approx 97\) — right where the table shows PC1 and PC2 turning into noise. At \(m = 250\) they are 97% noise, and the three clusters that are still perfectly separated in the data are gone from the picture.

A1 · The volume runs to the shell

For points spread uniformly through the unit ball, almost all of the volume sits in a thin skin next to the surface. The fraction inside the outer \(\varepsilon\) of the radius is \(1 - (1-\varepsilon)^d\), and the median radius is \((1/2)^{1/d}\) — at \(d = 100\) that is \(0.993\).

The counter-intuitive consequence is that the centre is empty. At \(d = 50\) essentially no point lies below 90% of the radius, so the notion of a "typical point near the centroid" — which carries a great deal of low-dimensional intuition — simply stops applying. A centroid in high dimensions is not close to anything.

A2 · The ball vanishes inside the cube

The ball inscribed in the cube \([-1,1]^d\) occupies \(\pi^{d/2} / \big(\Gamma(d/2+1)\,2^d\big)\) of it: 78.5% of the square, 52.4% of the cube, 0.25% at \(d=10\), and \(2.5\times10^{-8}\) at \(d=20\). The cube has \(2^d\) corners, and that is where the volume goes.

Push the slider past \(d = 18\) and the Monte Carlo estimate reports exactly zero: twenty thousand uniform points in the cube, and not one of them lands in the inscribed ball.

Why it matters: if you normalize into a hypercube — which is what MinMaxScaler does — the "central" region intuition pictures as typical is statistically unreachable. Every point is an extreme case in some coordinate. The same geometry is why a grid search over more than a handful of hyperparameters is hopeless: a grid samples corners, and corners are all there is.

A3 · Distances concentrate

The typical distance between two points grows as \(\sqrt d\) while the spread around it does not, so the relative contrast \((d_{\max}-d_{\min})/d_{\min}\) decays as \(O(1/\sqrt d)\).¹

This is the one that actually affects machine learning — kNN, k-means, RBF kernels, and t-SNE and UMAP themselves — and it is the only one of the four whose validity depends on the distribution of the data.

Compare the five generators: three collapse and two do not. At \(d = 256\) the relative contrast is 0.37 for uniform, 0.43 for gaussian and 0.44 for clusters plus noise — the farthest pair is less than one-and-a-half times the nearest. With signal in every column it is still 2.6, and on the rotated 2-D disc it is 392, exactly where it was at \(d = 2\).

A4 · Everything becomes orthogonal

The cosine between two random directions has mean zero and standard deviation \(1/\sqrt d\). At \(d = 1000\), 99% of pairs have \(\lvert\cos\theta\rvert < 0.082\).

This one has a good side that is rarely mentioned. Near-orthogonality is exactly what makes the Johnson–Lindenstrauss lemma work: a random projection into \(O(\log n / \varepsilon^2)\) dimensions preserves every pairwise distance to within a relative error \(\varepsilon\), regardless of the original dimension. It is also what lets an embedding of modest width hold an enormous number of nearly mutually orthogonal concepts — the reason a 768-dimensional embedding can carry far more than 768 distinguishable things.

A5 · The practical consequence

The signal is always in the first two columns; extra columns are added on top, in three flavours, and a 5-NN is actually trained and tested on each. The panel runs all 27 fits in your browser when you scroll to it.

In this sample, 250 noise columns take the accuracy from 90% to 71%, 250 weakly informative ones take it to 100%, and 250 noisy copies of the signal leave it at 90%. Press new sample a few times: the ends move by a couple of points, but the ordering never changes.

The same experiment in scikit-learn, with its own seed and a slightly different setup:

"""The curse of dimensionality is not about dimensions. It is about what is in them.

The signal always lives in the first two columns, and a 5-nearest-neighbour
classifier reads it at about 0.906. Then extra columns are added, of three
kinds, and only the kind changes:

  noise        independent gaussian columns, carrying nothing
  informative  columns that each shift with the label
  redundant    noisy copies of the two columns that already carried the signal

Read the three columns against each other. "High dimension hurts kNN" is true
only of the first, and it is the sentence people remember without the
qualification — which is why kNN works acceptably on MNIST at 784 dimensions,
where the intrinsic dimension of the digits is estimated at around 12 to 15.

Printed as a markdown table, in identifiers only, so one artifact serves both
the English and the Portuguese page.
"""

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

N, REPEATS, EXTRA = 500, 5, (0, 2, 8, 32, 128)


def build(extra, kind, seed):
    rng = np.random.default_rng(seed)
    signal = rng.normal(size=(N, 2))
    y = ((signal[:, 0] + signal[:, 1] + 0.3 * rng.normal(size=N)) > 0).astype(int)
    if extra == 0:
        return signal, y
    if kind == "noise":
        added = rng.normal(size=(N, extra))
    elif kind == "informative":
        added = rng.normal(size=(N, extra)) + 0.9 * (2 * y - 1)[:, None]
    else:                                        # noisy copies of what we already had
        added = np.tile(signal, (1, extra // 2 + 1))[:, :extra] + 0.5 * rng.normal(size=(N, extra))
    return np.hstack([signal, added]), y


def accuracy(extra, kind):
    scores = []
    for seed in range(REPEATS):
        X, y = build(extra, kind, seed)
        X_train, X_test, y_train, y_test = train_test_split(
            X, y, test_size=0.5, random_state=seed, stratify=y
        )
        scores.append(KNeighborsClassifier(5).fit(X_train, y_train).score(X_test, y_test))
    return float(np.mean(scores))


print("| `extra_dimensions` | `noise` | `informative` | `redundant` |")
print("|---:|---:|---:|---:|")
for extra in EXTRA:
    cells = " | ".join(f"**{accuracy(extra, k):.3f}**"
                       for k in ("noise", "informative", "redundant"))
    print(f"| {extra} | {cells} |")

• Noise columns: 0.906 → 0.595. Each adds distance that is the same for every pair, and the two columns that matter are progressively drowned.
• Informative columns: 0.906 → 1.000. More dimensions made the problem easier.
• Redundant columns — noisy copies of the signal, so the intrinsic dimension stays 2: 0.906 → 0.885. It holds up.

The three closed forms, checked

"""Three claims about high-dimensional geometry, each in closed form and each checked.

None of these depends on the data: they are facts about the shape of space, and
they hold for every dataset that lives in d dimensions. Each row reports the
analytic value and a Monte Carlo estimate beside it, so the formula can be
believed rather than taken on trust.

  shell        fraction of a unit ball's volume within the outer 10% of the radius,
               1 - 0.9^d, and the median radius (1/2)^(1/d)
  ball_in_cube volume of the inscribed ball over the volume of the cube,
               pi^(d/2) / (Gamma(d/2 + 1) * 2^d) — the cube has 2^d corners and
               that is where everything ends up
  cos_sd       standard deviation of the cosine between two random directions,
               1/sqrt(d): in high dimensions, everything is almost orthogonal

Printed as a markdown table, in identifiers only, so one artifact serves both
the English and the Portuguese page.
"""

import numpy as np
from scipy.special import gammaln

DIMS, SAMPLES = (2, 3, 5, 10, 20, 50, 100), 40_000

rng = np.random.default_rng(4)


def uniform_in_ball(d, n):
    """Direction from a gaussian, radius from U^(1/d) — uniform by volume."""
    direction = rng.normal(size=(n, d))
    direction /= np.linalg.norm(direction, axis=1, keepdims=True)
    return direction * rng.random((n, 1)) ** (1 / d)


print("| `d` | `shell_10pct` | `(mc)` | `median_radius` | `ball_in_cube` | `(mc)` | `cos_sd` | `(mc)` |")
print("|---:|---:|---:|---:|---:|---:|---:|---:|")
for d in DIMS:
    radii = np.linalg.norm(uniform_in_ball(d, SAMPLES), axis=1)
    shell, shell_mc = 1 - 0.9 ** d, float((radii > 0.9).mean())

    # log-volumes, or the ratio underflows well before d = 100
    log_ratio = d / 2 * np.log(np.pi) - gammaln(d / 2 + 1) - d * np.log(2)
    cube = rng.random((SAMPLES, d)) * 2 - 1                    # the cube [-1, 1]^d
    inside = float((np.linalg.norm(cube, axis=1) <= 1).mean())  # the inscribed ball

    a, b = rng.normal(size=(SAMPLES, d)), rng.normal(size=(SAMPLES, d))
    cos = np.einsum("ij,ij->i", a, b) / (np.linalg.norm(a, axis=1) * np.linalg.norm(b, axis=1))

    fmt = lambda v: f"{v:.2e}" if 0 < v < 1e-4 else f"{v:.4f}"
    print(f"| {d} | {shell:.4f} | {shell_mc:.4f} | {0.5 ** (1 / d):.4f} "
          f"| {fmt(np.exp(log_ratio))} | {fmt(inside)} "
          f"| {1 / np.sqrt(d):.4f} | {cos.std():.4f} |")

Every analytic column matches its Monte Carlo neighbour. At \(d = 20\) the ball-in-cube ratio is \(2.46\times10^{-8}\) and forty thousand samples find nothing — the estimate is not wrong, it is simply below the resolution of the experiment.

Summary

A6 · Complementary video

A narrated walk through the same argument. It is worth watching before the lab: the panels above are easier to read after hearing it told once.