The curse of dimensionality is the collective name for a set of counter-intuitive phenomena that arise when working with data of many features. The first is the exponential thinning of space: for sample density to stay constant, the amount of data would have to grow multiplicatively with every added dimension, so even a huge dataset is desperately empty in hundreds of dimensions and almost every new point falls into a region where the model has never seen anything. The second and even stranger phenomenon is distance concentration – in high dimensions the distances between any two points converge towards each other, the ratio between the nearest and the farthest neighbour approaches one, and the notion of “nearest” thus loses its discriminating power. Metric-based methods such as k-NN and k-means suffer most. In addition, the volume of a ball concentrates in a thin shell near its surface, so data lie at the edges rather than in the middle. The defences are dimensionality reduction, regularisation and feature selection. A practical relief is the manifold hypothesis: real data usually lie on a far lower-dimensional surface embedded in the high-dimensional space, which is why embeddings work at all.
Imagine looking for a friend. On a street a hundred metres long you find him at once. On a square a hundred by a hundred metres there are ten thousand spots, but it is still manageable. In a hundred-storey building a hundred by a hundred metres there are a million spots. Now add that he may be in one of a hundred times of day, one of a hundred moods and one of a hundred coat colours. The space of possibilities swells to such monstrous size that however many colleagues you bring, the searched portion stays infinitesimal. And the oddest part: in such a space, suddenly everyone is equally far from everyone else.