betaFeedback

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 (X,ρ)(\mathcal{X}, \rho) be a separable metric space with its Borel σ\sigma-algebra. For the estimation of the nonparametric regression function, let the random feature (predictor) XX take values in the space X\mathcal{X}, and let its response (label) YY be real valued. We denote by μ\mu the feature distribution, that is, μ(A)=P(X∈A)\mu(A) = \mathbb{P}(X \in A) for all measurable sets A⊆XA \subseteq\mathcal{X}. For the mean squared error analysis, assume EY2<∞\mathbb{E}Y^2 < \infty. Define measurable versions of the regression function and the conditional variance by

m(x)=E[Y∣X=x],(1)m(x) = \mathbb{E}[Y \mid X = x], \tag*{(1)}
σ2(x)=E[(Y−m(X))2∣X=x].(2)\sigma^2(x) = \mathbb{E}[(Y - m(X))^2 \mid X = x]. \tag*{(2)}

Let Dn={(X1,Y1),…,(Xn,Yn)}\mathcal{D}_n = \{(X_1,Y_1), \ldots, (X_n,Y_n)\} consist of independent copies of (X,Y)(X,Y). A test pair, again denoted by (X,Y)(X,Y), is independent of Dn\mathcal{D}_n. For a query xx, order the observations XiX_i by increasing distance ρ(x,Xi)\rho(x,X_i) and denote them by

(X(n,1)(x),Y(n,1)(x)),…,(X(n,n)(x),Y(n,n)(x)).(X_{(n,1)}(x), Y_{(n,1)}(x)), \ldots, (X_{(n,n)}(x), Y_{(n,n)}(x)).

Thus X(n,k)(x)X_{(n,k)}(x) is the kk-th nearest neighbor of xx. Ties are resolved by indices. For integers 1≤kn<n1 \leq k_n < n, n≥2n \geq2, satisfying

kn⟶∞,kn/n⟶0,(3)k_n \longrightarrow\infty,\qquad k_n/n \longrightarrow0, \tag*{(3)}

the estimate and its mean integrated squared error are

mn(x)=1kn∑i=1knY(n,i)(x),(4)m_n(x)=\frac{1}{k_n}\sum_{i=1}^{k_n}Y_{(n,i)}(x), \tag*{(4)}
Rn,2=E∫(mn(x)−m(x))2μ(dx).(5)R_{n,2}=\mathbb{E}\int\left(m_n(x)-m(x)\right)^2\mu(dx). \tag*{(5)}

The relevance of this criterion comes from the mean squared error identity

E[(Y−mn(X))2]=E[σ2(X)]+Rn,2.\mathbb{E}\left[(Y-m_n(X))^2\right]=\mathbb{E}\left[\sigma^2(X)\right]+R_{n,2}.

The first term is the irreducible prediction error. Thus Rn,2→0R_{n,2}\to0 means that the mean squared prediction error approaches the expected conditional variance, E[σ2(X)]\mathbb{E}[\sigma^2(X)]. We call this weak consistency in L2(μ)L_2(\mu). 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 X\mathcal{X} alone does not ensure consistency of ordinary kk-NN. There are feature distributions on the infinite-dimensional Hilbert space ℓ2\ell_2, 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 kk-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 X\mathcal{X} and averages the labeled responses within its cells. If the number MnM_n of prototypes tends to infinity and Mn/n→0M_n/n\to0, 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 log⁡n\log n observations and require Mnlog⁡n/n→0M_n\log n/n\to0. Their Theorem 5 and the subsequent discussion then give strong L2L_2 consistency whenever EY2<∞\mathbb{E}Y^2<\infty.

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 φ\varphi equals its conditional mean in that cell, multiplied by the probability that the cell is occupied. Averaging over the independent query therefore gives

E∑i=1nVn,i(X)φ(Xi)≤∫φ dμ,\mathbb{E}\sum_{i=1}^{n}V_{n,i}(X)\varphi(X_i)\leq\int\varphi\,d\mu,

where Vn,iV_{n,i} 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 kk-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 B(x,t)B(x,t) for the closed ball of radius tt around xx. For a query xx and a radius tt with μ(B(x,t))>0\mu(B(x,t))>0, the population mean response in the ball is

at(x):=E[Y∣X∈B(x,t)]=∫B(x,t)m(z) μ(dz)μ(B(x,t)).a_t(x):=\mathbb{E}[Y\mid X\in B(x,t)]=\frac{\int_{B(x,t)}m(z)\,\mu(dz)}{\mu(B(x,t))}.

This is the population quantity estimated by a local average over that ball. Recovering m(x)m(x) as t↓0t \downarrow0 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 xx where at(x)→m(x)a_t(x) \to m(x) as t↓0t \downarrow0. Given ϵ>0\epsilon> 0, there is a radius t0(x,ϵ)>0t_0(x,\epsilon) > 0 such that ∣at(x)−m(x)∣<ϵ\lvert a_t(x) - m(x) \rvert< \epsilon for every 0<t<t0(x,ϵ)0 < t < t_0(x,\epsilon). This controls the average also at a random positive nearest-neighbor radius once that radius is sufficiently small. Convergence in μ\mu-measure for a common radius tt 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 μ\mu. It is distinct from the almost-sure convergence along training sequences required by strong consistency.

The obstruction can occur even when XX has a Gaussian distribution. Preiss et al. [21] constructed a nondegenerate Gaussian measure μ\mu on an infinite-dimensional separable Hilbert space HH and a Borel set MM of positive measure for which

lim⁡t↓0sup⁡x∈Hμ(B(x,t)∩M)μ(B(x,t))=0.\lim_{t \downarrow0}\sup_{x \in H}\frac{\mu(B(x,t) \cap M)}{\mu(B(x,t))}=0.

For the noiseless response Y=1M(X)Y = \mathbf{1}_M(X), the population averages over small balls therefore approach zero even at points where the conditional mean equals one. A Gaussian distribution for XX 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 μ\mu of an independent test point XX. 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 ∣Y∣≤L\lvert Y\rvert\le L almost surely, then ∣mn(x)−m(x)∣2≤4L2\lvert m_n(x) - m(x)\rvert^2 \le4L^2 for μ\mu-almost every xx, almost surely. Pointwise almost-sure convergence for μ\mu-almost every xx 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 L2(μ)L_2(\mu) means

∫∣mn−m∣2 dμ⟶0almost surely.\int\lvert m_n - m\rvert^2\,d\mu\longrightarrow0 \qquad\text{almost surely}.

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 kn→∞k_n \to\infty and kn/n→0k_n/n \to0, using a specified randomized rule for distance ties. Their Theorem 2 treats integrated absolute error for integrable responses under the additional condition kn/log⁡n→∞k_n/\log n \to\infty. For metric spaces, Kumari and Pestov [16 Theorem 4.1] proved strong consistency of the kk-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

En=∫∣mn(x)−m(x)∣2 μ(dx),EEn=Rn,2,E_n = \int|m_n(x)-m(x)|^2\,\mu(dx), \qquad\mathbb{E}E_n = R_{n,2},

the corresponding relative-stability property is En/Rn,2→1E_n/R_{n,2} \to1 in probability, when Rn,2>0R_{n,2}>0 eventually. Relative stability of integrated errors, including nearest-neighbor regression errors, is studied by Györfi et al. [13].

Mean squared consistency of kk-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

m^n(x)=∑i=1nWn,i(x)Yi,(6)\widehat{m}_n(x) = \sum_{i=1}^{n} W_{n,i}(x)Y_i, \tag*{(6)}

where the weights are measurable functions of the query and the feature sample. For probability weights, Wn,i≥0W_{n,i} \ge0 and ∑iWn,i=1\sum_i W_{n,i}=1, 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 μ\mu be a Borel probability measure on a separable metric space, and let (Wn,i)(W_{n,i}) be feature-dependent probability weights. Suppose that:

  1. there is C<∞C < \infty such that for every nn and every nonnegative integrable Borel function φ\varphi,

E∑i=1nWn,i(X)φ(Xi)≤C∫φ dμ;(7)\mathbb{E}\sum_{i=1}^{n} W_{n,i}(X)\varphi(X_i) \le C\int\varphi\,d\mu; \tag*{(7)}
  1. for every a>0a>0, ∑iWn,i(X)1{ρ(Xi,X)>a}→0\sum_i W_{n,i}(X)1_{\{\rho(X_i,X)>a\}} \to0 in probability;

  2. max⁡iWn,i(X)→0\max_i W_{n,i}(X) \to0 in probability.

Then E∫∣m^n−m∣2 dμ→0\mathbb{E}\int|\widehat{m}_n-m|^2\,d\mu\to0 for every joint law with feature marginal μ\mu and EY2<∞\mathbb{E}Y^2<\infty.

The usual approximation and truncation proof applies on a separable metric space: bounded Lipschitz functions approximate square-integrable regression functions in L2(μ)L_2(\mu), 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 knk_n-NN,

Wn,i(x)=1kn1{Xi is among the kn selected neighbors of x}.(8)W_{n,i}(x) = \frac{1}{k_n}\mathbf{1}\{X_i\text{ is among the }k_n\text{ selected neighbors of }x\}. \tag*{(8)}

The maximum weight is 1/kn1/k_n. Locality on a separable metric space gives, under kn/n→0k_n/n \to0,

ρ(x,X(n,kn)(x))⟶0almost surely, for μ-almost every x;(9)\rho(x, X_{(n,k_n)}(x)) \longrightarrow0 \quad\text{almost surely, for }\mu\text{-almost every }x; \tag*{(9)}

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 fnf_n on X\mathcal{X}. Each is the density, relative to μ\mu, of an observation chosen uniformly among the knk_n nearest neighbors of an independent query XX. These densities describe how neighbor selection redistributes the feature distribution μ\mu, and their norm and integrability bounds control L2(μ)L_2(\mu) regression consistency under the corresponding moment assumptions. Cone-covering and Nagata dimension bounds depend only on the metric; the densities fnf_n also depend on μ\mu and the neighbor sequence (kn)(k_n).

Write

B(x,t)={z:ρ(x,z)≤t}B(x,t) = \{z : \rho(x,z) \le t\}

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

Hx(t)=μ(B(x,t)),t≥0,(10)H_x(t) = \mu(B(x,t)), \qquad t \ge0, \tag*{(10)}

is continuous on [0,∞)[0,\infty) and satisfies Hx(0)=0H_x(0)=0, for every x∈Xx \in\mathcal{X}. Thus the distribution of ρ(x,X)\rho(x,X) has no atoms, and distance ties have probability zero.

Define the averaging functional, for a nonnegative Borel function φ\varphi, by

An(φ)=1kn∑i=1knEφ(X(n,i)(X)).(11)A_n(\varphi) = \frac{1}{k_n}\sum_{i=1}^{k_n}\mathbb{E}\varphi(X_{(n,i)}(X)). \tag*{(11)}

This is the expectation of φ\varphi at a point chosen uniformly among the knk_n nearest neighbors of the independent query XX. With this notation, Stone’s domination condition (S) becomes

An(φ)≤C∫φ dμA_n(\varphi) \le C \int\varphi\,d\mu

for every n≥2n \ge2 and every nonnegative φ∈L1(μ)\varphi\in L_1(\mu), with one finite constant CC independent of nn and φ\varphi. Selection depends on distances to the query, so the randomly chosen neighbor may have a different distribution from μ\mu. Stone’s condition compares this distribution with μ\mu. To study this condition and its relaxations, we describe the selected-neighbor distribution by a density relative to μ\mu.

For a fixed query xx and candidate point zz, consider the sample z,X2,…,Xnz, X_2,\ldots,X_n. The point zz is selected precisely when at most kn−1k_n-1 of the remaining observations are closer to xx. Its selection probability is therefore

gn(x,z)=P{∑i=2n1{ρ(x,Xi)<ρ(x,z)}≤kn−1}(12)g_n(x,z)=\mathbb{P}\left\{\sum_{i=2}^{n}\mathbf{1}_{\{\rho(x,X_i)<\rho(x,z)\}}\le k_n-1\right\} \tag*{(12)}

where the probability is over X2,…,XnX_2,\ldots,X_n. Averaging over the query, define the neighbor-selection density by

fn(z)=nkn∫gn(x,z) μ(dx).(13)f_n(z)=\frac{n}{k_n}\int g_n(x,z)\,\mu(dx). \tag*{(13)}

For a fixed query xx, an observation at zz is selected with probability gn(x,z)g_n(x,z). A uniform choice from the knk_n selected observations then chooses that observation with probability gn(x,z)/kng_n(x,z)/k_n. The nn sample indices are exchangeable under (10), so their equal contributions to the selected-neighbor distribution sum to give the factor n/knn/k_n. The integral over xx in (13) averages over the independent query. These definitions specify measurable functions gng_n and fnf_n.

Lemma 1 (Averaging identity). For every n≥2n \ge2 and every nonnegative Borel function φ\varphi,

An(φ)=∫φfn dμ,0≤fn≤nkn,∫fn dμ=1.(14)A_n(\varphi)=\int\varphi f_n\,d\mu,\qquad0\le f_n\le\frac{n}{k_n},\qquad\int f_n\,d\mu=1. \tag*{(14)}

In particular, fnf_n is the density, relative to μ\mu, of a point chosen uniformly among the knk_n nearest neighbors of an independent query. The averaging identity also holds for every signed φ∈L1(μ)\varphi\in L_1(\mu).

The proof is given in § 5.1.

The quadratic decomposition and density conditions

All norms below are relative to μ\mu. For a measurable function ϕ\phi and 1≤p<∞1\le p<\infty,

∥ϕ∥p=(∫∣ϕ∣p dμ)1/p,\|\phi\|_p=\left(\int|\phi|^p\,d\mu\right)^{1/p},

and ∥ϕ∥∞\|\phi\|_\infty is the essential supremum. Write p′p' for the conjugate exponent, with 1/p+1/p′=11/p+1/p'=1, 1′=∞1'=\infty, and ∞′=1\infty'=1. Define

Fp=sup⁡n≥2∥fn∥p,Dq,2=sup⁡n≥2∥fn∥qkn,1≤p,q≤∞.(15)F_p=\sup_{n\ge2}\|f_n\|_p,\qquad D_{q,2}=\sup_{n\ge2}\frac{\|f_n\|_q}{k_n},\qquad1\le p,q\le\infty. \tag*{(15)}

By the averaging identity, Stone’s condition (S) is equivalent to F∞<∞F_{\infty}<\infty. Indeed, a bound fn≤Cf_n\le C gives the domination inequality. Conversely, applying domination to 1{fn>C}\mathbf{1}_{\{f_n>C\}} shows that fn≤Cf_n\le C almost everywhere. Each fnf_n is bounded by n/knn/k_n; the issue is control as nn varies.

The conditional mean of the estimate given the feature sample is

m‾n(x)=E[mn(x)∣X1,…,Xn]=1kn∑i=1knm(X(n,i)(x)).(16)\overline{m}_n(x)=\mathbb{E}[m_n(x)\mid X_1,\ldots,X_n]=\frac{1}{k_n}\sum_{i=1}^{k_n}m\left(X_{(n,i)}(x)\right). \tag*{(16)}

Write the noise and approximation errors as

In,2=E∫∣mn−m‾n∣2 dμ,Jn,2=E∫∣m‾n−m∣2 dμ.(17)I_{n,2}=\mathbb{E}\int|m_n-\overline{m}_n|^2\,d\mu,\qquad J_{n,2}=\mathbb{E}\int|\overline{m}_n-m|^2\,d\mu. \tag*{(17)}

For fixed nn all these quantities are finite: Jensen’s inequality and the fact that the selected responses form a subset of the sample give

E∣mn(X)∣2≤E[1kn∑i=1kn∣Y(n,i)(X)∣2]≤nknEY2.\mathbb{E}|m_n(X)|^2\le\mathbb{E}\left[\frac{1}{k_n}\sum_{i=1}^{k_n}|Y_{(n,i)}(X)|^2\right]\le\frac{n}{k_n}\mathbb{E}Y^2.

Conditional Jensen’s inequality gives the same bound for m‾n(X)\overline{m}_n(X), and E∣m(X)∣2≤EY2\mathbb{E}|m(X)|^2\le\mathbb{E}Y^2.

Conditionally on the feature sample and query, mn(X)−m‾n(X)m_n(X)-\overline{m}_n(X) has mean zero, whereas m‾n(X)−m(X)\overline{m}_n(X)-m(X) is fixed. Thus the cross term vanishes when the squared error is expanded, giving

Rn,2=In,2+Jn,2.(18)R_{n,2}=I_{n,2}+J_{n,2}. \tag*{(18)}

The selected responses are conditionally independent. Their variances therefore add:

E[(mn(X)−m‾n(X))2∣X,X1,…,Xn]=1kn2∑i=1knσ2(X(n,i)(X)).\mathbb{E}\left[(m_n(X)-\overline{m}_n(X))^2\mid X,X_1,\ldots,X_n\right]=\frac{1}{k_n^2}\sum_{i=1}^{k_n}\sigma^2\left(X_{(n,i)}(X)\right).

Averaging over the feature sample and query yields the exact identity (compare Lemma 1 above)

In,2=1knAn(σ2)=1kn∫σ2fn dμ.(19)I_{n,2}=\frac{1}{k_n}A_n(\sigma^2)=\frac{1}{k_n}\int\sigma^2 f_n\,d\mu. \tag*{(19)}

Thus the density describes which conditional variances are sampled, while 1/kn1/k_n describes the averaging of independent response noise. For the approximation error, the same functional averages squared errors in approximating mm at the selected neighbors. This leads to the following criterion.

Theorem 2 (Mean squared consistency). Assume (3) and (10). Fix 1<p≤q≤∞1<p\le q\le\infty and suppose Fp<∞F_p<\infty. Then Dq,2<∞D_{q,2}<\infty is necessary and sufficient for Rn,2→0R_{n,2}\to0 for every joint distribution with feature marginal μ\mu satisfying

m∈L2p′2(μ),σ2∈Lq′(μ).(20)m\in L_{2p'}^2(\mu),\qquad\sigma^2\in L_{q'}(\mu). \tag*{(20)}

If Dq,2=∞D_{q,2}=\infty, there is a single fixed law satisfying (19), with m=0m=0, for which Rn,2→∞R_{n,2}\to\infty along a subsequence. This last assertion does not require Fp<∞F_p<\infty.

The proof is given in § 5.2.

The approximation hypothesis and the noise condition have distinct roles. Approximating mm by a bounded Lipschitz function vv produces An((m−v)2)A_n((m-v)^2), which is bounded by Fp∥m−v∥2p′2F_p\lVert m-v\rVert_{2p^{\prime}}^2. For the noise, splitting the conditional variance at a level LL in (18) gives

In,2≤Lkn+Dq,2∥σ21{σ2>L}∥qq′.I_{n,2}\leq\frac{L}{k_n}+D_{q,2}\lVert\sigma^2\mathbf{1}_{\{\sigma^2>L\}}\rVert_q^{q^{\prime}}.

The first term vanishes as n→∞n\to\infty and the tail norm vanishes as L→∞L\to\infty. A larger qq 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 1<p≤q≤∞1<p\leq q\leq\infty, Fp<∞F_p<\infty, and Dq,2<∞D_{q,2}<\infty, then Rn,2→0R_{n,2}\to0 for every joint distribution with feature marginal μ\mu satisfying

m∈L2p′(μ),E∣Y∣2q′<∞.m\in L_{2p^{\prime}}(\mu),\qquad\mathbb{E}|Y|^{2q^{\prime}}<\infty.

In particular, Fp<∞F_p<\infty suffices whenever E∣Y∣2p′<∞\mathbb{E}|Y|^{2p^{\prime}}<\infty.

Proof. Since σ2(X)≤E[Y2∣X]\sigma^2(X)\leq\mathbb{E}[Y^2\mid X], conditional Jensen’s inequality gives ∫(σ2)q′ dμ≤E∣Y∣2q′\int(\sigma^2)^{q^{\prime}}\,d\mu\leq\mathbb{E}|Y|^{2q^{\prime}}. For the last assertion, take q=pq=p and use Dp,2≤FpD_{p,2}\leq F_p and ∫∣m∣2p′ dμ≤E∣Y∣2p′\int|m|^{2p^{\prime}}\,d\mu\leq\mathbb{E}|Y|^{2p^{\prime}}.

At p=q=∞p=q=\infty, 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 F2<∞F_2<\infty, then

Rn,2⟶0R_{n,2}\longrightarrow0

for every joint distribution of (X,Y)(X,Y) with feature marginal μ\mu and EY4<∞\mathbb{E}Y^4<\infty.

Proof. Conditional Jensen’s inequality gives

∫∣m∣4 dμ≤EY4,∫(σ2)2 dμ≤∫(E[Y2∣X=x])2 μ(dx)≤EY4.\int|m|^4\,d\mu\leq\mathbb{E}Y^4,\qquad\int(\sigma^2)^2\,d\mu\leq\int\bigl(\mathbb{E}[Y^2\mid X=x]\bigr)^2\,\mu(dx)\leq\mathbb{E}Y^4.

Thus m∈L4(μ)m\in L_4(\mu) and σ2∈L2(μ)\sigma^2\in L_2(\mu). Moreover, sup⁡n∥fn∥2/kn≤F2<∞\sup_n\lVert f_n\rVert_2/k_n\leq F_2<\infty. The quadratic criterion applies with p=q=2p=q=2. □

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 F2<∞F_2<\infty. If m∈L4(μ)m\in L_4(\mu) and EY2<∞\mathbb{E}Y^2<\infty, then Rn,2→0R_{n,2}\to0 under either of the following additional conditions:

  1. The conditional variance is essentially bounded.

  2. sup⁡n∥fn∥∞/kn<∞\sup_n \lVert f_n\rVert_\infty/k_n < \infty. In particular, this holds if sup⁡nn/kn2<∞\sup_n n/k_n^2 < \infty.

Proof. The approximation term tends to zero because F2<∞F_2 < \infty and m∈L4(μ)m \in L_4(\mu). If σ2≤K\sigma^2 \le K, then its noise term satisfies

In,2=1kn∫σ2fn dμ≤Kkn⟶0.I_{n,2} = \frac{1}{k_n}\int\sigma^2 f_n\,d\mu\le\frac{K}{k_n} \longrightarrow0.

For the second assertion, put D=sup⁡n∥fn∥∞/knD = \sup_n \lVert f_n\rVert_\infty/k_n. Since σ2∈L1(μ)\sigma^2 \in L_1(\mu), for every L>0L > 0,

In,2≤Lkn+D∫σ21{σ2>L} dμ.I_{n,2} \le\frac{L}{k_n} + D\int\sigma^2\mathbf{1}_{\{\sigma^2>L\}}\,d\mu.

First let n→∞n \to\infty, and then let L→∞L \to\infty. The bound fn≤n/knf_n \le n/k_n proves the last assertion. □

For example, the first case applies to additive noise Y=m(X)+εY = m(X) + \varepsilon, where ε\varepsilon is independent of XX, has mean zero and finite variance. No fourth moment of ε\varepsilon 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 μ\mu can also be formulated through neighborhoods of fixed population mass. For 0<u≤10 < u \le1, define

fu∗(z)=1uμ{x:Hx(ρ(x,z))≤u}.(21)f_u^*(z) = \frac{1}{u}\mu\{x : H_x(\rho(x,z)) \le u\}. \tag*{(21)}

Thus fu∗(z)f_u^*(z) is the mass, divided by uu, of query centres whose ball reaches zz before accumulating more than uu feature probability. Under (10), Hx(ρ(x,Z))H_x(\rho(x,Z)) is uniform on [0,1][0,1] when Z∼μZ \sim\mu. Tonelli’s theorem therefore gives ∫fu∗ dμ=1\int f_u^*\,d\mu= 1.

There is an exact relation with the sample densities. Let VnV_n be an auxiliary random variable with the beta distribution with parameters kn+1k_n + 1 and n−knn-k_n. Then

fn(z)=E[fVn∗(z)],(22)f_n(z) = \mathbb{E}[f_{V_n}^*(z)], \tag*{(22)}

where the expectation is only over VnV_n. Indeed, if Un∼Beta⁡(kn,n−kn)U_n \sim\operatorname{Beta}(k_n,n-k_n), the binomial selection probability in (12) equals P{Un≥Hx(ρ(x,z))}\mathbb{P}\{U_n \ge H_x(\rho(x,z))\}. Substitution into (13) and Tonelli’s theorem give

fn(z)=nknE[UnfUn∗(z)].f_n(z) = \frac{n}{k_n}\mathbb{E}[U_n f_{U_n}^*(z)].

To identify the weighted distribution explicitly, let B(a,b)=∫01ua−1(1−u)b−1 du\mathrm{B}(a,b) = \int_0^1 u^{a-1}(1-u)^{b-1}\,du be the beta function. The density of UnU_n is

bUn(u)=ukn−1(1−u)n−kn−1B(kn,n−kn),0<u<1;b_{U_n}(u) = \frac{u^{k_n-1}(1-u)^{n-k_n-1}}{\mathrm{B}(k_n,n-k_n)}, \qquad0 < u < 1;

see Biau and Devroye [1 Chapter 1]. Since B(kn+1,n−kn)=(kn/n)B(kn,n−kn)\mathrm{B}(k_n+1,n-k_n) = (k_n/n)\mathrm{B}(k_n,n-k_n),

nknubUn(u)=ukn(1−u)n−kn−1B(kn+1,n−kn)=bVn(u).\frac{n}{k_n}u b_{U_n}(u) = \frac{u^{k_n}(1-u)^{n-k_n-1}}{\mathrm{B}(k_n+1,n-k_n)} = b_{V_n}(u).

The right side is the probability density of Beta(kn+1,n−kn)(k_n+1,n-k_n). Consequently,

fn(z)=nknE[UnfUn∗(z)]=∫01fu∗(z)bVn(u) du=E[fVn∗(z)],f_n(z)=\frac{n}{k_n}\mathbb{E}[U_n f_{U_n}^*(z)]=\int_0^1 f_u^*(z)b_{V_n}(u)\,du=\mathbb{E}[f_{V_n}^*(z)],

which proves (22). Thus fnf_n averages the fixed-mass densities over these auxiliary mass thresholds.

Corollary 4 (A fixed-mass condition). Assume (3) and (10), and suppose that

lim sup⁡u↓0∫(fu∗(z))2 μ(dz)<∞.(23)\limsup_{u\downarrow0}\int(f_u^*(z))^2\,\mu(dz)<\infty. \tag*{(23)}

Then Rn,2→0R_{n,2}\to0 for every joint distribution with feature marginal μ\mu, EY2<∞\mathbb{E}Y^2<\infty, and m∈L4(μ)m\in L_4(\mu) satisfying

lim sup⁡u↓0∫σ2(z)fu∗(z) μ(dz)<∞.(24)\limsup_{u\downarrow0}\int\sigma^2(z)f_u^*(z)\,\mu(dz)<\infty. \tag*{(24)}

In particular, (23) implies Rn,2→0R_{n,2}\to0 for every joint distribution with feature marginal μ\mu and EY4<∞\mathbb{E}Y^4<\infty.

Proof. There is u0∈(0,1)u_0\in(0,1) such that both integrals in the hypotheses are bounded uniformly for 0<u<u00<u<u_0. For u0≤u≤1u_0\le u\le1, the identities 0≤fu∗≤1/u0\le f_u^*\le1/u and ∫fu∗ dμ=1\int f_u^*\,d\mu=1 give

∥fu∗∥22≤1u≤1u0,∫σ2fu∗ dμ≤1u0∫σ2 dμ<∞.\lVert f_u^*\rVert_2^2\le\frac{1}{u}\le\frac{1}{u_0},\qquad\int\sigma^2f_u^*\,d\mu\le\frac{1}{u_0}\int\sigma^2\,d\mu<\infty.

The square-integral hypothesis and its bound away from zero give

M2=sup⁡0<u≤1∥fu∗∥22<∞.M_2=\sup_{0<u\le1}\lVert f_u^*\rVert_2^2<\infty.

Likewise, the variance hypothesis and EY2<∞\mathbb{E}Y^2<\infty give

Mσ=sup⁡0<u≤1∫σ2fu∗ dμ<∞.M_\sigma=\sup_{0<u\le1}\int\sigma^2f_u^*\,d\mu<\infty.

The beta-mixture identity (22), Jensen’s inequality, and Tonelli’s theorem imply

∥fn∥22≤E∥fVn∗∥22≤M22,An(σ2)=E∫σ2fVn∗ dμ≤Mσ.\lVert f_n\rVert_2^2\le\mathbb{E}\lVert f_{V_n}^*\rVert_2^2\le M_2^2,\qquad A_n(\sigma^2)=\mathbb{E}\int\sigma^2f_{V_n}^*\,d\mu\le M_\sigma.

Thus F2≤M2F_2\le M_2, so the approximation argument in Theorem 2 gives Jn,2→0J_{n,2}\to0 for m∈L4(μ)m\in L_4(\mu). The exact noise identity gives

In,2=1knAn(σ2)≤Mσkn⟶0.I_{n,2}=\frac{1}{k_n}A_n(\sigma^2)\le\frac{M_\sigma}{k_n}\longrightarrow0.

Together these prove the first assertion. If EY4<∞\mathbb{E}Y^4<\infty, conditional Jensen’s inequality gives m∈L4(μ)m\in L_4(\mu) and σ2∈L2(μ)\sigma^2\in L_2(\mu). Cauchy–Schwarz then yields

∫σ2fu∗ dμ≤∥σ2∥2∥fu∗∥2≤∥σ2∥2M2,\int\sigma^2f_u^*\,d\mu\le\lVert\sigma^2\rVert_2\lVert f_u^*\rVert_2\le\lVert\sigma^2\rVert_2M_2,

so the variance condition also holds. □

Lemma 2 (Comparison at deterministic mass levels). Assume (9), and put c0=1−log⁡2>0c_0 = 1 - \log2 > 0. For every nsuchthat$2kn<nn such that \$2k_n < n and every z∈Xz \in\mathcal{X},

14fkn/(2n)∗(z)≤fn(z)≤2f2kn/n∗(z)+n2kne−c0kn.(25)\frac{1}{4}f^*_{k_n/(2n)}(z) \le f_n(z) \le2f^*_{2k_n/n}(z) + \frac{n}{2k_n}e^{-c_0k_n}. \tag*{(25)}

The lower bound holds for every n≥2n \ge2.

Proof. Put u=kn/(2n)u = k_n/(2n). If Hx(ρ(x,z))≤uH_x(\rho(x,z)) \le u, the number of other observations closer to xx than zz has expectation at most (n−1)u(n-1)u. Markov’s inequality gives gn(x,z)≥1−(n−1)u/kn≥1/2g_n(x,z) \ge1 - (n-1)u/k_n \ge1/2. Integrating over these query centres yields

fn(z)≥n2knμ{x:Hx(ρ(x,z))≤u}=14fu∗(z).f_n(z) \ge\frac{n}{2k_n}\mu\{x : H_x(\rho(x,z)) \le u\} = \frac{1}{4}f^*_u(z).

For the upper bound, put v=2kn/n<1v = 2k_n/n < 1 and use (22). By definition, ufu∗(z)uf^*_u(z) is nondecreasing in uu, so fu∗(z)≤(v/u)fv∗(z)f^*_u(z) \le(v/u)f^*_v(z) for u≤vu \le v. Since E[Vn−1]=n/kn\mathbb{E}[V_n^{-1}] = n/k_n,

E[fVn∗(z)1{Vn≤v}]≤vfv∗(z)E[Vn−1]=2fv∗(z).\mathbb{E}[f^*_{V_n}(z)1_{\{V_n\le v\}}] \le vf^*_v(z)\mathbb{E}[V_n^{-1}] = 2f^*_v(z).

The variable VnV_n has the distribution of the (kn+1)(k_n+1)-st order statistic of nn independent uniforms. Thus, for B∼Bin⁡(n,v)B \sim\operatorname{Bin}(n,v),

P(Vn>v)=P(B≤kn)≤2knE[2−B]=2kn(1−v/2)n≤exp⁡(knlog⁡2−nv/2)=e−c0kn.\begin{aligned} \mathbb{P}(V_n > v) = \mathbb{P}(B \le k_n) \le2^{k_n}\mathbb{E}[2^{-B}] \\ &= 2^{k_n}(1-v/2)^n \le\exp(k_n\log2-nv/2) = e^{-c_0k_n}. \end{aligned}

On {Vn>v}\{V_n > v\}, fVn∗(z)≤1/vf^*_{V_n}(z) \le1/v, so the remaining part of the mixture is at most

E[fVn∗(z)1{Vn>v}]≤1ve−c0kn=n2kne−c0kn.\mathbb{E}[f^*_{V_n}(z)1_{\{V_n>v\}}] \le\frac{1}{v}e^{-c_0k_n} = \frac{n}{2k_n}e^{-c_0k_n}.

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 μ\mu-mass of query centres whose balls reach a fixed point with mass at most uu. The resulting uniform bound on fu∗f^*_u transfers to fnf_n through (22), recovering Stone’s domination condition (S).

Lemma 3 (Euclidean fixed-mass bound). Let X=RdX = \mathbb{R}^d with Euclidean distance and assume (9). There is a constant γd<∞\gamma_d < \infty, depending only on dd, such that

fu∗(z)≤γd,z∈Rd,0<u≤1.f^*_u(z) \le\gamma_d,\qquad z \in\mathbb{R}^d,\qquad0 < u \le1.

This is the reverse-ball estimate of Devroye and Györfi [8 Lemma 1, p. 260]. We include its geometric argument.

Proof. Cover Rd∖{z}\mathbb{R}^d \setminus\{z\} by γd\gamma_d punctured cones with vertex zz, chosen so that the angle between any two rays in one cone is strictly less than π/3\pi/3. Such a finite cover exists by compactness of the unit sphere. If xx and yy lie in one cone and 0<∥y−z∥≤∥x−z∥0 < \lVert y-z\rVert\le\lVert x-z\rVert, then

∥x−y∥<∥x−z∥.\lVert x-y\rVert< \lVert x-z\rVert.

For one cone CC, let

EC={x∈C:μ(B(x,∥x−z∥))≤u}.E_C = \{x \in C : \mu(B(x,\lVert x-z\rVert)) \le u\}.

For every x∈ECx \in E_C, its radial initial segment satisfies

EC∩B(z,∥x−z∥)⊆B(x,∥x−z∥),E_C \cap B(z,\lVert x-z\rVert) \subseteq B(x,\lVert x-z\rVert),

and therefore has μ\mu-mass at most uu. If ECE_C is empty, its mass is zero. Otherwise, choose a sequence of radii of points of ECE_C increasing cofinally to the supremum of these radii, including the maximum if it is attained. The associated initial segments increase to ECE_C, so μ(EC)≤u\mu(E_C) \le u. Summing over the cones and using μ{z}=0\mu\{z\} = 0 gives

μ{x:Hx(∥x−z∥)≤u}≤γdu.\mu\{x : H_x(\lVert x-z\rVert) \le u\} \le\gamma d u.

Divide by uu.

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 L2([0,1])L_2([0,1]), 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 YY is an independent Rademacher sign, then m=0m = 0 and the mean squared error is exactly 1/k1/k when kk 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 1≤kn<n1 \le k_n < n satisfy kn/n→0k_n/n \to0; it is not necessary that kn→∞k_n \to\infty. Then for every noiseless response Y=m(X)Y = m(X) with m∈L4(μ)m \in L_4(\mu),

Rn,2⟶0.R_{n,2} \longrightarrow0.

In particular, this conclusion holds for 1-NN and for every other fixed number of neighbors, once nn exceeds that number.

Proof. Condition (22) and the bound ∥fu∗∥22≤1/u\lVert f_u^*\rVert_2^2 \le1/u give M=sup⁡0<u≤1∥fu∗∥2<∞M = \sup_{0<u\le1}\lVert f_u^*\rVert_2 < \infty. For every 1≤kn<n1 \le k_n < n, the beta-mixture identity (21) and Jensen’s inequality yield

∥fn∥22≤E∥fVn∗∥22≤M2.\lVert f_n\rVert_2^2 \le\mathbb{E}\lVert f_{V_n}^*\rVert_2^2 \le M^2.

Neither step requires kn→∞k_n \to\infty. Thus F2≤MF_2 \le M.

We also verify locality under the weaker assumption on knk_n. For μ\mu-almost every xx, every positive-radius ball around xx has positive μ\mu-probability, by separability of the feature space. Fix such an xx and b>0b > 0, and put px=μ(B(x,b/2))>0p_x = \mu(B(x,b/2)) > 0. The number Nn(x)N_n(x) of sample points in this ball has binomial distribution with parameters nn, pxp_x. Since kn/n→0k_n/n \to0, the law of large numbers gives

P{ρ(x,X(n,kn)(x))≥b}≤P{Nn(x)<kn}⟶0.\mathbb{P}\{\rho(x,X_{(n,k_n)}(x)) \ge b\} \le\mathbb{P}\{N_n(x) < k_n\} \longrightarrow0.

Dominated convergence over the independent query gives the same convergence with xx replaced by XX.

Fix ε>0\varepsilon> 0 and choose a bounded Lipschitz function vv with ∥m−v∥4<ε\lVert m-v\rVert_{4}<\varepsilon. Such an approximation is provided by Lemma 5 below. Put ϕ=m−v\phi=m-v. Since the response is noiseless, mn=m‾nm_n=\overline{m}_n, so adding and subtracting the neighbor average of vv gives

Rn,2≤3[An(ϕ2)+∥ϕ∥22+E∫∣1kn∑i=1knv(X(n,i)(x))−v(x)∣2μ(dx)].R_{n,2}\leq3\left[A_n(\phi^2)+\lVert\phi\rVert_2^2+\mathbb{E}\int\left\lvert\frac{1}{k_n}\sum_{i=1}^{k_n}v\left(X_{(n,i)}(x)\right)-v(x)\right\rvert^2\mu(dx)\right].

The first two terms satisfy

An(ϕ2)≤F2∥ϕ∥42≤Mε2,∥ϕ∥22≤∥ϕ∥42<ε2.A_n(\phi^2)\leq F_2\lVert\phi\rVert_4^2\leq M\varepsilon^2,\qquad\lVert\phi\rVert_2^2\leq\lVert\phi\rVert_4^2<\varepsilon^2.

For every η>0\eta>0, uniform continuity supplies b>0b>0 such that ∣v(z)−v(x)∣≤η\lvert v(z)-v(x)\rvert\leq\eta whenever ρ(x,z)<b\rho(x,z)<b. Consequently, the remaining term is at most

η2+4∥v∥∞2P{ρ(X,X(n,kn)(X))≥b}.\eta^2+4\lVert v\rVert_\infty^2\mathbb{P}\{\rho(X,X_{(n,k_n)}(X))\geq b\}.

Locality, followed by η↓0\eta\downarrow0, makes this term tend to zero. Hence lim sup⁡nRn,2≤3(M+1)ε2\limsup_n R_{n,2}\leq3(M+1)\varepsilon^2. Letting ε↓0\varepsilon\downarrow0 proves the assertion. □

The proof only uses the fixed-mass assumption to obtain F2<∞F_2<\infty. A uniform bound F∞<∞F_\infty<\infty instead permits the same proof with m∈L2(μ)m\in L_2(\mu), since An(ϕ2)≤F∞∥ϕ∥22A_n(\phi^2)\leq F_\infty\lVert\phi\rVert_2^2 and approximation in L2(μ)L_2(\mu) suffices. This recovers the corresponding noiseless Euclidean result, including fixed kk, 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 γ\gamma of subsets of X\mathcal{X} is

sup⁡z∈X∑V∈γ1V(z).\sup_{z\in\mathcal{X}}\sum_{V\in\gamma}\mathbf{1}_V(z).

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 A⊆X\mathcal{A}\subseteq\mathcal{X}, s∈(0,∞]s\in(0,\infty], and δ∈N0\delta\in\mathbb{N}_0. The subspace A\mathcal{A} has Nagata dimension at most δ\delta in X\mathcal{X} on scale ss if every finite family of closed balls in X\mathcal{X} with centres in A\mathcal{A} and radii less than ss admits a subfamily of multiplicity at most δ+1\delta+1 in X\mathcal{X} which covers all the centres of the original balls. Write dim⁡Nags(A,X)\dim_{\mathrm{Nag}}^s(\mathcal{A},\mathcal{X}) for the smallest such δ\delta, or ∞\infty if none exists.

An equivalent condition is that every finite disconnected family of such balls has multiplicity at most δ+1\delta+ 1. 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 X\mathcal{X}, not only on A\mathcal{A}. An intrinsic dimension bound on A\mathcal{A} therefore does not by itself establish the required relative bound.

We distinguish the original, global notion

dim⁡Nag(X):=dim⁡Nag∞(X,X)\dim_{\mathrm{Nag}}(\mathcal{X}) := \dim_{\mathrm{Nag}}^{\infty}(\mathcal{X},\mathcal{X})

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 Aj\mathcal{A}_j, each having finite Nagata dimension in X\mathcal{X} on some scale sj>0s_j > 0. 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 δ\delta, the covering argument gives fu∗≤δ+1f_u^* \le\delta+ 1 for every uu, and (21) gives fn≤δ+1f_n \le\delta+ 1. 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 ss, the covering bound applies only to centres with ρ(x,z)<s\rho(x,z) < s. 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 dim⁡Nag(X)≤δ<∞\dim_{\mathrm{Nag}}(\mathcal{X}) \le\delta< \infty, then

F∞≤δ+1.F_{\infty} \le\delta+ 1.

Thus Stone’s condition (S) holds with C=δ+1C = \delta+ 1, and knk_n-NN is weakly consistent in L2(μ)L_2(\mu) for every joint distribution of (X,Y)(X,Y) with feature marginal μ\mu and EY2<∞\mathbb{E}Y^2 < \infty.

Unbounded responses on the porcupine

Proposition 1. There is a complete separable metric probability space (T,ρ,μ)(\mathcal{T},\rho,\mu) that is sigma-finite dimensional in the sense of Nagata and satisfies (9), with the following property. There is one fixed nonnegative noiseless response Y=m(X)Y = m(X) with E∣Y∣r<∞\mathbb{E}|Y|^r < \infty for every finite r≥1r \ge1 such that

Rn,r:=E∫∣mn−m∣r dμ⟶∞R_{n,r} := \mathbb{E}\int|m_n - m|^r\,d\mu\longrightarrow\infty

for every finite r≥1r \ge1 and every sequence 1≤kn<n1 \le k_n < n satisfying kn/n→0k_n/n \to0. The joint distribution of (X,Y)(X,Y) depends neither on rr nor on the neighbor sequence.

The space T\mathcal{T} is the porcupine, or hedgehog, formed by countably many copies of [0,1][0,1], called spines, whose zero endpoints are identified as a common root oo. Write (i,a)(i,a) for the point at distance a∈(0,1]a \in(0,1] from oo on spine i≥2i \ge2. Two points have distance ∣a−b∣\lvert a-b\rvert on the same spine and a+ba+b on different spines. Each spine has Nagata dimension one relative to T\mathcal{T}, although T\mathcal{T} itself has infinite Nagata dimension at every positive scale. For the explicit unbounded response in Proposition 1, kk-NN regression is inconsistent in every finite moment order. The regression function is m(o)=0m(o)=0 and m((i,a))=[log⁡(e/a)]3m((i,a))=[\log(e/a)]^3.

In this same construction, fnf_n becomes large near the root on regions of vanishing feature probability. The regression function mm 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 F∞<∞F_\infty< \infty for every feature marginal μ\mu satisfying (10). Taking p=q=∞p=q=\infty in Corollary 1 therefore gives weak L2(μ)L_2(\mu) consistency whenever EY2<∞\mathbb{E}Y^2 < \infty. 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 s>0s>0 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 1/21/2, yet admits a fixed noiseless response with all finite moments for which Rn,r→∞R_{n,r}\to\infty for every finite r≥1r\ge1.

Neither sigma-finite Nagata dimension nor finite Nagata dimension on one positive scale guarantees the uniform Lp(μ)L_p(\mu) bounds assumed in the sufficient conditions of § 2. In each of the two examples, for every sequence satisfying (3),

Fp=sup⁡n≥2∥fn∥p=∞,1<p≤∞.F_p=\sup_{n\ge2}\lVert f_n\rVert_p=\infty,\qquad1<p\le\infty.

Indeed, the proofs show that ∫mfn dμ→∞\int m f_n\,d\mu\to\infty, whereas m∈Lp′(μ)m\in L_{p'}(\mu). Hölder’s inequality gives

∫mfn dμ≤∥m∥p′∥fn∥p,\int m f_n\,d\mu\le\lVert m\rVert_{p'}\lVert f_n\rVert_p,

so ∥fn∥p\lVert f_n\rVert_p cannot remain bounded as nn 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 mm. 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 h:[0,1]→[0,∞)h : [0,1] \to[0,\infty) with h(0)=0h(0)=0 and h(u)→0h(u) \to0 as u↓0u \downarrow0 satisfies

∣m(x)−m(z)∣≤h(Hx(ρ(x,z))),x,z∈X.(26)|m(x)-m(z)| \le h(H_x(\rho(x,z))), \qquad x,z \in\mathcal{X}. \tag*{(26)}

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 σ2≤K\sigma^2 \le K almost everywhere. If g=h2g=h^2 is concave, then, for every 1≤kn<n1 \le k_n < n,

Rn,2≤Kkn+h(knn+1)2≤Kkn+h(knn)2.(27)R_{n,2} \le\frac{K}{k_n} + h\left(\frac{k_n}{n+1}\right)^2 \le\frac{K}{k_n} + h\left(\frac{k_n}{n}\right)^2. \tag*{(27)}

Proof. The exact quadratic decomposition gives Rn,2=In,2+Jn,2R_{n,2}=I_{n,2}+J_{n,2}, with In,2≤K/knI_{n,2}\le K/k_n. Fix a query xx. The probability integral transform and (10) imply that Hx(ρ(x,Xi))H_x(\rho(x,X_i)), 1≤i≤n1\le i\le n, are independent uniform random variables. Consequently,

U(n,kn)(x)=Hx(ρ(x,X(n,kn)(x)))U_{(n,k_n)}(x)=H_x\left(\rho(x,X_{(n,k_n)}(x))\right)

has the knk_n-th uniform order-statistic distribution, whose mean is kn/(n+1)k_n/(n+1). By (26), monotonicity of hh, and Jensen’s inequality for the neighbor average,

∣1kn∑i=1knm(X(n,i)(x))−m(x)∣2≤1kn∑i=1kn∣m(X(n,i)(x))−m(x)∣2≤g(U(n,kn)(x)).\left|\frac{1}{k_n}\sum_{i=1}^{k_n}m(X_{(n,i)}(x))-m(x)\right|^2 \le\frac{1}{k_n}\sum_{i=1}^{k_n}|m(X_{(n,i)}(x))-m(x)|^2 \le g(U_{(n,k_n)}(x)).

Taking expectations and applying concavity gives

Jn,2≤∫Eg(U(n,kn)(x)) μ(dx)≤g(knn+1).J_{n,2}\le\int\mathbb{E}_g(U_{(n,k_n)}(x))\,\mu(dx)\le g\left(\frac{k_n}{n+1}\right).

This proves the first inequality; the second uses monotonicity. □

For example, if h(u)=c0uah(u)=c_0u^a with 0<a≤1/20<a\le1/2, then

Rn,2≤Kkn+c02(knn+1)2a.R_{n,2}\le\frac{K}{k_n}+c_0^2\left(\frac{k_n}{n+1}\right)^{2a}.

Choosing knk_n of order n2a/(2a+1)n^{2a/(2a+1)} gives the rate Rn,2=O(n−2a/(2a+1))R_{n,2}=O(n^{-2a/(2a+1)}). In particular, if X\mathcal{X} is the dd-dimensional Euclidean space and a=1/da=1/d with d≥2d\ge2, then the order is O(n−2/(d+2))O(n^{-2/(d+2)}) 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 φ\varphi. We first work with a fixed query xx. 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:

1kn∑i=1knφ(X(n,i)(x))=1kn∑j=1nφ(Xj)1{Xj is selected at x}.\frac{1}{k_n}\sum_{i=1}^{k_n}\varphi\left(X_{(n,i)}(x)\right)=\frac{1}{k_n}\sum_{j=1}^{n}\varphi(X_j)\mathbf{1}_{\{X_j\text{ is selected at }x\}}.

We next compute the expectation of each summand on the right. Fix an index jj and condition on Xj=zX_j=z. By independence, the remaining n−1n-1 observations still have the joint law μn−1\mu^{n-1}. For this fixed xx and zz, the no-ties assumption implies that none of the remaining observations has distance ρ(x,z)\rho(x,z) from xx, almost surely. Thus the candidate zz is selected precisely when at most kn−1k_n-1 of the remaining observations are closer to xx.

This conditional selection probability is gn(x,z)g_n(x,z). Although (11) uses the indices 2,…,n2,\ldots,n, the remaining observations have the same joint law after removing any index jj. Consequently, for μ\mu-almost every zz,

E[φ(Xj)1{Xj is selected at x}∣Xj=z]=φ(z)gn(x,z).\mathbb{E}\left[\varphi(X_j)\mathbf{1}_{\{X_j\text{ is selected at }x\}}\mid X_j=z\right]=\varphi(z)g_n(x,z).

Here the location zz is held fixed, and the expectation averages only over the remaining observations. Averaging this conditional expectation over XjX_j, whose distribution is μ\mu, gives

E[φ(Xj)1{Xj is selected at x}]=∫φ(z)gn(x,z) μ(dz).\mathbb{E}\left[\varphi(X_j)\mathbf{1}_{\{X_j\text{ is selected at }x\}}\right]=\int\varphi(z)g_n(x,z)\,\mu(dz).

The right-hand side does not depend on jj. Taking expectations in the first identity and summing these nn identical integrals therefore gives

1kn∑i=1knEφ(X(n,i)(x))=nkn∫φ(z)gn(x,z) μ(dz).\frac{1}{k_n}\sum_{i=1}^{k_n}\mathbb{E}\varphi\left(X_{(n,i)}(x)\right)=\frac{n}{k_n}\int\varphi(z)g_n(x,z)\,\mu(dz).

This explains both the use of gng_n and the factor n/knn/k_n.

Finally, the independent query has distribution μ\mu. Integrating over its location and applying Tonelli’s theorem, which is applicable because all integrands are nonnegative, we obtain

An(φ)=∫(nkn∫φ(z)gn(x,z) μ(dz))μ(dx)=∫φ(z)(nkn∫gn(x,z) μ(dx))μ(dz)=∫φ(z)fn(z) μ(dz),\begin{aligned} A_n(\varphi) &=\int\left(\frac{n}{k_n}\int\varphi(z)g_n(x,z)\,\mu(dz)\right)\mu(dx)\\ &=\int\varphi(z)\left(\frac{n}{k_n}\int g_n(x,z)\,\mu(dx)\right)\mu(dz)\\ &=\int\varphi(z)f_n(z)\,\mu(dz), \end{aligned}

where the last equality uses (13). These equalities remain valid when the integrals are infinite. Since 0≤gn≤10\leq g_n\leq1, the definition of fnf_n gives 0≤fn≤n/kn0\leq f_n\leq n/k_n. Taking φ=1\varphi=1 in the averaging identity gives

∫fn dμ=An(1)=1,\int f_n\,d\mu=A_n(1)=1,

because exactly knk_n observations are selected.

For a signed φ∈L1(μ)\varphi\in L_1(\mu), the bound on fnf_n gives ∫∣φ∣fn dμ<∞\int|\varphi| f_n\,d\mu< \infty. Applying the identity to the positive and negative parts of φ\varphi therefore proves the signed version. In particular, for every fixed nn, AnA_n is a continuous linear functional on Lr(μ)L_r(\mu) for every 1≤r≤∞1 \le r \le\infty.

Lemma 4 (Selection-count identity). Fix n≥2n \ge2, and let Z0,…,ZnZ_0,\ldots,Z_n be independent with distribution μ\mu. For each ii, let NiN_i be the indices of the knk_n nearest neighbors of query ZiZ_i among the other nn observations. Define the selection count of observation ZjZ_j by

Dn,j=∑0≤i≤ni≠j1{j∈Ni}.(28)D_{n,j} = \sum_{\substack{0 \le i \le n \\ i \ne j}} \mathbf{1}_{\{j \in N_i\}}. \tag*{(28)}

Under (9), for every j∈{0,…,n}j \in\{0,\ldots,n\},

fn(z)=1knE[Dn,j∣Zj=z]for μ-almost every z.(29)f_n(z) = \frac{1}{k_n}\mathbb{E}[D_{n,j} \mid Z_j = z] \qquad\text{for }\mu\text{-almost every }z. \tag*{(29)}

In particular, EDn,j=kn\mathbb{E}D_{n,j} = k_n.

Proof of Lemma 4. Fix jj and a possible query index i≠ji \ne j. Conditional on Zi=xZ_i = x and Zj=zZ_j = z, the remaining n−1n-1 feature observations are independent with distribution μ\mu. By (9), none has distance ρ(x,z)\rho(x,z) from xx, almost surely. Consequently,

P{j∈Ni∣Zi=x,Zj=z}=gn(x,z).\mathbb{P}\{j \in N_i \mid Z_i = x, Z_j = z\} = g_n(x,z).

Independence of ZiZ_i and ZjZ_j gives

E[1{j∈Ni}∣Zj=z]=∫gn(x,z) μ(dx)for μ-almost every z.\mathbb{E}[\mathbf{1}_{\{j \in N_i\}} \mid Z_j = z] = \int g_n(x,z)\,\mu(dx) \qquad\text{for }\mu\text{-almost every }z.

There are nn possible query indices i≠ji \ne j. Summing their contributions and using (12),

E[Dn,j∣Zj=z]=n∫gn(x,z) μ(dx)=knfn(z).\mathbb{E}[D_{n,j} \mid Z_j = z] = n \int g_n(x,z)\,\mu(dx) = k_n f_n(z).

Integrating over zz and using ∫fn dμ=1\int f_n\,d\mu= 1 gives EDn,j=kn\mathbb{E}D_{n,j} = k_n.

Approximation and the quadratic criterion

We first record the approximation fact used below.

Lemma 5. Bounded Lipschitz functions are dense in La(μ)L_a(\mu) for every 1≤a<∞1 \le a < \infty.

Proof. For Lipschitz density in L1(μ)L_1(\mu), see Hanneke et al. [15 supplementary material, Lemma A.1]. We give a proof for all 1≤a<∞1 \le a < \infty. Let H\mathcal{H} be their closure in La(μ)L_a(\mu). For a nonempty closed set FF, the bounded Lipschitz functions max⁡{0,1−jρ(x,F)}\max\{0,1-j\rho(x,F)\} converge pointwise to 1F\mathbf{1}_F. Dominated convergence shows that 1F∈H\mathbf{1}_F \in\mathcal{H}. The class of Borel sets whose indicators belong to H\mathcal{H} is a Dynkin class: it contains X\mathcal{X}, is closed under complements, and is closed under countable disjoint unions by LaL_a convergence of finite partial sums. The closed sets form a generating π\pi-system, so this class contains every Borel set. Density of simple functions proves the assertion.

Proof of Theorem 2. First suppose Dq,2<∞D_{q,2}<\infty and fix a joint law satisfying (20). The moment assumptions imply

EY2=∫σ2 dμ+∫m2 dμ≤∥σ2∥q′+∥m∥2p′2<∞,\mathbb{E}Y^2=\int\sigma^2\,d\mu+\int m^2\,d\mu\leq\|\sigma^2\|_{q'}+\|m\|_{2p'}^2<\infty,

so the quadratic identities above apply.

For the approximation term, fix ε>0\varepsilon>0 and choose a bounded Lipschitz function vv with ∥m−v∥2p′<ε\|m-v\|_{2p'}<\varepsilon. This is possible because p>1p>1 and therefore 2p′<∞2p'<\infty. Put ϕ=m−v\phi=m-v. Adding and subtracting the neighbor average of vv and its value at the query gives

m‾n(x)−m(x)=1kn∑i=1knϕ(X(n,i)(x))+[1kn∑i=1knv(X(n,i)(x))−v(x)]−ϕ(x).\overline{m}_n(x)-m(x)=\frac{1}{k_n}\sum_{i=1}^{k_n}\phi(X_{(n,i)}(x))+\left[\frac{1}{k_n}\sum_{i=1}^{k_n}v(X_{(n,i)}(x))-v(x)\right]-\phi(x).

The three terms are the approximation error at the selected neighbors, the local averaging error for vv, and the negative approximation error at the query. The inequality for a squared sum and Jensen’s inequality for the first average yield

Jn,2≤3[An(ϕ2)+E∫∣1kn∑i=1knv(X(n,i)(x))−v(x)∣2μ(dx)+∥ϕ∥22].(30)J_{n,2}\leq3\left[A_n(\phi^2)+\mathbb{E}\int\left|\frac{1}{k_n}\sum_{i=1}^{k_n}v(X_{(n,i)}(x))-v(x)\right|^2\mu(dx)+\|\phi\|_2^2\right]. \tag*{(30)}

The averaging identity (Lemma 1) and Hölder’s inequality give

An(ϕ2)=∫ϕ2fn dμ≤Fp∥ϕ∥2p′2<Fpε2.(31)A_n(\phi^2)=\int\phi^2 f_n\,d\mu\leq F_p\|\phi\|_{2p'}^2<F_p\varepsilon^2. \tag*{(31)}

Since μ(X)=1\mu(\mathcal{X})=1, Hölder’s inequality also gives

∥ϕ∥22=∫ϕ2⋅1 dμ≤∥ϕ2∥p′∥1∥p=∥ϕ∥2p′2<ε2.\|\phi\|_2^2=\int\phi^2\cdot1\,d\mu\leq\|\phi^2\|_{p'}\|1\|_p=\|\phi\|_{2p'}^2<\varepsilon^2.

For the middle term, let dn(x)=ρ(x,X(n,kn)(x))d_n(x)=\rho(x,X_{(n,k_n)}(x)). For every η>0\eta>0, bounded uniform continuity of vv supplies b>0b>0 such that ∣v(z)−v(x)∣≤η|v(z)-v(x)|\leq\eta whenever ρ(x,z)<b\rho(x,z)<b. Therefore

E∫∣1kn∑i=1knv(X(n,i)(x))−v(x)∣2μ(dx)≤η2+4∥v∥∞2P{dn(X)≥b}.(32)\mathbb{E}\int\left|\frac{1}{k_n}\sum_{i=1}^{k_n}v(X_{(n,i)}(x))-v(x)\right|^2\mu(dx)\leq\eta^2+4\|v\|_\infty^2\mathbb{P}\{d_n(X)\geq b\}. \tag*{(32)}

Locality (9) and dominated convergence make the probability tend to zero; see also the locality argument of Cover and Hart [6 Section V]. Letting η↓0\eta\downarrow0 and then ε↓0\varepsilon\downarrow0 in (30) proves Jn,2→0J_{n,2}\to0.

For the noise, the exact identity (19) gives

In,2≤Lkn+Dq,2∥σ21{σ2>L}∥q′.(33)I_{n,2}\leq\frac{L}{k_n}+D_{q,2}\|\sigma^2\mathbf{1}_{\{\sigma^2>L\}}\|_{q'}. \tag*{(33)}

The bounded part uses An(1)=1A_n(1)=1, and the tail uses Hölder’s inequality. Since q′<∞q'<\infty, the tail norm tends to zero as L→∞L\to\infty. First letting n→∞n\to\infty at fixed LL, then letting L→∞L\to\infty, proves In,2→0I_{n,2}\to0. Together with (18), this proves sufficiency.

For necessity, define positive continuous linear functionals on Lq′(μ)L_{q'}(\mu) by

Λn(φ)=1kn∫φfn dμ.(34)\Lambda_n(\varphi)=\frac{1}{k_n}\int\varphi f_n\,d\mu. \tag*{(34)}

Their norms are ∥Λn∥=∥fn∥q/kn\|\Lambda_n\| = \|f_n\|_q/k_n. Each is finite, since fn/kn≤n/kn2f_n/k_n \le n/k_n^2. For a nonnegative φ∈Lq′(μ)\varphi\in L_{q'}(\mu), let SS be an independent Rademacher sign and set Y=Sφ(X)Y = S\sqrt{\varphi}(X). This law has m=0m = 0 and σ2=φ\sigma^2 = \varphi, and hence belongs to (20). For this law,

Rn,2=In,2=Λn(φ).R_{n,2} = I_{n,2} = \Lambda_n(\varphi).

Consistency for every such law implies that (Λn(φ))n(\Lambda_n(\varphi))_n is bounded for every nonnegative φ∈Lq′(μ)\varphi\in L_{q'}(\mu). Decomposing a signed function into its positive and negative parts, the uniform boundedness principle gives sup⁡n∥Λn∥=Dq,2<∞\sup_n \|\Lambda_n\| = D_{q,2} < \infty. If these norms are unbounded, the same principle provides a fixed φ0∈Lq′(μ)\varphi_0 \in L_{q'}(\mu) with sup⁡n∣Λn(φ0)∣=∞\sup_n |\Lambda_n(\varphi_0)| = \infty. Set φ=∣φ0∣\varphi= |\varphi_0|. Positivity gives Λn(φ)≥∣Λn(φ0)∣\Lambda_n(\varphi) \ge|\Lambda_n(\varphi_0)|. The law Y=Sφ(X)Y = S\sqrt{\varphi}(X) then has Rn,2→∞R_{n,2} \to\infty along an increasing subsequence. Each fixed-nn error is finite, and the law does not depend on nn. 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 nn and write k=knk = k_n. Take n+1n + 1 independent points Z0,…,ZnZ_0, \ldots, Z_n with distribution μ\mu. For each ii, let NiN_i be the indices of the kk nearest neighbors of ZiZ_i among the other nn points. By (10), almost surely there are no distance ties at any of these queries. For a fixed target index jj, put

Ij={i≠j:j∈Ni}.I_j = \{i \ne j : j \in N_i\}.

Thus ∣Ij∣=Dn,j|I_j| = D_{n,j} in (28). For i∈Iji \in I_j, consider the closed ball Bi=B(Zi,ρ(Zi,Zj))B_i = B(Z_i,\rho(Z_i,Z_j)). Every such ball contains ZjZ_j. The Nagata property supplies a subfamily covering all centres ZiZ_i, i∈Iji \in I_j, with multiplicity at most δ+1\delta+ 1. Since every retained ball contains ZjZ_j, there are at most δ+1\delta+ 1 retained balls. Each contains at most k+1k + 1 of the augmented sample points, including its centre and ZjZ_j. As j∉Ijj \notin I_j, it therefore contains at most kk of the centres being counted. Hence

Dn,j=∣Ij∣≤k(δ+1).D_{n,j} = |I_j| \le k(\delta+ 1).

Taking the conditional expectation given Zj=zZ_j = z and using (29) gives

fn(z)=1kE[Dn,j∣Zj=z]≤δ+1for μ-almost every z.f_n(z) = \frac{1}{k}\mathbb{E}[D_{n,j} \mid Z_j = z] \le\delta+ 1 \qquad\text{for }\mu\text{-almost every }z.

The bound is uniform in nn. The averaging identity yields Stone’s condition. The consistency conclusion follows from Corollary 1 with p=q=∞p = q = \infty. □

For completeness, we retain the compactness proof of the fixed-mass bound in (21), in the global case used here.

Global bound for fu∗f_u^*. Suppose that X\mathcal{X} is complete and separable and dim⁡Nag(X)≤δ\dim_{\mathrm{Nag}}(\mathcal{X}) \le\delta. Fix z∈Xz \in\mathcal{X} and 0<u≤10 < u \le1. By inner regularity of a Borel probability measure on a complete separable metric space, it suffices to prove μ(K)≤(δ+1)u\mu(K) \le(\delta+ 1)u for an arbitrary compact subset KK of

{x:μ(B(x,ρ(x,z)))≤u}.\{x : \mu(B(x,\rho(x,z))) \le u\}.

Let D={am:m≥1}D = \{a_m : m \ge1\} be a countable dense subset of a nonempty KK. For every NN, apply the Nagata property to B(am,ρ(am,z))B(a_m,\rho(a_m,z)), 1≤m≤N1 \le m \le N. The retained balls cover all a1,…,aNa_1,\ldots,a_N and all contain zz, so there are at most δ+1\delta+ 1 of them. Repeating centres if necessary, denote their centres by x1N,…,xδ+1N∈Kx_1^N,\ldots,x_{\delta+1}^N \in K. Compactness gives a subsequence along which xiN→xi∈Kx_i^N \to x_i \in K for every ii.

We claim that B(xi,ρ(xi,z))B(x_i,\rho(x_i,z)), 1≤i≤δ+11 \le i \le\delta+ 1, cover KK. Their union is closed, so it suffices to show that it contains DD. For each fixed mm, some index ii covers ama_m along a further infinite subsequence. Passing to the limit in ρ(am,xiN)≤ρ(xiN,z)\rho(a_m,x_i^N) \le\rho(x_i^N,z) gives ρ(am,xi)≤ρ(xi,z)\rho(a_m,x_i) \le\rho(x_i,z). This proves the claim. Since each xi∈Kx_i \in K, every limiting ball has mass at most uu. Thus μ(K)≤(δ+1)u\mu(K) \le(\delta+ 1)u and fu∗(z)≤δ+1f_u^*(z) \le\delta+ 1. □

Proof of Proposition 1. Choose c>0c > 0 so that

∑i=2∞ci(log⁡i)2=1,pi=ci(log⁡i)2.\sum_{i=2}^{\infty} \frac{c}{i(\log i)^2} = 1,\qquad p_i = \frac{c}{i(\log i)^2}.

Let T\mathcal{T} be the countable bouquet of intervals

T={o}∪{(i,a):i≥2, 0<a≤1},\mathcal{T} = \{o\} \cup\{(i,a) : i \ge2,\ 0 < a \le1\},

with common root oo and tree metric

ρ(o,(i,a))=a,ρ((i,a),(j,b))={∣a−b∣,i=j,a+b,i≠j.\rho(o,(i,a)) = a,\qquad\rho((i,a),(j,b)) = \begin{cases} |a-b|, & i=j,\\ a+b, & i\ne j. \end{cases}

Put no mass at oo, and put Lebesgue measure of total mass pip_i on spine ii:

μ(E)=∑i=2∞pi∫011E((i,a)) da(E Borel).\mu(E) = \sum_{i=2}^{\infty} p_i \int_0^1 1_E((i,a))\,da \qquad(E\text{ Borel}).

The space is separable. It is also complete: a Cauchy sequence whose distances from oo tend to zero converges to oo; otherwise it eventually stays on one compact spine. Every sphere meets each spine in at most two points, so every sphere has zero μ\mu-mass. In particular, the no-distance-ties assumption holds.

Each spine has Nagata dimension one relative to T\mathcal{T}, 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 oo. Only the ball at the first centre can reach oo: any later ball that reaches oo 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, T\mathcal{T} is sigma-finite dimensional in the sense of Nagata. Its dimension in itself is infinite on every positive scale: for any 0<a<min⁡{s,1}0 < a < \min\{s,1\}, the balls B((i,a),a)B((i,a),a) form a disconnected family and all contain oo.

For 0<u<10 < u < 1, define

fu∗(y)=1uμ{x:μ(B(x,ρ(x,y)))≤u},N(u)=#{i≥2:pi≥u}.f_u^*(y) = \frac{1}{u}\mu\{x : \mu(B(x,\rho(x,y))) \le u\},\qquad N(u) = \#\{i \ge2 : p_i \ge u\}.

Fix y=(j,a)y = (j,a) with 0<a≤u/20 < a \le u/2. For every i≠ji \ne j with pi≥up_i \ge u, consider centres x=(i,t)x = (i,t) with

0<t≤u−a2pi.0 < t \le\frac{u-a}{2p_i}.

This interval is contained in (0,1](0,1]. Since ρ(x,y)=t+a\rho(x,y)=t+a, the corresponding ball satisfies

μ(B(x,ρ(x,y)))≤pi(2t+a)+(1−pi)a=a+2pit≤u.\mu(B(x,\rho(x,y))) \le p_i(2t+a)+(1-p_i)a=a+2p_i t\le u.

The mass of these centres on spine ii is (u−a)/2≥u/4(u-a)/2\ge u/4. Therefore

fu∗(y)≥N(u)−14if y=(j,a),0<a≤u/2.(35)f_u^*(y)\ge\frac{N(u)-1}{4}\qquad\text{if }y=(j,a),\quad0<a\le u/2. \tag*{(35)}

Now put un=kn/(2n)u_n=k_n/(2n). Fix x,yx,y with t=μ(B(x,ρ(x,y)))≤unt=\mu(B(x,\rho(x,y)))\le u_n. Since spheres have zero mass, the number ZZ of the other n−1n-1 sample points closer to xx than yy has distribution Bin⁡(n−1,t)\operatorname{Bin}(n-1,t). Markov’s inequality gives

P{Z≥kn}≤(n−1)tkn≤n−12n<12.\mathbb{P}\{Z\ge k_n\}\le\frac{(n-1)t}{k_n}\le\frac{n-1}{2n}<\frac{1}{2}.

Thus gn(x,y)≥1/2g_n(x,y)\ge1/2 on this set. By (13),

fn(y)≥n2knμ{x:μ(B(x,ρ(x,y)))≤un}=14fun∗(y).(36)f_n(y)\ge\frac{n}{2k_n}\mu\{x:\mu(B(x,\rho(x,y)))\le u_n\}=\frac{1}{4}f_{u_n}^*(y). \tag*{(36)}

Define one noiseless response by

Y=m(X),m(o)=0,m((i,a))=[log⁡(e/a)]3.Y=m(X),\qquad m(o)=0,\qquad m((i,a))=[\log(e/a)]^3.

The response is noiseless, and for every 1≤r<∞1\le r<\infty,

E∣Y∣r=∫∣m∣r dμ=∫01[log⁡(e/a)]3r da=e∫1∞t3re−t dt<∞.\mathbb{E}|Y|^r=\int|m|^r\,d\mu=\int_0^1[\log(e/a)]^{3r}\,da=e\int_1^\infty t^{3r}e^{-t}\,dt<\infty.

Thus the same regression function belongs to every finite Lr(μ)L_r(\mu). For all sufficiently large nn, N(un)≥2N(u_n)\ge2. For these nn, the averaging identity and (33)–(34) give

An(m)≥N(un)−116∫0un/2[log⁡(e/a)]3 da≥(N(un)−1)un64[log⁡(2e/un)]3.(37)A_n(m)\ge\frac{N(u_n)-1}{16}\int_0^{u_n/2}[\log(e/a)]^3\,da \ge\frac{(N(u_n)-1)u_n}{64}[\log(2e/u_n)]^3. \tag*{(37)}

For the second inequality, integrate only over a∈[un/4,un/2]a\in[u_n/4,u_n/2].

To see that this bound diverges for every un→0u_n\to0, choose jj with pj+1<u≤pjp_{j+1}<u\le p_j. Then N(u)=j−1N(u)=j-1, and

(N(u)−1)u[log⁡(2e/u)]3≥(j−2)pj+1[log⁡(2e/pj)]3≍log⁡j⟶∞.(N(u)-1)u[\log(2e/u)]^3\ge(j-2)p_{j+1}[\log(2e/p_j)]^3\asymp\log j\longrightarrow\infty.

Since kn/n→0k_n/n\to0, (35) shows that An(m)→∞A_n(m)\to\infty. For every 1≤r<∞1\le r<\infty, Jensen’s inequality on the joint distribution of the sample and the independent query yields

Rn,r≥E∣∫(mn−m) dμ∣r=∣An(m)−∫m dμ∣r⟶∞.R_{n,r}\ge\mathbb{E}\left|\int(m_n-m)\,d\mu\right|^r=\left|A_n(m)-\int m\,d\mu\right|^r\longrightarrow\infty.

Each fixed-nn risk is finite, since (14) gives

Rn,r≤2r−1[An(∣m∣r)+∥m∥rr]≤2r−1(nkn+1)∥m∥rr<∞.R_{n,r}\le2^{r-1}\left[A_n(|m|^r)+\|m\|_r^r\right]\le2^{r-1}\left(\frac{n}{k_n}+1\right)\|m\|_r^r<\infty.

The joint distribution of (X,Y)(X,Y) is fixed throughout, and the regression function depends neither on rr nor on the sequence (kn)(k_n).

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 ℓ1\ell_1 tree, with its induced metric:

X0=[0,1/2]e0 ∪ ⋃i≥2[1,2]ei,\mathcal{X}_0=[0,1/2]e_0\ \cup\ \bigcup_{i\ge2}[1,2]e_i,

where the eie_i are distinct unit coordinate vectors. It is complete and separable. Distinct interval components have distance at least one, so balls of radius less than 1/21/2 remain within one component. The interval covering property therefore gives dim⁡Nag1/2(X0,X0)≤1\dim_{\mathrm{Nag}}^{1/2}(\mathcal{X}_0,\mathcal{X}_0)\le1.

Give the hub [0,1/2]e0[0,1/2]e_0 Lebesgue density one, hence total mass 1/21/2, and give branch [1,2]ei[1,2]e_i uniform mass qi=pi/2q_i=p_i/2, with pip_i as in the preceding proof. Write μ0\mu_0 for this probability measure. Every sphere meets each component in at most two points, so (10) holds. Put

T(v)=∑i:qi≤vqi.T(v)=\sum_{i:q_i\le v}q_i.

The integral test for ∑i[i(log⁡i)2]−1\sum_i[i(\log i)^2]^{-1} gives T(v)≍1/log⁡(1/v)T(v)\asymp1/\log(1/v) as v↓0v\downarrow0.

For a target z=ae0z=ae_0 with 0<a≤u/20<a\le u/2 and 0<u<1/20<u<1/2, every query x=teix=te_i, 1≤t≤21\le t\le2, has

μ0(B(x,ρ(x,z)))=qi+a.\mu_0(B(x,\rho(x,z)))=q_i+a.

The ball contains its entire branch and the hub segment [0,a]e0[0,a]e_0, and it contains no other branch. Thus every branch with qi≤u/2q_i\le u/2 contributes its full mass to the fixed-mass reverse set, giving

fu∗(ae0)≥T(u/2)u.f_u^*(ae_0)\ge\frac{T(u/2)}{u}.

The binomial argument in (36) applies unchanged with μ0\mu_0, so, for un=kn/(2n)u_n=k_n/(2n),

fn(ae0)≥T(un/2)4un(0<a≤un/2).f_n(ae_0)\ge\frac{T(u_n/2)}{4u_n}\qquad(0<a\le u_n/2).

Define m(ae0)=[log⁡(e/a)]3m(ae_0)=[\log(e/a)]^3 for a>0a>0, put m(0)=0m(0)=0, and put m=0m=0 on every far branch. The noiseless response Y=m(X)Y=m(X) has every finite moment, by the same exponential-tail integral as above. Integrating only over a∈[un/4,un/2]a\in[u_n/4,u_n/2] yields

An(m)≥T(un/2)16[log⁡(2e/un)]3⟶∞.A_n(m)\ge\frac{T(u_n/2)}{16}[\log(2e/u_n)]^3\longrightarrow\infty.

Jensen’s inequality again gives Rn,r→∞R_{n,r}\to\infty for every finite r≥1r\ge1, for this one fixed law and every sequence with kn/n→0k_n/n\to0. Each fixed-nn risk is finite.

References

References

  1. [1]Biau, G. and Devroye, L. (2015). Lectures on the Nearest Neighbor Method. Springer, Cham.
  2. [2]Cérou, F. and Guyader, A. (2006). Nearest neighbor classification in infinite dimension. ESAIM: Probability and Statistics 10 340–355.DOI
  3. [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. [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. [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. [6]Cover, T. M. and Hart, P. E. (1967). Nearest neighbor pattern classification. IEEE Trans. Inform. Theory 13(1) 21–27.DOI
  7. [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. [8]Devroye, L. and Györfi, L. (1985). Nonparametric Density Estimation: The L₁ View. Wiley, New York.
  9. [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.
  10. [12]Györfi, L., Kohler, M., Krzyżak, A. and Walk, H. (2002). A Distribution-Free Theory of Nonparametric Regression. Springer, New York.DOI
  11. [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
  12. [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
  13. [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.
  14. [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
  15. [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.
  16. [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
  17. [22]Stone, C. J. (1977). Consistent nonparametric regression. Ann. Statist. 5(4) 595–620.DOI

Paper details

vlnc:W_94v9j6xp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents