At how many dimensions does the curse begin?

There is no threshold. What matters is the ratio of examples to dimensions, and how many dimensions carry signal. For kNN, problems already show up with a few dozen irrelevant features.

Are neural networks immune to the curse of dimensionality?

They are not immune by definition, but they exploit the structure of the data well: locality and hierarchy in images, sequential order in text. Without such structure they too would need exponentially many examples.

How does this differ from the Hughes phenomenon?

The Hughes phenomenon is one specific consequence: with a fixed number of examples, a classifier's accuracy first rises with the number of features and then falls. The curse of dimensionality is the broader name for all of these geometric effects.

11 · Laws · 4 min read · Interactive · updated 8 October 2026

What is the curse of dimensionality and why does it hurt models?

In short

As dimensions grow, space empties out exponentially and distances between points become nearly equal. Neighbourhood-based methods stop making sense.

What it is

The number of examples needed to cover a space equally densely grows exponentially with the number of dimensions, and in high dimensions the distances to the nearest and the farthest point become almost equal. The term was coined by Richard Bellman in 1957, writing about dynamic programming; the concentration of distances was described by Kevin Beyer and co-authors in 1999.

An example: to have one point in every tenth of the interval [0, 1], 10 points are enough. A square needs 100, a cube 1,000, and 20 dimensions — 10²⁰. No dataset can cover that, so the "nearest neighbour" in high dimensions is not near at all.

This is not a single phenomenon but a family of effects: the emptiness of space, the concentration of distances, nearly all the volume sitting "near the walls", and a vast number of possible interactions between features.

Mechanism — why it works this way

Volume escapes to the boundary. A circle inscribed in a square fills 79% of its area, a ball inscribed in a cube 52% of its volume, in 5 dimensions 16%, and in 10 a mere 0.25%. In a hypercube, a layer 5% thick along each wall contains 19% of the volume in 2 dimensions, 65% in 10 and practically 100% in 100. A typical point lies near the boundary, not in the middle.

Distances concentrate. The squared Euclidean distance is a sum of contributions from many independent dimensions. By the law of large numbers such a sum grows like d, while its spread grows only like √d. The ratio of spread to mean shrinks like 1/√d, so all distances become "more or less the same". Similarity-based methods — kNN, k-means, RBF kernels — then lose the information about which point is genuinely close.

Noise drowns out the signal. If only a few features carry information and the rest are noise, every irrelevant feature adds its own contribution to the distance. With hundreds of such features the signal is lost.

Caveat: the curse applies to data spread out in all dimensions. Real data (images, text) usually lies close to a surface of much lower dimension — which is why models on thousands of pixels work at all. That is the content of the manifold hypothesis.

By example

We drew 500 points from a uniform hypercube and measured their distances to a random query point. The ratio of the farthest to the nearest distance was 92.9 in 2 dimensions, 2.55 in 10, 1.34 in 100, 1.11 in 1,000 and 1.035 in 10,000. In 10,000 dimensions the nearest point is only 3.5% closer than the farthest.

On the Wine dataset (178 wines, 13 features), kNN with standardisation reaches an accuracy of 0.96 in 5-fold cross-validation. Adding 10 columns of pure noise lowers it to 0.94, 50 columns to 0.88, 100 to 0.80, 500 to 0.61, and 1,000 to 0.56 — barely better than guessing the most frequent class (0.40). The information in the 13 real features has not changed; it has drowned in distances computed over noise.

In practice

Before kNN, an RBF-kernel SVM or clustering, reduce the dimension: SelectKBest, PCA, domain knowledge.
Standardise features (StandardScaler) — otherwise a dimension with a large scale dominates the distance regardless of dimensionality.
Models with built-in selection (lasso, trees, gradient boosting) are far more robust to irrelevant features than kNN.
One-hot encoding a variable with thousands of categories is an easy way to wander into high dimensions without noticing.
Typical mistake: selecting features on the whole dataset before cross-validation — it gives falsely good results (data leakage).

Frequently asked questions

At how many dimensions does the curse begin?: There is no threshold. What matters is the ratio of examples to dimensions, and how many dimensions carry signal. For kNN, problems already show up with a few dozen irrelevant features.
Are neural networks immune to the curse of dimensionality?: They are not immune by definition, but they exploit the structure of the data well: locality and hierarchy in images, sequential order in text. Without such structure they too would need exponentially many examples.
How does this differ from the Hughes phenomenon?: The Hughes phenomenon is one specific consequence: with a fixed number of examples, a classifier's accuracy first rises with the number of features and then falls. The curse of dimensionality is the broader name for all of these geometric effects.

Sources

Bellman R. (1961). Adaptive Control Processes: A Guided Tour. Princeton University Press.
Beyer K., Goldstein J., Ramakrishnan R., Shaft U. (1999). When Is "Nearest Neighbor" Meaningful? International Conference on Database Theory (ICDT 1999), 217–235.
Aggarwal C. C., Hinneburg A., Keim D. A. (2001). On the Surprising Behavior of Distance Metrics in High Dimensional Space. ICDT 2001, 420–434.
Hastie T., Tibshirani R., Friedman J. (2009). The Elements of Statistical Learning, 2nd ed. Springer, ch. 2.5.