Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality

Authors: marko  medvedev
gal  vardi
nathan  srebro
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:37:02

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.

Main paper: 
 introduction: 
 A 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 leads 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 error when training on noisy data as the number of samples tends to 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] , i.e. 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 is decreased, when the sample size increases [51, 19] . Additionally, it makes sense to 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 are used, even with a kernel; because as more resources are available we scale 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 a kernel is used we can study the behaviour even when the input dimensionality increases much slower, and ask how slowly it could increase without catastrophic overfitting. Previous studies on kernel ridgeless regression considered polynomial increasing dimension (i.e. dimension ∝ sample-size a , for 0 < a ≤ 1) [4, 64, 24, 38, 40] , but not subpolynomial scaling.We aim 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, 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, as we show the first example of sub-polynomially scaling dimension that achieves benign overfitting for the Gaussian kernel. Additionally, we show that a class of dot-product kernels 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] .The test performance of overfitting models has been extensively studied for linear regression [27, 6, 3, 43, 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, 29] , and kernel methods. Below we focus on overfitting in kernel ridge regression. with zero mean independent noise ξ with variance σ 2 , that is y ∼ f * (x) + ξ. We note that our results can be extended to a distribution agnostic setting, as analyzed by Zhou et al. [66] .Let K : X × X → R be a positive semi-definite kernel function. Let ∥f ∥ K be the norm of f in the RKHS H K corresponding to K. For a predictor f , let R(f ) and R(f ) be the test and training risk of f ,R(f ) = 1 m m i=1(f (x i ) -y i ) 2 and R(f ) = E D (f (x) -y) 2 .Two important risks to consider are the risk of the null predictor, f ≡ 0, which we will denote by R(0) = E D [(y) 2 ], and the Bayes (or irreducible) risk, which we will denote σ 2 or R(f * ). Using this notation, the risk of the null predictor is R(0) = σ 2 + E D [(y) 2 ]. Bayes risk represents the minimum possible risk that can be achieved by any predictor. For a regularization parameter δ, the regularized ridge solution fδ is given byfδ = argmin f ∈H K R(f ) + δ m ∥f ∥ 2 K .We are interested in the minimum norm interpolating (ridgeless) solution f0 = lim δ→0+ fδ , namelyf0 = argmin R(f )=0;f ∈H K ∥f ∥ 2 K .We will focus on the Gaussian kernel, which is given by K(x 1 , x 2 ) = exp -∥x1-x2∥ 2 2 τ 2 m, where m is the sample size and τ m is a predetermined bandwidth parameter that can vary with sample size. The Gaussian kernel is widely used and achieves good error rates for a variety of learning tasks [51, 19] . Gaussian KRR achieves optimal convergence to the best possible (Bayes) error for learning any function in a 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 × Y [19] . For ridge regression with the Gaussian kernel and under a standard data distribution assumption, the minimum distance between samples decreases with sample size so it makes sense to also decrease τ m . Additionally, decreasing τ m with sample size helps to achieve good convergence rates theoretically [19] .Main question. We will consider the problem of learning using the minimum norm interpolating solution f0 of KRR. We want to understand the limiting behavior of test risk R( f0 ) as the sample size increases m → ∞, that is lim m→∞ R( f0 ). It suffices to understand lim sup m→∞ R( f0 ) and lim inf m→∞ R( f0 ) 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 lim m→∞ R( f0 ) 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, we 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.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 theorem decomposition of a kernel function K.Given a positive semi-definite kernel function K : X × X → R, we can decompose it asEQUATIONwhere λ k and ϕ k are the eigenvalues and eigenfunctions of the integral operator associated to K. The eigenfunctions {ϕ k } are an orthonormal basis of L 2 D X (X ), where D X is the marginal distribution of X . We denote the Bayes optimal target function by f * , and expand it in the kernel basis{ϕ i } ∞ i=1 as f * (x) = ∞ i=1 β i ϕ i (x).To state the close form of the test risk we will introduce a few quantities. Let effective regularization, κ δ , be the solution to∞ i=1 λi λi+κ δ + δ κ δ = m. Furthermore, let L i,δ = λi λi+κ δ and E δ = m m-∞ i=1 L 2 i,δ. Then, the predicted risk, i.e. the predicted closed form of the test risk of fδ , is given byEQUATIONwhere σ 2 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 a 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 a good estimate of the true test risk, namely R( fδ ) ≈ R( fδ ). Indeed, a 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. Assumption 1 (Gaussian design ansatz, cf. Zhou et al. [66] ). When sampling (x, •) ∼ D, we have that the Gaussian universality holds for the eigenfunctions in the sense that the expected risk is unchanged if we replace ϕ with φ, where φ is Gaussian with appropriate parameters, i.e. φ ∼ N (0, diag{λ i }).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, 57] .As discussed in Zhou et al. [66] , under this assumption, the equivalence R( fδ ) ≈ R( fδ ) 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 a small sample size m [8, 50] . 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 a 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( fδ ) and R( fδ ) 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( fδ ), but as previously presented evidence suggests, treating R( fδ ) ≈ R( fδ ) 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 we described ample empirical evidence that the eigenlearning predictions hold [8, 41] . Understanding the limitations of the eigenframework is an important future research direction. 
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 D be the distribution over X × Y = S d-1 × R, such that the X marginal, denoted by D X , is Unif(S d-1 ). We will assume that for a target functionf * ∈ L 2 D X (S d-1), the marginal Y distribution is given by y ∼ f * (x) + ξ, where ξ has mean zero and variance σ 2 > 0. We write f * = i β i ϕ i , where{ϕ i } is the L 2 D X (S d-1) eigenbasis corresponding to the kernel K (Equation ( 1)). If we write β = (β 1 , β 2 , . . . ), then we have that ∥β∥ 2 2 = E D X (f * (x)) 2 . We will use the notation ∥f * ∥ 2 = ∥β∥ 2 2 .The assumption on the distribution on X is common in the literature on KRR [38, 4, 64, 22] . The assumption that x ∼ Unif S d-1 can be relaxed to a 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 τ m so both f0 and R( f0 ) will depend on the bandwidth τ m 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 is 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( f0 ) of the minimum norm interpolating solution of Gaussian KRR:1. If τ m = o(m -1 d-1 ), then R(0) ≤ lim inf m→∞ R( f0 ) ≤ lim sup m→∞ R( f0 ) < ∞. More precisely, if τ m ≤ m -1 d-1 t(m), where t(m) → 0 as m → ∞, then there is a scalar c d that depends only on the dimension and m 0 that depends on t(m) such that for all m > m 0 we have R( f0) > σ 2 + (1 -c d t(m) d-1 2 )∥f * ∥ 2 . 2. If τ m = ω(m -1 d-1 ), then lim m→∞ R( f0 ) = ∞.Hence, for large enough m we have R( f0 ) > R(0).m = Θ(m -1 d-1 ), then lim sup m→∞ R( f0 ) < ∞. Moreover, Suppose that C 1 m -1 d-1 ≤ τ m ≤ C 2 m -1 d-1for some constants C 1 and C 2 , then there exist η, µ > 0 that depend only on d, C 1 , and C 2 , such that for all m we have R( f0 )> µ∥f * ∥ 2 +(1+η)σ 2 . Consequently, R( f0 ) > R(0) as long as σ 2 > 1-µ η ∥f * ∥ 2 .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 is never better than the null predictor. In the third case, the interpolating solution is worse than null for noise that is not too small. This shows that even though the minimum norm interpolating predictor is classified as 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 τ m = Θ(m1 d-1) there exists small enough σ 2 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.m = Θ(m -1 d-1 ), then lim sup m→∞ R( f0 ) < ∞. Moreover, suppose that C 1 m -1 d-1 ≤ τ m ≤ C 2 m -1 d-1for some constants C 1 and C 2 , then there exist η, µ > 0 that depend only on d, C 1 , and C 2 , such that for all m we have R( f0 )> µ∥f * ∥ 2 +(1+η)σ 2 . Consequently, R( f0 ) > R(0) as long as σ 2 > 1-µ η ∥f * ∥ 2 .Proof. All three proofs will similarly follow by directly analyzing Equation ( 2).Part 1: Note that for any i, we have that λi + κ 0 ≤ λ1 + κ 0 , so we have thatL i ≥ λi λ1 L 1 . FromTheorem 28 we know that for j ≤ √ T t(m) m = i N (d, i)L i > N (d, 1) + . . . N (d, √ T t(m)) 1 2 L 1 .Note that N (d, 1) + . . . N (d,√ T t(m)) > c l √ T t(m) 1 2 d-1 = c ′ l m(t(m)) -d-1 2 , where c ′ l = √ 2c l . Therefore, we have that L 1 < 2 c ′ l (t(m)) d-12 . Therefore, we have thatEQUATION.From Equation (2), we have that thenR( f0 ) ≥ E 0 σ 2 + E 0 (1 -c d t(m) d-1 2 )∥β∥ 2 .This shows the first claim.For the second part, note the following property of L i,δ = λi λi+κ δ : if for j > i, we have that L i,δ > L j,δ . Let λj λi > c for some fixed c > 0 and j > i, then we have thatL j,δ > cL i,δ .By Theorem 28, we have that for j ≤ √ T g(m) with g(m) → 0 as m → ∞λk +j λk > exp (-5g(m)) .So there is m > m 0 such that for m > m 0λk +j λk > exp (-5g(m)) > 1 2 . Note that m m - ∞ i=1 L 2 i,δ (1 -L j,δ ) 2 > 1 if ∞ i=1 L 2 i,δ > mL j,δ (2 -L j,δ )For this it suffices to have∞ i=1 L 2 i,δ > mL 1,δ (2 -L 1,δ ) ,since L i,δ are decreasing. Note that there is at leastN (d, 1) + • • • + N (d, √ T g(m)) > n l ( √ T g(m)) d-1 > c u m g(m) t(m) d-1of indices i such thatλ i λ 1 = λ1+j λ1 > 1 2 .Therefore, if we select g(m) = t(m), then we have that∞ i=1 L 2 i,δ > 1 2 c u m 1 t(m) d-1 2 > mL 1,δ (2 -L 1,δ ) .This implies that for all j simultaneously m m -∞ i=1 L 2 i,δ (1 -L j,δ ) 2 > 1.R( f0 ) > R(0) + m m - ∞ i=1 L 2 i,δ -1 σ 2 .This finishes the proof of the first part.Part 2: Note that we showed that for m large enough, E 0 > √ m. This shows thatR( f0 ) = E 0 i (1 -L 0 ) 2 v 2 i + σ 2 > √ mσ 2 .So, there is m 0 that depends only on t(m) such that for m > m 0 we have that R( f0) > √ mσ 2 . Part 3: Note first that L i ≥ L j for i ≤ j. Let T = 2 τ 2 m. From Lemma 26 it follows thatn l (α √ T ) d-1 ≤ N (d, 1) + • • • + N (d, α √ T ) ≤ n u (α √ T ) d-1 . Take α such that N (d, 1) + • • • + N (d, α √ T ) > 2m.Then, we have thatm = i N (d, i)L i > (N (d, 1) + • • • + N (d, α √ T ))L α √ T > 2mL α √ T L α √ T ≤ 1 2 =⇒ λ α √ T ≤ κ 0 . Note that (1 -L 1 ) 2 < (1 -L i ) 2 and (1 -L 1 ) 2 = κ 2 0 (λ 1 + κ 0 ) 2 . If κ 0 > λ 1 , then 2κ 0 > λ 1 + κ 0 , so 1 2κ0 < 1 λ1+κ0. This shows thatEQUATION.From Theorem 28 it follows thatλ α √ T 4λ 2 1 > exp(-α 2 ). Since 1 nu 2 C 2 1 1 d-1 < α < 1 n l 2 C 2 2 1 d-1 , we know that exp -α 2 > exp - 1 n l 2 C 2 2 2 d-1 , so µ = exp - 1 n l 2 C 2 2 2 d-1. Combining Lemma 18 and Lemma 19, we get Theorem 3.In Appendix C.1 we will prove Theorem 7 and Theorem 9. 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 a detailed proof of Corollary 13. In Appendix C.4, we will discuss when the conditions posed on kernels are satisfied.Theorem 20 (Error scaling for any kernel ridge regression). Let d and m be any dimension and sample size. Define L m , U m , k m , N (i), N l , and λk as in Definition 5. Consider KRR with a kernel K satisfying Assumption 6 for some A. Assume that for some integer l, the target function f * satisfies Assumption 4 with at most N l nonzero coefficients. Then, the risk of the minimum norm interpolating solution is bounded by the following:EQUATIONAdditionally, we can get an alternative bound if we swapl i=1 N (d, i) 1 λ2 i with l i=1 N (d, i) 1 λi , i.e. R( f0 ) ≤ 1 - L m m -1 1 - m L m -1 σ 2 +B 2 1 - L m m -1 1 - m L m -1 A m 2 Lm i=1 N (d, i) 1 λi .Proofs of Theorem 7 and Theorem 20: Note first that Equation (2) implies thatR( f0 ) = i E 0 (1 -L i,0 ) 2 β 2 i + E 0 σ 2 . Let L i = λi λi+κ0. Then, we can rewrite it asR( f0 ) = i E 0 N (d, i) (1 -L i ) 2 β 2 i + E 0 σ 2 ,with a slight of abuse of notation for β i . From Equation ( 5), we have that for k < mE 0 ≤ 1 - k m -1 1 - m k + r k -1. Take k = L m . Note that by Definition 5, L m < m Then λ k+1 = λkm+1 and it repeats N (d, k m + 1) times. Therefore, we have thatr k = N (d, k m + 1) + ∞ i=1 N (d, k m + i + 1) λkm+i+1 λkm+1.Therefore, r k + k > N (d, k m + 1) + L m = L m > m.Therefore, we can apply Equation ( 5). We get thatE 0 ≤ 1 - k m -1 1 - m k + r k -1 = 1 - L m m -1 1 - m L m -1.m = i N (d, i)L i .Note that λi + κ 0 > κ 0 so we have that L i < λi κ0 . Therefore, we have thatm = i N (d, i)L i < 1 κ 0 i N (d, i) λi < A κ 0 .Therefore, we have thatκ 0 < A m . Since (1 -L i ) 2 = κ 2 0 (κ0+ λ) 2 < κ 2 0 λ2. Since there are only l d nonzero β i , we have thati N (d, i)(1 -L i ) 2 β 2 i ≤ B 2 A 2 m 2 l i=1 N (d, i) 1 λ2 i .Going back to Equation (2), we haveR( f0 ) = E 0 i (1 -L i ) 2 N (d, i)β 2 i + E 0 σ 2 ≤ E 0 B 2 A 2 m 2 l i=1 N (d, i) 1 λ2 i + E 0 σ 2 ≤ 1 - L m m -1 1 - m L m -1 σ 2 + 1 - L m m -1 1 - m L m -1 B 2 A 2 m 2 l i=1 N (d, i) 1 λ2i This shows the first bound. For the second bound, note that∞ i=1 κ 2 0 (κ 0 + λ i ) 2 β 2 i ≤ ∞ i=l+1 β 2 i + l i=1 β 2 i 1 i λ i 1 λ i j>l λ j m 2 .So if we take β to have only l nonzero terms, we getl i=1 κ 2 0 (κ 0 + λ i ) 2 β 2 i ≤ l i=1 β 2 i 1 i λ i 1 λ i j>l λ j m 2 .From this, we have thatl i=1 κ 2 0 (κ 0 + λ i ) 2 β 2 i ≤ A λ i 1 m 2 .Therefore, we have thatN (d, i) κ 2 0 (κ 0 + λi ) 2 β 2 i ≤ N (d, i)β 2 i A λ i 1 m 2 .Therefore, we have the improved inequality froml i=1 N (d, i)(1 -L i ) 2 β 2 i ≤ l i=1 β 2 i N (d, i) A λ i 1 m 2 .This gives the second bound on the test risk, as we can boundl i=1 N (d, i)(1 -L i ) 2 β 2 i ≤ B 2 A m 2 l i=1 N (d, i) 1 λ i .[Lower bound for test risk in increasing dimension] Let k m and L m 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:R( f0 ) > 1 - b b + 1 2 L m m -1 σ 2 .Proof of Theorem 9: By Theorem 3 from Zhou et al. [66] , if k is the first k < m such that k + br k ≥ m, thenE 0 ≥ 1 - b b + 1 2 k m -1 .Therefore, it suffices to show that the first such k is actuallyL m = N (d, 1) + • • • + N (d, k m ). Note that r k = i>k λ i λ k+1 < max i≤k 1 λ i ( i>k λ i ) < A max i≤k 1 λ i . Since max i≤km 1 λi < m-Lm b , for l < N (d, 1) + • • • + N (d, k m ), we have that br l + l ≤ N (d, 1) + • • • + N (d, k m ) -1 + b max i≤km 1 λi < L m + m -L m ≤ m, so the first l for which r l + l > m is l = L m = N (d, 1) + • • • + N (d, k m ). Plugging in k = L m we get that E 0 ≥ 1 -b b+1 Lm m -1, so from Equation ( 6), we haveR( f0 ) ≥ 1 -b b+1 2 Lm m -1 σ 2 .C.2 Dot-product kernels on the sphere First we will prove results about the eigenvalue multiplicites Corollary 12 and Corollary 13. Theorem 21 (Log-scaling multiplicity). Let d = log 2 m, i.e. m = 2 d , and let k d be an index for which the following holds:N (d, 1) + • • • + N (d, k m ) < m N (d, 1) + • • • + N (d, k m + 1) ≥ m.Then the following hold: → 0. This also holds for dN (d,k)2 d with k = f (d) ≤ d 5 for all d. 2. N (d, d 2 ) 2 dis increasing and has lim d→∞N (d, d 2 ) 2 d → ∞.This also holds for N (d,k) 2 d with k = f (d) ≥ d 2 for all d.3. There is an absolutet constant d 0 such that for d > d 0 , we have thatd 5 ≤ k m ≤ d 2 .4. There are absolute constants c l-1 = 1 54 , c l = 1 9 , and c l+1 = 2 3 such that N (d, k m + i) > c l+i m, for all i ∈ {±1, 0}. Additionally, there are constantsc u-1 = 1 3 , c u = 1, c u+1 = 6, such that N (d, k m + i) < c u+i m for all i ∈ {±1, 0}. Furthermore, if d log m = Θ(1), then we will also have L m = Θ(m) and L m = Θ(m).Proof. We will split the proof into three parts. Note first that N (d, k) increases as k increases. This can be seen from the ratio of consecutive multiplicitiesN (d, k + 1) N (d, k) = 2k + d 2k + d -2 k + d -2 k + 1 .Part 1: We will use Stirling's approximation to estimate N (d, k). It states that n! ≈ n e n √ 2πn. Therefore, we have that N (d, k) = (2k + d -2)(k + d -3)! k!(d -2)! ≈ 2π(k + d -3) k+d-3 e k+d-3 (2k + d -2) k e k d-2 e d-2 √ k √ d -2 . Since N (d, k) is increasing in k and k ≤ d 5 ,√ d = 5 1/5 ( 6 5 ) 6/5 d √ d .Note that 5 1/5 ( 6 5 ) 6/5 < 1.8, so(5 1/5 ( 6 5 ) 6/5 ) d √ d < 1.8 d √ d .In particular, we have thatdN (d, d 5 ) 2 d < √ d(1.8) d 2 d → 0.Part 2: The same calculation in this case gives N (d, d 2 ) ≈ C 2 1 2 ( 3 2 ) 3 2 d √ d but note that 2 1 2 ( 3 2 ) 3 2 > 2.5, so N (d, d 2 ) 2 d > 2.5 2 d 1 √ d → ∞. Part 3: Note that if k m ≤ d 5 then for d large enough N (d, 1) + • • • + N (d, k m ) ≤ k m N (d, k m ) ≤ dN (d, k m ) < d. Similarly, note that if k m > d 2 , then N (d, k m ) > dm < N (d, 1) + • • • + N (d, k m + 1) < N (d, k m + 1) 1 + 1 3 + ( 1 3 ) 2 + . . . < N (d, k m + 1) 3 2 2 3 m < N (d, k m + 1). This now implies that N (d, k m ) > 1 6 N (d, k m + 1) > 1 9 m, N (d, k m -1) > 1 54 m. Similarly we have that N (d, k m ) < m, so N (d, k m + 1) < 6m and N (d, k m -1) < 13 m. Note that the same proof works even if d is not exactly equal to log 2 m. This shows that wheneverd log m = Θ(1), we have that L m = Θ(m) and L m = Θ(m).Remark 22. Note that this does not say that we will always have tempered overfitting for d log m = Θ(1) as sometimes it can happen that L m → m, so we cannot apply Equation ( 5) and Equation (6) . In this case we expect the overfitting to be catastrophic.Theorem 23 (Sub-polynomial scaling multiplicity). Let K be any dot product kernel on the sphere S d-1 (with nonzero eigenvalues). Let l ∈ N and let m = 2 2 2l and let d = 2 2 l . This corresponds to the case d = exp √ log m , which is sub-polynomial. Then, for the upper and lower index, L m and L m , we have the followingL m m ≤ 3 2 log m and m L m ≤ 1 d 0.89 .Additionally, for k = αk m , where α is a constant, we have that N (d, k) ≈ m α , where ≈ means up to sub-polynomial factors.Proof. Let k m be the maximum k for whichN (d, 1) + • • • + N (d, k m ) < m N (d, 1) + • • • + N (d, k m + 1) ≥ m. We want to show that N (d, k m ) = o(m) and N (d, k m + 1) = Ω(m). Then we can take k = N (d, 1) + • • • + N (d, k m ) and so k m → 0 and r k = N (d, k m + 1) + j=2 N (d, k m + j) λkm+j λkm+1 = Ω(m) m R k → 0.Note that we just need to estimate N (d, k m ) precisely. Let k = 2 l + l. We want to show that N (d, k) > m. Note that by Stirling's approximation n! ≈ n e n √ 2πnN (d, k) ≈ 2π(k + d -3) k+d-3 e k+d-3 (2k + d -2) k e k d-2 e d-2 √ 2πk 2π(d -2) = e √ 2π d k+d-2 √ d 2π(1 + k d -3 d ) 1 + k d -3 d k+d-3 1 + 2k d -2 d k k (d -2) d-2 √ k √ d -2 = e √ 2π d k+d-2 √ d 2π(1 + 2 l +l 2 2 l -3 2 2 l ) 1 + 2 l +l 2 2 l -3 2 2 l k+d-3 1 + 2k d -2 d k k d d-2 (1 -2 d ) d-2 √ k √ d 1 -2 d = e √ 2π d k 2π(1 + k d -3 d ) 1 + k d -3 d k+d-3 1 + 2k d -2 d (1 -2 d ) d-2 1 -2 d = e √ 2π 2π(1 + k d -3 d ) 1 + 2k d -2 d (1 -2 d ) d-2 1 -2 d d k k k √ k 1 + k d - 3 d k+d-3.Only the term d k k k √ k 1 + k d -3 d k+d-3is asymptotic here, as the rest tends to a constant as d → ∞.Note that since for all l > 5 (i.e. d)2 > 1 + k d - 3 d d k > 1.95,we have that1 + k d - 3 d k+d-3 > (1.95) k 2 d +k-3 k d > (1.95) k > 2 (0.9k) 1 + k d - 3 d k+d-3 < 2 k 2 d +k-3 k d .Note that we have that thend k k k √ k 1 + k d - 3 d k+d-3 < d k k k √ k 2 k 2 d +k-3 k d = 2 k log d-k log k-1 2 log k+ k 2 d +k-3k d .k log d -k log k -1 2 log k + k 2 d + k -3k d . For k = 2 l + l -1, we have that k log d -k log k - 1 2 log k + k 2 d + k - 3k d = k log d -k log k + k - 1 2 log k - 3k d + k 2 d = 2 l + l -1 2 l -2 l + (l -1) l + l -1 2 l + o( 1 2 2l ) - 1 2 (l) + o( 1 2 l ) + 2 l + l -1 + o( 1 2 l ) = 2 2l + 2 l (l -1) -2 l (l) + 2 l -l + 1 - 1 2 l + l -1 + o(1) = 2 2l - 1 2 l = log 2 m -log 2 log 2 m.In particular, this implies that for k ≤ 2 l + (l -1), we have thatN (d, k) < m2 -1 2 l = o(m).Now repeating the same computation for k = 2 l + l, we have thatd k k k √ k 1 + k d - 3 d k+d-3 > d k k k √ k 2 0.9k = 2 k log d-k log k-1 2 log k+0.9k . k log d -k log k - 1 2 log k + k 2 d + 0.9k - 3k d = k log d -k log k + k - 1 2 log k - 3k d + k 2 d = 2 l + l 2 l -2 l + l l + l 2 l + o( 1 2 2l ) - 1 2 (l) + o( 1 2 l ) + 0.9 • 2 l + 0.9l + o( 1 2 l ) = 2 2l + 2 l (l) -2 l (l) + 0.9 • 2 l -l - 1 2 l + l + o(1) = 2 2l + 0.9 • 2 l - 1 2 l = log 2 m + 0.9 • log 2 m -log 2 log 2 m.This shows that for k ≥ 2 l + l, N (d, k) > m2 0.9•2 l -1 2 l = Ω(m).To imply now thatk m = k = 2 l + l -1, it suffices to show that N (d, 1) + • • • + N (d, k) = o(m).But note that we have k ≪ d, soN (d, k -1) = 2k + d -2 2k + d k + 1 k + d -2 N (d, k) < 1 d N (d, k) N (d, 1) + • • • + N (d, k -1) < k -1 d N (d, k) N (d, 1) + • • • + N (d, k) = o(m).Therefore, we have computed with proof that k m = 2 l + l -1. So we can now compute L m and L m with L m = N (d, 1) + • • • + N (d, k m ). Note that N (d, k + 1) N (d, k) = 2k + d 2k + d -2 k + d -2 k + 1 . Since k << d, note that N (d,k+1) N (d,k) > 2, so we have that N (d,k) N (d,k+1) < 1 2 , which implies that N (d, 1) + N (d, 2) + • • • + N (d, k m ) < 3 2 N (d, k m ) = o(m).L m > N (d, k) > m2 0.9•2 l -1 2 l m L m < 1 d 0.9-1 2 log log dlog d < 1 d 0.89 .Note finally that for k = α2 l , the leading term in the exponent of N (d, k) as derived above is α2 2l , all other terms are at most l2 l , which is sub-polynomial in m, so this shows that N (d, αk) ≈ m α . 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 k , for integer k. Similarly in this case, there are sequences of (m, d) for which we do not get benign overfitting, but is much harder to identify them.Corollary 3 (Benign overfitting with Gaussian kernel and sub-polynomial dimension). Let K be the Gaussian kernel on the sphere S d-1 with a fixed bandwidth, and suppose that for l ∈ N the dimension and sample size scale as d = 2 2 l , m = 2 . Then, we have that the minimum norm interpolating solution achieves the Bayes error in the limit (m, d) → ∞. In particular, for d ≥ 4 and m ≥ 16 we haveR( f0 ) ≤ 1 - 1 log m -1 1 -exp -0.89 log m -1 σ 2 + 2B 2 1 m .If we take S d = poly(d), then we can improve the 1 m error dependence to = 2 l + l -1 = log d + log log d -1, L m = Θ( m log m) and L m ≥ Θ(md 0.89 ). Therefore, we have thatE 0 ≤ 1 - 1 log m -1 1 -exp -0.89 log m -1 .To finish the proof, we need to estimate N (d, 1) 1 λk λ1 > k i=1 2 τ 2 m 2 τ 2 m + 2(i + d 2 -1).Therefore, we have that1 λk < 1 λ1 k i=1 2 τ 2 m + 2(i + d 2 -1) 2 τ 2 m = d α τ 2 m 2 k Γ(d + 2k m + 2 τ 2 m ) Γ( d 2 )Γ(d + 2 τ 2 m ) < d α τ 2 m k d 2 + k + 2 τ 2 m k .Note also that if k = βk m for some constant β thenN (d, k) ≈ m β , in the sense of Theorem 23. So, N (d, k m ) 1 λ2 km < m β d 2k(1+ε)-2α. We want to take k as large as possible, so we will take it k = βk m . Then d 2k ≈ m 2β . Therefore, as long as 3β < 2, we will have a polynomially scaling error. So we can take β =2 3 . Note that with Theorem 20, we actually get even better dependence of the error, like m β d k(1+ε)-α . Plugging the first estimate into Theorem 7, for 3α = 1, we have thatR( f0 ) ≤ 1 - 1 log m -1 1 - 1 d 0.89 -1 σ 2 + B 2 1 - 1 log m -1 1 - 1 d 0.89 -1 1 m 2 m 3β ≤ 1 - 1 log m -1 1 - 1 d 0.89 -1 σ 2 + B 2 1 - 1 log m -1 1 - 1 d 0.89 -1 1 m .If we want to achieve S d = poly(d), note that we just need to take k to not scale wit d. That is, if we want deg S d = n, then we can take k = n. The eigenvalue will be1 λn < d α+2n .The multiplicity will be N (d, n) = Θ(d n ). Note that then error scales as d 5n m 2 , i.e. since d is sub poly m, we can take any such n.We have three main assumptions on kernels. First, the sum of its eigenvalues is bounded. 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=1 N (i) λi ≤ A. For a sequence of kernels K (d) , assume that all such A (d) are bounded by some constant A. 2 Second, there is a lower bound on the eigenvalues. Assumption 8 (Lower bound on eigenvalues). Assumme that the kernel K has eigenvalues that are not too small, i.e. there is a constant b such that max i≤km1 λi < m-Lm b. For a sequence of kernels K (d) , assume that for the corresponding m = m(d) (since d = d(m), we can also "invert" the dependence) all such b (d) are bounded below by some b.And third, the eigenvalues don't decrease too fast. Assumption 10 (Eigenvalue decay). The eigenvalues don't decrease too quickly, i.e. for k m as in Definition 5, we have that there is a constant c such that max i≤km 1 λi ≤ cN (k m ). For increasing dimension, we require that max i≤km1 λi ≤ cN (d, k m ).Note that Assumption 6 will hold quite broadly, in particular at least for dot product kernels on the sphere (that are 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 L m and k m , i.e. since L m = N (1) + • • • + N (k m ), we have that N (k m ) < m and as long as L m < Θ(m), we can take b large. This is usually the case (we show previously in Appendix C.2 for dot-product kernels on the sphere). 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 ϕ i are actually the spherical harmonics Y ks . Let K(x, y) = h(∥x -y∥). Note that for x ∈ S d-1 , it holds thatN (d,k) s=1 Y ks (x) 2 = N (d, k). Therefore, since K(x, y) = i λ i ϕ i h(0) = K(x, x) = k N (d,k) s=1 λk Y ks (x) 2 = k N (d, k) λk .So the assumption in Theorem 7 holds with A = h(0). For the Gaussian kernel, this is A = 1. Similarly, A = 1 for Laplace kernel.Second Assumption: For the eigenvalue assumption, max i≤km1 λi < m-LmAb , note the following. We will usually have L m = o(m). In particular, whenever d = ω(log m) for a dot-product kernel on the sphere this will hold.The eigegnvalue assumption will hold for the Gaussian kernel in the non-integer polynomial regime, d α = m. In Appendix C.3, we showed that 1 λk < d k , so since k m = ⌊α⌋, we will have Furthermore, this assumption can be weakened to the following: there exists b > 0 such for all k ≤ L m , b i>k λ i < λ k+1 (m -k). Additionally, since the assumption is specific to our approach, it seems to be possible to weaken it even further.Third assumption: This assumption holds for 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. It is 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 i ≤ k m .In this section, we will summarize and prove the results about eigenvalues of Gaussian and Laplace kernels when X ∼ Unif(S d-1 ).Given a positive semi-definite kernel function K : X × X → R, we can decompose it asK(x, t) = ∞ i=1 λ k ϕ k (x)ϕ k (t),where λ k and ϕ k are the eigenvalues and eigenfunctions of the operator associated to K, L K :L 2 D X (S d-1 ) → L 2 D X (S d-1 ) L K (f )(x) = X K(x, t)f (t)dµ(t).L K is a Hilbert-Schmidt operator and has a countable system of non-negative eigenvalues λ k satisfying∞ k=1 λ 2 k < ∞. The corresponding L 2 D X (S d-1 )-normalized eigenfunctions {ϕ k (x)} ∞ k=1 form an orthonormal basis of L 2 D X (S d-1). The eigenfunctions in this case are given by spherical harmonics, Y i,s . The eigenvalues corresponding to all Y i,s for fixed i have the same eigenvalue, λi . Eigenvalues λi are reach repeatedN (d, i) = (2i+d-2)(i+d-3)! i!(d-2)!times. So the sequence {λ i } ∞ i=1 = λ1 , . . . , λ1 , λ2 , . . . , λ2 , . . . . Using Funk-Hecke formula, we can compute λk explicitly, both for the case of Gaussian [46] kernel. For Gaussian kernel, we have the following theorem about the eigenvalues λk .Theorem 25 (Eigenvalues of the Gaussian kernel [46] ). Let X ∼ Unif(S d-1 ), with d ∈ N and d ≥ 2.For K(x, t) = exp -∥x-t∥ 2 τ 2 m , τ m > 0, and k ∈ N 0 we have thatλk = e -2 τ 2 m τ d-2 m I k+ d 2 -1 2 τ 2 m Γ d 2 .Each λk occurs with multiplicityN (d, k) = (2k+d-2)(k+d-3)! k!(d-2)!(we use λ notation to indicate that it has multiplicity) and its corresponding eigenfunction are the spherical harmonics of order k on S d-1 . Here, I v (z), v, z ∈ C is the modified Bessel function of the first kindI v (z) = ∞ j=0 1 j!Γ(v + j + 1) z 2 v+2j .It will be useful to know the size of N (d, i). Also, the size of the sum of the first k multiplicities will be useful.Let N k = k i=1 N (d, i). Lemma 26 (Size of multiplicity). For N (d, i) = (2k+d-2)(k+d-3)! k!(d-2)! , it holds that 1 (d -2)! k d-2 ≤ N (d, i) ≤ 2 d-1 k d-2 .Additionally, there exist constants n l , n u > 0 depending on the dimension d such that N k is bounded below and above by the followingn l k d-1 ≤ N k ≤ n u k d-1 .Proof. Since (2k + j) ≤ (2k)j for j ≥ 2 and (k + 1) ≤ 2k, we have thatN (d, k) = (2k + d -2)(k + d -3) . . . (k + 1) (d -2)! ≤ (d -2)!(2k) d-3 (2k) (d -2)! ≤ 2 d-1 k d-2andN (d, k) = (2k + d -2)(k + d -3) . . . (k + 1) (d -2)! ≥ 1 (d -2)! k d-2 .Note that by Bernoulli's formulak l=1 l d-2 = 1 d -1 k d-1 + o(k d-1) .Therefore, we have thatn l k d-1 ≤ 1 (d -1)(d -2)! k d-1 + o(k d-1 ) ≤ N k ≤ 2 d-1 d -1 k d-1 + o(k d-1 ) ≤ n u k d-1 .Lemma 27 (Inverting the index). If the index of an eigenvalue λj is such that N k-1 ≤ j ≤ N k -1, then λj = λ k . We will denote such j with k, i.e. k is an index such that λk = λ k .Proof. Immediate from the fact that {λ i } ∞ i=1 is a sequence with λi repeating N (d, i) times, in that order.An interesting property of eigenvalues of the Gaussian kernel is that they are sorted because the Modified Bessel functions are [48] . In particular, I v+1 (x) < I v (x) for all v, x > 0, so λi+1 < λi . This is not the case for the Laplace kernel. Proof. First of all, note that from [48] , we have that for 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 λk of bandwidth τ m we have thatv ≥ 1 2 (v) + (v) 2 + x 2 x > I v-1 (x) I v (x) > (v -1 2 ) + (v -1 2 ) 2 + x 2 x x (v) + (v) 2 + x 2 < I v (x) I v-1 (x) < x (v -1 2 ) + (v -1 2 ) 2 + x 2λk+1 λk < 1 τ 2 m (k + d 2 ).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 Furthermore, for τ m fixed we have thatλ1 > 1 τ 2 m + 4 1 (( d 2 + 2 τ 2 m ) 1+ 2 τ 2 m )• 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 are out of range (e.g. negative error rates). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
increasing dimension: 
 For the case of increasing dimension, we consider the problem of learning a sequence of distributions D (d) over X × Y = R d × R given by y ∼ f * d (x) + ξ d using a sequence of kernels K (d) . Here, ξ d is independent noise with mean 0 and variance σ 2 > 0. 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 * d onto the eigenfunctions ϕ (d) i | ≤ B, i.e. ∥β∥ ∞ ≤ B, for B that is independent of d.The functions that can be represented in this form depend on the number of nonzero coefficients, S d , and the kernel that we are using. In particular, for dot-product kernels on the sphere it includes all polynomials of degree k ≤ k d where k d is such that the multiplicities of first k d eigenfunctions are at most S d . If S d 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 of 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. Definition 5 (Lower and upper index). Let λk be the k-th non-repeating eigenvalue of a kernel K and let N (k) be its multiplicity. Let N k = N (1) + • • • + N (k). Let m be the sample size. Let k m be defined as the maximal k such that there is less than m eigenvalues with index k, i.e. k m = max{k ∈ N|N (1) + • • • + N (k) < m}. Define the lower index L m and the upper index U m as followsL m = N (1) + • • • + N (k m ) and U m = N (1) + • • • + N (k m + 1). When the dimension changes with sample size, we sometimes denote N (k) by N (d, k).We will first state a generic bound on the test risk for any data distribution, kernel with a bounded sum of eigenvalues, 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=1 N (i) λi ≤ A. For a sequence of kernels K (d) , assume that all such A (d) are bounded by some constant A. 1This is a reasonable assumption for most dot-product kernels, as we show in Appendix C.4. It 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 L m , U m , k m , N (i), N l , and λk as in Definition 5. Consider KRR with a kernel K satisfying Assumption 6 for some A. Assume that for some integer l, the target function f * satisfies Assumption 4 with at most N l nonzero coefficients. Then, the predicted risk of the minimum norm interpolating solution is bounded by the following:EQUATIONEQUATIONAlternatively, we can bound the risk usingl i=1 N (i) 1 λi instead of l i=1 N (i) 1 λ2 i(see Theorem 20 in the appendix).We also establish a generic inconsistency result for any data distribution, kernel with a bounded sum of eigenvalues, sample size, and dimension based on 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 eigenvalues). Assumme that the kernel K has eigenvalues that are not too small, i.e. there is a constant b such that max i≤km1 λi < m-Lm b. For a sequence of kernels K (d) , assume that for the corresponding m = m(d) (since d = d(m), we can also "invert" the dependence) all such b (d) 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 k m and L m be as in Definition 5. Consider learning a target function f * , with some sample size m. Let K be a kernel satisfying Assumption 6 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:R( f0 ) > 1 - b b + 1 2 L m m -1 σ 2 .To apply Theorem 7 for varying dimension d, we would additionally require that A is uniformly bounded for all d and kernel K (d) and also that l = l(d) changes with d such that Assumption 4 holds with S d = N l(d) . For dot-product kernels K (d) on the sphere, if we let K (d) (x, y) = h (d) (∥x -y∥), we will have A = sup d h (d) (0), so if h (d) does not change with d we can take A = h(0) (see Appendix C.4 for more details). Specifically, this holds for the Gaussian kernel on the sphere with A = 1.To apply Theorem 9 to the case of increasing dimension, we would require that the bounds i N (d, i) λi ≤ A and max i≤km 1 λi < m-Lm b hold for all d and kernels K (d) . Usually, the condition max i≤km 1 λi < m-Lm b will be satisfied for b = 1. We will show it for the two cases of sub-polynomially scaling dimensions with a Gaussian kernel. For the polynomial scaling dimension, it is reasonable to assume it for general dot-product kernels, as 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 k m as in Definition 5, we have that there is a constant c such that max i≤km This assumption is stronger than Assumption 8, but as we show in Appendix C.4, it is reasonable for dot-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 a sequence of target functions f * d satisfying Assumption 4 with S d ≤ Θ(d ⌊α⌋ ) with a dot-product kernel K(x, y) = h(∥x -y∥) with h(0) = 1 on the sphere S d-1 (where h does not depend on d, i.e. A = 1 from Assumption 6)) that further satisfies Assumption 10. Let1 λi ≤ cN (k m ).d α m = Θ(1) for α ∈ (0, ∞).Then the overfitting behavior of the minimum norm interpolating solution is benign if α is not an integer and tempered if α is an integer.Additionally, we will show that for d = log m, we cannot get benign overfitting, i.e. consistency with a class of dot-product kernels on 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 K (d) be a sequence of dot-product kernels on S d-1 that satisfy Assumption 8. Let the dimension d grows with sample size as d = log 2 m (i.e. m = 2 d ). Then, the minimum norm interpolant cannot exhibit benign overfitting for any such sequence K (d) , i.e. there exists an absolute constant η > 0 such that for all d, m, R( f0) > (1 + η)σ 2 .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 d = exp( √ log m). Corollary 13 (Benign overfitting with Gaussian kernel and sub-polynomial dimension). Let K be the Gaussian kernel on the sphere S d-1 with a fixed bandwidth, and take a sequence of dimensions d and sample sizes m that scale as d = exp √ log m (in particular, we take l ∈ N such that d = 2 2 l and m = 2 2 2l with l = 1, 2, 3 . . . ). Consider learning a sequence of target functions f * d as in Assumption 4 with S d ≤ m 1 4 . Then, we have that the minimum norm interpolating solution achieves the Bayes error in the limit (m, d) → ∞. In particular, for d ≥ 4 and m ≥ 16 we haveR( f0 ) ≤ 1 - 1 log m -1 1 -exp -0.89 log m -1 σ 2 + 2B 2 1 m .Remark 14 (Allowed target functions). The set of allowed target functions f * d in Corollary 13, i.e. 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 d α m = Θ(1), the result holds only if the target function is a polynomial of degree at most ⌊α⌋. On the other hand, Corollary 13 shows that sub-polynomially scaling dimension allows for the target function to be a polynomial of arbitrary degree, as well as non-polynomial functions. In particular, in dimension d, we can represent polynomials of degree up to Θ(log 2 d). 
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 E 0 , L i,0 behave. In Zhou et al. [66] , the authors show that E 0 is bounded both above and below in terms of the effective rank of the systems of eigenvalue {λ} ∞ i=1 , defined byr k := ∞ i=k+1 λi λ k+1. We will use this, along with directly bounding L i,0 .If K is a dot-product kernel on the sphere (such as the Gaussian kernel), we can take the eigenfunctions ϕ i to be the spherical harmonics Y ks , where k ≥ 0 and s ∈[1, N (d, k)]. Here N (d, k) = (2k+d-2)(k+d-3)! k!(d-2)!is the multiplicity of the k-th spherical harmonic. All Y ks for the same k will have the same eigenvalue, which we will denote λk . In this case, we can write a closed-form expression for the eigenvalues of Gaussian kernel, λk , in terms of the bandwidth τ m and modified Bessel functions of the first kind I v (x) [46] (see Appendix D). Using the closed form of λi and the multiplicities of eigenvalues, we can understand how the test risk of the minimum norm interpolating solution R( f0 ) behaves as m → ∞, which tells us its overfitting behavior.Additionally, E 0 appearing in Equation (2), will be informative. For example, if lim m→∞ E 0 > 1 then the overfitting cannot be benign. The following bound using the effective rank r k holds [66] :EQUATIONFor k ≥ m it holds thatEQUATION)Proof sketch of Theorem 3. We will focus on the lower bounds in this case, as the result is negative. The key elements to understanding the effective rank r k and the test risk Equation ( 2) is to understand how the ratios of eigenvalues λk+1 λk and the multiplicities N (d, k) behave. Using the 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 eigenvaluesEQUATIONFrom these bounds, we can derive tight bounds on λk+j λk for indices k and j using simple but long calculations (see Theorem 28 in the appendix).If k = o 1 τm and j = o 1 τm , then λk+j λk ≈ 1. If k ≤ Θ 1 τm and j = Θ 1 τm , then λk+j λk = Θ(1). If k = ω 1 τm , then λk+j λk = o 1 j n for any integer n ∈ N (i.e. it deceases super-polynomialy). For N (d, l) it holds that N (d, l) = Θ(l d-2 ) and N l := N (d, 1) + • • • + N (d, l) = Θ(l d-1 ). Therefore if l is the index such that λl = λ l , we have that l = Θ(l 1 d-1 ). For τ m ≥ ω(m -1 d-1), we will take l = (1 + 1 √ m )m and show that r l = o(m). Then, the bound in Equation ( 6) will imply thatE 0 ≥ 1 + √ m, so from Equation (2), R( f0 ) > E 0 σ 2 = √ mσ 2 . Note that for l = (1 + 1 √ m )m, we have that l = Θ(m 1 d-1 ) = ω 1 τm .Note that for r l-1 , we have thatr l-1 = ∞ i=0 λ l+i λ l < N (d, l) + ∞ i=1 N (d, l + i) λl +i λl < Θ(m d-2 d-1 ) (1 + Θ(1)) , since N (d, l + i) < N (d, j)i d-2 and λl +i λl < 1 i d . So indeed r l-1 = o(m) which implies r l = o(m). For τ m = o(m -1 d-1 ) and τ m = Θ(m -1 d-1), we will directly analyze Equation (2) . Fork = Θ( 1 τm ), we have that λi λ1 > 1 2 for all i ≤ k. Let L i = λi λi+κ0 . Note that L i > 1 2 L 1 for i ≤ k. Note that m = i N (d, i)L i > 1 2 L 1 (N (d, 1) + • • • + N (d, k)) > Θ 1 τ m d-1 L 1 .So, we have that for all i thatL i < L 1 < m Θ ( 1 τm ) d-1 . From Equation (2), we have that R( f0 ) = E 0 i N (d, i)(1 -L i ) 2 β 2 i + E 0 σ 2 > E 0     1 - m Θ 1 τm d-1     2 ∥f * ∥ 2 + E 0 σ 2 .Forτ m = o(m 1 d-1) this is sufficient. Additionally, by a similar computation as above, in this case, r 1 = ω(m), so E 0 is bounded by Equation (5) . For τ m = Θ(m 1 d-1 ), using Equation ( 5) and Equation ( 6), by showing that for l = Θ(m), r l = Θ(m), we have Θ( 1)> E 0 > 1 + Θ(1). Proof sketch of Theorem 7. Let L i = λi λi+κ0 . Note that (1 -L i ) 2 = κ 2 0 (κ0+ λi) 2 .Then, Equation ( 2) can be rewritten and bounded as (with an abuse of notation for β i )R( f0 ) = E 0 i N (d, i)(1 -L i ) 2 β 2 i + E 0 σ 2 ≤ E 0 B 2 l i=1 N (d, i) κ 2 0 (κ 0 + λi ) 2 + E 0 σ 2 .Note thatκ 2 0 (κ0+ λi) 2 < κ 2 0 λ2 i and also L i ≤ λi κ0 . Therefore, we have that R( f0 ) ≤ E 0 B 2 κ 2 0 l i=1 N (d, i) 1 λ2 i + E 0 σ 2 . Note that m = i N (d, i)L i < i N (d, i) λi κ0 < A κ0 , so κ 0 < A m .Finally, to bound E 0 , note that in Equation ( 5) we can choose k = L m < m, thenr k + k > U m > m, so E 0 ≤ 1 -Lm m -1 1 -m Um -1. Combining these with κ 0 < A m gives the claim of Theorem 7. The proof of the alternative bound is harder and will be delayed to the appendix.Proof sketch of Theorem 9. By Theorem 3 from Zhou et al. [66] , if k is the first k < m such that k + br k ≥ m, then E 0 ≥ 1 -b b+1 2 k m -1 . Since max i≤km 1 λi < m-Lm b , for l < N (d, 1)+• • •+N (d, k m ), we have that br l +l ≤ N (d, 1)+• • •+N (d, k m )-1+b max i≤km 1 λi < L m + m -L m ≤ m, so the first l for which r l + l > m is l = L m = N (d, 1) + • • • + N (d, k m ). Plugging in k = L m we get that E 0 ≥ 1 -b b+1 Lm m -1, so from Equation ( 6), we haveR( f0 ) ≥ 1 -b b+1 2 Lm m -1 σ 2 .Proof sketch of Corollary 11. Note that an analogous proof holds for any d α m → c, for a constant c, but we take equality for simplicity. If k is a constant, i.e. it does not change with the dimension, we have thatN (d, k) = Θ(d k ). Therefore, k m = ⌊α⌋ if α is a non-integer and α -1 if α is an integer. If α is a non-integer, then L m = N (d, k m ) + • • • + N (d, 1) = Θ(d ⌊α⌋ ) and U m = N (d, k m + 1) + • • • + N (d, 1) = Θ(d ⌊α⌋+1 ). So we have that Lm m = d ⌊α⌋-α , m Lm = d α-⌊α⌋-1 , N (d, ⌊α⌋) = d ⌊α⌋ .Note that k m = ⌊α⌋. We have from Assumption 10 that max i≤km1 λi = O(N (d, k m )). Note that Theorem 7 holds with l i=1 N (d, i) 1 λi instead of l i=1 N (d, i) 1 λ2 i . Therefore, we have 1 m 2 max l≤km 1 λi N (d, i) ≤ O(d (2⌊α⌋-2α) ). This gives R( f0 ) ≤ 1 -d ⌊α⌋-α -1 1 -d α-⌊α⌋-1 -1 σ 2 + O B 2 1 -d ⌊α⌋-α -1 1 -d α-⌊α⌋-1 -1 d (2⌊α⌋-2α) .Therefore, lim m→∞ R( f0 ) = σ 2 . So, if α is not an integer, we get benign overfitting. If α is an integer, note that N (d, 1)+ • • • + N (d, α -1) = o (d α ), so k m = α. Then there are c u , c l ∈ (0, 1) such that c l < Lm m ≤ c u < 1. So, Theorem 9 holds for b = 1 2 , so R( f0 ) > 1 1- c 1 9 σ 2 . This shows that lim inf m→∞ R( f0 ) ≥ 1 1- c 1 9σ 2 > σ 2 . The upper bound follows as above. Since we assumed that max i≤km1 λi = O(N (d, k m )), and max i≤km N (d, i) = N (d, k m ) = Θ(d α ), we have that km i=1 N (d, i) 1 λi = Θ(d 2α ), so R( f0 ) ≤ (1 -c l ) -1 1 -d -1 -1 σ 2 + Θ B 2 1 -d -1 -1 .So, we conclude that for integer α we have tempered overfitting and for non-integer α 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 in the appendix (Theorem 21), it is not hard to see that L m ≈ α l m for some constant α l < 1 and L m ≈ α u m for some constant α u > 1. Theorem 9 implies that we cannot get benign overfitting in this case, i.e. for all m, R( f0 )> 1 1-( b b+1 ) 2 α l σ 2 . This shows that lim inf m→∞ R( f0 ) ≥ 1 1-( b b+1 ) 2 α l σ 2 > σ 2 .Proof sketch of Corollary 13. We have that for the Gaussian kernel on the sphere, Theorem 7 holds with A = 1 (see Appendix C.4 for further details). First, we will compute k m and hence L m and U m . After some tedious calculation (Theorem 23 in the appendix), we see that for k ≤ 2 l + l -1 we have N (d, 1)+ • • • + N (d, k) = o(m), but for k = 2 l + l we have N (d, 1) + • • • + N (d, k) > m.This shows that k m = 2 l + l -1 and so again after long calculations L m = Θ( m log m ) and U m > Θ(md 0.89 ). To estimate 7) and an estimate on the size of the first eigenvalue (Corollary 31) λ1 = Θ( 1 d α ), for fixed α > 0, we can estimate the size λk . We have that1 λk < 1 λ1 (τ m ) k d 2 + k + 2 τ 2 m k < d k(1+ε) ,for arbitrarily small ε. For k = 7km 24 , from additional calculation (Theorem 23 in the appendix), we have that m  
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 a 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 as d = exp( √ log m).In Figure 1 , Figure 2 , and Figure 3 we provide empirical justification for the fixed dimension case considered in Theorem 3. The code to reproduce these experiments can be found at https://github.com/marko-medvedev/overfitting-behavior-of-gaussian-kernel-ridgeless-regression.We ran the experiments on one A6000 GPU.(a) τm = o(m -1 d-1) with σ 2 = 1 and d = 6. We see that the test error tends to something that is equal to or larger than the test risk of the null predictor.(b) τm = ω(m -1 d-1) with σ 2 = 10 and d = 4. We see that the test error is increasing with the sample size m, suggesting that the test error diverges to infinity.(c) τm = Θ(m -1 d-1) with σ 2 = 10000 and d = 6. We see that the test error is well above the risk of the null predictor.Figure 1 : Here we plot the test error for 100 different runs of the experiment and their mean test error. We see that the test error concentrates around its mean and that the behavior is as predicted by Theorem 3.Using the setup of Theorem 3 in the paper, we plot the dependence of the test error on the sample size for the Gaussian kernel ridgeless predictor. We consider y = f * (x) + ξ where ξ ∼ N (0, σ 2 ), f * = 10, σ 2 is the noise level, and x ∼ Unif(S d-1 ). We compare the test error with the noise level (the Bayes risk) and the risk of the null predictor. We see that for all three cases, our predictions agree with the experiments. In Figure 2 and Figure 3 , we present evidence for the statistical significance of our experimental results. First, we the mean test loss for a test size of given size, L. We use 50 of the 100 experiments to estimate an interval [L low , L high ] and the other 50 to test whether this interval contains p = 0.8 of the total mass of the distribution of L at α = 0.05 significance level. In Figure 2 , we plot L low and L high . We perform one lower-tailed and one upper-tailed test [17] . The null hypotheses are: 1 -1-p 2 population quantile is no greater than L high and 1-p 2 population quantile is at least as great as L low . In Figure 3 , we report the relevant test statistics, T 1 which is the number of draws of L no greater than L high and T 2 which is the number of draws of L less than L low . We report an aggregated p-value. We accept the null hypothesis in both cases -the test statistics T 1 and T 2 satisfy the required conditions and the p-values are high.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.Definition 15 (Cost of overfitting). Let fδ * be the optimally regularized solution, i.e.* ) = inf δ≥0 R( fδ ).For a distribution D over X × R, we will define the cost of overfitting C(D, m) asC(D, m) = R( f0 ) R( fδ * ) .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 {λ i } ∞ i=1 of a given kernel (coming from Mercer's theorem)r k := ∞ i=k+1 λ i λ k+1 and R k := ∞ i=k+1 λ i 2 ∞ i=k+1 λ 2 i .We will assume additionally that the eigenvalues are nonzero, so r k and R k are well defined on N.Since we chose that the eigenvalues are sorted and since they square summable, we have thatr k ≤ R k ≤ r 2 k .The following two results of [66] summarize how we will use effective ranks to control the cost of overfitting. Proposition 16 gives a necessary and sufficient condition for the overfitting to benign in terms of the cost of overfitting, i.e. that C(D, m) → 1, in terms of effective ranks.Proposition 16 (Necessary and sufficient condition for benign overfitting [66] ). Let k n be the smallest integer k ∈ N ∪ {0} for which n < k + r k . Then E 0 → 1 if and only iflim n→∞ k n n = 0 and lim n→∞ n R kn = 0.Proposition 17 gives a sufficient condition for R( f0 ) → ∞ in terms of effective ranks.Proposition 17 (Sufficient condition for catastrophic overfitting [66] ). Let ε > 0 and let k = (1+ε)m.If lim k→∞ r k k = 0 then E 0 → ∞, i.e. the overfitting is catastrophic.Using sharp bounds on eigenvalues {λ i } ∞ i=1 , 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 {ϕ k } in the Mercer decomposition of the kernel function can be taken to be the spherical harmonics Y ks . 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 τ m and modified Bessel function of the first kind I v (x). 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.The bounds on cost of overfitting will be used to show whether the test risk is bounded above or away from Bayes risk.Lemma 18 (Cost of overfitting for Gaussian KRR). Let X ∼ Unif(S d-1 ). Then the following bounds hold for the minimum norm interpolating solution of KRR and its cost of overfitting C(D, m) and E 0 :1. If τ m ≤ m -1 d-1 t(m), where t(m) → 0 as m → ∞ then there is a constant C I that depends on d and C, such that1 ≤ C(D, m) ≤ E 0 ≤ 1 - 1 m -2 1 -C I t(m) d-1 2 -1 . 2. If τ m ≥ m -1 d-1 t(m), where t(m) → ∞ as m → ∞ then there is a integer m 0 depending on d and t(m) such that for all m ≥ m 0E 0 ≥ √ m. 3. If C 1 m -1 d-1 ≤ τ m ≤ C 2 m -1 d-1then there exist constants C I > 0 and C II depending on C 1 , C 2 and d such thatC(D, m) ≤ E 0 ≤ C I E 0 ≥ 1 + C II .Proof. We will break down the proof into the proof of the three parts.Part 1: We will use Proposition 16 to prove this that E 0 → 1. We can see the upper bound on E 0 from Theorem 2 [66] . We have that for k < mE 0 ≤ 1 - k m -2 1 - m R k -1. Now we will show that for k = 1, we have that k + r k > m and lim m→∞ m R1 = 0. This implies that conditions of Proposition 16 hold so E 0 → 1. We will rewrite r k = i>k λ k λ k+1 using λi . We have thatr 1 = i>1 λ i λ 2 = Ñ (d, 1) + ∞ j=1 N (d, 1 + j) λ1 +j λi1 ,where N (d, 1) = d, so 1 = 1 and Ñ (d, 1) = d -1. Therefore, we have In particular, we have that for m large enough, for all such j it holds that λ1+j λ1 > 1 2 . Going back to r 1 , this means thatr 1 = (d -1) + ∞ j=1 N (d, 1 + j) λ1+j λ1 . Let T = 2 τ 2 m . Taking √ T g(m) 2 ≤ j ≤ √ T g(m), k = 1,r 1 = (d -1) + ∞ j=1 N (d, 1 + j) λ1+j λ1 > √ T g(m) j= 1 2 √ T g(m) N (d, 1 + j) λ1+j λ1 > √ T g(m) j= 1 2 √ T g(m) (1 + j) d-2 1 2 > √ T g(m) j= 1 2 √ T g(m) 1 2 d+1 ( √ T g(m)) d-2 > 1 2 √ T g(m) 1 2 d+1 ( √ T g(m)) d-2 > 1 2 ( √ T g(m)) d-1 . If √ T g(m)is not an integer, we can take its integer part and add a small constant since √ T g(m) will be large. Note that τ m ≤ m -1 d-1 t(m), soT ≥ m 2 d-1 1 t(m) 2 . Therefore r 1 > 1 2 ( √ T g(m)) d-1 > 1 2 m 1 d-1 g(m) t(m) d-1 = m 1 g(m) t(m) d-1, so as long as g(m) t(m) → ∞, r 1 > m for m large enough. We can take g(m) = t(m). Then, in Proposition 16, we can select k m = 1, since 1 + r 1 > m for large enough m. Note also that R 1 ≥ r 1 , so we also have thatR 1 ≥ r 1 > m 1 g(m) t(m) d-1, solim m→∞ 1 m = 0 and lim m→∞ m R 1 = 0.This finishes the proof of the first claim.Part 2: Let τ m ≥ m -1 d-1 t(m), where t(m) → ∞ as m → ∞. We will use Proposition 17 to prove this claim. Using Theorem 5 from [66] we know that for any ε > 0 if r k = o(m) for k = (1 + ε)m then the following bound holdsE 0 ≥ 1 1 -m k k-m k-m+r k > 1 + 1 ε .We will show that there is a constant U > 0 such that for any k ≥ m, we have thatEQUATION.By Theorem 28, we have that for j ≥ √ T g(m) where g(m) → ∞ as m → ∞ thatλk +j k < exp - g(m) 2 4 .Let k = (1 + ε)m. We have thatEQUATION).Therefore, we have thatr k = Ñ (d, k) + ∞ j=1 N (d, k + j) λk +j λk = Ñ (d, k) + j-1 j=1 N (d, k + j) λk +j λk + ∞ j=j N (d, k + j) λk +j λk ≤ n u j d-1 + ∞ j=j N (d, k + j) λk +j λk .Note that by Theorem 28, for j ≥ l √ T g(m) we have that λk +j k < exp -l 2 g(m) 2 4 .Note also that this bounds holds for all l simultaneously. Therefore, we can writer k ≤ n u j d-1 + ∞ j=j N (d, k + j) λk +j λk = n u j d-1 + ∞ l=1 j s=1 N (d, lj + s) λk +lj+s λk ≤ n u j d-1 + ∞ l=1 j s=1 N (d, (l + 1)j) λk +lj λk ≤ n u j d-1 + ∞ l=1 (l + 1) d-1 j d-1 exp(- l 2 g(m) 2 4 ) ≤ m g(m) t(m) d-1 n u + ∞ l=1 (l + 1) d-1 exp(- l 2 4 ) ≤ U m g(m) t(m) d-1 = o(m).Second to last inequality is true because g(m) → ∞ as m → ∞. The last inequality follows from the fact that∞ l=1 (l + 1) d-1 exp(-l 2 4) is bounded by a constant. Note that the bound is independent of k, so we can vary ε with m as well. If we choose ε = 1 √ m , the desired result follows.Part 3: Let C 1 m -1 d-1 ≤ τ m ≤ C 2 m -1 d-1. Note that the following two bounds hold for E 0 [66] :1. For k < m such that r k + k > m E 0 ≤ 1 - k m -1 1 - m k + r k -1 . 2. For k ≥ m it holds that 1 m i L i,δ ≥ m k k -m k -m + r k . Note that in this case c ′ 1 m 1 d-1 ≤ √ T = 2 τ 2 m ≤ c ′ 2 m 1 d-1 , where c ′ 2 = 2 C 2 1(and similarly for indices 1 and 2 swapped with inequalities reversed). Theorem 28 shows that for i is such that i ≤ (k √ T ), we have that for λi it holds thatλi λ1 ≥ 1 1 + k √ T k √ T ≥ exp(-k 2 ).Take k = (1 + ε)m. We want to show that there is a constant B > 0 that depends on the dimension d and the constant C such thatr k ≤ Bm. Let k = ((1 + ε)m) 1 d-1. Note that by an analogous proof to Theorem 28, we have that for the size of eigenvalues it holdsEQUATION.For l k ≤ j ≤ (l + 1) k, we have thatλk +j λk ≤ T T + ( k + j -1 + d 2 -1 2 ) j-1 2 < T T + ((l + 1) k) l k-1 2 < T T + ((l + 1) k) (l+1) k 4.We have that k = 1 c ′ (1+ε)1 d-1 c ′ m 1 d-1 = 1 c ′ (1+ε) 1 d-1 √ T = α √ T for α = 1 c ′ (1+ε) 1 d-1. Therefore, we have thatλk +j λk < T T + ((l + 1) k) (l+1) k 4 = T T + ((l + 1)α √ T ) (l+1)α √ T 4 → exp - (l + 1) 2 α 2 4 , as m → ∞ i.e.√ T → ∞. Therefore, for m large enough, for all l we have that ifl k ≤ j ≤ (l + 1) k then λk +j λk ≤ 1 (l + 1) d+2 .The last inequality is true because we can take m large enough so that αT and √ T α are both greater than 400d. Then we have that for all l λk +jλk < T T + ((l + 1)α √ T ) (l+1)α √ T 4 < 1 1 + l+1 100d (l+1)100d < 1 (l + 1) d+2 .The last inequality holds because of the following1 + l + 1 100d (l+1)100d > l + 1 100d d+2 (l + 1)100d d + 2 > (l + 1) d+2 1 (100d) d+2 (100d) d+2 > (l + 1) d+2 .Therefore, we can bound r k as followsr k = i>k λ k λ k = Ñ (d, k) + ∞ j=1 N (d, k + j) λk +j λk < N (d, k) + ∞ j=1 N (d, k + j) λk +j λk < ( k) d-2 + ∞ l=1 ((l + 1) k) d-2 ( k) 1 (l + 1) d+2 < kd-1 ∞ l=1 1 (l + 1) 4 < kd-1 C = C(1 + ε)m. Therefore, applying claim 1, we have that k -m + r k < (C(1 + ε) + ε)m, so we have that k-m k-m+r k > ε (C(1+ε)+ε) , so it follows that E 0 > (1 -(1+ε)ε (C(1+ε)+ε) ) -1 > 1.Note that the above proof actually shows that for any k 1 ≤ k, we have that r k1 ≤ Cm. Now we want to show that r k is lower bounded and that we can take k < m such that k + r k > m. Again apply Theorem 28, we can generalizeλi λ1 ≥ 1 1 + k √ T k √ T ≥ exp(-k 2 ).to other ratios as well. Let j ≤ k√ T and let k √ T ≤ i ≤ (k + 1) √ T . Then we have that λi λj ≥ 1 1 + 2k √ T (k+1) √ T ≥ exp(-2k(k + 1)). Note that c ′ 1 m 1 d-1 ≤ √ T = 2 τ 2 m ≤ c ′ 2 m 1 d-1 , where c ′ 2 = 2 C 2 1(and similarly for indices 1 and 2 swapped with inequalities reversed). Therefore, we have that the following bound holds on r k for any k < m:r k = i>k λ i λ k+1 = Ñ (d, (k + 1)) + ∞ j=1 N (d, (k + 1) + j) λ (k+1)+j λ (k+1) .Note that since√ T ≥ c ′ 1 m 1 d-1 then N √ T ≥ n l (c ′ 1 ) d-1 m, so m ≤ 1 c ′ 1 1 n 1 d-1 l. Therefore, if we takej = k, l = 1 c ′ 1 1 n 1 d-1 l, and any l √ T ≤ i ≤ (l + 1) √ T , we have that (since exp(-2l(l + 1)) < exp(-l 2 )) λi λj ≥ exp(-2l(l + 1)).Note that there is at leastN (l+1) √ T -N l √ T ≥ n l (l + 1) d-1 -l d-1 m such indices i, we have that r k = i>k λ i λ k+1 = Ñ (d, (k + 1)) + ∞ j=1 N (d, (k + 1) + j) λ (k+1)+j λ (k+1) . > l √ T ≤i≤(l+1) √ T N (d, i) λi λk > n l (l + 1) d-1 -l d-1 m exp(-2l(l + 1)) > βm,where β = n l (l + 1) d-1 -l d-1 exp(-2l(l + 1)). Note that β is independent of k, so in particular for k = (1 -β/2)m, we will have r k + k > m. Therefore we can use the upper bound on E 0 to see thatE 0 ≤ 2 2 β 2 (1 + β/2).Since β only depends on d and C 1 and C 2 , this finishes the proof.In particular, Lemma 18 shows that whenτ m = o(m -1 d-1 ) or τ m = ω(m -1 d-1 ), then lim sup R( f0 ) ≤ ∞.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 2, the following bounds hold for the risk R( f0 ) of the minimum norm interpolating solution of Gaussian KRR:1. If τ m = o(m -1 d-1 ), then R(0) ≤ lim inf R( f0 ) ≤ lim sup m→∞ R( f0 ) < ∞. More precisely, if τ m ≤ m -1 d-1 t(m), where t(m) → 0 as m → ∞, then there is a scalar c d that depends only on the dimension so that for all such t(m) there is m 0 that depends on t(m) such that for all m > m 0 we have R( f0) > σ 2 + (1 -c d t(m) d-1 2 )∥f * ∥ 2 . 2. If τ m = ω(m -1 d-1 ), then lim m→∞ R( f0 ) = ∞. More precisely, if τ m ≥ m -1 d-1 t(m), where t(m) → ∞ as m → ∞ then there is an integer m 0 that depends on the dimension and t(m) such that for m > m 0 , we have that tR( f0 ) → √ m(σ 2 ) (note that R(0) is bounded). Hence, for large enough m we have R( f0 ) > R(0). 
safeguards: 
 Question: Does the paper describe 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 a 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 a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.Note that this assumption implicitly sets the scale of the kernel.Note that this assumption implicitly sets the scale of the kernel. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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
on 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

- 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)
- for a fixed bandwidth, but varying dimensionthey derivelower and upper bound on the population risk. This allows them to
	- recover known results stating that when the dimension size increases polynomially with sample size, overfitting is benign or tempered
	- show that when the dependency is logarithmic, overfitting is not benign (under additional assumptions verified for the gaussian kernel)
	- show that when the dependency is subpolynomial $\exp(\sqrt{m)$ scaling, overfitting can be benign
strength_weakness: strength_weakness: - 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.
- The eigenframework which they use rely on a number of assumptions to be valid.
questions: 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
  distributed on the whole of $\mathbb  R^d$?


Typos:

l 294
l 298
limitations: limitations: Mentioned in weaknesses.
paper_summary: paper_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.

They 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.
strength_weakness: strength_weakness: 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. 

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

Different 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.
questions: questions: Can you explain the theoretical basis for the catastrophic overfitting observed with certain bandwidth scalings and the choice of kernels intuitively?

What are the practical guidelines for choosing the bandwidth parameter in real-world applications since there is no experiment?

How does the proposed method perform across different types of data distributions besides Assumption 2?
limitations: limitations: Yes
paper_summary: paper_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).*

In 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.
strength_weakness: strength_weakness: There are a few weaknesses. The current reject score is due to my concerns with the proofs. 

1) **Theorem 1**

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

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

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

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

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

2) Eigenlearding Framework and Predicted Risk

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

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


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

[B] Kausik, C., Srivastava, K., & Sonthalia, R. (2023). Double Descent and Overfitting under Noisy Inputs and Distribution Shift for Linear Denoisers.TMLR 2024

3) References 

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

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

[D] Hu, H., Lu, Y.M., & Misiakiewicz, T. (2024). Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime. ArXiv, abs/2403.08160.
questions: questions: Please see weaknesses
limitations: limitations: The limitations are well discussed.
paper_summary: paper_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."
strength_weakness: strength_weakness: 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.
questions: 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: limitations: None.
paper_summary: paper_summary: This paper concerns the overfitting behaviour of Gaussian kernel ridge regression (KRR) with varying bandwidth or dimensionality. The contribution is two-fold: 

1. In fixed-dimension, the ridgeless solution of Gaussian KRR is not consistent with any varying or tuned bandwidth. 

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

All the results are under the Gaussian universality Ansatz and the (non-rigorous) risk predictions in terms of the kernel eigenstructure introduced in [Simon2023]. 

Reference:

- 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.
strength_weakness: strength_weakness: 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).

Secondly, 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.

Reference:
- Barzilai, Daniel, and Ohad Shamir. "Generalization in kernel regression under realistic assumptions." arXiv preprint arXiv:2312.15995 (2023).
- Cheng, Tin Sum, et al. "Characterizing overfitting in kernel ridgeless regression through the eigenspectrum." arXiv preprint arXiv:2402.01297 (2024).
questions: questions: The most important question would be if the authors could provide some experimental validations on these two claims.
limitations: limitations: All assumptions are stated in the claims. However, as mentioned before, GUA and Eigenframework assumptions are too unrealistic and might provide wrong results.

Comments: title: Regarding the contribution of the paper
Thank you for your response
Please read rebuttal and comment
Reply
comment: Thanks for the clarification and the attached PDF. I have increased my scores.
Thanks for your clarification. I have increased the score.
We thank the reviewer for additional comments. Indeed, for the interpolating solution of the Gaussian KRR, there is one parameter that can be varied, the bandwidth $\tau_m$. Note that the bandwidth can (and in practice often does) depend on sample size $m$. Our first technical contribution, which is understanding how the eigenvalues of the Gaussian kernel for the sphere depend on the bandwidth $\tau _ m$, holds without the Gaussian design ansatz assumption. The second technical contribution is understanding how the test risk of the interpolating solution of Gaussian KRR depends on the bandwidth and thus characterizing its overfitting behavior, under the Gaussian design ansatz. Note that both of these are highly nontrivial technical contributions. Our third technical contribution is for the case of increasing dimension, understanding how the test risk behaves for any scaling of the dimension and sample size. We achieve this by showing upper and lower bounds on the test risk of the interpolating solution of KRR. Our fourth technical contribution is using these bounds for increasing dimension to demonstrate that we can achieve benign overfitting even with sub-polynomially increasing dimension and Gaussian KRR, improving the currently known result for polynomially increasing dimension. This is also a nontrivial technical contribution.
We thank the reviewer for additional comments. We will update the update the paper to include this explanation.
We thank the reviewer for a productive discussion and for increasing our score.
We thank the reviewer for their further feedback. We believe that the discussion about the significance of the theoretical results is important for all the reviewers to see, so we are providing a global reply to this discussion.
We thank the reviewers for their continued feedback.
We feel some reviewers are dismissive of the contribution of analyzing the Gaussian kernel under the eigenframework. Indeed, we are relying on the eigenframework predictions, which are a powerful (but non-rigorous) tool, and proving the eigenframework predictions for the Gaussian kernel would be very important (and difficult) contribution. We acknowledge that understanding the limitations of eigenframework is an important research direction, but we point to both empirical [7,38] and theoretical evidence [38] that the eigenframework holds well for the Gaussian kernel.


Taking an extreme analogy, we feel that dismissing work because it relies on the eigenframework is analogous to dismissing hardness results relying on NP!=P because "the hard part was done by Cook, Lewin and Karp” or “more interesting is to prove NP!=P", or asking if the hardness result can be relaxed to "avoid this assumption". This analogy is extreme and we are not saying the eigenframework is at the same status as NP!=P, but more direct analogies are other papers relying on the eigenframework (e.g. [1, 7, 12, 25, 47, 54, 63]), or with a more historical perspective, the entire body of work relying on the Parisi predictions for the Sherrington-Kirkpatrik Ising Model, a spin glass model (e.g. by Mazard, Parisi, Virasoro and many others), which was only much later proven rigorously by Talagrand.


Yes, we are using a tool (the eigenframework predictions) that involved some heavy lifting, but that is the point of a tool - to allow for simplified further analysis.  The analysis we do using this tool is highly non-trivial at the technical level and is not just a simple application of Zhou et al 2023 [63]. First, for fixed dimension, our technical contribution is deriving the dependence of the eigenvalues of the Gaussian kernel on the bandwidth (Theorem 8) and hence understanding how the test risk depends on the bandwidth (Theorem 1). 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), by introducing the “upper and lower index” (Definition 1).


We agree that proving the eigenframework predictions rigorously for a Gaussian kernel (i.e. lifting the GUA assumptions) would indeed be a strong contribution, but we are very explicit on exactly what we rely on, what is new, what is rigorous, and what is an assumption. We do not think the fact that we do not prove all of this in a single paper should diminish the contribution of what we actually do.
Thank you for the clarification. I have increased my score
In kernel regression, there are two quantities that characterize the generalization ability of the kernel estimator (and for interpolation, there might be only one such quantity). These quantities are in turn determined by the eigenvalues of the kernel.

When considering the Gaussian kernel, there is an explicit formula for the eigenvalues in terms of the bandwidth h. Thus, if 
h varies, the two quantities will vary as well. Since the author has further adopted the Gaussian ansatz, I assume the major contribution is characterizing how the eigenvalues and these two quantities vary with changes in 
h. Could you please correct me if I have overlooked any other key contributions?
Thank you for your prompt response and the experimental results. We can now be confident that the Gaussian kernels behave as predicted by the theory. However, for a theoretical result, I would expect a more realistic assumption to explain the Gaussian kernel interpolation. As mentioned by other reviewers, the major technique was developed in earlier works, and the results presented in this paper alone do not justify acceptance. I believe one possible direction could be to drop the GUA assumption in your analysis.
Thank you to the authors for their response.

Regarding 2 - reading again that section of the paper, it think it would help guide the reader unfamiliar with this literature if the authors explained how the predicted risk expression is obtained. For instance, quoting [38], "[BCP20] presents two different approaches to obtain this analytical expression: a continuous approximation to the learning curves inspired by the Gaussian process literature [Sol01], and replica method with a saddle-point approximation". A sentence along these lines could be helpful to make this formula less "magic".
Dear reviewers, 

could you have a look at the authors response and 
comment on them if you have done so, yet. So far,
we have quite a bit of a spread in the opinions, so
we need a discussion to converge.

thanks in advance
your area chair
Yes, we can provide references and explain further. In [43], in section 2 and Theorem 2, it is explained that when we are on $S^{d-1}$, the eigenfunctions of the Gaussian kernel are spherical harmonics. This is shown in their proof of Theorem 2 in equation (24). Namely, using the Funk-Hecke formula (see page 30 of the reference below), one can show that for any inner product kernel on the sphere, the spherical harmonics are the eigenfunctions. The Funk-Hecke formula states that for any spherical harmonic of order $k$, $Y_k$, and any $x\in S^{d-1}$ the following equation holds $\int_{S^{d-1}} f(\langle x,t \rangle) Y_k(t) dS^{d-1}(t) = \lambda_k Y _ k(x)$, where $\lambda_k$ is a real number given by an integral that depends on $f$ (see [43] for the formula). Then, if our kernel $K: X\times X\to \mathbb R$ is an inner product kernel, there is a function $k: \mathbb R\to \mathbb R$ such that $K(x,t) = k(\langle x,t\rangle)$. Then applying the Funk-Hecke formula for $f=k$ would give the desired result. Note that on $S^{d-1}$, we have that $\exp\left(-\frac{\| x-t \|^2}{\sigma^2} \right) = \exp \left( -\frac{2}{\sigma^2}\right) \exp \left( \frac{2 \langle x,t \rangle }{\sigma^2} \right)$, which shows that the Gaussian kernel is an inner product kernel. For the proof of the Funk-Hecke formula, the reviewer can look at the reference given below. The fact that eigenfunctions of inner product kernels are spherical harmonics is frequently used in papers that discuss inner product kernels, such as [4] (Section G).

Funk-Hecke formula reference: C. Muller. Analysis of Spherical Symmetries in Euclidean Spaces. Applied Mathematical Sciences 129, Springer, New York, 1997.


[43] Minh Ha Quang and Yuan Yao. Mercer’s theorem, feature maps, and smoothing. Conference: Learning Theory, 19th Annual Conference on Learning Theory, COLT, 2006.


[4] Daniel Barzilai and Ohad Shamir. Generalization in kernel regression under realistic assumptions. arXiv preprint arXiv:2312.15995v2, 2024.
Could the authors expand on how we know the eigenfunctions are spherical harmonics? Even a reference to another work would be appreciated.  

Line 100 seems to cite Mercer's Theorem. These notes (https://www.stat.berkeley.edu/~bartlett/courses/2014spring-cs281bstat241b/lectures/20-notes.pdf) by Peter Bartlett seem like a reasonable reference to me. Here the order of implications is for a given kernel there exist eigenfunctions such that...  so it looks like the eigenfunctions are dependent on the kernel.