Consistency and the factor of two
Section of Nearest neighbours, part of Statistical learning
Consistency and the factor of two
| Type | Section |
| Taught in | Nearest neighbours |
| Part | Statistical learning |
Theorem 1 (Bayes consistency of k-nearest neighbours) In fixed-dimensional Euclidean space, the standard independent identically distributed k-nearest-neighbour rule is weakly universally consistent when k=k_n\to\infty and k_n/n\to 0, with appropriate tie handling: its expected risk approaches the Bayes risk. More neighbours reduce voting noise. A vanishing sample fraction keeps the neighbourhood local.
Fixed-k bounds, including the factor-two bound for one neighbour, concern asymptotic risk under their stated conditions. They are not finite-sample upper bounds for an arbitrary metric, and they are not a promise about one iris split.
The factor of two has a short argument for two classes. As n\to\infty, the nearest neighbour of a fixed x converges to x, so its label is an independent draw from the same conditional distribution that produced the label Y of a fresh point at x. Write \tau=\tau_1(x). The two labels differ with probability
2\tau(1-\tau):
either the new point is class 1 and the neighbour is class 0, which has probability \tau(1-\tau), or the reverse, which has the same probability. The Bayes rule, which knows \tau(x), errs with conditional probability
r(x)=\min(\tau,1-\tau).
The identity \tau(1-\tau)=r(1-r) rewrites the nearest-neighbour conditional error as 2r(1-r). To see the identity, take \tau\le 1/2, so r=\tau and \tau(1-\tau)=r(1-r). If instead \tau>1/2, then r=1-\tau and \tau(1-\tau)=(1-r)r again.
Taking the expectation, the asymptotic nearest-neighbour error is
\mathbb{E}\bigl[2r(X)\bigl(1-r(X)\bigr)\bigr]\le 2\mathbb{E}\bigl[r(X)\bigr]=2R^*,
where R^*=\mathbb{E}[r(X)] is the Bayes risk, because 1-r\le 1. Jensen’s inequality, using the concavity of u\mapsto u(1-u) on [0,1] together with \mathbb{E}[r(X)]=R^*, gives the sharper Cover–Hart bound
\mathbb{E}\bigl[2r(1-r)\bigr]\le 2R^*(1-R^*).
Concavity says \mathbb{E}[r(1-r)]\le R^*(1-R^*), and the factor 2 remains. The assumption that did the work is the convergence of the neighbour to x, which makes the neighbour’s label a fresh draw from \tau(x) rather than a draw from some other region. No parametric model was used. Even k=1, which stores the sample and estimates nothing else, pays at most twice the minimum possible error in the limit, and at most 2R^*(1-R^*).
The universal-consistency conditions ask for more. The neighbourhood size k must grow, so that the vote estimates \tau(x) rather than merely sampling it once, and k/n must shrink, so that the estimate is local. Finite-sample error can still be far from the Bayes error when the dimension is high or the sample is small. Consistency is a limit, not a statement about one finite sample.
A coarser fixed-k comparison multiplies the Bayes risk by 1+\sqrt{2/k}. At k=1 that multiplier is 1+\sqrt{2}\approx 2.41, larger than the factor two already proved, so the Cover–Hart bound is the sharper statement for a single neighbour. The multiplier falls toward 1 as k grows. Growing k all the way to the sample size is a different regime: the rule then predicts the majority class, and the conditions k_n\to\infty and k_n/n\to 0 both fail.
A call that assesses a pre-specified k, with scaling fit on the training rows only, is
scaled <- scale_train(x[tr, ], x[te, ])
pred <- knn(train = scaled$train, test = scaled$test, cl = y[tr], k = 7)
mean(pred != y[te])If the scaling is itself estimated, scale_train has to be refit inside every cross-validation fold. That is the laboratory on Estimating error rates.
Used in
See also
Rank distance · -nearest neighbours · Bayes consistency of -nearest neighbours · Distance and scale in nearest neighbours · Ties and the choice of k · Laboratory: what a distance metric changes · Cover–Hart bound