An Example of Curse of Dimensionality Ibuki

It’s well-known that estimating regression function is very difficult in high-dimensional spaces. Sometimes this phenomenon is referred to as curese of dimensionality. The following example is adapted from one section and an exercise problem in the book A Distribution-Free Theory of Nonparametric Regression by László Györfi, et al. This example shows that in the case of high dimension, it’s not possible to densely cover the space of $X$ with sample $X_{1}, \ldots, X_{n}$, even if sample size $n$ is quite large.

Let $X, X_{1}, \ldots, X_{n}$ be a random sample from the uniform distribution on $[0,1]^d$. For large $d$, we’ll examine the quantity

\[\E\left[ \min_{i=1,...,n} \| X-X_i\| \right],\]

which can be considered as the expected distance of $X$ from the sample $X_1,…,X_n$. Let’s don’t specify the type of the norm for now. Directly, we have

\[\begin{aligned} \E\left[ \min_{i=1,...,n} \| X-X_i\| \right] &= \int_0^{\infty} P\left( \min_{i=1,...,n} \| X-X_i\| > t \right)~dt \\ & = \int_0^{1} 1- P\left( \min_{i=1,...,n} \| X-X_i\| \le t \right)~dt. \end{aligned}\]

We may use the union bound on the last probability:

\[\begin{aligned} P\left( \min_{i=1,...,n} \| X-X_i\| \le t \right) &= P\left( \bigcup_{i=1}^n \left\{ \| X-X_i\| \le t \right\} \right) \\ &\le \sum_{i=1}^n P\left( \| X-X_i\| \le t \right)\\ & = n P(\| X-X_i\| \le t ). \end{aligned}\]

For supremum norm $\Vert\cdot\Vert_\infty$, the above quantity is easy to bound:

\[\begin{aligned} P(\| X-X_i\|_\infty \le t ) & = P\left( \bigcap_{j=1}^d \left\{\vert X^{(j)}-X_i^{(j)}\vert \le t \right\}\right)\\ & = \left[1-(1-t)^2\right]^d = (2t-t^2)^d \le (2t)^d. \end{aligned}\]

Therefore, we have

\[\begin{aligned} \E\left[ \min_{i=1,...,n} \| X-X_i\|_\infty \right] & = \int_0^{1}1- P\left( \min_{i=1,...,n} \| X-X_i\|_\infty \le t \right)~dt\\ &\ge \int_0^{2^{-1}n^{-1/d}}1- P\left( \min_{i=1,...,n} \| X-X_i\|_\infty \le t \right)~dt\\ & \ge 2^{-1}n^{-1/d}- 2^d n \int_0^{2^{-1}n^{-1/d}} t^{d}~dt \\ & = \frac{d}{d+1}\cdot \frac{1}{2n^{1/d}}. \end{aligned}\]

When the dimension $d$ is a large fixed number, the first term is about 1. However, for large $d$, $\frac{1}{2n^{1/d}}$ decreases very slowly in $n$. Hence, for large $d$, $\frac{1}{2n^{1/d}}$ will not be close to zero even if $n$ is quite large. When $d=20$, we compute the above quantity in R for $n = 1000, 10000, 100000$ and $1000000$:

We can see that the distance is quite a bit away from zero even if $n$ is 1000000.

Let’s now check what happens for Euclidean norm $\Vert\cdot\Vert_2$. In this case, we have

\[P(\| X-X_i\|_2 \le t ) = V_n(t) = \frac{ \pi^{\frac{d }{2}}}{\Gamma\left(\frac{d}{2}+1 \right)} t^{d},\]

where $V_n(t)$ is the volume of $d$-dimensional ball with radius $t$. Therefore, we have

\[\begin{aligned} \E\left[ \min_{i=1,...,n} \| X-X_i\|_2 \right] & = \int_0^{1}1- P\left( \min_{i=1,...,n} \| X-X_i\|_2 \le t \right)~dt\\ &\ge \int_0^{\frac{\Gamma\left(\frac{d}{2}+1 \right)^{1/d}}{\sqrt{\pi} n^{1/d}}}1- P\left( \min_{i=1,...,n} \| X-X_i\|_2 \le t \right)~dt\\ & = \frac{\Gamma\left(\frac{d}{2}+1 \right)^{1/d}}{\pi^{1/2} n^{1/d}}- \frac{ n\pi^{\frac{d }{2}}}{\Gamma\left(\frac{d}{2}+1 \right)} \int_0^{\frac{\Gamma\left(\frac{d}{2}+1 \right)^{1/d}}{\pi^{1/2} n^{1/d}}} t^{d}~dt \\ & = \frac{\Gamma\left(\frac{d}{2}+1 \right)^{1/d}}{\pi^{1/2} n^{1/d}} - \frac{ n\pi^{\frac{d }{2}}}{\Gamma\left(\frac{d}{2}+1 \right)} \frac{\pi^{-d/2-1/2} n^{-1-1/d}\Gamma\left(\frac{d}{2}+1 \right)^{1+1/d}}{d+1} \\ & = \frac{\Gamma\left(\frac{d}{2}+1 \right)^{1/d}}{\pi^{1/2} n^{1/d}}\left( 1 - \frac{1 }{(d+1) } \right) = \frac{\Gamma\left(\frac{d}{2}+1 \right)^{1/d}}{\pi^{1/2} } \cdot \frac{d }{d+1 }\cdot \frac{1}{n^{1/d}}. \end{aligned}\]

When the dimension $d$ is a large fixed number, the first two terms are constants (actually, one may use Stirling’s formula for Gamma function $\Gamma(z+1)\sim \sqrt{2\pi z}(\frac{z}{e})^{z}$ to check the behavior). However, as discussed in the first case, the behavior of $\frac{1}{n^{1/d}}$ in $n$ tells us that the above quantity will not be close to zero either, even if $n$ is large.