Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality
Authors: Marko Medvedev
Gal Vardi
Nathan Srebro
Venue: NeurIPS 2024 poster (2024)
Keywords: Kernel ridge regression
benign overfitting
tempered overfitting
Gaussian kernel
Primary area: learning_theory

Abstract: We consider the overfitting behavior of minimum norm interpolating solutions of Gaussian kernel ridge regression (i.e. kernel ridgeless regression), when the bandwidth or input dimension varies with the sample size. For fixed dimensions, we show that even with varying or tuned bandwidth, the ridgeless solution is never consistent and, at least with large enough noise, always worse than the null predictor. For increasing dimension, we give a generic characterization of the overfitting behavior for any scaling of the dimension with sample size. We use this to provide the first example of benign overfitting using the Gaussian kernel with sub-polynomial scaling dimension.  All our results are under the Gaussian universality ansatz and the (non-rigorous) risk predictions in terms of the kernel eigenstructure.

Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality
Marko Medvedev The University of Chicago medvedevbuchicage edu
Gal Vardi
Nathan Srebro TTI-Chicago nati@ttic.
Weizmann Institute of Science gal. vardi www.wwwwmanmmmm.......e...ma.wwe ac i1
Abstract
We consider the overfitting behavior of minimum norm interpolating solutions Gaussian kernel ridge regression (i.e. kernel ridgeless regression), when the bandwidth or input dimension varies with the sample size. For fixed dimensions, we show that even with varying or tuned bandwidth, the ridgeless solution is never consistent and, at least with large enough noise, always worse than the null predictor. For increasing dimension, we give generic characterization of the overfitting behavior for any scaling of the dimension with sample size. We use this to provide the first example of benign overfitting using the Gaussian kernel with sub-polynomial scaling dimension. All our results are under the Gaussian universality ansatz and the (non-rigorous) risk predictions in terms of the kernel eigenstructure.
1
Introduction
central question in learning theory is how learning algorithms can generalize well even when returning models that perfectly fit (i.e. interpolate) noisy training data. This phenomenon was observed empirically by Zhang et al. [63], and does not align with the traditional belief from statistical learning theory that overfitting to noise Ieads to poor generalization. Consequently, it attracted significant interest in recent years, and there has been much effort to understand the overfitting behavior of linear models, kernel methods, and neural networks.
In this paper, we study the overfitting behavior of Kernel Ridge Regression (KRR) with Gaussian kernel, namely, the behavior of the limiting test eтrоr when training on noisy data as the number of samples tends infinity by insisting on interpolation (achieving zero training error). When the input dimension and bandwidth are fixed, the overfitting behavior is known to be "catastrophic" [37], ie. for any nonzero noise, the test risk tends to infinity as the sample size increases. However, this is not how Gaussian Kernel Ridge Regression is typically used in practice. In fixed dimension, the bandwidth is tuned, that decreased, when the sample size increases [51, 19]. Additionally, makes sense study the behaviour when the input dimension increases with sample size (as in, e.g. linear models with proportional scaling [42]). This could be because when more data is available, more input features used, even with kernel; because more resources are available up both the input dimension and amount of data used; or to capture the fact that very large scale problems typically involve both more samples and higher input dimension. But unlike with linear models, where the dimension must scale linearly with the number of samples in order to allow for interpolation, when kernel is used we can study the behaviour increases much slower, and ask how slowly it could increase without catastrophic overfitting. Previous studies kernel ridgeless regression considered polynomial increasing dimension (i.e. dimension x sample-size", for 0 < < 1) [4, 64, 24, 38, 40], but not subpolynomial scaling.
scale
when the input dimensionality
We aim to provide more comprehensive picture of overfitting with Gaussian KRR by studying the overfitting behavior with varying bandwidth or with arbitrarily varying dimension, including
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

hubb-ooynomially. In particular, we show that for fixed dimension, even with varying bandwidth, the interpolation learning is never consistent and generally not better than the null predictor (either the test error tends to infinity or is finite but it is almost always not better than the null predictor). For increasing dimension, we give an upper and lower bound on the test risk for any scaling of the dimension with sample size, which indicates in many cases whether the overfitting is catastrophic (test error tends to infinity), tempered (test error tends to a constant), or benign (consistent). Our result agrees with the polynomial scaling of the dimension with sample size, showing tempered overfitting for an exponent that is a reciprocal of an integer and benign overfitting for any other exponent [4, 64]. Moreover, our result goes further, scaling dimension that achieves benign overfitting for the Gaussian kernel. Additionally, we show that class of dot-product kemels on the sphere is inconsistent when the dimension scales logarithmically with sample size. All our results are under the Gaussian universality ansatz and the non-rigorous but well-established risk predictions in terms of the kernel eigenstructure [50, 66, 8, 57].
show the first example of sub-polynomially
Related work
The test performance of overfitting models has been extensively studied for linear regression [27, 6, 3, 4343, 45, 16, 32, 58, 53, 65, 30, 54, 13, 2, 49, 25], linear classification [12, 55, 10, 44, 42, 49, 36, 52, 56, 18], neural networks [20, 21, 11, 34, 60, 61, 39, 33, 23, 31, 291, and kernel methods. Below we focus on overfitting in kernel ridge regression.
Overfitting fixed dimension with fixed kernel. In Mallinar et al. [37], the authors show that the minimum norm interpolating solution for Gaussian kernel with fixed bandwidth overfits catastrophically. In [15, 4, 64], the authors derive bounds on the test risk of minimum norm interpolant with fixed kernel under various assumptions. Our result for fixed dimension will only apply to the Gaussian kernel, but allows for any varying or adaptively chosen bandwidth.
Inconsistency of Kernel Ridge Regression. The case of varying bandwidth has been considered in Beaglehole et al. [5], Rakhlin and Zhai [47], Haas et al. [26]. In Beaglehole et al. [5], the authors show that there exists a specific data distribution for which the minimum norm interpolanting solution for a particular set of translation invariant kernels is not consistent. In Rakhlin and Zhai [47], the authors show that for input distributions on the unit ball, the Laplace kernel is inconsistent, even with varying bandwidth. In Haas et al. [26], the authors show that under different assumptions on the data distribution, for general class of (potentially varying) kernels in fixed dimension, any differentiable function that overfits the data and is not much different from the minimum norm interpolant is inconsistent. All of these works only consider whether we can achieve consistency. None of these results apply in the case of data distributions that we are considering, and even if the predictor is not consistent, we ask how bad is it by comparing it to the null predictor and whether it might be tempered.
Overfitting in increasing dimensions. Many papers have studied the setup where the dimension increases with sample size [4, 64, 66, 38, 40, 28, 59], in particular when the dimension a function of sample size (or vice versa), but they all consider only the case of a polynomial scaling of dimension and sample size. It was shown that in this case the minimum norm interpolating solution of dot product kernels on the sphere can be benign, depending on if the exponent is not an integer. We generalize these results to any scaling of the dimension and sample size. Our results recover the existing results in the case of polynomially scaling dimension and show benign overfitting in certain sub-polynomial scaling. Having sub-polynomimal scaling of the dimension allows us to expand the set of possible target functions from only polynomials of bounded degree, as in the case of polynomial scaling of dimension [4, 64, 66, 38, 40], to, in our case of oolloolynomilly increasing dimension, polynomials of any degree and even non-poly non-polynomial functions.
2 Problem formulation and assumptions
Kernel ridge(less) regression and the Gaussian kernel. Let D be an unknown distribution over X x ) C Rd x R and let ((x,, y:) p ~ D'm be a dataset consisting of m samples. For simplicity, we will assume that the distribution of the target is given by target function f" of the input X
2

---

with zero mean independent noise & with variance o², that is ~ (x) + &. We note that our results can be extended to a distribution agnostic setting, as analyzed by Zhou al. [66].
Let K X' x X' + R be positive semi-definite kernel function. Let ||/l be the norm of f in the RKHS Hx corresponding to K. For predictor f. let R(f) and R(f) be the test and training risk of f.
m (f(x)) m
R(f)
y1)² -b) and R(f) ED [(f(z) y)
Two important risks to consider are the risk of the null predictor. f = O, which we will denote by R(O) = (E))], I, and the Bayes (or irreducible) risk, which we will denote o² or R(f*). Using this notation, the risk of the null predictor is R(O)- o² + ED [(v)²]. Bayes risk represents the minimum possible risk that can be achieved by any predictor. For regularization parameter 6, the regularized
ridge solution fs is given by
fs = argmin R()) _ 11
m
We are interested in the minimum norm interpolating (ridgeless) solution fo = limg fs. namely
fo argmin R(f)= Il
We will focus on the Gaussian kernel, which is given by K (x11, = exp the sample size and Tm predetermined bandwidth parameter that can vary with sample size. The Gaussian kernel is widely used and achieves good error rates for variety of learning tasks [51, 19]. Gaussian KRR achieves optimal convergence to the best possible (Bayes) error for learning any function in Besov space of high enough order (essentially bounded and twice differentiable in the weak sense) under very mild assumptions on the distribution of the input and target X' x y [19]. For ridge regression with the Gaussian kernel and under standard data distribution assumption, the minimum distance between samples decreases with sample size so makes sense to also decrease Ti- Additionally, decreasing with sample size helps to achieve good convergence rates theoretically [19].
[. | Tm
where m
Main question. will consider the problem of learning using the minimum norm interpolating solution fo of KRR. We want to understand the limiting behavior test risk R(fo) as the sample size increases m + do, that is limm-+oo R(fo). It suffices to understand lim R(fo) and R(fo) and this way we do not assume the existence of the limit. In this work, we use the taxonomy of benign, tempered, and catastrophic overfitting from Mallinar et al. [37], which indicates whether limm- R(fo) is the Bayes (optimal) error, a non-optimal but constant error, or infinity. Note that in this taxonomy, the null predictor can be classified as tempered. Therefore, will compare the limiting risk to the risk of the null predictor R(0) in order to understand whether the performance of the interpolating solution is non-trivial.
lim inf
Main tool: Eigenframework and a closed form of the test risk. Our main tool will be the closed form of the test risk predicted by the eigenframwork [50]. Under the eigenframework, we can write down the closed form of the test risk using Mercer's 's theorem decomposition of kernel function K.
Given a positive semi-definite kernel function K X' X +
R, we can decompose it as
20
K K(11, x2) Σ Aeda (x1)
where A and Φy are the cigenvalues and cigenfunctions of the integral operator associated to K. The eigenfunctions {Ø*} are an orthonormal basis of -T (X). where Dx the marginal distribution of X. We denote the Bayes optimal target function by f and expand f*(z) = Eie (z). To state the close form of the test risk we will introduce few quantities. Let effective regularization, Ks, be the solution to E X
the kernel basis {d.) as
+ 5.
m. Furthermore, let Lts5 A.tRa
A:
Autra
3

---

and Eg m -.--.= 4,,6" is given by
m Then, the predicted risk, i.e. the predicted closed form of the test risk of fa.
20 (1 - C1,8) B + +0²
R(fs) Es
(2)
where x² is the Bayes error of D. Equation (2) was initially heuristically derived using the replica method or continuous approximations to the learning curves inspired by the Gaussian process literature [7]. In [50], it is dervied using conservation law. Note that [66] shows that the predicted closed form of the test risk from [50] extends to general target distributions. There is strong evidence that the predicted risk is good estimate of the true test risk, namely R(fss) Pe R(fs). Indeed, number of works use the predicted risk closed form to estimate the test risk of KRR [58, 8, 66). The following assumption on Gaussian design ansatz is used by all of these works.
Asumption 1 (Gaussian design ansatz, cf. Zhou et al. [66]). When sampling (a,, -) ~ DD we have that the Gaussian universality holds for the eigenfunctions in the sense that the expected risk is unchanged we replace e with Φ, where ő is Gaussian with appropriate parameters, i.e. Ø ~ NO, d (A,)).
This assumption appears to hold for real datasets as well, namely, the predictions computed for Gaussian design agree well with the experiments on kernel regression using real data [8. 50, 57J. As discussed in Zhou et al. [66], under this assumption, the equivalence R(fs) = R(fs) holds in a few ways. First, in an appropriate asymptotic limit in which the sample size m and the number of eigenmodes in a given eigenvalue grow proportionally, the equivalence holds [27, 1]. Second, if the eigenstructure of the task is fixed, the error between the two can be bounded by a decaying function of m [14]. Finally, various numerical experiments show that the error between the two is small even for small sample size m [8, 50J. Specifically, Canatar et al. [8] (see Figure 5 there) gives empirical evidence that the predicted risk closely approximates the true risk for the Gaussian kernel with data uniform on sphere, which is the setting that we consider in some of our results.
There has been some recent progress in bounding the error between R(fs) and R(fs) unconditionally. Misiakiewicz and Saeed [41] shows that the error will tend to zero if the dimension d grows fast enough with the sample size. Additionally, they provide strong empirical evidence that the predicted risk is close to the test risk for a real dataset (MNIST) and Gaussian kernel, see Figure 1 in [41].
Formally, we will prove results about the predicted risk R(fa), but as previously presented evidence suggests, treating R(fss) ~ R((f.s) as equivalence is sufficient for understanding the behavior of KRR.
We note that using the eigenframework might introduce restrictions for which kernels some of our results apply, as concurrent work showed that the eigenframework prediction might not hold for the NTK in fixed dimension [4, 15]. Our two main results concern the Gaussian kernel, for which described ample empirical evidence that the eigenlearning predictions hold [8, 41]. Understanding the limitations of the eigenframework is an important future research direction.
3 Fixed dimension: Gaussian kernel with varying bandwidth
We will assume that the source distribution is uniform on a d dimensional sphere, that the target function is square integrable, and that the target distribution is given by the target function with an independent noise.
Assumption 2 (Target function and data distribution). Let DD be the distribution over X' x y gd-1 x IR, such that the X' marginal, denoted by Dx, is Unif()d-1). We will assume that for target function f E ( the marginal y' distribution is given by y f((x) + 5, where & has mean zero and variance 0² > O. We write f = E, Bidi, where { is the T2Z (sd-1) eigenbasis corresponding the kernel K (Equation (1)). If we write 3 = (B1, B2...... ..... ), then have that || Exx (())))))). We will use the notation || = 1|3112.
The assumption on the distribution on X' is common in the literature on KRR [38, 4, 64, 22]. The assumption that x Unif (s4-1) can be relaxed to more general setting where x is uniformly distributed on other manifolds that are diffeomorphic to the sphere using the results of Li et al. [35], although that will not be the focus of this paper.

---

Note that here we vary the bandwidth Tm so both fo and R(fo) will depend on the bandwidth as well as m. We will identify three different regimes of bandwidth scaling. We will show that the minimum norm interpolating solution exhibits either tempered or catastrophic overfitting, and we will argue that it almost always worse than the risk of the null predictor.
Theorem 3 (Overfitting behavior of Gaussian kernel in fixed dimension). Under Assumption 2, the following bounds hold for the predicted risk R(fo) of the minimum norm interpolating solution of Gaussian KRR:
1. If Tm = o(m (mm_+))) then R())= S lim inf i- Refo) < lim supm-to R(fo) < co. More precisely, if Tm I "-mmm="-- T'mt(m), where t(m) 0 m + co, then there a scalar ca that depends only on the dimension and my that depends on ((m) such that for all m > mo
we have R(fo)) > o² + (1 -ct((m) - |1
2. If Tm w(m d-1), then mimo R(fo) = co. Hence, for large enough m we have i((fo) > I((0).
3. If Tm O(m - then lim su R(fo)
co. Moreover, Suppose that Cim a I Tm I Cym air for some constants C1 and C22 then there exist 17, μ > 0 that depend only on d, C₁, and C2, such that for all m we have R(fo) > fll (1+n)o
Consequently, R((f) > i() as long as o² 1-1 |-
Theorem 3 shows that the minimum norm interpolating solution of Gaussian KRR cannot be consistent when data is distributed uniformly on the sphere, even with varying or adaptively chosen bandwidth. Additionally, in the first two modes of bandwidth change, the minimum norm interpolating solution never better than the null predictor. In the third case, the interpolating solution is worse than null for noise that not too small. This shows that even though the minimum norm interpolating predictor is classified tempered in the first and third cases of scaling of the bandwidth, it is still worse than the trivial null predictor. Note that our analysis does not exclude the possibility that for Tm ((m ) there exists small enough 0² for which the interpolating solution is better than the null predictor. We leave this as an open question. In Appendix A, we provide further empirical justification for Theorem 3.
4 Increasing dimension
For the case of increasing dimension, we consider the problem of learning sequence of distributions D(d) over X' y IRd x IR given by y ~ fi( &a using sequence of kernels (d)) Here, & is independent noise with mean 0 and variance 2² O. Formally, the kernel and the target function can change with the dimension d, but we will think of it as the same kernel and target with higher dimensional input. Furthermore, d will increase with sample size m, i.e. d d(m) (or analogously m will increase with d). A common assumption, which we also adopt, is that the projections of the target function få onto the eigenfunctions ((()) of the kernels (4)) are uniformly bounded [4, 64].
Assumption 4 (Target function and distribution in increasing dimension). Consider learning a sequence of target functions fä with sequence of kernels (d) Let the target function f have only Sa nonzero coefficients (where Sa can change with d), so fā Ei= ((()) 0; where o, are from Equation (1) and [3(4] < B, i.e.
Sa b| < B, for B that is independent d.
(d)
The functions that can be represented in this form depend on the number of nonzero coefficients, Sa- and the kernel that are using. In particular, for dot- product kernels on the sphere it includes all polynomials of degree & ka where ka is such that the multiplicities of first ky eigenfunctions are at most Sz. If Sa grows with d, then this set will include much more general functions. See Remark 14 for further discussion.
First, we will consider a general kernel K since Theorem 7 and Theorem 9 will apply more generally. Then, we will apply these results to the cases dot-product and Gaussian kernels.
The multiplicities of eigenvalues will play an important role in bounding the test risk, both from above and below, so we will introduce the following related notation.
5

---

Definition 5 (Lower and upper index). Let d be the k-th non nop-retcating eigenvalue of kernel K and let [kk) be its multiplicity, Let N₂ ( +.... + (Nk).. Let m be the sample size. Let km be defined as the maximal & such that there is less than eigenvalues with index k, i.e. km = max (k: E (1) + +................. N(k) < m) Define the lower index T. and the upper index Un as follows I = (1) + +................... (km)) and U (1) + .......... + NNmm + 1). When the dimension changes with sample size, we sometimes denote N (k) by k),
We will first state generic bound on the test risk for any data distribution, kernel with bounded sum of cigenvalues, sample size, and dimension. This bound will be informative when we scale the dimension d with sample size m, but it holds for any kernel that satisfies the following assumption.
Assumption 6 (Bounded sum of eigenvalues), Assume that the kernel K has a bounded sum of eigenvalues. i.e. there is a constant A such that Σi= (i)) S A. For a sequence of kernels K (d) assume that all such (4)) are bounded by some constant A.!
This is a reasonable assumption for most dot- dot-product kernels, as we show in Appendix C.4. also implicitly sets the scale of the kernel.
Theorem 7 (Test risk upper bound for kernel ridgeless regression). Let d and m be any dimension and sample size. Define Lm. Um. km N (i). N,. and Å as in Definition 5. Consider KRR with kernel K satisfying Assumption 6 for some A. Assume that for some integer the target function f* satisfies Assumption 4 with at most Nj nonzero coefficients. Then, the predicted risk of the minimum norm interpolating solution bounded by the following:
R(fo)) -
(1
Lm
7
o²
(3)
Um
+ B²
1
Lm
1
m
A
Σ
N
1 X2
(4)
m
Um
m
Alternatively, we can bound the risk using rem 20 in the appendix).
EL 2)) instead of (Eiz1 N(i) x
(see Theo-
We also establish a generic inconsistency result for any data distribution, kernel with a bounded sum of cigenvalues, sample size, and dimension based the upper and lower indices from Definition 5. We will further need to assume that the eigenvalues are bounded away from zero. Similarly, this will be useful when scaling dimension d with sample size, but it holds generally.
Assumption 8 (Lower bound on cigenvalues). Assumme that the kernel K has eigenvalues that are not too small, i.c. there is a constant b such that max,5km. km (2+)
m-hm For a sequence of < m- b
kernels K k((4,, assume that for the corresponding m = m(d) (since d = d(m),, we can also "invert" the dependence) all such ((4) are bounded below by some b.
This assumption will hold for most dot-product kernels and we will show it for Gaussian kernel in Appendix C.4.
Theorem 9 (Test risk lower bound for any kernel ridgeless regression). Let km and Im be as in Definition 5. Consider learning target function f", with some sample size Let K be kernel satisfying Assumption and Assumption 8 for some A and b Consider the minimum norm interpolating solution of KRR (with any data distribution) with kernel K. Then, for the predicted risk of minimum norm interpolating solution, the following lower bound holds:
1 b +++1
b
Tam m
R(fo)
(1-
0²
To apply Theorem for varying dimension d, we would additionally require that A is uniformly bounded for all dl and kernel ((d) and also that / = I(d) changes with d such that Assumption 4 holds with S. Nuay For dot- dot-product kernels ((d) on the sphere, if we let k(d) (a, y) ( (|| yl))-
Note that this assumption implicitly sets the scale of the kernel.

---

(0), so if (/44) does not change with d we can take A = h(O) (see Appendix C.4 for more details). Specifically, this holds for the Gaussian kernel on the sphere with A 1.
we will have A = sup, h(d)
To apply Theorem 9 the case of increasing dimension, we would require that the bounds Σ, (dd, S A and max;sk...
x
m -m hold for all d and kernels K(O, Usually, the
condition maxiskm (+) m-Lm will be satisfied for b = 1. We will show it for the two cases of yub-polynomillyy scaling dimensions with a Gaussian kernel. For the polynomial scaling dimension, it is reasonable to assume it for general dot-product kemels, discussed in Appendix C.4.
Now, we will show that using Theorem 7 and Theorem 9 we can recover the behavior of the minimum norm interpolating solution for polynomially increasing dimension [4, 64), i.e. tempered overfitting for integer exponent and benign for non-integer exponent. Here, we will need to additionally assume that the eigenvalue decay is not too fast.
Assumption 10 (Eigenvalue decay). The eigenvalues do not decrease too quickly, i.e. for km as in
Definition 5, we have that there is constant e such that maxisk.. (+) S c.V (km). For increasing
dimension, we require that maxiskm. increase).
cN((d for all m (i.e. all d, d and m both Xx
This assumption is stronger than Assumption 8, but as we show in Appendix C.4, it is reasonable for dot-pr not-product kernels on the sphere and even the NTK.
Corollary 11 (Dot-product kernels with polynomially increasing dimension, recovering the results of [24, 38, 40, 4, 64)). Consider the problem of learning sequence of target functions fī satisfying Assumption 4 with Sa (ddla)) with dot-product kernel K (xx, v) h[[1== -yl) with h(0)= on the sphere gd-1 (where h does not depend on d, i.e. A = from Assumption 6)) that further satisfies Assumption 10. Let d= ((1) for E (0, oo). Then the overfitting behavior of the minimum norm interpolating solution is benign a is not an integer and tempered if a is an integer.
Additionally, we will show that for d = log m, we cannot get benign overfitting, i.c. consistency with class of dot-product kernels the sphere. Similarly, as in the previous corollary, this will hold for any sequence where d = log m even only asymptotically.
Corollary 12 (Inconsistency with dot-product kernels in logarithmically scaling dimension). Let (dd) be a sequence of dot-product kernels on gd-1 that satisfy Assumption 8. Let the dimension d grows with sample size as d log, m (i.e. m = 2d). Then, the minimum norm interpolant cannot exhibit benign overfitting for any such sequence k(dd) i.e. there exists an absolute constant 7) such that for all d, m, R(fo)) > (1 + 7))
On the other hand, using Theorem 7, we will establish the first case of sub-polynomial scaling dimension with benign overfitting using the Gaussian kernel and data on the sphere. We will use = exp( /lo m).
Corollary 13 (Benign overfitting with Gaussian kernel and sub-polynomial dimension). Let K be the Gaussian kernel on the sphere gd-1 with fixed bandwidth, and take a sequence of dimensions and sample sizes m that scale as d = exp (Vlogm) (in particular, we take E N such that d = 2²' and m 2²d with Assumption 4 with Sa I m Then, we have that the minimum norm interpolating solution achieves the Bayes error in the limit (m, d) + sc. In particular, for d 2 4 and 2 16 we have
1,2,3...) Consider learning a sequence of target functions fā as in
R(fo) (1-1og log m
(1 exeexp (-0.89 m)
-1 o² + 2B2 1
m
Remark 14 (Allowed target functions). The set of allowed target functions fī in Corollary 13, i.. with sub-polynomial scaling dimension, is strictly larger than the set of allowed target functions for polynomially scaling dimension, as in Corollary 11 and [38, 4, 64]. In particular, for polynomially scaling dimension dt (1), the result holds only if the target function is polynomial of degree at most ax). On the other hand, Corollary 13 shows that sub- polynomilllll scaling dimension allows for the target function to be polynomial of arbitrary degree, well as non polynoooaai functions. In particular, in dimension d, we can represent polynomials of degree up to O(log" d).
7

---

Proofs outline
In this section, we discuss the main proof ideas. All formal proofs are provided in the appendix.
By Equation (2), to understand how the test risk of the minimum norm interpolating solution behaves, it suffices to understand how the eigenvalues corresponding to the kernel K and thus the quantities Eu, Lio behave. In Zhou et al. [66], the authors show that & is bounded both above and below in terms of the effective rank the systems of eigenvalue {イ} use this, along with directly bounding C.,..
defined by rh == E d A
We will
If K is dot-product kernel the sphere (such as the Gaussian kernel), we can take the eigen- functions Φj to be the spherical harmonics Yks. where 2 0 and s E [1, (d, k)]. Here (dd, k) [2k+-d2((k=-- 21 is the multiplicity of the k-th spherical harmonic. All YEs for the k]]
same k will have the same eigenvalue, which we will denote ÅR- In this case, we can write closed-form expression for the eigenvalues of Gaussian kemel, Åς. in terms of the bandwidth Tm and modified Bessel functions of the first kind I, (z) [46] (see Appendix D). Using the closed form of A and the multiplicities of cigenvalues, we can understand how the test risk of the minimum norm interpolating solution R(fo) behaves as m + co, which tells us its overfitting behavior.
Additionally, Eo appearing in Equation (2), will be informative. For example, if lim Eo > 1 then the overfitting cannot be benign. The following bound using the effective rank g holds [66]: For k m such that rx k m we have
h m
Eu <
1
1
(5)
k + Tk
For 2 m it holds that
Eo 2
(6)
m
k-m
1- E-m++re
Proof sketch of Theorem 3. We will focus on the lower bounds in this case, as the result is negative. The key clements to understanding the effective rank 7h and the test risk Equation (2) is to understand how the ratios of eigenvalues Ac+1 and the multiplicities (dd, behave. Using the A
closed form of the eigenvalues of Gaussian kernel and the properties of modified Bessel functions [46, 48], with some computation (see Theorem 28 in the appendix for the computations), we can derive the following bounds on ratios of eigenvalues
A6+1
T
d 2 2 (k +
+
(Is +
+
2
m
Auta for indices i and j using simple but long A
From these bounds, we can derive tight bounds on
calculations (see Theorem 28 in the appendix). If = I and j = then
d
s 1.
If
A
A s θ
i and j e (+)+) then deti Fm
O(1). If
Fin then
A de
for any
A
integer n E N (i.e. it deceases super-polynomialy). For N(d, 1) it holds that (dd O (1d-2) and
Ni : N (d, 1) + (d, O(1-1)). Therefore if is the index such that X = \ we have that i - (
For Tm 2 wm --),, we will take = (1 + 1 )m and show that r, omm). Then, the bound in Equation (6) will imply that & + /m, so from Equation (2), RR(fo) Ego² vmo² Note )m, have that i i= 0'm w Fm
vm
that for 1 = (1 + Vi
1 Note that for r/-1, we have that
Áito < =0(m)))(++(1), M- A4s < N(ddi) + Σ N(d,i+i)
1
8

---

since N(d,(+i) < ((d, ()d and A b
<
1. iu
So indeed rz-1 o(m) which implies ri = o(m).
For Tm o(m +t) and Tm ((m F.), we will directly analyze Equation (2). For is 0 (
we have that L > for all i S k. Let C; = d. Note that L, > L1 for i S k. Note that d
Autmo
(
1 L (N(d,1) + N(d >0 -
m Σ
L1.
Fm
So, we have that for all that L; < L1 < )
From Equation (2), we have that
2
R(FO) E Σ (1 p,) + Ego
Eo 1 +
m
|| || Ego?.
d-1
Tin
For Tm o(m=-1) this is sufficient. Additionally, by similar computation above, in this case, ri = (m), so Eo is bounded by Equation (5). For Tm Omm T-I), using Equation (5) and Equation (6), by showing that for / = ((m), ri = (()), we have O(1) > & 1 ((1).
Proof sketch Theorem Let &
__
Note that (1 (1-2i) 11-2,)²
2 (m)=
Then, Equation (2)
can be rewritten and bounded (with an abuse of notation for (i))
in(f)) Eo
Σ (dd 2.) + Ego² S EBB Σ ((d,
Kg (No + 2z)2
+ Ego
Note that [c))
3
d and also C. I
Therefore, have that R(fo) s
x
No
E ((d,)) i) x2
+ Ego². Note that m N(d, (dd &
so K0 < A Finally, to bound Eo, note that in Equation (5) we can choose k = L'm < m, then
ND
سا) Tk + Um m, so Eo S (1- m (m) (1- ma
Un Combining these with Ko gives the claim of Theorem 7. The proof of the alternative bound harder and will be delayed to the appendix.
Proof sketch of Theorem By Theorem from Zhou et al. [66], if le is the first k < m such
that k + brk 2 m, then Eo 2 1 -
(1-(
k Since max (1)
m Lm for I <
b+
b
(d, 1) +). (d, kim), we have that br. 1 S N(d, +)+... ...... N km 1 b maxiskm 1
Im + m - I.m I m, so the first I for which rı + I > m is = Iim = N 1) + .... + N N(d, kmm)
Plugging in k Lmn we get that Eo 2
b
Lm
from Equation (6), we have
b+1
m
Ri(S))
6
Lm
02
b+1
Proof sketch of Corollary 11. Note that analogous proof holds for any d for constant but we take equality for simplicity. If l is a constant, i.c. it does not change with the dimension, we have that N (d, k) (d*)). Therefore, km |a] if a: is non-integer and 1 if is an integer.
If a is non-integer, then Lm N (d, km) + ... (d, 1) (dd and Um (d, Km + 1)
+ N (d, 1) +ddl)++1). So we have that Lm d || T... d -al-- (d, [a]) = d|ai Note that km = [a]. We have from Assumption 10 that maxıskm.
1 = O(N (d, km)) Note X.
that Theorem holds with (E'n, (d. 2) instead of (Ei=1 N(d, ) Therefore, we have

---

m maxiskm (d. - 0(d(2la) 220)). This gives
R(fo) - (1- -llooo (1 (1- 1000--(o)-1)-- o²
+0 B² -ddll-a) (1- (1- d(2(a)-20)
Therefore, limm- R(f()) = 0². So, a is not an integer. we get benign overfitting. If a is an integer, note that N (d,1) ..... + NN, a 1) o (d so km
Then there are Cu. CJ (0,1) such that a < Lm S Ca < 1. So, Theorem 9 holds for b 2.2 so R(ff)) - This shows
m
that lim inf Rd (b) 2 T > 0². The upper bound follows as above. Since we assumed that maxçskn 2. = ( km))) and maxiskn (d, = N(d, = ((d"), we have that Σmm i) O(d2ar), ) 80
R()o) S (1 ca) (1-
(1 (1-(1-dd)))))
So, we conclude that for integer a we have tempered overfitting and for non-integer a we have benign overfitting, This recovers results of Ghorbani et al. [24], Mei et al. [38], Misiakiewicz [40], Barzilai and Shamir [4], Zhang et al. [64].
Proof sketch of Corollary 12. Note that this holds for any scaling of d and m where d = θ (log m). but we take this particular one for concreteness. As we show the appendix (Theorem 21), is not hard to see that L. & aym for some constant og < 1 and Lm s amm for some constant Qu > 1. Theorem implies that we cannot get benign overfitting this case, i.e. for all m, R(fo)= > (-(r)))aa o². o² This shows that lim inf m- R(fo)) 2 (Gftr)) o² > o².
Proof sketch of Corollary 13. We have that for the Gaussian kernel on the sphere, Theorem 7 holds with A = (see Appendix C.4 for further details). First, we will compute km and hence L.n. and Un- After some tedious calculation (Theorem 23 in the appendix), we see that for k < 2 + 1
have (d,, 1) +.... + (dd, k) o(m), but for h 2 + / we have Nd,, 1) + ((d > m. This shows that km 2 + 1 and so again after long calculations Lm = O log and - 2itd itd-2 o(N(d, i 1)) (take h < d), so it suffices to estimate N(d, k) x
Um > (mmd9.89). To estimate Σi= (d,, i),,, note that eigenvalues are decreasing and iN i)
(d, 1 2i+d-2 i+1
Now,
from Equation (7) and an estimate on the size of the first eigenvalue (Corollary 31) A₃ O fixed a > 0, we can estimate the size Ån. We have that
do ), for
<
( +
(Tm)
2 mm
< (k(++))
A T
for arbitrarily small e. For ls have that m < (d, k) < m and d < m So E/m ((d, 1) 1/2 <.. Plugging these back into Theorem gives the desired result.
7km
from additional calculation (Theorem 23 in the appendix),
24
Summary
In this paper, we considered the minimum norm interpolating solution of kernel ridge regression in fixed dimension with Gaussian kernel and varying or adaptively chosen bandwidth, and in increasing dimension with various kernels. In fixed dimension, we showed that if the source distribution is uniform on the sphere, then the minimum norm interpolating solution is inconsistent for any choice of bandwidth, and usually worse than the null predictor, except possibly in one particular scaling of bandwidth and with small noise. Furthermore, we showed general upper and lower bound on the test risk, which we applied in the case of increasing dimension to recover the currently known results about polynomially increasing dimension and show two new results: We showed that no dot-product kernel on the sphere can achieve consistency for logarithmic scaling of the dimension, and obtained the first case of sub-polynomially scaling dimension where the minimum norm interpolating solution exhibits benign overfitting, namely with Gaussian kernel and dimension scaling d = expl Vlog m).
10

---

Acknowledgments and Disclosure of Funding
We would like to thank Theodor Misiakiewicz and Sam Buchanan for useful discussions.
This work was done as part of the NSF-Simons funded collaboration on the Theoretical Foundations of Deep Learning (https//deepfouddaaiossssl and primarily while GV was TTIC. GV is supported by research grants from the Center for New Scientists at the Weizmann Institute of Science, and the Shimon and Golde Picker Weizmann Annual Grant.
References
[1] Francis Bach. High-dimensional analysis double descent for linear regression with random projections. arXiv preprint MrXiiv2303.01372 2023.
[2] Peter L.. Bartlett and Philip M. Long. Failures of model-dependent generalization bounds for least-norm interpolation. The Journal of Muchine Learning Research, 22(1):999--3111 2021.
[3] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overtitting in linear regression. Proceedings of the National Academy of Sciences, 117448)3300033300700 2020.
[4] Daniel Barzilai and Ohad Shamir. Generalization in kemel regression under realistic assumptions. arXiv preprint 2xx.:23312.15992 2023.
[5] Daniel Beaglehole, Mikhail Belkin, and Parthe Pandit. On the inconsistency of kernel ridgeless regression in fixed dimensions. arXiv preprint MXXi:2205.13525, 2023.
Mikhail Belkin, Daniel Hsu, and Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4): 167-11800, 2020.
[7] Blake Bordelon, Abdulkadir Canatar, Cengiz Pehlevan. Spectrum dependent learn- ing curves in kernel regression and wide neural networks. International Conference on Machine Learning, PMLR, pages 1024-1034, 2020.
[8] Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model aligument explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12(1);
1-12, 2021.
[9] Yuan Cao, Zhiying Fang. Yue Wu, Ding- Ding-Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning, arXiv preprint arXiv:1912.01 198, 2019.
[10] Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for over- perapaarmettrizee maximum margin classification on uub-gaussian mixtures. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[11] Yuan Cao, Zixiang Chen, Mikhail Belkin, and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. arXiv preprini arXiv:2202.06522 2022.
[12] Niladri S. Chatterji and Philip M. Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Revearch, 1 -30, 2021.
[13] Niladri S. Chatterji. Philip M. Long, and Peter L Bartlett. The interplay between implicit bias and benign overfitting two-layer linear networks, arXiv preprint arXiv:2108. 11489, 2021.
[14] Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv preprint a7X0v.2210.08571, 2022.
[15] Tin Sum Cheng, Aurelien Lucchi, Anastasis Kratsios, and David Belius. Characterizing overfitting in kernel ridgeless regression through the eigenspectrum. arXiv preprint arXiv:2402.01297, 2024.
[16] Geoffrey Chinot and Matthieu Lerasle. the robustness the minimum & interpolator. arXiv preprint a0Xiv:2003.05838, 2020.
[17] W. J. Conover. Practicul Nonparumetric Statistics. Wiley Series in Probability and Statistics, 1999.
[18] Konstantin Donhauser, Nicolo Ruggeri, Stefan Stojanovic, and Fanny Yang. Fast rates for noisy interpo- lation require rethinking the effect of inductive bias. In International Conference on Machine Learning (ICML), 2022.
11

---

[19] Mona Eberts and Ingo Steinwart. Optimal regression rates for syms using gaussian kernels. Electromic Journal of Statistics, page Vol. 7 1-42, 2013.
[20] Spencer Frei, Niladri S. Chatterji, and Peter L. Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. Conference on Learning Theory (COLTT), 2022.
[21] Spencer Frei, Gal Vardi, Peter L Bartlett, and Nathan Srebro. Benign overfitting linear classifiers and leaky relu networks from kki conditions for margin maximization. arXiv preprini arXiv:2303. 01462, 2023.
[22] Amnon Geifman, Abhay Yaday, Yoni Kasten, Meirav Galun, David Jacobs, and Ronen Basri. On the similarity between the laplace and neural tangent kernels. arXiv preprint arXiv:2007.011800 2020.
[23] Erin George, Michael Murray, William Swartworth, and Deanna Needell. Training shallow relu networks noisy data using hinge loss: when do we overfit and is it benign? Advances in Neural Information Processing Systems, 36, 2024.
[24] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 4292):10 2021.
[25] Nikhil Ghosh and Mikhail Belkin. A universal trade-off between the model size, test loss, and training loss of linear predictors. arXiv preprint arXiv:2207. 1621,, 2022.
[26] Moritz Haas, David Holzmüller, Ulrike von Luxburg, and Ingo Steinwart. Mind the spikes: Benign overfitting of kemels and neural networks in fixed dimension. 37th Conference on Neural Information Processing Systems (NeurIPS 2023), 2023.
[27] Trevor Hastic, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high nigh-dimensional ridgeless least squares interpolation. arXiv peprint arXiv:/903.00mm 08560, 20200,
[28] Hong Hu, Yue M. Lu, and Theodor Misiakiewiez. Asymptotics of random feature regression beyond the linear scaling regime. arXiv preprint urXiv:240..081660,, 2023.
[29] Nirmit Joshi, Gal Vardi, and Nathan Srebro. Noisy interpolation learning with shallow univariate relu networks. arXiv preprint MxXi:2337.113940 2023.
[30] Peizhong Ju, Xiaojun L Lin, and Jia Liu, Overfitting can be harmless for hasis pursuit, but only to a degree. Advances in Neural Information Processing Systems, 33:7956-7967, 2020.
[31] Kedar Karhadkar, Erin George, Michael Murray, Guido Montúfar, and Deanna Needell. Benign overfitting in leaky relu networks with moderate input dimension. arXiv preprint arXi::2403.06903 2024.
[32] Frederic Koehler. Lijia Zhou, Danica Sutherland, and Nathan Srebro. Uniform convergence of in- terpolators: Gaussian width, norm bounds, and benign overfitting arXiv preprint 0rX2222006.09266. 2021.
[33] Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in relu neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[34] Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting for two-layer relu networks. arXiv preprint arXiv:2303.04145, 2023.
[35] Yicheng Li, Zixiong Yu, Guhan Chen, and Qian Lin. Statistical optimality of deep wide neural networks. arXiv preprint arXiv:2303 02657, 2023.
[36] Tengyuan Liang and Benjamin Recht. Interpolating classifiers make few mistakes. arXiv preprint arXiv:2101.11885, 2021.
[37] Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakki- ran. Benign, tempered, or catastrophic: A taxonomy of overfitting. arXiv preprint 2oXiv:220700666900 2022.
[38] 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.
[39] Xuran Meng, Difan Zou, and Yuan Cao. Benign overfitting in two-layer relu convolutional neural networks for xor data. arXiv preprint 23X1022110.01975.200 2023.
12

---

[40] Theodor Misiakiewicz. Spectrum of luner-produs kernel matrices in the polynomial regime and multiple descent phenomenon in kemel ridge regression. arXiv:2204. 10425, 2022.
[41] Theodor Misiakiewicz and Basil Saced. A non non asymptotic theory of kernel ridge regression: deterministic equivalents, test error, and gev estimator. arXiv preprint arXiv:2403. 08938, 2024.
[42] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime. Preprint
2023.
[43] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 2020.
[44] Vidya Muthukumar, Adhyyan Narang. Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Docs the loss function matter? Journal of Machine Learning Research, 22(222):1-66 2021.
[45] Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform convergence: General- ization via derandomization with an application to interpolating predictors. In International Conference on Machine Learning, pages 7263-7272, 2020.
[46] Minh Ha Quang and Yuan Yao. Mercer's ' theorem, feature maps, and smoothing. Conference: Learning Theory, 19th Annual Conference on Learning Theory, COLT, 2006.
[47] Alexander Rakhlin and Xiyu Zhai. Consistency of interpolation with laplace kernels is a nigh-dimensional phenomenon. arXiv preprint arXiv: 1 2018.
[48] Javier Segura. Simple bounds with best possible accuracy for ratios of modified bessel functions. arXiv preprint arXiv:2207.0271333. 2023.
[49] Ohad Shamir. The implicit bias of benign overfitting. In Conference on Learning Theory, pages 448-478. PMLR, 2022.
[50] James Simon, Madeline Dickens, Dhruva Karkada, and Michael R. DeWeese. The eigenlearning framework: A conservation law perspective on kernel regression and wide neural networks. arXiv preprint arXiv:2110.03922. 2021.
[51] Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
[52] Christos Thrampoulidis, Samet Oymak, and Mahdi Soltanolkotabi. Theoretical insights into multiclass classification: A high-dimensional asymptotic view. Advances Neural Information Processing Systems, 33:8907-89777 8920, 2020.
[53] A. Tsigler and P. L. Bartlett. Benign overfitting ridge regression. arXiv peprint arXiv:2009. 2020.
[54] Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum 11 noom interpolation of noisy data. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
[55] Ke Wang and Christos Thrampoulidis, Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting and regularization. arXiv peprint arXiv:2011.09 1.09148, 2021.
[56] Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis. Benign overfitting in multiclass classification: All roads lead to interpolation. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[57] Alexander Wei, Wei Hu, and Jacob Steinhardt. More than a toy: Random matrix models predict how real- world neural representations generalize. In International Conference on Machine Learning, Proceedings of Machine Learning Research, 2022.
[58] Denny Wu and Ji Xu. On the optimal weighted 6a regularization in overparameterized linear regression. Advances in Neural Information Processing Systems, 33: 101 12-10123, 2020.
[59] Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue M. Lu, and Jeffrey Pennington, Precise learning curves and higher-order scaling limits for dot product kernel regression. arXiv preprint: arXiv:2205. 14846v3, 2023.
[60] Xingyu Xu and Yuantao Gu. Benign overtitting of soo-hh neural networks beyond lazy training. In International Conference Artificial Intelligence and Statistics, pages 11094-11117, PMLR, 2023.
13

---

[61] Zhiwei Xu, Yutong Wang, Spencer Frei, Gal Vardi, and Wei Hu. Benign overfitting and grokking in relu networks for cluster data. arXiv preprint arXi::2310.02541, 2023.
[62] Zhen-Hang Yang and Yu-Ming Chu. On approximating the modified bessel function of the first kind and toader-qi mean. Journal of Inequalities and Applications, 2016.
[63] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations 2017.
[64] Haobo Zhang, Weihao Lu, and Qian Lin. The phase diagram of kernel interpolation in large dimensions. arXiv preprint 12w-274.4...57v1. 2024.
[65] Lijia Zhou, Frederic Koehler, Pragya Sur, Danica J Sutherland, and Nathan Srebro. A non-asymptotic moreau envelope theory nigh-dimensional generalized linear models. arXiv preprint arXiv:2210.20082, 2022.
[66] Lijia Zhou, James Simon, Gal Vardi, and Nathan Srebro. An agnostic view on cost overfitting (kernel) ridge regression. arXiv preprint arXiv:2306. 13185, 2023.
14

---

A Empirical Justification
200
60
sced proditor ar1
20-
(a) Tm o(m - with o² = and d 6. We that the test tends to something that is equal to larger than the test risk of the null prodictor.
20000
rebio lnvel
raail prodictor SITO
3500C
(b) Tm = wmm ~ with x² 10 and d We see that the test error is increasing with the sample size m, suggesting that the test error diverges to infinity.
3800C
380CC
34002
3200C
3000C
2000
4330
4007
5000
10000
(c) 7m = O(m -=T) -==) with o² 10000 and 6. We see that the test error is well above the risk of the null predictor.
Figure 1: We plot the dependence of the test enror of the Gaussian kernel ridgeless predictor for y= fx) + E, with & (N0 o²), f" = 10, x ~ Unif(Sd-11) and o² and d as above, and sample size m. Light blue lines represent the test error for 100 different runs of the experiment and dark blue the mean all those runs. The red dotted line is the noise level o² and the yellow dotted line is the error the null predictor achieves in this setting. We see that the test error concentrates around its mean and that the behavior is as predicted by Theorem 3.
In this section, we provide empirical justification the predictions of Theorem 3, which deals with the case of fixed dimension. Figure/ 1 shows the dependence of the test error the sample size for the Gaussian Kernel Ridgeless prediction with varying bandwidth, as in the setup of Theorem Specifically, consider y = (x) + where & N o2), 10, o² is the noise level, and
15

---

~ U We vary the values of d and o² and the bandwidth scaling Tm as follows: for Tm o(m 2-1) we take o² and 6, for Tm w(m --=r)) we take o² = 10 and for Tm = (m = we take x² = 10000 and d = 6. We compare the test error (light blue) and of the experiment (dark blue) with the noise level (the Bayes risk; red) and the risk of the null predictor (yellow). We see that for all three cases, our predictions agrec with the experiments, that is, in the case Tm o(m क the test error is eventually above the null predictor error but finite, the case Tm w(m a-1) the test error increases with sample size, and in the case Tm = ( - the test error is above null predictor emror The code to reproduce these experiments can be found
and
the mean of the test error for 100 different
attpa://github http//aakk-eddveeevvveeeeeeeeese wewaogobbbbvv-----e-ee www.ooo-gggu-----eeeee aan--ennl-------e--ee wewernee-riigggle----eeee
We ran the experiments on one A6000 GPU.
Statistical significance of experimental results: In Figure and Figure 3, we present evidence for the statistical significance of our experimental results. We examine whether significant mass of the distribution of the mean of the test loss, L, exhibits the same behavior L. We use 50 of the 100 experiments to estimate an interval [Trow: Tnigh] and the other 50 to test whether this interval contains p = 0.8 of the total mass of the distribution of a 0.05 significance level. Figure 2, we plot Lho and Lnigh. the dark blue lines. We perform one lower-tailed and one upper-tailed test [17]. The
null hypotheses are: - 1- population quantile is greater than Liggh and -_ population quantile at least as great as Loo-- Indeed, both Low and Lighh have the desired behavior. Furthermore, in Figure 3, we report the relevant test statistics, Ti which is the number of draws of T. no greater than Lrigh and 7.2 which is the number of draws of L less than Law- 41 and le are the minimum numbers such that P(Y S (4) variables with parameters and = 50. The leftmost bar plot compares Ti and é1, the middle bar plot compares 722 and l2, and the rightmost bar plot shows the p-value and the significance a. To accept the null hypothesis we need 7i > 1, T2 I 12, and high p-value. We report an aggregated p-value. We accept the null hypothesis in both cases the test statistics T₁ and T2 satisfy the required conditions and the p-values are high.
and P(Y < f22)
a, where Y is binomially distributed random
Overall. conclude that the prediction of Theorem 3 agrees with the empirical observations that are statistically significant.
16

---

80-
Maricce antiratt
Mas how solndde
nome
44
(a) Tpx. ( 2-1
with o² and d = 6.
5000
las sabmett
1032
5000
5900
1003
(b) w(m d-1
with o² 10 and d = 4.
38002
Mos los entretts
node
3000C
5000
200m
11200
(c) Tm O(m a=1) with 0² 10000 and 6.
Figure 2: For each of the setups of Theorem 3, we plot the dependence of the estimates for the minimum and maximum of the error of the Gaussian kernel ridgeless predictor Laow and Lnigh for y - (x) + E, with Ç ~ N(0,o")) f" 10, æ ~ Unif(S and o² and sample size The red dotted line is the noise level o² and the yellow dotted line is the error the null predictor achieves this setting.
above, on the
dark blue, we plot estimates for the minimum and maximum of mean test eπrо Loow and Lnigh for given sample size. We test whether [Loo Lnghh] contains p = 0.8 the total mass the mean test error L.
17

---

Camporien al
Freegttor 2
Camperion sysiiraze Inaal
A
Tm m
with o² = 1 and d = 6.
camparioon syyttonze
2000
600
1000
400
(b) w(m a-1 with o² = 10 and d = 4.
Cemperiosn awer
Compastter of 200122
Carqurioonal passesant systtorce lase
1000 mamm
Sames
(c) Tm O(m
# with 0² 10000 and 6.
Figure 3: For each of the setups of Theorem 3. we test the statistical significance that p 0.8 of the probability mass of L., the test error, is inside [Toow; Tnugh] at a = 0.05 significance level. In the leftmost plots, we plot the dependence of the test statisties Ti and t sample size m. Ti is the number of draws of the test error L no greater than Lnigh and f is the minimal number such that P(Y < (1) = In the middle plots, we plot the dependence of test statistics T2 and (2 sample size m. T2 is the number of draws of the test error L less than Liw and l is the minimal number such that P(Y < t²) 1 a. Here Y is binomially distributed random variable with parameters p and n = 50. On the rightmost plots, we show the dependence of the aggregated p-value on the sample size m. We accept the null hypothesis in both cases because Ti > t1 T2 I t2, and the p-values high.
B The case of fixed dimension
Cost of overfitting The cost of overfitting, introduced in [66], is defined as the ratio of the test risk of an interpolating solution and the test risk of the optimally regularized solution. It measures how worse off are we interpolating rather than regularizing.
18

---

Definition 15 (Cost of overfitting). Let fo- be the optimally regularized solution, i.e.
R(fo-) inf R R(ffs).
820
For distribution D over X' x IR, we will define the cost of overfitiing C(D,m)
R(fu)
C(D, m) = R(fo-)
Zhou et al. [66] show that agnostically to the distribution D, the behavior of the cost of overfitting is tightly controlled by the effective ranks of systems of eigenvalue {>:);=1 of given kernel (coming from Mercer's theorem)
Eis++1 A
Cii A.) 2
and R4
Ak+1
Linkt1 X
We will assume additionally that the eigenvalues are nonzero, T& and R₂ are well defined on N. Since we chose that the eigenvalues are sorted and since they square summable, we have that
Fk S R S r
The following two results of [66] summarize how we will use effective ranks to control the cost of overfitting. Proposition 16 gives necessary and sufficient condition for the overfitting to benign in terms of the cost of overfitting, i.. that C(D, m) + 1, in terms of effective ranks.
Proposition 16 (Necessary and sufficient condition for benign overfitting [66]). Let kn be the smallest integer k E NU {0} for which n < k + rk. Then E + 1 if and only if
kin =0 and lim n = 0. 120000
lim 71-000
RR.
Proposition 17 gives sufficient condition for R(fo)) oc in terms of effective ranks. Proposition 17 (Sufficient condition for catastrophic overfitting [66]). Let >> and let k = (1++)m. If Timm F then & -> oo, i.e. the overfitting is catastrophic.
Using sharp bounds on eigenvalues {A:) derived in Theorem 28, we can derive bounds on effective ranks so that we can apply the results of [66] and Equation (2) to bound the test risk of minimum norm interpolant.
When the input is distributed uniformly on the sphere. the eigenfunctions {øx} in the Mercer decomposition of the kernel function can taken be the spherical harmonics Yks- Using the Funk- Hecke formula we can find the closed form of eigenvalues for the Gaussian kernel [46], which are given in terms of bandwidth Tm and modified Bessel function of the first kind I, In Appendix D, we will derive bounds on the sizes of the eigenvalues using the properties of Bessel functions and their multiplicities.
We need to take a particular input distribution, in order to able to compute the eigenvalues explicitly and to know their multiplicities. The result of Cao et al. [9] offers one possible way of generalizing our result to more general different distributions
We split the proof into two parts. First, we will bound the cost of overfitting. Then, we will provide lower bounds on the test risk of Gaussian KRR.
Bounds on cost of overfitting The bounds on cost of overfitting will be used to show whether the test risk bounded above or away from Bayes risk.
Lemma 18 (Cost of overfitting for Gaussian KRR). Let N' ~ U Then the following bounds hold for the minimum norm interpolating solution of KRR and its cost of overfitting C(D, m) and Ey:
1. If Fm I m I'1 f(m), where t(m) + as m + co then there is a constant Ct that depends d and C, such that
1 m
-2 (1- (1-C(t(m)
< C(D, m) S -
19

---

2. Tm 2 m ==(l((mm where ((m) + 0o - oc then there is integer mh depending on d and ((m) such that for all 2 mg
& m.
3. If Cim Cim= C1 C2 and d such that
S Tm S C2m उं then there exist constants C₁ 0 and Cir depending on
C(D,m) S C₁
&q 2 1 CTI-
Proof. We will break down the proof into the proof of the three parts.
Part I: We will use Proposition 16 to prove this that &g + 1. We can see the upper bound on Eg
from Theorem [66]. We have that for m
k
111
Eo -
1
R
Now we will show that for l: = 1, we have that k + Tk >> m and limm
m
O. This implies that
Ri
conditions of Proposition 16 hold so Eo 1. We will rewrite Th Evst
using X. We have that
Ao+1
Σi>1 A = idd + Σ N(d, d2
A1ti
dis
1=1
where N(d, d, so i =1 1 and Ñ(d, 1) d - 1. Therefore, we have
A1ts X
r1 = (d 1) + N(d, 1 +
Let T Therefore, we have that
= Taking
vTy(m) 2
Sj S (Tg(m)) 1, we can apply the bound Theorem on
Aits
A
exp(-5g(mm) < Ártá X1
< 1.
dtts d
In particular, we have that for m large enough, for all such j holds that f1, this means that
Going back to
Aits
= (d- 1) + Σ
(d, j)
Nn
==l
VTg(m)
d
VTy(m)
Σ
N(d, 1 + 1)
Σ
(1+
2
3 (Ta(m)
1= TTm(m
VTg(m)
2d41 (VTg(m))&-2
TT(mm) 5
2d (VT (Tg(mm))
j= j= (Tg(m)
2 (VTg(m))
1
If (Tg(m) is not an integer, we can take its integer part and add small constant since gTg(m) will be large. Note that Fm S x'r f(m), so
1
T >
l(m)²
20

---

Therefore
1 r 1>>22(T/gg) (VTg(m))dd 1 m g(m) ((m)
d-1
g(m) t(m)
d-1
g(m) so as long as f(mj + oc, ri > m for m large enough. We can take g(m) = v f(m). Then, in
Proposition 16, we can select ki = 1, since + > m for large enough m. Note also that Rt 2 Ti.
so we also have that R1 2 ri m [g(m) f(m)
s0
m m-+00 R1
lim m 7- m
and
lim
O.
This finishes the proof of the first claim.
Part 2: Let Tm 2 m (mm). where t(m) + oo as m + co. We will use Proposition 17 to prove this claim. Using Theorem from [66] we know that for any >> 0f o(m) for k (1 + s)m then the following bound holds
Eo
2
1+
k-m m-m+Tkk
E
We will show that there is constant U > 0 such that for any t: 2 we have that
2
rk I Um
((m)
By Theorem 28, we have that for j 2 (Tg(m) where g(m) - oc as m + op that
Aits exp (- g(m)²
Let (1 E)m. We have that
DD
Aatss d
Tk -(d,k)) Σ
N(d, k
Now, if we take j jo = VTg(m), it holds that
X A
< eep(( g(m)
Therefore, we have that
dits
Th = (d, +
N(d, k +)
dx
i-1
Ao+ +
N(d,k) + Σ
N(d, To +
Σ
Ndd,
+
N(d, k + 1)
Note that by Theorem 28, for j 2 (Tg(m)) we have that
N X < exp (- [2((m)))
21

---

Note also that this bounds holds for all simultancously. Therefore, we can write
Aets
Tk I nnJ
nuja-1
d-1 +
N(d h: + +)
d;
j=
Aktl++s
nna
jd-1
+
Nd. +
d
1=1 s=1
S nna
d-1
N(d, (1+1
s=1
exp( (m)((m)
(1+ 1) -
1 1
S nod
4
1=1
[(()
d-1
S m
nu +
Σ
(1 + 1)d-1 exp(
- 4
((m)
1=1
g(m)
d-1
S Um
=(m)).
((m)
Second to last inequality is true because g(m) + as co. The last inequality follows from the fact that Ei (1 + 1)d-1 exp(- bounded by constant. Note that the bound is independent of k. so we can vary & with m as well. If we choose vm the desired result follows.
Part 3: Let Cim प S Tm S C2m
Note that the following two bounds hold for Eo [66]:
1. For & < m such that rk + k > m
-1
(1
m
-1
Eo <
1
m
k + Tk
2. For k 2 it holds that
m Σ
Liss 2
k
k m + vk
Note that in this case cim S VT = = S E-ma-, where dg = =vva
(and similarly for
c7
indices and 2 swapped with inequalities reversed).
Theorem 28 shows that for is such that < (KVT), we have that for X, holds that
KVT
A A1
exp(-k?).
1
VT
Take i (1 + e)m. We want to show that there is a constant > that depends on the dimension d and the constant C such that
Fk S Bm.
Let k ((1 (1++)m))+ Note that by an analogous proof to Theorem 28, we have that for the size of cigenvalues it holds
Pits <
T
1 - 2 2
22

---

For th S S (1+ 1)k, we have that
Akts A
4
d+1bk
T
T
- 1 + - 5
+ ((1 + 1)k)
T ((1 + 1)k)
We have that k = (1+E) cm J (1+e) ग. /T = T 2 (1+e) ग.. Therefore, we have that
Aitt <
T
0+11
T
(1-)ay/
(1+ 1)
T
- exp
2
T (11+
T + ((1 1)vVT)
4
as m + 00 i.c vT + co. Therefore, for m large enough, for all we have that if (b S j S (1 1)k then
A S (1+ 1)d+2'
1
The last inequality is true because we can take m large enough so that T and y are both greater than 400d. Then we have that for all
doti < +++((+DaVT))
T
(1+1)100d
d
1
I+1 100d
(I ()d+2++2
The last inequality holds because of the following
[
++1 ((+1)100d
[+1)
d+2
(1 + 1)100d
> (1 + 1)
(100d) (100c)at2 > (1+ 1)at2.
1
100d
100d
d+2 2
Therefore, can bound ra follows
rk Eish dE d
8 N(d,k+ +
Aats
kdd
Xi
Aitts
<N(,,)) +
N(d,k +
< xk))a=2
> ((1+1)A) (1+ 1)d+2
X
1=1
8 Σ (1+1)4
< C(1++)m.
Therefore, applying claim 1, we have that h: + Tk < (C(1 +e) + E)m, we have that (1+5)s )-1 > 1.
lm- > (c(++))+e)> so follows that E, > (1 (c(++))=))
k-miry
Note that the above proof actually shows that for any kn S k. we have that Fhg S Cm. Now we want to show that is lower bounded and that we can take h < such that k + r3 m. Again apply Theorem 28, we can generalize
K/T
A Å
2 exp(-k2).
1+
to other ratios as well. Let j < TvT and let l. T Si S (k: + 1)vT. Then we have that
(K+1)TT
1
> 2k(k - 1)).
1 +
VT
23

---

Note that em S & = S Emmai,, where 62 (and similarly for indices and
swapped with inequalities reversed). Therefore, we have that the following bound holds rie for any < m.
Eised (id, (k: +1) AR+1
X (aFt)t
Σ Ndd, 1) +)
)a+1)
j=1
Note that since VT 2 emm then NT 2 n((d) so - 1 - Therefore, we take
j
k,
. and any IVT Si (1 1)VT, we have that (since exp(-21(1 + 1)) <
of
n,
exp(-12))
1 ス exp(-21((1) 1)).
2
Note that there is at least N N(+IJTT that
NIT 2 ni (1+ (1+11)--1 (d-1) 1) m such indices have
Eishi d
sait))t )1o7
[dd (K: + + Σ
N(d, (k. + +)+
Th
Abt1
N(d, i) d₁
E
d
WTSIS(+1)VT where 3 = n1 ((1 - nu 11 11-1 exxp 21(1 + 1)) > 8m,
exp(-2210 1)). Note that B is independent of k, so in particular for 1e = (1 - B/2)m, we will have rx + > m. Therefore we can use the upper bound on Eg to see that
22 & - 82 (1 + 3/2).
Since only depends d and C and C22 this finishes the proof.
In particular, Lemma 18 shows that when Tm = o(m o(m==TT) or Tm w(m AT), then lim sup (R)f)) I cc.
Lower bound for the test risk of Gaussian KRR Now we will show lower bounds for the test risk of Gaussian KRR.
Lemma 19 (Lower bound for the test risk). Under Assumption the following bounds hold for the risk fo) of the minimum norm interpolating solution of Gaussian KRR:
1. If Tm o(m 1o(m--ary * then R(0) < lim inf R(fo) S lim supm-400 R((fo) co. More precisely. if Tm I m + a where t(m) + 0 as m + oc, then there a scalar ca that depends only on the dimension so that for all such t(m) there is mo that depends on t(m) such that for m > mg we have R(ff) o² + (1 - cal(m) - ( ||
2. Tm = w(m - 2 ), then limm-+00 R(fo)) oo. More precisely, Tm m a-r t(m). where t(m) +
oo then there is integer my that depends on the dimension and t(m) such that for m > mo. we have that
(R(fo) + vmn(o²) (note that i2(0) is bounded). Hence, for large enough mn we have R(fo) > R(O).

---

3. If Tm ammm==) then lim suPm- R(fo) < oo. Moreover, suppose that Cim= I Tm I C2m यंं for some constants C1 and C2. then there exist 77, μ > 0 that depend only on d, C1, and C22 such that for all m we have R(fo) > fl (1+m)o²
Consequently, R(fo) > R(0) as long as o² - 1 11
Proof. All three proofs will similarly follow by directly analyzing Equation (2).
Part 1: Note that for any we have that À K0 S d Kip, we have that Lu 2 4. L1. From Theorem 28 we know that for j S vTt(m))+ $ we have that
exp(-t(m)),
so there is my that depends on t(m) such that for all m mo
1 A 2 2 2
for all is VT Therefore we have that
m N(d,i) (N(d,1) ((d vT((m))) ((d.VT(m))) c1.
Note that (d 1) +) +... N(d, vT((m))) > 11 (VT((m)#)* = (m(((mm) = where of = 22g. Therefore, we have that L1 < (t(m)) - Therefore, we have that
(1- (1 21- 22) > (1 2 (1m)))
2
From Equation (2), we have that then
iu(ffo) 2 Egg² + Eo cal(m) - |1
This shows the first claim.
For the second part, note the following property of Li.5 Arting' if for > i, we have that
Li,5 Lg.5. Let X > for some fixed > 0 and j > i, then we have that
Cj8 > cCi.5.
By Theorem 28, we have that for S VT (m)) with g(m) + 0 as m + oo
Àits
> e-p(mg((
b
So there is m mn such that for m > m00
exp (-5g(m)) > 2
\j
Note that
m
L? (1 23,6)² > 1 if
00
1=
C mL,,5 (2 C,,6)
1=1
25

---

For this it suffices to have
Σ fi mL1,8 (2 L1,8), 1=1
since Lis are decreasing.
Note that there is at least (d, + ... + N(d, (dd.V))())) >
d-1 of indices such that
m(VTg(m)))d > cam
giml 1(m)
x 1 2
A
Therefore, if we select g(m) = [(m), then we have that
+
E
2 2cum
1
-L1188
(2 -
t(m)
This implies that for all j simultaneously
>
171
1.8
This translates to
R(fa) R(0)
C. 0².
1 1
m
This finishes the proof of the first part.
Part 2: Note that we showed that for large enough, Eo mm. This shows that
R(fo) = Eo
Lu) + o²
/mo²
So, there is my that depends only on (mm) such that for m mo we have that R(fo) Vmo?
Part 3: Note first that Li 2 Lú for i S Let 7 2 From Lemma 26 it follows that na(avT) < N(d, 1) + Ndd avT) (n(avT) Take such that Ndd, 1) + N(d.avT) > 2m. Then, have that
Σ N(d,))c, (Nv(d) 1) . a(T) 2mLar/
LavT 1 2 = X S ko-
Note that (1 - 22 (1 2 and
N (A1 + no)
(1-
If Ko Å1. then 2no A1 Ko, so 2ng
< Antno
This shows that [
4
Otherwise
Ri S }j Kg + + 2dj- This implies that
KS
AOT
(Ko + A1
4X2
4x
From Theorem 28 it follows that
AoU' 129
cxp(-a?). Since
1
1
z
mi
c3
we know that exp (-a²) >
exp
80 11
exp
Combining
RI c2
Lemma 18 and Lemma 19, we get Theorem 3.
26

---

C The case of increasing dimension
In Appendix C.I we will prove Theorem and Theorem In Appendix C.2, we will prove related claims about the eigenvalue multiplicities for relevant scalings of the dimension Corollary 12 and Corollary 13. In Appendix C.3, we will give detailed proof of Corollary 13. In Appendix C.4, we will discuss when the conditions posed on kernels are satisfied.
C.1 Proofs of Theorem and Theorem 9
Theorem 20 (Error scaling for any kernel ridge regression). Let d and m be any dimension and sample size. Define Lms Um kms (t), Ni, and ÅS as Definition Consider KRR with a kernel K satisfying Assumption 6 for some A. Assume that for some integer I, the target function f" satisfies Assumption 4 with most N, nonzero coefficients. Then, the risk of the minimum norm interpolating solution is bounded by the following:
R(fa)= -
Lim m
711
0²
(8)
Um
+ B²
Tom
1
m
A
Σ i==
N(i)
1
(9)
U
m2
X?
Additionally, we can get alternative bound if we swap
(Ei= N(d,
with
EL it), i..
RRff) 1 Lm )((1 m
o² +B² (1 (1-
Lm
(1
A
Jum
N
(d.
Tum
m
T.m
A
Proofs of Theorem 7 and Theorem 20:
Note first that Equation (2) implies that
R((f)) = Σ En (1 Lx,0)² 33 + E
Let C. A,_
Then, we can rewrite it as
Actmo
R(fo) = Σ ENN(
Ego
with slight abuse of notation for B,. From Equation (5), we have that for < m
Eo S 1
m
k + Tk
Take h = Lm Note that by Definition 5, Lm times. Therefore, we have that
m Then Ae+1
Rem+i and it repeats N(d, km + 1)
Th = N(d, km + +1) + Σ N(d, km +i+1)
Akntit1
Abm+1
Therefore, Th + k> N(d, km 1) + Lm Lm > m. Therefore, apply Equation (5). We get that
-1
(1
Lm
(1
En
<
1
m
+ T
m
Lm
Note now that
m Σ i(d
27

---

Note that A + Ko Ki so have that Cg Therefore, we have that
m Σ N(d,i)ci
1
i(d
A
80
KO
Therefore, have that Ki m 3i we have that
Since (1 Li)
Since there are only la nonzero
+x0
X2
(d. S B² A2
1
1
Σ
(dd, i)
m²
17
Going back to Equation (2), we have
R(Fo) Eo Σ (1
2,)2 1)83 EgOZ
S E B² A2
(dd 1)
+ Ego²
m²
X3
(1
Lm
S
1
a²
m
Lm
+
Lm
-1
m
-1
B
A2
Σ
N(d,
m
Lm
m
X?
This shows the first bound. For the second bound, note that
Σ
D
1 1 De
2
NNO +
m
i=/+1
i=1
So if we take 3 to have only I nonzero terms, we get
O (no + X1
(Exiddi)²
2
Σ
S
B
Σ A A
m
i=1
i=1
From this, we have that
Kg
(No
+ X₂
x; m2
1=1
Therefore, we have that
(dd, i)
Kig
8 S (dd, i)
A X; m²
(RO X.)²
Therefore, we have the improved inequality from
Σ (1--)) < Σ Nd i) A 1
X, m²
1=1
This gives the second bound on the test risk, as we can bound
Σ N(d 2,93 <
B m
Σ ENd 1
[Lower bound for test risk in increasing dimension] Let kim and Lm be as in Definition 5. Consider learning a target function f³, with some sample size m. Let K be a kernel satisfying Assumption 8 for some A and b. Consider the minimum norm interpolating solution of KRR (with any data distribution) with kernel K. Then, for the risk of minimum norm interpolating solution, the following lower bound holds:
2
Lm
R(fo) >
1
2
b+1
m
28

---

Proof of Theorem 9: By Theorem 3 from Zhou et al. [66], if & is the first & < m such that k + br 2 m, then
1
& 2
b
Therefore, it suffices to show that the first such k is actually L. = N(d, 1) + +... + [(d, km). Note
that
Tk = Eish>e A
(1)
(N){) Xd) < A max a
1
Ak+1
max iSh
\1
Ax
Since maxiskm + < m-km, for 1 < N(d, + .... + Nd,, km). we have that br + S
(d,, 1) + ... + N (d, km - 1-12--1 + bmaxiskn. km
< Lm + m - Lm I m, so the first / for Lm ((d +... N (d,, km). Plugging in = Lm we get that
which rj + > m
Eo 2
b
Lm
so from Equation (6), we have P((fo)
6
Lm
0².
b+I
5-1
C.2 Dot-product kernels the sphere
First we will prove results about the eigenvalue multiplicites Corollary 12 and Corollary 13.
Theorem 21 (Log-scaling multiplicity). Let d logz m. i.c. 24, and let ka be an index for which the following holds:
N(d, 1) .... Níd, km) < m
(dd, +.... [d,, km +1) m.
Then the following hold:
1. (d ()
2d decreasing and has lim
dN g)
2 - This also holds for dN(d.k)
with
24
k = [(d) < for all d.
2. (d. 5) is increasing and has lima-
N(d, 2) + oo. This also holds for N(d,))
with k
24
24
2
(dd 2 for all d.
3. There is an absolutet constant dg such that for d do. we have that & S km S.
4. There are absolute constants q-1 51: q g. and ct+1 such that N(d, kim i) > Q+im, for all í (+1, 0}. Additionally, there constants Cu-1 2. Cu 1, Cut1 such that Ndd, km + i) < Cu+im for all i E (3.
1
Furthermore, if
Log @(1,, then we will also have Lmm = (m) and Lm = O(m).
Proof. We will split the proof into three parts. Note first that N k) increases k increases. This can be seen from the ratio of consecutive multiplicities
(dd, l 1 (d,
2k +
+ d 2
2k 2k+ 2
k +
Part 1: We will use Stirling's approximation to estimate N(d, k). It states that nd! R (2)" 22mn. Therefore, we have that
k ~ 2 + d -3) (ktd=3) k+d (2k: d - 2)
N(d, k) = (2k ()xk))()+++)
+ 33!
(5) ( Vkvd-2
29

---

Since (d, k) is increasing in l and l S 5 so we can just plug in h = 5 in the expression. Therefore
N(d, 3) V2T (k: + d - 3) k (ktd k-d d-3 3
(2k + 2) 2)
(*) (d-2) d-2 vavd-2
2m + - 3) (8+d=3 +td-3
(2 + d 2)
(
(1-2)
)
8 bv -
/ddd's +d-3 8-3 gd-3
vd
(1) dg) Vdva
58 4d
(2)05
Vd
Vd
(3)/01g)018)) Vd
Note that (5/161900/5)
1.8, so
1.8
In partieular, we have that
Va
dd g
/d(188)
0.
2d
2d
Part 2:
The same calculation this case gives
(2 (2)))
((d, d
C
2
Vd
but note that (2)
2.5, so N(d
2.5 (25)d
vd 00. 00.
Part 3:
Note that if km S d then for dl large enough
N(d, 1) +.... + ((d, km) kim N km) (N(d,kmm)) < d.
Similarly, note that if km d. then km)) d for d large enough. Both of these imply hat S kim S d when d do (do is determined by when the inequalities above start holding).
Part 4: Note that when _ s k < 2. we have that 6 > N(d.+11 =
2k+d ktd-2 > 3 for d large N(d.)) 26+d-2 K+I
enough, since the firs ratio is close to 1 and the second is + k+1
d-2 This implies that ((dk)
N(d,k+1) <
whenever is large enough (larger than an absolute constant) and < 4. Note now that
m < N(d, 1) + .... + ((d, km + 1) < N(d, km + 1) (1+
1
+ p++...) < Ndd, + +1
3 3
2 3 m < N(d, km + 1).
This now implies that N(d, km)) > Ndd, Km +1) > Jm, N(d, Km - -1) m.m. Similarly have that (dd, km) m, so N (dd, km + 1) 6m and (d,, km 1) m.
Note that the same proof works even if d not exactly equal to loga m. This shows that whenever d
Tog (1), we have that L.n = (m)) and L.,. O(m).
Remark 22. Note that this does not say that we will always have tempered overfitting for log m (11) as sometimes it can happen that T.m -> m, so we cannot apply Equation (5) and Equation (6). In this case expect the overfitting to be catastrophic.
30

---

Theorem 23 Sub-polynomial scaling multiplicity). Let K be any dot product kernel on the sphere gd-1 (with nonzero eigenvalues). Let I N and let = 2 and let d 2 This corresponds to the case d = exp (vlogm) which is aab-polynomial. Then, for the upper and lower index, Lm and Lms we have the following
Lm
m
-
and
m
2 log m
Lm
d0.89
Additionally, for k = adimm where is a constant, we have that N k.) m², where 2 means up to sub-polynomia factors.
Proof. Let km be the maximum & for which
[(d, 1) +...- (d,, km) < m
N(d, 1) + ..... +N. km + +1)
We want to show that (dd, kmm) o(m) and N(d, km + 1) 2(m)). Then we can take A
(d,, 1) +.. (íd, km) and so + 0 and
((d, kim + j) Akm+t 12(m
rk (d, km + +1 Σ
dkn+1
j=2
m R
- O.
Note that we just need to estimate [d,, km) precisely. Let k = 2 + I. We want to show that (d, > m. Note that by Stirling's approximation n! ~ (z) V2nn.
(dd RJ 2 + d 3) #+d-3) k+d-3 (2k + d - 2)
(1)) (2=2) d-2 2 / 2T d 2)
dktd-2 dd 2T (1 + 3 3) (1 + 3))
k+d-3
(1+ --3) 3)
2t
1²d 20
k+d-3
dhtd-2 2/d 2T (1
21
3
1 +
2'-1
3
(1 +
24
3)
2
2
2
2
d
2m
k 2
2 2 2 Vovadd d
dh
V 12(( A/2 2) (1
2) k+d-3 (1 +
2T
(1 - 1) / - z/2
2T + 1/2 - 3) (1 + 24
d=
k
3 d
ktd-3
1
2m
(1 - dd 2/ 3/
k
d
Only the term ALVE (1+ k kg is asymptotic here, as the rest tends to a constant as d + co.
dt
d)
Note that since for all 1. > 5 (i.e. d)
3
2> 1
1.95.
d
we have that
k 3 k+d-3
12 (1.95) 2 +4-3ス > (1.95)* > (00.9)
1 +
d
1
1
k 3)
ktd-3
12 <2 d
3
d
31

---

Note that we have that then
dlc
1
3
k+d-3
dh
2 +k-35
2²
= 2 logd k lng log k2 +h
1thh
d
d
1ht //
Consider now the expression log - k log k that
loog ki + d + -
38 d.
For k: = 2' +1 1, we have
22
3k
1
3k k2
A llogd klog
log k
klog d klog k + k
log k
d + d
2
= =(2' +1 11) -0--0- -2' + (1 (1-1)) (1+
1-1
+ o 2 - 2 (1) + o
1
+ +
+ o 7
2
2
= -2 + 1) - 2 +
- 1 1+1 - o(1) 2
1
2 loog
logg log2 m.
2
In particular, this implies that for < 2 + (1 - 1), we have that
kdd < m22
o(m).
Now repeating the same computation for k 2 I, we have that
dh
h ( (1+
k+d-3
d
2099
= 2k logk- log k409
d
kk VK
1
k2
3k
1
3k
h2
log d- klogh: k:
log +
+ 0.9k
kloo
k log k + k:
2 log k
+
d
d
d
= (2' +1) - (2' +1) |+ 2
+ o
(1) + ol 27 + 0.9 2 0.91 + to
1
2
2
21
2 + + - 21) + 0.9 2 -1 - ++1+ (11) = 2 0.
2
= logg m + 0.9 Vlogg m loga logg m.
This shows that for k: 2 2 +1,
N ((d k) m2 +1 = Q(m).
To imply now that km = k 2 + [ suffices to show that N Nd, 1) + +... .......N..)) = o(m).
But note that we have k < d, so
N(d, 1)
2k d 2 k+1
N(d,k) < 2 ((d,A)
2k + d k+d-2 2
k N(d, k) d
(dd, 1) +.... + N k -
(d, 1) +... Ndd k) = omm).
Therefore, we have computed with proof that km with Lm Ndd, 1) + + (d, km). Note that
2 + 1 - 1. So we can now compute Lm and Lm
N(d, 1)
2k + d h: + d 2
(dd, k) 2 2 k+
Since k << d, note that N(d++1) N(d.))
> 2, so we have that N(d.k) N(d,kt1]
< 11, which implies that
N(d, N + N(d, < < N(d, kmm) o(m).
Therefore, we have that Lm N(.1)+N(d22) N(d.ke)) computed previously, we have that
in
m
2 m
3 N(d.km)
2log
3
From what
Lm > N(d,k) > 220.9-2'-
1
1
T.m 60.9 loo log dlug d
d0.89
Note finally that for ls a2 the leading term in the exponent of (dd, as derived above is a:22. all other terms are at most (2), which is sub-polynomial in m, so this shows that N ((d, ak) m 0
32

---

Remark 24. Note that for the polynomially increasing d, there are sequences (m, d) for which we do not get benign overfitting, i.e. when d = m², for integer Similarly this case, there are sequences of (m, d) for which we not get benign overfitting, but is much harder to identify them.
C.3 Proof of Corollary 13
Corollary 3 (Benign overfitting with Gaussian kernel and sub- sub-polynomial dimension). Let be the Gaussian kernel on the sphere Sd-1 with a fixed bandwidth, and suppose that for / E N the dimension and sample size scale d 2² m 2² i.e. d exp (vlog m). Consider learning sequence of target functions få as in Assumption 4 with Sa S m². Then, we have that the minimum norm interpolating solution achieves the Bayes error in the limit (m, d) + co. In particular, for d 2 4 and m 2 16 we have
Re(F)) (1 log mi
(1- (1-exp exp (- -0.89 log m
o² 2B2 1
If take Sy = poly(d)), then can improve the m error dependence p Furthermore, can improve the bound on Sa by reducing the rate of convergence. Let 8a be an integer such that Sa < Neg. Then error dependence is + 5 (d, sx)d(+))
1/ (1(+)))
Proof: We have that from Theorem 23 that in this case km 2 = log d + log log 1, T. 0 log and Imm 2 O(md0.89) Therefore, we have that
Eo (1 log m
(1 )
exp (-0.89 log m
To finish the proof, we need to estimate Nd, 1) + +... (cl, km x Note that the eigenvalues are
sorted and Ndd. k 1) (d, k 1)) since ki = odd) This implies that it suffices to estimate
N (dd, km)) X2 Note that for the first eigenvalue, we have from Corollary 31 for a 1 + +m
1 da
<A1
So, for Aς. it holds that
Fm
X
2
+ 2i + 2 - 1)
i=1
Therefore, we have that
+ 2(i +
1)
2
* r(d + 2hm
+ 2
d
k
da
< da
(12)
+
k
+
A
2
2
T())
2) mm
2
7 m
Tm
Note also that k = Bkm for some constant 3 then
((d m²
in the sense of Theorem 23. So, (d,, kim) kim) < m (h(1+t)-22 We want to take & as large as
possible, so we will take it k Blin. Then d2h 25 Therefore, long as 33 < 2, we will have
23
a polynomially scaling error. So we can take 3 = 2
3. Note that with Theorem 20, we actually get
even better dependence of the error, like m 8 d (1+t)) Plugging the first estimate into Theorem 7, for 3a = 1, we have that
R(fo) < 1
0²
log
0.89
1
-
-1
-1
-1
B²
m
log m
d..9
m2
log m
50.89
1
1
-1
1
2²
1
1
log m
c.89
m
33

---

If we want to achieve Sa = poly(d), note that we just need to take & to not scale wit d. That is, if we want deg S n, then we can take n. The eigenvalue will be
+
den i.. since d is sub poly The multiplicity will be N (d, n) ((d)). Note that then error scales m, we can take any such n.
C.4 Kernel conditions
We have three main assumptions on kernels. First, the sum of its cigenvalues is bounded. Assumption 6 (Bounded sum of eigenvalues), Assume that the kernel K has bounded sum of cigenvalues, i.c there is a constant A such that Σi=1 (i) S A. For a sequence of kernels K (4) assume that all such (4)) are bounded by some constant A.?
Second, there is lower bound on the eigenvalues.
Assumption 8 (Lower bound eigenvalues). Assumme that the kernel K has eigenvalues that are not too small, i.c. there is a constant b such that maxighm. {/)
< m- Lm For a sequence of
kernels ((d), assume that for the corresponding the dependence) all such ((d) are bounded below by some b.
m(d) (since d(m), can also "invert"
And third, the eigenvalues don't 't decrease too fast.
Assumption 10 (Eigenvalue decay). The eigenvalues don't decrease quickly, i.e. for kim in Definition 5, we have that there is constant such that maxisk..
S c.V (km)). For increasing
dimension, require that max;skm km
(+++ S cN (d, km).
Note that Assumption will hold quite broadly, in particular at least for dot product kernels on the sphere (that effectively the same kernel just in increasing dimensions). Note also that the Assumption 10 is almost always stronger than Assumption 8. This follows from the definition of Lm and km. i.e. since Imm = N(1) +... (kkm), have that N N(km)
and long as Lm < <O(m), we can take large. This is usually the case (we show previously in Appendix C.2 for dot-product kernels
the sphere). For w(og m), we even have I-m o(m). So in particular N (d, km) < (m - Lm) and for d = (logm), we have (d, km) o(m - Lm), so indeed Assumption 10 is stronger than Assumption 8.
Assumption 6 and Assumption 10 are also taken to be true in the literature on the polynomially scaling dimension [4, 64].
First assumption: For dot-product kernels on the sphere, we know that the eigenfunction Φ; are actually the spherical harmonics Yks- Let K(x, y) = h([l yll). Note that for E gd-1, it holds that
(d.k) Σ
k).
Therefore, since
K K(2,0)= = Σ Apoi
N(d.)
A(O) = K(x,x) = Σ
d =
So the assumption in Theorem 7 holds with h(0). For the Gaussian kernel, this is A Similarly, A = 1 for Laplace kernel.
Note that this assumption implicitly sets the scale of the kernel.
34

---

Second Assumption: For the eigenvalue assumption, maxiskm A,
m-Lm, note the following.
Ab
We will usually have T-m o(m). In particular, whenever d = w m) for dot-product kernel on the sphere this will hold.
The cigegnvalue assumption will hold for the Gaussian kernel in the non-integer polynomial regime, d = m. In Appendix C.3, we showed that X < d", so since kim = [aa], we will have + < dd X
(dd=))) Similarly, we can show this for the Gaussian kernel for d = log m and d = exp( (v Vlog m) regime. Note that in Corollary 31, we showed that Åι > ग. and Ås > -ーTh. so then _ X, Additionally, in the d = exp( /ool m) regime, we showed that Lm = o(m) and that 1 = @(Lm) for any k (kk)) < kim- The same proof shows that this assumption holds for any sub- hob--olynomilly scaling dimension and Gaussian kernel.
Furthermore, this assumption can be weakened to the following: there exists b > 0 such for all S Lons Eisk d < A (m - k). Additionally, since the assumption specifie to our approach, it seems to be possible to weaken it even further.
Third assumption: This assumption holds for dot- dot-product kernels on the sphere. It was shown in Zhang et al. [64] (Lemma 5.2.1) under another assumption similar to (1) that it holds for polynomially scaling dimension.
also assumed in Barzilai and Shamir [4] (page 11) for polynomially scaling
dimension. Furthermore, Cao et al. [9] (Theorem 4.3) shows that this holds for Neural Tangent Kernel even more broadly, i.e. for all i and not only
kim.
D Sharp bounds on the eigenvalues of the Gaussian kernel
In this section, we will summarize and prove the results about eigenvalues of Gaussian and Laplace kernels when X' Unif(S4-1). Given a positive semi-definite kernel function K : X' x X ++R, R, we can decompose it as
K(x,t) = Σ dR (1)
where A and Φb are the eigenvalues and eigenfunctions of the operator associated to K, Lx L. (Sa-1) + L22xx0x (S (Sd-1)
(x(f(x) = / K(x, Kzz
Lk is Hillert-Schmicc operator and has countable system of non-negative eigenvalues A satisfying Σx X/ < co. The corresponding 1.2,( --ormaaizdl eigenfunctions {ou {2 form an orthonormal basis of 1.222 (sd-1). The eigenfunctions. in this case are given by spherical harmonies, Vi... The eigenvalues corresponding to Vr., for fixed have the same eigenvalue, ,; Eigenvalues \; are reach repeated N [d, i) 42i+--2)(+4 ddi+d-3) times. So the sequence { :!(d-2
AI,..., Å1, Ag,..., AZ,.... Using Funk-Hecke formula, we can compute Å explicitly, both for the case of Gaussian [46] kernel. For Gaussian kernel, we have the following theorem about the eigenvalues Ag.
Theorem 25 (Eigenvalues of the Gaussian kernel [46]). Let X ~ Uni with d E N and d 2 2. [x==
For K(z, t) = exp (- = ) Tm > 0, and k E No we have that
2
d == e
mm k -1
r
T2
Each X occurs with multiplicity (d,
(2k+d (2k+d-2)(k-dd 3y!
(we use notation to indicate that it
k!dd 2).
has multiplicity) and its corresponding eigenfunction are the spherical harmonics order & on $d-1 Here, 1z),,, U. 2 E C is the modified Bessel function of the first kind
v+2j
(x(2)
== T +1
2
35

---

It will be useful to know the size of [d,, i). Also, the size of the sum of the first k multiplicities will be useful. Let N E N(d, i).
Lemma 26 (Size of multiplicity). For (dd (2k d- 2 3y
it holds that
k!(d-2) 2)
1 kd ((d 1
2)
Additionally, there exist constants n4; na > 0 depending on the dimension d such that Ng bounded below and above by the following
nikh h- S No S nikh-1
Proof. Since (2k +) S (2k) for j 2 2 and (I: + 1) S 2k, we have that
(2k + d (k: + d - 3) (k: 1) (d 2) (2k)
(d,
S 2d-1nd
(d (d-2)1 2)!
2d)
and
(d) (2k + d 2)(k: + d d-33 3)
(k: #1
1 hd-2
(d - 2)!
(d 2)!
Note that by Bernoulli's formula
k
1
(kd-1 + o(khd
1=1
Therefore, we have that
2d-1 nika < (d- 1)(d 2)1 (1--1 + =(k(-l)) S No S d- (h--1 + (((kdl)) S nukd-1
Lemma 27 (Inverting the index). If the index of an eigenvalue Ūy is such that Nx-1 SJS No- 1, then Xy Ag. We will denote such j with i.. is an index such that Rष Ap-
Proof. Immediate from the fact that (2:) is sequence with K, repeating N(d, i) times, in that order.
An interesting property of eigenvalues of the Gaussian kernel that they are sorted because the Modified Bessel functions are [48]. particular, [x)1(x)= < [z(z) for all v, x > O, so \++1 < d This is not the case for the Laplace kernel.
Theorem 28 (Size of Ratios of Eigenvalues for Gaussian Kernel), Let T ( For j S
VTt(m),k (Tmmm), where t(m) -> -> co, have that
Ao+j <1. 1.
exp(-6t(m))
d
For j 2 VTt(m), where t(m) + as we have that for any k
dett < exp
(- t(m)2
(-a4))
36

---

Proof. First of all, note that from [48], we have that for 2
(V- + v (v ) + x²
(v) + (v) + x²
(--1(x)
(1)
1x)
x
(0) + (v) + x2
(--1(x)
(v - ()) + v (v 2 + x²
In partieular, this means that for the eigenvalues Ay. we have
(
dRt1
4-- 3/2 -
(22
(k: + d) 2) + (k: + 2) +
1 k (T)
(I: + d - 2 + v
(k
1
2
)
2
2
This can be bounded with a simpler expression as follows
ARt1
(
2(k: + ( (
1
(k 2 2 (
X++1 An
We will use these bounds to derive tight bounds for the ratios
Note the following
Akti
j
deti
2
II
2(k i
+
d 2
d
Auti-l
(k+
+
d 2
i=1
Note now that
(
2
detj
mm
<
2(k
+ 1+ ( (
==1 2(k + 1 (
dx
Note that since therefore
= x² + ix + (j- i)d, we have that (a +j - i) + i) 2 (x + +1xx.
(
+1
2 - 3)
2
i+1
(x)
jk 1 / - +
(k:
1
+
2
We use j+1 and j - 1 to account for the fact that might be odd when we split into (j - 1)/2 pairs.
When j is even, we split into pairs and use the fact that the term with exponent 2 is larger.
i+1
Let T = (-=). We can bound the ratio
Anta tightly now. A
When j S VTm -6, KS VTm-6 we have that
Àets 1.
exp(-6m-0)
d
When j 2 VTm., we have that for any k
37

---

Akts d
m2 ).
< <expl-
To see why this is true, note first that
2(k +j 1 + +
VT
T
T
2(k: + +++)+7 +T
2(k +
1 () + +
VT
VI
T
exp( )))
5(VTm-6)) +T
VT m
== +)+ +
as + 0c. For the second inequality, note that
2
m
<1.
(k +
2
We also have that
#
2
VTm
T
(k + 1
2
(k+
1 2
d
2)
+
T
(VTm²) +
TTm!
TTm
1
(VIm²)
m
VT
VT
m11 26
>>
exp(
0+0,
3
-> 00. Note that turn the limits am t(m) into inequalities of the form (1 =))(m)
am < (1 (m) for some e and all m since the convergence is uniform.
The following is a simple corollary.
Corollary 29. Let T ( - If > 1 and the index of the eigenvalue i is such that i S (kVT))-11 we have that for A; holds that
AVT
A A
2 exp(_k3)
1
VT
KvT
Proof. Note that
is increasing in VT and note that VT increases increases. Note
that for vT suffices to show e(k) > + & which is true for all long as vT 1.
The following simple bound also holds for eigenvalues of Gaussian kernel.
Proposition 30 (Ratio of eigenvalues bounded above [46]). For the eigenvalues associated to the Gaussian Kernel Å of bandwidth Tm we have that
1
7
T
(k: + 4
38

---

It is straightforward to convert the bounds on ratios of eigenvalues Theorem 25 to bounds on the sizes of the actual eigenvalues.
Corollary 31 (Sizes of the eigenvalues of Gaussian kernel). The following bounds hold for the largest eigenvalue of the Gaussian kernel
3 + 1)) r((
T(( 3 (
1
1
< 111
m + r(
2) 72
mm + 4T
I( 2 + + [
Therefore, for A we have that
1 r( +k+ +
\1 < d
2k I' +k 2)
r( +
d < 2h
26
r
2/4 +
m
Furthermore, for Tm fixed we have that
1
d
72
4
(($
+
and
1
T
+
4
(12
-x
2
1+
2
m
-2k
((k:
+ )))
+
Proof.
Note that from [62] we have
2
2
1
2
exp
Iu
exp
+
72
-2
+
We also have from [48]
2 1
FT
2 +
1
2
2
Then
2 2- tm
2
d 2
m
k+
-2
r
So then
r(( + 1))
$ - II
1
1+ α -1
1 r
Tm
P
2
+ +))
2
+
1)
2
Io
2(1
2(1
!))
T/.
l(5)
7
1=0
So then
1
r(( 2
+ ())
1
T(( 7.
())))))))))))))
< Â1
2
+
r
2)
v T/.
472 m
T
---
+ d
2
+
39

---

By repeating the same argument, the claim about dS follows.
Note that
\ >>>- T
II
+
4
(i+
1) (
+
Tm + 4 (15
1=0
Therefore, we have that
k-1
2
1
X1
h:
+
2
T ((k:
)m)
1=0
mm
40

---

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: All the contributions are clearly stated in the introduction, particularly the third paragraph of the introduction. The assumptions and limitations are also clearly stated in that paragraph.
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 the paper and important assumptions and limitations. A No or
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 to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: All assumptions are clearly and concisely stated. We also provide detailed reasoning for each one of our assumptions. The assumptions are further discussed in the appendix.
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
41

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are stated clearly before each result is presented. We give an outline of proofs in the main body and complete proofs in the appendix.
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 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 whether the code and data are provided or not)?
Answer: [Yes]
Justification: The description of the experiments that are provided along with the figures is sufficient to reproduce the experiments.
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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
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 new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
42

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide code and instructions required to reproduce experimental
results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
wtwpessbbbmsssoooooiooooooo asionnliccy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //iiss... wwwpcccpppc/.aee..c...ccce.cetle muublicguuides...e/ /ttggggueee/eeeeeaaiiiiiieae SCodeSubmissiond seiobbiiiisioooccccccc.oo for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are 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 in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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?
Question:
Answer: [Yes]
Justification:
All the necessary details are included the descriptions of the figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in 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]
We report appropriate information about the statistical significance of the experiments.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
43

---

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 or the standard error of the mean.
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 or figures symmetric error bars that would yield results that out of 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
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The compute resources are stated along the explanation of the experiments.
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 failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the csGuidelines!
NeurlPS Code of Ethics attps://neurre http://errrpp..ccpuiiiicec
Answer:
[Yes]
Justification: Yes, the paper conforms all aspects of the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS 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: [NA]
Justification: [NA]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
44

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out 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 generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 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 to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: 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)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no 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 use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi wwwode.hco....c. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
45

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if 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 the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset 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. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well 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 the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS 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 or Equivalent for Research with Human Subjects
Question: 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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.
46


Reviews:
[{"review_id": "fnGVhfG8Ih", "reviewer": "Reviewer_Ymgo", "summary": "The authors derive estimates of the population risk of the kernel (ridgeless) regression estimator for spherical data when either the kernel bandwidth or the dimension of the data depends\non the number of training points $m$. To do so, authors rely on the eigenframework and prior work, which provides (under assumptions on the distributions of the random variable $\\phi(X)$ where $\\phi$ is the kernel feature map and $X$ is the input random variable) formulas for the population risk of the kernel ridge regression estimator as a function of the eigenvalues of the kernel integral operator. Using these formulas, authors then derive nonasymptotic estimates of these quantities in order to establish the limit value of the risk, as well as its dependency w.r.t $m$ and $d$. They obtain that\n\n- for a fixed dimension, overfitting is always harmfull (tempered or catasrophic) unless the bandwidth scales in precisely in $m^{-1/d-1}$ in which case overfitting is shown to be tempered for large enough noise in the data (Theorem 1)\n- for a fixed bandwidth, but varying dimensionthey derivelower and upper bound on the population risk. This allows them to\n\t- recover known results stating that when the dimension size increases polynomially with sample size, overfitting is benign or tempered\n\t- show that when the dependency is logarithmic, overfitting is not benign (under additional assumptions verified for the gaussian kernel)\n\t- show that when the dependency is subpolynomial $\\exp(\\sqrt{m)$ scaling, overfitting can be benign", "questions": "In the analysis, the data is assumed to be on the sphere. Can the authors comment on how they expect the results to change for data\n  distributed on the whole of $\\mathbb  R^d$?\n\n\nTypos:\n\nl 294\nl 298", "limitations": "Mentioned in weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clear, with a good effort spent on litterature review and comparison with prior work.\n\nThe main technical contributions seem to be bounds on the spectra of dot-product kernels on the sphere, which if novel (I am not an expert of this domain) could be of independent interest and are welcomed.", "weaknesses": "- This paper investigates the behavior of **ridgeless** (e.g. no RKHS norm penalty) kernel estimators, something which should be made clearer.  For example, kernel ridge regression is part of the paper title, whereas the paper does not study kernel ridge regression.\n- The eigenframework which they use rely on a number of assumptions to be valid.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback. Below we address the main comments:\n\n1. Ridge vs Ridgeless: We will change the title to use “ridgeless” instead and reword other relevant parts of the paper. \n\n2. Assumptions for the eigenframework: There is ample empirical evidence that the eigenframework holds well for the Gaussian kernel. For example, Figure 1 in [38] shows the predicted vs. true test risk for Gaussian KRR (using MNIST data) and Figure 5 in [7] shows the true vs. predicted risk for Gaussian KRR with data uniform on the sphere (which is the setup we consider here). In both of these plots, the prediction matches closely with the true test risk. \n\n3. Answer to the reviewer's question: The Gaussian kernel will essentially zero out contributions of points that are far away, so as long as the bandwidth is small enough and the sample size is sufficiently large, the d-sphere will “look” the same as $\\mathbb R^d$. So we expect that the result stays the same for other measures on $\\mathbb R^d$, but we leave this question for further research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hCpuXGzdDn", "reviewer": "Reviewer_cvRM", "summary": "The paper investigates the overfitting behavior of Gaussian Kernel Ridge Regression (KRR) in high-dimensional settings, focusing on how the model performance is influenced by the choice of the bandwidth parameter and sample size.\n\nThey aimed to provide a more comprehensive picture of overfitting with Gaussian KRR by studying the overfitting behavior with varying bandwidth or with arbitrarily varying dimension, including sub-polynomially. In particular, they showed that for fixed dimension, even with varying bandwidth, the interpolation learning is never consistent and generally not better than the null predictor (either the test error tends to infinity or is finite but it is almost always not better than the null predictor). For increasing dimension, they gave an upper and lower bound on the test risk for any scaling of the dimension with sample size, which indicates in many cases whether the overfitting is catastrophic, tempered or benign. They showed the first example of sub-polynomially scaling dimension that achieves benign overfitting for the Gaussian kernel. Additionally, they showed that a class of dot-product kernels on the sphere is inconsistent when the dimension scales logarithmically with sample size.", "questions": "Can you explain the theoretical basis for the catastrophic overfitting observed with certain bandwidth scalings and the choice of kernels intuitively?\n\nWhat are the practical guidelines for choosing the bandwidth parameter in real-world applications since there is no experiment?\n\nHow does the proposed method perform across different types of data distributions besides Assumption 2?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The presentation of the paper looks really in good order with adequate clarifications and rich literature reviews. The motivation is clear to me. The proof provided also looks correct in general.,\n\nThey clearly provided an upper and lower bound on the test risk for any scaling of the dimension with sample size, which provides a clear and comprehensive understanding on the issue of overfitting with Gaussian KRR, which is not restricted on particular regimes, while it also discovers new result for sub-polynomially varying dimension. I found the proof technique quite interesting and insightful.\n\nAlthough the contribution is not extremely outstanding or groundbreaking, the results completely reflect the effect of varying bandwidth or dimensionality in a very comprehensive way and it certainly facilitates the understanding of this issue and also provides a very insightful theoretical guidance of picking these crucial parameters.", "weaknesses": "The first and a clear weakness would be lack of experiments. Since the results in the paper focus on the overfitting behavior with varying bandwidth or with arbitrarily varying dimension, including sub-polynomially, it should benefit a lot and is very instructive to study the real effects guided by the theories on the simulated or real-word datasets. \n\nThe results should be sensitivity to tuning parameters. The paper highlights the complexity of balancing these parameters but does not provide robust, practical guidelines for optimal tuning.\n\nDifferent data distributions and kernel eigenstructures result in non-uniform impacts of the tuning parameters, complicating the tuning process further. It is better the paper could consider more general date distributions in Assumption 2 or at least can provide some insights on how the results may vary given different date distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback. Below we address the main comments:\n1. Regarding the experiments:  There is ample empirical evidence about the eigenframework holding well for the Gaussian kernel. For example, Figure 1 in [38] shows the predicted vs. true test risk for Gaussian KRR (data is from MNIST), and Figure 5 in [7] shows the true vs. predicted risk for Gaussian KRR with data uniform on the sphere (which is the setup we consider here). In both of these plots, the prediction matches closely with the true test risk. Furthermore, in the attached PDF we also provide empirical evidence that the claim for the case of fixed dimension holds. We plot the dependence of the test error on sample size for the Gaussian kernel ridgeless (interpolating) predictor. In Figure a, we consider the first case of Theorem 1, namely when the bandwidth $\\tau_m = o(m^{-\\frac{1}{d-1}})$. It shows that the test error tends to something equal to or larger than the test risk of the null predictor. In Figure b, we consider the second case, i.e $\\tau_m = \\omega(m^{-\\frac{1}{d-1}})$ and the plot shows that the test error increases with sample size, which aligns with the claim that it diverges as the sample size $m$ increases. In Figure c, we consider the case when $\\tau_m = \\Theta(m^{-\\frac{1}{d-1}})$ and the plot shows that for some noise level (which is high enough), the predictor is worse than the null predictor, as predicted by our theorem. We will add these simulations to the final version of the paper.\n\n2. Intuitive explanation for the catastrophic behavior observed: As discussed in [24], the functions learned by the Gaussian kernel are too smooth, so they overfit the noise harmfully. On the other hand, the authors construct a “spiky-smooth” kernel that can exhibit benign overfitting in a fixed dimension.\n\n3. Practical guidelines for optimal parameter tuning: Since the result for fixed dimension is negative, i.e. we show that the overfitting is catastrophic or tempered and that the predictor is almost always worse than the null predictor, it’s not expected that the Gaussian ridgeless regression would be successful in practice. The guideline would be to use an optimally tuned ridge and to avoid interpolation when using Gaussian KRR.\n\n4. Different data distributions: As briefly mentioned in lines 142-145, the same result extends to more general distributions, namely uniform on a manifold that is diffeomorphic to the sphere. So the result holds for more general data distributions as well. Furthermore, considering inner product kernels with respect to the uniform distribution on the sphere is very common in many theoretical works, such as [4,37,38,61], just to mention a few. We agree with the reviewer that extending the results for additional distributions is an interesting future direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5yjJXNrwxq", "reviewer": "Reviewer_FXXZ", "summary": "This paper looks at the problem of kernel (ridgeless) regression with Gaussian kernel and data on a sphere. The paper studies two cases, first we fix the dimension $d$ and are allowed to send the number of data points $m \\to \\infty$ and the width of the kernel $\\tau_m \\to 0$, second, we are allowed to scale $d$. For both problems they study how a quantity known as the predicted risk scales. *It is important to note that the paper assumes that this is a good estimate of the true excess risk, which is not immediately evident and I think requires more justification (see weaknesses).*\n\nIn the first case they show that if $\\tau_m$ goes to zero too quickly, we have tempered overfitting for the *preditcted risk* and that it has a worse risk than the null estimator. If it goes to 0 too slowly, then we have catastrophic overfitting for the *predicted risk*, and that if it goes to zero at the appropriate rate, we have tempered overfitting again and that we may outperform the null estimator. The paper also presents some results about the case when $d$ scales as well.", "questions": "Please see weaknesses", "limitations": "The limitations are well discussed.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper uses the predicted risk as an estimate of the true risk. The prdicted risk is given by \n\n$$ \\tilde{R}(\\tilde{f}\\_{\\delta})  = \\mathcal{E}\\_\\delta \\left(\\sum\\_{i=1}^\\infty  (1-\\mathcal{L}\\_{i,\\delta})^2 \\beta_i^2 + \\sigma^2 \\right) $$\n\nWhere $\\beta_i$ are the coefficients of the target function in the eigenbasis of the kernel function and $\\mathcal{E}, \\mathcal{L}$ are coefficients based on eigenvalues and $\\sigma^2$ is the noise variance. *If we assume that this is a good estimate of the excess risk*. Then to understand the risk, we have reduced the problem to understanding how $\\mathcal{E}, \\mathcal{L}$ **and** $\\beta_i$ scale. \n\n**This paper studies how $\\mathcal{E}_0$ scales by providing some bounds on the eigenvalues of the Gaussian kernel function. This I think is the primary contribution of the paper.**\n\nHowever, there are some issues, see weaknesses.", "weaknesses": "There are a few weaknesses. The current reject score is due to my concerns with the proofs. \n\n1) **Theorem 1**\n\nI have some concerns with the results in Theorem 1. Theorem 1 states that unless we meet some very specific conditions, the null predictor (i.e. the zero function) outperforms kernel ridge regression. This seems quite surprising to me. \n\nTaking a closer look at the proof, we see that proof is broken down into two Lemmas. One proves the upper bounds, the other lower bounds. However, Lemma 1, only deals with $\\mathcal{E}_0$. However, I think something has to be said about $\\sum\\_{i=1}^\\infty  (1-\\mathcal{L}\\_{i,\\delta})^2 \\beta_i^2$. \n\nIf I understand correctly, when we change $m$, we change the width, which changes the kernel function. However, since $\\lambda_i$ and $\\phi_i$ are the dependent on $K$. Hence $\\beta_i$ which are the coefficients of $f$ in this eigenbasis are dependent on $m$. Hence $\\sum\\_{i=1}^\\infty  (1-\\mathcal{L}\\_{i,\\delta})^2 \\beta_i^2$ has a subtle dependence on $m$ which I think needs to be accounted for. Because apriori it is not clear to me that this is bounded in $m$. That is, $\\sum_i \\beta_i^2(m) = S(m)$ could be unbounded in $m$. \n\nI did not go through the lower bound proofs as carefully, but I do think the the dependence of $\\beta_i$ on $m$ is addresses. Please correct me if I am wrong. \n\nHence I think either another assumption needs to be added (and if it is added a discussion of its reasonableness would be appreciated) or that terms needs to be explicity dealt with. \n\n2) Eigenlearding Framework and Predicted Risk\n\nIn general, I would prefer results showing that the predicted risk is a good estimate of the true risk. The paper on lines 116-131 attempt to this. However, the primary papers that have been cited [1,12,25] are all about **linear** regression and not **kernel** regression. Specifically, they all assume that $y_i = \\beta^T x_i + \\epsilon_i$ and that we are fitting a linear function. This is not quite the setting of this paper, as we have an infinite dimensional feature vector space that we are working in. Hence I do not think those papers are sufficient theoretical justification. \n\nMy other concern with this, is that the discussion from lines 98-111 **do not assume that** $y = f(x) + \\epsilon_i$ which I think is needed in [47]. The paper presents for general distributiuons on $\\mathcal{X}$ and $\\mathcal{Y}$. I do not think the eigenlearning framework captures the following situation $x_i  = z_i + \\epsilon_j$ and $y_i = f(z_i)$, but the paper here, as written, would claim this. See [A,B] for papers that address such a situation, [B] even has results on benign overfitting. \n\n\n[A] Sonthalia, Rishi and Raj Rao Nadakuditi. “Training Data Size Induced Double Descent For Denoising Feedforward Neural Networks and the Role of Training Noise.” Trans. Mach. Learn. Res. 2023 (2023): n. pag. \n\n[B] Kausik, C., Srivastava, K., & Sonthalia, R. (2023). Double Descent and Overfitting under Noisy Inputs and Distribution Shift for Linear Denoisers.TMLR 2024\n\n3) References \n\nI think the long list of references on lines 45-48 need to be changed. The paper should either further subcategorize them, or cite fewer papers. In the case that the authors decide to further subvategorize them. I think they are missing some references [A,B,C,D]. Additionally, some papers are cited twice, see 25, 26, and 23, 24. \n\n[C] Xiao, L., Hu, H., Misiakiewicz, T., Lu, Y., & Pennington, J. (2022). Precise Learning Curves and Higher-Order Scalings for Dot-product Kernel Regression. Neural Information Processing Systems.\n\n[D] Hu, H., Lu, Y.M., & Misiakiewicz, T. (2024). Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime. ArXiv, abs/2403.08160.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful feedback. Below we address the main comments:\n\n1. Regarding the claim about Theorem 1:\n$\\beta_i$ in this case do not depend on $m$. Changing $m$ does change the bandwidth $\\tau_m$, but the eigenfunctions remain the same despite the kernel changing - the eigenfunctions are the spherical harmonics. Therefore, $\\beta_i$ does not depend on $m$, as it is $\\beta_i = \\mathbb E_{D_X} \\left( f^* \\phi_{i}\\right)$ and $\\phi_{i}$ is a fixed spherical harmonic in $d$ dimensions (i.e. $Y_{ks}$ for some $k$ and $s$; here $d$ is fixed). Therefore $\\sum_i \\beta_i^2 = S(m)$ is fixed and independent of $m$. \nNote however that $\\mathcal{L}_{i,\\delta}$ does depend on $m$ as it depends on the eigenvalues and this is addressed in both the upper and lower bounds (although indirectly for the lower bound).\n\n\n2. Regarding the eigenlearning framework: In lines 126-129, we discuss a more recent work, [38], in which they provide theoretical justification for eigenframework in the case of kernel regression. Since there are quite a few theoretical works that rely on the eigenlearning framework (including ours), for example [1, 7, 12, 25, 47, 54, 63],  and since there is vast empirical evidence to support it, we agree with the reviewer that obtaining further theoretical justification for it is an important topic for future research.\nThe assumption on the target in 98-111: It’s true that as it’s written, it is not yet assumed that $y = f^*(x) +\\xi$. However, as discussed in Zhou et al 2023 [63], the results of [47] can be extended to a more general setup. We will edit the paper to clarify this.\n\n3. Regarding the references: Thanks. We will update this section of the paper to include these additional references.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BQE3SXAE68", "reviewer": "Reviewer_dZGD", "summary": "This paper discusses the generalization ability of Gaussian kernel interpolation, an interesting topic. However, the authors sidestep the most challenging part by assuming the 'Gaussian universality ansatz,' which significantly simplifies the problem. With this assumption, their work essentially consists of elementary computations. Furthermore, their argument heavily relies on the earlier work by Lijia Zhou, James B. Simon, Gal Vardi, and Nathan Srebro, titled 'An agnostic view on the cost of overfitting in 473 (kernel) ridge regression,' an arXiv preprint with the identifier arXiv:2306.13185, published in 2023.\"", "questions": "Perhaps due to my lack of knowledge, could the author elaborate on their contributions beyond the detailed computation of the Gaussian kernel with varying bandwidths?", "limitations": "None.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "A detailed calculation of the eigenvalue structure of the Gaussian kernel with various bandwidths has been performed. This could be valuable for future studies.", "weaknesses": "No significant contribution was made to the kernel interpolation problem itself. The major workhorse was developed in earlier work by Lijia Zhou, James B. Simon, Gal Vardi, and Nathan Srebro, as detailed in their paper titled 'An agnostic view on the cost of overfitting in 473 (kernel) ridge regression,' published as an arXiv preprint with the identifier arXiv:2306.13185 in 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Below we address the main comments:\n\n1. The goal of the paper is to study the kernel interpolation problem by understanding its behavior under common settings. It achieves this goal in two ways. First, we consider the common Gaussian kernel with varying bandwidth. In lines 82-86, we argue that this is an important setting since it achieves optimal rates of convergence for a large set of target functions (note that the optimal rates are achieved by varying the bandwidth). Indeed, using a varying bandwidth is a standard practice when using the Gaussian kernel. We are the first to consider whether the interpolating solution exhibits tempered or catastrophic behavior in this setting and how it compares to the null predictor. This result shows that even with varying bandwidth, the interpolating solution is almost always worse than the null predictor. Second, we consider increasing dimensions and sample size with more general kernels. We establish upper and lower bounds on the test risk for any scaling of the dimension and sample size, which indicates what type of overfitting we get. This result not only agrees with the known case of polynomial scaling of the dimension but also allows us to show the first case of sub-polynomially increasing dimension that achieves benign overfitting for the Gaussian kernel. Our results provide a more comprehensive analysis of overfitting in kernel interpolation. \n\n\n2. The results are highly non-trivial at the technical level and do not simply use Zhou et al 2023 [63] (as the reviewer suggested). First, for fixed dimension, our technical contribution is deriving the dependence of the eigenvalues of the Gaussian kernel on the bandwidth (Theorem 8, line 1133) and hence understanding how the test risk depends on the bandwidth. Second, for increasing dimension, our technical contribution is deriving upper and lower bounds for the test risk that work for any scaling of the dimension and sample size (Theorems 2 and 3, lines 189 and 203), by introducing the “upper and lower index” (Definition 1, line 182).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fScjTCQgbS", "reviewer": "Reviewer_zGqe", "summary": "This paper concerns the overfitting behaviour of Gaussian kernel ridge regression (KRR) with varying bandwidth or dimensionality. The contribution is two-fold: \n\n1. In fixed-dimension, the ridgeless solution of Gaussian KRR is not consistent with any varying or tuned bandwidth. \n\n2. In high dimension with input dimension $d=2^{2^l}$, sample size $m=2^{2^{2^l}}$ for any arbitrary integer $l$, the overfitting of Gaussian KRR is benign.\n\nAll the results are under the Gaussian universality Ansatz and the (non-rigorous) risk predictions in terms of the kernel eigenstructure introduced in [Simon2023]. \n\nReference:\n\n- James B. Simon, Madeline Dickens, Dhruva Karkada, and Michael R. DeWeese. The eigenlearning framework: A conservation law perspective on kernel regression and wide neural networks. arXiv preprint arXiv:2110.03922, 2021.", "questions": "The most important question would be if the authors could provide some experimental validations on these two claims.", "limitations": "All assumptions are stated in the claims. However, as mentioned before, GUA and Eigenframework assumptions are too unrealistic and might provide wrong results.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "The two contributions are novel.", "weaknesses": "However, I have serious concerns about the assumptions made in this paper. Firstly, the eigenframework under the Gaussian Universality Ansatz (GUA) is non-rigorous and actually fails to explain the catastrophic overfitting of NTK in fixed dimensions, as reported in \\cite{Barzilai2023} and \\cite{Cheng2024}. I am uncertain whether benign overfitting would still hold in high-dimensional settings. This paper does not offer experimental validation either, so I cannot ensure the correctness of the claim for Gaussian kernels (not its proxy under GUA).\n\nSecondly, the catastrophic overfitting of Gaussian kernels with fixed bandwidth is well-known. It is not difficult to imagine that Gaussian KRR with varying bandwidth remains inconsistent. While the first contribution of this paper is novel, I question whether it is significant enough for paper acceptance, especially given my concerns regarding the second contribution.\n\nReference:\n- Barzilai, Daniel, and Ohad Shamir. \"Generalization in kernel regression under realistic assumptions.\" arXiv preprint arXiv:2312.15995 (2023).\n- Cheng, Tin Sum, et al. \"Characterizing overfitting in kernel ridgeless regression through the eigenspectrum.\" arXiv preprint arXiv:2402.01297 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Below we address the main comments:\n1. Regarding the wrong predictions of the Gaussian Universality Ansatz (GUA): There is ample empirical evidence that the eigenframework holds well for the Gaussian kernel. For example, Figure 1 in [38] shows the predicted vs. true test risk for Gaussian KRR (with data from MNIST) and Figure 5 in [7] shows the true vs. predicted risk for Gaussian KRR with data uniform on the sphere (which is the setup we consider here). In both of these plots, the prediction matches closely with the true test risk. Furthermore, there are many works that rely on the eigenframework, such as [1, 7, 12, 25, 47, 54, 63]. Therefore, this limitation holds for the entire line of work and not just for the current paper. We agree with the reviewer that understanding the limitations of this framework is an important future research direction. We will update the paper to highlight this as a limitation.\n\n2. Experimental results confirming the validity of our claims: In the attached PDF, we plotted the dependence of the test error on sample size for the Gaussian kernel ridgeless (interpolating) predictor. In Figure a, we consider the first case of Theorem 1, namely when the bandwidth $\\tau_m = o(m^{-\\frac{1}{d-1}})$. It shows that the test error tends to something equal to or larger than the test risk of the null predictor. In Figure b, we consider the second case, i.e $\\tau_m = \\omega(m^{-\\frac{1}{d-1}})$ and the plot shows that the test error increases with sample size, which aligns with the claim that it diverges as the sample size $m$ increases. In Figure c, we consider the case when $\\tau_m = \\Theta(m^{-\\frac{1}{d-1}})$ and the plot shows that for some noise level (which is high enough), the predictor is worse than the null predictor, as predicted by our theorem. We will add these simulations to the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all of the reviewers for their thoughtful feedback.
In the attached PDF, we provide empirical evidence that our predictions are correct. We focus on the finite-dimensional case because of computational constraints. In Figure a, we consider the first case of Theorem 1, namely when the bandwidth $\tau_m = o(m^{-\frac{1}{d-1}})$. It shows that the test error tends to something equal to or larger than the test risk of the null predictor. In Figure b, we consider the second case, i.e $\tau_m = \omega(m^{-\frac{1}{d-1}})$ and the plot shows that the test error increases with sample size, which aligns with the claim that it diverges as the sample size $m$ increases. In Figure c, we consider the case when $\tau_m = \Theta(m^{-\frac{1}{d-1}})$ and the plot shows that for some noise level (which is high enough), the predictor is worse than the null predictor, as predicted by our theorem. We will add these simulations to the final version of the paper.

Meta-review: The paper investigates how the "predicted risk" of kernel rigdeless 
regression behaves for Gaussian kernels on the sphere if the width 
changes with the sample size. The first main result shows that 
catastrophic or tempered behavior of this risk surrogate occurs depending
on how the width changes. The second main result establishes a
similar result for more general kernels (without a width parameter) 
if the dimension increases. 

The paper enjoyed serious reviews as well as a productive rebuttal phase. 
Most concerns centered around: a) the used eigenframework,
b) the Gaussian universality assumption, and c) the novelty of 
the technical contribution. In view of a) the authors argued with a list 
of recent papers working with the same assumption. However, about half
of these papers have not been published, yet, and hence it is probably
too early for a decisive conclusion about this framework. However, I 
would argue for an "in dubio pro accept" approach as the alternative 
(if applied consistently in all areas of ML) would substantially slow
down scientific progress. Issue b) is actually closely related to a) 
for the paper under review as it provides a "justification" for a). 
In view of c) the authors made a convincing case that they do not 
simply apply the work of others. 

Overall, I agree with the outcome of the discussion which went in favor
of accepting the paper despite the fact that some parts (e.g. Example 1)
could certainly be improved or clarified.
Decision: Accept (poster)