45.08.11 · mathematical-statistics / 08-learning-methods

k-Nearest-Neighbors and Local Regression

shipped3 tiersLean: none

Anchor (Master): Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e §6.1-6.6 and §2.5 (local methods, the curse of dimensionality); Cover & Hart 1967 (asymptotic 1-NN risk $\leq 2 R^{*}$ ); Stone 1977 Ann. Statist. 5 (universal consistency of nearest-neighbour and local-average rules); Fan & Gijbels 1996 Ch. 3 (minimax efficiency and design adaptation of local polynomial fits)

Intuition Beginner

Some prediction methods study the data once, distil it into a formula, and then throw the data away. Memory-based methods do the opposite: they keep all the training cases and answer each new question by looking up the cases most similar to it. To guess a new house's price, find the handful of past sales whose size and location are closest, and report their average price. To guess whether an email is spam, look at the nearest few emails you have already labelled and take a vote. There is no formula learned in advance; the data itself is the model.

The number of neighbours you consult is the one dial that matters most. Ask only the single closest case and your answer follows it exactly, jumping around as you move from query to query. Ask many neighbours and the answer is a smooth average, steadier but blurrier, because some of those neighbours are not really that close. Few neighbours means a jumpy, detailed fit; many neighbours means a smooth, coarse one. This is the same tension between detail and stability that runs through all of model fitting.

A cousin idea improves the plain average. Instead of giving every neighbour an equal say, weight the close ones more than the far ones, with the weights fading smoothly with distance. This is kernel-weighted prediction, and a refinement fits a small tilted line through the nearby points rather than a flat average, which behaves much better at the edges of the data where one-sided neighbours would otherwise drag the answer.

The catch is that "close" gets hard to define when each case carries many measurements. In a high-dimensional space, even your nearest neighbours are surprisingly far away, so the neighbourhood you trust is no longer local. That failure of locality is the price these otherwise simple methods pay.

Visual Beginner

Picture points scattered on a plane, each a training case, and a new query marked with a star. Draw a circle around the star just large enough to enclose its $k$ closest points; the prediction is the average of those points' values. Shrink $k$ and the circle tightens onto one or two points; grow $k$ and the circle swells to take in distant, less relevant cases.

Number of neighbours $k$	Fit shape	Bias	Variance
Very small (1-3)	Ragged, follows every point	Low	High
Moderate	Smooth with local detail	Medium	Medium
Very large	Nearly a flat global average	High	Low

Reading the table and the picture together: the circle's size is the smoothness knob. A tiny circle trusts only the most similar cases and pays for it with a jumpy answer; a large circle is calm but reaches for cases that are not truly alike.

Worked example Beginner

Five past house sales, each with a lot size (in thousands of square feet) and a sale price (in thousands of dollars). We predict the price of a new house with lot size $5$ , using nearest neighbours.

House	Lot size	Price
1	2	150
2	4	200
3	6	280
4	7	330
5	9	360

Step 1. Measure distance from the query lot size $5$ to each house: house 1 is $∣5 - 2∣ = 3$ away, house 2 is $∣5 - 4∣ = 1$ , house 3 is $∣5 - 6∣ = 1$ , house 4 is $∣5 - 7∣ = 2$ , house 5 is $∣5 - 9∣ = 4$ .

Step 2. The 1-nearest neighbour. The closest distance is $1$ , tied between houses 2 and 4 — sorry, between houses 2 and 3 (both at distance $1$ ). Taking house 2, the 1-NN prediction is its price, $200$ . Taking house 3 instead gives $280$ . The single-neighbour answer is unstable: a tie or a tiny shift flips it.

Step 3. The 3-nearest neighbours. The three smallest distances are $1$ (house 2), $1$ (house 3), and $2$ (house 4). Their prices are $200$ , $280$ , $330$ , averaging $(200 + 280 + 330) /3 = 810/3 = 270$ .

Step 4. Distance weighting. Give each of the three neighbours a weight that fades with distance, say $w = 1/ (1 + d)$ : house 2 and house 3 get $1/2 = 0.5$ , house 4 gets $1/3 \approx 0.333$ . The weighted average is $(0.5 \cdot 200 + 0.5 \cdot 280 + 0.333 \cdot 330) / (0.5 + 0.5 + 0.333) = (100 + 140 + 110) /1.333 \approx 350/1.333 \approx 263$ .

What this tells us: the 3-neighbour average of $270$ is steadier than either single-neighbour answer, and weighting pulls it slightly toward the two closest sales, giving $263$ . Consulting more neighbours trades a little accuracy near the query for a lot of stability.

Check your understanding Beginner

Exercise (easy, multiple choice).

You change a $k$ -nearest-neighbour regressor from $k = 1$ to $k = 25$ . What typically happens to the fit?

A. It becomes more jagged and follows individual points more closely.

B. It becomes smoother and more biased, but steadier across datasets.

C. It stops working because $25$ neighbours is too many.

D. Bias and variance both rise.

Hint

Averaging more neighbours calms the answer but reaches for cases that are farther away.

Answer

B. A larger $k$ averages over more, hence more distant, neighbours, smoothing the fit and steadying it from one dataset to the next (lower variance), at the cost of pulling the average away from the truth near the query (higher bias). Feedback-correct: large $k$ is the smooth, high-bias, low-variance end. Feedback-wrong: small $k$ , not large, gives the jagged low-bias fit; the method works fine at $k = 25$ , and bias and variance move in opposite directions, not together.

Formal definition Intermediate+

Let $(X, Y)$ have a joint law on $X \times Y$ with $X \subseteq R^{p}$ equipped with a metric $d$ , and let ${(x_{i}, y_{i})}_{i = 1}^{n}$ be an i.i.d. training sample. Write $η (x) = E [Y ∣ X = x]$ for the regression function (for classification with $Y = {0, 1}$ , $η (x) = P (Y = 1 ∣ X = x)$ ). For a query $x$ , let $(x_{(1)}, y_{(1)}), \dots, (x_{(n)}, y_{(n)})$ denote the training cases reindexed so that $d (x, x_{(1)}) \leq d (x, x_{(2)}) \leq \dots$ , and let $N_{k} (x) = {x_{(1)}, \dots, x_{(k)}}$ be the $k$ -nearest-neighbour set.

$k$ -nearest-neighbour estimators. The $k$ -NN regressor is the local average over $N_{k} (x)$ ,

\hat{f}_{k} (x) = \frac{1}{k} x_{i} \in N_{k} (x) \sum y_{i} = i = 1 \sum n W_{ni} (x) y_{i}, W_{ni} (x) = \frac{1}{k} 1 {x_{i} \in N_{k} (x)} .

The $k$ -NN classifier predicts the plurality label among $N_{k} (x)$ ; for two classes this is $\overset{g}{^} (x) = 1 {\hat{f}_{k} (x) > \frac{1}{2}}$ with $\hat{f}_{k}$ the local fraction of class- $1$ neighbours. The single-nearest-neighbour rule is the case $k = 1$ .

Kernel-weighted (Nadaraya-Watson) regression. With a kernel $K \geq 0$ and bandwidth $h > 0$ , write $K_{h} (x, x_{i}) = K (d (x, x_{i}) / h)$ . The Nadaraya-Watson estimator is the kernel-weighted average

\hat{f}_{N W} (x) = \frac{\sum _{i = 1}^{n} K _{h} ( x , x _{i} ) y _{i}}{\sum _{i = 1}^{n} K _{h} ( x , x _{i} )} = i = 1 \sum n W_{ni} (x) y_{i}, W_{ni} (x) = \frac{K _{h} ( x , x _{i} )}{\sum _{j} K _{h} ( x , x _{j} )},

the solution of the locally weighted constant fit $min_{c} \sum_{i} K_{h} (x, x_{i}) (y_{i} - c)^{2}$ . The kernel-density estimator $\overset{p}{^} (x) = \frac{1}{n h ^{p}} \sum_{i} K_{h} (x, x_{i})$ is the companion object of 26.08.01.

Local polynomial regression. Fix a degree $r \geq 0$ . The local polynomial fit solves, for each query $x$ ,

β_{0}, \dots, β_{r} min i = 1 \sum n K_{h} (x, x_{i}) (y_{i} - β_{0} - β_{1} (x_{i} - x) - \dots - β_{r} (x_{i} - x)^{r})^{2},

and reports $\hat{f} (x) = \hat{β}_{0}$ . The case $r = 0$ recovers Nadaraya-Watson; $r = 1$ is local linear regression. In matrix form, with $B$ the design matrix of monomials $(x_{i} - x)^{j}$ and $W = diag (K_{h} (x, x_{i}))$ , the fit is $\hat{f} (x) = e_{1}^{⊤} (B^{⊤} WB)^{- 1} B^{⊤} Wy = \sum_{i} ℓ_{i} (x) y_{i}$ , a linear smoother whose weights $ℓ_{i} (x)$ form the equivalent kernel.

Risk. For classification the risk is the misclassification probability $R (\overset{g}{^}) = P (\overset{g}{^} (X) \neq = Y)$ , minimised by the Bayes rule $g^{*} (x) = 1 {η (x) > \frac{1}{2}}$ at the Bayes risk $R^{*} = E [min (η (X), 1 - η (X))]$ . All three estimators are linear smoothers $\hat{f} (x) = \sum_{i} W_{ni} (x) y_{i}$ differing only in the weight scheme; the notation $N_{k} (x)$ , $W_{ni} (x)$ , $η$ , $K_{h}$ , $ℓ_{i} (x)$ , $R^{*}$ is recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"The 1-NN rule is consistent because it always uses the closest point." Using a single neighbour keeps the variance from vanishing: even as $n \to \infty$ the nearest label is one noisy draw, so the 1-NN risk converges to a limit above the Bayes risk (the Cover-Hart limit), not to it. Consistency needs $k \to \infty$ as well as $k / n \to 0$ .
"Nadaraya-Watson and local linear differ only cosmetically." They differ exactly where it matters: at the boundary of the design and at peaks of $f$ , the local-constant fit has bias of order $h$ (one-sided neighbours pull the average), whereas local linear cancels that leading term and keeps bias of order $h^{2}$ throughout. The fix costs nothing in rate but removes the boundary penalty.
"Euclidean distance is the natural metric, so feature scaling is a detail." A nearest-neighbour rule is only as good as its metric: rescaling one coordinate by a factor $100$ makes it dominate every distance, silently changing which points are "near". Standardising features, or learning an adaptive metric, is part of the method, not a preprocessing afterthought.

Key theorem with proof Intermediate+

The signature theorem of memory-based learning is that the simplest possible classifier — predict the label of the single nearest stored case — is, with unlimited data, never worse than twice the best achievable error. This is the result that made nearest-neighbour methods respectable: an assumption-free rule with a hard performance guarantee.

Theorem (Cover-Hart asymptotic nearest-neighbour risk). Consider two-class classification with $η (x) = P (Y = 1 ∣ X = x)$ continuous at $μ$ -almost every $x$ . Let $R_{n}$ be the risk of the single-nearest-neighbour rule trained on $n$ i.i.d. samples and $R = lim_{n \to \infty} R_{n}$ its asymptotic risk. Then

R^{*} \leq R = E [2 η (X) (1 - η (X))] \leq 2 R^{*} (1 - R^{*}) \leq 2 R^{*},

where $R^{*} = E [min (η (X), 1 - η (X))]$ is the Bayes risk. ^{[Cover 1967]}

Proof. Fix a query $x$ and let $x_{n}^{'}$ be its nearest neighbour in the sample, with label $Y_{n}^{'}$ . Because the samples are i.i.d. with $x$ in the support, $d (x, x_{n}^{'}) \to 0$ almost surely as $n \to \infty$ , so by continuity $η (x_{n}^{'}) \to η (x)$ . The 1-NN rule predicts $Y_{n}^{'}$ , and it errs at $x$ when the query's own label $Y$ (drawn from $η (x)$ ) differs from $Y_{n}^{'}$ (drawn from $η (x_{n}^{'})$ , independent given the locations). The conditional probability of disagreement is

P (Y \neq = Y_{n}^{'} ∣ x, x_{n}^{'}) = η (x) (1 - η (x_{n}^{'})) + (1 - η (x)) η (x_{n}^{'}) .

Letting $n \to \infty$ and using $η (x_{n}^{'}) \to η (x)$ gives the limiting conditional error $2 η (x) (1 - η (x))$ . Taking expectation over $X$ yields $R = E [2 η (X) (1 - η (X))]$ .

For the lower bound, the pointwise Bayes error is $min (η, 1 - η)$ , and $2 η (1 - η) \geq min (η, 1 - η)$ for all $η \in [0, 1]$ (write $m = min (η, 1 - η)$ ; then $2 η (1 - η) = 2 m (1 - m) \geq m$ since $m \leq \frac{1}{2}$ ), so $R \geq R^{*}$ . For the upper bound, set $m (x) = min (η (x), 1 - η (x))$ , so the pointwise 1-NN error is $2 m (x) (1 - m (x))$ . The function $t \mapsto 2 t (1 - t)$ is concave on $[0, \frac{1}{2}]$ , so by Jensen's inequality

R = E [2 m (X) (1 - m (X))] \leq 2 E [m (X)] (1 - E [m (X)]) = 2 R^{*} (1 - R^{*}) \leq 2 R^{*},

the last step because $1 - R^{*} \leq 1$ . $□$

Bridge. This bound is the foundational reason nearest-neighbour methods are taken seriously: with no model of the class boundary at all, the crudest rule captures at least half the available classification information, and the factor $2 R^{*} (1 - R^{*})$ shows the penalty is small exactly when the problem is easy ( $R^{*}$ near $0$ ). The result builds toward the consistency theory of the Advanced results, where allowing $k \to \infty$ removes the residual gap entirely and the local average converges to $η$ itself; the bridge is that 1-NN pays a variance tax for using a single neighbour, and $k$ -NN with $k \to \infty, k / n \to 0$ is exactly the move that drives that tax to zero. The factor-of-two ceiling generalises: for the $k$ -NN rule the asymptotic risk tightens toward $R^{*}$ as $k$ grows, and putting these together with the bias-variance reading of 45.06.02 identifies $k$ as a smoothing parameter, the same role the bandwidth $h$ plays for kernel methods. This appears again in the partition view shared with 45.08.04, where a tree leaf is an adaptive neighbourhood and the leaf average is a $k$ -NN-like local mean.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

For the $k$ -NN regressor $\hat{f}_{k} (x) = \frac{1}{k} \sum_{ℓ = 1}^{k} Y_{(ℓ)}$ with $Y_{(ℓ)} = f (x_{(ℓ)}) + ε_{(ℓ)}$ , treat the neighbour locations as fixed and the noises as independent with variance $σ^{2}$ . Derive the variance of the fit and its leading bias, and explain the opposite dependence on $k$ .

Hint

The variance of an average of $k$ independent noises is $σ^{2} / k$ ; the bias comes from averaging $f$ over points at nonzero distance from $x$ .

Answer

The variance is $Var (\hat{f}_{k} (x)) = \frac{1}{k ^{2}} \sum_{ℓ = 1}^{k} Var (ε_{(ℓ)}) = σ^{2} / k$ , falling as $1/ k$ . The bias is $E [\hat{f}_{k} (x)] - f (x) = \frac{1}{k} \sum_{ℓ} f (x_{(ℓ)}) - f (x)$ ; as $k$ grows the neighbour set reaches farther from $x$ , so the averaged values of $f$ drift away from $f (x)$ and the (squared) bias grows. Small $k$ is low-bias, high-variance; large $k$ is high-bias, low-variance — the bias-variance trade-off of 45.06.02 with $k$ as the smoothing parameter, the effective number of parameters being $n / k$ . Rubric: full credit for $σ^{2} / k$ , the local-averaging bias expression, and the opposed monotonicities.

Exercise 4 (medium, symbolic).

Show that the Nadaraya-Watson estimator $\hat{f}_{N W} (x)$ is the minimiser of the locally weighted constant objective $\sum_{i} K_{h} (x, x_{i}) (y_{i} - c)^{2}$ , and hence is the locally weighted mean.

Hint

Differentiate the weighted sum of squares in $c$ and set it to zero.

Answer

Let $ϕ (c) = \sum_{i} K_{h} (x, x_{i}) (y_{i} - c)^{2}$ . Then $ϕ^{'} (c) = - 2 \sum_{i} K_{h} (x, x_{i}) (y_{i} - c)$ , which vanishes at $c = \sum_{i} K_{h} (x, x_{i}) y_{i} / \sum_{i} K_{h} (x, x_{i})$ , and $ϕ^{''} (c) = 2 \sum_{i} K_{h} (x, x_{i}) > 0$ confirms a minimum. This minimiser is exactly $\hat{f}_{N W} (x)$ , so the Nadaraya-Watson fit is the kernel-weighted mean of the responses, the degree- $0$ case of local polynomial regression. Rubric: full credit for the first-order condition recovering the weighted mean and the positive second derivative.

Exercise 5 (medium, short-answer).

Explain why local linear regression has smaller bias than Nadaraya-Watson at the boundary of the design region, and why this matters in practice.

Hint

At a boundary the available neighbours all lie on one side; a flat fit averages them, a tilted line extrapolates the local slope.

Answer

Near a boundary the kernel window is one-sided: all the neighbours of a left-edge query lie to its right. The Nadaraya-Watson fit averages their responses, so if $f$ is sloping it returns a value biased toward the interior, a bias of order $h$ (linear in bandwidth). Local linear regression fits a line through the weighted neighbours and reports its value at $x$ ; the slope term absorbs the local trend, cancelling the leading one-sided term and leaving bias of order $h^{2}$ , the same order it has in the interior. This "automatic boundary correction" matters because the edges are where extrapolation is most dangerous and where many quantities of interest live; it is the main reason local linear is the default degree in practice. Rubric: full credit for identifying one-sided neighbours as the source, the $O (h)$ versus $O (h^{2})$ improvement, and the slope term as the mechanism.

Exercise 6 (hard, symbolic).

For a one-dimensional interior point, the Nadaraya-Watson estimator with a symmetric kernel of variance $μ_{2} (K) = \int u^{2} K (u) d u$ and design density $p$ has leading bias $\frac{1}{2} h^{2} μ_{2} (K) (f^{''} (x) + 2 f^{'} (x) \frac{p ^{'} ( x )}{p ( x )})$ , while local linear has leading bias $\frac{1}{2} h^{2} μ_{2} (K) f^{''} (x)$ . Identify the extra term in the Nadaraya-Watson bias and explain why local linear is design-adaptive.

Hint

Compare the two bias expressions; the difference is a single term involving the design density $p$ .

Answer

The extra Nadaraya-Watson term is $h^{2} μ_{2} (K) f^{'} (x) p^{'} (x) / p (x)$ : the local-constant fit is biased by the gradient of the design density coupled to the slope of $f$ , because where data are denser on one side the weighted average is pulled that way. Local linear regression removes this term entirely — its leading bias $\frac{1}{2} h^{2} μ_{2} (K) f^{''} (x)$ depends only on the curvature of $f$ , not on $p$ or $p^{'}$ . This is the sense in which local linear is design-adaptive: its bias is unaffected by how the predictor values are distributed, so it behaves the same in sparse and dense regions and at the boundary (where $p^{'} / p$ blows up), which is exactly the failure mode that cripples Nadaraya-Watson at the edges. Rubric: full credit for naming the $f^{'} p^{'} / p$ term, attributing it to design-density asymmetry, and explaining design adaptivity as the elimination of that term.

Exercise 7 (hard, short-answer).

State Stone's conditions for universal consistency of a local-averaging estimator $\hat{f}_{n} (x) = \sum_{i} W_{ni} (x) Y_{i}$ , and show how they specialise to $k$ -NN to give the requirements $k \to \infty$ and $k / n \to 0$ .

Hint

Stone's key conditions are that no single weight dominates and that the weight concentrates on shrinking neighbourhoods. For $k$ -NN each weight is $1/ k$ and the neighbourhood radius shrinks only if $k$ grows slowly relative to $n$ .

Answer

Stone (1977) proves universal $L^{2}$ consistency of $\hat{f}_{n} (x) = \sum_{i} W_{ni} (x) Y_{i}$ under conditions of the form: (i) a Besicovitch-type covering condition bounding $E \sum_{i} ∣ W_{ni} (X) ∣ g (X_{i})$ by a constant times $E g (X)$ for all integrable $g$ ; (ii) asymptotic negligibility of the maximum weight, $E [max_{i} W_{ni} (X)] \to 0$ ; and (iii) concentration of weight on shrinking neighbourhoods, $\sum_{i} W_{ni} (X) 1 {∥ X_{i} - X ∥ > δ} \to 0$ for every $δ > 0$ . For $k$ -NN, $W_{ni} = 1/ k$ on the $k$ nearest points and $0$ otherwise. Condition (ii) is $max_{i} W_{ni} = 1/ k \to 0$ , forcing $k \to \infty$ . Condition (iii) requires the $k$ -th nearest-neighbour distance to vanish, which holds iff the neighbourhood does not engulf a positive fraction of the data, i.e. $k / n \to 0$ . Condition (i) holds for $k$ -NN weights by a geometric covering argument. Together these give consistency exactly when $k \to \infty$ and $k / n \to 0$ . Rubric: full credit for stating the negligibility and shrinking-neighbourhood conditions and deriving both $k$ -NN requirements from them.

Advanced results Master

The Cover-Hart bound is the $k = 1$ corner of a fuller theory in which allowing $k$ to grow recovers the Bayes rule exactly, kernel and local-polynomial smoothers attain optimal nonparametric rates, and the whole family is undone by dimension.

Theorem 1 (universal consistency of $k$ -NN; Stone). Let $\hat{f}_{n} (x) = \sum_{i} W_{ni} (x) Y_{i}$ with $k$ -nearest-neighbour weights $W_{ni} (x) = \frac{1}{k _{n}} 1 {x_{i} \in N_{k_{n}} (x)}$ . If $k_{n} \to \infty$ and $k_{n} / n \to 0$ , then $\hat{f}_{n}$ is universally consistent: $E [(\hat{f}_{n} (X) - η (X))^{2}] \to 0$ for every distribution of $(X, Y)$ with $E [Y^{2}] < \infty$ , and the induced $k$ -NN classifier is risk-consistent, $R_{n} \to R^{*}$ ^{[Stone 1977]}. The proof verifies Stone's three weight conditions: $max_{i} W_{ni} = 1/ k_{n} \to 0$ kills the variance, the $k_{n}$ -th nearest-neighbour radius vanishing under $k_{n} / n \to 0$ kills the bias, and the covering condition holds for nearest-neighbour weights by a geometric argument bounding how many query balls a fixed training point can be the neighbour of. The dual conditions for kernel weights are $h_{n} \to 0$ and $n h_{n}^{p} \to \infty$ , giving consistency of Nadaraya-Watson and local polynomial estimators.

Theorem 2 (bias-variance and the optimal bandwidth of local linear regression). For a one-dimensional interior point with twice-differentiable $f$ , design density $p$ , noise variance $σ^{2}$ , symmetric kernel with $μ_{2} (K) = \int u^{2} K$ and $R (K) = \int K^{2}$ , the local linear estimator has, to leading order,

Bias (x) = \frac{1}{2} h^{2} μ_{2} (K) f^{''} (x), Var (x) = \frac{σ ^{2} R ( K )}{nh p ( x )} .

Minimising the asymptotic mean squared error $Bias^{2} + Var$ over $h$ gives the optimal bandwidth $h_{opt} \propto n^{- 1/5}$ and the optimal rate $MSE ≍ n^{- 4/5}$ ^{[Fan 1996]}. The bias is free of $p$ and $p^{'}$ , so local linear is design-adaptive and corrects boundary bias automatically; Nadaraya-Watson carries the additional $f^{'} (x) p^{'} (x) / p (x)$ term and degrades at the edges (Exercise 6). Local polynomials of odd degree $r = 2 m + 1$ extend the principle, removing the next boundary term.

Theorem 3 (the equivalent kernel). Every linear smoother $\hat{f} (x) = \sum_{i} ℓ_{i} (x) y_{i}$ — $k$ -NN, Nadaraya-Watson, local polynomial, and the smoothing spline — has weights $ℓ_{i} (x)$ that act as an effective, query-dependent kernel. For local linear regression the equivalent kernel converges, as $n \to \infty$ , to a fixed shape $K^{*} (u)$ independent of the design density $p$ , the Epanechnikov-type effective kernel, which is why two smoothers with very different formulations (local linear and the cubic smoothing spline) produce nearly identical fits ^{[Hastie 2009]}. The effective degrees of freedom $\sum_{i} ℓ_{i} (x_{i}) = tr (S)$ index the smoother's complexity continuously, the same complexity measure that governs the optimism of 45.06.02.

Theorem 4 (the curse of dimensionality for local methods). Let the design be uniform on $[0, 1]^{p}$ . To capture a fraction $r$ of the data a neighbourhood needs edge length $r^{1/ p}$ , so for fixed $r$ the neighbourhood spans almost the whole range as $p$ grows, and conversely a genuinely local neighbourhood of fixed radius captures an exponentially small fraction of the data. The expected distance to the nearest of $n$ points grows toward the diameter, and almost all sample points lie near the boundary ^{[Hastie 2009]}. Consequently the local-averaging bias cannot be controlled without either an exponential sample size $n ≍ ϵ^{- p}$ or strong structural assumptions; the nonparametric MSE rate degrades from $n^{- 4/5}$ ( $p = 1$ ) to $n^{- 4/ (4 + p)}$ , vanishingly slow for large $p$ . Structured kernels, additive and projection-pursuit models, and learned (adaptive) metrics that stretch the relevant directions are the standard escapes, trading universality for a usable rate.

Synthesis. The foundational reason this family coheres is that $k$ -NN, kernel smoothing, local polynomials, and even tree leaves are one object — a local weighted average $\sum_{i} W_{ni} (x) Y_{i}$ of the responses — read with different weights, and the central insight of Stone's theorem is that any such estimator is universally consistent precisely when its weights satisfy two conditions: no single neighbour dominates (driving variance to zero) and the weight concentrates on shrinking neighbourhoods (driving bias to zero). The Cover-Hart ceiling is exactly the price of violating the first condition by keeping a single neighbour: $1$ -NN never shrinks its variance, so its risk floors at $2 E [η (1 - η)]$ rather than $R^{*}$ , and putting these together with the bias-variance decomposition of 45.06.02 identifies $k$ and the bandwidth $h$ as the same smoothing dial that trades the two error sources. Local linear regression is dual to Nadaraya-Watson through the equivalent kernel: both are weighted averages, but the linear fit's design-adaptivity removes the $f^{'} p^{'} / p$ boundary term, which is the bridge that makes a memory-based method behave well at the edges where it is needed most. The curse of dimensionality is the structural fact that defeats the whole programme in high $p$ , and it generalises the same neighbourhood geometry that powers consistency in low dimension into an obstruction in high dimension — the adaptive neighbourhoods of 45.08.04 and the decorrelated forests downstream are exactly the response, building data-driven metrics that keep neighbourhoods local where a fixed Euclidean ball cannot.

Full proof set Master

Proposition 1 (asymptotic 1-NN error equals $2 η (1 - η)$ and the factor-of-two bound). Under the Cover-Hart hypotheses the limiting single-nearest-neighbour risk is $R = E [2 η (X) (1 - η (X))]$ , and $R^{*} \leq R \leq 2 R^{*} (1 - R^{*}) \leq 2 R^{*}$ .

Proof. Fix $x$ ; the nearest neighbour $x_{n}^{'}$ satisfies $d (x, x_{n}^{'}) \to 0$ a.s. (in the support, the minimum of $n$ i.i.d. distances vanishes), so $η (x_{n}^{'}) \to η (x)$ by continuity. Conditioned on the locations, the query label $Y \sim Bernoulli (η (x))$ and the neighbour label $Y_{n}^{'} \sim Bernoulli (η (x_{n}^{'}))$ are independent, and disagreement has probability $η (x) (1 - η (x_{n}^{'})) + (1 - η (x)) η (x_{n}^{'})$ , which tends to $2 η (x) (1 - η (x))$ . Bounded convergence over $X$ gives $R = E [2 η (X) (1 - η (X))]$ . With $m = min (η, 1 - η) \in [0, \frac{1}{2}]$ , the pointwise error is $2 m (1 - m)$ ; since $m \leq \frac{1}{2}$ we have $2 m (1 - m) \geq 2 m \cdot \frac{1}{2} = m$ , so $R \geq E [m] = R^{*}$ . The map $t \mapsto 2 t (1 - t)$ is concave, so Jensen gives $R = E [2 m (X) (1 - m (X))] \leq 2 E [m (X)] (1 - E [m (X)]) = 2 R^{*} (1 - R^{*})$ , and $1 - R^{*} \leq 1$ closes the chain. $□$

Proposition 2 (variance and bias of the $k$ -NN regressor). With neighbour locations fixed and independent homoscedastic noise of variance $σ^{2}$ , $Var (\hat{f}_{k} (x)) = σ^{2} / k$ and $Bias (\hat{f}_{k} (x)) = \frac{1}{k} \sum_{ℓ = 1}^{k} f (x_{(ℓ)}) - f (x)$ .

Proof. $\hat{f}_{k} (x) = \frac{1}{k} \sum_{ℓ = 1}^{k} Y_{(ℓ)}$ with $Y_{(ℓ)} = f (x_{(ℓ)}) + ε_{(ℓ)}$ . Linearity of expectation gives $E [\hat{f}_{k} (x)] = \frac{1}{k} \sum_{ℓ} f (x_{(ℓ)})$ , so the bias is the displayed difference. Independence of the $ε_{(ℓ)}$ gives $Var (\hat{f}_{k} (x)) = \frac{1}{k ^{2}} \sum_{ℓ = 1}^{k} σ^{2} = σ^{2} / k$ . The variance falls as $1/ k$ and the bias grows as the neighbours reach farther from $x$ , so $k$ is the smoothing parameter trading the two; the effective number of parameters is $n / k$ , matching the linear-smoother degrees of freedom $tr (S)$ . $□$

Proposition 3 (Nadaraya-Watson is the local constant fit; equivalent-kernel weights sum to one). The Nadaraya-Watson estimator minimises $\sum_{i} K_{h} (x, x_{i}) (y_{i} - c)^{2}$ over $c$ , and every local polynomial smoother $\hat{f} (x) = \sum_{i} ℓ_{i} (x) y_{i}$ reproduces constants, $\sum_{i} ℓ_{i} (x) = 1$ .

Proof. For the first claim, $\frac{d}{d c} \sum_{i} K_{h} (x, x_{i}) (y_{i} - c)^{2} = - 2 \sum_{i} K_{h} (x, x_{i}) (y_{i} - c) = 0$ at $c = \sum_{i} K_{h} (x, x_{i}) y_{i} / \sum_{i} K_{h} (x, x_{i}) = \hat{f}_{N W} (x)$ , with positive second derivative $2 \sum_{i} K_{h} (x, x_{i})$ . For the second, the local polynomial fit solves a weighted least-squares problem whose design matrix $B$ has first column the all-ones vector (the intercept monomial $(x_{i} - x)^{0}$ ). The fitted intercept is $\hat{β}_{0} = e_{1}^{⊤} (B^{⊤} WB)^{- 1} B^{⊤} Wy$ , so $ℓ_{i} (x)$ is the corresponding row functional. Applying the smoother to the constant response $y_{i} \equiv 1$ : weighted least squares fits this exactly with $\hat{β}_{0} = 1$ and higher coefficients zero (a constant is in the polynomial span), so $\sum_{i} ℓ_{i} (x) \cdot 1 = 1$ . Reproduction of constants is what makes the leading bias depend on curvature rather than level, and for degree $r \geq 1$ reproduction of linear functions removes the design-density term. $□$

Proposition 4 (curse-of-dimensionality neighbourhood geometry). For $n$ points uniform on $[0, 1]^{p}$ , the side length of an axis-aligned subcube containing in expectation a fraction $r$ of the data is $e_{p} (r) = r^{1/ p}$ , and $e_{p} (r) \to 1$ as $p \to \infty$ for every fixed $r \in (0, 1)$ .

Proof. A subcube of side $s$ has volume $s^{p}$ ; under the uniform law the expected fraction of points it contains equals its volume, $s^{p}$ . Setting $s^{p} = r$ gives $s = r^{1/ p} = e_{p} (r)$ . For fixed $r \in (0, 1)$ , $lo g e_{p} (r) = \frac{1}{p} lo g r \to 0$ , so $e_{p} (r) \to 1$ . Hence to capture any fixed positive fraction of the data the neighbourhood must, in high dimension, span essentially the full range of every coordinate, which is the precise sense in which "local" neighbourhoods cease to be local and local-averaging bias becomes uncontrollable without structural assumptions. $□$

Connections Master

$k$ -NN and local regression are the explicit local-averaging instances of the bias-variance trade-off anatomised in 45.06.02: the variance $σ^{2} / k$ of Proposition 2 is the $k$ -NN special case of the variance term there, the neighbour count $k$ (and the bandwidth $h$ ) plays the role of the complexity dial, and the effective degrees of freedom $tr (S)$ of the equivalent-kernel smoother is the same complexity measure that governs the optimism and the U-shaped test curve of that unit.
The kernel-weighted average and the kernel-density estimator of this unit are the regression and density faces of the nonparametric smoothing developed in 26.08.01: the Nadaraya-Watson estimator is a ratio of a kernel-weighted response sum to the kernel-density estimate of the design, so the bandwidth bias-variance trade-off and the $n^{- 2 s / (2 s + 1)}$ minimax rates established there for density estimation transfer directly to the local-regression rates $n^{- 4/ (4 + p)}$ proved here, the central insight being that both are local averages with vanishing-bandwidth bias and $1/ (n h^{p})$ variance.
Memory-based local methods and the tree-based partition methods of 45.08.04 are two ways of choosing the neighbourhood weights $W_{ni} (x)$ in the common estimator $\sum_{i} W_{ni} (x) y_{i}$ : $k$ -NN fixes a Euclidean ball of $k$ points, a tree leaf is a data-adaptive axis-aligned rectangle, and the Lin-Jeon reading there casts a tree (and a forest) as an adaptive nearest-neighbour rule — so this unit supplies the fixed-neighbourhood baseline against which the adaptive, metric-learning, dimension-resistant partition methods are the response.
The curse of dimensionality formalised in Theorem 4 is the obstruction whose subset-selection and sparsity remedies are developed in 45.06.05: where local methods fight high dimension by structured kernels, additive models, and learned metrics, that unit attacks the same exponential-neighbourhood problem by selecting a low-dimensional set of relevant predictors, and the two are dual strategies — restrict the metric versus restrict the feature set — for restoring a usable convergence rate.

Historical & philosophical context Master

The nearest-neighbour idea is old as a heuristic, but its theoretical standing dates to Evelyn Fix and Joseph Hodges' 1951 unpublished USAF technical report on discriminatory analysis, which introduced nonparametric nearest-neighbour density and classification rules. The decisive result is Thomas Cover and Peter Hart's 1967 paper Nearest neighbor pattern classification ^{[Cover 1967]}, which proved that the single-nearest-neighbour rule, asymptotically, errs at most twice as often as the optimal Bayes classifier — a guarantee with no assumption on the class densities, establishing that "half the available information in an infinite sample is contained in the nearest neighbour." The kernel-weighted regression estimator was introduced independently by Élisbar Nadaraya (1964) and Geoffrey Watson (1964).

The consistency theory was unified by Charles Stone's 1977 Consistent nonparametric regression ^{[Stone 1977]}, which gave distribution-free conditions on the weight sequence guaranteeing universal consistency of any local-averaging estimator and pinned the $k$ -NN requirement to $k \to \infty$ , $k / n \to 0$ . The local-polynomial refinement — local linear regression's automatic boundary correction and design adaptivity — was developed and given its definitive minimax-efficiency treatment by Jianqing Fan and Irène Gijbels in Local Polynomial Modelling and Its Applications (1996) ^{[Fan 1996]}. The recasting of all these estimators within the bias-variance and effective-degrees-of-freedom framework, and the explicit diagnosis of the curse of dimensionality as the structural limit of local methods, is due to Hastie, Tibshirani and Friedman's Elements of Statistical Learning ^{[Hastie 2009]}.

Bibliography Master

@article{coverhart1967,
  author  = {Cover, Thomas M. and Hart, Peter E.},
  title   = {Nearest Neighbor Pattern Classification},
  journal = {IEEE Transactions on Information Theory},
  volume  = {13},
  number  = {1},
  pages   = {21--27},
  year    = {1967}
}

@article{stone1977,
  author  = {Stone, Charles J.},
  title   = {Consistent Nonparametric Regression},
  journal = {The Annals of Statistics},
  volume  = {5},
  number  = {4},
  pages   = {595--645},
  year    = {1977}
}

@book{fangijbels1996,
  author    = {Fan, Jianqing and Gijbels, Ir{\`e}ne},
  title     = {Local Polynomial Modelling and Its Applications},
  publisher = {Chapman \& Hall},
  address   = {London},
  year      = {1996}
}

@book{hastie2009esl,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2},
  publisher = {Springer},
  year      = {2009}
}

@article{nadaraya1964,
  author  = {Nadaraya, {\'E}lizbar A.},
  title   = {On Estimating Regression},
  journal = {Theory of Probability and Its Applications},
  volume  = {9},
  number  = {1},
  pages   = {141--142},
  year    = {1964}
}

@article{watson1964,
  author  = {Watson, Geoffrey S.},
  title   = {Smooth Regression Analysis},
  journal = {Sankhy\=a: The Indian Journal of Statistics, Series A},
  volume  = {26},
  number  = {4},
  pages   = {359--372},
  year    = {1964}
}

@techreport{fixhodges1951,
  author      = {Fix, Evelyn and Hodges, Joseph L.},
  title       = {Discriminatory Analysis, Nonparametric Discrimination: Consistency Properties},
  institution = {USAF School of Aviation Medicine, Randolph Field, Texas},
  number      = {Report No. 4},
  year        = {1951}
}

Prerequisites

26.08.01
45.06.02
45.08.04

Tier anchors

beginner: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) §2.3.2 (nearest-neighbour methods); a 'ask the people most like you' analogy for predicting from the closest training cases
intermediate: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e §2.3.2, §6.1-6.3 (k-nearest neighbours, kernel smoothing, local regression); Cover & Hart 1967 IEEE Trans. Inf. Theory 13 (the nearest-neighbour risk bound); Fan & Gijbels 1996 Local Polynomial Modelling and Its Applications (Chapman & Hall) Ch. 2-3 (local linear bias/variance, boundary behaviour, equivalent kernel)
master: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e §6.1-6.6 and §2.5 (local methods, the curse of dimensionality); Cover & Hart 1967 (asymptotic 1-NN risk $\leq 2 R^{*}$ ); Stone 1977 Ann. Statist. 5 (universal consistency of nearest-neighbour and local-average rules); Fan & Gijbels 1996 Ch. 3 (minimax efficiency and design adaptation of local polynomial fits)

References

Hastie, T., Tibshirani, R. & Friedman, J. — The Elements of Statistical Learning · Springer, 2nd edition (2009). Section 2.3.2 introduces nearest-neighbour methods as the prototypical low-bias, high-variance memory-based learner: the k-nearest-neighbour fit $\hat{f} (x) = \frac{1}{k} \sum_{x_{i} \in N_{k} (x)} y_{i}$ averages the responses of the $k$ training points closest to the query under a chosen metric, with $k$ controlling smoothness; small $k$ gives a ragged, low-bias fit and large $k$ a smooth, high-bias one, and the effective number of parameters is roughly $n / k$ . Section 2.5 develops the curse of dimensionality: in $p$ dimensions a neighbourhood capturing a fraction $r$ of the data has edge length $r^{1/ p}$ , so local neighbourhoods are no longer local, sampling density falls as $n^{1/ p}$ , and almost all points sit near the boundary of the sample. Chapter 6 (kernel smoothing methods) develops the Nadaraya-Watson kernel-weighted average $\hat{f} (x) = \sum_{i} K_{h} (x, x_{i}) y_{i} / \sum_{i} K_{h} (x, x_{i})$ , its boundary and interior bias, local linear and local polynomial regression that remove the leading boundary bias automatically, the equivalent-kernel representation $\hat{f} (x) = \sum_{i} ℓ_{i} (x) y_{i}$ of a linear smoother, local likelihood, and kernel density classification; it also treats structured kernels and local feature scaling as a partial remedy for high dimension.
Cover, T. M. & Hart, P. E. — Nearest neighbor pattern classification · IEEE Transactions on Information Theory 13 (1967), 21-27. Proves that the large-sample (infinite training set) risk $R$ of the single-nearest-neighbour classification rule satisfies $R^{*} \leq R \leq R^{*} (2 - \frac{M}{M - 1} R^{*}) \leq 2 R^{*}$ for an $M$ -class problem, where $R^{*}$ is the Bayes risk. The argument fixes a query $x$ , notes that under mild continuity the nearest neighbour's feature value converges to $x$ as $n \to \infty$ so its label is an independent draw from the same conditional class distribution $η (x)$ , and computes the probability that query and neighbour labels disagree as a function of $η (x)$ ; bounding the resulting integrand by its Bayes value yields the factor-of-two ceiling. The paper frames nearest-neighbour classification as a method that, with unlimited data, recovers at least half of the classification information in the sample at essentially no modelling assumption.
Stone, C. J. — Consistent nonparametric regression · Annals of Statistics 5 (1977), 595-645. Establishes general conditions under which a weighted-average (local) estimator $\hat{f}_{n} (x) = \sum_{i} W_{ni} (x) Y_{i}$ is universally consistent — consistent for every distribution of $(X, Y)$ with $E ∣ Y ∣ < \infty$ — in terms of conditions on the weight sequence $W_{ni}$ (asymptotic negligibility of any single weight, concentration of weight on shrinking neighbourhoods, a Besicovitch-type covering condition). Specialised to $k$ -nearest-neighbour weights this gives universal $L^{2}$ and risk consistency of the $k$ -NN regression and classification rules precisely when $k = k_{n} \to \infty$ and $k_{n} / n \to 0$ , and specialised to kernel weights it gives the analogous consistency of Nadaraya-Watson and local polynomial estimators under bandwidth conditions $h_{n} \to 0$ , $n h_{n}^{p} \to \infty$ .

Estimated time

beginner: 20m
intermediate: 55m
master: 90m