Textbook of AI

The Curse of Dimensionality refers to the exponential growth of difficulty as the number of dimensions increases—a phenomenon that affects machine learning in several distinct and counterintuitive ways. The term was coined by Richard Bellman and has become shorthand for the many ways high-dimensional spaces behave unlike our low-dimensional intuitions.

One manifestation is sparsity: the volume of a high-dimensional space grows exponentially, so a fixed amount of data becomes ever more sparse relative to the volume. With 10 samples per dimension in 1 dimension you have 10 samples; in 10 dimensions you would need 10 billion samples for the same density. This makes density estimation, nearest-neighbour search, and kernel methods increasingly difficult. Another manifestation is distance concentration: in high dimensions, pairwise Euclidean distances between points tend to converge, making all points approximately equidistant and degrading nearest-neighbour queries. A third is volume concentration: in a high-dimensional ball, almost all the volume is concentrated in a thin shell near the surface.

In machine learning, the curse affects classical non-parametric methods (KNN, kernel density estimation, decision trees) far more than parametric ones. Deep learning partially escapes the curse by learning low-dimensional representations of high-dimensional data—the manifold hypothesis holds that natural data lies on or near low-dimensional manifolds within high-dimensional spaces. Dimensionality reduction techniques (PCA, t-SNE, UMAP, autoencoders) explicitly exploit this. Monte Carlo integration famously escapes the curse too: its error scales as $1/\sqrt{N}$ regardless of dimension, while deterministic quadrature degrades exponentially.