Beyond Benign Overfitting in Nadaraya-Watson Interpolators
Authors: Daniel Barzilai
Guy Kornowski
Ohad Shamir
Venue: NeurIPS 2025 poster ()
Keywords: Benign overfitting
tempered overfitting
interpolation
generalization
Nadaraya-Watson
kernel
Primary area: theory

Abstract: In recent years, there has been much interest in understanding the generalization behavior of interpolating predictors, which overfit on noisy training data. Whereas standard analyses are concerned with whether a method is consistent or not, recent observations have shown that even inconsistent predictors can generalize well. In this work, we revisit the classic interpolating Nadaraya-Watson (NW) estimator (also known as Shepard's method), and study its generalization capabilities  through this modern viewpoint. In particular, by varying a single bandwidth-like hyperparameter, we prove the existence of multiple overfitting behaviors, ranging non-monotonically from catastrophic, through benign, to tempered.
Our results highlight how even classical interpolating methods can exhibit intricate generalization behaviors. In addition, for the purpose of tuning the hyperparameter, the results suggest that over-estimating the intrinsic dimension of the data is less harmful than under-estimating it. Numerical experiments complement our theory, demonstrating the same phenomena.

Beyond Benign Overfitting in Nadaraya-War Watson Interpolators
Daniel Barzilai
Guy Kornowski
Weizmann Institute of Science daniel. barzi lai @weizmann ac. i1
Weizmann Institute of Science guy wwy.koonoosk1@eeizaama ac
Ohad Shamir
Weizmann Institute of Science
ohad. shamir@wei zmann. ac
Abstract
In recent years, there has been much interest in understanding the generalization behavior of interpolating predictors, which overfit noisy training data. Whereas standard analyses are concerned with whether a method is consistent or not, recent observations have shown that In this work, we revisit the classic interpolating Nadaraya-Watson (NW) estima- tor (also known as Shepard's s method), and study its generalization capabilities through this modern viewpoint. In particular, by varying a single bandwidth-like hyperparameter, we prove the existence of multiple overfitting behaviors, ranging non-monee monoooootonicalyy from catastrophic, through benign, to tempered. Our results highlight how even classical interpolating methods can exhibit intricate generaliza- tion behaviors. In addition, for the purpose of tuning the hyperparameter, the results suggest that over-estimating the intrinsic dimension of the data is less harmful than under-estimating it. Numerical experiments complement our theory, demonstrating the same phenomena.
inconsistent predictors can generalize well.
Introduction
The incredible success of preemmaramttri machine learning models has spurred substantial body of work, aimed at understanding the generalization behavior of interpolating methods (which perfectly fit the training data). particular, according classical statistical analyses, interpolating inherently noisy training data can be harmful in terms of test error, due to the bias-variance tradeoff. However, contemporary interpolating methods seem defy this common wisdom [1, 2]. Therefore. a current fundamental question in statistical learning is to understand when models that perfectly fit noisy training data can still achieve strong generalization performance.
The notion of what it means to generalize well has somewhat changed over the years. Classical analysis has been mostly concerned with whether not method is consistent, meaning that asymptotically (as the training set size increases), the excess risk converges to zero. By now, several settings have been identified where even interpolating models may consistent, phenomenon known as "benign overfitting" [3-6]. However, following Mallinar et al. [7], more nuanced view of overfitting has emerged, based on the observation that not all inconsistent learning rules necessarily unsatisfactory.
In particular, it has been argued both empirically and theoretically that in many realistic settings, benign overfitting may not occur, yet interpolating methods may still overfit in a "tempered" manner, meaning that their excess risk is proportional to the Bayes error. On the other hand, in some situations
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

overfitting may indeed be "catastrophic", leading to substantial degradation in performance even in the presence of very little noise. The difference between these regimes is significant when the amount of noise in the data is relatively small, and in such a case, models that overfit in a tempered manner may still generalize relatively well, while catastrophic methods do not. These observations led to several recent works aiming at characterizing which overfitring profiles occur in different settings beyond consistency, mostly for kernel regression and shallow ReLU networks [8-14]. We note that one classical example of tempered overfitting is 1-nearest neighbor, which asymptotically achieves at most swice the Bayes error [15]. Moreover, results of a similar flavor are known for k-nearest neighbor where k > 1 (see [16]). However, unlike the interpolating predictors we study here, h-nearest neighbors do not necessarily interpolate the training data when k > 1.
With this modern nuanced approach in mind, we revisit in this work one of the earliest and most classical learning nules, namely the Nadaraya- analysis focusing on interpolating predictors, we focus on interpolating variant of the NW estimator,
(NW) estimator [17. 18]. In line with recent
for binary classification: given (possibly noisy) classification data S (x,, yt) y:) C Rd x {+1}
sampled from some continuous distribution D, and given some 3 > O, we consider the predictor
sign
m
if x E S
ha(x)=
x
1/4
x; for some x, E S.. if
The predictor in Eq. (1) has a long history in the literature and is known by many different names, such as Shepard's 's method, inverse distance weighting (IDW), the Hilbert kernel estimate, and singular kernel classification (see Section 2 for a full discussion).
Notably, for any choice of / > O. hg interpolates the training set, meaning that ha (x,) = yt- We will study the predictor's generalization in "noisy" classification tasks: we assume there exists a ground truth f Rd + { [1] (satisfying mild regularity assumptions), so that for each sampled point x, its associated label y E [+1} satisfies Pr(y = [xx x] = - p for some p E (0, 0.49). Clearly, for this distribution, no predictor can achieve expected classification error better than p 0. However, interpolating predictors achieve O training error on the training set, and thus by definition overfit. We are interested in studying the ability of these predictors to achieve low classification error with respect to the underlying distribution. Factoring out the inevitable error due to noise, we can measure this via the "clean" classification error Prx~D, (x) * f (x)), which measures how well hg captures the ground truth function f*
As our starting point, we recall that he is known to exhibit benign overfitting when B = d precisely; Theorem 1.1 (Devroye et al. [19]). Suppose Dx has a density on TR and let B = d. For any noise level p E (0, 0.49, it holds that the clean classification error of ha goes to zero as + co, i.e. hg exhibits benign overfating.
In other words, although training labels are flipped with probability p E (0, 0.49), the predictor is asymptotically consistent, and thus predicts according the ground truth f Furthermore, Devroye et al. [19] also informally argued that setting 3 a d is inconsistent in general, and therefore excess risk should be expected. Nonetheless, the behavior of the predictor hg beyond the benign/consistent setting is not known prior to this work.
In this paper, in light of the recent interest in inconsistent interpolation methods, we characterize the price of overfitting in the inconsistent regime 3 * d. What is the nature of the inconsistency for 3 # d? Is the overfitting tempered, or in fact catastrophic? As our main contribution, we answer these questions and prove the following asymmetric behavior:
Theorem 1.2 (Main results, informal). For any dimension d E N and noise level E (0,0.49), the following hold asymptotically as oC:
("Tempered"' overfitting) For any 3 > d, the clean classification error of hi is between ((poly(p)) and Ö(p).
("Catastrophic" overfitting) For any 3 < d. there is some f for which he will suffer constant clean classification error, independently of p.
We summarize the overfitting profile that unfolds in Figure 1, with an illustration of the Nadaraya- Watson interpolator in one dimension. These results provide a modern analysis of a classical learning

---

rule, uncovering a range of generalization behaviors: By varying a single hyperparameter, these behaviors range non- monotonically from catastrophic to tempered overfitting, with a delicate sliver of benign overfitting behavior in between. Our results highlight how intricate generalization behaviors, including the full range from benign to catastrophic overfitting can appear in simple and well-known interpolating learning rules. To the best of our knowledge, for kernel interpolators, there is no other example a single kernel provably exhibiting all three types of overfitting as we do here (even with varying bandwidth).
Moreover, the results provide an interesting insight about the optimal tuning of 3: Although Theo- rem 1.1 might seem to suggest that the optimal value of / is simply the input dimension d, it does not cover the common case where the data has some intrinsic dimension dmt (due the requirement that xx has a density on RR). In that situation, our analysis suggests that the optimal value for /8 is in fact dint. not d. Unfortunately, dine is generally not known, and can only be estimated. In that case, our results suggest that setting 3 to an over-estimate of dint (namely, choosing some B > dim)) much preferable to estimmanng it, as the former leads tempered overfitting, whereas the latter may lead to catastrophic overfitting. We further discuss this in Remark 5.2, and in Section 6 we present numerical evidence supporting this claim.
benign
catastrophic
tempered
d
B
(a)
Bid (Catastrophic)
8-d (Benign)
B d (Tempered)
Predicer hy00 o
(b)
Figure I: (a): Illustration of the entire overfitting profile of the NW interpolator given by Eq. (1). (b): Toy illustration of the NW interpolator in dimension d = with noisy data, (Left) Catastrophic overfitting for 3 < d: the prediction at each point is influenced too heavily by far-away points, and therefore the predictor does not capture the general structure of the ground truth function f*. (Middle) Benign overfitting for B d: asymptotically the excess risk will be Bayes-optimal. (Right) Tempered overfitting for 3 > d, the prediction at each point is influenced too heavily by nearby points, the predictor misclassifies large regions around label-fiipped points, but only around them.
The paper is structured follows. In Section present the discussed setting. In Section 4, we present our result for the tempered regime / >> d. In Section 5 present our result for the catastrophic regime 3 < d. In Section 6 we provide some illustrative experiments to complement our theoretical findings. We conclude in Section 7. All of the results in the main text include proof sketches, while full proofs appear in the appendix.
review related work. In Section 3 formally
Related work
Nadaraya- Watson kernel estimator. The Nadaraya- Watson (NW) estimator was introduced independently in the seminal works of Nadaraya [17] and Watson [18]. Later, and again independently. in the context of reconstructing smooth surfaces, Shepard [20] used a method referred as Inverse Distance Weighting (IDW), which is in fact a NW estimator with respect certain kerness leading to interpolation, identical to those we consider this work. To the best of our knowledge, Devroye et al. [19] provided the first statistical guarantees for such interpolating NW estimators (which they
3

---

called the Hilbert kernel,, showing that the predictor given by Eq. (1) with = is asymptotically consistent. For a more general discussion on so called "kemell rules", see [16, Chapter 10]. In more recent works, Belkin et al. [21] derived non-asymptotic rates showing consistency under slight variation of the kernel. Radhakrishnan et al. [22], Eilers et al. [23] showed that in certain cases, neural networks in the NTK regime behave approximately as the NW estimator, and leverage this to show consistency. Abedsoltan et al. [24] showed that interpolating NW estimators can be used in a way that enables in-context learning.
Overfitting and generalization. There a substantial body of work aimed at analyzing the generalization properties of interpolating predictors that overfit noisy training data. Many works study settings in which interpolating predictors exhibit benign overfitting, such as linear predictors [3, 25-30J, kernel methods [31, 32, 6]. and other learning rules [19, 33, 1].
On the other hand, there is also a notable line of work studying the limitations of generalization bounds in interpolating regimes [34, 2, 35]. In particular, several works showed that various kernel interpolating methods are not consistent any fixed dimension [36-38], or whenever the number of samples scales an integer-degree polynomial with the dimension [39, 40, 12, 41].
Motivated by these results and by additional empirical evidence, Mallinar et al. [7] proposed more nuanced view of interpolating predictors, coining the term tempered overfitting to refer to settings in which the asymptotic risk is strictly worse than optimal, but is still better than random guess. A well-known example is the classic --nearest-neighbo interpolating method. for which the excess risk scales linearly with the probability of label flip [15]. Several works subsequently studied settings in which tempered overfitting occurs in the context of kernel methods [11, 12, 42], and for other interpolation rules [8, 9, 43].
Finally, some works studied settings in which interpolating with kernels is in fact catastrophic, meaning that the excess error lower bounded by a constant which is independent of the noise level, leading to substantial risk even in the presence of very little noise [9. 10, 13, 14].
We note that our proof techniques differ from most known results for kernel interpolators, which typically rely on a spectral analysis. However, this often requires additional non-trivial assumptions (e.g. Gaussian universality). By contrast, our proofs are based on characterizing the "locality" of the predictor.
Varying kernel bandwidth. Several works considered generalization bounds that hold uniformly over a family of kernels, parameterized by a bandwidth parameter [36, 44, 37, 13). The bandwidth plays the same role the parameter /3 in this paper, controlling how local/global the kernel is. Specif- ically, these works showed that in fixed dimensions various kernels are asymptotically inconsistent for all bandwidths. Medvedev al. [13] showed that with large enough noise, the Gaussian kernel with any bandwidth is at least as bad as a constant predictor, which we classify as catastrophic. As far as we know, our paper provides the first known example of kernel method provably exhibiting all types of overfitting behaviors in fixed dimensions by varying the bandwidth alone.
3 Preliminaries
Notation. We use bold-faced font to denote vectors, e.g. x E Rd and denote by ||x|| the Euclidean norm. We let [ni] ;= .l.....n, Given some set A C I2 and a function f. we denote its restriction by flA : A + IR, and by Unif(A) the uniform distribution over A. We let B r) := {z ||x - z| S r) be the ball of radius r centered x. We denote by - equality in distribution. We use the standard Oig-O notation, with O-), ((-) and 22(-) hiding absolute constants that do not depend on problem parameters, and (-), 2(-) additionally hiding logarithmic factors. Given some parameter (or set of parameters) 0, we denote by (()), C,)),, (O), etc. positive constants that depend on 0.
Setting. Given some target function f .dd - {+1}, we consider classification task based on noisy training data S = (x;, y1) C Rd x (+1). such that x,,..., X,, Dx are sampled from some distribution Dx with density μt, and for each i E [m] independently. yı = f=((x) with probability 1 - p or else y (xi) with probability p E (0, 0.49). We note that while we focus

---

on fixed noise level p for simplicity, our results can also be extended to the case where p varies smoothly with x.
Given the predictor ha introduced in Eq. (I), denote the asymptotic clean classification error by"
[(h#)= lim Es (xxx-x_lhxx)) + (x)) m-
Throughout the paper we impose the following mild regularity assumptions on p and f* Assumption 3.1. We assume μ is continuous al almost every x E IRd, We also assume that for almost every x E R., there is neighborhood Bx 5 {x} such that l = fx)..
We note that the assumptions above very mild. Indeed, any density is Lebesgue integrable, whereas our assumption for μ is equivalent to being Riemann integrable. As for f*, the assumption asserts that its associated decision boundary has measure, ruling out pathological functions.
Types of overfitting. We study the asymptotic error guaranteed by ha in "minimax" sense, namely uniformly over nt: f" that satisfy Assumption 3.1. Under the described setting with noise level p E (0, 0.49), we say that:
hg exhibits benign overfitting if C(ha) O;
Else, hg exhibits tempered overfitting if L(hs) scales monotonically with pt there exists :: [0, 1011- + [0, 1] non-decreasing, continuous with (o(0) = O, so that C(ha) S <(p);
ha exhibits catastrophic overfitting if there exist some j (satisfying the regularity assumptions) such that C(h3) is lower bounded by a positive constant (independent of p).
We remark that the latter definition catastrophic overfitting slightly differs from the one of Mallinar et al. [7], which called the method catastrophic only if L(ha) = 1- Medvedev et al. [13] noted that the latter definition
result in the most trivial predictor, function that is constant outside the training set, being classified as tempered instead of catastrophic. We therefore find the formalization above more suitable, which also coincides with previous works [8, 9, 12, 13, 43).
4 Tempered overfitting
We start by presenting our main result for the 3 > d parameter regime, establishing tempered overfitting of the predictor hg
Theorem 4.1. For any d E N, any B > d, any density and target function f satisfying Assump- tion 3. and any noise level p E (0, 0.49), it holds that
C1(3/d)
polR/dy L(ha) < C2(3/d) log 373 (1/p) p.
8.20/d 3/d-1
where c(3/d)- on the ratio B/d.
and ((B/)),C2(B/) > are constants that depend only
In particular, the theorem implies that for any 3 > it holds that [(hs) Ö(p), hence in low noise regimes the error is never too large. Moreover, we note that the lower bound (of the form (polly (p)) for any d) holds for any target function satisfying mild regularity assumptions. Therefore, the tempered cost of overlitting holds not only in minimax sense, but for any instance.
Further note that since we know that
leads to benign overfitting, one should expect the lower bound in Theorem 4.1 to approach 0 as / - d Indeed, the lower bound's polynomial degree
(8.28/4 37d + oe, and thus ((8/d) 8-d+ 0.2
satisfies c(B/d)
(3/0-1)
'Technically, limit may not exist in general. In that case, our lower bounds hold for the lim inf while our upper bounds hold for the lim supm-+oo and therefore both hold for all partial limits.
TTo be precise, one needs to make sure that the constant C1 (B/d) does not blow up. which is indeed the case.
5

---

We provide below sketch of the main ideas that appear in the proof of Theorem 4.1, which is provided in Appendix B. In nutshell, the proof establishes that when / > d, the predictor hg highly local, and thus prediction at a test point is affected by flipped labels nearby, yet only by them. The proof essentially shows that in this parameter regime, h3 behaves similar to the nearest neighbor (k-NN) method for some finite k that depends on //dd (although notably, opposed to hg, k-NN does not interpolate), and has a similarly tempered generalization guarantee accordingly.
Proof sketch of Theorem 4.1. Looking at some test point R the prediction (x). Clearly, by definition in Eq. (1), the prediction depends on the random variables ||x - x:|| for i E [m]] so that closer datapoints have great affect on the prediction at x. Denote by 2(1) ((m) the labels ordered according the distance of their corresponding datapoints, namely |x x(1) S ||x- x x(2)|| S .... ||x x(m)] ||. By analyzing the distribution of distances from the sample to x, for datapoints sufficiently close to we can jointly approximate the random variables by
interested in understanding
|xx - [ 11 = (xx)(EE))) (En+t) E.)8///(i E,)a/d, where E,,..., Fm f. exp(1) are standard exponential random variables. Furthermore, datapoints which are more than some constant distance away from x can contribute at most constant, so for some m' we obtain
3/d ml
hx(x) se sign ((x)
Σ
E
Σ
V(1)
Ed)and + 0(m))
2j=1
Since EI E,] = i, apply concentration bounds for sums of exponential variables to argue
that with high probability Σj= Eg i simultaneously over all i E N, so the prediction is roughly
m
m'
hx(x)= sign (mx) 1)
V((1) 3/4
+ (m))
sign
Σ
V(()
33/4
since O(m) & (m + 1)8/d is asymptotically negligible and ((x)(m + 1)8/d
Crucially, for any 3 > d, the sum above converges, and therefore there exists a constant E (that depends only on the ratio 3/d so that the tail is smaller than the first k summands:
m
U( 23/d
29/4
k3/d-1
1374
i=
k=
Therefore, under the event that all nearby labels coincide, the prediction depends only on the & nearest neighbors, and would get that predictor returns their value. By Assumption 3.1, for sufficiently large sample size m and fixed k, for almost every x the & nearest neighbors should be labeled the (x(x)). So overall, we see that
same as x, namely f f (x(n)
Pr(ha(x) # (x)) Pr e [M] 2O # (x(()) (1 -)* S kp.
nlipped label
and similarly
Pr(ha(x) + (x)) Privic Mi + [x =
all labels flipped
The two inequalities above show the desired upper and lower bounds the prediction error.
5 Catastrophic overfitting
We now turn to present our main result for the B < parameter regime, establishing that ha can catastrophically overfit:

---

Theorem 5.1. For any d E 14 and any 0 < 3 < d. there exist a density j and target function f" satisfying Assumption 3.1, such that for some absolute constants C₁ C2 E (0, 1). and ((3dd.
of (1-3/d)= > 0, it holds for any p E (0,0.49) that
[(h²) 2 c(3.d)
The theorem states that whenever 3 < d. the error can be arbitrarily larger than the noise level, since [(ha)) = 2 ) even as p + O. Note that since the benign overfitting result for B = d holds over any distribution and target function (under the same regularity assumptions), the fact that the lower bound of Theorem 5.1 approaches 0 as 8 + d is to be expected.
Remark 5.2. Interestingly, the only role played by d in the proofs of Theorems 4.1 I and 5.1 is the fact that locally, the probability mass scales as JB(x,)) 11 = ra (for almost all x and small r > 0). Accordingly, when the data distribution is supported on a lower dimensional manifold of dimension dipt. d, the result suggests that tempered overfitting occurs whenever B > dimts and that catastrophic overfitling can occur whenever 3 < dint. Although we do not attempl to formalize it in this paper," we conjecture that in general the parameter d can be replaced by dipt in all our results. Since dint generally can only be estimated, it suggests potential practical implication: Setting B to an over-estimate of dint is less harmful than under-estimating it, as the former leads to tempered overfitting whereas the latter may lead to catastrophic overfitting. This is further supported by our experiments in Section 6.
We provide below a sketch of the main ideas of the proof, which is provided in Appendix C. Notably, the main idea behind the proof is quite different from that of Theorem 4.1. There, the analysis was highly local, i.c. for every test point x we showed that we can restrict our analysis to a small neighborhood around that point. In contrast, the reason we will obtain catastrophic overfitting for 33 < d is precisely that the predictor is too global, as we will see that for every test point x, all points x; in the training set have a non-negligible effect on hi (x). Our proof essentially shows that whenever small region of constant probability mass is surrounded by the opposite label, the predictor will mislabel it, incurring a constant error. Our construction is therefore quite generic, and we expect the same intuition to extend to many target functions f*. The full proof can be found in the appendix.
Proof sketch of Theorem 5. We will construct an explicit distribution and target function for which ha exhibits catastrophic overfitting. The distribution we consider consists of an inner ball of constant probability mass labeled 11, and an outer annulus labeled +1, as illustrated in Figure 2. Specifically, we denote == c(B, d) C²¹² (1 3/d) for some absolute constant C₁ 0 to be specified later, and consider the following density and target function:
if
|
<
(ol(
f(()) = {i)
(-1
if |x|| 5
(x(x)= =
Voll Vol(B(O)))B(0..))
if
3 E |x||
11
1
else
else
We consider test point with ||||| S 7. probability x will be misclassified as +1. This implies the desired result, since then
1. and will show that for sufficiently large m, with high
((ha) 2 Pr [|x] S +l cc
x
To that end, we decompose
171
y/
Σ
yi
Σ s:||x: 2
V/
x;
3
||x x111
||x - x;
t:[1x:ll
1 2p
1/1 1
2p ||X x;
(3)
||x x;
|| x;
8: +||xilss
x
=Ta
'This should not be difficult in principle, but the proof's would become substantially more technical when the manifold is non- non-linear.
7

---

Figure 2: Illustration of the lower bound construction used in the proof of Theorem 5.1. When B < d, the inner circle will be misclassified as +1 with high probability, inducing constant error.
where 7, crudely bounds the contribution of points in the inner circle, T2 is the expected contribution of outer points labeled 1, and T3 is perturbation term. Noting that T2 > O, our goal is to show that T3 dominates the expression above, implying that Eq. (3) is positive and thus (x 1.
Let A: := {i ||x||| < b denote the number of points inside the inner ball, and note that we can expect = [[k] = cm. To bound Ti, we express its distribution using exponential random variables in manner that is similar the proof of Theorem 4.1. Specifically, for standard exponential random
variables E Fm i.d. (1p(1), we show that with high probability
E,)a/d
TR Σ k=k+1
-T 2
Σ x||x;| 5
B/d 2(1) -id m
8/d
j3/d
(aotra) )
EE== P3))
31048 m 3/d h1-B/d
43
3/d 2(2)
(1 (1-3/d)
where (1) uses concentration bounds on the sums of exponential random variables to argue that Ej=1 E, x i, and (2) follows from showing k z em.
To show that T2 is sufficiently large, Hi ||x|||| } x (1 c)m fm with high probability obtain
the fact that |xx x; || 1 |x|| + ||x;||
5. and that
T2
Σ
1- 2p
2 (1 - 2p)
{xx : |xx
3 3
m
4
||x - x;
4
5
x
Lastly, we show that T3 is asymptotically negligible, by noting that E [3] = 0 hence T3 = o(m) with high probability by Hoeffding's inequality. Thus Eq. (3) becomes
(
(4 8
c. 43
(x(x)= = sign Σ
y/s
2 sign m
5 1 - 1-B/d
x
Overall, we see that the right-hand side above is positive as long as c = Ch (1 2)
1-8/d 5
or
equivalently Ci < J. meaning that (xx(x)= 1 even though (*(() -1.
6 Experiments
In this section, we provide numerical simulations that illustrate and complement our theoretical findings. In all experiments, we sample m datapoints according to some distribution, flip each label independently with probability p. and plot the clean test error of hg for various values 3. We ran each experiment 50 times, and plotted the average error surrounded 95% confidence interval.

---

6.1
Synthetic data
We start by discussing several experiments with synthetic data distributions.
Warm up: one dimensional data. In our first experiment, we considered data in dimension d = 1 distributed according to the construction considered in the proof of Theorem 5.1. In particular, consider
D Unif ((0,
1o
Unif (C.
f(x)= -
-
if x x0,
(4)
else
In Figure 3, on the left we plot the results for m 2000 and various values p, and on the right we fix 0.04 and vary
0.12
0.08
Test error
Noise level
Tost error
Sample size
0.00
0.1
0.06
100
0.04
0.08
0004
500
0.02
1000
0.02
2000
0.
0.5
1.5
2.5
3.0
0.0
0.5
1.0
1.5
B
Figure 3: The classification error of h2 for varying values of 8, with data in dimension d 1 given by Eq. (4). On the left, m = 2000 fixed, p varies. On the right, = 0.04 is fixed, m varies. Best viewed in color.
As seen in Figure 3, the generalization is highly asymmetric with respect to 3. For 8 < 1, the test error degrades independently of the noise level p. and quickly reaches 0.1 in all cases, illustrating that the predictor errors on the negative labels (which have 0.1 probability mass). On the other hand, for >>> 1, the test error exhibits a gradual deterioration. Moreover, we see this deterioration is controlled by the noise level p. matching our theoretical finding. The right figure illustrates all of the discussed phenomena hold similarly for moderate sample sizes, which complements our asymptotic analysis.
Spherical data. In our second experiment, we consider a similar distribution over the unit sphere 2 C R3, where the inner negatively labeled region spherical cap. In particular, consider the spherical cap defined by A x (I1, 22, 2z) $2
23 > v3/2). and
{
if x
Dx 10 (A) + :01 Unif(s?
\ A)
((()
(5)
else
In Figure 4, the left plot the results for 2000 and various values of p. and on the right fix 0.04 and vary m.
0.08
Test error
Noise laval
Tost orror
Sample size m
0.08
0.08
250
0.04
0.04
1000
0.02
2000
08
0.5
1.0
1.8
2.5
3.0
3.5
4.0
0.0
0.5 1.0
2.0
2.
3.0
3.5
B
Figure 4: The classification error of ha for varying values of B, with data on C R given by Eq. (5). On the left, m 2000 is fixed, p varies. On the right, p 0.04 fixed, m varies. Best viewed in color.
As seen in Figure 4, the same asymmetric phenomenon holds in which overly large are more forgiving than overly small B, especially in low noise regimes. The main difference between the first

---

and second experiment is that the optimal "benign" exponent in the second case is 3 = 2, matching the intrinsic dimension of the sphere, even though the data is embedded in 3-dimensional space. This agrees with our conjecture that for distributions with low intrinsic dimension dint < d, the overfitting behavior depends on dint rather than d (as discussed Remark 5.2).
In Appendix E we provide an extension of the spherical data experiment, in which the inputs are corrupted by Gaussian noise. As the noise variance increases, hence the dataset is drawn away from having low intrinsic dimension, the 3 value with minimal test error gradually increases from 2 to 3. This illustrates a robustness to input-noise which prevalent in practice, complementing an aspect that our current formal results do not cover.
6.2 Intrinsic Dimension of MNIST
Next, consider experiment in which the data consists of images of handwritten 0 and digits from the MNIST dataset. In Figure 5, on the left we plot the results with respect to the entire training m 12, 665 and various values of p, and the right fix p 0.1 and vary m.
0.175
Noise
0.30
Sample
0.2
0.25
10000
0.1
2000
Teat effor
0.05
Test afror
0.20
500
0.900
0.02
100
0.755
0.000
0.00
Figure 5: The classification error of hg for varying values of B. with respect to MNIST's 0/1 data. On the left, m is fixed to the entire train set, p varies. On the right, 0.1 is fixed, m varies. Best viewed color.
As in Figure 5, the same asymmetric phenomenon demonstrated by both our theory well as the synthetic experiments, clearly holds once more. It is interesting to note that each image in MNIST of size 28 28 784 pixels, and so the extrinsic dimension 784. Nonetheless, the optimal exponent is roughly 8 R 8 & 784, which matches an estimate of the intrinsic dimension of MNIST measured by Pope et al. [45]. Moreover, as seen the right, the asymptotic phenomenon manifests quite clearly already for small samples sizes, and only becomes more pronounced as the number of samples increases.
7 Discussion
In this work, we characterized the generalization behavior of the NW interpolator for any choice of the hyperparameter 3. Specifically, NW interpolates in tempered manner when / > d. exhibits benign overfitting when 3 = d, and overfits catastrophically when 3 < d. This substantially extends the classical analysis of this method, which only focused on consistency, In addition, it indicates that the NW interpolator is much more tolerant to over-estimating 3 opposed to under-estimating it.
Our analysis and experiments both suggest that the dependence on d arises from the assumption that the distributions considered here have density in R and that more generally over-estimating the estimaait it when setting S.
intrinsic dimension of the data preferable
Overall, our results highlight how intricate generalization behaviors, including the full range from benign through tempered catastrophic overfitting, can already appear in simple and well-known interpolating learning rules. We hope these results will further motivate revisiting other fundamental learning rules using this modern viewpoint, going beyond the classical consistency-vs.ineee -iinoosisiiinc dichotomy.
10

---

Acknowledgments and Disclosure of Funding
This research is supported in part by European Research Council (ERC) grant 754705, by the Isracli Council for Higher Education (CHE) via the Weizmann Data Science Research Center and by research grants from the Estate of Harry Schutzman and the Anita James Rosen Foundation, GK is supported by an Azrieli Foundation graduate fellowship.
References
[1] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias variance bias-variance trade-off. Proceedings of the National Academy of Sciences, 11663))115899113 15854, 2019.
[2] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3): 107-115, 2021.
[3] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117748):300033-00770 2020.
[4] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statisties, (3(3)):329-1333 2020.
[5] Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. Conference on Learning Theory, pages
PMLR, 2022.
[6] Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. Mach. Learn. Res., 24:123-1, 2023.
[7] Neil Mallinar, James Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: Toward a refined taxonomy of overfitting. Advances in Neural Information Processing Systems, 35:1 182-11929 2022.
[8] Naren Sarayu Manoj and Nathan Srebro. Interpolation learning with minimum description length. arXiv preprint arXiv:2302.07726, 2023.
[9] Guy Kornowkii, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in relu neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[10] Nirmit Joshi, Gal Vardi, and Nathan Srebro. Noisy interpolation learning with shallow univariate relu networks. In The Twelfth International Conference on Learning Representations, 2024.
[11] Yicheng Li and Qian Lin. On the asymptotic learning curves of kernel ridge regression under power-law decay. Advances in Neural Information Processing Systems, 36, 2024.
[12] Daniel Barzilai and Ohad Shamir. Generalization in kemel regression under realistic assump- tions. In Forty-first International Conference on Machine Learning, 2024.
[13] Marko Medvedev, Gal Vardi, and Nathan Srebro. Overfitting behaviour of gaussian kernel ridgeless regression: Varying bandwidth or dimensionality. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[14] Tin Sum Cheng, Aurelien Lucchi, Anastasis Kratsios, and David Belius. Characterizing overfitting in kernel ridgeless regression through the eigenspectrum. In Forty-first International Conference on Machine Learning, 2024.
[15] Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1):21-27, 1967.
[16] Lue Devroye, Láázžó Györfi, and Gábor Lugosi, probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.

---

[17] Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 91): 141-142, 1964.
[18] Geoffrey S Watson, Smooth regression analysis. Sankhyā: The Indian Journal of Statistics, Series A, pages 359-372, 1964.
[19] Luc Devroye, Laszlo Györfi, and Adam Krzyžak. The Hilbert kernel regression estimate. Journal of Multivariate Analysis, 65(2):209 2277 1998.
[20] Donald Shepard. A two-dimensional interpolation function for ireeullary-spaced data. In Proceedings of the 1968 23rd ACM national conference, pages 517-524, 1968.
[21] Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1611-1619. PMLR, 2019.
[22] Adityanarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. Wide and deep neural networks achieve consistency for classification. Proceedings of the National Academy of Sciences, 120((4)):2208779122,,, 2023.
[23] Luke Eilers, Raoul-Martin Memmesheimer, and Sven Goedeke. A generalized neural tangent kernel for surrogate gradient learning. arXiv preprini vrXiv:2405.15533 2024.
[24] Amirhesam Abedsoltan, Adityanarayanan Radhakrishnan, Jingfeng Wu, and Mikhail Belkin. Context-scallin scaling versus task-scaling in in-context learning. arXiv preprint arXiv:2410. 12783, 2024.
[25] Mikhail Belkin, Daniel Hsu, and Xu. Two models of double descent for weak features. SIAM Journal Mathematics of Data Science, 2(4):1167-11800 2020.
[26] Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform conver- gence: Generalization via derandomization with an application to interpolating predictors. In International Conference on Machine Learning, pages 7263-7272. PMLR, 2020.
[27] Frederic Koehler, Lijia Zhou, Danica J Sutherland, and Nathan Srebro. Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting, Advances in Neural Information Processing Systems, 34:20657-20668, 2021.
[28] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statisticx, 50(2):949-986, 2022.
[29] Lijia Zhou, Frederic Koehler, Danica J Sutherland, and Nathan Srebro. Optimistic rates: A unifying theory for interpolation learning and regularization in linear regression. ACM/MMS Journal of Data Science, 1, 2023.
[30] Ohad Shamir. The implicit bias of benign overfitting. Journal of Machine Learning Research, 24(113): 40, 2023.
[31] Zitong Yang, Yu Bai, and Song Mei. Exact gap between generalization error and uniform convergence in random feature models. In International Conference on Machine Learning, pages 11704-11715. PMLR, 2021.
[32] Song Mei and Andrea Montanari. The generalization error random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
[33] Mikhail Belkin, Daniel Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. Advances in neural information processing systems, 31, 2018
[34] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. International Conference on Machine Learning, pages 541-549. PMLR, 2018
12

---

[35] Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[36] Alexander Rakhlin and Xiyu Zhai. Consistency of interpolation with laplace kernels a high-dimensional phenomenon. In Conference Learning Theory, pages 2595-2623, PMLR, 2019.
[37] Daniel Beaglehole, Mikhail Belkin, and Parthe Pandit, On the inconsistency of kernel ridgeless regression in fixed dimensions. SIAM Journal on Mathematics of Data Science, 5(4):854 872, 2023.
[38] Moritz Haas, David Holzmüller, Ulrike Luxburg, and Ingo Steinwart. Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension. Advances Neural Information Processing Systems, 36, 2024.
[39] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3-84, 2022.
[40] Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington. Precise learning curves and higher-order scalings for dot-product kernel regression. Advances in Neural Information Processing Systems, 35:4558 4570, 2022.
[41] Haobo Zhang. Weihao Lu, and Qian Lin. The phase diagram of kernel interpolation in large dimensions. Biometrika, page asae057, 2024.
[42] Tin Sum Cheng, Aurelien Lucchi, Anastasis Kratsios, and David Belius. A comprehensive analysis on the learning curve in kernel ridge regression. The Thirty-eighti Annual Conference on Neural Information Processing Systems, 2024.
[43] Itamar Harel, William M Hoza, Gal Vardi, Itay Evron, Nathan Srebro, and Daniel Soudry. Provable tempered overfitting of minimal nets and typical nets. Advances in Neural Information Processing Systems, 37, 2024.
[44] Simon Buchholz. Kernll interpolation in sobolev spaces is not consistent in low dimensions. In Conference on Learning Theory, pages 3410-3440. PMLR, 2022.
[45] Phil Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning. In International Conference on Learning Representations, 2021.
[46] Lue Devroye. Nonuniform random variate generation. Handbooks in operations research and management science, 13:83-121, 2006.
[47] Galen R Shorack and Jon Wellner. Empirical processes with applications to statistics. SIAM, 2009.
[48] Elias M Stein and Rami Shakarchi. Real analysis: measure theory, integration, and Hilbert spaces. Princeton University Press, 2009.
[49] Roman Vershynin. High-ddmeensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
[50] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 1.3027, 2010.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction describe the concrete contributions of this paper, indicated throughout the rest of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: As discussed in Remark 5.2 and elsewhere in the paper, our analysis does not formally cover the case in which the distribution is supported over a lower-dimensional curved manifold. Other than that, any theoretical paper is limited by the setting it considers, and we do not believe our paper is further missing pointers to any specific limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions, theorems, lemmas and proof sketches are provided in the main text. The full proofs are provided in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We clearly discuss all of the above in Section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: The experiments described in Section 6 are very easy to reproduce based on our accurate description. We believe there is added value by sharing this code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: btttps://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips.
httpa//guuddee//eeuuubbiiiiiiiie /Cooe/oooiissseeeeee aessonoolicyyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide a complete description of the details in Section We remark that some of the variables described above are not directly relevant to the experiments in this paper (e.g., no optimizer etc.).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The figures in Section 6 include confidence intervals, as described therein. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [No]
Justification: We do not explicitly mention these, as the experiments are extremely light- weight and take most couple of minutes run locally standard computer.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https //tu/nnuripp.. wwt.rriss.cppppppppe htcp/pullcc/Bthccciiideeeeeeeedd
Answer: [Yes]
Justification:
We reviewed the NeurIPS Code of Ethics, and the research conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This work theoretical, and its goal is to advance our understanding of certain phenomenon observed the field of Machine Learning. While there are potential societal consequences Machine Learning whole, we believe none of which must be specifically highlighted here.
17

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
18

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: pottpa://ntt http:///eeuueeeeeeeeee http:pppc.cccoooeeeeeeeee/e//e// for what should or should not be described.
20

---

A Notation and order statistics
We start by introducing some notation that we will use throughout the proofs to follow. We denote X1 x X2 to abbreviate Xı (X2), X1 I X2 to abbreviate Xi ((2)) and X₁ 2 X2 to abbreviate X1 (2)))). Throughout the proofs we a : 3/d, and abbreviate hg. Given some x E supp(n) and m E N, we consider the one-dimensional random variables
W V -
where Va is the volume of the dimensional unit ball, and the randomness over x,. We let Fx be the CDF of W (which is clearly the same for all E (m]. We also let U3 ~ ([0,, I)), E [m] be standard uniform random variables, and denote by W and Ug) the ordered versions of the Wis and U,S respectively, namely
(1)
W S (3) S ... W (m)
Un) - U(2 S ... - U(m)
We will often omit the superseript/subscript where it is clear by context and the nota- tions W., W(g and F to denote W?', W and Fx respectively. Lastly, we let F-1 : [0, 1] +
[0, 1]. (t) inf F(s) 2 t) and only if w < F F- (
be the quantile function, and note that it satisfies F(w) if
Lemma A.1 (46, Theorem 2.1). For any i E [m]. x EER Id:
Note that since (W;) [m(m) are independent, the lemma above further applies to the joint distribution, and to the joint distribution of the order statisties (see e.g. 46, Example 2.3). Since we will use this often, state this separate lemma.
Lemma A.2. For any Rd: (Wi))emm) d (Fx)(U())) sem) jointly.
The behavior of U()) is best understood through the following lemma.
Lemma A.3 (47, Chapter 8, Proposition 1). Let Ei,... Em+1 be ii.d standard exponential random variables. Then
m
(U()....,
Σ
E
Fa
Ema E,
B Proof of Theorem 4.1
Throughout the proof, we will use the notation introduced in Appendix A.
Lemma B.1. For almost every x E Rd and e O, there exists 6x > O such that for any u S V 88
3x(x) a < F (v) < m(x) 4
Proof. By the Lebesgue differentiation theorem (cf. 48, Chapter 3), for almost every x E Rdd and >> 0, there exists some 8x such that
SB(x.)) p(z)dz
sup S6r
Vard
u(x)
<x((x).
In particular, for any 0 < a S Va 83 taking r
(which in particular satisfies r S 6x) we have vi7a
1/3
SBIX. u(z)dz
u(x) se((x).
u1
21

---

As result,
w²/B
F(w)= - Pr V2 ||x 2112 w)) - Pr
||x [|x-z|) z)|
V
= - u(z)dz E (1 c))((x)=/// + c))((x)w>/a
Bxxr))
The result readily follows by plugging c= and inverting.
Lemma B.2. For any N, a > and almost every x E Rd there exists a constant Ö(x, k, a) such that as long as m 2 C(x, k, a). the following holds: If the k nearest neighbors of x are all labeled the same y(1) = D(R), then h(x) = y(1) with probability at least - C1 exp(-o2k) exp(-cak!-5 over the randomness of (x))=r
Proof. Given x, let 5 8x > be the radius given by Lemma B.1, and assume without loss of generality that is sufficiently small so that f is constant over B(x, 6) (otherwise replace it by the smaller radius given by Assumption 3.1) ). Note that for all indices i such that W() I 6, it holds that
Y: independent variables (that equal (x( with probabilityy 1 - p). Furthermore, given & E N,
assume m is sufficiently large so that the nearest neighbors of x all lie in B(x, 6) with probability at least 1 exp( -k). Under this likely event, we decompose
172
IS,nB(x,6)
y1
Σ
y
Y W,
3(3
V(
34
W
W,
(U())
F-
W
W:
(o
(Wi)) 26
(IT)
(III)
We will show that whenever V(1) D(A), then with high probability (T) is the dominant term in the sum above. We start by noting that if y(1) ((k)) then (I) = M(1) Ex=
i= F (()))))
thus
((x)
m(())
m
100I = Σ
2 F-I(U())
2
E
(6)
F =1
(U))
2
2
E
Similarly,
SxnB(xx5)1
m+1
a
((T)) s (x(x)
Σ
S 24(xx
Σ k=++1
4 2μ(x)
Σ
E,
Σ i=++1
U
(Ej=
i=b+1
(2)
So the probability of (II))
1 is least the probability of the event in which To see this event is indeed likely, we apply Lemma D.1 to get
5 E,v ET
that with probability at least 1 - exp(-cak)) for all i 2 k+1:
1 E B2) I (1/2)a and
therefore under this event we get
< 8 2 1 at
8.
8
Σ 1= E E₁)aa
58.20 2
ja
(a 1)ka-1
1=1+1
The latter is smaller than 1/E7 as long Es (a- (a-1)//at-1//- which by definition, oc- 2.8t/a
curs with probability 1 exp (a-1)-/a k1-1/a]. To complete the proof, we note that [(IIT) < m is asymptotically negligible for sufficiently large m, since using Eq. (6) we see
2.81/o
8
that [ 2 μ(х)
(m/2)a = ((m) with probability at least 1 - c1 (xp(-ccm) [m+t] F.) 2F
w(x)
TE
by Lemma D.I.
Lemma B.3. Given x E RRd, let At be the event in which all of nearest neighbors (x1)) satisfy (x; (x).. Then for any fixed k. it holds for almost every x E Suрр(μ4 that limm-+oo Pr[AA] 1.
22

---

Proof. Let x E supp(u) be such that is continuous at x (which holds for a full measure set by assumption). Since μ(x) > 0, then there exists p > so that (()())))) > O, and assume p is sufficiently small so that f B(x,p) (x). Note that [xx p) has some positive probability mass which we denote by Ø JB(x.p) μ.. Under this notation, we see that
Pr[-A < Pr (x1, ................................ xm S B(x,, p)]
k] (r(Binomial(m.o) < "-3" 0.
We start by proving the upper bound. Let k: == log (1/p), and for any X E Rd, consider the event A in which x's k nearest neighbors (x()))=z satisfy f (x,) - (x) (as described in Lemma B.3). Using the law of total expectation, we have that
Proof of Theorem 4.1
Es Pr(h(xx) # (x)) Ex [L (h(x) + f (x)
Es [1 [h(x) + f (x))
Ex Es [1 (h(x) * (x)) | | Ppl441|
+ Ex Fs [1 (h(x) * (x))) -4 Pr( Pr(-A
$ Eg
[1 (h(x) + f (x)) A
+ Ex P
Note that by Lemma B.3 limm--so Prs| A 0, and therefore it remains to bound the first summand above.
To that end, we continue by temporarily fixing x. Denote by B the event in which x's k nearest neighbors are all labeled correctly (namely, their labels were not flipped), and note that Prs[
(1 - p)* 2 1 kp, hence Prs[ [Ts[ < kp. By Lemma B.2 we also know that for sufficiently large m:
(r[M(x)= + (x) S
* B S exp( c22k) + exp(-cak*-b)
Therefore,
Es|1 (h(x) * (x))
A = Pr[h(()] # f (x) A
5
= =Prlh(x) # (x)x A Bt] Pr[Ba]]
+ PPrlh(x) + (x) A -B Pr(- Pr--B
p
$ ( (exp(_ca)) + exp ( co hht -t)
1 kp
< C. log-="- (1/p) log(p)
where the last inequality follows by our assignment of k. Since this is true for any x, it is also true in expectation over x, thus completing the proof of the upper bound.
We proceed to prove the lower bound. We consider A to be the same event as before, yet now we set l: := lia
8:2
By lower bounding Eq. (7) (instead of upper bounding as before), we
obtain
Es Pr(h(xx= # (xx) 2 Ex Es[1 {h(x) # (x))
A
PF[A 3
- Ex Pri-4
5
(x)
As lim Prs Prs[AA] = and limm-+50 Prs [TA] = 0 by Lemma B.3, once again remains to bound (+).
To that end, we temporarily fix x, denote by D the event in which the labels of x's k nearest neighbors were are all flipped. Note that since the label flips are independent of the location of the datapoints, it holds that Prş D A&] = Prs D = p². By Lemma B.2 we also know that for sufficiently large m
Pr(M(x) + (x)
A D 2 exp(-c2k) exp(-co -xp(-)
23

---

Therefore,
Es (h(x) + (x))
A = PF]M(x) + (x)x A
2 Pr]M(x)= # (x)
D A
s Pr]h(x)= + f (x) A DJ PrID A c1 -cck) exp( 1pp(--c.he h.hht - p
m cap
due to our assignment of & (and the explicit form of co in Lemma B.2).
C Proof of Theorem 5.1
Setting for the proof. Throughout the proof, we will use the notation introduced in Appendix A. We start by specifying the target function and distribution for which will prove that catastrophic overfitting occurs. We will consider a slightly more general version than mentioned the main text. We define distribution on B(0, R) whose density is given by
Fix R, r, c 0 that satisfy R 3r.
((..))
|
<
r
Vara
x
<
μ(x): ==
3r else
S X
S
R
3r else
S |x||
S
R
(3))
where Va is the volume of the d-dimensional unit ball. We also define the target function
f" (x) = {1)
| rr
else
The main lemma from we derive the proof of Theorem 5.1 is the following: Lemma C.1. Under setting suppose that satisfies
1 - 1-3/d
2400 (1+ )))
Then there exists some ma E N, such that for any x E B(0,r), m > mg and p E (0,0.49), it holds with probability at least Öm m
over the randomness of the training set that
hg (x) 11
We temporarily defer the proof of Lemma C.1, and start by showing that it easily implies the theorem:
B/d Proof. of Theorem 5.1 Fix R > 3r, let 2400 + g and consider the distribution and target function given by Setting C. Using the law of total expectation, we have that
Es Pr(h(x)= + (x)) Es 1 (M(2) # (*()
E,Es [1
Ez Es (1(z) f()x)) z B(0,r) Pr Pr(ze B(0,r) Ez [Pr (1(x) + (x)) z 2 B(,r)) e
Pr
(0) c 1 3m
BIA
37d
where (+) follows from Lemma C. This completes the proof by sending 00.
24

---

C.1 Proof of Lemma C.1
Fix some x with ||x]| < v, we will show that for sufficiently large m, with high probability x will be misclassified as +1. To that end, we decompose
yi
Σ
x
X;
x
X
X;
#:||>:
23r
|x - x;|
yi
1 2p
V1 + 2p
|x
x;
|x x1
||x X; || 1
1Sr
12rr
::||xc: 23r
- 2p
Σ
Y/ 1 + 2p
(8)
xx - x;
||x
x;
8
||x - x,1l
k|| Sr
<||,, 23r
=:
=
where Ti crudely bounds the contribution of points in the inner circle, T2 is the expected contribution of outer points labeled 1, and T3 is a perturbation term. Let km == Ki E [m] ||x=|| S rr] denote the number of training points inside the inner ball. By Lemma C.3, whenever happens) it holds with probability at least exx m
(we will ensure this
that
cm S km S 2
3cm
3m
(9)
4
Throughout the rest of the proof, we assume this event indeed occurs.
Bounding Ti: Using that ||x|| and that the pdf y is such that for all x; B(O, r), ||x - x,| >
3r 2r, we have that the km nearest neighbors (()):..., ((kk.)) are precisely the points with
||x,] S r.
For any w S (2r) and any z E B wd) it holds that ||z||| S 3r, and v(x) Vara Thus, for such a w.
[|z - x11 S was) ) S (x(xwottt) u(x)dzz
F(w)= := == Pr (lz xx|" x11" S w0)
= Pr a
< (xx Varal dz c w
pd
Correspondingly, by substituting u _. w., we obtain for any u S 2dc that 2 F uuyad
and thus (w) 2 ad Note that for any [km]] ||x x 11 (2r)ad W(s) satisfies the condition that W(2) S (2r)ad, As such, using Lemma A.2 we obtain
ca
ca
rad
Vi E [km]]
W _ F (U()
(10)
Now for Tı, we have from Eq. (10):
-T
d
km
F (U 2
km
2(1)
(1 (1- (1-a) a) pad -ma 1l1
3. ea
pad
U
i=1
3a α 3em
1-a
2a.3 3
2(2) (1 (1-0) a) pad
maa
- (1 - a prad C,
2
where (1) holds by Lemma C.4 with probability at least
Ökm
1
1
h o
Om m
and (2) follows from Eq. (9).
25

---

Bounding T2: Using the fact that for any E [m].
| - x:ll
-
|x]
+ ||x
I R + and the bound
on km from Eq. (9), we have for any p < 0.49 that
T2 2 (1 2p)(m km))
(1 - 2p)
(R + r)ad
2
(R + r)ad
4 m
>
m
200 R + r))ddd
Bounding T3: From Lemma C.2 and Eq. (9), it holds with probability least 1 2exp (- v that
(m km)= (rd ad
T3 I
m
(2r)od
Putting it Together: For any > 0 there is some mo E N. such that for any m > mo. -I' 2 -m.. So overall, we obtain that with probability at least - Öm
1
1
Vi
1 - (- TT T3)
2a 33
+
x
ad
m
)rad
200 r)ad
6
1
(1 ror ++
400 (R + r)
where the last line follows by using that a < 1, and by fixing some sufficiently small e. Finally, fixing suffices to ensure that this is positive, implying hx(x)) =
(1-a)pad some e 2400(Rtrjao 2400 ++ 2)az
1-a
Lemma C.2. Under Setting C, let x E B(0,r) r) and km == Ki E [m] ||x:|| S rr) It holds with probability at least 2 exp
v m km) that
y1 + 2p
(m km)
||x
x 1
(2r) ad
Proof. Let & be the random variable representing a label flip, meaning that &, is 1 with probability p and with probability 1 p. and Y/: (x; by assumption. For any x, with ||x;|| 3r, holds that f (x:) = 1, and that x x;1l
2 ||x;| - | 2 2r, and thus d1
are bounded as ||x-x,
Vi
||x
x;
ad
(2r)ad
We thus apply Hoeffding's Inequality (cf. 49, Theorem 2.2.6) yielding that for any t
Σ
Σ
1- 2p
(- (- (²(2r) 2nxd
2t < 2 2exp
|
xx
ad
|X
x;|| nnd
2(m kim)
<||,,|||33
In particular, have that with probability at least 1 2exp
(- 1 vm kmm that
Yi
ad (1 (1p)
Σ
(m km
||x
x;
||x - x; and
ard
6:||,, |23r
*:||>, 123r
Lemma C.3. Under setting C, let km == (i: || S r.). then it holds with probability at least
1 - --2 2exp(- Zm that
Cm ki
3cm
2
26

---

Li=1 B, where B, = 1 if X - r and 0 otherwise. Notice that each B, Bernoulli random variable with parameter c, i.e B, with probability e and 0 with probability 1 - c. So by Hoeffding's s inequality (cf. 49, Theorem 2.2.6), we have for any /. 2 0 that
Proof. We can rewrite km
m
m
21
Pr
Σ
cm
2
exp
m
Taking 1. concludes the proof.
Lemma C.4. holds for any & S m E N. < 0
1 that with probability at least
1 O2
k
Σ
Proof. Fix some no S k which will be specified later. Using Lemma A.3, write
Σ
Σ
Ej=1
i=1
1=1
np
Es
(11)
i=1
Eg
1=no
Ej=n Eg
:=
By Lemma D.1, for some absolute constant C > that for all n 2 no.
holds with probability 1 1-2(1+ + 2)
1 2
3n 2
(12)
Conditioned on this even occurring, we use this to bound both Ti and Tz. For Ti, Eq. (12) directly implies that Ti (3m)² For Ta, using both Eq. (12) as well as the integral test for convergence we obtain
1
k
(no 1)'-a
T3 < 2
2
2
2a
1
remains to bound T2. By definition of an exponential random variable, for any t 2 0 it holds for any E, with probability at least exp(-t) (which is 2 1) that E, 2 So taking = (x -x
mg holds with probability at least - ( j that Ej 2 Ag
1/
As result,
1
Tb S no
no
k 1-
(13)
ET
To ensure that the probability that both Eq. (12) and Eq. (13) hold is sufficiently high, we take no = max () log(k), 2). As such, we obtain that with probability at least
that
Eq. (11) can bounded as
3
kl-a
(no 1
Mi (I2 +
T3)
-
2
2a
+ kl--
1-a a
(4)
3
2
3
2a
m
1l-o
+1
<
= m
kl-a
1-a a
2
1 1-a
3
27

---

D Auxiliary lemma
Lemma D.I. Suppose (Ei)ien sid exp(1) are standard sxpooemiiaa random variables. Then there exists some absolute constant such that:
1. For any N holds that
3n 2
Pr
E,
S
2 1 11-2exp(-CM)
2
2. For any no E N it holds that
Pr
80
n
n
E,
S
3n
2 21-2 2
(1+ (1-2(11 (1+2) exp(-Cro)-
n=010 T1D
2
=1
Proof. Denote by ||. l1.. the sub-exponential norm of a random vector (for a reminder the definition, see for example Vershynin 49, Definition 2.7.5). Each E; satisfies for any > 0. Pr (E, 2 t) <
exp(-t) implying that | So Bernstein's 's inequality for sub exponential random variables [49, Corollary 2.8.3] states that there exists some absolute constant C" > O such that for any t 2 0
By Vershynin [50, Remark 5.18], this implies || - 1 1l S
I 2 exx (-c' min
t t
Pr
E
2t
4
Taking and taking C ==
C' 16
yields
Pr
E,
2 n
< 2 exp (-Cn).
This proves the first statement. For the second statement, union bound and apply the integral test for convergence, to get that
Pr
U n
Σ 1m
Es
n
n
Pr
E,
n 2 n
2
2
n=
im1
2
exp (-On)
n=
< 2 1exepp-Chii +2 expl-
< 2 (epp(-Cno)
+ C exp(-Cno))
expertine
E Additional experiment
extension
In this appendix, we provide an extension of the spherical data experiment discussed in the main paper, demonstrating the effect of noisy sampling on our results.
We repeated the experiment with data sampled from the sphere the sphere $ c R given by Eq. (5). This time, after sampling from the sphere, we added Gaussian noise distributed as (0, (2)) to each data point independently, and examined the effect of the noise variance o² the exponent achieving minimal test error (corresponding to the intrinsic dimension in our theory).
The results presented in Figure 6, with 2000, 0.04 and various values of a
28

---

0.10
Dataset variance
Test error
0.1
0.08
0.06
0.04
0.02
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
B
Figure 6: The classification error of hg for varying values of B and sampling noise 0². Best viewed in color.
As the noise increases, see that this "best" gradually increases from 2 to 3, the data indeed becomes fully dimensional for significant noise in the data-points, For example, with variance 0.04 in each coordinate (equivalently, standard deviation 0.2), the optimal is roughly 2.5, which is notably still smaller than 3.
29


Reviews:
[{"review_id": "vX3Wj8Rg3D", "reviewer": "Reviewer_AL49", "summary": "The authors study different generalization regimes using a simple well-defined interpolating model, the Nadaray-Watson kernel estimator for binary classification. They show that even this simple model can exhibit complex generalization behavior and that the progression from catastrophic, to benign, to tempered overfitting occurs, and - in this case - can be controlled by a single hyperparameter: the exponent of the kernel denominator (beta). The main contribution of the paper is theoretical, with proofs provided of the role of beta in the progression from one regime to another. This is supplemented with experimental verification using synthetic data.", "questions": "Please discuss the significance of the findings.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- A very specific theoretical question is precisely answered.\n- Claims are clear and well supported.\n- Theoretical analysis is similarly well presented and an effort is made to make the proofs accessible. \n- Work is carefully developed and the methodology used is sound.\n- Results are interesting and novel.\n- The discussion around explicit vs implicit dimension and the implications of over- or underestimating dimensionality contributes to the main result.\n\nWeaknesses:\n- I am uncertain of the significance of the main analysis.\n\nOther comments:\n- Line 96 – introduction to sections needs an update.\n- I did not review the proofs in the supplementary material.", "was_revised": true, "final_justification": "Solid technical paper. Novel contribution to relevant field. Significance for the broader field is somewhat borderline, but I believe it to be over the threshold.", "rebuttal": "We thank the reviewer for their time, and are encouraged by their appreciation of our contributions. We also thank them for spotting the need for updating the section numbering in Line 96, which we will incorporate into the final version.\n\nAddressing the reviewer’s question, we believe the significance of our results is two-fold:\n- Overfitting regimes of interpolating predictors are a widely studied topic recently. However, we are not aware of any single interpolator that provably exhibits the full range of catastrophic-tempered-benign overfitting behaviors, as we show here. Thus, we identify a simple and classical predictor whose analysis allows us to understand the full spectrum of overfitting behaviors, and the factors that underlie them (such as the effect of locality).\n- By revisiting the analysis and extending it to inconsistent regimes not previously covered, we identify an interesting dependence on the *intrinsic* dimension, which is typically unknown. This phenomenon, also backed up by numerical evidence, has an implication on the optimal choice of the hyperparameter $\\beta$ in practice, as we further discuss in the paper.\n\nWe hope our response addresses the reviewer’s comments, and will be happy to further clarify any point if needed."}, {"review_id": "H5dMSVhoBE", "reviewer": "Reviewer_bJoP", "summary": "The paper analyzes the generalization performance of the NW interpolator. The results show that if $\\beta>d$, there exists tempered overfitting, meaning the excess risk has the same order as the noise rate. If $\\beta<d$, there exists catastrophic overfitting, meaning that the excess risk may be $\\Theta(1)$ large.", "questions": "Is it possible to extend your result to multi-class classification? What will the result look like?\n\nIs it possible to extend your result to a setting in which the noise rate is data dependent? (p is a function of x)\n\nWhat is the convergence rate of the NW interpolator? Can you express the excess risk as a function of m? Is it in general better than using a neural network to solve the classification problem?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The introduction and the main results are stated very clearly.\n\nProof sketches and the intuitions behind proofs are explained in detail.\n\nExperiments are presented to justify the theories.\n\nThe solved problem is technical and contributive.", "was_revised": true, "final_justification": "This is a very good paper and the results are interesting. I recommend accepting this paper.", "rebuttal": "We thank the reviewer for their time, and are encouraged by their appreciation of our contribution. Below, we address the reviewer’s questions:\n- Extensions to the multi-class setting are a very interesting direction, which are generally under-studied in the modern overfitting context (see [1] for a notable exception). We would like to remark that for kernel rules, there is generally not a single canonical way to extend the predictor itself to the multi-class setting. If viewing the outputs as vector valued and taking the argmax, we do expect the results to generalize. In any case, this is certainly an interesting direction for future research.\n- It is very likely that our results extend to the case in which the noise rate is data-dependent. Indeed, since our tempered analysis is highly local, it is likely that p can be replaced by a localized quantity such as $\\int p(x) d\\mu(x)$, namely the averaged noise rate with respect to the underlying distribution. As to the catastrophic case, the results should readily hold for data-dependent p as long as it is bounded away from 0 and 1/2, which would not actually alter the analysis. We thank the reviewer for this excellent point, and we will remark about this in the final version of the paper.\n- Convergence rates of NW interpolators and related non-parametric rules are extensively studied in the literature, and such rates generally depend on the smoothness properties of the underlying $f^{\\star}$, see e.g. the books [2,3]. NW interpolators are one of the most well-studied learning rules in statistics for decades, and the question of comparing whether they are preferable or not to neural networks is beyond the scope of this work. In our work, we chose not to make any such quantitative assumptions on  $f^{\\star}$ for the results to be as generally applicable as possible, and therefore did not go into analyzing the corresponding rates. We remark that indeed using these existing techniques, it is not difficult to establish the corresponding rates for smoothness classes.\n\nWe hope our response addresses the reviewer’s comments, and will be happy to further clarify any point if needed.\n\nReferences:\n\n[1] Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation, Wang et al. NeurIPS 2021\n\n[2] Introduction to Nonparametric Estimation, by Tsybakov\n\n[3] A probabilistic theory of pattern recognition, by Devroye, Gyorfi and Lugosi"}, {"review_id": "ObZKYlYKMd", "reviewer": "Reviewer_y616", "summary": "This paper analyzes overfitting of Nadaraya-Watson Interpolators, and identifies the benign overfitting regime encountered where $d=\\beta$ (for dimension $d$ and bandwidth $\\beta$) as a phase transition between so-called 'tempered' and 'catastrophic' regimes. These regimes are characterized in terms of the asymptotic classification error as a function of label noise.", "questions": "How do the estimators behave numerically at values of $p$ closer to 0.5?\n\nML problems frequently have high data dimension. How does varying the input dimension (both intrinsic and ambient) interact with your results. For GP regression problems, UQ quantities have been shown to be sensitive to data dimension, exhibiting monotonicity in some cases and double-descent in others. However these kernels do not include the one used here (since both the kernel and its gradient blow up at $\\|x-y\\|=0$). Any similarity or contrast in behavior of either $d$ or $d_\\mbox{int}$ near $m$ could provide some insight here. Of course, there is also the risk that the results break down for high dimensional problems, so it should be confirmed that this is not the case. Similarly, data seldom has a clean intrinsic dimension, even if it’s just due to measurement or other noise. How does the addition of a small amount of noise perturbing the data from sub manifolds impact your results?\n\nIs there any reason that there is inconsistency between the requirement that $p\\int(0,\\frac{1}{2})$ and $p\\in(0,0.49)$ besides convenience? In my opinion, consistency here, and statement of the dependence away from $\\frac{1}{2}$ would be preferable.", "limitations": "Limitations of the work are not explicitly addressed.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is generally well-written and the proofs appear to be correct.\nThe numerics section of the paper only considers the cases where $d=1$, and $d=3$ with intrinsic dimension of $d_\\mbox{int}=2$.\nSimilarly, the behavior is only treated numerically for small values of $p$.\nThe claims switch from $p\\in(0,\\frac{1}{2})$ to $p\\in(0,0.49)$ which appears to be purely for convenience (in the calculation of $T_2$ in the proof of Theorem 4.1). Restatement of the theorems in terms of $(1-2p)$ may be illustrative.\n\nI think this is good work and would like to be able to raise my score if the paper is improved.", "was_revised": true, "final_justification": "This is a good paper, and I think it should be accepted. Being primarily a theory paper, the experimental section was weak, but the authors have provided some additional experiments that I believe strengthen the work.", "rebuttal": "We thank the reviewer for their time and constructive comments. Below, we address all of the comments raised by the reviewer:\n\n- Value of the noise parameter $p$: Indeed, as the reviewer correctly noted, the choice of stating the claims for $p\\in (0, 1/2)$ or $p \\in (0, 0.49)$ is purely for convenience, as the term $1-2p$ appears in the proof of Theorem 4.1. As $p$ approaches $0.5$, the training labels approach pure noise, regardless of $f^{\\star}$. Therefore, previous works focus on the regimes in which $p$ is small, since that is when tempered overfitting is far less harmful than catastrophic, which is of key interest. We emphasize that the ability to cover the entire noise interval is actually an advantage of our analysis, rather than a drawback. We agree that consistency in the statement of the theorems would improve the presentation of the paper, and we will make the necessary adjustments. Thank you for this suggestion! \n- Dimension of the data: An important observation is that the NW predictor depends entirely on the distances between points, and as such, the results depend on the intrinsic dimension of the data, and not the ambient dimension (as exemplified in Figure 4 in the paper). The reviewer raised a very interesting question regarding noise, which can influence this ambient dimension. Yet, since the predictor only depends on the distances between points, the predictor is robust to sufficiently small perturbations, which would hardly affect the distances. Indeed, we have new simulations showing this phenomenon, which we will add to the final version of the paper (note that we cannot add them here due to the new NeurIPS policy).\nLastly, regarding the interaction between the dimension and number of samples, the proofs in the paper hold for any dimension, though of course, the constants and the rates may depend on the dimension. This is inevitable, as a larger dimension may lead to slower convergence, as is to be expected for non-parametric learning rules. Please see also our 3rd item in response to reviewer bJoP on this point.\n\nWe hope our response addresses the reviewer’s comments, and will be happy to further clarify any point if needed. If there are any concerns remaining after this response that are preventing the reviewer from raising their score, please let us know so that we can address them."}, {"review_id": "j5d5kVK9mU", "reviewer": "Reviewer_eB3z", "summary": "This paper studies the benign overfitting under the setting of Nadaraya-Watson(NW) estimators for binary classification with noise level $p \\in (0,1/2)$ measured by the clean classification error.\nIn particular, the paper considers a special type of NW interpolator which is controlled by a hyperparameter $\\beta$.\nPrevious work showed that if $\\beta = d$, the interpolator has vanishing error as the sample size goes to infinity, which is benign overfitting.\nThis work focuses on the cases $\\beta \\neq d$ and shows that:  for $\\beta > d$, the error is non-zero but bounded between $poly(p)$ and $O(p)$, corresponding to termpered overfitting; for $\\beta < d$, the error is bounded below by some constant independent of $p$, corresponding to catastrophic overfitting.\nNumerical simulations are also provided to validate the results.", "questions": "1. Can you compare the interpolating behaviors of the NW interpolator with other kind of (possibly benign) overfittings, such as the kernel interpolators in Mallinar et al. [7]  and http://arxiv.org/abs/2305.14077?\n\n2. Can be discuss more on the intuition or insight of the parameter $\\beta$? It seems that small $\\beta$ leads to \"underfitting\" and large $\\beta$ leads to \"overfitting\" (though it is already an interpolator).\n\n3. Can the insights in this paper be applied to NW estimators for regression where there is a bandwidth parameter? What are the differences?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n* This paper extends the understanding of benign overfitting to NW interpolators for binary classification.\n* The non-monotonic phase change in the overfitting behaviors is novel and interesting.\n\n\n## Weaknesses\n\n* For the catastrophic overfitting, Theorem 4.1 is only stated for \"there exist a density and a target function\", but not for any density and target function, limiting the significance of the result.\n* While the new phenomenon under the NW interpolator is discovered, more in-depth analysis and comparision can be provided to improve the understandings.\n\n I am willing increase my score if the weaknesses (particularly the first one) are properly addressed.", "was_revised": true, "final_justification": "The authors' response clarifies the generality of their theory, particularly Theorem 4.1.\nNow I tend to accept the paper because of the theoretical contributions.", "rebuttal": "We thank the reviewer for their time and constructive comments. \n\n- Theorem 4.1 statement: We thank the reviewer for this important comment, which we would like to thoroughly address. First, it is important to note that even the most trivial predictor can “accidentally” succeed at learning some target functions under certain densities. For example, consider the most trivial predictor which always predicts $0$ on points not in the training set: if the target function happens to be a constant zero, this predictor achieves perfect generalization. Of course, for almost any other target function, this predictor would exhibit terrible overfitting, and any sensible definition of catastrophic overfitting should be satisfied by such a predictor. We thus believe that the natural way to define catastrophic overfitting, as also done by all previous works, is in a worst-case manner, and therefore the statement of Theorem 4.1 is not a limitation of our analysis, but is rather a natural way to present a lower bound in this context. Nonetheless, we agree that we should better emphasize how our analysis applies to other constructions besides the specific counter-example in this theorem. Indeed, the analysis essentially shows that whenever a small region of constant probability mass is surrounded by the opposite label, it will be mislabeled by the predictor, incurring constant error. This is actually very generic, and applies to many ground truths $f^{\\star}$. We will therefore revise the presentation to emphasize this point, and thank the reviewer for bringing this to our attention.\n\n- Comparison with other methods: There are by now many known results regarding the overfitting behavior of kernel interpolators, as partially summarized in the excellent paper by Mallinar et al. that you referenced. To the best of our knowledge, for kernel interpolators, there is no example of a single kernel provably exhibiting all three types of overfitting as we do here (even with a varying bandwidth). For example, as shown in [1], for any bandwidth, the RBF kernel is always worse than the constant-zero predictor, which implies catastrophic overfitting.\nAnother important point is the difference in proof techniques. Known results for kernel interpolators typically rely on a spectral analysis. However, this often requires additional non-trivial assumptions (e.g. Gaussian universality). By contrast, our proof techniques are entirely different, based on characterizing the “locality” of the predictor. Following the reviewer’s comment, we will add this discussion to the final version of the paper.\n\n- Intuition regarding $\\beta$: The hyperparameter $\\beta$ influences “locality” of the predictor, meaning that as $\\beta$ increases, the evaluation of the NW predictor at a new point will be influenced more by nearby points. \n\n- Extension for regression: Thank you for this excellent question. We suspect that the results should remain valid for regression, as the underlying idea behind the proofs should still hold. Specifically, if $\\beta > d$ the predictor should still be “too local”, and if $\\beta < d$, it should still be “too global”. Nevertheless, formalizing this would be an interesting future work. \n\nWe hope our response addresses the reviewer’s comments, and will be happy to further clarify any point if needed. If there are any concerns remaining after this response that are preventing the reviewer from raising their score, please let us know so that we can address them.\n\n[1] Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality, Medvedev et al., NeurIPS 2024"}]

Author rebuttal:

Meta-review: The paper provides the overall overfitting profiles for the Nadaraya-Watson Interpolators. The key is the selection of $\beta$ in the inverse distance weighting Kernel $K(x,y)=1/||x-y||^\beta$. (Since the inverse distance weighting interpolates the data. ) When $\beta$ is smaller than $d$, the classifier would seek data apart from the origin, thus making catastrophic overfitting results. When $\beta$ is larger than $d$, the estimator is similar to a $k$-nearest neighbor estimator with finite $k$. The proof sketch is clean and easy to follow, providing a comprehensive understanding of the Nadaraya-Watson Interpolators. Thus, I suggest acceptance.
Decision: Accept (poster)