{'fraction_non_alphanumeric': 0.05536171202605257, 'fraction_numerical': 0.015526866713189114, 'mean_word_length': 3.8634049773755654, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A nearest neighbor estimate of the residual variance

Abstract: We study the problem of estimating the smallest achievable mean-squared error in regression function estimation. The problem is equivalent to estimating the second moment of the regression function of Y on X ∈ Rd. We introduce a nearest-neighbor-based estimate and obtain a normal limit law for the estimate when X has an absolutely continuous distribution, without any condition on the density. We also compute the asymptotic variance explicitly and derive a non-asymptotic bound on the variance that does not depend on the dimension d. The asymptotic variance does not depend on the smoothness of the density of X or of the regression function. A non-asymptotic exponential concentration inequal-


Introduction
In this paper we study the problem of estimating the smallest achievable meansquared error in regression function estimation in multivariate problems. We introduce and analyze a nearest neighbor-based estimate of the second moment of the regression function. The second moment of the regression function is closely tied to the best possible achievable mean squared error. It is shown that the estimate is asymptotically normally distributed. It is remarkable that the asymptotic variance only depends on conditional moments of the regression function but not on its smoothness. Moreover, the non-asymptotic variance is bounded by a constant that is independent of the dimension. We also establish a non-asymptotic exponential concentration inequality. We illustrate these results studying variable selection. In particular, we construct and analyze a test for deciding whether a component of the observational vector has predictive power.
The formal setup is as follows. Let (X, Y ) be a pair of random variables such that X = (X (1) , . . . , X (d) ) takes values in R d and Y is a real-valued random variable with E[Y 2 ] < ∞. We denote by μ the distribution of the observation vector X, that is, for all measurable sets A ⊂ R d , μ(A) = P{X ∈ A}. Then the regression function is well defined for μ-almost all x. The center of our investigations is the functional The importance of this functional stems from the fact that for each measurable function g : R d → R one has E (g(X) − Y ) 2 = L * + E (m(X) − g(X)) 2 and, in particular, where the minimum is taken over all measurable functions g : R d → R. In other words, L * is the minimal mean squared error of any "predictor" of Y based on observing X. L * is often referred to as the residual variance.
In regression analysis the residual variance L * is of obvious interest as it provides a lower bound for the performance of any regression function estimator. In this paper we study the problem of estimating L * based on data consisting (For a detailed theory of universally consistent regression function estimation see [15].) However, the rate of convergence of such estimators is determined by the rate of convergence of the mean squared error of m n which can be quite slow even under regularity assumptions on the underlying distribution. Estimating the entire regression function m(x) is, intuitively, "harder" than estimating the value of L * . Indeed, nearest-neighbor-based estimators of L * have been constructed and analyzed by Devroye, Ferrario, Györfi, and Walk [6], Devroye, Schäfer, Györfi, and Walk [10], Evans and Jones [12], Liitiäinen, Corona, and Lendasse [17], [18], Liitiäinen, Verleysen, Corona, and Lendasse [19], and Ferrario and Walk [13]. These estimates have been shown to have a faster rate of convergence-under some natural assumptions-than estimates based on estimating the error of consistent regression function estimators. Moreover, the estimate in [6] is strongly universally consistent.
In this paper we introduce yet another universally consistent nearest-neighborbased estimator of L * . The advantage of this estimator, apart from sharing the fast rates of convergence of previously defined estimators, is that its random fluctuations may be bounded by dimension-, and distribution-independent quantities. In particular, we prove a central limit theorem and a distributionfree upper bound for the variance for the new estimator that show that it is concentrated around its expected value in an interval of width O(1/ √ n), independently of the dimension. The established concentration property is crucial in a variable-selection procedure that we discuss as an application. In particular, we design a test for deciding whether exclusion of a certain component of X increases L * or not.
The paper is organized as follows. In Section 2 we introduce a novel estimate of L * and establish some of its properties such as asymptotic normality and a non-asymptotic concentration inequality. The central limit theorem holds without any smoothness condition on the regression function, and the asymptotic variance depends only on the conditional moments of Y (Theorem 2.1). We prove a non-asymptotic bound on the variance that does not depend on the dimension of X (Theorem 2.2), and show an exponential concentration inequality for the centered estimate (Theorem 2.3). All these results are universal in the sense that we only assume that X has a density and Y is bounded.
In Section 3 we briefly describe how the results method based on the results of Section 2 may be relevant for variable selection. Finally, the proofs are presented in Section 4.

A nearest-neighbor based estimate and its asymptotic normality
Denoting the second moment of the regression function by and therefore estimating L * is essentially equivalent to estimating S * (as the "easy" part E Y 2 may be estimated by, e.g., (1/n) n i=1 Y 2 i whose behavior is well understood).
Next we introduce a nearest neighbor-based estimator of S * . Based on the data D n , we start by constructing a nearest-neighbor (1-NN) regression function estimator as follows. Let X 1,n (x) be the first nearest neighbor of x among X 1 , . . . , X n (with respect to the Euclidean distance in R d ) and let Y 1,n (x) be its label. (In order to rigorously define the nearest neighbor, we assume that ties are broken in order to favor points with smaller index. Since we assume the distribution of X to be absolutely continuous, this issue is immaterial since ties occur with probability zero.) The 1-NN estimator of the regression function m is defined as m n (x) = Y 1,n (x).
The proposed estimate of S * is By a straightforward adjustment of the arguments of Devroye, Ferrario, Györfi, and Walk [6], one may show that S n is a strongly universal consistent estimate of S * , that is, lim n S n = S * with probability one for any distribution of (X, Y ) with E[Y 2 ] < ∞. Note that the consistent functional estimate S n is based on a non-consistent regression function estimate m n . Next we establish asymptotic normality of S n under the condition that the response variable Y is bounded. In order to describe the asymptotic variance, we introduce the dimension-dependent constant α(d) as follows.
Let B x,r denote the closed ball of radius r > 0 centered at x in R d and let λ denote the Lebesgue measure on R d . Let V be a random vector uniformly distributed in B 0,1 . Define 1 = (1, 0, 0, . . . , 0) ∈ R d and let B = B 1,1 B V, V . Introduce the random variable and define Assume that μ has a density and that there exists a constant L > 0 such that and define The dependence of the asymptotic variance on the dimension d is weak, merely via the constant α(d). Given X 1 , . . . , X n , Devroye, Györfi, Lugosi, and Walk [8] considered the probability measures of the Voronoi cells. They proved that the asymptotic variance of n-times the probability measure of the Voronoi cell is equal to α(d) − 1. Thus, this asymptotic variance is universal in the sense that it does not depend on the underlying density. A few values are α(1) = 1.5, α(2) ≈ 1.28, α(3) ≈ 1. 18 The next theorem shows that, up to a constant factor, this bound holds nonasymptotically.

Theorem 2.2.
Assume that μ has a density and that |Y | < L. Then for all n ≥ 1, A nearest neighbor estimate of the residual variance

1757
The next result is a non-asymptotic exponential inequality that extends Theorem 2.2. It implies that for all t > 0, for a universal constant c > 0. It is an interesting open question whether the right-hand side can be improved to e −(t/(cL 2 )) 2 . This would give a nonasymptotic analog of the central limit theorem of Theorem 2.1.

Theorem 2.3.
Assume that μ has a density and that |Y | < L. Write Then for every n ≥ 1 and > 0, we have and 3) The proofs of Theorems 2.1, 2.2 and 2.3 are presented in Section 4.

Illustration: testing for dimension reduction
In standard nonparametric regression design, one considers a finite number of real-valued features X (i) , i ∈ I ⊂ {1, . . . , d} for predicting the value of a response variable Y . A first question one may try to answer is whether these features suffice to explain Y . In case they do, an estimation method can be applied on the basis of the features already under consideration. Otherwise more or different features need to be considered. The quality of a subvector {X (i) , i ∈ I} of X is measured by the minimum mean squared error that can be achieved using the features as explanatory variables. L * (I) depends upon the unknown distribution of (Y, X (i) : i ∈ I).
Thus, even before a regression function estimate is chosen, one may be interested in estimating L * . For possible dimensionality reduction, one needs, in general, to test the hypothesis for a particular (proper) subset I of {1, . . . , d}. A natural way of approaching this testing problem is by estimating both L * and L * (I), and accept the hypothesis if the two estimates are close to each other (De Brabanter, Ferrario and Györfi [5]). Introduce the notation Then the hypothesis (3.1) is equivalent to Without loss of generality, consider the case I = {1, . . . , d − 1}, that is, the case when one tests whether the last component X (d) of the observation vector (X (1) , . . . , X (d) ) is ineffective. Let the transformation T be defined by Thus, dropping the component X (d) from the observation vector X = (X (1) , . . . , X (d) ) leads to the observation vector Using the notation and the null-hypothesis S * = S * is equivalent to We propose to approach this testing problem by considering the nearestneighbor estimate defined in Section 2. Let S n be the estimate of S * using the sample Assume that an independent sample of size 2n is available: We use D 2n to construct an estimate S n of S * . S n is defined as the nearestneighbor estimate computed from the sample The proposed test is based of the test statistic T n = S n − S n and accepts the null hypothesis (3.2) if and only if where ω n is an increasing unbounded sequence such that a n → 0. Under the alternative hypothesis, according to the consistency result of Devroye, Ferrario, Györfi, and Walk [6], for bounded Y , and this convergence is universal, that is, it holds without any conditions. Thus, since a n → 0, if S * = S * , then, with probability one, the test does not make any mistake for a sufficiently large n.
In order to understand the behavior of the test, one needs to study the difference of the biases of the estimates ET n = ES n − E S n under the null hypothesis (3.2). In this case we have If m and f are Lipschitz continuous and f is bounded away from 0, then, by Devroye, Ferrario, Györfi, and Walk [6], when d ≥ 2 and Thus, under the null hypothesis (3.2),  (3.5) imply that the probability of error may be bounded as Thus, the test is consistent.
The condition that the density f is bounded away from zero may be avoided at the price of a worse rate of convergence. In particular, if m is C-Lipschitz and X is bounded, then In this case the threshold should be larger: One may prove that the test is not only consistent in the sense that P{T n > a n } → 0 under the null hypothesis but also in the sense that lim sup n→∞ 1 {Tn>an} = 0 with probability one. For a discussion and references on the notion of strong consistency we refer the reader to Devroye and Lugosi [9], Biau and Györfi [2], Gretton and Györfi [14].
The proof of strong consistency under the alternative hypothesis follows simply from (3.3). Under the null hypothesis it follows from Theorem 2.3. Indeed, Theorem 2.3 implies that For δ > 3/2, choose a n := (ln n) δ n −1/2 + ω n · n −2/d with increasing unbounded ω n = o(n 2/d ). Then, under the null hypothesis and so the Borel-Cantelli Lemma implies that the test makes error only finitely many times almost surely. Remark. In applications, one would like to test not only if a given component of X carries predictive information but rather test the same for each of the d variables. In such cases, one faces a multiple testing problem with d dependent tests. In order to analyze such multiple testing procedures, say, by the Bonferroni approach, one needs a uniform control over the fluctuations of the test statistic. In such cases a non-asymptotic concentration inequality of Theorem 2.3 is particularly useful.

Proofs
In the proofs below we use two lemmas on the measure of Voronoi cells. Let Proof. Devroye, Györfi, Lugosi, and Walk [8] proved that there exists a positive constant c k such that n k E μ(A n (X 1 )) k ≤ c k , and nμ(A n (X 1 )) converges in distribution to a random variable Z such that . . This lemma is on the same non-asymptotic bound. We show that E μ(A n (X 1 )) k (4.1) ≤ P {X n+1 , . . . , X n+k are the nearest neighbors of X 1 among X 2 , . . . , X n+k } , which implies that Recall that B x,r denotes the closed ball of radius r > 0 centered at x and note that and P {X n+1 . . . , X n+k are the nearest neighbors of X 1 among X 2 , . . . , X n+k } (4.1) follows from comparing the right-hand sides of the two equations above. On the one hand, while on the other hand,

Proof of Theorem 2.2
We prove the variance bound of Theorem 2. Then By the decomposition we have that Conditionally on D n , S n is an average of independent, identically distributed (i.i.d.) random variables bounded by L 2 , and therefore Notice that we may write

m(x)μ(dx).
Putting L n = E [S n | D n ], this implies Considering L n as a function of the n i.i.d. pairs (X i , Y i ) n i=1 , we may use the Efron-Stein inequality to bound the variance of L n . Define L (j) n as L n when (X j , Y j ) is omitted from the sample. By Lemma 4.3, Let {A n (X 2 ), . . . , A n (X n )} be the Voronoi partition, when X 1 is omitted from the sample. Then Thus, Lemma 4.1 implies and therefore to the desired bound

Introduce the notation
and and We prove Theorem 2.1 by showing that, for any u, v ∈ R, where Φ denotes the standard normal distribution function, and that Györfi and Walk [16] proved that Thus, (4.2) holds if and Proof of (4.4).
Let's start with the decomposition Next we apply a Berry-Esseen type central limit theorem (see Theorem 14 in Petrov [20]). For a universal constant c > 0, we have we have We need to show that in probability and We use this to prove (4.7). Indeed, Thus, and so To complete the proof of (4.7), it suffices to show that the sum above converges to zero as n → ∞. To this end, note that Lemma 4.1 implies that nE μ(A n (X 1 )) 2 ≤ c 2 /n → 0, and furthermore nE An(X1) It remains to show that Fix any > 0 and choose a bounded continuous function M 2 such that (4.10) The first term on the right-hand side converges to 0 by the dominated convergence theorem, since, by Lemma 6.1 in [15], To bound the second term, we introduce some notation. A set C ⊂ R d is a cone of angle π/3 centered at 0 if there exists an x ∈ R d with x = 1 such that Let γ d be the minimal number of cones C 1 , . . . , C γ d of angle π/3 centered at 0 such that their union covers R d . The second term on the right-hand side of (4.10) is bounded by by Lemma 6.3 in [15]. Thus, (4.9) is proved and hence so is (4.7). For the proof of (4.8), we have that Similarly, the derivation for (4.7) implies that and so (4.8) is proved, too. Thus, in probability. Moreover, These relations imply (4.4).

Proof of (4.5).
For notice that the triangular array V n,j , n = 1, 2, . . . , j = 1, . . . , n is (row-wise) exchangeable, for which there is a classical central limit theorem: (4.18) follows from The expression on the right-hand side converges to zero. To show this, fix an arbitrary > 0 and choose a decomposition m = m * + m * * such that m * is Lipschitz continuous with bounded support and E[m * * (X) 2 ] < . Then it suffices to show the limit relation for m * . But this follows from the fact that diam(A n (X 1 )) → 0 in probability (Devroye,Györfi,Lugosi,and Walk [8,Section 5]). Lemma 4.2 implies that verifying (4.16). One may check (4.17) similarly to (4.3). Indeed, put Thus, by Lemma 4.1, we obtain (4.17).

Proof of Theorem 2.3
As we mentioned in the proof (4.4), for given D n , S n is an average of i.i.d. random variables bounded by L 2 . Therefore, by the Hoeffding inequality, one has For the term V n , apply the extension of the Efron-Stein inequality for the centered higher moments, which is a slight modification of Theorem 15.5 in Boucheron et al. [4]: with a universal constant c < 5.1.