The curse of dimensions

Every intuition you have about distance was trained in 2D. It lies in 200D.

High-dimensional space is mostly empty — and in an empty space, everything is about equally far from everything else.

Two names, two problems

Bellman, 1957 — coined "the curse of dimensionality." A useful grid needs resolution raised to the power of the dimension. Work explodes.
Hughes, 1968 — the peaking phenomenon: with fixed data, accuracy rises with features, peaks, then declines. More measurements, worse model.

Same root: space empties out as you add axes, and finite data can't keep up.

200 random points, distances ÷ mean, as the dimension climbs.

Nearest and farthest start miles apart — and converge to the same value.

Relative contrast — how much farther the farthest is than the nearest:

\text{contrast}(q) = \frac{\max_i \, d(q, x_i) - \min_i \, d(q, x_i)}{\min_i \, d(q, x_i)}

It collapses (Beyer et al., 1999):

\lim_{d \to \infty} \; \text{contrast}(q) \; \to \; 0

Volume grows like $r^d$ , so to keep the same density you need $N \propto (1/\varepsilon)^{d}$ points — exponential in the dimension.

Each frame: 200 fresh points at one dimension, the spread of their pairwise distances (÷ mean). Nearest (cyan) and farthest (orange) march together.

Contrast falls from 41.90 at d = 2 to 0.10 at d = 1000.

When the histogram is a spike, "nearest neighbor" means nothing — and kNN, k-means, and kernels are running on noise.

5 informative features, the rest pure noise. kNN peaks at 5, then falls off a cliff. A regularized linear model barely notices the noise.

kNN: 0.9958 at 5 features → 0.6708 at 500. Logistic: still 0.9208 at 500.

At 200 features, kNN is stuck at 0.7250. Three defenses:

Variance threshold: 0.7250 — no dead columns, no help. It's not a noise filter.
SelectKBest (k=5): 0.9833 — drop the noise, restore the contrast.
PCA (k=5): 0.8542 — unsupervised, so partial recovery.

More features is not more signal — past Hughes's peak it's actively less.
Distance-based methods (kNN, k-means, RBF) die first, and die silently.
Trees and regularized linear models ignore junk columns — often the better answer.
Variance threshold clears constants, not noise. SelectKBest is cheap and strong but judges features one at a time. PCA reduces without labels.
Underneath it all: get more data, or use fewer dimensions. Nothing else scales against an exponential.