Curse of Dimensionality

Machine learning learns from examples. A model usually predicts better on new inputs when those inputs are similar to examples it saw during training. During training, the model adjusts itself to fit patterns in the dataset, so similar new inputs let it reuse those patterns with more confidence.

Input features define a space. If an input has $d$ features, we can think of it as a point in a $d$-dimensional space. The goal is not to cover every possible point in that space, but to cover the parts where real data can appear, especially the parts where the model must make predictions.

The curse of dimensionality is that this space grows extremely fast as the number of dimensions grows. In one dimension, covering the interval from $0$ to $1$ with points spaced $0.1$ apart takes about $10$ points. In two dimensions, the same spacing takes about $100$ points. In three dimensions, it takes about $1000$ points. Each extra dimension multiplies the number of points needed.

For a fixed dimension, making the spacing twice as fine requires at least $2^d$ times more points to cover the whole $d$-dimensional space. This is only a lower bound. It assumes new points land in the ideal places, roughly in the middle of the existing gaps across every small hypercube. Real samples do not arrive on a perfect grid. They collide, cluster, and leave other regions uncovered, so the actual data requirement can be even larger.

Spacing is also a resolution limit. If the nearest useful training example is far away, there is a lower bound on how local the model's prediction can be. To lower that bound, we need more diverse data in the uncovered regions. Better resolution therefore costs more coverage.

This is the curse. Volume grows exponentially with dimension, so data becomes exponentially sparse. In practice, real data is often not spread evenly through the whole space. It usually varies mostly along a smaller number of important directions, which is why learning can still work.