Answer: Curse of Dimensionality: Volume Collapse

Key Idea / Intuition

Volume in high dimensions is brutally concentrated near the boundary of the cube, not the interior. A neighborhood that seems "small" in each individual dimension actually covers a vanishingly small fraction of the total volume — yet to capture a fixed fraction of the data, the neighborhood must stretch to cover nearly the entire range in every dimension. Local methods implicitly assume "nearby" points are close in all relevant ways, but in high dimensions there are no truly nearby points.

---

Formal Proof / Solution

Step 1: The side-length formula

If you use a hypercubic neighborhood of side length $\ell$ centered at a point in $[0,1]^p$, its volume is $\ell^p$. The total volume of the unit hypercube is $1$. So to capture a fraction $r$ of uniformly distributed data:

$\ell^p = r \implies \ell = r^{1/p}.$

Step 2: Numerical illustration for $r = 0.01$

| Dimension $p$ | Required side length $\ell = (0.01)^{1/p}$ | |:---:|:---:| | $p = 1$ | $0.01$ (1% of range) | | $p = 2$ | $0.1$ (10% of range) | | $p = 10$ | $(0.01)^{0.1} = 10^{-0.2} \approx 0.63$ (63% of range!) | | $p = 100$ | $(0.01)^{0.01} = 10^{-0.02} \approx 0.955$ (95% of range!) |

To capture just 1% of the data in 10 dimensions, you already need a neighborhood covering 63% of the range in each coordinate. At $p = 100$, you need 95% of the range. The neighborhood is no longer "local" at all.

Step 3: The reverse question — volume of a fixed small neighborhood

Now fix $\ell = 0.1$ (10% of the range in each direction). The fraction of data captured is:

$r = \ell^p = (0.1)^p = 10^{-p}.$

| $p$ | Fraction captured | |:---:|:---:| | $1$ | $10\%$ | | $2$ | $1\%$ | | $10$ | $10^{-10} \approx 10^{-8}\%$ | | $\infty$ | $\to 0$ |

As $p \to \infty$, any fixed neighborhood (with $\ell < 1$) captures an exponentially vanishing fraction of the data. You would need an exponentially large dataset $n$ just to have even one neighbor nearby.

Step 4: The core statistical consequence

For a $k$-NN estimator to be consistent, you need:

• $k \to \infty$ (enough neighbors for stability), and
• $k/n \to 0$ (neighbors are truly local).

But in high dimensions, achieving locality requires either:

• a neighborhood so large it is no longer "local" (high bias), or
• so few actual neighbors that estimates are noisy (high variance).

This is the curse of dimensionality: the fundamental conflict between locality and statistical efficiency that makes nonparametric local methods degrade exponentially with $p$.

Summary

$\boxed{\ell(p, r) = r^{1/p} \xrightarrow{p \to \infty} 1 \quad \text{for any fixed } r > 0.}$

No matter how small a fraction you want to capture, the required neighborhood eventually spans the entire space. Conversely, any genuinely small neighborhood contains an exponentially small fraction of the data.