The Curse of Dimensionality

Adding more features to a dataset — more columns describing each stock, each customer, each transaction — feels like it should only ever help a model, since more information can't hurt. In practice it can hurt a lot. As the number of features grows, the space those features live in grows so much faster that the data points inside it end up scattered thin and far apart, and any method that relies on "nearby points are similar" starts failing. This is the curse of dimensionality.

The analogy: filling a room versus filling a warehouse with the same 100 marbles

Scatter 100 marbles across a small tabletop and they crowd together, close enough that neighboring marbles really do look alike. Scatter the same 100 marbles across a vast warehouse and each one sits alone in its own empty patch of floor, with no two marbles close enough to say much about each other. Adding a feature is like adding another dimension of "floor space" — the warehouse doesn't just get a little bigger, its volume grows exponentially with each new dimension, while the number of data points (marbles) stays the same.

Worked example: how "nearby" evaporates

Suppose data points are spread roughly uniformly in a hypercube, and you want to capture the 10% of points closest to a target by taking a small cube around it that covers 10% of the volume along each dimension. In $d$ dimensions, if each side of the small cube covers a fraction $s$ of the range, the volume covered is $s^d$. To capture $10\% = 0.10$ of the volume:

$$s^d = 0.10 \implies s = 0.10^{1/d}$$

With $d = 1$: $s = 0.10$, a tight neighborhood covering just 10% of the range along the one axis. With $d = 10$: $s = 0.10^{0.1} \approx 0.794$ — the "neighborhood" now has to stretch across nearly 80% of the range on every axis just to capture the same 10% of points. With $d = 100$: $s \approx 0.977$, essentially the entire range. What was a tight, local neighborhood in low dimensions becomes almost the whole space in high dimensions — there is no such thing as "nearby" anymore.

The curve above traces $s^d$-style growth: as the exponent increases, a fixed target volume forces the covered side-length toward 1 — visually, exactly the same effect making a fixed fraction of a hypercube swallow almost the whole range once dimensionality climbs.

What this means in practice

Methods that lean directly on distance or local neighborhoods — k-NN, kernel density estimation, many clustering algorithms — degrade sharply as feature count grows unless the number of training examples grows enormously to compensate, which is rarely feasible. The usual fixes are reducing dimensionality (dropping or combining redundant features, PCA), or switching to a model that doesn't rely on raw distance, like a tree ensemble that only ever compares one feature at a time.