Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
The 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.
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:
- 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. 
- 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 .
- 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.



limitations_and_societal_impact: No.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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$.
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.
  
As 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.

In 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.

You write that "Despite the superficial resemblance, the wiNN and Hilbert Kernel estimators have quite different convergence rates,..." but do not discuss it.

In 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.

Not clear why the growth conditions are chosen as they are and how they relate to other standard tail conditions in the regression literature.

In line 176, I believe the expectation should be on $E_X$ and not $E_{X|x_i}$.

I couldn't understand how the equality in line 194 follows.

It 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.

In 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.

In line 280, $C^\sigma$ should be $C^\rho$.

In 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?
 
Anyway, given the estimator statistical performance, one might conclude that using this estimator is a bad choice.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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.
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.

The 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.
limitations_and_societal_impact: No special limitations are observed.

Societal impact: better understanding of the Hilbert kernel-based interpolation algorithm.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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.

**Main Comments:**

1. 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.

2. 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$.

3. 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:
a. 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?
a. 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?

4. 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?

**Minor Comments:**
1. 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.
2. Typo on Line 48: "A key observations" -> "A key observation"
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_title: null

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