Answer: Curse of Dimensionality: Shell Concentration

Key Idea / Intuition

The core insight is embarrassingly clean: in high dimensions, the volume of a ball scales as $r^d$, so shrinking the radius even slightly collapses the volume exponentially fast. Think of it this way — in $d$ dimensions, "most" of the ball lives near its boundary because volume is dominated by the outermost layer, just as most of the mass of a thin-shelled balloon is in the rubber, not the air inside. This geometric fact has devastating consequences for any distance-based method.

---

Formal Proof / Solution

Part (a): Nearest Neighbor Distance in the Hypercube

Let $r$ be the distance to the nearest neighbor. For a query point, the probability that a single point falls outside a ball of radius $r$ is roughly $1 - \text{Vol}(B^d(r) \cap [0,1]^d)$.

A simpler clean version: consider a $k$-NN rule that captures fraction $p$ of the data. The side length $s$ of a hypercube containing fraction $p$ of the unit hypercube satisfies:

$s^d = p \implies s = p^{1/d}.$

For $k=1$, $p = 1/n$, so the required side length is:

$s = \left(\frac{1}{n}\right)^{1/d} = n^{-1/d}.$

As $d \to \infty$ with $n$ fixed:

$n^{-1/d} = e^{-\ln(n)/d} \to e^0 = 1.$

So the neighborhood needed to find even 1 neighbor expands to the entire space. Distance loses meaning.

---

Part (b): Volume Concentrates in a Shell

The volume of a $d$-dimensional ball of radius $r$ is:

$\text{Vol}(B^d(r)) = C_d \, r^d,$

where $C_d = \pi^{d/2}/\Gamma(d/2+1)$ is a constant depending only on $d$.

Therefore:

$\frac{\text{Vol}(B^d(1)) - \text{Vol}(B^d(1-\varepsilon))}{\text{Vol}(B^d(1))} = \frac{C_d \cdot 1^d - C_d \cdot (1-\varepsilon)^d}{C_d \cdot 1^d} = 1 - (1-\varepsilon)^d.$

Since $0 < 1-\varepsilon < 1$, we have:

$(1-\varepsilon)^d \to 0 \quad \text{as } d \to \infty.$

Therefore:

$\frac{\text{Vol}(B^d(1)) - \text{Vol}(B^d(1-\varepsilon))}{\text{Vol}(B^d(1))} = 1 - (1-\varepsilon)^d \to 1. \qquad \blacksquare$

Concretely: In $d = 100$ dimensions, with $\varepsilon = 0.05$:

$1 - (0.95)^{100} \approx 1 - e^{-5.13} \approx 0.994.$

Over 99.4% of the ball's volume lives in the outermost 5% shell!

---

Part (c): Implications for $k$-NN Classifiers

The combined picture is stark:

1. All points are far away: nearest neighbors are nearly as far as the farthest point. The notion of "close" becomes meaningless.

2. All points are equidistant: since data lives in a thin shell, the ratio of max to min distance satisfies: $\frac{\max_i \|x - x_i\|}{\min_i \|x - x_i\|} \to 1 \quad \text{as } d \to \infty.$ Sorting by distance becomes numerically unstable and semantically vacuous.

3. $k$-NN needs exponentially more data: to maintain a fixed neighborhood fraction $p$, you need $n \sim (1/p)^d$ points — exponential in $d$.

Practical takeaway (from ESL Chapter 2): In $d = 10$ dimensions, to cover 1% of the data range in each direction, you need $0.01^{-10} = 10^{20}$ training points. This is the curse of dimensionality — distance-based methods silently degrade as dimension grows, unless the data has low intrinsic dimension or strong structure (like smoothness or sparsity).