# rigorous proof of a statement in Elements of Statistical Learning

In Section 2.4 of the book ESL by Hastie etc., it was said that $\hat{f}(x)=\text{Ave}(y_i\mid x_i\in N_k(x))\rightarrow E(Y\mid X=x)$ when $N, k\rightarrow \infty$ and $k/N\rightarrow 0$.

Here $N_k(x)$ is the neighborhood containing the $k$ points and "Ave" denotes average.

Is there a rigorous proof of this statement?

• Although the notation is a little unclear, it looks remarkably like a Law of Large Numbers. These date to Jacob Bernoulli's time, published posthumously in 1713.
– whuber
May 2, 2014 at 16:34
• could you elaborate about the analogy? I actually don't see it immediately, for example, why the requirement $k/N\rightarrow 0$? May 2, 2014 at 21:34
• I have no idea because you haven't provided a context for understanding what this statement is trying to do. For this question to be comprehensible, it needs to include descriptions of what the various terms mean.
– whuber
May 2, 2014 at 21:44
• It is actually here statweb.stanford.edu/~tibs/ElemStatLearn/printings/… on page 19. May 2, 2014 at 22:09

This is about the consistency of the k-NN regression estimator. Section 6.2 of A distribution-free theory of nonparametric regression‎, László Györfi, Michael Kohler, Adam Kryzak, Harro Walk, Springer-Verlag, 2002 shows weak consistency based on Stone's theorem. See Theorem 6.1 and the proof developed there. The next section of the same book gives you rates. The Hastie book is pretty vague about the type of consistency that they are talking about, but I am guessing that they talk about almost sure uniform convergence of the estimator. This usually requires stronger conditions, such as the existence of a density w.r.t. the Lebesgue measure of the distribution of the inputs ($X$). The proof would be very similar to what you see in Section 6.2.