Curse of Dimensionality

Where We Are

k-Nearest Neighbours gave us an almost childlike rule: look at nearby examples and let them vote. It sounds wonderfully general because we did not assume a line, tree, or equation.

But that rule hides one dangerous word: nearby.

What happens when the space becomes so large that almost nothing is truly nearby anymore?

1. Start with a tiny world

On a number line of length 1, covering 10% of the world needs an interval of length 0.1.

0 ---------[---]--------- 1
            10%

In a 2-D square, a region covering 10% of each axis occupies only:

$0.1^2 = 0.01$

or 1% of the square.

In 10 dimensions:

$0.1^{10}=10^{-10}$

A neighbourhood that felt reasonably large in one dimension becomes microscopic in a high-dimensional space.

2. The volume grows faster than intuition

Suppose we want a box that contains 10% of a unit cube’s volume. If every side has length $s$ in $d$ dimensions,

$s^d = 0.1$

so

$s = 0.1^{1/d}$

For $d=1$, $s=0.1$. For $d=10$, $s\approx0.79$. For $d=100$, $s\approx0.977$.

That means that to capture only 10% of the data volume in 100 dimensions, we may need to stretch across almost the entire range of every feature.

The idea of a small local neighbourhood has disappeared.

3. Distances begin to look alike

High-dimensional data has another strange behaviour: the nearest point and farthest point can become similar in distance.

Imagine random points whose coordinates are all between 0 and 1. Euclidean distance is

$d(x,y)=\sqrt{\sum_{j=1}^{D}(x_j-y_j)^2}$

Every new dimension adds another non-negative term. Distances grow, but they also concentrate around a typical value.

low dimension:   near ---- medium ---------------- far
high dimension:                    near--far

If “nearest” is barely nearer than “farthest,” k-NN loses the geometric contrast it depends on.

4. Why more features can make a model worse

Adding features sounds like adding information. But irrelevant dimensions add noise to distance.

Suppose dog-vs-cat really depends on ear shape and nose shape. Then we add 500 unrelated pixel statistics. Euclidean distance now spends most of its effort measuring differences that do not matter.

This is why feature selection and representation learning matter.

5. A tiny experiment

import numpy as np

rng = np.random.default_rng(0)
for d in [2, 10, 100, 1000]:
    x = rng.random((2000, d))
    q = rng.random(d)
    dist = np.linalg.norm(x - q, axis=1)
    print(d, dist.min(), dist.max(), dist.min()/dist.max())

Watch the ratio nearest / farthest. As dimension grows, it tends to move closer to 1.

Predict before running

Which dimension should make “nearest” feel most special: 2 or 1000? Explain before you run the cell.

6. The lesson is not “high dimensions are bad”

Images, text embeddings and neural-network activations are naturally high-dimensional. The real lesson is:

Geometry only helps when the representation makes meaningful things close.

Modern deep learning spends enormous effort learning such representations.

7. Practical responses

We can fight the curse by using fewer useful features, dimensionality reduction such as PCA, a better distance metric, more data, regularization, or a model whose structure does not depend directly on local Euclidean distance.

History note

Richard Bellman popularized the phrase curse of dimensionality while studying dynamic programming. The phrase survived because the same explosion appears everywhere: grids, search, density estimation and nearest-neighbour methods.

What to Remember

• Volume grows exponentially with dimension.
• Data becomes sparse relative to the available space.
• Distances can concentrate and become less informative.
• Irrelevant dimensions can drown out useful similarity.
• High-dimensional learning succeeds when the representation has useful structure.

Next → Decision Trees: instead of asking “which whole example is nearest?”, can we learn a sequence of useful questions?