Intermediate26 min

The Curse of Dimensionality

Volume concentration, distance concentration, sample-density collapse, and its consequences for kNN and kernels.

Assumes you know

The Bias–Variance Trade-off

The Curse of Dimensionality

Intuition first

Adding features feels like adding information. Geometrically, it is closer to adding emptiness.

Consider covering the interval $[0,1]$ with points spaced 0.1 apart: 10 points. In two dimensions, covering the unit square at the same resolution needs $10^2 = 100$ . In ten dimensions, $10^{10}$ — ten billion. The number of points required to maintain the same density grows exponentially, so any fixed dataset becomes exponentially sparser as dimensions increase.

Two consequences follow, and both break methods that work fine in low dimensions. Every point becomes far from every other point, so "nearest neighbour" stops meaning anything. And almost all of a high-dimensional region's volume sits near its boundary, so most of your data is at the edge, where models must extrapolate rather than interpolate.

Volume concentrates at the boundary

Take a unit-radius ball in $d$ dimensions, and ask what fraction of its volume lies in the outer 10% shell — the region between radius 0.9 and radius 1.

Volume scales as $r^d$ , so the fraction inside radius $0.9$ is $0.9^d$ , and

\text{fraction in the shell} = 1 - 0.9^{\,d}

$d$	$0.9^d$	Fraction in outer 10%
1	0.900	10.0%
2	0.810	19.0%
5	0.590	41.0%
10	0.349	65.1%
50	0.005	99.5%
100	0.0000266	99.997%

Distances concentrate

More damaging for algorithms that rely on distance: in high dimensions, the nearest and farthest points become nearly equidistant.

Why distances convergeAdvanced

Let $x$ and $y$ have independent coordinates with variance $\sigma^2$ each. The squared Euclidean distance is

\lVert x - y \rVert^2 = \sum_{j=1}^{d} (x_j - y_j)^2

This is a sum of $d$ i.i.d. terms, each with mean $2\sigma^2$ and some finite variance $\tau^2$ . So

\E\big[\lVert x - y \rVert^2\big] = 2 d \sigma^2, \qquad \Var\big(\lVert x - y \rVert^2\big) = d\tau^2

The mean grows like $d$ while the standard deviation grows like $\sqrt{d}$ . The relative spread is therefore

\frac{\text{SD}}{\text{mean}} = \frac{\sqrt{d}\,\tau}{2d\sigma^2} = \frac{\tau}{2\sigma^2\sqrt{d}} \;\propto\; \frac{1}{\sqrt{d}} \;\longrightarrow\; 0

All pairwise distances converge to the same value relative to their magnitude. Formally,

\frac{d_{\max} - d_{\min}}{d_{\min}} \;\longrightarrow\; 0 \quad \text{as } d \to \infty

Once that ratio is small, "the nearest neighbour" is not meaningfully nearer than the tenth or the hundredth — it is selected by noise. Every method whose logic rests on relative distance degrades: kNN, k-means, DBSCAN, RBF kernels, and cosine retrieval over poorly-structured embeddings.

Solved problem 1 · Sample size needed for constant density

You have 1,000 points in 1 dimension, giving a comfortable density. How many are needed for the same density in 10 dimensions? In 20?

Step 1 — density in one dimension

Spread over $[0,1]$ , 1,000 points give a spacing of

\frac{1}{1000} = 0.001

Step 2 — what the same spacing requires in d dimensions

To keep spacing $h$ along every axis, each axis needs $1/h$ positions, so the total is

n_d = \left(\frac{1}{h}\right)^{d} = 1000^{\,d}

Step 3 — evaluate

d = 10: \quad n = 1000^{10} = 10^{30}

d = 20: \quad n = 1000^{20} = 10^{60}

Step 4 — put those numbers in context

The observable universe contains roughly $10^{80}$ atoms. So covering 20 dimensions at this resolution would require a dataset with more points than there are atoms in a galaxy.

Answer

$10^{30}$ for 10 dimensions and $10^{60}$ for 20. Uniform coverage of even moderately high-dimensional space is not merely expensive but physically impossible — which means every high-dimensional method must rely on structure rather than coverage.

Why anything works at all

If high-dimensional space is this hostile, why do image models with a million pixels succeed?

Because real data does not fill its space. A $256 \times 256$ colour image lives in about 196,608 dimensions, but the set of images that look like photographs occupies a vanishingly thin subset. Perturb a photo randomly and you get static, not a different photo.

This is the manifold hypothesis: real high-dimensional data concentrates near a low-dimensional manifold embedded in the ambient space. The intrinsic dimension is far lower than the ambient dimension, and that is what makes learning feasible.

Practical consequences

Method	Effect of high $d$	Mitigation
kNN	Neighbours become arbitrary	Reduce dimension; learn a metric
k-means	Clusters lose meaning	PCA first; use cosine on normalised vectors
RBF kernel SVM	All points look equidistant	Tune $\gamma$ carefully; use linear kernel
Linear models	Perfect separability, high variance	Strong L1/L2 regularisation
Trees	Mostly robust — they use one feature at a time	Limit depth
Vector search	Recall degrades; index quality falls	Lower-dimensional or Matryoshka embeddings

Note where trees sit. Axis-aligned splitting ignores the geometry that causes the problem, which is part of why gradient-boosted trees remain hard to beat on wide tabular data.

Demonstrating it

python

import numpy as np

rng = np.random.default_rng(0)

print(f"{'d':>5}  {'mean dist':>10}  {'(max-min)/min':>14}  {'in outer 10% shell':>19}")
for d in (1, 2, 5, 10, 50, 100, 500):
    X = rng.uniform(0, 1, size=(500, d))

    # Pairwise distances from the first point to all others.
    dists = np.linalg.norm(X[1:] - X[0], axis=1)
    contrast = (dists.max() - dists.min()) / dists.min()

    shell = 1 - 0.9 ** d      # fraction of ball volume in the outer 10%
    print(f"{d:5d}  {dists.mean():10.3f}  {contrast:14.3f}  {shell:18.4%}")

The contrast column is the one to watch: it falls from several hundred percent at $d = 1$ towards a few percent by $d = 500$ . Once it is small, nearest-neighbour queries are returning essentially random points.

Exercise 1

A kNN classifier scores 0.91 on 5 features and 0.62 on 200 features, on the same data with the extra 195 features being weak but non-zero predictors. Explain, and give two fixes.

Show solution

The added features are individually weak but each contributes noise to the distance computation. Euclidean distance sums over all 200 dimensions, so 195 weak dimensions collectively dominate the 5 informative ones. Neighbours are selected mostly by noise, and kNN's entire logic — that nearby points share labels — no longer holds.

This is distance concentration doing exactly what the derivation predicts: the relative contrast between near and far neighbours has collapsed.

Two fixes:

Dimensionality reduction before the distance computation. PCA to 10–20 components, or a supervised alternative like LDA. This concentrates variance into few dimensions and discards noise directions, restoring contrast.
Metric learning or feature weighting. Learn a weighted distance so informative features dominate — for example scale each feature by its mutual information with the target, or use a learned Mahalanobis metric.

A third option worth mentioning: switch model. Gradient-boosted trees split on one feature at a time and never compute a distance, so they largely ignore this problem. Sometimes the right response to the curse is to stop using a distance-based method.

Exercise 2

Explain why a 50,000-dimensional TF-IDF text representation works well with a linear SVM despite the curse.

Show solution

Several things make this case benign.

Extreme sparsity. A document contains a few hundred distinct terms out of 50,000, so each vector is over 99% zeros. Two documents only interact through terms they share, so the effective dimension of any comparison is tiny — the noise dimensions contribute exactly zero rather than a small random amount.

Low intrinsic dimension. Language has heavy structure: words co-occur in predictable patterns, so documents lie near a far lower-dimensional manifold. Latent semantic analysis routinely captures most of the variance in a few hundred components.

Linear models are the right family here. With $d > n$ , data is almost always linearly separable, and a maximum-margin linear classifier with regularisation has a hypothesis space whose complexity depends on the margin rather than on $d$ . The generalisation bound for SVMs involves $1/\text{margin}^2$ , not the dimension — which is precisely why SVMs survived the move to high-dimensional text.

Cosine similarity, not Euclidean. Normalising to unit length removes document-length effects, and angular similarity on sparse vectors degrades far more gracefully than Euclidean distance.

The general lesson: the curse bites methods that depend on dense geometry and local neighbourhoods. Sparse data with a margin-based linear model avoids nearly all of it.

Next: Feature Engineering — which, given this lesson, is as much about restraint as about creativity.