mathematics//curse of dimensionality

The curse of dimensionality is the phenomenon in which the volume of a space grows so fast with the number of dimensions that the available data becomes sparse. In 1 dimension, 10 data points cover a lot of ground. In 100 dimensions, 10 data points are lost in a void.

The curse of dimensionality is the phenomenon in which the volume of a space grows so fast with the number of dimensions that the available data becomes sparse. In 1 dimension, 10 data points cover a lot of ground. In 100 dimensions, 10 data points are lost in a void.

Three consequences follow: distances between points become nearly uniform (everything is far from everything else), density estimation requires exponentially more data, and models trained in high-dimensional spaces are prone to overfitting because they can memorize sparse data without learning generalizable patterns.

d = 15.0 % in the outer shell, nearest ÷ farthest pair 0.00 d = 1040.1 % in the outer shell, nearest ÷ farthest pair 0.19 d = 10099.4 % in the outer shell, nearest ÷ farthest pair 0.66 d = 1000100.0 % in the outer shell, nearest ÷ farthest pair 0.87 As the dimension grows almost all of a ball's volume sits in a thin shell at its surface (here 5 % of the radius thick), and 80 random points in the unit cube end up nearly equidistant from one another.

Slide the dimension up from 2 to 100 and watch the volume move into the thin outer shell while the histogram of distances closes into a spike around its mean.

Richard Bellman named it while solving sequential decisions, and in engineering it is above all a wall of counting: any method that lays a grid over the state, or needs samples spread over it, pays the product of the sizes of every axis.

Value iteration sweeps every state of a Markov decision process, each sweep costing about states times actions times successors. A robot described by 10 variables of 100 values each has 102010^{20}1020 states, and no computer sweeps them.

Grid planners drown the same way: a 7-joint arm with 100 values per joint gives 101410^{14}1014 cells, which is why high-dimensional configuration spaces are searched by random sampling (RRT) rather than by graph search.

A particle filter needs a number of particles that grows exponentially with the size of the state: a few hundred localize a robot's planar pose on a known map, while the 24 states of a drone's navigation filter are out of reach, which is why autopilots run Kalman-type filters.

Joint action explosion: with NNN agents choosing among kkk actions each, the joint actions number kNk^NkN, the combinatorial explosion raised to the number of agents, which pushes fleets toward decentralized decisions (fleet).

Kernel methods and nearest-neighbour rules suffer the uniform distances directly: when every point is about equally far from every other, similarity stops discriminating (kernel methods).

The curse applies primarily to the data space, not to the parameter space. In overparameterized neural networks, the parameter space exhibits the opposite effect: the blessing of dimensionality, where more dimensions create more paths to good solutions. The distinction matters: the claim that deep learning should not work because of the curse of dimensionality applies a data-space intuition to a weight-space phenomenon.