The Curse of Dimensionality

Richard Bellman coined the phrase "curse of dimensionality" in 1957 while studying dynamic programming: the number of states explodes exponentially with the number of variables. In machine learning the curse has several faces — data sparsity, distance concentration, and counter-intuitive geometry. Understanding them explains why nearest-neighbour methods struggle on raw pixels, why feature selection matters, and why deep learning's ability to find low-dimensional structure is so valuable.

Face 1: exponential sparsity#

To cover the unit interval $[0, 1]$ with a grid of spacing 0.1 you need 10 points. To cover the unit cube $[0,1]^d$ at the same resolution you need $10^d$ points. At $d = 20$ that is $10^{20}$ — more than any dataset will ever contain. In high dimensions, data is always sparse: most of the space contains no training examples at all.

Consequence for local methods such as k-nearest neighbours: to capture a fraction $r$ of uniformly distributed data in a hypercube neighbourhood, the neighbourhood's edge length must be

To capture 1% of the data in 10 dimensions, you need $0.01^{1/10} \approx 0.63$ — 63% of the range of each feature. Your "local" neighbourhood is not local at all.

Face 2: volume concentrates in the shell#

The volume of a $d$-dimensional ball of radius $r$ scales as $r^d$. The fraction of a unit ball's volume lying within the outer shell of thickness $\epsilon$ is

For $d = 100$ and $\epsilon = 0.05$ this is $1 - 0.95^{100} \approx 0.994$. Almost all the volume is near the surface. Similarly, a high-dimensional Gaussian's samples do not cluster near the mean; they concentrate on a thin shell of radius about $\sqrt{d}\,\sigma$.

Face 3: distance concentration#

For many distributions, as $d$ grows, the distances from a query point to its nearest and farthest neighbours become almost equal:

If all points are roughly equally far away, "nearest neighbour" loses meaning.

import numpy as np

rng = np.random.default_rng(0)
for d in [2, 10, 100, 1000, 10000]:
    X = rng.random((1000, d))
    q = rng.random(d)
    dist = np.linalg.norm(X - q, axis=1)
    contrast = (dist.max() - dist.min()) / dist.min()
    print(f"d={d:>5}: relative contrast = {contrast:.3f}")

Run it: the relative contrast collapses as $d$ grows.

Face 4: random vectors are orthogonal#

The cosine similarity of two random vectors in $\mathbb{R}^d$ concentrates around zero with standard deviation about $1/\sqrt{d}$. In 10,000 dimensions, random vectors are almost exactly orthogonal. This is a blessing too: high-dimensional spaces can host an enormous number of nearly-orthogonal directions, which lets embeddings and neural representations pack many features with little interference (the "superposition" hypothesis in interpretability research).

Face 5: more parameters, more data#

A model with more features has more parameters to estimate. Without enough data, it overfits. Classical rules of thumb suggest needing many examples per parameter; the Hughes phenomenon describes how, with a fixed training set, classifier accuracy first rises and then falls as features are added.

Why does machine learning work at all?#

If the curse were the whole story, image classification on $224 \times 224 \times 3 = 150{,}528$-dimensional inputs would be impossible. It works because real data is not uniformly spread:

1. The manifold hypothesis — natural data (images, speech, text) lies near low-dimensional manifolds embedded in the high-dimensional space. The set of plausible face images is a tiny, structured subset of all pixel arrays.
2. Smoothness and structure — nearby inputs usually have similar labels, and many features are correlated.
3. Inductive biases — convolutional networks assume locality and translation invariance; transformers exploit relational structure. These priors drastically reduce what must be learned from data.
4. Compositionality — deep networks build complex functions from simple parts, which can be exponentially more efficient than shallow ones for certain structured functions.

Remedies#

• Feature selection — keep only informative features.
• Dimensionality reduction — PCA (linear), autoencoders (non-linear), UMAP/t-SNE (for visualisation).
• Regularisation — constrain model complexity.
• Better representations — learned embeddings in which distances are meaningful; this is why semantic search uses learned embeddings rather than raw bag-of-words vectors.
• Domain knowledge and architecture — encode known structure into the model.
• More data and data augmentation.