Nearest Neighbours and the Curse of Dimensionality

Consistency of k-NN, the exact rate under smoothness, and the concentration argument that explains why it fails in high dimension.

Classical MLAdvanced⏱ 3 hours8 min readknnmetric spaceconsistencycurse of dimensionalitynonparametric rates

4 problems →

AssumesHigh-Dimensional Geometry and Concentration of the Norm · Empirical Risk Minimisation and Uniform Convergence

The rule and its asymptotics

Given $(x_i,y_i)_{i=1}^n$ and a query $x$ , order the training points by distance to $x$ and average the labels of the $k$ closest.

TheoremCover–Hart inequality

For the zero-one loss with $\Ycal=\{0,1\}$ , the asymptotic risk $R_{1\text{NN}}$ of the $1$ -nearest-neighbour rule satisfies

R^\star \le R_{1\text{NN}} \le 2R^\star\big(1 - R^\star\big) \le 2R^\star ,

where $R^\star$ is the Bayes risk.

TheoremUniversal consistency of k-NN (Stone)

If $k = k_n \to\infty$ and $k_n/n\to0$ , then the $k$ -NN rule is universally consistent: its risk converges to the Bayes risk for every distribution on $\R^d\times\{0,1\}$ , with no smoothness or density assumptions whatsoever.

Both are quoted from the references. Stone's theorem is a remarkable statement — there is a fully distribution-free learning rule — and it is worth pausing on why it does not contradict no free lunch. The resolution is that consistency is an asymptotic statement with no rate: for every distribution the risk eventually converges, but the sample size at which it becomes small depends on the distribution, and no free lunch says that dependence cannot be bounded uniformly.

TheoremNonparametric rate for k-NN regression

Let $y = f(x)+\varepsilon$ with $f$ being $\Lambda$ -Lipschitz on $[0,1]^d$ , $\Var(\varepsilon)=\sigma^2$ , and $x$ having a density bounded above and below on $[0,1]^d$ . Then the $k$ -NN regression estimate satisfies, at a fixed interior point,

\E\big(\hat f(x)-f(x)\big)^2 \;\lesssim\; \underbrace{\Lambda^2\left(\frac kn\right)^{2/d}}_{\text{bias}^2} + \underbrace{\frac{\sigma^2}{k}}_{\text{variance}},

which is minimised at $k \asymp n^{2/(d+2)}$ , giving

\E\big(\hat f(x)-f(x)\big)^2 \;\lesssim\; n^{-2/(d+2)} .

Key idea

The exponent $2/(d+2)$ is the curse of dimensionality written as a number. To reach accuracy $\eps$ one needs $n \asymp \eps^{-(d+2)/2}$ samples — exponential in $d$ . At $d = 10$ and $\eps = 0.1$ that is $10^6$ samples; at $d=100$ it is $10^{51}$ . And this rate is minimax optimal over the Lipschitz class, so no method does better: the problem is hard, not the algorithm.

Contrast this with the $O(p/n)$ sample complexity of covariance estimation. Both are called "the curse of dimensionality" and they differ by an exponential. The difference is parametric versus nonparametric: assuming a parametric form is what converts $\eps^{-d}$ into $d/\eps^2$ .

Why distances stop being informative

PropositionDistance contrast vanishes

Let $x, x_1,\dots,x_n$ be i.i.d. with independent coordinates of unit variance and bounded $\psi_2$ norm in $\R^d$ . Then

\frac{\max_i\norm{x_i-x}_2}{\min_i\norm{x_i-x}_2} \xrightarrow[d\to\infty]{\P} 1

for fixed $n$ , and more quantitatively, with probability at least $1-\delta$ ,

\max_i\norm{x_i - x}_2 - \min_i\norm{x_i-x}_2 \;\lesssim\; \sqrt{\log(n/\delta)} ,

while both are of order $\sqrt{2d}$ .

What this does not say

Read the hypotheses. The coordinates are assumed independent and identically scaled. That is the worst case for nearest neighbours and it is not what real data looks like. The proposition says: if your data is isotropic noise, distances carry no information. It does not say nearest-neighbour search is meaningless on real high-dimensional data, and interpreting it that way is a misreading that was common for years after Beyer et al. raised the question.

Empirical observationNearest neighbours work better than the theory predicts

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

$k$ -NN and approximate nearest-neighbour search perform far better on real high-dimensional data — image embeddings, text embeddings, audio features — than the $n^{-2/(d+2)}$ rate with $d$ the ambient dimension would allow.

What this does not say

The standard explanation is that the data concentrates near a low-dimensional structure, so the relevant exponent involves the intrinsic dimension $d_0 \ll d$ rather than the ambient one. There are theorems supporting this: under a manifold assumption the $k$ -NN rate becomes $n^{-2/(d_0+2)}$ , and doubling-dimension conditions give similar results.

But this is not a complete explanation of practice, for two reasons. Estimating $d_0$ for real data is itself hard and the estimates are unstable. And the manifold hypothesis is an assumption about data that is rarely tested in the settings where it is invoked. The honest position: the gap between the isotropic worst case and observed performance is real, low intrinsic dimension is the best available explanation, and it has not been verified quantitatively for the embeddings used in production retrieval systems.

Problems

The k-NN bias–variance balanceProof · Advanced · 1 hour Distance contrast and the failure of nearest neighboursProof · Intermediate · 30 min Two different curses of dimensionalityNumerical · Beginner · 15 min Simulate distance contrastCoding · Beginner · 30 min

References

PaperThomas M. Cover and Peter E. Hart (1967). Nearest neighbor pattern classification
PaperCharles J. Stone (1977). Consistent nonparametric regression
BookLászló Györfi, Michael Kohler, Adam Krzyżak and Harro Walk (2002). A Distribution-Free Theory of Nonparametric Regression
PaperKevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan and Uri Shaft (1999). When Is Nearest Neighbor Meaningful?

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremCover–Hart inequality for 1-NNThe asymptotic risk of the 1-nearest-neighbour rule is at most twice the Bayes risk.
TheoremUniversal consistency of k-NNWith k growing and k/n going to zero, the k-NN risk converges to the Bayes risk for every distribution.
TheoremNonparametric rate for k-NN regressionproof includedUnder Lipschitz smoothness the excess risk is of order n to the minus two over d plus two.
PropositionDistance contrast vanishes in high dimensionproof includedThe ratio of the farthest to the nearest distance among n random points tends to one as the dimension grows.
Empirical observationNearest neighbours work better than the theory predictsReal data concentrates near low-dimensional structure, so the relevant exponent is the intrinsic dimension.

Problems (4)

All problems