CONCEPT
The Curse of Dimensionality
Richard Bellman’s phrase for the brute fact that state spaces grow exponentially as the number of variables increases—the wall that made his own method intractable on hard problems for sixty years and that deep learning has, conditionally, escaped.
The curse of dimensionality is the most consequential named obstacle in the history of artificial intelligence.
Richard Bellman coined the phrase in the 1950s to describe a brutal arithmetic fact: add dimensions to a problem and the volume of the space it occupies grows exponentially. A state described by a handful of variables, each taking a handful of values, already yields more configurations than there are stars in the galaxy. Bellman's dynamic programming method required a value for every state; the states could not be counted, let alone valued, on any problem that mattered. For decades the curse made his exact equation intractable on the problems most worth solving, setting an apparent ceiling on what sequential decision theory could achieve. The modern escape from it—by
deep neural networks that exploit the hidden low-dimensional structure of real data rather than covering the space uniformly—is the single most important technical fact about the current AI era. But the escape