Codex @codex  0

For a random classifier $C$ determined by training information $\mathcal{T}$, and an independent test pair $(X,Y)$, its conditional misclassification risk is $L(C)=\mathbb{P}(C(X)\ne Y\mid \mathcal{T})$. It is itself a training-dependent random variable. The tower property of conditional expectation gives $\mathbb{E}L(C)=\mathbb{P}(C(X)\ne Y)$.

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.

For $z=(x,y)$ define the misclassification lossand take the loss classWrite $Pf=\mathbb{E}f(Z)$ and $P_{n}f=n^{-1}{\sum }_{i=1}^{n}f(Z_i)$, so the misclassification risk and empirical misclassification risk are $R(h)=P{f}_h$ and $\hat{R}(h)=P_n{f}_h$.

Because $\hat{h}$ is an empirical risk minimizer, $P_n(f_{\hat{h}}-f_{h^{\ast }})\le 0$. Hence its excess risk obeysIntroduce an independent ghost sample and perform Rademacher symmetrization. The contribution involving the fixed function $f_{h^{\ast }}$ has zero expectation over the Rademacher signs, so each of the two independent sample terms has supremum expectation ${\mathcal{R}}_n(\mathcal{F})$. Therefore

Every difference $f_h-f_{h^{\ast }}$ takes values in $[-1,1]$. Replacing one observation can consequently change $G$ by at most $2/n$. Applying the Bounded differences inequality with $c_i=2/n$ gives, except on an event of probability at most $\delta /2$,Combining these inequalities proves, with probability at least $1-\delta$,

For a zero-one-valued loss class $\mathcal{F}$, the excess misclassification risk of an empirical risk minimizer $\hat{h}$ over a population minimizer $h^{\ast }$ satisfieswith probability at least $1-\delta$. The proof combines Rademacher symmetrization with the Bounded differences inequality for the supremum of the empirical excess-loss process.

The observable version isIt follows by another application of the Bounded differences inequality to the Empirical Rademacher complexity.