Curse of Dimensionality

The curse of dimensionality is the phenomenon where data, computation, and intuition all break down as the number of input dimensions grows. Volume grows exponentially with $d$, so to densely sample a unit cube you need $n$ exponential in $d$.

As $n\to \infty$, $\sigma \to 0$.

Intuition

In high dimensions, the volume of a unit ball vanishes relative to its bounding cube: almost all the mass sits in the corners. Random points drawn uniformly from a high-$d$ cube are all roughly the same distance from each other, so “nearest” neighbor loses meaning. Distance-based methods (kNN, clustering, Gaussian kernels) degrade because there is nothing distinctive about the closest point.

Concrete example

Sample $n$ points uniformly in $[0,1{]}^d$. To have even one neighbor within distance $0.1$ in expectation, you need $n\gtrsim (1/0.1{)}^d=10^d$. In $d=10$ that is 10 billion points, in $d=100$ it is hopeless.

Two consequences stacked together:

• Data sparsity: any finite dataset looks sparse relative to the volume it lives in
• Distance concentration: ratios of max to min pairwise distances tend to 1, so ranking by distance becomes meaningless

First heard about by reading this research paper: https://onlinelibrary.wiley.com/doi/full/10.1002/sam.11161

• I can’t access this, which is annoying because I remember they had a really nice sentence explaining how the curse of dimensionality worked

Other references:

• Stackoverflow thread: https://stackoverflow.com/questions/23391589/clustering-in-high-dimensions-some-basic-stuff
• Subspace clustering for high dimensional data: https://www.kdd.org/exploration_files/parsons.pdf

CS287

For an $n$-dimensional state space, the number of states grows exponentially in $n$ (for fixed number of discretization levels per coordinate).

Therefore, in practice, discretization is considered only computationally feasible up to 5 or 6 dimensional state spaces even when using:

• Variable resolution discretization
• Highly optimized implementations

Function approximation might or might not work, in practice often somewhat local.