WorksComputer Science
On k-nearest-neighbor regression in metric spaces
Abstract
We study mean squared consistency of k-nearest-neighbor regression for metric space valued features. For a fixed feature distribution mu with atomless distance distributions, we describe how neighbor selection redistributes probability through the density of a uniformly chosen neighbor of an independent query. This gives separate conditions for the approximation error and the conditional response variance, and weakens Stone's domination condition when stronger response moments are available. In particular, when k_n tends to infinity and k_n/n tends to zero, a uniform L2(mu) bound on the selection densities suffices under a finite fourth response moment. We give a corresponding condition in terms of neighborhoods of fixed population mass and recover the Euclidean density bound. Finite global Nagata dimension gives Stone's domination. While sigma-finite Nagata dimensionality is known to ensure universal consistency of k-NN classification in complete separable spaces, we show that this is not the case for mean squared consistency with unbounded responses: we construct a space in this class on which one fixed noiseless response with all finite moments has diverging mean squared error.
Introduction
Let be a separable metric space with its Borel -algebra. For the estimation of the nonparametric regression function, let the random feature (predictor) take values in the space , and let its response (label) be real valued. We denote by the feature distribution, that is, for all measurable sets . For the mean squared error analysis, assume . Define measurable versions of the regression function and the conditional variance by
Let consist of independent copies of . A test pair, again denoted by , is independent of . For a query , order the observations by increasing distance and denote them by
Thus is the -th nearest neighbor of . Ties are resolved by indices. For integers , , satisfying
the estimate and its mean integrated squared error are
The relevance of this criterion comes from the mean squared error identity
The first term is the irreducible prediction error. Thus means that the mean squared prediction error approaches the expected conditional variance, . We call this weak consistency in . Background on nearest-neighbor regression is given in Györfi et al. [12, Chapter 6] and Biau and Devroye [1, Chapter 11].
Separability of the metric space alone does not ensure consistency of ordinary -NN. There are feature distributions on the infinite-dimensional Hilbert space , with deterministic binary responses, for which the rule is inconsistent for every sequence satisfying (3); see Cérou and Guyader [2, Section 3.2] and Collins et al. [5, Section 3]. Thus locality of the selected neighbors is not by itself sufficient for estimating an arbitrary measurable conditional mean.
The failure of ordinary -NN in some separable metric spaces is a property of this estimator, rather than an impossibility of learning in those spaces. For classification, the OptiNet rule of Hanneke et al. [15] is universally strongly Bayes consistent in every separable metric space. The simpler Proto-NN construction of Györfi and Weiss [14] uses an independent unlabeled sample (prototypes) to form a Voronoi partition of and averages the labeled responses within its cells. If the number of prototypes tends to infinity and , their Theorem 3 gives strong integrated consistency of regression for bounded responses. For unbounded responses, set the estimate to zero in cells with fewer than observations and require . Their Theorem 5 and the subsequent discussion then give strong consistency whenever .
The partition structure explains an important difference. Conditional on a partition independent of the labeled sample, the expected cell-average of a nonnegative integrable function equals its conditional mean in that cell, multiplied by the probability that the cell is occupied. Averaging over the independent query therefore gives
where are the cell-average weights and are zero on empty cells. The modified rule for unbounded regression only reduces these weights, leaving the inequality intact. This domination holds without any dimension bound. Ordinary -NN uses a different neighborhood for every query, so a separate argument is needed to control the distribution of the observations it selects.
The classical connection with differentiation of measures also has a statistical interpretation. Write for the closed ball of radius around . For a query and a radius with , the population mean response in the ball is
This is the population quantity estimated by a local average over that ball. Recovering as is therefore the approximation requirement behind local averaging. In Euclidean spaces the differentiation theorem supplies this requirement almost everywhere for every Borel probability measure and every integrable regression function [1 Theorem 20.19]. In general metric spaces it can fail, even for an indicator function. The relevance to nearest-neighbor classification was developed by Cérou and Guyader [2]. Their corrected sufficient condition uses almost-everywhere differentiation even for weak consistency; see Pestov [19, Section 2.3, Theorem 2.2].
To see the role of this condition, fix a query where as . Given , there is a radius such that for every . This controls the average also at a random positive nearest-neighbor radius once that radius is sufficiently small. Convergence in -measure for a common radius says only that most query points are well approximated at that radius; it does not provide the same control when the radius is selected separately for each query. Here “almost everywhere” concerns query points under . It is distinct from the almost-sure convergence along training sequences required by strong consistency.
The obstruction can occur even when has a Gaussian distribution. Preiss et al. [21] constructed a nondegenerate Gaussian measure on an infinite-dimensional separable Hilbert space and a Borel set of positive measure for which
For the noiseless response , the population averages over small balls therefore approach zero even at points where the conditional mean equals one. A Gaussian distribution for alone does not ensure that local averages recover arbitrary measurable regression functions.
Pointwise estimation and integrated prediction error address different statistical questions. Pointwise consistency concerns the estimate at a fixed query, whereas integrated consistency averages its error over the distribution of an independent test point . Devroye [7] studies conditions for pointwise convergence of nearest-neighbor regression estimates. In metric measure spaces, Cesari and Colomboni [3] connects Lebesgue points with noiseless nearest-neighbor pointwise estimation and examines the role of distance ties. Pointwise convergence alone does not ensure convergence of the mean integrated squared error: large errors on sets of small feature probability can still make a substantial contribution to the integral. If almost surely, then for -almost every , almost surely. Pointwise almost-sure convergence for -almost every then allows passage through both integration and expectation by the bounded convergence theorem. For unbounded responses there is no such bound, and additional integrability control is needed.
Strong consistency in means
Weak consistency requires the expectation of this integrated error, taken over the training sample, to tend to zero. Strong consistency requires the integrated error itself to approach zero for almost every infinite training sample. For Euclidean predictors and bounded responses, Devroye et al. [9, Theorem 1 and Remark 7] established strong integrated consistency under and , using a specified randomized rule for distance ties. Their Theorem 2 treats integrated absolute error for integrable responses under the additional condition . For metric spaces, Kumari and Pestov [16 Theorem 4.1] proved strong consistency of the -NN classifier on complete separable sigma-finite-dimensional spaces in the absence of distance ties, under (3). Here sigma-finite dimensionality means a countable cover by sets of finite relative Nagata dimension on positive scales; the geometric definition is given in § 3. Their proofs also use concentration inequalities to control deviations of integrated error terms from their expectations over the training sample. The results of the present paper concern mean integrated squared error.
Another statistical question is whether the random integrated error is accurately described by its expectation. Writing
the corresponding relative-stability property is in probability, when eventually. Relative stability of integrated errors, including nearest-neighbor regression errors, is studied by Györfi et al. [13].
Mean squared consistency of -nearest-neighbor regression is studied in § 2, the underlying geometric conditions in § 3, and rates of convergence in § 4. Proofs of the main consistency and geometric results are deferred to § 5.
Stone's condition and the role of the feature distribution
A local averaging estimate has the form
where the weights are measurable functions of the query and the feature sample. For probability weights, and , the following form of Stone’s sufficient criterion isolates the property that will concern us; see Stone [22 Theorem 1].
Theorem 1 (Stone’s sufficient criterion). Let be a Borel probability measure on a separable metric space, and let be feature-dependent probability weights. Suppose that:
there is such that for every and every nonnegative integrable Borel function ,
for every , in probability;
in probability.
Then for every joint law with feature marginal and .
The usual approximation and truncation proof applies on a separable metric space: bounded Lipschitz functions approximate square-integrable regression functions in , and the three displayed conditions control approximation, locality, and response noise. Euclidean geometry is used to verify the domination condition (S) for ordinary nearest neighbors. We use only the sufficient part of the criterion here.
For -NN,
The maximum weight is . Locality on a separable metric space gives, under ,
see Cérou and Guyader [2 Proposition 2.1] and Györfi et al. [12 Lemma 6.1]. For the one-neighbor locality result, see Cover and Hart [6 Section V]. Thus the last two conditions hold under (3). In finite-dimensional normed spaces, a cone-covering argument supplies the remaining domination bound by controlling how often an observation can be selected as a neighbor; see Collins et al. [5 Lemma 4.3 and Remarks 4.4–4.5].
For functional predictors, a dimension bound of this kind need not be available. A condition on the feature distribution can still make the ordinary rule consistent. Our questions are therefore: how can Stone’s domination be weakened when a fourth response moment, or separate moments of the conditional mean and variance, are available? Which geometric assumptions provide these distributional bounds, and how do they relate to convergence rates?
Neighbor selection and mean squared consistency
Neighbor-selection densities
To answer these questions, we introduce neighbor-selection densities on . Each is the density, relative to , of an observation chosen uniformly among the nearest neighbors of an independent query . These densities describe how neighbor selection redistributes the feature distribution , and their norm and integrability bounds control regression consistency under the corresponding moment assumptions. Cone-covering and Nagata dimension bounds depend only on the metric; the densities also depend on and the neighbor sequence .
Write
for the closed ball. For the density analysis from this section onward, we assume that distance ties have probability zero. More precisely, we assume that
is continuous on and satisfies , for every . Thus the distribution of has no atoms, and distance ties have probability zero.
Define the averaging functional, for a nonnegative Borel function , by
This is the expectation of at a point chosen uniformly among the nearest neighbors of the independent query . With this notation, Stone’s domination condition (S) becomes
for every and every nonnegative , with one finite constant independent of and . Selection depends on distances to the query, so the randomly chosen neighbor may have a different distribution from . Stone’s condition compares this distribution with . To study this condition and its relaxations, we describe the selected-neighbor distribution by a density relative to .
For a fixed query and candidate point , consider the sample . The point is selected precisely when at most of the remaining observations are closer to . Its selection probability is therefore
where the probability is over . Averaging over the query, define the neighbor-selection density by
For a fixed query , an observation at is selected with probability . A uniform choice from the selected observations then chooses that observation with probability . The sample indices are exchangeable under (10), so their equal contributions to the selected-neighbor distribution sum to give the factor . The integral over in (13) averages over the independent query. These definitions specify measurable functions and .
Lemma 1 (Averaging identity). For every and every nonnegative Borel function ,
In particular, is the density, relative to , of a point chosen uniformly among the nearest neighbors of an independent query. The averaging identity also holds for every signed .
The proof is given in § 5.1.
The quadratic decomposition and density conditions
All norms below are relative to . For a measurable function and ,
and is the essential supremum. Write for the conjugate exponent, with , , and . Define
By the averaging identity, Stone’s condition (S) is equivalent to . Indeed, a bound gives the domination inequality. Conversely, applying domination to shows that almost everywhere. Each is bounded by ; the issue is control as varies.
The conditional mean of the estimate given the feature sample is
Write the noise and approximation errors as
For fixed all these quantities are finite: Jensen’s inequality and the fact that the selected responses form a subset of the sample give
Conditional Jensen’s inequality gives the same bound for , and .
Conditionally on the feature sample and query, has mean zero, whereas is fixed. Thus the cross term vanishes when the squared error is expanded, giving
The selected responses are conditionally independent. Their variances therefore add:
Averaging over the feature sample and query yields the exact identity (compare Lemma 1 above)
Thus the density describes which conditional variances are sampled, while describes the averaging of independent response noise. For the approximation error, the same functional averages squared errors in approximating at the selected neighbors. This leads to the following criterion.
Theorem 2 (Mean squared consistency). Assume (3) and (10). Fix and suppose . Then is necessary and sufficient for for every joint distribution with feature marginal satisfying
If , there is a single fixed law satisfying (19), with , for which along a subsequence. This last assertion does not require .
The proof is given in § 5.2.
The approximation hypothesis and the noise condition have distinct roles. Approximating by a bounded Lipschitz function produces , which is bounded by . For the noise, splitting the conditional variance at a level in (18) gives
The first term vanishes as and the tail norm vanishes as . A larger permits a weaker variance moment, while requiring a stronger density norm. The proof of necessity uses the same exact variance identity.
Corollary 1 (Conditional mean and response moments). Assume (3) and (9). If , , and , then for every joint distribution with feature marginal satisfying
In particular, suffices whenever .
Proof. Since , conditional Jensen’s inequality gives . For the last assertion, take and use and .
At , this recovers the finite-second-moment condition under Stone’s domination. Finite exponents allow more concentration of the selected-neighbor distribution at the cost of stronger conditions on the response moments. The following consequences emphasize the fourth moment and the usual regression model with additive noise.
Concrete moment conditions
Theorem 2 gives the following particularly simple consequence under a fourth response moment.
Corollary 2 (A finite fourth response moment). Assume (3) and (9). If , then
for every joint distribution of with feature marginal and .
Proof. Conditional Jensen’s inequality gives
Thus and . Moreover, . The quadratic criterion applies with . □
The fourth moment is one convenient way to control both the regression function and the noise. The separate conditions in the quadratic criterion also cover responses with only a finite second moment.
Corollary 3 (A fourth moment of the conditional mean). Assume (3) and (9), and suppose . If and , then under either of the following additional conditions:
The conditional variance is essentially bounded.
. In particular, this holds if .
Proof. The approximation term tends to zero because and . If , then its noise term satisfies
For the second assertion, put . Since , for every ,
First let , and then let . The bound proves the last assertion. □
For example, the first case applies to additive noise , where is independent of , has mean zero and finite variance. No fourth moment of is required. The second case allows unbounded conditional variances while retaining only a finite second response moment; it controls their contribution through the scaled density bound.
Neighborhoods of fixed population mass
A condition on can also be formulated through neighborhoods of fixed population mass. For , define
Thus is the mass, divided by , of query centres whose ball reaches before accumulating more than feature probability. Under (10), is uniform on when . Tonelli’s theorem therefore gives .
There is an exact relation with the sample densities. Let be an auxiliary random variable with the beta distribution with parameters and . Then
where the expectation is only over . Indeed, if , the binomial selection probability in (12) equals . Substitution into (13) and Tonelli’s theorem give
To identify the weighted distribution explicitly, let be the beta function. The density of is
see Biau and Devroye [1 Chapter 1]. Since ,
The right side is the probability density of Beta. Consequently,
which proves (22). Thus averages the fixed-mass densities over these auxiliary mass thresholds.
Corollary 4 (A fixed-mass condition). Assume (3) and (10), and suppose that
Then for every joint distribution with feature marginal , , and satisfying
In particular, (23) implies for every joint distribution with feature marginal and .
Proof. There is such that both integrals in the hypotheses are bounded uniformly for . For , the identities and give
The square-integral hypothesis and its bound away from zero give
Likewise, the variance hypothesis and give
The beta-mixture identity (22), Jensen’s inequality, and Tonelli’s theorem imply
Thus , so the approximation argument in Theorem 2 gives for . The exact noise identity gives
Together these prove the first assertion. If , conditional Jensen’s inequality gives and . Cauchy–Schwarz then yields
so the variance condition also holds. □
Lemma 2 (Comparison at deterministic mass levels). Assume (9), and put . For every and every ,
The lower bound holds for every .
Proof. Put . If , the number of other observations closer to than has expectation at most . Markov’s inequality gives . Integrating over these query centres yields
For the upper bound, put and use (22). By definition, is nondecreasing in , so for . Since ,
The variable has the distribution of the -st order statistic of independent uniforms. Thus, for ,
On , , so the remaining part of the mixture is at most
Adding the two parts proves the upper bound. □
In Euclidean space, the fixed-mass densities are bounded by the same cone geometry that underlies Stone’s lemma [12 Lemma 6.2]. Stone’s argument bounds how often a sample point can be selected as a neighbor; the cones used in the proof below bound the -mass of query centres whose balls reach a fixed point with mass at most . The resulting uniform bound on transfers to through (22), recovering Stone’s domination condition (S).
Lemma 3 (Euclidean fixed-mass bound). Let with Euclidean distance and assume (9). There is a constant , depending only on , such that
This is the reverse-ball estimate of Devroye and Györfi [8 Lemma 1, p. 260]. We include its geometric argument.
Proof. Cover by punctured cones with vertex , chosen so that the angle between any two rays in one cone is strictly less than . Such a finite cover exists by compactness of the unit sphere. If and lie in one cone and , then
For one cone , let
For every , its radial initial segment satisfies
and therefore has -mass at most . If is empty, its mass is zero. Otherwise, choose a sequence of radii of points of increasing cofinally to the supremum of these radii, including the maximum if it is attained. The associated initial segments increase to , so . Summing over the cones and using gives
Divide by .
For functional predictors, an important question is to verify these density conditions from explicit properties of the predictor law. For example, when continuous curves are viewed as elements of , which distributions satisfy (22)? The criterion gives a sufficient distributional condition for every fourth-moment response, without requiring the conditional mean to be smooth.
Noiseless observations and a fixed number of neighbors
A fixed number of neighbors need not average away response noise. For example, if is an independent Rademacher sign, then and the mean squared error is exactly when neighbors are averaged. For noiseless observations, however, the noise term vanishes, and consistency only requires the neighbor locations to approach the query while controlling approximation error.
Corollary 5 (Noiseless observations). Assume (9) and (22). Let satisfy ; it is not necessary that . Then for every noiseless response with ,
In particular, this conclusion holds for 1-NN and for every other fixed number of neighbors, once exceeds that number.
Proof. Condition (22) and the bound give . For every , the beta-mixture identity (21) and Jensen’s inequality yield
Neither step requires . Thus .
We also verify locality under the weaker assumption on . For -almost every , every positive-radius ball around has positive -probability, by separability of the feature space. Fix such an and , and put . The number of sample points in this ball has binomial distribution with parameters , . Since , the law of large numbers gives
Dominated convergence over the independent query gives the same convergence with replaced by .
Fix and choose a bounded Lipschitz function with . Such an approximation is provided by Lemma 5 below. Put . Since the response is noiseless, , so adding and subtracting the neighbor average of gives
The first two terms satisfy
For every , uniform continuity supplies such that whenever . Consequently, the remaining term is at most
Locality, followed by , makes this term tend to zero. Hence . Letting proves the assertion. □
The proof only uses the fixed-mass assumption to obtain . A uniform bound instead permits the same proof with , since and approximation in suffices. This recovers the corresponding noiseless Euclidean result, including fixed , under the standing no-distance-tie assumption; see Györfi et al. [12 Problem 6.3].
Nagata dimension and nearest-neighbor selection
The density criteria separate the distributional requirement from its geometric verification. Global geometric control yields Stone’s domination. Sigma-finite dimensionality does not ensure consistency for unbounded responses, as the example below shows.
Global dimension, scale, and relative dimension
Recall that the multiplicity of a family of subsets of is
Also, a family of balls is disconnected if no ball of the family contains the centre of any other ball.
Definition 1 (Nagata dimension). Let , , and . The subspace has Nagata dimension at most in on scale if every finite family of closed balls in with centres in and radii less than admits a subfamily of multiplicity at most in which covers all the centres of the original balls. Write for the smallest such , or if none exists.
An equivalent condition is that every finite disconnected family of such balls has multiplicity at most . Closed balls can also be replaced with open balls, or a mixture of the two, cf. Collins et al. [5 Propositions 7.2–7.3]. For relative dimension the multiplicity is measured throughout the ambient space , not only on . An intrinsic dimension bound on therefore does not by itself establish the required relative bound.
We distinguish the original, global notion
from finite dimension on some positive scale. The latter restricts the covering property to small balls; the global notion imposes one common bound for balls of every radius. The relative, scale-dependent formulation is due to Preiss [20]. For a normed vector space, homotheties preserve centre containment and multiplicity while scaling radii, so a bound on one positive scale gives the same global bound.
Following Preiss, a metric space is sigma-finite dimensional in the sense of Nagata if it is a countable union of subspaces , each having finite Nagata dimension in on some scale . The dimensions and scales may all be different. The subspaces may be taken closed, hence Borel [5 Proposition 7.4, Definition 7.6 and Remark 7.7]. For basic properties and further examples see Pestov [19, Section 3].
Global domination
In a complete separable space with global Nagata dimension at most , the covering argument gives for every , and (21) gives . The fixed-mass covering argument of Kumari and Pestov [16, Lemma 4.6] is used here at the infinite scale; its proof in this case is given in § 5.3. For a finite scale , the covering bound applies only to centres with . Small ball mass alone does not enforce this radius restriction uniformly over the centres. This distinction is essential to the counterexample below.
Corollary 6 (Global Nagata dimension). Assume (3) and (9). If , then
Thus Stone’s condition (S) holds with , and -NN is weakly consistent in for every joint distribution of with feature marginal and .
Unbounded responses on the porcupine
Proposition 1. There is a complete separable metric probability space that is sigma-finite dimensional in the sense of Nagata and satisfies (9), with the following property. There is one fixed nonnegative noiseless response with for every finite such that
for every finite and every sequence satisfying . The joint distribution of depends neither on nor on the neighbor sequence.
The space is the porcupine, or hedgehog, formed by countably many copies of , called spines, whose zero endpoints are identified as a common root . Write for the point at distance from on spine . Two points have distance on the same spine and on different spines. Each spine has Nagata dimension one relative to , although itself has infinite Nagata dimension at every positive scale. For the explicit unbounded response in Proposition 1, -NN regression is inconsistent in every finite moment order. The regression function is and .
In this same construction, becomes large near the root on regions of vanishing feature probability. The regression function specified above is large enough on these regions to make the expected integrated error diverge.
In a finite-dimensional normed space, Stone’s geometric bound gives for every feature marginal satisfying (10). Taking in Corollary 1 therefore gives weak consistency whenever . The same conclusion holds under the global Nagata hypothesis of Corollary 6, which imposes one common dimension bound on balls of every radius. Thus the failure for unbounded responses above cannot occur under such a global density bound.
By contrast, imposing the dimension bound only on balls of radius less than one fixed does not by itself ensure mean squared consistency, even for a response with all finite moments. The separated-spine construction in Remark 1 has Nagata dimension at most one on scale , yet admits a fixed noiseless response with all finite moments for which for every finite .
Neither sigma-finite Nagata dimension nor finite Nagata dimension on one positive scale guarantees the uniform bounds assumed in the sufficient conditions of § 2. In each of the two examples, for every sequence satisfying (3),
Indeed, the proofs show that , whereas . Hölder’s inequality gives
so cannot remain bounded as increases. The proofs of the geometric statements are given in § 5.3.
Smoothness and convergence rates
The preceding criteria impose conditions on neighbor selection and allow arbitrary conditional means in the stated moment class. A complementary route imposes smoothness directly on . The next bound requires no density-norm condition.
A generalized Lipschitz condition
Quantitative bounds require regularity of the regression function. One useful condition measures smoothness through the probability mass of a neighborhood rather than its radius. This results in a joint smoothness and tail condition. Following Györfi and Weiss [14], suppose that a nondecreasing function with and as satisfies
Mass-based smoothness conditions have been used to obtain classification rates without requiring bounded feature support. The modified Lipschitz condition in Döring et al. [10] compares regression values at two points using the probability of the ball joining them. Chaudhuri and Dasgupta [4] uses a related condition comparing a regression value with its average over a ball. The generalized Lipschitz condition (26) follows the metric-space formulation in Györfi and Weiss [14].
Proposition 2 (A mean squared error bound). Assume (10), (26), and almost everywhere. If is concave, then, for every ,
Proof. The exact quadratic decomposition gives , with . Fix a query . The probability integral transform and (10) imply that , , are independent uniform random variables. Consequently,
has the -th uniform order-statistic distribution, whose mean is . By (26), monotonicity of , and Jensen’s inequality for the neighbor average,
Taking expectations and applying concavity gives
This proves the first inequality; the second uses monotonicity. □
For example, if with , then
Choosing of order gives the rate . In particular, if is the -dimensional Euclidean space and with , then the order is under the stated mass-based smoothness condition. Euclidean geometry alone does not imply that smoothness condition.
Proofs of the consistency and geometric results
The averaging and selection-count identities
Proof of Lemma 1. Fix a nonnegative Borel function . We first work with a fixed query . For every realization of the sample, summing over the selected neighbors is the same as summing over all sample indices and retaining only those selected:
We next compute the expectation of each summand on the right. Fix an index and condition on . By independence, the remaining observations still have the joint law . For this fixed and , the no-ties assumption implies that none of the remaining observations has distance from , almost surely. Thus the candidate is selected precisely when at most of the remaining observations are closer to .
This conditional selection probability is . Although (11) uses the indices , the remaining observations have the same joint law after removing any index . Consequently, for -almost every ,
Here the location is held fixed, and the expectation averages only over the remaining observations. Averaging this conditional expectation over , whose distribution is , gives
The right-hand side does not depend on . Taking expectations in the first identity and summing these identical integrals therefore gives
This explains both the use of and the factor .
Finally, the independent query has distribution . Integrating over its location and applying Tonelli’s theorem, which is applicable because all integrands are nonnegative, we obtain
where the last equality uses (13). These equalities remain valid when the integrals are infinite. Since , the definition of gives . Taking in the averaging identity gives
because exactly observations are selected.
For a signed , the bound on gives . Applying the identity to the positive and negative parts of therefore proves the signed version. In particular, for every fixed , is a continuous linear functional on for every .
Lemma 4 (Selection-count identity). Fix , and let be independent with distribution . For each , let be the indices of the nearest neighbors of query among the other observations. Define the selection count of observation by
Under (9), for every ,
In particular, .
Proof of Lemma 4. Fix and a possible query index . Conditional on and , the remaining feature observations are independent with distribution . By (9), none has distance from , almost surely. Consequently,
Independence of and gives
There are possible query indices . Summing their contributions and using (12),
Integrating over and using gives .
Approximation and the quadratic criterion
We first record the approximation fact used below.
Lemma 5. Bounded Lipschitz functions are dense in for every .
Proof. For Lipschitz density in , see Hanneke et al. [15 supplementary material, Lemma A.1]. We give a proof for all . Let be their closure in . For a nonempty closed set , the bounded Lipschitz functions converge pointwise to . Dominated convergence shows that . The class of Borel sets whose indicators belong to is a Dynkin class: it contains , is closed under complements, and is closed under countable disjoint unions by convergence of finite partial sums. The closed sets form a generating -system, so this class contains every Borel set. Density of simple functions proves the assertion.
Proof of Theorem 2. First suppose and fix a joint law satisfying (20). The moment assumptions imply
so the quadratic identities above apply.
For the approximation term, fix and choose a bounded Lipschitz function with . This is possible because and therefore . Put . Adding and subtracting the neighbor average of and its value at the query gives
The three terms are the approximation error at the selected neighbors, the local averaging error for , and the negative approximation error at the query. The inequality for a squared sum and Jensen’s inequality for the first average yield
The averaging identity (Lemma 1) and Hölder’s inequality give
Since , Hölder’s inequality also gives
For the middle term, let . For every , bounded uniform continuity of supplies such that whenever . Therefore
Locality (9) and dominated convergence make the probability tend to zero; see also the locality argument of Cover and Hart [6 Section V]. Letting and then in (30) proves .
For the noise, the exact identity (19) gives
The bounded part uses , and the tail uses Hölder’s inequality. Since , the tail norm tends to zero as . First letting at fixed , then letting , proves . Together with (18), this proves sufficiency.
For necessity, define positive continuous linear functionals on by
Their norms are . Each is finite, since . For a nonnegative , let be an independent Rademacher sign and set . This law has and , and hence belongs to (20). For this law,
Consistency for every such law implies that is bounded for every nonnegative . Decomposing a signed function into its positive and negative parts, the uniform boundedness principle gives . If these norms are unbounded, the same principle provides a fixed with . Set . Positivity gives . The law then has along an increasing subsequence. Each fixed- error is finite, and the law does not depend on . This completes the proof. □
Nagata dimension and domination: Proofs
This subsection proves the geometric results of § 3. The geometric count below yields Stone’s domination under finite global Nagata dimension. The subsequent constructions prove the counterexamples for unbounded responses. The general analytic consistency criteria in Subsection 5.2 do not require these geometric assumptions.
Proof of Corollary 6. Fix and write . Take independent points with distribution . For each , let be the indices of the nearest neighbors of among the other points. By (10), almost surely there are no distance ties at any of these queries. For a fixed target index , put
Thus in (28). For , consider the closed ball . Every such ball contains . The Nagata property supplies a subfamily covering all centres , , with multiplicity at most . Since every retained ball contains , there are at most retained balls. Each contains at most of the augmented sample points, including its centre and . As , it therefore contains at most of the centres being counted. Hence
Taking the conditional expectation given and using (29) gives
The bound is uniform in . The averaging identity yields Stone’s condition. The consistency conclusion follows from Corollary 1 with . □
For completeness, we retain the compactness proof of the fixed-mass bound in (21), in the global case used here.
Global bound for . Suppose that is complete and separable and . Fix and . By inner regularity of a Borel probability measure on a complete separable metric space, it suffices to prove for an arbitrary compact subset of
Let be a countable dense subset of a nonempty . For every , apply the Nagata property to , . The retained balls cover all and all contain , so there are at most of them. Repeating centres if necessary, denote their centres by . Compactness gives a subsequence along which for every .
We claim that , , cover . Their union is closed, so it suffices to show that it contains . For each fixed , some index covers along a further infinite subsequence. Passing to the limit in gives . This proves the claim. Since each , every limiting ball has mass at most . Thus and . □
Proof of Proposition 1. Choose so that
Let be the countable bouquet of intervals
with common root and tree metric
Put no mass at , and put Lebesgue measure of total mass on spine :
The space is separable. It is also complete: a Cauchy sequence whose distances from tend to zero converges to ; otherwise it eventually stays on one compact spine. Every sphere meets each spine in at most two points, so every sphere has zero -mass. In particular, the no-distance-ties assumption holds.
Each spine has Nagata dimension one relative to , on the infinite scale. To verify the ambient-relative assertion, take a finite disconnected family of balls with centres on one spine, and order the centres by increasing distance from . Only the ball at the first centre can reach : any later ball that reaches would contain the first centre. Thus the multiplicity outside the spine is at most one. On the spine it is at most two, by the usual interval argument: among three centres, a common point of their balls lies on one side of the middle centre, forcing one of the extreme balls to contain that centre. Consequently, is sigma-finite dimensional in the sense of Nagata. Its dimension in itself is infinite on every positive scale: for any , the balls form a disconnected family and all contain .
For , define
Fix with . For every with , consider centres with
This interval is contained in . Since , the corresponding ball satisfies
The mass of these centres on spine is . Therefore
Now put . Fix with . Since spheres have zero mass, the number of the other sample points closer to than has distribution . Markov’s inequality gives
Thus on this set. By (13),
Define one noiseless response by
The response is noiseless, and for every ,
Thus the same regression function belongs to every finite . For all sufficiently large , . For these , the averaging identity and (33)–(34) give
For the second inequality, integrate only over .
To see that this bound diverges for every , choose with . Then , and
Since , (35) shows that . For every , Jensen’s inequality on the joint distribution of the sample and the independent query yields
Each fixed- risk is finite, since (14) gives
The joint distribution of is fixed throughout, and the regression function depends neither on nor on the sequence .
Remark 1 (Finite dimension on a positive scale). The preceding failure also occurs on a space of finite Nagata dimension at one fixed scale. To see this, take the following closed subset of the countable tree, with its induced metric:
where the are distinct unit coordinate vectors. It is complete and separable. Distinct interval components have distance at least one, so balls of radius less than remain within one component. The interval covering property therefore gives .
Give the hub Lebesgue density one, hence total mass , and give branch uniform mass , with as in the preceding proof. Write for this probability measure. Every sphere meets each component in at most two points, so (10) holds. Put
The integral test for gives as .
For a target with and , every query , , has
The ball contains its entire branch and the hub segment , and it contains no other branch. Thus every branch with contributes its full mass to the fixed-mass reverse set, giving
The binomial argument in (36) applies unchanged with , so, for ,
Define for , put , and put on every far branch. The noiseless response has every finite moment, by the same exponential-tail integral as above. Integrating only over yields
Jensen’s inequality again gives for every finite , for this one fixed law and every sequence with . Each fixed- risk is finite.
References
References
- [1]Biau, G. and Devroye, L. (2015). Lectures on the Nearest Neighbor Method. Springer, Cham.
- [2]Cérou, F. and Guyader, A. (2006). Nearest neighbor classification in infinite dimension. ESAIM: Probability and Statistics 10 340–355.DOI
- [3]Cesari, T. R. and Colomboni, R. (2020). A nearest neighbor characterization of Lebesgue points in metric measure spaces. Mathematical Statistics and Learning 3(1) 71–112.
- [4]Chaudhuri, K. and Dasgupta, S. (2014). Rates of convergence for nearest neighbor classification. In Advances in Neural Information Processing Systems 27, pages 3437–3445.arxiv.org/abs/1407.0067
- [5]Collins, B., Kumari, S. and Pestov, V. G. (2020). Universal consistency of the k-NN rule in metric spaces and Nagata dimension. ESAIM: Probability and Statistics 24 914–934.DOI
- [6]Cover, T. M. and Hart, P. E. (1967). Nearest neighbor pattern classification. IEEE Trans. Inform. Theory 13(1) 21–27.DOI
- [7]Devroye, L. (1982). Necessary and sufficient conditions for the pointwise convergence of nearest neighbor regression function estimates. Zeitschrift für Wahrscheinlichkeits-theorie und verwandte Gebiete 61 467–481.DOI
- [8]Devroye, L. and Györfi, L. (1985). Nonparametric Density Estimation: The L₁ View. Wiley, New York.
- [10]Döring, M., Györfi, L. and Walk, H. (2018). Rate of convergence of k-nearest-neighbor classification rule. Journal of Machine Learning Research 18(227) 1–16.
- [12]Györfi, L., Kohler, M., Krzyżak, A. and Walk, H. (2002). A Distribution-Free Theory of Nonparametric Regression. Springer, New York.DOI
- [13]Györfi, L., Schäfer, D. and Walk, H. (2002). Relative stability of global errors of nonparametric function estimators. IEEE Trans. Inform. Theory 48(8) 2230–2242.DOI
- [14]Györfi, L. and Weiss, R. (2021). Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces. Journal of Machine Learning Research 22(151) 1–25.arxiv.org/abs/2010.00636
- [15]Hanneke, S., Kontorovich, A., Sabato, S. and Weiss, R. (2021). Universal Bayes consistency in metric spaces. Ann. Statist. 49(4) 2129–2150. See also the supplementary material, Lemma A.1.
- [16]Kumari, S. and Pestov, V. G. (2024). Universal consistency of the k-NN rule in metric spaces and Nagata dimension. II. ESAIM: Probability and Statistics 28 132–160.arxiv.org/abs/2305.17282
- [20]Preiss, D. (1983). Dimension of metrics and differentiation of measures. In General Topology and its Relations to Modern Analysis and Algebra V (Prague, 1981), pages 565–568. Sigma Series in Pure Mathematics, 3. Heldermann, Berlin.
- [21]Preiss, D., Riss, E. and Tišer, J. (2021). A set of positive Gaussian measure with uniformly zero density everywhere. Journal of the European Mathematical Society 23(7) 2439–2466.DOI
- [22]Stone, C. J. (1977). Consistent nonparametric regression. Ann. Statist. 5(4) 595–620.DOI