The Curse of Dimensionality, Playable

EP 01

The distance histogram — watch near and far become the same word

Scatter 200 random points in a box, measure all pairwise distances, draw the histogram. In 2D it's wide: some pairs are neighbors, some are strangers — distance carries information. Now drag the dimension slider. The histogram squeezes into a needle: in 1,000 dimensions the closest pair and the farthest pair differ by a few percent. Every measurement is redone live as you drag.

✓ good case: d=2 — nearest pair 30× closer than farthest; "neighbor" means something✗ bad case: d=1000 — contrast collapses to ~5%; near and far are synonyms

dimensions 2 —

Slider is powers of two, 1 → 1024 dimensions. Distances are normalized by √d so the histograms are comparable; the squeeze you see is the concentration-of-measure phenomenon, computed, not illustrated.

Distance concentration is the root curse: every algorithm built on "similar things are close" — search, clustering, recommendation, kNN — inherits this failure the moment you feed it raw high-dimensional vectors. It's why embedding quality matters more than embedding size.

EP 02

The empty middle — a warehouse where everything's stacked against the walls

Take a box and mark its "core": the inner region at 90% of the side length. In 2D the core holds 81% of the volume — most of the box is middle. Drag the slider: at d=50, the core holds half a percent. The volume didn't disappear; it moved into a thin shell near the walls and corners. The dots below are a live 3,000-point Monte Carlo — green lands in the core, orange in the shell.

✓ good case: d=2 — a fair split, your intuition works✗ bad case: d=50 — 99.5% of random points hug the walls; the "typical" point is an edge case

dimensions 2 —

The theoretical curve 0.9^d is drawn in grey; the gold dots are the measured Monte Carlo fraction at each d you visit — watch them agree.

"Average" is a low-dimensional concept. In high dimensions almost every sample is extreme in some coordinate — which is why outlier detection gets philosophically hard, and why generated faces from early GANs looked weird when sampled far from the data shell.

EP 03

Watch a classifier rot — the noise-feature experiment

Two classes of points, cleanly separated in 2 informative dimensions — a nearest-neighbor classifier scores ~95%. Now do what real datasets do to you: add irrelevant features. Each extra dimension is pure noise, no signal. Drag the slider and watch the measured accuracy of the exact same algorithm decay toward a coin flip, because the useless dimensions drown the two useful ones inside every distance computation.

✓ good case: 2 informative dims, 0 junk — kNN 95%✗ bad case: + 200 junk dims — same data, same algorithm, 55%

junk dimensions 0 —

Real kNN (k=5) on 300 training / 150 test points, re-run per click. The left panel shows the 2 informative dims (always separable to the eye) — the algorithm just can't see them through the noise.

"More features can't hurt" is the most expensive lie in applied ML. Every irrelevant column you keep dilutes the metric that everything downstream depends on. Feature selection, PCA, and learned embeddings are all the same act: throwing the junk dimensions overboard before they drown the signal.

EP 04

The exponential bill — how many samples to cover the space?

Coverage: drop N reference points, then ask — for a random query, how far is its nearest reference? In 2D, 1,000 points blanket the box; queries always land near one. Raise the dimension with N fixed and the measured gap explodes: your 1,000 points become a few lonely lighthouses in fog. Try to fix it with the N slider and watch how little each doubling buys.

✓ good case: d=2, N=1000 — average query-to-nearest gap: tiny, the space is covered✗ bad case: d=30 — even ×16 more points barely moves the gap; coverage is unbuyable

dimensions 2 reference points 1024 —

Gap measured over 200 random queries per setting (normalized by √d). The bar chart accumulates your measurements so you can compare settings side by side.

This is why lookup tables can't be intelligence. Covering a 100-dim space at any useful resolution needs more samples than atoms in the universe. Any system that works up there — including every neural network — must generalize between samples, because visiting enough of the space is physically impossible.

EP 05

The escape hatch — real data cheats

So why does anything work? Because real data doesn't fill high-dimensional space — it lies on thin manifolds inside it. Here's a 1-dimensional spiral embedded in a 100-dimensional box. Ambient dimension: 100. The kNN classifier that died in EP 03 — run it here: it thrives, because distances along the manifold still mean something. Then drag the off-manifold noise slider and watch the curse seep back in.

✓ good case: on-manifold, ambient d=100 — kNN accuracy 90%+; intrinsic dimension is what matters✗ bad case: same 100 dims filled with isotropic noise — back to the coin flip

off-manifold noise 0.0 —

Data: two interleaved spiral arcs rotated into 100 dimensions (intrinsic dim ≈ 1), 300 train / 150 test, real kNN each click. The left panel shows the first two coordinates — the shadow of the manifold.

The manifold hypothesis is deep learning's load-bearing assumption: images, speech and language occupy vanishingly thin sheets inside their pixel/token spaces. Neural networks don't defeat the curse — they change the battlefield, learning coordinates along the sheet so that distance means something again. Every embedding model you've ever used is selling exactly this service.