Curse of Dimensionality

As dimensionality increases, data becomes exponentially sparse. This breaks intuitions from low-dimensional spaces and has deep consequences for ML.

The core problem: to maintain the same density of data points, you need exponentially more samples as dimensions grow. In $d$ dimensions with $n$ samples on $[0,1]^d$, the expected distance to the nearest neighbor grows as $n^{-1/d}$.

Surprising consequences:

• Distances concentrate: in high dimensions, the farthest point and nearest point become almost equidistant — $\frac{\max \text{ dist} - \min \text{ dist}}{\min \text{ dist}} \to 0$. This makes distance-based methods like K-Nearest Neighbors unreliable
• Volume lives on the shell: most of the volume of a high-dimensional sphere is near its surface, not near the center
• Corners dominate: most of the volume of a high-dimensional cube is in its corners

How ML fights it:

• Principal Component Analysis (PCA) and autoencoders — reduce dimensionality to the intrinsic dimension
• Regularization — constrains the effective number of parameters
• Embeddings — learn low-dimensional representations of high-dimensional inputs
• Manifold hypothesis — real-world high-dimensional data (images, text) actually lives on low-dimensional manifolds, which is why deep learning works at all
• Feature selection — discard irrelevant dimensions before training

Rule of thumb: you need $O(10^d)$ samples to densely cover $d$ dimensions. This is why raw pixel inputs need massive datasets but learned 768-dim embeddings work with much less.

See also: Principal Component Analysis (PCA), Embeddings, Bias-Variance Tradeoff