# Proof: Nearest Neighbor classifier achieves Bayes rate asymptotically on countable domains

I am trying to understand in which situations the 1-NN classifier asymptotically attains the Bayes error rate. My intuition is that if the domain is countable, then 1-NN will asymptotically do as well as the Bayes classifier. Here is my proof:

We wish to show that:

$$\mathbb P(Y \neq \hat Y_N) \rightarrow \mathbb P(Y \neq \hat Y_*)$$

as $$N \rightarrow \infty$$ where $$\hat Y_N$$ is the 1-nearest neighbor classifier with a dataset of size $$N$$ and $$\hat Y_*$$ is the Bayes classifier. Recall the Bayes classifier is given by $$\mathbb 1(\eta(X) \geq 1/2)$$ where $$\eta(X) = \mathbb P(Y=1 | X)$$.

Rewriting $$\mathbb P\left(Y \neq \hat Y_N\right)$$ by expanding the cases in which the 1-NN prediction is incorrect:

$$\mathbb E \left[\mathbb P\left(Y \neq \hat Y_N | X\right)\right] = \mathbb E \left[\mathbb P\left(Y = 0, \hat Y_N =1 | X\right) + \mathbb P\left(Y = 1, \hat Y_N =0 | X\right)\right]$$

Then since $$Y,\hat Y_N$$ are independent given $$X$$ and conditioning on the dataset:

$$=\mathbb E \left[\mathbb 1\left(\hat \eta_N(\phi_N(X)) > 1/2\right)(1-\eta(X)) + \mathbb 1\left(\hat \eta_N(\phi_N(X)) \leq 1/2\right)\eta(X) \right ]$$

where $$\phi_N$$ gives the nearest neighbor in the training dataset of size $$N$$ and $$\hat\eta_N(x)$$ is the counting estimate from the training set given by: $$\sum_i \mathbb 1 (Y_i = 1, X_i = x) / \mathbb 1 (X_i = x)$$.

Expanding the expectation into a summation:

$$\sum_{x \in \mathcal X} \left \{\sum_{\mathcal D_N} \left [\mathbb 1\left(\hat \eta_N(\phi_N(x)) > 1/2\right)(1-\eta(x)) + \mathbb 1\left(\hat \eta_N(\phi_N(x)) \leq 1/2\right)\eta(x)\right] \mathbb P (D_N) \right \} \mathbb P(X=x)$$

Where the second summation is over all possible datasets of size $$N$$.

Since $$\hat \eta _N$$ converges uniformly in probability to $$\eta$$, and $$\phi_N(x)$$ converges to $$x$$ in probability, each term in the summation converges to $$\min \{\eta(x), 1-\eta(x)\} = \mathbb P(Y \neq \hat Y_* | X)$$.

I believe that if $$\mathcal X$$ was not countable, then we would also need a dominated convergence argument, which is not possible without more information about $$\eta$$.

I could use some feedback on my proof and reasoning.

EDIT: I realized this claim is incorrect since the asymptotic error rate is given by $$\mathbb E 2\eta(1-\eta)$$ which is only equal to $$\mathbb E \min\{\eta, 1-\eta \}$$ when $$\eta \in \{0, 1/2, 1\}$$ for all $$x \in \mathcal X$$. But this condition is unrelated to the countability of $$\mathcal X$$.

The error in this proof comes from assuming that $$\hat \eta_N$$ converges uniformly to $$\eta$$. This might be true for the k-NN classifier where $$k$$ grows with the sample size, $$N$$, but it is not true in general for $$k=1$$ or any fixed $$k$$. The expectation of the indicator $$\mathbb 1\left(\hat \eta_N(\phi_N(x)) > 1/2\right)$$ over the set of datasets $$D_N$$ is given by $$\mathbb P(\hat \eta_N(\phi_N(x)) > 1/2)$$, but $$\hat \eta_N$$ is not given by the counting estimate stated earlier, it is simply given by the $$Y$$ corresponding with the nearest neighbor of $$x$$. When $$\mathcal X$$ is finite, the nearest neighbor is the point itself with high probability when $$N$$ is large enough, so $$\mathbb P(\hat \eta_N(\phi_N(x)) > 1/2)$$ converges to $$\mathbb P (Y = 1 | X=x)$$ which is just $$\eta(x)$$.

• From what I recall of this proof, it makes use of a result by Cover & Hart (1967). It might be best to consult an authoritative reference and compare, as these kinds of proofs tend fall in a blind spot on Cross Validated. (At least from my own experience with these kinds of questions). Aug 29, 2021 at 16:20