I'm reading "The Elements of Statistical Learning", in Fig. 2.8 there is a simulation example highlighting curse of dimensionality with $1$-NN (Nearest Neighbors). In this example the variance should dominate over bias when dimension is large. The problem is as follows.

$X$ has $p$ components, each component $X_i$ is independent and follows a uniform distribution on $[-1, 1]$.

We estimate $F(X) = \frac{1}{2} \left( X_1 + 1 \right)^3$ in $x_0 = \mathbf{0}$ by using $1$-NN algorithm (with Euclidian metric). The random variable related to this prediction is called $\hat{Y}$.

The aim is to get the behavior of bias and variance when $p$ is large and training sample is fixed to $N=1000$.

I don't understand why the variance should dominate heavily bias here, as shown in the following figure (on the right).

Simulation example with 1-NN

Here my understanding of the problem:

When $p$ is large, and because $N$ is fixed, $1$-NN will select an element $\hat{X}$ such that $\hat{X}_1$ follows $\text{Unif}([-1,1])$ approximatively (curse of dimensionality).

We write $\hat{Y} = F(\hat{X})=4\left(\frac{\hat{X}_1+1}{2} \right)^3 = 4U^3$ with $U$ following $\text{Unif}([0,1])$.

So we obtain the bias and variance as follows:

$$\text{Bias} = \mathbb{E}(\hat{Y}) - F(x_0) = 4\mathbb{E}(U^3) - 1/2 = 4/4 - 1/2 = 0.5$$


$$\text{Var} = \mathbb{E}(\hat{Y}^2) - \mathbb{E}(\hat{Y})^2 = 16\mathbb{E}(U^6) - \left( 1 \right)^2 = 16/7 - 1 \approx 1.28.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.