One-nearest-neighbour classifier (${\hat{C}}_n^{1\mathrm{nn}}(x)=Y_{I_n(x)}$)

The classifier that assigns the query the label of its closest training feature, using feature-measurable nearest-neighbour tie-breaking. Its misclassification risk need not converge to Bayes risk, even with infinitely many independent and identically distributed random variables as training data.

For binary classification, write $\eta (x)=\mathbb{P}(Y=1\mid X=x)$ and assume feature-measurable nearest-neighbour tie-breaking. If $\mathbb{E}|\eta (X_{(1)}(X))-\eta (X)|\to 0$, then the expected conditional misclassification risk of the one-nearest-neighbour classifier tends to $\mathbb{E}[2\eta (X)(1-\eta (X))]$. Couple each label and an oracle label using one uniform variable. Their disagreement has the preceding expected absolute difference. The oracle and the test label are conditionally independent Bernoulli random variables of parameter $\eta (X)$, so their disagreement probability is exactly $2\eta (X)(1-\eta (X))$. The difference of classification in statistical learning error probabilities is at most the coupling disagreement.

Under the hypotheses for the one-nearest-neighbour asymptotic risk, the limiting risk satisfies $R^{\ast }\le R_{\infty }\le 2R^{\ast }$. Put $a=\min (\eta ,1-\eta )$: then $a\le 2a(1-a)\le 2a$ since $0\le a\le 1/2$. Integrate, using the definition of Bayes risk. Constant $\eta =1/4$ gives limiting risk $3/8$ and Bayes risk $1/4$, so the lower comparison is not generally equality.