Parameter-free Statistically Consistent Interpolation: Dimension-independent Convergence Rates for Hilbert kernel regression
Authors: Partha P Mitra
Clément Sire
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Statistically Consistent Interpolation
Hilbert kernel regression
Risk bounds

Abstract: Previously, statistical textbook wisdom has held that interpolation of noisy training data will lead to poor generalization. However, recent work has shown that this is not true and that good generalization can be obtained with function fits that interpolate training data. This could explain why overparameterized deep nets with zero or small training error do not necessarily overfit and could generalize well. Data interpolation schemes have been exhibited that are provably Bayes optimal in the large sample limit and achieve the theoretical lower bounds for excess risk (Statistically Consistent Interpolation) in any dimension. These interpolation schemes are non-parametric Nadaraya-Watson style estimators with singular kernels, which exhibit statistical consistency in any data dimension for large sample sizes. The recently proposed weighted interpolating nearest neighbors scheme (wiNN) is in this class, as is the previously studied Hilbert kernel interpolation scheme. In the Hilbert scheme, the regression function estimator for a set of labelled data pairs, $(x_i,y_i)\in \mathbb{R}^d\times\mathbb{R},~i=0,...,n$, has the form $\hat{f}(x)=\sum_i y_i w_i(x)$, where $w_i(x)= \|x-x_i\|^{-d}/\sum_j \|x-x_j\|^{-d}$. This interpolating function estimator is unique in being entirely free of parameters and does not require bandwidth selection. While statistical consistency was previously proven for this scheme, the precise convergence rates for the finite sample risk were not established. Here, we carry out a comprehensive study of the asymptotic finite sample behavior of the Hilbert kernel regression scheme and prove a number of relevant theorems. We prove under broad conditions that the excess risk of the Hilbert regression estimator is asymptotically equivalent pointwise to $\sigma^2(x)/\ln(n)$ where $\sigma^2(x)$ is the noise variance. We also show that the excess risk of the plugin classifier is upper bounded by $2|f(x)-1/2|^{1-\alpha}\,(1+\varepsilon)^\alpha \sigma^\alpha(x)(\ln(n))^{-\frac{\alpha}{2}}$, for any $0<\alpha<1$, where $f$ is the regression function $x\mapsto\mathbb{E}[y|x]$. Our proofs proceed by deriving asymptotic equivalents of the moments of the weight functions $w_i(x)$ for large $n$, for instance for $\beta>1$, $\mathbb{E}[w_i^{\beta}(x)]\sim_{n\rightarrow \infty}((\beta-1)n\ln(n))^{-1}$.  We further derive an asymptotic equivalent for the Lagrange function and explicitly exhibit the nontrivial extrapolation properties of this estimator. Notably, the convergence rates are independent of data dimension and the excess risk is dominated by the noise variance. The bias term, for which we also give precise asymptotic estimates, is always subleading when the density of data at the considered point is strictly positive. If this local density is zero, we show that the bias term does not vanish in the limit of a large data set and we compute its limit explicitly. Finally, we  present heuristic arguments and numerical evidence for a universal $w^{-2}$ power-law behavior of the probability density of the weights in the large $n$ limit.


Parameter-free Statistically Consistent Interpolation: Dimension-indeeenden Convergence Rates for Hilbert kernel regression
Anonymous Author(s)
Affiliation
Address email
Abstract
Previously, statistical textbook wisdom has held that interpolation noisy training data will lead to poor generalization. However, recent work has shown that this is not true and that good generalization can be obtained with function fits that interpolate training data. This could explain why overparameterized deep nets with zero or small training error do not necessarily overfit and could generalize well. Data interpolation schemes have been exhibited that provably Bayes optimal in the large sample limit and achieve the theoretical lower bounds for excess risk (Sta- tistically Consistent Interpolation) in any dimension. These interpolation schemes are non- non-parametric Nadaraya- Watson style estimators with singular kernels, which exhibit statistical consistency in any data dimension for large sample sizes. The recently proposed weighted interpolating nearest neighbors scheme (wiNN) is this class, is the previously studied Hilbert kernel interpolation scheme. In the Hilbert scheme, the regression function estimator for set of labelled data pairs, (z,, y:) E R R. i O..... n. has the form f(z) Σi w,,;()) where (;(x) = - 2. unique in being entirely free of parameters and does not require bandwidth se- lection. While statistical consistency was previously proven for this scheme, the precise convergence rates for the finite sample risk were not established. Here, we carry out comprehensive study of the asymptotic finite sample behavior of the Hilbert kernel regression scheme and prove a number of relevant theorems. We prove under broad conditions that the excess risk of the Hilbert regression estimator is asymptotically equivalent pointwise to o² (x:) In(n) where (²(x) is the noise variance. We also show that the excess risk of the plugin classifier upper bounded by fx)(x) 1/2 x (1 + 2) o (z)(Inn)) (m)) 2 for any 0 < 1, where f is the regression function x + Elyle zz]. Our proofs proceed by deriving asymptotic equivalents of the moments of the weight functions wx(x) for large for instance
3
5
11
13
14
||. 2, This interpolating function estimator is
15
18
17
18
19
20
21
23
25
for 1, E u (æ)] ~n+ ((3 1)m In(n)) We further derive an asymptotic equivalent for the Lagrange function and explicitly exhibit the nontrivial extrapola- tion properties of this estimator. Notably, the convergence rates are independent of data dimension and the excess risk is dominated by the noise variance. The bias term, for which we also give precise asymptotic estimates, is always subleading when the density of data at the considered point is strictly positive. If this local density zero, we show that the bias term does not vanish the limit of large data set and compute its limit explicitly. Finally, we present heuristic arguments for universal -" pawer-law behavior of the probability density of the weights in the large limit.
27
28
29
30
31
32
33
34
35
Submitted to Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

Introduction
37
38
Data interpolation and statistical regression of noisy data are both classical subjects but their domain of application have been disjoint until recently. Scattered data interpolation techniques [ are generally used for clean data. On the other hand, when supervised learning or statistical regression techniques are applied to noisy data, in general smoothing or regularization methods are applied to prevent training data interpolation, as the latter is believed to lead to poor generalization (2). However, accumulating empirical evidence from overparametcrized deep networks has shown that data interpolation (equivalently, zero error on the training set) does not automatically imply poor generalization 3 []. This has in turn given rise to a rapidly growing body of theoretical work to
39
40
41
43
44
45
understand how and why noisy data interpolation can still lead to good generalization [5
g 9
47
10
14 15
48
A key observations in this regard is the phenomenon of Statistically Consistent Interpolation [16]. i.e. regression function estimation that interpolates training data but also generalizes as well as possible by achieving the Bayes limit for expected generalization error (risk) when the sample size
49
50
51 becomes large. This hints at rich set of theoretical questions the interface between the disciplines of scattered data interpolation and supervised learning, that have only begun to be addressed. In
53 particular, there has been comparatively little study of the generalization error or risk of interpolating
54 learners. Computation of generalization error bounds in machine learning often relies on the capacity
55 of the class of fitting functions [17, however such model complexity based bounds are not tight enough to be useful for interpolating learners 4 For nonparametric interpolation approaches such as that considered here, it is also not clear what model complexity means. Thus, there is a need for other 58 approaches to understanding the generalization behavior of nonparametric interpolating learners, including more direct treatments of the generalization error for specific interpolation schemes so as to gain better theoretical understanding. The current paper addresses this need.
57
59
60
61 We present a detailed analysis of the finite-sample risk of an interpolating learner with intriguing theoretical properties, the Hilbert kernel estimator (Devroye et. al. (88). A unique property of this Nadaraya-Watte Watson (NW) style estimator [19 20 is that it is fully parameter- free and does not have any bandwidth or scale parameter. It is global and uses all data points for each estimate: the associated kernel is a power law and thus scale-free. Although statistical consistency of this estimator was proven [18] when it was proposed, there has been systematic amalysis of the associated convergence rates and asymptotic finite sample behavior. We provide this analysis in the present study.
63
64
65
67
68
69
Related work The only other interpolation scheme we are aware of, that proven to be statistically consistent in arbitrary dimensions under general conditions, is the recently proposed weighted interpolating nearest neighbors method (wiNN) (7]. which is also a NW estimator utilizing a singular power law kernel of a very similar form but with two important differences; a finite number of neighbors & is utilized (rather than all data points), and the power law exponent of the NW kernel satisfies 0 < 5 < d/2 rather than 8 d. To achieve consistency & has to scale appropriately with sample size. Despite the superficial resemblance, the wiNN and Hilbert Kernel estimators have quite different convergence rates, as we will see from the results of this paper. Also worth mentioning is the Shepard interpolation scheme [2] originally proposed for interpolation of 2D geospatial data sets, also NW style interpolating estimator, though used in the context of scattered data interpolation.
70
71
73
74
75
77
78
79 In scattered data interpolation [. the focus is generally on the approximation error (corresponding
80
to the "bias" term in our analysis below). The approximation error of the Shepard scheme has been analyzed (22) but as we will see below the risk for Hilbert kernel interpolation is dominated by the noise "variance" term. In contrast with wiNN or Hilbert kernel interpolation, other interpolating learning methods such as simplex interpolation 7 or ridgeless kernel regression are generally not statistically consistent in fixed finite dimension
81
82
83
94
85
Summary of results of this paper Notation and assumptions pertaining to this summary are defined in the problem setup section below. We prove under broad conditions that the excess risk of the Hilbert regression estimator is asymptotically equivalent pointwise to (²x) In(n) where 2²(x) is
86
87
88
the noise variance. We also show that the excess risk of the plugin classifier is upper bounded by (x) - 1/2 1-o (1 e) (œ) (In())) 2 for any 0 < a < 1, where f is the regression function I hH HHE Ely x). Our proof's proceed by deriving asymptotic equivalents of the moments of the weight
89
90
functions (x) for large n, for instance for 3 > 1, Elu (z)) ~ ((B 1)m In( We
91
further derive an asymptotic equivalent for the Lagrange function and explicitly exhibit the nontrivial
2

---

93
extrapolation properties of this estimator. Notably, the convergence rates are independent of data 94 dimension and the excess risk is dominated by the noise variance. The bias term, for which we also give precise asymptotic estimates, is always subleading when the density of data at the considered point is strictly positive. If this local density is zero, we show that the bias term does not vanish the limit of large data set and we compute its limit explicitly. Finally, we present heuristic arguments for a universal w power-law behavior of the probability density of the weights in the large n limit.
95
96
97
96
2 Problem setup
99
100
Notation, Definitions, Statistical Model We model the labelled training data set (zo, yo)..... (In, yn) as n + iid. observations of a random vector (X, with values in Rd R for regression, and with values in R x {0, 1} for binary classification. Due to the indepen- dence property, the collection No.... Xx, has the product density I[; p(z;). We will denote by E an expectation over the collection of n + 1 random vectors and by Ex the expectation over the col- lection Xo...., Xn. An expectation over the same collection while holding X; = zzz will be denoted defined as the conditional mean of Y given X = 2, f(z)= := E[Y X = x] and the conditional variance function is (z) == E| - f(X) = z]. minimizes the expected value of the mean squared prediction error (risk under squared loss), arg min (h) where R == [((((X) 2) Given any regression estimator f(xx) the corresponding risk can be decomposed as Rs (f(x)) = (f) + B[(((X) - f(x)²). The excess risk is given by (f) - Raq(f) = [I(f(X) - f(x)) For a consistent estimator this excess risk goes to zero as n + oo and we are interested in characterizing the rate at which it goes to zero with increasing n (note our sample size is n + for notational simplicity but for large n this
101
102
103
104
105
jx, The regression function/ ʃ: Rd -
106
107
108
109
110
111
112
113
114
does not change the rate).
F: Rd + {0,1) In the case of binary classification, E {0, 1) and f() = = 1 1| x
115
116
denote the Bayes optimal classifier, defined by F(x) = (z)())) (1) 1/2) where 0(-) is the Heaviside theta function. This classifier minimizes the risk Ro/1 (h) == Bi1 [x()++r]] (()(() + Y) under
117
zero-one loss. Given the regression estimator f. we consider the plugin classifier =((=)(((===))))))))0 0(f(x)
118
The classification risk for the plugin classifier f is bounded as B[Ra/1 - Ro
119
fz) - fx))] = 2 ((((((())))))) f()))) f(
120
121
Finally, we define two sequences an 6n > O, n E N, to be asymptotically equivalent for n + toc, denoted an ~o 6,, if the limit of their ratio exists and lim an/b, = 1.
122
In summary, our work will focus on the estimation of asymptotic equivalents for B[(((x) (xx)) and other relevant quantities as this determines the rate at which the excess risk goes to zero for regression, and bounds the rate at which the excess risk goes to zero for classification.
123
124
125
126
We define the support 52 of the density P as Ω {ar E /p(x)) > 0}, the closed support f2 as the closure of Ω and f22 as the interior of f2. Our results will not assume any compactness condition on Q or 2 The boundary of ②2 is then defined as an Ω \ f2. We assume that p has a finite variance o. In addition, we will most of the time assume that the density p is continuous at the considered point æ E 22,, and some cases, x E 00 nt.
Assumptions.
127
128
130
131
For the regression function f. we will obtain results assuming either of the following conditions
Comn f is continuous at the considered x;
132
cf Holdge: for all E S2, there exist a, > 0. K2 > 0, and 6, > 0, such that I' E Q and ||æ - z'Il < & = 1f(x) f(x') ) < K2 || - x' 2'11"=
133
134
(local Hölder smoothness condition),
where condition Chooderr is obviously stronger than C In addition, we will always assume growth condition for the regression function f:
136
137
(2( Croweeki (()) 14 d'y < co.
138
.
3

---

139
As for the variance function o, we will obtain results assuming either that or is bounded or satisfies a growth condition similar to the one above
140
-ound there exists of 2 O, such that, for all x E Ω we have o²(x) S o d²(y) Groweh f p(U) 1+Ily| y < 00.
141
.
142
143
When we will assume condition C Growth (obviously satisfied when o² is bounded), we will also assume continuity condition C for a at the considered x.
145
Note that all our results can be readily extended in the case where x E an = S2 \ 52 but keeping the condition p(x) 0 (i.e., x a2 n 92), and assuming the continuity
148
æ of p as seen as function restricted to Ωt i.e., limygst-az p(y) - p(z). Useful examples are when the support S of
147
148
p is d-dimensional sphere hypercube and is on the surface of l (but still with p(x;) > 0). To
149
guarantee these results for E a52 S2 we need also to assume the continuity at x of f. and assume
150
that Q is smooth enough near x, so that there exists a strictly positive local solid angle we defined by
Wx = lim r-0 Vaplz)rd / I-- p(y) d'y ply)dd
lim r Vard JEER/Ie--lls>>
d'y,
(1)
where Va2 = Sa/d x /d/////////////////////// + 11) is the volume of the unit ball in d dimensions, and the second inequality results from the continuity of at If E Ω", we have = 1, while for E an, we sphere or on the interior of a face of a
151
153
have 0 S Wg I 1. For instance, if x is on the surface hypercube (and in general, when the boundary near is locally an hyperplane), we have wr = 2.2 If x a corner of a hypercube, we have Wa 2 From our methods of proof presented in the appendix, it should be clear that all our results for x E Ω2 perfectly generalize to any x E 82 n S2 for which by simply replacing Va whenever it appears in our different results by wy Va.
155
156
157
Wa
158
Hilbert kernel interpolating estimator and Bias- Variance decomposition. The Hilbert kernel regression estimator (x) is a Nadaraya- Watson style estimator employing a singular kemnl::
159
| xz
wx(x) =
(2)
>
j ||
xz -
f(x) = Σ wy (2)))
(3)
160
The weights wx(x) are also called Lagrange functions the interpolation literature and satisfy the
161
interpolation property (x;3)) diz. where 6y = 1, if = j. and otherwise. At any given point
162
x, they provide a partition of unity so that Ei= w; (xx = 1. The mean squared error between the
163
Hilbert estimator and the true regression function has bias-variance decomposition (using the i.i.d
184
condition and the carlier definitions)
f(x) - f(x) Σ
mn( f(+)] + Σ (.(xl) f(x,)).
(4)
1=0
1=0
B[(((z) - f(x))1 = B(x) + V(z),
(5)
9.
(Bias) B(x) = Ex
wi
(6)
(V (Variance) V(x) =
E
(x( f(x))) = -Ex Σ w (z)
(7)
185
The present work derives asymptotic behaviors and bounds for the regression and classification risk of the Hilbert estimator for large sample size n. These results are derived by analyzing the large behaviors of the bias and variance terms, which turn depend on the behavior of the moments the weights or the Lagrange functions wz(xr). For all these quantities, asymptotically equivalent forms are derived. The proofs exploit a simple integral form of the weight function and details are provided in the appendix, while the body of the paper provides the results and associated discussions.
186
167
189

---

3
Results
172
3.1
The weights, variance and bias terms
173
3.1.1
Moments of the weights: large behavior
174
In this section, we consider the moments and the distribution of the weights we (x) at a given point æ.
175
The first moment is simple compute. Since the weights sum to 1 and X, are i.i.d, it follows that
178
Ex [x)))) are all equal and thus E [x)] = (n + 1)- The other moments are much less trivial to compute and we prove the following theorem in the appendix A.2
177
Theorem 3.1. For E SP (so that p(z) 0), we assume p continuous at æ. Then, the moments of the weight wo(x) satisfy the following properties:
179
180
For B 1:
E
w wg(x) (x))
1
(8)
t (3 - In()n
For 0 < < 1: defining kg(x)) ==
platu)
d < oc, we have Mulln
kg(l)
wo (v))
(9)
+ (Vap(æ)) In()))
For B < O: all moments for B -1 are infinite, and the moments of order -1 < satisfy
183
E
[
51+ x1+
(10)
so that sufficient condition for its existence is kz(l)) = f p(x + y)ll [āld d'y < co.
184
185
Heuristically, the behavior of these moments are consistent with the random variable W wo (z)
having probability distribution satisfying scaling relation P(W) W. function p having the universal tail (i.e., independent of and p). p(w) expected vanish with n, when +00. With this assumption, w-+00 imposing the exact condition B[W] = 1/(n + 1) 1/n:
P
W W..
with the scaling
and scale Wr
determine the scale W,, by
189
1
W
E[
p
W WdW-
Wn, =W, Wn, Wn(nn
p(w)w dw
(11)
Wa
Jo
W
Wn
dw
W,
(12)
w
190
leading to Wn, a [nn)
Then, the moment of order 3 > 1 given by
W W
W dw ~ Wn ['' w dW
E[W* 8
(13)
W Jo
n- (3 - Inn)
which indeed coincides with the first result of Theorem 3.1 that in the case 0 < B < 1, we have
Our heuristic argument also suggests
192
1 Wn
W W
Jo (w) w du (n (n)))
W
8
dw
(14)
193
where the last integral converges since p(w) u w0++
w- and B < 1. This result is perfectly consistent
with Eq. (9 in Theorem 3.1 and suggests that fo f (w) 8 dw = [Vap(a)s Interestingly, for
<x(x))
194
195
0 < B < I, and contrary to the case H > 1, we find that the large n equivalent of the moment is not
196
universal and depends explicitly on æ and the density p. As for moments of order -1 < O, we
conjecture that they are still given by Eq. (9) (and equivalently, by Eq. (14) provided they exist, and that the sufficient condition for their existence (x) < co hence also necessary, since K, k,,(2)) also
198
appears in Eq. (9) The fact that moments for 3 -1 do not exist strongly suggests that p(0) > 0.
5

---

200 In fact. Eq. (14) also suggests that all moments for -1 < 8 < 0 exist if and only if < p(0) < oc. In the Fig. 2 of the appendix, we present numerical simulations confirming our scaling ansatz, the w and the quantitative prediction for W..
201
fact that p w)
+00
203
It is shown in Devroye et al. [18] that the Hilbert kernel regression estimate does not converge almost surely (a.s.) by giving a specific example. Insight can be gained into this lack of almost sure
204
205
convergence by considering the weight function wo(x), for a sequence of independent training sample
208
sets of increasing size + 1. Let the corresponding sequence weights be denoted as w/ [0, 1].
207
From Theorem 3.1 it is clear that wn, converges to zero in probability, since the following Chebyshev
208
bound holds (analogous to the bound on the regression risk):
1+8
P( > E) e2n1n(n)
(15)
209
for arbitrary& E 0 and 5 >> 0, and for n larger than some constant N2,5- Alternatively, one can exploit the fact that E[wn]] = x+I leading to P(w,, > >) S 2/1 which is less stringent than Eq. 15
210
211
as far as the n-dependence concerned, but is more stringent for the e-dependence of the bounds.
Let us show heuristically that does not converge a.s. to zero. Consider the infinite sequence of 213
events &, {w, > s}, n E N, and the corresponding infinite sum Σn, P(E,) = En. P(wn, > e). Exploiting our previous heuristic argument for the scaling form of the distribution of weights, we obtain
215
[
1
W Wn
o In dw
1-E
P(wn >
W.
P
dW
en In())))
(16)
Jenln
216
2 n In(n) In(In([V) is divergent series, a Borel-Cantelli argument suggests that an infinite number of the events En (i.e., wi > E) must occur, which implies that wi, does not converge
Since En=
217
a.s. to O. Note that the weights are equal to 1 at the data points due to the interpolation condition, so that large weights occasionally occur, causing the lack a.s. convergence.
219
220
3.1.2
Lagrange function: scaling limit
221
The expected value of the Lagrange functions wy (x) have a simple form in the large n limit. Due to the i..dd condition the indices are exchangeable and we set i 0 for the computation of the
222
223
expected Lagrange function [z) = Ex mo [wo(z)]. Thus, one of the sample points (denoted z0) is held fixed and the other ones are averaged over in computing the expected Lagrange function. For
224
225
To o x kept fixed, we have lim Lu(z) = O. However, we show in the appendix A.3 that La (x()) takes a very simple form when taking specific scaling limit:
226
227
Theorem 3.2. For I E Ω2", we assume continuous at x. Then, in the limit (denoted by limz). n +
+00, ||- | + +00 (i.e., xy > x), and such that 2, (n, za) = Vap(=)]l No In log(n) - Z.
228
229
the Lagrange function Lo(z)= = E x [w)(r)] converges to proper limit,
lim Lo(x) (z) %
(17)
+ Z
The proof of this theorem shows that the relative error between Lo(x)) and 1 for finite but large n I+z and large || --.1-d such that zz (n,, zo) remains close to Z, is O(1/ In(n)).
230
231
Exploiting Theorem 3.2] we use simple heuristic argument estimate the tail of the distribution of the random variable W = wo(x). Indeed, approximating Lo(x) for finite but large n by its
233
asymptotic form [n,o01 with z (n, mo) = Vap(z)) log(n)]l || no 1 we obtain
234
S"' P(W') dw"
/ pl0o)o
1+ Vap(z))noogn))) - rolld W
dd d2
(18)
(1+ log(z)) W)) du,
Vap(x)
0
(19)
P(W) In())
(20)
n In(n)W
235 where 0(.) is the Heaviside function. This heuristic result is again perfectly consistent with our guess with the scaling function p having the universal 236 of the previous section that P(W) = W.P W.

---

237 tail, p(w) ~
w=
and a scale Wn, xin(n)
1
Indeed, in this case and in the limit - +oo, we
w-+00
obtain that P(W)
W
W W
nln(s)W2 which is identical to the result of Eq. (00)
3.1.3
The variance term
simple application of the result of Theorem 3.1 for B = 2 (see appendix A.4
allows bound
the variance term (xx) E Ei= wf (2) [u - [(])]] for bounded variance function o²:
242
Theorem 3.3. For 92, p continuous at x, o² S of for any E >> 0, there exists constant
N such that for 2 Ne we have
V(x) - (1 E)
(21)
In(n)
244
Relaxing the boundedness condition for but assuming the continuity of o² at along with a growth condition, allows us to obtain a precise asymptotic equivalent of V(z), when n + +00:
245
246
Theorem 3.4. For 22, (x)) > 0, pa? continuous at x, and assuming the condition C
Crowth
d²( Le., J p(y) 1+ +lyll 2a d'y oo, have
(a) In(n)
V(z)
(22)
+00
Note that if the mean variance / (())o²()) d'y < oc, which is in particular the case when o² is bounded over Q then the condition C Growth is in fact automatically satisfied.
249
250
3.1.4
The bias term
251
In appendix A.5 we prove the following three theorems for the bias term
252
Theorem 3.5. F St (so that p(x) > 0), we assume that p is continuous at x, and the conditions
flg) Crowwen' p(y(y) 1+llul dd < xc.
253
Chosttee there exist 02 > 0, K2 0, and 8, > 0, such that
255
x' E 52 and ||x - 2'|| < 6n = 1f(x) f(x') & K₂ || x 1
(local Hölder condition for f).
Moreover, we define tι(z)= = p(x + y) [(ott)-f(()) d' where we have [x(x)] < oc. llvl
257
Then, for n(()) # 0, the bias term B(x) = Ex (E w. ((<)))]
258
satisfies
B(x)
E [(0))
f(x))
with E B[((x)] - f(x) notto In((x)
<(x))
(23)
259 In the non generic case x(x) O, we have the weaker resuli
o 29 (In(n))- 20x
for d > 20x
B(x) =
O (n-((()n))--1)
for d = -0
(24)
0 (n (1-2m)(()))-
for d < 20x
280 Note that <<x)) = 0 non generic but can still happen, even if f is not constant, For instance, if is a
251 sphere centered at or Rdd if p(x+ - y) = م ((] is isotropic around æ, and fa y +> f(x (x++)) an odd function of y, then indeed have x<xz) at this symmetric point x.

---

263
Interestingly, for x(x) * 0, Eq. 23 shows that the bias (xx) is asymptotically dominated by the square of E [(x) - f(x)), showing that the fluctuations of EE' [(x) - o wa)) are
264
negligible compared to E [(x)] - f(r), in the limit - too and for x(x) + 0.
285
266
One can relax the local Hölder condition, but at the price of weaker estimate for (x)) which will however be enough to obtain strong results for the regression and classification risks (see below):
267
Theorem 3.6. For x E S2,, we assume p and I continuous at x, and the growth condition Cf Growth
268
p(y) Piv) d' < co. Then, the bias term satisfes 1+1ly
269
B(x) = In(n))
(25)
270
or equivalently, for any E > O, there exists N2.5, such that for n 2 No.5
B(x) S In(n)
(26)
Let now consider point x On for which we have p(x) (note that x 02 does necessarily imply p(x) = 0). In appendix A.5 we show the following theorem for the expectation 272
value of the estimator f(x) in the limit -00
Theorem 3.7. For E 00 such that p(x: = O, we assume that I and p satisfy the conditions
Crowwhh S p(y)
15(01 1+llal1a d'y < co.
275
"Holder" there exist Ozz > 0, K2 > O. and 5g > 0, such that E and || 2'|l 8,
278
(p(x') S K2 1| x 1|az
278
(local Hölder condition.for p).
Moreover, we define x(x) p(x + y) flatt)- d (1((1) co under condition Crrowth).
279
and M(x) = plztyl day (0 < M(x) oo under condition C Chooddor) Then, Tyll"
280
x(x)
lim E[f(x)] - f(x) 1(x)
(27)
+oc
281
Hence, in the generic case <(x) * 0 (see Theorem 3.5 and the discussion below it) and under condition Holldrr we find that the bias does not vanish when p(x) O, and that the estimator f(x) does not converge to (xx) When p(x) = the scarcity data near the point x indeed prevents the estimator converge to the actual value of f fzr). In [p.e we show an example of density
283
285
continuous at æ and such that p(x) = O, but not satisfying the condition Holder and for which
lim, +.00 [)x())) (xx), even if <<x)) of O.
3.2
Asymptotic equivalent for the regression risk
288 In appendix A.6 we prove the following theorem establishing the asymptotic rate at which the excess risk goes to zero with large sample size n for Hilbert kernel regression, under mild conditions that do not require f or to be bounded, but only to satisfy some growth conditions:
289
290
Theorem 3.8. For x E Ω2, we assume a (zx) > O, p. a. and f continuous at x, and the growth dw(
conditions Chrowthi f p(y) T+lly za d'y < oo and C'rowhhi' J P(y) T+ T+ d < cc.
f2
292
293
Then the following statements are true:
TThe excess regression risk the point satisfies
)²(x)
- +00 In(n))
(28)
8

---

295
The Hilbert kernel estimate converges pointwise to the regression function in probability.
296
More specifically, for any ó O, there exists constant N,.6. such that for any we have the following Chebyshev bound, valid for 2
297
NN.8
+ 8
o²
- - 2 =]
(29)
g² In(
298
This theorem is a consequence of the corresponding asymptotically equivalent forms of the variance and bias terms presented above. Note that as long p(z) >> 0, the variance term dominates over the bias term and the regression risk has the same form as the variance term.
300
301
3.3
Rates for the plugin classifier
302
In appendix A.7, we prove the following theorem establishing the asymptotic rate at which the classification risk goes zero with large sample size for Hilbert kernel regression:
303
304
Theorem 3.9, For 92, we assume (z)) p. a, and continuous at æ. Then, the classification
risk [( - Ro/1( (F(x)) vanishes for n + t00.
305
306
More precisely, for any 0, there exists No.e, such that for any 2 Nz.e,
(x)
s ( Ro/1(F(x)) - 2(1
(30)
Vn(n)
307
In addition, for any 0 < a < 1, the general inequality
E| (x))] - (F(()) S 2z) - 1/2 E [f(z) f(x))
(31)
308
holds unconditionally and, for n 2 N2,5, leads to
o" (x)
< [[ - Ro/ (4 S 1 (1++) =)
(32)
(In(n))
309
For 0 < < 1, Eq. 32 is weaker than Eq. 30 in terms of its dependence on but explicitly
310 shows that the classification risk vanishes for f(x) 1/2. This theorem does not require any growth
condition for f or since both functions takes values in [0, 1] in the classification context.
312
3.4
Extrapolation behavior outside the support of
We now take the point outside the closed support Ω of the distribution (which excludes the case
314 Ω Rd). We are interested in the behavior of [(x) as + +oo. In appendix A.8 we prove:
Theorem 3.10. For & Ωt assume the growth condition f p(y) 1+1l8T d'y
[f(y
Then,
(x) = lim TE [[(x)] = J p(y) vll d' n--
(33)
I P(y)] x ull dd
316 and for is continuous at all $ 5t
317 In addition, if (()) d'y oc, and defining d(x, Ω) the distance between æ and Ω we
318 have
lim foo(x) ff plu)f(s)d' d'y. +00000)+++00
(34)
319
Finally, we consider 2o E a such that p(xn) > (Le, To E an n S2), and assume that f and p seen as functions restricted to S2 continuous at Fo. i.e. limygst-ro ply) p(2o) and lim f(y) = f(z0). We also assume that the local solid angle wo = lim Vapizo)e [ p(y) d'y exists and satisfies wp > O. Then,
321
322
lim fo) = f(xo).
(35)
=gfl+zag
323
Eq. 34 shows that far away from Ω (which is possible to realize, for instance, when Ω is bounded),
324 f rr) goes smoothly to the p-mean of f. Moreover, Eq. 35) establishes a continuity property for
the extrapolation for at E 82 n Ω under the stated conditions (remember that for x E Ω we
325
326 have limn E [(x>] = [xx); see Theorem 3.5 and in particular Eq. (23).

---

References
327
328
[1] Holger Wendland. Scattered data approximation, volume 17. Cambridge university press, 2004.
329
[2] Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An introduction to statistical learning, volume 112. Springer, 2013.
330
331
[3] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
332
333
334
[4] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In Proceedings of the 35th International Conference Machine Learning, pages 541-549, 2018.
336
337
[5] Adele Cutler and Guohua Zhao. Pert-perfect random tree ensembles. Computing Science and Statistics, 33:490 49700-997440000 2001.
[6] Abraham J Wyner, Matthew Olson, Justin Bleich, and David Mease. Explaining the success of adaboost and random forests as interpolating classifiers. Journal of Machine Learning Research, 18(48):1-33, 2017.
340
341
342
[7] Mikhail Belkin, Daniel Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. arXiv preprint arXiv:1806.055 2018.
343
8 Alexander Rakhlin and Xiyu Zhai. Consistency of interpolation with laplace kernels is high-dimensional phenomenon. arXiv preprini arXiv: 18.:./ 1166, 2018.
345
346
99] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint 1rXiv:1910.01635, 2019.
348
349
[10] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849-15583
350
351
2019.
352
[11] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel" ridgeless" regression can generalize. arXiv preprint arXiv: 00387, 2018.
353
354
[12] Peter I. Bartlett, Philip Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitring in linear regression. arXiv preprint 19Xxv:1906.11000 2019.
[13] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max- max-margin linear classifiers: high-dimmnsional asymptotics in the overparametrized regime. arXiv preprini arXiv: 1.4554444 2019.
357
358
359
[14] Mina Karzand and Robert D Nowak. Active learning in the overparameterized and interpolating regime. arXiv preprint arXiv: 12782, 2019.
380
[15] Yue Xing, Qifan Song, and Guang Cheng. Statistical optimality of interpolated nearest neighbor algorithms. arXiv preprint 181000284, 2018.
362
363
[16] Partha P. Mitra. Fitting elephants in modern machine learning by statistically consistent
interpolation. Nature Machine Intelligence, 3(5):378-386 May 2021.
[17] Martin Anthony and Peter L Bartlett. Neural Nenwork Learning: Theoretical Foundations. Cambridge University Press, 1999.
366
387
[18] Luc Devroye, Laszlo Györfi, and Adam Krzyžak. The hilbert kernel regression estimate. Journal of Multivariate Analysis, 65(2):209-227, 1998.
368
369
[19] Elizbar A Nadaraya. On estimating regression. Theory of Probability Its Applications, 91):141-442, 1964.
370
[20] GS Watson. Smooth regression analysis. Sankhya A: 26: 359-372, (50), 1964.
10

---

372
[21] Donald Shepard. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 1968 23rd ACM national conference, pages 517-524. ACM. 1968.
373
374
[22]
Reinhard Farwig. Rate of convergence of shepard's global interpolation formula. Mathematics of Computation, 46(174):577-590 1986.
Checklist
378
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes] Brief statement of the primary theorems are included the abstract together with verbal descriptions of the principal results.
379
(b) Did you describe the limitations of your work? [Yes] Theorems include limiting conditions.
382
(c) Did you discuss any potential negative societal impacts of your work? [No] The paper consists of theorems and proof's about the convergence rates of an interpolation scheme and it is hard to conceive any negative social impact of this mathematical exercise. anything might have positive impact by shedding theoretical light on the interpolation of noisy data in modern ML.
383
384
385
386
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? 387
[Yes] We have read the guidelines.
2. If you are including theoretical results...
380
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We state the conditions for the theorems proven.
391
382
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs of all theorems
are provided in the appendix. The relevant appendix section is noted in the corresponding sections containing the theorems.
394
395
If you ran experiments..
Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] The paper is directed to proving number of theorems.
397
399
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [N/A] We do not rely on numerical experiments for the results presented in the paper.
400
401
402
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
404
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
405
406
you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
407
(a) If your work uses existing assets, did you eite the creators? [N/A]
408
(b) Did you mention the license of the assets? [N/A]
409
(C) Did you include any new assets either the supplemental material or as a URL? [N/A]
410
(d) Did you discuss whether and how consent was obtained from people whose data you't 're
411
using/curating? [N/A]
412
Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
414
5.
If you used crowdsourcing or conducted research with human subjects...
415
(a) Did you include the full text of instructions given to participants and screenshots, if applica-
416
ble? [N/A] There are no human subjects.
417
(b) Did you describe any potential participant risks, with links to Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
420


Reviews:
[{"review_id": "_-ZiWYXXUeb", "reviewer": "Reviewer_mgwj", "summary": "This article investigates the generalization guarantees of the Nadaraya-Watson estimator. The focus was put on the study of the finite sample risk of the estimator for two learning tasks: regression and classification.\nThe contributions are theoretical: the excess risk at a point $x$ (in the interior of the domain) converges to $0$ at the rate $\\mathcal{O}(\\sigma(x)^2/\\log^{\\alpha}(n))$, where $\\sigma(x)$ is the noise variance at the point $x$, $\\alpha$ is a positive real number that depends on the learning task, and n is the number of nodes used for the interpolation. Most importantly, the convergence rate is independent of the dimension $d$. In the process, many interesting theoretical results were proven: the study of the asymptotic equivalents of the moments of the weight functions, along with a scaling limit of the associated Lagrange functions.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although the theoretical results proved in this work are very interesting for the kernel-based interpolation community, yet the exposition of the results is not typical, and I believe it is not suitable for an ML conference for the following reasons:\n- there is no discussion of the theoretical results. The rates of convergence are “slow” compared to the typical Monte-Carlo rate. I believe that this interesting dependency of the risk on $n$ deserves a discussion. \n- the technical results on the moments of the weight functions were presented before the main results (Theorem 3.8 and Theorem 3.9) that are relevant to ML community .\n- in Theorem 3.1. the asymptotic of the moments $\\mathbb{E} w_{0}(x)^\\beta$ were calculated for $\\beta \\in ]-1,+\\infty [$. Yet, it seems that only the case $\\beta =2$ is relevant for the analysis of the regression and classification risk.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "UOrgezZfUUE", "reviewer": "Reviewer_zJY4", "summary": "This paper provides an asymptotic analysis of the Hilbert kernel interpolating estimator, at a fixed covariate point $x$. First, it is noted that, since the estimator is a Nadaraya-Watson-type estimator, the bias and variance of the estimator depend primarily on the distribution of the weights $w_i(x)$. The paper thus provides a fairly precise asymptotic characterization of the moments of the weights. This characterization is then used to bound the variance (by $O(\\sigma^2(x)/\\log(n)$) and the bias (by $O(1/\\log(n)$). This also leads to a comparable bound on classification risk for a plug-in classifier based on Hilbert kernel regression.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I feel that the paper contains interesting and significantly novel results, but I found it difficult to understand the motivation and intuition behind several parts of the paper (esp. Sections 3.1.2 and 3.4, but for other sections as well). I also suggest adding more exposition regarding the overall conclusions and consequences of the results derived in the paper, even if this requires removing some of the technical content.\n\n**Main Comments:**\n\n1. The length and detail of the abstract makes it hard to efficiently understand the purpose of the paper. I suggest cutting the first few sentences (\"Previously.... generalize well\"), since these are well-understood in the context of interpolating regression, and would be better placed in the intro to the paper. I also suggest replacing the exact mathematical bounds (e.g., \"$2|f(x) − 1/2|^{1−\\alpha} (1 + \\epsilon)^\\alpha \\sigma^\\alpha(x) (ln(n))^{-\\alpha/2}$\") with higher-level descriptions, especially since some of the notation (e.g., $\\epsilon$) is not defined here.\n\n2. I couldn't understand the notation \"$Z$\" in Theorem 3.2. As far as I could tell, $$Z := V_d \\rho(x) \\lim_{n \\to \\infty} \\lim_{y \\to 0} y^d n \\log(n) = 0.$$ Thus, I couldn't understand what Theorem 3.2 was saying. More broadly, I don't know the motivation for characterizing the Lagrange function $L_0$.\n\n3. More discussion is needed regarding the convergence rates derived in this paper. The derived rates are quite different from those usually seen in nonparametric regression. Specifically, they are polynomial in $1/\\log(n)$, with exponents independent of the dimension $d$. Hence, the convergence rates are described as \"dimension-independent\", in contrast to more common rates for nonparametric regression that are polynomial in $1/n$, but with exponents decaying with $d$. Some specific questions:\na. On the practical side, a polynomial rate in $1/log(n)$ is too slow to be useful with realistic sample sizes. since the paper shows that Hilbert kernel regression converges at this rate regardless of the problem dimension, is the main conclusion of the paper that Hilbert kernel regression is impractical even in low dimensions?\na. On the theoretical side, it is interesting that a rate can be obtained independently of the problem dimension. Such a rate would have to be slower than any polynomial in $1/n$, given standard minimax lower bounds for nonparametric regression, but it is unclear whether the derived rates are optimal. Do there exist any other papers providing comparable dimension-independent upper or lower bounds?\n\n4. I don't understand the motivation for Section 3.4. Why do we care about the behavior of the estimator for values $x$ that will never be observed?\n\n**Minor Comments:**\n1. On Line 186, what is \"P(W)\"? Based on Eq. (11), it looks like P the density function of W, but this isn't clear from the text.\n2. Typo on Line 48: \"A key observations\" -> \"A key observation\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper could benefit from additional discussion of its limitations (e.g., assumptions that could be weakened or results that could be strengthened), but this is not a serious weakness. I don't foresee any negative societal impacts of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Cn4DN7xLIat", "reviewer": "Reviewer_pxdi", "summary": "This paper studies the asymptotic behavior of the Hilbert kernel-based interpolation scheme. By asymptotic analysis, limits of basis functions, bias and variance terms, and the mean of predicted functions are derived.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes to use the Hilbert kernel for interpolation, and eventually expect the obtained function to generalize. To this end, the underlying regression function is assumed Holder smooth with growth condition, and the distribution of noise is assumed to have bounded or slowly growing point-wise variance function. The proposed algorithm is parameter-free and does not need training, but it is expected to consume a lot of time for prediction.\n\nThe main technique adopted is asymptotic analysis. Some technical assumptions are made for the analysis. This paper definitely helps to better understand the Hilbert kernel interpolation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No special limitations are observed.\n\nSocietal impact: better understanding of the Hilbert kernel-based interpolation algorithm.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "5cEO7dw3JwH", "reviewer": "Reviewer_GNs9", "summary": "The paper studies convergence rates for point-wise kernel-based regression in $R^d$ with the Hilbert kernel. This kernel is parameter-free and singular, yielding an interpolator of the data. Various results are given for this estimator, in particular, it is shown that under some continuity and growth conditions on the regression function $f(x) = E[y|X=x]$ and the density $\\rho$, the excess error follows the asymptotic rate of $\\Theta(\\sigma(x)^2/ \\text{log}(n))$, where $\\sigma(x)^2$ is the variance of $y$ at $x$.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results seem thorough, rich in detail, interesting, and important, especially for the goal of better understanding the contemporary issue of interpolating vs. generalization (although here the number of samples $>>$ dimension). Unfortunately however, the paper is not well written and very hard to follow. It suffers from unclear and lacking discussions and it is written more like a technical report than a conference paper.\n  \nAs I see it, significantly more emphasize should be put on the context of the results and their connection to other results in the literature. For example, a rate of $O(\\sigma^2/\\text{log}(n))$ for the excess error is extremely slow as compared to non-interpolating methods such as $k$-NN or standard kernel methods in finite-dimensional spaces. In fact, such rates are what standard methods achieve in various infinite-dimensional spaces where one gets exponential small-ball probability; see, for example, Section 6 in the book \"Nonparametric functional data analysis\" by Ferraty & Vieu (2010) and the discussion at the end of Section 1 in \"Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces\" by Weiss & Gyorfi (2020). In some sense, this might explain why the bound you give is dimension free. It is also not clear why in Theorem 3.2 you consider the specific limit $lim_Z$, which exactly corresponds to the mentioned small-ball probability regime.\n\nIn the abstract and line 89, it is not clear what $\\epsilon$ is. Anyway, the abstract should be shortened significantly and should not simply repeat the main text.\n\nYou write that \"Despite the superficial resemblance, the wiNN and Hilbert Kernel estimators have quite different convergence rates,...\" but do not discuss it.\n\nIn the paper, the support is defined as the set of points $x$ with density $\\rho(x)>0$. This makes sense only when $\\rho$ is assumed continuous, since when $\\rho$ is not continuous this set is not well defined as $\\rho$ can be changed on a set of measure zero without any consequences. A standard definition of the support is the set of points $x$ such that any ball around $x$ with positive radius has non-zero measure. Since all your results assume continuous $\\rho$ (if I'm not mistaken), the nonstandard definition makes sense, but the such continuity assumption is not mentioned when the support $\\Omega$ is defined in Section 2. In addition, the definitions with the notation suggesting \"interior\" and \"boundary\" of $\\Omega$ are not identical to the standard definition.\n\nNot clear why the growth conditions are chosen as they are and how they relate to other standard tail conditions in the regression literature.\n\nIn line 176, I believe the expectation should be on $E_X$ and not $E_{X|x_i}$.\n\nI couldn't understand how the equality in line 194 follows.\n\nIt is not clear what is the purpose and implications of the discussion beginning in line 203 on the a.s. convergence of the weights $w_0(x)$. It is also not clear at the end whether the failure of such convergence is conjectured or a solid fact.\n\nIn Theorem 3.5, it is not readily clear if \"where we have $|\\kappa(x)| < \\infty$\" is an additional assumption or follows from the previous assumptions.\n\nIn line 280, $C^\\sigma$ should be $C^\\rho$.\n\nIn Theorem 3.7 you do not assume that $f$ is continuous. So the discussion following the theorem is not clear: the failure of convergence of $\\hat{f}(x)$ to $f(x)$ at $x$ such that $\\rho(x)=0$ can hold trivially by changing the value of $f$ at that point, without affecting the Bayes error. In addition, I couldn't fully interpret Theorem 3.7 given my comments above on the support. Do you assume condition (1) of a solid angle at $x$ in Theorem 3.7?\n \nAnyway, given the estimator statistical performance, one might conclude that using this estimator is a bad choice.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The topic of the submission is the study of nonparametric interpolation approaches in the context of supervised learning on R^d with real/binary labels. Particularly, the authors focus on the Hilbert kernel estimator (HKE, (2)-(3)), and study its L^2 risk: they show (Theorem 3.8) that the excess risk of the HKE estimator at point x is O(\sigma^2(x)/log(n)) where n denotes the sample size and \sigma^2(x) is the conditional variance function, and similar result (Theorem 3.9) holds for the classification risk of the plugin classifier.

Unfortunately, as the reviewers pointed out:
1) The submission is not written in a didactic way, it is quite hard to follow.
2) Discussion and numerical demonstration of the relevance on the established result are completely missing.

Significant revision is required.
Decision: Reject