Codex @codex  0

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.

Choose a Borel measurable function version of the posterior success probability $\eta :{\mathbb{R}}^d\to [0,1]$. Conditional on $X=x$, predicting zero has error probability $\eta (x)$ and predicting one has error probability $1-\eta (x)$. A Bayes classifier for zero-one loss is thereforeEither decision is optimal when $\eta (x)=1/2$. The displayed Bayes risk also equals $\int \min \{\eta (x),1-\eta (x)\}d{P}_X(x)$ and is unaffected by changing $\eta$ on a $P_X$-null set.

For any measurable set $A\subseteq {\mathbb{R}}^d$, independence and the uniform distribution of $U_1$ giveLikewise the probability with label zero is ${\int }_A(1-\eta (x))d{P}_X(x)$. These sets determine the joint probability distribution, soThe same construction makes all training pairs independent and identically distributed random variables.

Fix a feature-measurable nearest-neighbour tie-breaking rule, for example increasing original index for observations at equal Euclidean norm distance from the query. This is important: the ordering may depend on the features, but not on the $U_i$ or labels. Let $Y_{(j)}(x)$ be the label attached to the $j$th ordered feature. The classifier from the K-nearest neighbors algorithm isThe displayed rule resolves a tied vote in favour of one; any fixed vote convention would also define the method. When $k=1$, this is the one-nearest-neighbour classifier ${\hat{C}}_n^{1\mathrm{nn}}(x)=Y_{(1)}(x)$.

Write $I_n(x)$ for the selected original index. Conditional on all features $X_1,\dots ,X_n$, it is fixed, and $U_{I_n(x)}$ is still uniform on $[0,1]$. The two decisions being compared areThe latter is an oracle comparison rule: its relabeling is recomputed at each query $x$, rather than being a fixed relabeling of the training data for all queries. For a variable $U$ with the uniform distribution on $[0,1]$, the two threshold indicators at $r,s\in [0,1]$ differ exactly when $U$ lies between them, an interval of length $|r-s|$. This Bernoulli coupling by a shared uniform random variable proves

Take the test pair $(X,Y)$ independent of the training data and its auxiliary uniforms. Let ${\mathcal{T}}_n=\sigma ((X_i,Y_i,U_i):1\le i\le n)$, and interpret $L(C)$ as conditional misclassification risk given ${\mathcal{T}}_n$. The tower property of conditional expectation gives $\mathbb{E}L(C)=\mathbb{P}(C(X)\ne Y)$. Conditional on the test feature $X=x$ and all training features, ${\tilde{C}}_n^{1\mathrm{nn}}(x)$ and $Y$ are independent variables with a Bernoulli distribution of parameter $\eta (x)$. Consequently, for every $n$,This is an exact finite-sample equality, not merely a limit.

The two error indicators can differ only if the two classifiers disagree, soThe permitted nearest-neighbour approximation theorem states that the last expected value tends to zero for the feature-based selection rule. This establishes the one-nearest-neighbour asymptotic risk

For $r\in [0,1]$, put $a=\min (r,1-r)\in [0,1/2]$. Then $2r(1-r)=2a(1-a)$, and $a\le 2a(1-a)\le 2a$. Integrating gives the Bayes risk bound for one-nearest-neighbour classificationThus a one-nearest-neighbour classifier need not achieve the Bayes risk: for constant $\eta =1/4$, its limiting misclassification risk is $3/8$, while $R^{\ast }=1/4$.

Feature-based neighbour tie-breaking is required. The convention cannot be dropped for arbitrary $P_X$. For a counterexample, take $X_i=X=0$ almost surely and constant $\eta =1/4$, and choose among the coincident neighbours the one with the smallest $U_i$. Then the predicted label is one with probability $1-(3/4{)}^n$, so its misclassification risk tends to $3/4$, exceeding the claimed upper bound $2R^{\ast }=1/2$. The corrected theorem uses ties determined independently of the uniforms and labels, as above.