Curse of Dimensionality

Introduction

High dimensional spaces behave in many ways that are counter-intuitive to us. Of course, that is bound to happen: we are creatures that inhabit a 3D space, and what we see around us shapes our intuition. However, there is immense utility, particularly in the craft of data science and machine learning, in understanding these properties and turning them to our advantage. Our ability to gather and process data has exploded in recent decades, and with it the number of features we describe each data point with. We routinely work with feature spaces that have hundreds or thousands of dimensions, and with algorithms that are designed to work in such spaces.

Richard Bellman, an applied mathematician, coined the phrase ‘curse of dimensionality’ in his 1957 book Dynamic Programming. He was confronted with algorithms whose cost exploded as the number of variables grew. The failure can be computational, i.e., the work or the data needed grows exponentially with the dimension. It can also be statistical: a model that works well in a few dimensions loses its accuracy in many.

This post goes in three steps. First, five strange facts about high dimensional geometry, each derived from scratch. Second, what those facts do to algorithms that rely on distances, with k-nearest neighbors and DBSCAN as the examples. Third, why all of this amounts to a curse, and what we can do about it.

Strange things that happen in high dimensional spaces

Almost everything below follows from one rule. If a quantity is the sum of $n$ independent terms, each with mean $\mu$ and variance $\sigma^2$, then

$$\mathbb{E}[\text{sum}] = n\mu, \qquad \operatorname{SD}(\text{sum}) = \sqrt{n}\,\sigma.$$

The mean grows like $n$, but the spread only grows like $\sqrt{n}$, so relative to its mean the sum gets more and more predictable. Squared lengths and squared distances are exactly such sums, one term per coordinate. Keep this ”$\sqrt{n}$ rule” in mind.

1. Two random vectors are almost always orthogonal

This one goes against everything we would expect. High dimensional spaces are so vast that if you pick two random directions, the angle between them will almost always be close to $90^\circ$.

Let $\mathbf{a}$ and $\mathbf{b}$ be two independent random unit vectors in $n$-dimensional space. We want to understand why their angle is usually close to $90^\circ$ when $n$ is large. (A standard way to draw one: sample every coordinate from a standard normal distribution and divide the vector by its length. The result points in a uniformly random direction. That is how the plot below was made.)

Want to reproduce the experiment? The animated Python demo is available in the public repository: Random directions become orthogonal. Clone it, install the two dependencies, and run the script to watch the angle distribution tighten around $90^\circ$ as the dimension increases.

Angle and dot product

For any two vectors,

$$\mathbf{a} \cdot \mathbf{b} = \lVert\mathbf{a}\rVert\lVert\mathbf{b}\rVert\cos\theta.$$

Because $\mathbf{a}$ and $\mathbf{b}$ are unit vectors,

$$\lVert\mathbf{a}\rVert = \lVert\mathbf{b}\rVert = 1.$$

Therefore,

$$\cos\theta = \mathbf{a} \cdot \mathbf{b}.$$

So instead of studying the angle directly, we study the dot product. If $\mathbf{a} \cdot \mathbf{b} = 0$, then $\theta = 90^\circ$. If $\mathbf{a} \cdot \mathbf{b}$ is close to $0$, then $\theta$ is close to $90^\circ$.

Rotate one vector to a simple position

Because the directions are uniformly random, no direction is special. We may imagine rotating the entire coordinate system so that

$$\mathbf{a} = (1, 0, 0, \ldots, 0).$$

Rotating everything does not change the angle between $\mathbf{a}$ and $\mathbf{b}$. Write

$$\mathbf{b} = (b_1, b_2, \ldots, b_n).$$

Then

$$\mathbf{a} \cdot \mathbf{b} = (1, 0, \ldots, 0) \cdot (b_1, b_2, \ldots, b_n) = b_1.$$

Therefore,

$$\cos\theta = b_1.$$

The problem has become: what does one coordinate of a random unit vector look like?

Why its average is zero

The vector $\mathbf{b}$ is equally likely to point in any direction. Therefore, its first coordinate $b_1$ is equally likely to be positive or negative: values such as $0.2$ and $-0.2$ are equally likely. These positive and negative values cancel on average, so

$$\mathbb{E}[b_1] = 0.$$

Since $\cos\theta = b_1$,

$$\mathbb{E}[\cos\theta] = 0.$$

This means the cosine is centered around zero.

Why its variance is $1/n$

Because $\mathbf{b}$ is a unit vector,

$$b_1^2 + b_2^2 + \cdots + b_n^2 = 1.$$

All coordinates behave in the same way because no coordinate direction is special. So, on average, each squared coordinate contributes the same amount to the total $1$. There are $n$ coordinates, so each contributes $1/n$:

$$\mathbb{E}[b_1^2] = \frac{1}{n}.$$

Since the mean of $b_1$ is zero,

$$\operatorname{Var}(b_1) = \mathbb{E}[b_1^2] = \frac{1}{n}.$$

Thus,

$$\begin{gathered} \operatorname{Var}(\cos\theta) = \frac{1}{n}, \\ \operatorname{SD}(\cos\theta) = \frac{1}{\sqrt{n}}. \end{gathered}$$

This tells us the typical size of $\cos\theta$. For example, when $n = 100$, $1/\sqrt{n} = 0.1$; when $n = 10{,}000$, $1/\sqrt{n} = 0.01$. As the dimension grows, the cosine becomes more tightly concentrated around zero.

Back to the angle

Near zero, $\arccos(x) \approx 90^\circ - x \cdot \frac{180^\circ}{\pi}$, so a small cosine turns into a small deviation from a right angle:

$$\theta \approx 90^\circ \pm \frac{57.3^\circ}{\sqrt{n}}.$$

In 100 dimensions, two random directions are typically within about $6^\circ$ of perpendicular; in 10,000 dimensions, within about $0.6^\circ$. Keep this in mind for later: it also means that the cosine similarity between two unrelated vectors is almost always close to $0$.

2. All points live on the surface

Section 1 was about directions. This one is about lengths, and it starts from the most common model of data there is: the Gaussian, whose density is highest at the center.

Let $\mathbf{x} = (x_1, \ldots, x_n)$ have independent standard normal coordinates. Where do such points actually sit?

Want to check it yourself? Section 3 of the curse of dimensionality notebook samples 20,000 Gaussian vectors in each dimension and measures their lengths.

The squared length is a sum

$$\lVert\mathbf{x}\rVert^2 = x_1^2 + x_2^2 + \cdots + x_n^2.$$

Each term $x_j^2$ has mean $1$ (the variance of a standard normal) and variance $2$. By the $\sqrt{n}$ rule,

$$\mathbb{E}\lVert\mathbf{x}\rVert^2 = n, \qquad \operatorname{SD}\big(\lVert\mathbf{x}\rVert^2\big) = \sqrt{2n}.$$

From squared length to length

For large $n$, $\lVert\mathbf{x}\rVert^2$ stays close to $n$. A square root turns a small change $\delta$ around $n$ into $\sqrt{n + \delta} \approx \sqrt{n} + \frac{\delta}{2\sqrt{n}}$, so

$$\begin{aligned} \lVert\mathbf{x}\rVert &\approx \sqrt{n} \pm \frac{\sqrt{2n}}{2\sqrt{n}} \\ &= \sqrt{n} \pm \frac{1}{\sqrt{2}} \approx \sqrt{n} \pm 0.71. \end{aligned}$$

The typical length grows like $\sqrt{n}$, but the spread around it stays fixed at about $0.71$. In 100 dimensions, about 95% of points have a length between 8.6 and 11.4; in 10,000 dimensions, between 98.6 and 101.4.

Highest density, yet empty

This looks like a contradiction. The Gaussian density is highest at the origin, so why is nobody there? Because the amount of space at distance $r$ from the origin grows like $r^{n-1}$. The probability of landing at distance $r$ is the density times the space available, and in high dimensions the space wins by an enormous margin until the density’s $e^{-r^2/2}$ finally catches up near $r = \sqrt{n}$.

So a high dimensional Gaussian is not a solid blob but a thin soap bubble of radius $\sqrt{n}$. The “typical” point, the center, is the one place a sample never lands. One practical consequence: the midpoint of two Gaussian samples has length about $\sqrt{n/2}$, well inside the bubble, so it is itself a very atypical point. This is why people interpolate between latent vectors of generative models along the sphere rather than in a straight line.

3. The shrinking hypersphere

Section 2 found Gaussian points crowding onto a shell. The same thing happens to a plain ball filled uniformly, and here the reason is pure geometry: of whatever “stuff” fills a high dimensional ball, where does it actually sit?

Want to reproduce the numbers? The cleaned-up notebook and its animation are available in the curse-of-dimensionality repository. Clone it, install the dependencies, and run hypersphere_shrinkage_animation.py to watch the shell’s share of the volume climb toward 1 as the dimension increases.

The ball’s own volume collapses

The volume of an $n$-dimensional ball of radius $r$ is

$$V_n(r) = \frac{\pi^{n/2}}{\Gamma\!\left(\frac{n}{2} + 1\right)}\, r^n,$$

where $\Gamma$ extends the factorial ($\Gamma(m + 1) = m!$). It checks out in familiar dimensions: $n = 2$ gives $\pi r^2$ and $n = 3$ gives $\tfrac{4}{3}\pi r^3$.

Take a unit ball (radius 1). Its volume already misbehaves before we ask anything about shells: it grows through low dimensions, peaks at $n=5$ (volume $\approx 5.26$), and then falls back toward zero, because the factorial-like $\Gamma$ in the denominator eventually overwhelms the $\pi^{n/2}$ above it. By $n=20$ it is down to $0.026$; by $n=30$ it is about $0.00002$. A “ball” in high dimensions is not a big, roomy object; there is almost nothing there.

Volume scales with $r^n$

The sharper fact is about where whatever volume remains actually lives. Volume of an $n$-dimensional ball scales with the $n$-th power of its radius:

$$V(r) = r^n \, V(1).$$

So a smaller, concentric ball of radius $(1-\varepsilon)$ holds this fraction of the full ball’s volume:

$$\frac{V(1-\varepsilon)}{V(1)} = (1-\varepsilon)^n.$$

Everything else, a thin shell of thickness $\varepsilon$ sitting just inside the surface, holds the remainder:

$$f(n) = 1 - (1-\varepsilon)^n.$$

The shell holds (almost) everything

Fix any $\varepsilon > 0$, however small. As $n \to \infty$, $(1-\varepsilon)^n \to 0$, so $f(n) \to 1$. Dimension alone is enough to push essentially all of a ball’s volume into an arbitrarily thin outer shell: however thin you make $\varepsilon$, there is always a dimension past which almost everything lives there.

For example, when $\varepsilon = 0.01$ (the outer 1% of the radius) and $n = 10$, the shell already holds $9.6\%$ of the volume; by $n = 100$ that is $63.4\%$, by $n = 300$ it is $95.1\%$, and by $n = 1000$ it is over $99.99\%$. A fatter $\varepsilon = 0.10$ shell holds $99.5\%$ of the volume by $n = 50$ alone. The core of a high dimensional ball is, for all practical purposes, empty: almost every point in it sits close to the boundary.

This is why “the middle” stops meaning anything as dimensionality grows. Points sampled uniformly from a high dimensional ball crowd against its surface instead of filling its interior, so any notion of a typical or central point becomes unreliable. The next section shows the same underlying fact from the point of view of the distances between points.

4. Everyone is far away, but equally far away

Sections 2 and 3 measured distances from the center. Now take two random points and measure the distance between them. In high dimensions, all of these distances come out almost the same. This is called distance concentration, and it is the effect that does the most damage to machine learning.

The derivation and the simulations are in Section 5 of the curse of dimensionality notebook.

Squared distance is a sum

Let $\mathbf{x}$ and $\mathbf{y}$ be independent random points in the unit cube $[0, 1]^n$, with every coordinate uniform on $[0, 1]$. The squared distance between them is

$$D^2 = \lVert\mathbf{x} - \mathbf{y}\rVert^2 = \sum_{j=1}^{n} (x_j - y_j)^2,$$

once again a sum of $n$ independent terms.

One term

Let $u = x_j - y_j$, the difference of two independent uniform numbers. It has a triangular density $1 - |u|$ on $[-1, 1]$, which gives

$$\begin{gathered} \mathbb{E}[u^2] = 2\int_0^1 u^2 (1 - u)\,du = \frac{1}{6}, \\ \mathbb{E}[u^4] = 2\int_0^1 u^4 (1 - u)\,du = \frac{1}{15}. \end{gathered}$$

So each term $u^2$ has mean $\mu = \tfrac{1}{6}$ and variance $\sigma^2 = \tfrac{1}{15} - \tfrac{1}{36} = \tfrac{7}{180}$.

The whole distance

By the $\sqrt{n}$ rule, $\mathbb{E}[D^2] = n/6$ and $\operatorname{SD}(D^2) = \sqrt{7n/180}$. Taking the square root as in Section 2,

$$\begin{gathered} \mathbb{E}[D] \approx \sqrt{\frac{n}{6}}, \\ \operatorname{SD}(D) \approx \frac{\sqrt{7n/180}}{2\sqrt{n/6}} \approx 0.24. \end{gathered}$$

Typical distances grow like $\sqrt{n}$, while their spread stays fixed at about $0.24$. Relative to their size, they all become the same:

$$\frac{\operatorname{SD}(D)}{\mathbb{E}[D]} \approx \frac{0.59}{\sqrt{n}} \;\longrightarrow\; 0.$$

In 1,000 dimensions the typical distance is about $12.9$, and almost every pair of points is between about $12.4$ and $13.4$ apart.

Nearest and farthest

Now take one query point and many data points. The nearest and the farthest of them sit only a few standard deviations below and above the mean distance. Since the standard deviation shrinks relative to the mean, the ratio between nearest and farthest climbs toward 1. In the simulation above, with 1,000 points, the nearest point is 24% as far away as the farthest one in 10 dimensions, 69% in 100 and 89% in 1,000.

This is the result of Beyer, Goldstein, Ramakrishnan and Shaft, “When Is ‘Nearest Neighbor’ Meaningful?” (1999): whenever the relative spread of the distances goes to zero, the farthest point becomes only marginally farther than the nearest. Any method that ranks points by distance, or compares a distance with a threshold, loses its resolution. Everyone is far away, and everyone is equally far away.

5. The spiky hypercube

The last oddity is about the most ordinary shape there is. Fit the largest possible ball inside the unit cube: radius $\tfrac{1}{2}$, touching the middle of every face. In two dimensions the disk covers most of the square, and in three the ball still fills half the cube. Then it disappears.

The formula and a simulation that throws 200,000 random points into the cube are in Section 3 of the curse of dimensionality notebook.

The ball inside the cube

The cube has volume 1, so the share of it inside the ball is just the ball’s volume from Section 3 with $r = \tfrac{1}{2}$:

$$V_n\!\left(\tfrac{1}{2}\right) = \frac{\pi^{n/2}}{\Gamma\!\left(\frac{n}{2} + 1\right) 2^n}.$$

That is $78.5\%$ in 2 dimensions, $52.4\%$ in 3, $16.4\%$ in 5, $0.25\%$ in 10 and about 2 in 100 million in 20. Throw 200,000 random points into a 20-dimensional cube and, on average, not a single one lands inside the ball.

Corners run away

If the volume is not in the ball, where is it? In the corners. The center of the cube is $\tfrac{1}{2}$ away from the middle of each face, but a corner differs from the center by $\tfrac{1}{2}$ in every one of the $n$ coordinates, so it is

$$\sqrt{n \cdot \left(\tfrac{1}{2}\right)^2} = \frac{\sqrt{n}}{2}$$

away.

In 100 dimensions the corners are 10 times farther from the center than the faces are, and there are $2^{100}$ of them. A high dimensional cube is less like a box and more like a sea urchin: a small core with an astronomical number of long spikes, and nearly all of the volume out in the spikes.

Neighborhoods stop being local

This geometry is what makes “local” a slippery idea. Suppose we want a small cube around a point that holds 1% of uniformly spread data. Its volume must be $0.01$, so its edge must be $0.01^{1/n}$ of each axis. In 1 dimension that is 1% of the axis; in 10 dimensions it is $63\%$; in 100 dimensions, $95.5\%$ (the example is from Hastie, Tibshirani and Friedman, The Elements of Statistical Learning, §2.5). A neighborhood that holds 1% of the data has to span nearly the whole range of every feature. Equivalently, to keep a cube of edge $0.1$ around a point occupied, we need about $10^n$ data points.

A demonstration of the failure of distance based algorithms

Distance concentration and empty neighborhoods hurt every method built on distances. I worked through the best known example, k-nearest neighbors (KNN), in two notebooks, now in the curse-of-dimensionality repository:

• A hands-on KNN tutorial builds KNN from scratch, checks it against scikit-learn, and works through every practical decision: choosing $k$, scaling features, weighting votes, picking a metric, and what it all costs.
• The curse of dimensionality and KNN follows up on the warning the first one ends with, and explains from first principles why KNN breaks down in high dimensions, and why it often doesn’t.

Both are saved with their outputs, so they can be read on GitHub without running anything.

k-nearest neighbors

To classify a new point, KNN finds the $k$ labeled points closest to it and lets them vote. It learns nothing else: the distance function is its only source of knowledge, and every feature enters that distance with the same weight. That makes it the perfect victim.

The first notebook ends with a simple experiment. A two-feature dataset that KNN classifies with $96.8\%$ accuracy drops to $92.7\%$ with 2 irrelevant features added, $77.0\%$ with 50, and $65.5\%$ with 200. The data still contains exactly the same signal; KNN just can’t find it any more.

Neighbors move far away

The emptiness of Section 5 has a direct price: to keep the nearest neighbor close, the data has to grow exponentially with the dimension. With $N$ points, the nearest-neighbor distance shrinks only like $N^{-1/n}$, so halving it takes $2^n$ times more data: twice as much in 1 dimension, about a thousand times as much in 10, $10^{30}$ times as much in 100. In high dimensions, the “nearest” neighbors are not near, and they are barely nearer than a random point (Section 4).

Signal drowned by noise

Real data is not pure noise; some features matter. The follow-up notebook makes this precise with one informative feature and $m$ irrelevant ones. KNN works when a point from the query’s own class tends to be nearer than a point from the other class. Writing the difference of the two squared distances as signal plus noise, every irrelevant feature adds variance to that difference but nothing to its mean, so the probability $p$ that the same-class point is nearer behaves like

$$p \approx \Phi\!\left(\frac{g}{\sqrt{v_0 + 12m}}\right) \;\longrightarrow\; \frac{1}{2},$$

where $g$ and $v_0$ are the mean and variance of the signal part and $\Phi$ is the normal distribution function. The signal-to-noise ratio of every distance comparison falls like $1/\sqrt{m}$. In the notebook, KNN holds its best possible accuracy of $93\%$ up to about 30 noise features, then falls to $88\%$ at 100, $70\%$ at 1,000 and $62\%$ at 3,000. Logistic regression doesn’t suffer the same way, because it learns a weight per feature and can push the useless ones to zero.

Hubness

A subtler effect: a few points become everyone’s neighbor. On average a point’s squared distance to everybody else is its squared distance from the center of the data plus a constant, so slightly more central points are slightly closer to everyone. When all distances are squeezed together, that small systematic advantage decides the “nearest” contest for many queries at once. These hubs end up in a huge number of neighbor lists and dominate the votes, while points on the outside become anti-hubs that never appear in anyone’s list (Radovanović, Nanopoulos and Ivanović, Hubs in Space, 2010).

Not every dimension is a curse

The twist at the end of the notebook: take the two-dimensional “moons” dataset, pad it with 498 columns of zeros, and rotate it at random so the signal is smeared across all 500 columns. Rotations preserve every distance exactly, so KNN scores the same $96.3\%$ in 500 dimensions as in 2. The column count was never the problem.

What hurts is independent variation in many directions. Add a little noise to every one of the 500 columns, with a standard deviation of only $0.1$ against a signal spread of $1$, and the noise vector’s total length is already $0.1\sqrt{500} \approx 2.2$, larger than the signal. Accuracy slides to $94.4\%$; at $0.5$ per column, to $79.0\%$. Real data usually sits in between: the 8×8 handwritten digits have 64 columns but need only 21 directions to explain 90% of their variance, and KNN classifies them with $96.3\%$ accuracy.

DBSCAN

DBSCAN clusters points by density. A point with at least min_samples neighbors within a radius $\varepsilon$ is a core point, clusters grow from core points, and everything else is noise. Unlike KNN, which only ranks distances, DBSCAN compares them with a fixed threshold. That makes distance concentration even more damaging.

The usual way to pick $\varepsilon$ is the k-distance plot: sort the points by the distance to their min_samples-th neighbor and look for the elbow where points inside clusters give way to points between them. When all distances concentrate, every point’s k-distance is nearly the same, and the elbow flattens out. Any $\varepsilon$ is then either below almost every k-distance, so everything is labeled noise, or above almost every one, so everything merges into one giant cluster. The range of $\varepsilon$ that recovers the real clusters gets narrower as noise dimensions are added, until it disappears. As with KNN, the remedy is to remove the noise dimensions before clustering, not to search harder for $\varepsilon$.

Why is high-dimensionality a curse

Taking stock, the curse has two faces.

1. Distance concentration. Distances between points converge to the same value (Section 4), so algorithms that rank or threshold distances, such as KNN, DBSCAN, k-means and kernel methods with a fixed bandwidth, lose the contrast they depend on.
2. Emptiness. The volume of the space grows exponentially with its dimension (Section 5), so any realistic dataset is sparse. Neighborhoods are not local, and covering the space densely would take $10^n$ points.

The manifold effect is a cause of trouble but at the same time a blessing. High dimensional data often does not occupy the entire space, but lives on or near a lower dimensional manifold embedded in it. Algorithms that use distances as they come may miss the relationships along that manifold. But the same property is what saves us: we do not have to fill the immense empty space, only the manifold, and its intrinsic dimension can be far smaller than the number of columns (21 against 64 for the digits). The rotated moons show the extreme case: 500 columns, intrinsic dimension 2, and no curse at all. In practice, the enemy is irrelevant variation spread across many directions, not the column count itself.

Tangents

Learning in high dimensions always amounts to extrapolation

We like to think of a model as interpolating between its training examples. If “interpolation” means a new point lies inside the convex hull of the training set, then in high dimensions it essentially never happens: the number of samples needed for a new point to land inside the hull grows exponentially with the intrinsic dimension of the data. Balestriero, Pesenti and LeCun, “Learning in High Dimension Always Amounts to Extrapolation” (2021), show that test points of real image datasets fall outside the training hull, yet models generalize well anyway. The intuition that interpolation is safe and extrapolation is risky comes from low dimensions and doesn’t transfer.

The impact of noise, or more importantly the signal-to-noise ratio

Noise behaves like the Gaussian vectors in Section 2: a little noise per coordinate adds up to a noise vector of length $\sigma\sqrt{n}$, while the signal stays the same size. Small noise in many directions is therefore not small. That is exactly why adding features is never free for a distance based method: each irrelevant feature adds noise to every comparison, and the signal-to-noise ratio of a distance falls like $1/\sqrt{m}$, as in the KNN experiment above. More features help only if they bring more signal than noise.

Dealing with the curse of dimensionality

None of this means high dimensional data is unusable, only that the tools have to change with the geometry.

The most direct fix is to remove the dimensions that carry noise before doing anything else. Feature selection does it with the labels: in the notebook, burying the 64 digit pixels among 500 noise features drops KNN from $96.3\%$ to $84.3\%$, and keeping the 64 features that best separate the classes brings it straight back to $96.3\%$. Dimensionality reduction does it without labels: methods like PCA or a trained autoencoder project the data onto the few directions it actually varies in, the manifold from the previous section. PCA to 20 components recovers $92.3\%$ on the same data. It works only when the signal has more variance than the noise in the directions it keeps; if the noise were stronger, PCA would keep the noise. The follow-up post on dimensionality reduction goes into these methods.

Where the dimension has to stay high, it helps to pick algorithms that are not built around raw distance. Models that learn a weight per feature, such as logistic regression or tree-based models that split on one feature at a time, can learn to ignore irrelevant features. For KNN itself, metric learning (for example neighborhood components analysis) learns a distance in which the informative directions count for more.

Switching from Euclidean distance to cosine similarity does not escape the curse. Section 1 says precisely that the cosine similarity between unrelated random vectors crowds around $0$, so cosine similarities concentrate just like distances do. Cosine similarity is the right choice when a vector’s length is a nuisance, as with text embeddings, but it works there because the embeddings were learned so that their directions carry the signal, not because of the metric.

Finally, more data helps less than it sounds like it should. The sample size needed to cover a space densely grows exponentially with dimension, so in practice we lean on regularization and strong priors to make up for data that will never be dense enough to fill the space it occupies.