What is the curse of dimensionality?

Question

Specifically, I'm looking for references (papers, books) which will rigorously show and explain the curse of dimensionality. This question arose after I began reading this white paper by Lafferty and Wasserman. In the third paragraph they mention a "well known" equation which implies that the best rate of convergence is $n^{-4/(4-d)}$; if anyone can expound upon that (and explain it), that would be very helpful.

Also, can anyone point me to a reference which derives the "well known" equation?

Answer 1

Following up on richiemorrisroe, here is the relevant image from the Elements of Statistical Learning, chapter 2 (pp22-27):

As you can see in the upper right pane, there are more neighbors 1 unit away in 1 dimension than there are neighbors 1 unit away in 2 dimensions. 3 dimensions would be even worse!

Answer 2

I know that I keep referring to it, but there's a great explanation of this is the Elements of Statistical Learning, chapter 2 (pp22-27). They basically note that as dimensions increase, the amount of data needs to increase (exponentially) with it or there will not be enough points in the larger sample space for any useful analysis to be carried out.

They refer to a paper by Bellman (1961) as their source, which appears to be his book Adaptive Control Processes, available from Amazon here

Answer 3

This doesn't answer your question directly, but David Donoho has a nice article on High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality (associated slides are here), in which he mentions three curses:

• Optimization by Exhaustive Search: "If we must approximately optimize a function of $D$ variables and we know only that it is Lipschitz, say, then we need order $(1/\epsilon)^D$ evaluations on a grid in order to obtain an approximate minimizer within error $\epsilon$."
• Integration over product domains: "If we must integrate a function of $d$ variables and we know only that it is Lipschitz, say, then we need order $(1/\epsilon)^D$ evaluations on a grid in order to obtain an integration scheme with error $\epsilon$."
• Approximation over high-dimensional domains: "If we must approximate a function of $D$ variables and we know only that it is Lipschitz, say, then we need order $(1/\epsilon)^D$ evaluations on a grid in order to obtain an approximation scheme with uniform approximation error $\epsilon$."