Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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?
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.
