Curse of dimensionality introducing bias and variance

Question

The example presented on page 23 of Elements of Statistical Learning: $Y = f(X) = e^{-8||X||^2}$. $X$ is sampled between $[-1,1]$

is the underlying structure for $Y$. Authors use k- nearest neighbors. The argument presented is:

a. For lower dimensions, the estimate $\hat{y}_0$ (using 1-nearest neighbors or k) is going to be less than $y_0$ [value of y for x=0, $y_0 = 1$].

b. As we move to higher dimensions(for X), $\hat{y}_0$ tends to be farther from 1. (very close to 0)

I am unable to get an intuition for part b. k-nearest neighbor would look at the closest ones and therefore, distance wise we would still be close to x=0. How does increased dimensionality cause it to move away.

Answer 1

Here is their example coded in R: a sample size $1000$ with points in the $p$-dimensional hypercube $[-1,1]^p$ with $p=10$:

set.seed(1)
p <- 10
samples <- 1000
matdat <- matrix(runif(samples*p, min = -1, max = 1), ncol=p)
Y <- exp(-8*rowSums(matdat^2)) 

and you get for the nearest neighbour

> max(Y)
[1] 0.005093686

rather than $1$ at the origin.

Some of this is accentuated by their particular function $Y=f(X)$, but the thousand points must be a distance between $0$ and $\sqrt{p}$ (here about $3.162$) from the origin. In this particular sample the nearest is in fact $0.812$ away and the furthest $2.534$ from the origin, and these are not unusual examples

In general, the distances of points in this hypercube from the origin are approximately normally distributed with mean about $\sqrt{\frac{p}3 -\frac1{15}}$ and standard deviation about $\sqrt{\frac1{15}}\approx 0.258$. It is this small standard deviation not changing materially with $p$ which gives rise to this particular form of the curse of dimensionality

If you were to increase $p$ to $1000$ then you would expect more than $99.999\%$ of points to be at distances between $17$ and $19.5$ from the origin, even when they could have been anywhere between $0$ and $31.62$ away. So not only would the nearest neighbours probably be more than half the maximum distance away, but the furthest sample points would not be much further away than the nearest ones, making the whole predictive process highly dubious at high dimensions