# In k-NN, how does the condition $k(N)/N \to 0$ ensure that all the k nearest neighbors are close to a given test point $\mathbf{x}$?

Consider the k-NN algorithm and let $$k(N)$$ be the choice of k as a function of N (data points).

For $$N \to \infty$$, if $$k(N) \to \infty$$ and $$k(N)/N \to 0$$, then k-NN converges to optimal classifier.

Question: How does the condition $$k(N)/N \to \infty$$ ensure that all the k nearest neighbors are close to a given test point $$\mathbf{x}$$?

Theorem 6.2

The goal here is to prove the fraction of the test point $$\mathbb{x}$$'s $$k$$ nearest neighbors with $$y=1$$ approximates the conditional probability $$P(y=1|\mathbb{x})$$ defined as $$\pi(\mathbb{x})$$, therefore strictly speaking you only need to prove all $$\mathbb{x}$$'s $$k(N)$$ nearest neighbors out of $$N$$ data points are close to $$\mathbb{x}$$ relative to the maximum $$N$$. Formally you define a ratio $$r$$ between $$\mathbb{x}$$ and its farthest neighbor within its $$k$$ nearest neighbors which is nothing but the $$k$$th nearest neighbor, divided by the maximum distance. Under the assumption of $$k(N)/N$$ which means the fraction of points within $$r$$ of $$\mathbb{x}$$ approaches $$0$$ in the limit as $$N$$ approaches $$\infty$$, this relative $$r$$ must approach $$0$$ too.
• Once you understand what the goal the condition $k(N)/N \to 0$ can achieve, my propositions would become clear. I've highlighted the goal here is to use the faction of a test point's 'nearest neighbors with class label 1' as a proxy to the 'conditional probability of class label 1 given the said data feature', ensuring KNN classifier converges to the optimal classifier in the limit with infinite training data. Indeed the mere absolute distance in your reference never approaches 0 especially if you have numerous nearest neighbors, only relative distance approaches 0 and this implies the goal. Nov 23 at 8:31