Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension
Authors: Moritz Haas
David Holzmüller
Ulrike von Luxburg
Ingo Steinwart
Venue: NeurIPS 2023 poster (2023)
Keywords: benign overfitting
kernels
neural tangent kernel
consistency
learning theory

Abstract: The success of over-parameterized neural networks trained to near-zero training error has caused great interest in the phenomenon of benign overfitting, where estimators are statistically consistent even though they interpolate noisy training data. While benign overfitting in fixed dimension has been established for some learning methods, current literature suggests that for regression with typical kernel methods and wide neural networks, benign overfitting requires a high-dimensional setting, where the dimension grows with the sample size. In this paper, we show that the smoothness of the estimators, and not the dimension, is the key: benign overfitting is possible if and only if the estimator's derivatives are large enough. We generalize existing inconsistency results to non-interpolating models and more kernels to show that benign overfitting with moderate derivatives is impossible in fixed dimension. Conversely, we show that benign overfitting is possible for regression with a sequence of spiky-smooth kernels with large derivatives. Using neural tangent kernels, we translate our results to wide neural networks. We prove that while infinite-width networks do not overfit benignly with the ReLU activation, this can be fixed by adding small high-frequency fluctuations to the activation function. Our experiments verify that such neural networks, while overfitting, can indeed generalize well even on low-dimensional data sets.

Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension
Moritz Haas David Holzmüller** Urrike von Luxburg' Ingo Steinwart?
University of Tübingen and Tübingen Al Center, Germany
Institute for Stochastics and Applications, University of Stuttgart, Germany
{mo haas, ulrike. (areourrrnunnntuuuuuteee (david. holzmueller, ingo. steinwart)
wtw.:/irrrrnnsssttiiieaaa... weeinwart)mmthhmmtiik Smathematik uni-stuttgart.de
Abstract
The success of over-parameterized neural networks trained to near-zero training егror has caused great interest in the phenomenon of benign overfitting, where estimators are statistically consistent even though they interpolate noisy training data. While benign overfitting in fixed dimension has been established for some learning methods, current literature suggests that for regression with typical kernel methods and wide neural networks, benign overfitting requires high-dimensional setting where the dimension grows with the sample size. In this paper, we show that the smoothness of the estimators, and not the dimension, is the key: benign overfitting is possible if and only the estimator's derivatives are large enough. We generalize existing inconsistency results to non-interpolating models and kernels to show that benign overfitting with moderate derivatives impossible show that rate-optimal benign overfitting
in fixed dimension. Conversely, is possible for regression with a sequence of spiky-smooth kernels with large derivatives. Using neural tangent kernels, we translate our results wide neural networks. We prove that while infinite-width networks do not overfit benignly with the ReLU activation, this can be fixed by adding small nigh-freqeeccy fluctuations to the activation function. Our experiments verify that such neural networks, while overfitting, can indeed generalize well even on diw-emnnsiionl data sets.
1 Introduction
While neural networks have shown great practical success, our theoretical understanding of their generalization properties is still limited. A promising line of work considers the phenomenon of benign overfitting, where researchers try understand when and how models that interpolate noisy training data can generalize (Zhang et al., 2021, Belkin et al., 2018, 2019). In the high- high-dimensional regime, where the dimension grows with the number of sample points, consistency of minimum-norm interpolants has been established for linear models and kernel regression (Hastie et al., 2022, Bartlett al., 2020, Liang and Rakhlin, 2020, Bartlett et al., 2021). In fixed dimension, minimum-noo interpolation with standard kernels is inconsistent (Rakhlin and Zhai, 2019, Buchholz, 2022).
In this paper, shed differentiated light benign overfitting with kernels and neural networks. We argue that the ceamension-dependeen perspective does not capture the full picture of benign overfitting. In particular, we show that harmless interpolation with kernel methods and neural networks is possible, even in small fixed dimension, with adequately designed kernels and activation functions. The key to properly design estimators of the form "signal+spikk'.. While minimum-norm criteria have widely been considered a useful inductive bias, we demonstrate that designing unusual norms can resolve the shortcomings of standard norms. For wide neural networks, harmless interpolation can be
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

realized by adding tiny fluctuations to the activation function. Such networks do not require explicit regularization and can simply be trained to overfit (Figure 1).
ReLU
Prodiction
Prediction
RMSE
0.5
Spicy smooth
0.6
ReLUi Spuky-smooth smooth
Laplace Spiky-smooth
Signal nerwork
0.0
10P
10'
102
10
Angle (radians)
Angle (rudians)
Epochs
Figure 1: Spiky-smooth overfitting dimensions. a. We plot the predicted function for ridgeless kernel regression with the Laplace kernel (blue) versus our spiky-smooth kernel (4) with Laplace components (orange) on S'. The dashed black line shows the true regression function, black "x' denote noisy training points. Further details can be found in Section 6.2. b. The predicted function of a trained 2-layer neural network with ReLU activation (blue) versus ReLU plus shifted sin-function (8) (orange). Using the weights learned with the smiky-smooth activation function in ReLU network (green) disentangles the spike component from the signal component. c. Training error (solid lines) and test error (dashed lines) over the course of training for b. evaluated on 10* test points. The dotted black line shows the optimal test error. The spiky-smooth activation function does not require regularization and simply be trained to overfit.
On technical level, we additionally prove that overfitting in kernel regression can only be consistent the estimators have large derivatives. Using neural tangent kernels or neural network Gaussian process kernels, we can translate our results from kernel regression to the world of neural networks (Neal, 1996, Jacot et al., 2018). In particular, our results enable the design of activation functions that induce benign overfitting in fixed dimension: the spikes in kernels can be translated into infinitesimal fluctuations that can be added to an activation function to achieve harmless interpolation with neural networks. Such small high frequency oscillations fit noisy observations without affecting the smooth component too much. Training finite neural networks with gradient descent shows that spiky-smooth activation functions indeed achieve good generalization even when interpolating small, low-dimensional data sets (Figure b,c).
Thanks to new technical contributions, our inconsistency results significantly extend existing ones. We use a novel noise concentration argument (Lemma D.6) to generalize existing inconsistency results on minimum-noo norm interpolants to the much more realistic regime of overfitting estimators with comparable Sobolev norm scaling, which includes training via gradient flow and gradient descent with "late stopping" as well as low levels of ridge regularization. Moreover, a novel connection to eigenvalue concentration results for kernel matrices (Proposition 5) allows us to relax the smoothness assumption and to treat heteroscedastic noise in Theorem 6. Lastly, our Lemma E. translates inconsistency results from bounded open subsets of IR to the sphere Sd, which leads to results for the neural tangent kernel and neural network Gaussian processes.
2 Setup and prerequisites
General approach. We consider general regression problem on Rd with an arbitrary, fixed dimen- sion d and analyze sernel-based approaches to solve this problem: kernel ridge regression, kernel gradient flow and gradient descent, minimum-nore norm interpolation, and more generally, overfitting norm-bounded estimators. We then translate our results to neural networks via the neural network Gaussian process and the neural tangent kernel. Let us now introduce the formal framework.
Notation. We denote scalars by lowercase letters x, vectors by bold lowercase letters æ and matrices by bold uppercase letters X. We denote the eigenvalues of A (A) 2 ... X, (A) and the Penroee pseudo-inverse by A+. We say that probability distribution P has lower and upper bounded density if its density p satisfies < c < p(x) < C for suitable constants c, C' and all x on given domain.
Regression setup. We consider data D ((x), yI), ..... (I., Mn)) (Rd x Ry" with i.i.d. samples (x,, y:) ~ P. written D P where P is probability distribution on Rd R. We define X = (X), (I1,..., xx) and y = (V1...., ,y)..".)"""""" TT) e R². Random variables (x, y) P denote

---

test points independent of D, and Px denotes the probability distribution of æ. The (least squares) empirical risk RD and population risk Rp of function f I2d + R are defined as
1 w s(x:))² Rr(J)= = Eu [(x)))²]
RD(J)=
We assume Var(yla:) < 00 for all æ. Then, Ry is minimized by the target function fp(2)) = -E(ylaz) and the excess risk of function is given by
Rr(s) Rp(sp) = E. (Sp(()) f(x)))
We call data-dependent estimator fo consistent for P its excess risk converges to in probability, that is, for all E > O, lim p" (D E (R x R)" Rr(fD) - Rf(fp) 2 E) = O. We call fo consistent in expectation for P if mi EnRp(/D) RF( = 0. We call fn universally consistent if is it consistent for all Borel probability measures P on R x R.
Solutions by kernel regression. Recall that kernel k induces a reproducing kernel Hilbert space Hy. abbreviated RKHS (more details in Appendix B). For f E Hy. we consider the objective
1 n Σ ( f(xx)) + +
= (f)
with regularization parameter p 2 O. Denote by St.p the solution this problem that is obtained by optimizing on Cp in Hr with gradient flow until time t E [0, oo), using fixed a regularization constant p 0, and initializing at f = He. We show in Appendix C.1 that it is given as
(2))()) = k(x x) I - 2XXK( x (&(X, X) + pnl y
(1)
where ((x, X) denotes the row vector (k(x, æz)) ke( and k(X, X) (k(2;;, Ji))),ee(ii the kernel matrix. ft.p elegantly subsumes several popular kernel regression estimators as special cases: (i) classical kernel ridge regression for t + co, (ii) gradient flow on the unregularized objective for
y 0, and (iii) kernel "ridgeless" regression f=c.0 (ar) = k(x, X)k(X, x) y in the joint limit of + 0 and + xo. If k(X, X) is invertible, Soo.0 is the interpolating function f E Hr with the smallest H4-norm.
From kernels to neural networks: the neural tangent kernel (NTK) and the neural network Gaussian process (NNGP) Denote the output of NN with parameters @ input æ by fo()). is known that for suitable random initializations 0g in the infinite-widit limit the random initial function fe, converges in distribution to Gaussian Process with the so-called Neural Network Gaussian Process (NNGP) kernel (Neal, 1996, Lee et al., 2018, Matthews et al., 2018). In Bayesian inference, the posterior mean function is then of the form foe.p- With minor modifications (Arora et al., 2019, Zhang et al., 2020), training infinitely wide NNs with gradient flow corresponds to learning the function fr, with the neural tangent kernel (NTK) (Jacot al., 2018. Lee et al.. 2019). If only the last layer is trained, the NNGP kernel should be used instead (Danicly et al., 2016). For ReLU activation functions. the RKHS of the wnidt NNGP and NTK on the sphere Sa is typically a Sobolev space (Bietti and Bach, 2021, Chen and Xu, 2021), see Appendix B.4. Using other parametrizations induces feature learning infinite-widh limits for neural networks (Yang and Hu, 2021); an analysis of such neural network algorithms is left for future work.
3 Related work
We here provide short summary of related work. A more detailed account is provided in Appendix A.
Kernel regression. With appropriate regularization, kernel ridge regularization with typical universal kernels like the Gauss, Matérn, and Laplace kernels is universally consistent (Steinwart and Christ- mann, 2008, Chapter 9). Optimal rates Sobolev RKHS can also be achieved using validation of the regularization (Steinwart et al., 2009) or early stopping rules (Yao et al., 2007. Raskutti et al., 2014, Wei al., 2017). The above kernels as well as NTKs and NNGPs of standard fully-connected neural networks are rotationally invariant, In the high-dimensional regime, the class of functions that learnable with -nnaaian-nnvariant kernels quite limited (Donhauser et al., 2021, Ghorbani et al., 2021, Liang et al., 2020).
3

---

Inconsistency results. Besides Rakhlin and Zhai (2019) and Buchholz (2022), Beaglehole et al. (2023) derive inconsistency results for ridgeless kernel regression given assumptions on the spectral tail in the Fourier basis, and contemporaneously propose special case of our spiky-smooth kernel sequence to mimic kernel ridge regression without providing any quantitative statements. Li et al. (2023) show that polynomial convergence is impossible for common kernels including ReLU NTKs. Mallinar et al. (2022) conjecture inconsistency for interpolation with ReLU NTKs based on their semi- rigorous result, which essentially assumes that the eigenfunctions can be replaced by structureless Gaussian random variables. Lai et al. (2023) show an inconsistency-type result for overfitting two- layer ReLU NNs with d 1, but for fixed inputs X. They also note that an earlier inconsistency result by Hu et al. (2021) relies on an unproven result. Mücke and Steinwart (2019) show that global minima of NNs can overfit both benignly and harmfully, but their result does not apply to gradient descent training. Overfitting with typical linear models around the interpolation peak is inconsistent (Ghosh and Belkin, 2022, Holzmüller, 2021).
Classification. For binary classification, benign overfitting is more generic phenomenon than for regression (Muthukumar et al., 2021, Shamir, 2022), and consistency has been shown under linear separability assumptions (Montanari al., 2019, Chatterji and Long, 2021, Frei et al., 2022), through complexity bounds for reference classes (Cao and Gu, 2019, Chen et al.. 2021) or as long as the total variation distance of the class conditionals is sufficiently large and f (x) = Efy a=] lies in the RKHS with bounded norm (Liang and Recht, 2023). Chapter 8 of Steinwart and Christmann (2008) discusses how the overlap of the two classes may influence learning rates under positive regularization.
4 Inconsistency of overfitting with common kernel estimators
We consider a regression problem on Rd in arbitrary, fixed dimension that is solved by kernel regression. In this section, we derive several new results, stating that overfitting estimators with moderate Sobolev norm are inconsistent, in a variety of settings. In the next section, we establish the other direction: overfitting estimators can be consistent when we adapt the norm that is minimized.
4.1 Beyond minimum-norm interpolants: general overfitting estimators with bounded norm
Existing generalization bounds often consider the perfect minimum norm interpolant. This is rather theoretical construction; estimators obtained by training with gradient descent algorithms merely overfit and, in the best case, approximate interpolants with small norm. In this section, we extend existing bounds to arbitrary overfitting estimators whose norm does not grow faster than the minimum norm that would be required to interpolate the training data. Before we can state the theorem, need to establish some technical assumptions.
Assumptions on the data generating process. The following assumptions (as in Buchholz (2022)) allow for quite general domains and distributions. They are standard in nonparametric statisties.
(D1) Let Px be a distribution on bounded open Lipschitz domain Ω S Rd with lower and upper bounded Lebesgue density. Consider data sets D = {(x), V1),.... (I,, b.)}. where
z Px i.i.d. and yi = (ax &4, where & is i.i.d. Gaussian noise with positive variance d² > 0 and f E C (S)) denotes a smooth function with compact support.
Assumptions on the kernel. Our assumption on the kernel is that its RKHS is equivalent to a Sobolev space. For integers
N, the norm of a Sobolev space H H*2) can be defined as
1 = Σ | 112
05ial5
where D denotes partial derivatives in multi-indes notation for It measures the magnitude of derivatives up to some order s. For general s > 0, H (equivalent to) an RKHS if and only if s > /.2 For example. Laplace and Matérn kernels (Kanagawa et al., 2018, Example 2.6) have Sobolev RKHSs. The RKHS of the Gaussian kernel HGaus is contained in every Sobolev space, Hauss Ç Ha for all & 2 0 (Steinwart and Christmann, 2008, Corollary 4.36). Due to its smoothness, the Gaussian kernel potentially even more prone to harmful overfitting than Soboley kernels (Mallinar et al., 2022). We make the following assumption the kernel:

---

(K) Let k be positive definite kernel function whose RKHS H₁ is equivalent to the Sobolev
3d space Ha for some 8 E 2 4
Now we are ready to state the main result of this section:
Theorem 1 (Overfitting estimators with small norms are inconsistent). Let assumptions (D1) and (K) hold. Let Cftt E (0, 1] and Cnorm > 0. Then, there exist c > O and ne E N such that the following holds for all n 2. no with probabiliiyy 1 - O(1/n) over the draw of the data set D with samples: Every function f E Hy that satisfies the follwing two conditions
(0) (f - y²)² < (1 -1-60 CCt) o² (training error of f is below Bayes risk) (N) If S norm foc. (norm comparable to minimum-non interpolant (1)), has an excess risk that satisfies
- Re(f)-R((f7) 2 co22 00
(2)
In words: In fixed dimension d, every diffcrentiable function ff that overfits the training data and is not much "spikier" than the minimum RKHS-norm interpolant is inconsistent!
Proof idea. Our proof follows similar approach Rakhlin and Zhai (2019), Buchholz (2022), and
also holds for kernels with adaptive bandwidths. For small bandwidths, fo ( < | (Px))
because foo.0 decays to 0 between the training points, which shows that purely 'spiky' estimators inconsistent. In this case, the lower bound is independent of o². For all other bandwidths, interpolating (n)) many noisy labels y, incurs (1) error in an area of volume (((/n)) around ((n) data points with high probability, which accumulates to total error (2(1). Our observation is that the same logic holds when overfitting by a constant fraction. Formally, we show that f and f must then be separated by a constant on constant fraction of training points, with high probability, by using the fact that a constant fraction of the total noise cannot concentrate on less than ((1) noise variables, with high probability (Lemma D.6). The full proof can be found in Appendix D.
Assumption (O) necessary in Theorem 1, because optimally regularized kernel ridge regression fulfills all other assumptions of Theorem 1 while achieving consistency with minimax optimal convergence rates (see Section 3). The necessity of Assumption (N) is demonstrated by Section
The following proposition establishes that Theorem I covers the entire overfitting regime of the popular (regularized) gradient flow estimators ft,p for all times t E [0, oo] and any regularization p 22 O. The proof in Appendix C.2 also covers gradient descent.
Proposition (Popular estimators fulfill the norm bound (N)). For arbitrary t E [0, oo] and P E [0, o0). ft.p as defined in (1) fulfills Assumption (N) with Cnarm 1.
Remark 3 (Dimension dependency). Some works argue that for specific sequences of kernels (Ka)aEN, the constant e Theorem 1 decreases with increasing dimension d (Liang et al., 2020, Liang and Rakhlin, 2020, Mallinar al., 2022). In Theorem if the equivalence constants in Assumption (K) are uniformly bounded in d, the behavior in d might still depend on the definition of the Soboley norms. Overall. similar to Rakhlin and Zhai (2019) and Buchholz (2022), our proof techniques do not allow to easily obtain dependence on d.
4.2 Inconsistency of overfitting with neural kernels
We would now like to apply the above results to neural kernels, which would allow us to translate our inconsistency results from the kernel domain neural networks. However, achieve this, we need to take one more technical hurdle: the equivalence results for NTKs and NNGPs only hold for probability distributions on the sphere Sd (detailed summary in Appendix B.4). Lemma E.I provides the missing technical link: It establishes smooth correspondence between the respective kernels, Sobolev spaces, and probability distributions. The inconsistency of overfitting with (deep) ReLU NTKs and NNGP kernels then immediately follows from adapting Theorem 1 via Lemma E.
Theorem 4 (Overfitting with neural network kernels in fixed dimension is inconsistent). Let e E (0, 1), and let P be a probability distribution with lower and upper bounded Lebesgue density on an arbitrary spherical cap T = {x E Sd Iatz < v} C Sd.
(-1, 1). Let is either be (i) the fully-connected ReI.U NTK with 0-imitialized biases of any fixed depth 2 2, and d 2 2, or (ii) the conlecco ReLU NNGP kernel without biases of any fixed depth L 2 3, and d 2 6.
5

---

Then, if ft.o fulfills Assumption (O) with probability at least e over the draw of the data set D, St.p is inconsistent for P.
Theorem also holds for more general estimators in Theorem 1, cf. the proof in Appendix E.
Mallinar et al. (2022) already observed empirically that overfitting common network architectures yields suboptimal generalization performance on large data sets in fixed dimension. Theorem now provides a rigorous proof for this phenomenon since sufficiently wide trained neural networks and the corresponding NTKs have similar generalization behavior (e.g. (Arora et al., 2019, Theorem 3.2)).
4.3 Relaxing smoothness and noise assumptions via spectral concentration bounds
In this section, we consider a different approach to derive lower bounds for the generalization error of overfitting kernel regression: through concentration results for the eigenvalues of kernel matrices. On a high level, we obtain similar results as in the last section. The novelty of this section on the technical side, and we suggest that non-technical readers skip this section in their first reading.
We define the convolution kernel of a given kernel k as k. (xr, x') = f k(æ, æ" x")k(a", x') dPx (æ"), which is possible whenever k(æ; -) E L2(Px) for all æ. The latter condition is satisfied for bounded kernels. Our starting point is the following new lower bound:
Proposition 5 (Spectral lower bound). Assume that the kernel matrix k(x, X) is almost surely positive definite, and that Var(ylæ) 2 0² for Px almossstt all x. Then, the expected excess risk satisfies
0²
n
(1a ()K,))/nn 21---211, x
Ep EpRp(fe.) Rp
Ex x
(3)
71
(2((((X))/m)) p)²
Using concentration incqualities for kernel matrices and the relation between the integral operators of k and k., it can be seen that for t oo and O, every term in the sum in Eq. (3) should converge as n - co. However, since the number of terms in the sum increases with n and the convergence may not be uniform, this is not sufficient to show inconsistency in expectation. Instead, relative concentration bounds that are even stronger than the ones by Valdivia (2018) would be required to show inconsistency in expectation. However, by combining multiple weaker bounds and further arguments on kernel equivalences, we can still show inconsistency in expectation for a class of dot-product kernels on the sphere, including certain NTK and NNGP kernels (Appendix B.4):
Theorem 6 (Inconsistency for Sobolev dot- dot-product kernels the sphere). Let k be dot-product kernel on Sd, i.e., a kernel of the form k(x, x') = n((a, x )), such that its RKHS Hy is equivalent to a Sobolev space H (8A), s > d/2. Moreover, let Px has lower and upper bounded density w.r.t. the uniform distribution (Sa).. and such that Var(y)æ) 2 o² >> for Px- Px-almost all x E . Then, for every C' >> O, there exists independent of o² such that for all 2 1, E (C-1n2o/d, so), and p Cn (2-e/d),, the expected excess risk satisfies
a distribution on Sd B. such that
Ep EnRr(S(.p) - Rí 2 c02 0.
The assumptions of Theorem 6 and Theorem 4 differ in several ways. Theorem 6 applies to arbitrarily high smoothness and therefore to ReLU NTKs and NNGPs in arbitrary dimension d. Moreover, applies distributions on the whole sphere and allows more general noise distributions. On the flip side, it only shows inconsistency in expectation, which we believe could be extended to inconsistency for Gaussian noise. Moreover, it only applies functions of the form ft,p but provides explicit bound on f and p get inconsistency. For t = oo, the bound p O -2e/dd appears be tight, as larger yield consistency for comparable Sobolev kernels on Rd (Steinwart et al., 2009, Corollary 3).
We only prove Theorem 6 for dot-product kernels on the sphere since we can show for these kernels that Ha. is equivalent to a Sobolev space (Lemma F. F.13), while this is not true for open domains Ω (Schaback, 2018). However, an improved understanding of Hk. for such Z could potentially allow to extend our proof to the non-spherical case.
The spectral lower bounds in Theorem F.2 show that our approach can directly benefit from developing better kernel matrix concentration inequalities. Conversely, the investigation of consistent kernel interpolation might provide information about where such concentration inequalities do not hold.

---

5 Consistency via spiky-smooth estimators - even in fixed dimension
In Section 4, we have seen that when common kernel estimators overfit, they are inconsistent for many kernels and wide variety of distributions. We now design consistent interpolating kernel estimators. The key is to violate Assumption (N) for every fixed Sobolev RKHS norm .|NN, and introduce an inductive bias towards learning spiky-smooth functions.
5.1 Almost universal consistency of spiky-smooth ridgeless kernel regression
In high dimensional regimes (where the dimension d supposed to grow with the number of data points), benign overfitting of linear and kernel regression has been understood by an additive decom- position of the minimum-nowe norm interpolant into a smooth regularized component that is responsible for good generalization, and a spiky component that interpolates the noisy data points while not harming generalization (Bartlett et al., 2021). This inspires us to enforce such a decomposition in arbitrary fixed dimension by adding a sharp kernel spike phy, to a common kernel k. In this way, we can still generate any Sobolev RKHS (see Appendix G.2).
Definition 7 (Spiky-smooth kernel). Let k denote any universal 1.1 kernel function on Ii We call the smooth component. Consider a second, translation invariant kernel k. of the form ky (2. y)
Laplace Spiky-smootth
p
q( (( ) for some function q Rd + R. We call it the spiky component. Then we define the p-regularized spiky- smooth kernel with spike bandwidth as
1.0
0.9
(ar, y) = k( y) + p. (2, v),
y, E Rd.
(4)
-0.1
0.0
0.1
We now show that the minimum-none interpolant of the spiky- Figure 2: The spiky-smooth ker- smooth kernel sequence with properly chosen Po: 7n - 0 is nel with Laplace components (or- consistent for large class of distributions, on a space with fixed (possibly small) dimension d. We establish our result under the following assumption (as in Mücke and Steinwart (2019)), which is weaker than our previous Assumption (D1).
ange) consists of Laplace ker- nel (blue) plus a Laplace kernel of height p and small bandwidth y.
(D2)
There exists constant 3x and a continuous function d [0, oo) (0, 1] with o(0) such that the data generating probability distribution satisfies Px (x(B((x)) < 6(t) O(t*x)
for all æ e Ω and all t 2 (here Br (z) denotes the Euclidean ball of radius t around x).
Theorem (Consistency of spiky-smooth ridgeless kernel regression). Assume that the training set D consists of n i..dd pairs (a. v) ~ P such that the marginal Px fulfills (D2) and Eyy < co. Let the kernel components satisfy:
* k is universal kernel, and pr. + 0 and nph + oc.
* hn, denotes the Laplace kernel with sequence of positive bandwidths (7h) fulfilling
In S In 2-a (() + 2 Inn) where a > O arbitrary.
Then the minimum-norm interpolant of the Pa Pn-regularized spiky-smooth kernel sequence kn == kipne consistent for P.
Remark 9 (Benign overfitting with optimal convergence rates). Suppose that we have Sobolev target function f' E H* H* (N)MO), that the noise satisfies moment condition and that Px has an upper- and
density on a Lipschitz domain or the sphere. Then, we show in Theorem G.5 that, by using smooth components i whose RKHS is equivalent to a Sobolev space H > max(s". d/2), and choosing the spike components ky,, as in Theorem the minimum-norm
interpolant of k;,, kp..... ... achieves the convergence rate n (a= log² (n) when choosing the quasi-regularizzaioon Pn properly. Moreover, for s* > d/2, this rate is known to be optimal up to the factor log" (n) (Remark G.6). Since optimal rates can be achieved both with optimal regularization and with interpolation, our results show that in Sobolev RKHSs, overfitting is neither intrinsically helpful nor harmful for generalization with the right choice of kernel function.
7

---

Proof idea. With sharp spikes - O, it holds that (X. 2 I,. with high probability. Hence, ridgeless kernel regression with the spiky-smooth kernel interpolates the training set while approximating kernel ridge regression with the smooth component k and regularization p.
L
The theorem even holds under much weaker assumptions on the decay behavior of the spike compo- nent ky., including Gaussian and Matérn kernels. The full version the theorem and its proof can be found in Appendix G. also applies to kernels and distributions on the sphere $d.
Remark 10 (Interplay between smoothness and dimensionality). Irrespective of the dimension d, we achieve benign overfitting with estimators in RKHS of arbitrary degrees of smoothness. With in- creasing d, for the Laplace kernel the spike bandwidth is allowed be chosen as n/ Ω2 (((n=(2+a)/4) a > 0, for covariate distributions with upper bounded Lebesgue density (see Remark G.2). Hence the magnitude of derivatives of the spikes is allowed scale less aggressively with increasing dimension.
5.2 From spiky-smooth kernels spiky-smooth activation functions
So far, our discussion revolved around the properties of kernels and whether they lead to estimators that consistent. We now turn attention the neural network side. The big question is whether it is possible to specifically design activation functions that enable benign overfitting in fixed, possibly small dimension. We will that the answer is yes: similarly to adding sharp spikes to kernel, we add tiny fluctuations to the activation function. Concretely, we exploit (Simon et al., 2022, Theorem 3.1). It states that any dot-product kernel on the sphere that is dot-product kernel in every dimension d can be written as an NNGP kernel or an NTK of two-layer fully-connected networks with specifically chosen activation function. Further details can be found in Appendix H.
Theorem 11 (Connecting kernels and activation functions (Simon et al., 2022)). Let k: [-1,1] -
R be function such that kig Sd Sd + R. kal xx) ((( x²)) is kernel for every d 2 1. Then, there exist by 2 0 with Li=o by < oc such that k(t)= = Linn bet', and for any choice of signs (si (ee) S [[1,+1], the kernel kis can be realized as the NNGP kernel or NTK of a two-layer fully-connected network without biases and with activation function
bi
1/2
dKNNGP()) = Σ E>>(>b)) s.(6.))/22.
ONTK (x)
St
(it1)
h.(z).
(5)
Here, hy denotes the i-th Probabilist's Hermite polynomial normalized such that [|hellraavro.1)
The following proposition justifies the approach of adding spikes /²/22f to activation function to enable harmless interpolation with wide neural networks. Here we state the result for the case of the NTK; an analogous result holds for induced NNGP activation functions.
Proposition 12 (Additive decomposition of spiky-smooth activation functions). Fix 7, p > 0 arbitrary. Let ks k pk., denote the spiky-smotth kernel where k and k, are Gaussian kernels of bandwidth 7y and respectively. Assume that we choose signs {st and then the activation functions ΦiTK. ΦNTK and @NTK as Theorem 11. Then, for y >> O small enough, holds that
le,
1 - (ON + Sp.ONTTTA (l 2/ 3/2/ exp (-+)
4T +1(++))
7
Proof idea. When the spikes are sharp enough (y small enough), the smooth and the spiky component of the activation function are approximately orthogonal in (2(A 1)) (Figure 3c), that the spiky- smooth activation function can be approximately additively decomposed into the smooth activation component &e and the spike component o² responsible for interpolation.
To motivate why the added spike functions pl/2 should have small amplitudes, observe that Gaussian activation components oi satisfy
1 LINOO = (1-exp (-2) (-2))
| k PeWNGrl22, 1,
(6)
Hence, the average amplitude of NNGP spike activation components 22/22 does not depend on 7, while the average amplitude of NTK spike components decays to 0 with 7 O. Since consistency requires the quasi-regularization p - O, the spiky component of induced NTK as well as NNGP activation functions should vanish for large data sets + so to achieve consistency.
8

---

Coefficient value
1.0
0.4
0.10-
0.2
0.5
0.07
8.0
0.0
0.06-
0.2
=.01
-0.5
0.04
0.02
0.05
0.00
3
26
50
75
100
125
160
175
Index
Figure 3: a., b. Gaussian NTK activation components ΦNTK defined via (5) induced by the Gaussian
kernel with varying bandwidth E [0.2, 0.05) (the darker, the smaller 7) for a. bi-alternating signs 9, = +1 iff [i/2] even, and b. randomly iid chosen signs 8; ~ of the Hermite series of Gaussian NTK activation component with varying bandwidth y. Observe peaks at 2/7y. For reliable approximations activation functions use a truncation 2 4/7. The sum of squares of the coefficients follows Eq. (6). Figure 1.8 visualizes NNGP activation components.
) c. Coefficients
Experiments
Now we explore how appropriate spiky-smooth activation functions might look like and whether they indeed enable harmless interpolation for trained networks of finite width on finite data sets. Further experimental results are reported in Appendix I.
6.1 What do common activation functions lack in order achieve harmless interpolation?
To understand which properties we have to introduce into activation functions to enable harmless interpolation, we plot NTK spike components of induced by the Gaussian kernel (Figure 3a,b) as well as their Hermite series coefficients (Figure 3c). Remarkably, the spike components 6t approximately correspond to shifted, gigh-frequency sin-curve, when choosing the signs in (5) alternate every second that is 8; +1 iff [i/2] even (Figure 3a). Proposition H. shows that the NNGP activation functions correspond to the fluctuation function
(iin==sinnnnn00 WNNGP (x; 7) = V sin 2/2 - + 7/4) = sin (V2/7. + cos (V2/7.2) (ore)+cco(/////
(7)
where the last equation follows from the trigonometric addition theorem. For small bandwidths 7, the NTK activation functions are increasingly well approximated (Appendix 1.6) by
(NTK(E; == VT sin (V2/7 112//.x=+///// x//4 va/2 (sin (V2/7 a)) + cos (V2/7 (8)
With decreasing bandwidth 7 + 0 the frequency increases, while the amplitude decreases for the NTK and remains constant for the NNGP (see Eq. (6)). Plotting equivalent spike components of. with different choices the signs s; (Figure 3b and Appendix I.5) suggests that harmless interpolation requires activation functions that contain small high-frequency oscillations or that explode at large lz], which only affects few neurons. The Hermite series expansion of suitable activation functions should contain negligilee weight spread across high-order coefficients (Figure 3c). While Simon et al. (2022) already truncate the Hermite series of induced activation functions order Figure 3c shows that an accurate approximation of spiky-smooth activation functions requires the truncation index to be larger than 2/7. Only a careful implementation allows us to capture the high-order fluctuations in the Hermite series of the spiky activation functions. Our implementation can be found at https:/ //github.. com htt./morrttiaee wtwaaasttaaaaaaaaaa //iindinn---eeii the- stiees.
6.2 Training neural networks to achieve harmless interpolation in low dimension
In Figure 1, we plot the results of (a) ridgeless kernel regression and (b) trained 2-layer neural networks with standard choices of kernels and activation functions (blue) well as our spiky-smooth alternatives (orange). We trained on 15 points sampled i.i.d. from x = (x1, ~ ld(S') and y = I1 + e with ~ (0, The figure shows that both the Laplace kernel and standard ReLU networks interpolate the training data too smoothly in low dimension, and do not generalize well. However, our spiky-smooth kernel and neural networks with spiky-smooth activation functions achieve close to optimal generalization while interpolating the training data with sharp spikes.

---

We achieve this by using the adjusted activation function with high-freeqn frequenyy oscillations x H ReLU(z) + WNTK t00r) as defined in Eq. (8). With this choice. we avoid activation functions with exploding behavior, which would induce exploding gradients. Other choices of amplitude and frequency in Eq. (8) perform worse. To bring our neural networks close to the kernel regime, we use the neural tangent parameterization (Jacot et al., 2018) and make the networks very wide (20000 hidden neurons). To ensure that the initial function is identically zero, we use the antisymmetric initialization trick (Zhang et al., 2020). Over the course of training (Figure Ic), the standard ReLU network exhibits harmful overfitting, whereas the NN with spiky-smooth activation function quickly interpolates the training set with nearly optimal generalization. Training details and hyperparameter choices can be found in Appendix I.1. Although the -requeenyynccy oscillations perturb the gradients, the NN with spiky smooth activation has stable training trajectory using gradient descent with large learning rate of 0.4 or stochastic gradient descent with a learning rate of 0.04. Since our activation additively decompose the network into its Rel.U-component
function is the sum of two terms, and its WNTK component. Figure 1b and Appendix 1.2 demonstrate that our interpretation of the WNTK comppnent as 'spiky" accurate: The oscillations in the hidden neurons induced by WNTK interfere constructively to interpolate the noise in the training points and regress to 0 between training points. This entails immediate access the signal component of the trained neural network in form of its ReLU-component.
7 Conclusion
Conceptually, our work shows that inconsistency of overfitting is quite a generic phenomenon for regression in fixed dimension. However, particular spiky-smooth estimators enable benign overfitting, even in fixed dimension. We translate the spikes that lead to benign overfitting in kernel regression into infinitesimal fluctuations that can be added to activation functions to consistently interpolate with wide neural networks. Our experiments verify that neural networks with spiky-smooth activation functions can exhibit benign overfitting even on small, low-dimensional data sets.
Technically, our inconsistency results cover many distributions, Sobolev spaces of arbitrary order, and arbitrary
overfitting estimators. Lemma E.1 serves as a generic tool to extend generalization bounds to the sphere 3d, allowing us to cover (deep) ReLU NTKs and ReLU NNGPs.
Future work. While our experiments serve as a promising proof of concept, it remains unclear how to design activation functions that enable harmless interpolation of more complex neural network architectures and data sets. As another interesting insight, our consistent kernel sequence shows that although kernels may have equivalent RKHS (see Appendix G.2), their generalization error can differ arbitrarily much; the constants of the equivalence matter and the narrative that depth does not matter in the NTK regime as in Bietti and Bach (2021) is too simplified. More promisingly, analyses that extend our analysis in the infinite-width limit to a joint scaling of width and depth could help to understand the influence of depth (Fort et al., 2020, Li et al., 2021, Seleznova and Kutyniok, 2022). Finite-sample analyses of moderate width neural networks with feature learning parametrizations (Yang and Hu, 2021) and other initializations could enable to understand how to induce smiky-smooth inductive bias in feature learning neural architectures.
Acknowledgments and Disclosure of Funding
Funded by Deutsche Forschungsgemmeinschal (DFG, German Research Foundation) under Germany's
Excellence Strategy EXC 2075 390740016 and EXC 2064/1 Project 390727645, as well as the DFG Priority Program 2298/1, project STE 1074/5-1. The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting Moritz Haas and David Holzmüiller. We want to thank Tizian Wenzel and Václav Voráček for interesting discussions. We also thank Nadine Große, Jens Wirth, and Daniel Winkle for helpful comments on Sobolev spaces, and Nilotpal Sinha for pointing us to Laurent series.
References
Robert A. Adams and John J.F. Fournier. Sobolev Spaces. Elsevier Science, 2003.
10

---

Michael Aemi, Marco Milanta, Konstantin Donhauser, and Fanny Yang. Strong inductive biases provably prevent harmless interpolation. In International Conference on Learning Representations (ICLR), 2023.
Mikhail Agranovich.
Sobolev spaces, their generalizations and elliptic problems in smooth and Lipschitz domains. Springer, 2015.
Ludovic Amouud, Claire Boyer, and Erwan Scornet. Is interpolation benign for random forest regression? In International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Russ R. Salakhutdinov, and Ruosong Wang- On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Yaroslav Averyanov and Alain Celisse. Early stopping and polynomial smoothing in regression with reproducing kernels. arXiv:2007.06827, 2020.
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear
regression. Proceedings of the National Academy of Sciences, 117(48):3003333077 2020.
Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acla Numerica, 30:87-201, 2021.
Daniel Beaglehole, Mikhail Belkin, and Parthe Pandit. On the inconsistency of kernel ridgeless regression in fixed dimensions. SIAM Journal on Mathematics of Data Science, 5(4):854-872, 2023.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand keree learning. In International Conference on Machine Learning (ICML), 2018.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B. Tsybakov. Does data interpolation contra- dict statistical optimality? In International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Jordan Bell. The singular value decomposition of compact operators Hilbert spaces, 2014.
Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. In International Conference Learning Representations (ICLR), 2021.
Simon Buchholz. Kernel interpolation in sobolev spaces is not consistent in low dimensions. In Conference Learning Theory (COLT), 2022.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Bernd Carl and Irmtraud Stephani. Entropy, Compactness and the Approximation of Operators. Cambridge University Press, Cambridge, 1990.
Niladri S. Chatterji and Philip M. Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research (JMLR), 2021.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. In International Conference on Learning Representations (ICLR), 2021.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much perrpearamtttiizzatinnn is sufficient to learn deep ReLU networks? In International Conference on Learning Representations (ICLR), 2021.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: a survey. Internet Mathematics, 3(1):79 127, 2006.

---

Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
Ernesto De Vito, Nicole Müccee, and Lorenzo Rosasco. Reproducing kernel hilbert spaces on manifolds: Sobolev and diffusion spaces. Analysis and Applications, 19(03):363-39, 2021.
Ronald A DeVore and Robert C
Sharpley. Besov spaces domains in R Transactions of the American Mathematical Society, 335(2):843-864, 1993.
Luc Devroye, Laszlo Györfi, and Adam Krzyžak. The Hilbert kernel regression estimate. Journal of Multivariatee Analysis, 65(2):209-22) 227, 1998.
Eleonora Di Nezza, Giampiero Palatucci, and Enrico Valdinoci. Hitchhiker's guide to the fractional Sobolev spaces. Bulletin des Sciences Mathematiques, 136(5):521-573, 2012.
Konstantin Donhauser, Minggi Wu, and Fanny Yang. How rotational invariance of common kernels prevents generalization in high dimensions. International Conference on Machine Learning (ICML), 2021.
Konstantin Donhauser, Nicolò Ruggeri, Stefan Stojanovic, and Fanny Yang. Fast rates for noisy interpolation require rethinking the effect of inductive bias. In International Conference on Machine Learning (ICML), 2022.
Lutz Duembgen. Bounding standard gaussian tail probabilities. arXiv:1012.2063 2010.
David E. Edmunds and Hans Triebel. Function Spaces, Entropy Numbers, Differential Operators. Cambridge University Press, Cambridge, 1996.
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research (JMLR), 2020.
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy, and Surya Ganguli. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory (COLT), 2022.
Semjon Gerschgorin. Über die Abgrenzung der Eigenwerte einer Matrix. Izv. Akad. Nauk. USSR Otd. Fiz.Matt Nauk, 1931.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029 1054, 2021.
Nikhil Ghosh and Mikhail Belkin. A universal trade-off between the model size, test loss, and training loss of linear predictors. arXiv:2207. 2022.
Tilmann Gneiting. Strictly and non-strictly positive definite functions on spheres. Bernoulli, 19(4): 1327-1349, 2013.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949 986, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level. performance on imagenet classification. In IEEE international conference on computer vision (ICCV), 2015.
David Holzmüller. On the universality of the double descent peak ridgeless regression. In International Conference Learning Representations (ICLR), 2021.
12

---

David Holzmüller and Ingo Steinwart. Training two-layer relu networks with gradient descent is inconsistent. Journal of Machine Learning Research (JMLR), 23((81):1 2022.
Roger Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2013.
Tianyang Hu, Wenjia Wang. Cong Lin, and Guang Cheng. Regularization matters: nonparamet- ric perspective overparametrized neural network. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Simon Hubbert, Quoc Le Gia, and Tanya Morton. Spherical Radial Basis Functions, Theory and Applications. Springer International Publishing, 2015.
Simon Hubbert, Emilio Porcu, Chris J. Oates, and Mark Girolami. Sobolev spaces, kernels and discrepancies over hyperspheres. Transactions on Machine Learning Research (TMLR), 2023.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernll: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Ziwei Ji, Justin D. Li, and Matus Telgarsky. Farly-stopped neural networks are consistent. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Fredrik Johansson et al. mpmath: Python library for arbitrary-precision floatinn floating-poin arithmetic (version 1.3.0), 2023. https://mpmathh org/.
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K. Sriperumbudur. Gaussian processes and kernel methods: review on connections and equivalences. arXiv:1805.08844W/ 2018.
Jianfa Lai, Manyun Xu, Rui Chen, and Qian Lin. Generalization ability of wide neural networks on R. arXiv:2302.0594 05533, 2023.
Béatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. The Annals of Statistics, 28(5):1302 1338, 2000.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as Gaussian processes. International Conference on Learning Representations (ICLR), 2018.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Mufan Li, Mihai Nica, and Dan Roy. The future is oog-gaussin:: Resnets and their infinite-depth-and- width limit at initialization. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly. Biometrika, 2023.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. Annals of Statistics, 48(3):1329-13447 2020.
Tengyuan Liang and Benjamin Recht. Interpolating classifiers make few mistakes. Journal of Machine Learning Research (JMLR), 24(20):1-27, 2023.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-nore interpolants and restricted lower isometry of kernels. In Conference on Learning Theory (COLT), 2020.
Jacques Louis Lions and Enrico Magenes. Non-homogeneous boundary value problems and applica- tions: Vol. 1. Springer Science & Business Media, 2012.
Neil Rohit Mallinar, James B Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: Toward a refined taxonomy of overfitting. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
13

---

Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks, International Conference on Learning Representations (ICIR), 2018.
Andrew D. Mcrae, Santhosh Karnik, Mark Davenport, and Vidya K. Muthukumar. Harmless interpolation in regression and classification with structured features. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Robert E. Megginson. An Introduction to Banach Space Theory. Springer-Vertte New York, 1998.
Leon Mirsky. On the trace of matrix products. Mathematische Nachrichten, 20(3-6)171-177,, 1959.
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization eπror of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime.
arXiv:1911.0154. 2019.
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? 2021.
JMLR,
Nicole Mücke and Ingo Steinwart. Global minima of DNNs: The plenty pantry. arXiv:1905.10686. 2019.
Radford M. Neal. Priors for Infinite Networks. Springer New York, 1996.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, -erg-performncce deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Albrecht Pietsch. Eigenvalues and s-Numbers. Geest & Portig K.-G, Leipzig, 1987.
Iosif Pinelis. Exact lower and upper bounds on the incomplete gamma function. Mathematical Inequalities & Applications, 23)4): 1261-1278, 2020.
Alexander Rakhlin and Xiyu Zhai Consistency of interpolation with Laplace kernels is a high- dimensional phenomenon. In Conference Learning Theory (COLT), 2019.
Akshay Rangamani, Lorenzo Rosasco, and Tomaso Poggio. For interpolating kernel machines. minimizing the norm of the erm solution maximizes stability. Analysis and Applications, 21:193 215, 2023.
Garvesh Raskutti, Martin Wainwright, and Bin Yu. Early stopping and non- con-aaraettric regression: An optimal data-dependent stopping rule. Journal of Machine Learning Research (JMLR), 15(11): 335-366, 2014.
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2005.
Hans Richter. Zur Abschätzung von Matrizennormen. Mathematische Nachrichten, 18(1-6):178-187, 1958.
Robert Schaback. Superconvergence of kernel-based interpolation. Journal of Approximation Theory, 135: 2018.
Cornelaa Schneider and Nadine Große. Sobolev spaces Riemannian manifolds with bounded geometry: General coordinates traces. Mathematische Nachrichten, 286(16), 2013.
Mariia Seleznova and Gitta Kutyniok. Neural tangent kernel beyond the infinite-width limit: Effects of depth and initialization. In International Conference on Machine Learning (ICML), 2022.
Ohad Shamir, The implicit bias of benign overfitting. In Conference on Learning Theory (COLT), 2022.
14

---

James Benjamin Simon, Sajant Anand, and Mike Deweese. Reverse engineering the neural tangent kernel. In International Conference on Machine Learning (ICML), 2022.
Ingo Steinwart. Consistency of support vector machines and other regularized kernel machines. IEEE
Transactions Information Theory, 2001.
Ingo Steinwart. A short note the comparison of interpolation widths, entropy numbers, and Kolmogorov widths. J. Approx. Theory, 215:13-27, 2017.
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer New York, 2008.
Ingo Steinwart and Clint Scovel. Mercer's theorem on general domains: on the interaction between measures, kernels, and RKHSs. Constr: Approx. 35:363-4117 2012.
Ingo Steinwart, Don R. Hush, and Clint Scovel. Optimal rates for regularized least squares regression.
In Conference Learning Theory (COLT), 2009.
Daniel W. Stroock et al. Essentials of integration theory for analysis. Springer, 2011.
Sattar Vakili, Michael Bromberg, Jezabel Garcia, Da-shan Shiu, and Alberto Bernacchia. Uniform generalization bounds for overparameterized neural networks. arXiv:2109.06000 2021.
Ernesto Araya Valdivia. Relative concentration bounds for the spectrum of kernel matrices.
arXiv:1812.02108, 2018.
Roman Vershynin. High-dimensional probability: An introduction with applications data science. Cambridge University Press, 2018.
Guorong Wang, Yimin Wei, Sanzheng Qiao, Peng Lin, and Yuzhuo Chen. Generalized Inverses: Theory and Computations. Springer, 2018.
Yutong Wang and Clayton Scott. Consistent interpolating ensembles via the manifold-Hilbert kernel. In Advances Neural Information Processing Systems (NeurIPS), 2022.
Yuting Wei, Fanny Yang, and Martin J Wainwright. Early stopping for kernel boosting algorithms: A general analysis with localized complexities. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Holger Wendland. Scattered Data Approximation. Cambridge University Press, 2005.
Xingyu Xu and Yuantao Gu. Benign overfitting of non-smooth neural networks beyond lazy training. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
Greg Yang and Edward J. Hu. Tensor programs iv: Feature learning in infinite-width neural networks. In International Conference on Machine Learning (ICML), 2021.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26:289-316 315, 2007.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Yaoyu Zhang, Zhi-Qin John Xu, Tao Luo, and Zheng Ma. A type of generalization error induced by initialization in deep neural networks. In Proceedings of The First Mathematical and Scientific Machine Learning Conference, 2020.
15

---

Appendices
Appendix Contents.
A Detailed related work
17
Kernels and Sobolev spaces on the sphere
19
B.1 Background on Sobolev spaces
19
B.2 General kernel theory and notation
19
B.3 Dot-product kernels on the sphere
20
B.4 Neural kernels
21
C Gradient flow and gradient descent with kernels
22
C.1 Derivation of gradient flow and gradient descent
22
C.2 Gradient flow and gradient descent initialized at have monotonically growing H-norm
23
D Proof of Theorem
24
D.I Auxiliary results for the proof of Theorem
28
E Translating between Rd and Sd
32
F
Spectral lower bound
35
F.1
General lower bounds
35
F2 Equivalences of norms and eigenvalues
38
F3 Kernel matrix eigenvalue bounds
41
F.4 Spectral lower bound for dot-product kernels on the sphere
43
G Proof of Theorem 8
45
G.1 Auxiliary results for the proof of Theorem 8
50
G.2 RKHS norm bounds
H Spiky-smooth activation functions induced by Gaussian components
52
I Additional experimental results
56
I.1 Experimental details Figure
56
1.2
Disentangling signal from noise in neural networks with spiky- smotoh activation functions
56
I.3
Repeating the finite-sample experiments
58
1.4
Spiky-smooth activation functions
58
1.5
Isolated spike activation functions
60
1.6
Additive decomposition and sin-fit
62
1.7
Smooy- kernel
selection
63
16

---

A Detailed related work
Motivated by Zhang et al. (2021) and Belkin et al. (2018), an abundance of papers have tried to grasp when and how benign overfitting occurs in different settings. Rigorous understanding is mainly restricted to linear (Bartlett et al., 2020), feature (Hastie et al., 2022) and kernel regression (Liang and Rakhlin, 2020) under restrictive distributional assumptions. In the well-specified linear setting under additional assumptions, the minimum norm interpolant is consistent if and only if lo < n & d, the top-k eigendirections of the covariate covariance matrix align with the signal, followed by sufficiently many quasi-isotropic" directions with eigenvalues of similar magnitude (Bartlett et al., 2020).
Kernel methods. The analysis of kernel methods more nuanced and depends on the interplay between the chosen kernel, the choice of regularization and the data distribution. Lz-generalization error bounds can be derived in the eigenbasis of the kernel's 's integral operator (Mcrae et al., 2022), where upper bounds of the form vy y k - y/nn promise good generalization when the regres- sion function f* is aligned with the dominant eigendirections of the kernel, or in other words, when || is small. Most recent work focuses on high- gigh-dimensional limits, where the data dimensionality d co. For d - o0, the Hilbert space and its norm change, so that consistency results that demand bounded Hilbert norm of rotation-invariat kernels do not even include simple functions like sparse products (Donhauser et al., 2021, Lemma 2.1). In the regime d' < n S dd+1-0 intarinn-nnvariant (neural) kernel methods (Ghorbani et al., 2021, Donhauser et al., 2021) can in fact only learn the polynomial parts up to order 1 of the regression function /", and fully-connecttd NTKs do so. Liang et al. (2020) uncover a related multiple descent phenomenon in kernel regression, where the risk vanishes for most + oc, but peaks at n d' for all i N. The slower d grows, the slower the optimal rate n . between the peaks. Note, however, that these bounds are only upper bounds, and whether they optimal remains an open question to the best of our knowledge. Another recent line of work analyzes how different inductive biases, measured in || llp-norm minimization, p E [1,2], (Donhauser al., 2022) or in the filter size of convolutional kernels (Aerni et al., 2023), affects the generalization properties of minimum-norm interpolants. While the risk on noiseless training samples (bias) decreases with decreasing p or small filter size, the sensitivity to noise in the training data (variance) increases. Hence only 'weak inductive biases', that is large or large filter sizes, enable harmless interpolation. Our results suggest that to achieve harmless interpolation in fixed dimension one has to construct and minimize more unusual norms than -ormss.
x
Regularised kernel regression achieves optimal rates. With appropriate regularization, kernel ridge regularization with typical universal kernels like the Gauss, Matérn, and Laplace kernels is universally consistent (Steinwart and Christmann, 2008, Chapter 9). Steinwart et al. (2009, Corollary 6) even implies minimax optimal nonparametric rates for clipped kernel ridge regression with Sobolev kernels and f* e H where d/2 < 3 < for the choice Pn. n 2e/ 2+/(2++4) Although f is not necessarily in the RKHS, KRR is adaptive and can still achieve optimal learning rates. Lower smoothness 3 of f well higher smoothness of the kernel should be met with faster decay of Pn. Optimal rates in Sobolev RKHS can also be achieved using cross-validation of the regularization P (Steinwart al., 2009), early stopping rules based on empirical localized Rademacher (Raskutti et al., 2014) or Gaussian complexity (Wei et al., 2017) or smoothing of the empirical risk via kernel matrix eigenvalues (Averyanov and Celisse, 2020).
Lower bounds for kernel regression. Besides Rakhlin and Zhai (2019) and Buchholz (2022), Beaglehole et al. (2023) derive inconsistency results for kernel ridgeless regression given assumptions on the spectral tail in the Fourier basis. Mallinar et al. (2022) provide characterization of kernel ridge regression into benign, tempered and catastrophic overfitting using a heuristic approximation of the risk via the kernel's eigenspectrum, essentially assuming that the eigenfunctions can be replaced by structureless Gaussian random variables. A general lower bound for ridgeless linear regression Holzmüller (2021) predicts bad generalization near the "interpolation threshold", where the dimension of the feature space is close to n, also known as the double descent phenomenon. In this regime, Ghosh and Belkin (2022) also consider overfitting by fraction beyond the noise level and derive lower bound for linear models.
Benign overfitting in fixed dimension. Only few works have established consistency results for interpolating models in fixed dimension. The first statistical guarantees for Nadaraya- Watson kernel
17

---

smoothing with singular kernels were given by Devroye et al. (1998). Optimal non non-asynnnaaee asymmpotiiicc results have only been established more recently. Belkin et al. (2019) show that Nadaraya- -aaaannnantnnnn kernel smoothing achieves minimax optimal convergence rates for E (0, d/2) under smoothness assump- tions on f", when using singular kernels such as truncated Hilbert kernels K K(u) ||ul[ Il wll<1+ which do not induce RKHS that only contain weakly differentiable functions (as our results do). By thresholding the kernel they can adjust the amount of overfitting without affecting the generalization bound. To the best of our knowledge, rigorously proving disproving analogous bounds for kernel ridge regression remains an open question. Arnould et al. (2023) show that median random forests are able to interpolate consistently in fixed dimension because of averaging effect introduced through feature randomization. They conjecture consistent interpolation for Breiman random forests based on numerical experiments.
Classification. For binary classification tasks, benign overfitting is a more generic phenomenon than for regression tasks (Muthukumar et al., 2021, Shamir, 2022). Consistency has been shown under linear separability assumptions (Montanari et al., 2019, Chatterji and Long, 2021, Frei et al., 2022) and through complexity bounds with respect to reference classes like the 'Neural Tangent Random Feature' model (Cao and Gu, 2019, Chen et al., 2021). Most recently, Liang and Recht (2023) have shown that the 0-1 ----genneralization error of minimum RKHS- norm interpolants fo is upper bounded by I and analogously that kernel ridge regression f generalizes as y (*(X)X)+ttt) 'y where
the numerator upper bounds ll Their bounds imply consistency as long as the total variation distance between the class conditionals is sufficiently large and the regression function has bounded RKHS-norm, and their Lemma 7 shows that the upper bound is rate optimal. Under noise condition on the regression function f (x: [x]][=] for binary classification and bounded [I 11,, our results together with Liang and Recht (2023) reiterate the distinction between benign overfitting for binary classification and inconsistent overfitting for least squares regression for large class of distributions in kernel regression over Sobolev RKHS Chapter 8 of Steinwart and Christmann (2008) discusses how the overlap of the two classes may influence learning rates under positive regularization. Using Nadaraya- Watson kernel smoothing, Wang and Scott (2022) offer the first consistency result for a simple interpolating ensemble method with fata-independent base classifiers.
Connection to neural networks. It is known that neural networks can behave like kernel methods in certain infinite-widh limits. For example. the function represented by randomly initialized NN behaves like a Gaussian process with the NN Gaussian process (NNGP) kernel, which depends on details such as the activation function and depth of the NN (Neal, 1996, Lee et al., 2018, Matthews et al., 2018 8). Hence, Bayesian inference in infinitely wide NNs is GP regression, whose posterior predictive mean function is of the form foo.p. where P depends on the assumed noise variance. Moreover, gradient flow training of certain infinitely wide NNs is similar to gradient flow training with the so-called neural tangent kernel (NTK) (Jacot et al., 2018, Lee et al., 2019, Arora et al., 2019), and the correspondence can be made exact using small modifications to the NN to remove the stochastic effect of the random initial function (Arora et al., 2019, Zhang et al., 2020). In other words, certain infinitely wide NNs trained with gradient flow learn functions of the form fi.o-
When considering the sphere Ω = Sd the NTK and NNGP kernels of fully-connected NNs are dot-product kernels, i.e., k(ær, .²) x²( (ar, xx) for some function [-1,1] IR. Moreover, from Bietti and Bach (2021) and Chen and Xu (2021) it follows that the RKHSs of typical NTK and NNGP kernels for the ReLU activation function are equivalent to the Sobolev spaces Hdd+1)/2 (gd) and ((d+3) (24+3)/220) (Sd). respectively, of Appendix B.4.
Regarding consistency, Ji et al. (2021) use the NTK correspondence to show that early-stopped wide NNs for classification are universally consistent under some assumptions. On the other hand, Holzmüller and Steinwart (2022) show that zero-initialized biases can prevent certain two-layer ReLU NNs from being universally consistent. Lai al. (2023) show an inconsistency-type result for overfitting two-layer ReLU NNs with d 1, but for fixed inputs X. They also note that an earlier inconsistency result by Hu et al. (2021) relies on an unproven result. Li et al. (2023) show that consistency with polynomial convergence rates is impossible for minimum-non -nomm interpolants of common kernels including ReLU NTKs. Mallinar et al. (2022) conjecture tempered overfitting and therefore inconsistency for interpolation with ReLU NTKs based on their semi-rigorous result and the results of Bietti and Bach (2021) and Chen and Xu (2021). Xu and Gu (2023) establish consistency of overfitting wide 2-layer neural networks beyond the NTK regime for binary classification in very
18

---

high dimension d = I and for a quite restricted class of distributions (the mean difference μ of the class conditionals needs to fulfill j (2(((d))))/)))) log" (md/n)) and μ. ((d/n))/2))
B Kernels and Sobolev spaces on the sphere
B.1 Background on Sobolev spaces
We say that two Hilbert spaces H1, H2 are equivalent, written as Hi H2, they are equal as sets and the corresponding norms || 11H, and || l/ are equivalent.
Let Ω be an open set with O boundary. In this paper. we will mainly consider &g b-lball for Ω. There are multiple equivalent ways to define a (fractional) Sobolev space ( E Rgo. these are equivalent in the sense that the resulting Hilbert spaces will be equivalent. For example, ( can be defined through restrictions of functions from H (IR)), through interpolation spaces, or through Gobolev-Slobodedd
norms (see e.g. Chapter 5 and 14 in Agranovich, 2015 and Chapters 7-10 in Lions and Magenes, 2012). Some requirements on Q can be relaxed, for example to Lipschitz domains, by using more general extension operators (e.g. DeVore and Sharpley, 1993). Since our results are based on equivalent norms and not specific norms, we do care which of these definitions is used. Further background on Sobolev spaces can be found in Adams and Fournier (2003), Wendland (2005) and Di Nezza et al. (2012).
B.2 General kernel theory and notation
There a one-to-one correspondence between kernel functions and the corresponding reproducing kernel Hilbert spaces (RKHS) Ha. Mercer's 's theorem (Steinwart and Christmann, 2008, Theorem 4.49) states that for compact Q continuous and a Borel probability measure Px on 5 whose support is Ω2 the integral operator Tx.Px (2(xx) L2(Px) given by
TR.Px f(x) = J. ;
can be decomposed into an orthonormal basis (ei)ier of L2(xx) and corresponding eigenvalues (Ac)ier 2 0, > 0, such that
Tx Σ Adisseides feL2(Px).
NEI
We write (x) A4 Moreover, k(xxx²) Diee)ee( converges absolutely and uniformly, and the RKHS is given by
Σ a < )
Hts Σ
aiv Cie Tre
(B.1)
Vel
iET
The corresponding inner product between f Eier oiv E and g = Eier biv H. can then be written as
(f.9)
La.b.
(B.2)
iET
We use asymptotic notation O, θ for integers n in the following way: We write
f(n) = (g)))) + 30 OVn : f(n) S Cg(n)
f(n) ((g(n)) + g(n) = ((f(n)
[(n) = O(g(n)) + [(m) O(g(n) and g(n) O([(n)).
Above, we require that the incquality f(n) S C'g(n) holds for all and not only for n 2 ng. This implies that if (n) = [gg(n)), then f must be nonzero whenever is nonzero. This is an important detail when arguing about equivalence of RKHSs, since it allows the following statement: If we have two kernels k k with Mercer representations
k(xx
Σ (xex(z))
19

---

x') (xe(()))s(())
SE
with identical eigenfunctions e; and eigenvalues satisfying A +(Ae), then the associated RKHSs are equivalent by (B.1) and (B.2).
B.3 Dot-product kernels on the sphere
A kernel of the form k(æ,, x²) <((x, x²)) for some function K is called dot-product kernel. Dot- product kernels are rotationally invariant. Especially, NTKs and NNGPs of fully-connected NNs restricted the sphere S are dot-product kernels. Moreover, kernels like the Laplace, Matém, and Gaussian kernels that only depend on the distance between their inputs are also dot-product kernels when restricted to the sphere $d. Therefore, in this section, will assume that k 8 x Sd IR is dot-produce kernel.
We can then leverage some convenient results from the theory of dot-product kernels on the sphere, which are summarized in more detail by Hubbert et (2023). Let (V........Y.N. ) be real orthonormal basis for the space of spherical harmonics of degree I within L2()).. Moreover, let wa be the surface area of Sd, then the Y1,3 VwaYi,a form a corresponding orthonormal basis w.r.t. the uniform distribution ((A)). Then, a Mercer representation of k is given by
No.i
00
k(xxx')
Σ M
(z
with ju = 14/wa- Especially, the integral operator (B3) for the uniform distribution U($4) has eigenvalues in with multiplicity Ni, and eigenfunctions V1, The RKHS of & is then given by
Ni.
Ni,d
H4:
Y..
oc
t= im
Since the index 1 can be zero, we will denote decay asymptotics for I in the form ([[++))T) and not ((--9), cf. our definition of notation in Appendix B.2.
Lemma B.1 (Sobolev dot-product kernels on the sphere). For a dot-product kernel on S as above, the RKHS Hs is equivalent to the Sobolev space H (S*)), > d/2, if and only if un O(1 2 In this case, we have
>e (T(TE(118))) = (ii-0s/i))
Proof. Step O: Equivalence. p4 O(( + 1)- -2*), 2,), is stated in Section 3 in Hubbert al. (2023) that H4 = (S*)).. On the other hand, if y4 # ((1+1)-22) it easy see that Hr is not equivalent to the RKHS of a kernel with hr O((1 + 12). It remains to show (T(T,,u((1)) O(i 20/4). Step 1: Ordering the eigenvalues. Consider permutation и : No + No such that
μт(1) 2 (T(1)= 2...
We then define the partial sums
S = Σ Nx(i).
For Si-1 <ig St. we then have (T = P((1)-
Step 2: Show (ii) (()) Let C > 0 such that cll + 1) iu C(1 1)- 2$ for all / E No- For indices i.j E No, we have the implications
i ソ>メ= + +1) 2a S (m(()) & (n()) S <C(T(j) + 1
+ m (g)
1/(2a)
(I(() +1)
20

---

Therefore, for i 2 and j 2 0,
T +1) c 1/(2*)
max( (c) - 1/(2x)
( 1)) 1)++1),
P'
1/(2a)
C 1/(2s)
+0++15
min
( (T()) +1) -
(0+1) 1) - 0(j + +
We can thus conclude that (i) +1 Step 3: Individual Eigenvalue decay. As explained in Section 2.1 in Hubbert et al. (2023), we have
O + 1).
Ni.a ( + 1) Therefore,
S Σ ((( + 1) ==
= 1)9).
1=0
Now, let i > 1 and let / E No such that S < <is < St. We have i 2 2((t)) and i S O(11 + 1)9),
which implies i @((1 + 1) since i 2 1. Therefore,
A (1))) ((((()) + 20) @((I + +))-2n 2*) 1 @ (i-22//)
B.4 Neural kernels
Several NTK and NNGP kernels have RKHSs that are equivalent to Sobolev spaces on Sd. In the following cases, we can deduct this from known results:
Consider fully-connected NNs with L 2 3 layers without biases and the activation function xpx) = max(0, xr)"", m E Ng. Especially, the case m = corresponds to the ReLU activation. Vakili et al. (2021) generalize the result by Bietti and Bach (2021) from = 1 to m 2 1, showing that the NTK-RKHS is equivalent to (S*) for $ = (d + 2m 1)/2 and the ANGP-RKHE is equivalent to (S*) for = (d + 2m + 1)/2. For m Bietti and Bach (2021) essentially show that the NNGP-RKHS equivalent to !1* for s =d 3)/2. However, all of the aforementioned result have the problem that the main theorem by Bietti and Bach (2021) allows for the possibility that finitely many μ are zero, which can change the RKHS. Using our Lemma B.2 below, it follows that all μ are in fact nonzero for NNGPs and NTKs since they are kernels every dimension d using the same function K. independent of the dimension. Hence, the equivalences to Sobolev spaces stated before are correct.
Chen and Xu (2021) prove that the RKHS of the NTK corresponding to fully-connected ReLU NNs with zero-initialized biases and L 2 (as opposed to no biases and L 2 3 above) layers is equivalent to the RKHS of the Laplace kernel on the sphere. Since the Laplace kernel is Matérn kernel of order v = 1/2 (see e.g. Section 4.2 Rasmussen and Williams (2005)).
use Proposition 5.2 of Hubbert et al. (2023) to obtain equivalence to H"d) with s = (d+ + 1). Alternatively, we can obtain the RKHS of the Laplace kernel from Bietti and Bach (2021) combined with Lemma B.2.
Bietti and Bach (2021) also show that under integrability condition on the derivatives, O activations induce NTK and NNGP kernels whose RKHSs are smaller than every Sobolev space. Lemma B.2 (Guaranteeing non-zero eigenvalues). Let K [-1,1] - RR let 2 1, and let
ka Sd gd ka(a,, x²) = (((xxx'))
kat2 gd42 gd+2 kazz(a x') ==
Suppose that ka42 is kernel. Then, kis is a kernel. Moreover, if the corresponding eigenvalues of ka satisfy μn for infinitely many then they satisfy μ4 for all E No-
Proof. The fact that ka is a kernel follows directly from the inclusion & S T mentioned in Gneiting (2013). For D E (d, d + 2}. let Hr,a be the sequence of eigenvalues 14 associated with kp Then, as mentioned for example by Hubbert et al. (2023), the Schoenberg coefficients bi. satisfy
r T(
d+1 N an
212
bi.4
(d+11/
21

---

Especially, the Schoenberg coefficients bi,d have the same sign as the eigenvalues pt,d- We use
bi,d 7b442,d
and 1
0 S b1,4+2
2
(1 + 1) - 2242,a)
I 2 and = 1 d 2 2,
b142,4 (4d-1)((-d)) bi, 2(2(+4+3)
(++1)+22)
d(21+d-1)
where the inequality follows from the fact that ka+2 is kernel and the equality is the statement of Corollary by Gneiting (2013). In any of the three cases, 4422, > 0 implies b4.d > O. Hence, br. > 0 for infinitely many I, then bi,d > 0 for all I, which implies pr,d > 0 for all L.
C
Gradient flow and gradient descent with kernels
C.1 Derivation of gradient flow and gradient descent
Here, we derive expressions for gradient flow and gradient descent in the RKHS for the regularized loss
n
2
pllslR = Σ0 (vs L()) = T2 Σ (u.)))
+ Note that we will take derivatives in the RKHS with respect to f. which different from taking derivatives w.r.t. the coefficients in a model f(x) = c k(X, In the RKHS-Norm, the Fréchet derivative of
i=1
al(f) f
Σ
(f(x,) - (b(2), + 22(ff )
n
which is represented in H4 by
2 Σ (s(x)) y.)k((e,,)) + 2ps
n 1=1
Now assume that f DE ask(a;, :) a 1(X Then,
I'()) = Σ (a (Xx,( xzi) - y;)k((z;))) + 2pa :(x,,)
i=1
(a T ki X, X )
k: X + pma" T k(x,)
((*(X, X) + pnI,,aa 3) kx),))
n
Especially, under gradient flow of f, the coefficients follow the dynamics
2
a(t)
n ly (k(X,, X) + pnIn)a(t))
which is solved for a0)) = 0 by
(l))
In - e 2((E(XX)) (k:X,, + pmI y
which is the closed form expression (1) of fr.p- For gradient descent, assuming that JCP = T ((x, .). we have
GD = GD - -1 = T (x,,))
((k(X,)) + pmin)ee y) T ((X,,)
2 (g) (k(x,X) + pmin) k(x.-)
Ct.p + TT n
If JCD 0, the coefficients evolve as Cq = and
2
Ct11p Ct.p + n n For an analysis of gradient descent for kernel regression with p = 0, we refer to, egg. Yao al. (2007).
(y (k(X,X) + pn.n.)ct.p)
22

---

C.2 Gradient flow and gradient descent initialized at O have monotonically growing K-norm
In the following proposition show that under gradient flow and gradient descent with suffi- ciently small learning rates initialized at O, the RKHS norm grows monotonically with time L. This immediately implies that Assumption (N) with Cnorm holds for all estimators St.p from (1). Proposition C.1.
(i) For any t E [0, oo) and any 2 0, ft.p from (1) fulfills Assumption (N) with Cuorm = 1. (ii) For any E No {oo} and any p 2 0, with sufficiently small fixed learning rate 0 S 17 S 2mp+ (k( (x(X.XX))))) ()/m)) st.p fulfills Assumption (N) with Cnorm = 1.
Proof. Proof of (i):
We write (ax)(a) k( X) where Ct,p = (X)y, We now show that the RKHS-
of Jt.p grows monotonically in 1, by using the eigendecomposition x) UAU where
A = diag(A)...... An) E R= is diagonal and U E Ruxn is orthonormal, and writing ÿ = U
Then it holds that
21 In exp exp (- pmJ,i)) A.
11 = (a,,))x((xx X,,,) = ÿ T(AA + pmIt.)
2/ (2 pmtn)) ) (A pml
In exp
n
n
d
2t
Σ
yk
(Ac + pn)z
1- exp
( (Ax + pm)) n
$1/2t
= ol
Uk
A
1=
Proof of (ii):
Expanding the iteration in the definition of Ct.p yields
C1t1p = Σ h-i-1
II
I
2 2
X) + pml))
2m y.
1=0 ==0
We again use the eigendecompositionn k(X, X)=
UAUT, where A diag A ... Xn) E R=*= is diagonal and U E R is orthonormal, and write ÿ = U y. Then, using sufficiently small in all time steps E N, it holds that
learning rates S 1)t S 2(pt)mas
I 11
(ct,p) T((, X)C.,
2m7
t-i-1
II
((1 2mt-jp)
2171 217112 A)
A
2m/
t-i-1
II ((1
2 2ne-sp)
2 A) " n
n
n
n
==
1=0
1=0
n
2m
f-i-1
II j=0
(1 27, 2p + xx/n))
(C.1)
n
E|
The last display shows that [| 1 grows monotonically in t, strictly monotonically if m e
(0, Z(o+ (MIX, (1) holds for all t. It also shows that if p' 2 p then || |æ < [1 [|x for and all p 2 0, observe 1
any E [ To see that || 7t < || l for all L E
that with fixed learning rates me 17 E (0, Mot (MXX
C (0. Dimax (1(( x) ) for all
t E N U {oo} it holds that
2m7
2n (1 20/ds/m)(
(1 2mh
2=0 n
n =0
==
23

---

2n
2nj 2n/2//n 2n2x/n)
n Σ (1
n
21/2x/ n
Ak
Since it suffices to consider the case - 0, using the above derivation in (C.1) yields [15 1 ol for all E N, which concludes the proof.
D Proof of Theorem 1
Our goal this section is to prove Theorem D.I, which can be seen as a generalization of Theorem to varying bandwidths. To be able to speak of bandwidths, we need to consider translation-invariaa kernels. Although Theorem is formulated for general kernels with Sobolev RKHS, it follows from Theorem D.I since equivalent RKHS, such that only the constant Caorm changes in the theorem statement.
always find, for fixed bandwidth, translation inveriiannnv kernel with
To generate the RKHS H' Buchholz (2022) uses the translation-invariin kernel k y) = u (x y) defined via its Fourier transform (B (1 + ( Adapting the bandwidth, the kernel is then normalized in the usual L1 sense,
k (x. y) = - ((x 4)/7).
(D.1)
Theorem D.1 (Inconsistency of overfitting estimators). Let assumptions (D1) and (K) hold. Let Cit (0, 1] and Cuorm O. Then, there exist O and no I such that the following holds for all n 2 no with probability O(/rn) over the draw of the data set D with n samples: For every
function f E Hx with
(0) 1E - y1)² yz)² (1- cRt) a² (training error below Bayes risk) and (N) 11 S Cnomm oo, (norm comparable to minimum-norm interpolant (1)),
the excess risk satisfies
Rp(f) -
(D.2)
kin denotes Li-nomallied translation-invarian kernel with bandwidth 7 > i.e. there exists q: Rd + I. such that (, y) = -y" 4 (²==)))) then inequality (D.2) holds with e independent of the sequence of bandwidths (?m)nEN S (0, 1), as long as fo fulfills (N) for the sequence (Hy,) )NER with
constant Cnorm² 0.
Proof. By assumption, the RKHS norm |1-1 induced by the kernel k (or k. if we allow bandwidth adaptation) is equivalent the RKHS norm -1x,, induced by a kernel of the form (D.1) with an arbitrary but fixed choice of bandwidth E (0. 1). which means that there exists constant C, > 0 such that 2 11/1lx,, S || S C,ll,l,, for all f E Hr. Hence the minimum-norm interpolant gD in H, satisfies
[|bll, S Cyllsnlla S CnCCoomllllllla S C. 1gp, 1 S C...C MeCCoolllgnllllee Ign
where 1191|H I IIl because, gD is the minimum-norm interpolant in Hi. Now consider the RKHS norm || lRR of translation innsaationinvvaiiant kemnel ky, Then the functions (z)(())= = " are eigenfunctions of the kernel's integral operator, so that the RKHS norm can be written as (Rakhlin and Zhai, 2019)
IS, = (2 /
1f(W) du,, J&s ((w)
where i denotes the Fourier transform of f. By assumption we know that there exists a Cro > such that بيع 11 S 11 S Cr 1lllls1 holds for some fixed bandwidth > O, then substituting by w = =w yields
(70) d 1f(w)12 du (2 d S m âi (m)w)) Il, (2 RR @1(7w)
1
/
((
di = 11
24

---

C-u {a
10 a
Cr di )2x))
I
1f(w)2 no (2(Tw)
I Co l1fll110
dw = Crallfll
(2(7)00)
In the same way we get Cap If - Il, for arbitrary > E (0, 1). This shows that the constant Cro that quantifies the equivalence between || ||H, and || RR, does not depend on the bandwidth y- Finally Proposition D.4, Proposition D.2 and Remark D.3 together yield the result.
The following proposition generalizes the inconsistency result for large bandwidths, Proposition 4 in Buchholz (2022), beyond interpolating estimators estimators that overfit at least an arbitrary constant fraction beyond the Bayes risk and whose RKHS norm is at most constant factor larger than the RKHS norm of the minimum-norm interpolant. Compared to Rakhlin and Zhai (2019), Buchholz gets statement in probability over the draw of training set D and less restrictive assumptions on the domain 52 and dimension d.
Proposition D.2 (Inconsistency for large bandwidths). Let cat E (0, 1] and Corm O. Let the data sei D ((x11,1)........ (ma, Wa)} } be drawn i..d. from a distribution P that fulfills Assumption (DI), let g2.> be the minimum-norm interpolant in H == Hy with respect to the kernel (D.1) for bandwidth
0. Then, for every A > O, there exist > 0 and no E N such that the following holds O(1/n) over the draw of the data set with n samples:
for all n 2 ng with probability
For every function f E HH that fulfills Assumption (O) with Oat and Assumption (N) with Cuorm the excess risk satisfies
[n( (x))) 2 c> 0,
where e depends neither on nor on > 7 An An-1/d 1/d
>
Remark D.3. Proposition D.2 holds for any kernel that fulfills Assumption (K). The reason is that any kernel & that fulfills assumption (K) and the kernel defined in (D.1) have the same RKHS and equivalent norms. Therefore every function f E Hr H. (equality as sets) that fulfills Assumptions (O) and (N) for the kernel k also fulfills Assumptions (O) and (N) with an adapted constant Cnorm for the kernel (D.1).
Proof. Step 1: Generalizing the procedure in Buchholz (2022).
We write [n] = (l....,n} and follow the proof of Proposition 4 in Buchholz (2022). Define u(x)) = f' f() - (a)). We need to show that with probability at least O(n over the draw of D it holds that [|ы]|л((**) 2 > O, where depends neither on n nor on 7.
For this purpose we show that with probability at least -1 over the draw of there exist a constants e", n² >> 0 depending only on cat and subset P C [m] with [P"| 2 [x"" .n..]] such that
(x.) (xx)) 2 c" > 0 holds for all E P"
(D.3)
Then via Lemma 7 in Buchholz (2022) well as Lemma D.7 can choose large subset pD [r]] of the training point indices with |P"| 2 n - |P21/2, such that the x; for i E p are well-separated in the sense that mij i ||:; - I1 Z dmin with dmin := cn 11/d where c" depends on Ofi, d, the upper bound on the Lebesgue density C₁ and on the smoothness of the RKHS s. Then the
intersection P" ryp" contains at least |P"| points. Now we can replace p' in the proof of Proposition 4 for & E N in Buchholz (2022) by the intersection p" n p" The rest of the proof applies without modification, where (42) holds by assumption || ll S Cxl1ooll Our modifications do not affect Buchholz' arguments for the extension to s & N.
2
Step 2: The existence of P"
Given a choice of n²" d" > O, consider the event (over the draw of D)
E = { p" C [n] with |P"| 2 |K" -n] that fulfills (D.3)}
= P C [n] with P Z [(1 =²)m] such that (fr)()::) - f(x;)) < d" WeP)
With the proper choices of c" and R" independent of n and f. we will show P(E) S 3n We will find small c" > 0 such that if fr and ff are closer than c" on too many training points P
25

---

and f overfits by at least the fraction Cūt. the noise variables E; on the complement P would have be unreasonably large. contradicting the event Ess defined below, and implying (D.3) with high probability. We will use the notation || == Σiep f(x;)" and |
ii Vi
Step 2b: Noise bounds.
Lemma D.6 (i) states that there exists n² 0 small enough such that the event (over the draw of D)
Es: = (VP1 C [n] with [Pil S [k<" n it holds that
1f 1
ylli,
Σ IEP
c
Cht
0²
72
n2
4
fulfills, for n large enough, P(Es)) 2 1 - n Lemma D.6 (ii) implies that there exists a Clower
0 such that the event (over the draw of D)
Ess == (VP2 with [P2| 2
Clower o [(1 x xn] it holds that ||f 2llis
fulfills, for n large enough, P(Esn) 2 1 n-! Lemma D.5 states that the total amount of noise ||]] concentrates around its mean no², More precisely, we will use that for any Ce E (0, 1) the event (over the draw of D)
yll 2 0² )
Es
1f
fulfills P(Es) 2
exp (-n exp ( )²)
Step 2c: Lower bounding ||=
Given some function f E H. assume in steps 2c and 2d that event E holds and that P C [n] denotes a subset of the training set that fulfills [PI 2 [(1 x")n] and (x.) - f(x,)) < c" Vi E P.
In step 2c, assume we choose Ert > 0 such that Cnill 21 s I| y1ا Then by the overfitting Assumption (O) it holds that
1 1 (cmll - -11 |f y13. < (lf 21 + +15 y1
s (1 cn
(D.4)
If restrict ourselves event F.s, dropping the term |l y y in (D.4), then dividing by a.. and subtracting the result from the inequality in the definition of event Es yields
| = - || - y U1 2 c
CBt 0²
(D.5)
Cnt
Step 2d: Choosing the constants.
If we choose cg = 1 Ctu and Ens
2-2cnt (0, 1), then (D.5) becomes 2-che
4
1 [|l1 2
Cit 0²
4
Now it is left to show that the condition ane ||5" - y13 < Il y1?.. that is required for Step 2c, holds with high probability with our choice of cac-
With some arbitrary but fixed EJower (0, / /lowwrr) choose d" = (1 Vonl Then on event Egis for n large enough, it holds that
vI xxp )o.
(1 - Cne) llf - u 2 (1 Võnu) ((ae)// Vlowwrr 2 VI 13ll d +
(D.6)
Vn"
By definition of P. holds that
|f
1-, = - < [(1 k²)n] (c")
-
EEP
26

---

so that
d" Vii
|f f < vI R" e'
(D.7)
Now, using the triangle inequality, (D.7) and (D.6) yields the condition required for Step 2c,
f 4|ا
1
||f 5u1
|lf f
f
Vn
|| y|ا vI n² c" d'
nL
2V Che
If yll
Step 2e: Upper bounding the probability E.
To conclude, we have seen in steps 2c and 2d that on Eos n Es, holds that
Cüt
4
On Figs, it holds that
|| 4
Cât
0².
Hence Es; n En Eas n Eb = 0. This implies E' C [Ei n Es: n Bea) where the right hand side independent of H and just depends on the training data D. Since P(Es;) 2 2-nn" n- and P(Ea n E5)) 2 1 - n exp (-n )²) it must hold that, for n large enough,
P(E) S P((Es n Egg n Esa))) S 2n + exp (nn- 1.. Ce )
S 3n-
The following proposition generalizes the inconsistency result for small bandwidths, Proposition in Buchholz (2022), beyond interpolating estimators to estimators whose RKHS norm is at most constant factor larger than the RKHS norm of the minimum-norm interpolant. The intuition that if the bandwidth is small, then the minimum-norm interpolant gn,> returns 0 between the is smaller and bounded away from I ||
training points. Then [|gD.> 9D.v by any other function f H that fulfills Assumption (N).
We can replace
Proposition D.4 (Inconsistency for small bandwidths). Under the assumptions of Proposition D.2. there exist constants B,c 0 such that, with probability O(n over the draw of D: For any function f E H. that fulfiills Assumption (N) but not necessarily Assumption (O), the excess risk
satisfies
E (f)) - (())
where depends neither on nor on Bn
Proof. Denote the upper bound the Lebesgue density of Px by Cu. The triangle inequality implies 2 || // 2 |I - 1/1l2 2 >Iff)l VC.llflle [If" - Cn Culll,......
I1 flle,(xx)
where |lf Il follows from the fact that the Fourier transform & of the kernel satisfies k(E) < 1. Now in the proof of Lemma 17 in Buchholz (2022) a > can be chosen smaller to generalize the statement to
1l 12ee <
6C 6,,,C, 11
+ (1/7 2/d + ,, 20/d),
where depends on Cu. f* d, and Crorm Finally can choose B small enough such that Eq. (32) Buchholz (2022) can be replaced by CH Tn (g S (| so that we get
|| -=1ll(((Px) 2 lf [1xx((p() >
27

---

D.1 Auxiliary results for the proof of Theorem
Lemma D.5 (Concentration of Xn variables). Let U be a chi-squared distributed random variable with n degrees of freedom. Then, for any E (0, 1) it holds that
- (-n.
(1-
P c
S exp
2
Proof. Lemma in Laurent and Massart (2000) implies for any x > 0,
U P
- 2 -m I exp (-z).
7
Solving c= 1-2 for x yields r (2=0)²
Lemma D.6. Let El,.,,,,,, En be i.i.d. (00 o²) random variables, o² > 0. Let (52)() denote the i-th largest of e..
(i) A constant fraciont of noise cannot concentrate on less than ( points: For all constants or, c > O there exists constant C E (0,1) such that with probability at least - n ffr n large enough,
Cn. Σ (E2)()
<
n 1=1
(ii) (n) points amount to a constant fraction of noise: For all constants a >> 0 and K E (0, 1) there exists constant >> O such that with probability at least n for large enough,
[(1
(1-=k)m)
(=2)n-itt))
200
n
Proof. Without loss of generality, we can assume 0² 1.
(i) For a constant C' (0,1) yet to be chosen, consider the sum
[Cn] > (E
Sc,,
For T' yet be chosen, consider the random set IT {i E [n] o T} and denote its size by K == |. To bound K, we note that K = E1 +... + E.. where &, = 1 We first want to bound pr == EG, P( T). The random variables e? follow a -i-diitributton, whose CDF we denote by F(t) and whose PDF is
f(t) = (1,c exp(-1/2)
(D.8)
for some absolute constant C₁. Moreover, T and & to denote the CDF and PDF of N (0, 1), respectively.
Step 1: Tail bounds. Following Duembgen (2010), have for 0:
2Φ(x:)
2Φ(x))
((x)
- +(x) >
2
4 V +
2
1 1
20(x)
26(x)
((x)
V2 + x2 +
1+x
Hence, for L. 0, we have
1 F(t) 2 20- ((vF)) 20(v8)
2 expl-t/12
1 17
π
I + Vi
F(t) = 21 - -(v7)) < 40(v1)
8 exp( 11/2)
1+ VE
π
1 1 1+v2 Vt
28

---

By choosing T = -2log(CVT/33) > O, we obtain
PT - 9T=1-P(1) < -
Step 2: Bounding K. The random variables Ç, from above satisfy & E 00, 1]. By Hoeffd- ing's ss inequality (Steinwart and Christmann, 2008, Theorem 6.10), we have for > 0
( - (c: - EE)) 2 (1 (1-0) VV P
S exp(-r))
2n
We choose
C² C2 such that with probability 2 1 exp( -C2n/2).
have
C3112 C/2.
K/n PT
E(E (E: -EE,) -
2n
Suppose that this holds. Then, K S npr Cn/2 K & [C']. This implies
Cn and, since K is integer,
Sc,,
1 n
(E9) +(CC) + -K)T S CT D (
(D.9)
We now want to bound E (E))(0) To this end, note that conditioned on K k for iim
some [n]. the random variables (E:)eez, are i.i.d. drawn from the distribution e² given E² T. for (N(0, 1). By X, X1, we denote i.id. random variables drawn
from the distribution of E² T E² > This means that conditioned on K k
&
Σ (
Σ SEIr
of is distributed as kT Σ
X
(D.10)
1
Step 3: Conditional expectation. The density of X is given by
+1) (t) = 1,0 1- F(T)
(D.)
I 1,50 CT exp(
/2/mexp(-T/2)/11+
S 12 exp( (t/2).
where we have used that for > 0,
1 + VT
1 VT
=1+
2
VT +t
VT
VT
since T = -2 -og
2 -2
T/32) 1.008. We can now bound
E[X] (0 (t)
- L Cztexp(-tt2)dt 4C2
(D.11)
Step 4: Conditional subgaussian norm. For t 20
P( x) P P(X t) 1 1- F(T +t) 1- F(T) < 1+ V 2ep 11/2)
I+VT+7 exp(-T
Since the denominator in exp( (tt() is constant, by Proposition 2.7.1 and Definition
2.7.5 in Vershynin (2018), the subexponential norm || is therefore bounded by an absolute constant C3. Moreover, by Excercise 2.7.10 in Vershynin (2018), we have || EX < Xall < C2 for absolute constants Ca, Cs.
Step 5: Conditional Concentration. Now, Bernstein's 's inequality for subexponential random variables (Vershynin, 2018, Corollary 2.8.1) yields for L > O and some absolute
constant Co
X; EX; 21 < 2exp (-Ca min (
.
t
P Σ
(D.12)
KC
29

---

We choose t = CnCn and obtain for k 2 Cn
P
(=2)(0) KT 4C2k + 4C2k+
C3Cn
K K=
(D.10)
p
X 2 4C2k C3On
K K=K
(D.II)
S P
Σ
X₁ EX, 2t)
(D.12)
S 2 exp (-CgOn).
Step 6: Final bound. From Step 2, we know that K & [Cn] with probability 2 1 exp( C22n/2). Moreover, in this case, Step 5 yields
K
Σ (E2) < KT 442K + CgCn S Cn(T + 402 + Cs)
with probability exp( (ep(--CCCi) By Eq. (D.9), we therefore have
Scn, < CT C(T + 4C2 + Cs) = -4C log (VV/T//32))) + CyC.
Since lime - C'lo((C) = 0, we can choose C' E (0, 1) such that -4C CC /32) CrC for the given constant > from the theorem statement, and obtain the desired
bound with high probability in
(ii) Since the of are non-negative and their distribution has a density, there must exist T
with P(e < T) < (1 <)/4. Similar to the proof of (i), we then want to bound K ==
{i E [n] 8 < TT] = 31 + +........ E. with & = 1 The & E [o, 1] are independent with < (1 - -xx)/4 /. As Step 2 of (i), Hoeffding 's incquality then yields for
EG,- = P(e < T)
0:
P
Σ (E: RC)
2 0)
O)y
T
I eep((-7)
2n
1=1
We 7 = (1- 2/22, such that with probability
2 1 - exp((1 (1 - n2)2 we have
(1 x=)22
K/n - k < K/n P(e < <T)
Σ (E. - EEi)
2n
1-K K
In this case, we have
[(1 (Q=x))]
Σ
(n2)())i+1))
> - (1(1 - x)ml KYT 2
1 (((1 -x) 1) KYT
1 n
T
where the right-hand side lower bounded by e (1 - x)T/8 for large enough.
The next lemma a generalization of Lemma 9 in Buchholz (2022) to arbitrary fractions k of the training points. Therefore, for any x E (0, define
2/d
8min (K) = nnn-11 1/dd -1/d
R Cptwd
Lemma D.7 (Generalization of Lemma 9 in Buchholz (2022)). Let N,V E (0, 1), and let O
be a constant that satisfies Px (dist((r, 02) < on) S K. Let (a1,..., an) be Lid. points distributed according the measure Px, which has lower and upper bounded density its entire
30

---

bounded open Lipschitz domain Ω S CR, G px S Ca. Then there exists constant θ >> 0 depending on d, Cu: V such that with probability at least 1 - exp
Jen there exists good subset
P C P, IP'| N (1 7k)n, with the following properties: For a E P we have dist(æ, 022) 2 cn
x y 8min (R)) for x y P', and for all x E P' we have
29 (k) 2
Σ
x y
2u
R2
MEP' (z)
Proof. First by the definition of min holds that
P
UB Kj
B (x; 6miu)
S Cawsominn S
Also for all y Ω
Ey ((x - y) - 2d-201 (100 y 2 dminn)
x - y) dd-2v px (2))dæ
Bly bmiin)
S Cu B(a,kmin))
x yl -d d- 2u dy S A5m2n 2v
for some θ >>> O depending only on Cu, d and v. We conclude that for each j
P
x; Øz d 2v 1 (læ:; Bgy >> 6min)
K
Also P (dist (zj, 022 < cn) K. The union bound implies that
o 2y min n
& U (as,, 6min),
Σ i<j
Dc - x.J
2-
1|2, -z, 12,1,, 8mi
dist 00) > co
i<j
Oo min
=P
Øj $ UB(x, min),
Σ
x xz}
d=2u
dist (x,, > en 2 3K.
i<j
isj
We use a martingale construction similar to the one Lemma 7 of Buchholz (2022) by defining
O
2v
Eg xz U (æ;; Bx Smiu), i2)
Σ x xz51 --11--2
min
dist(a;, 02) ca
Now define Sn = Σi= 1E, Using the filtration F, o OzI,,........................... æ;), S, be decomposed into S, Mn. + An, where Mn is martingale and An is predictable with respect to F, We then get
A. < Σ (FE,(F,-)) 3kn as well as Var(M.]FF-1) < 3x. Hence Freedman's 's inequality
Theorem D.8 yields
3KM
P(S, 6KM) P(A, 3Rm) P(M, 2 3kn) S exp
This implies that with probability at least - exp with IP,1 2 (1 6x)n on which holds that min 2
(-
3Km 7
we can find a subset P. = -. 2m3
I,1 2 8min dist (z,, 2 on and
Σ 1z: 12a-2,1-00 -d-20 (
205
22 min n
Using Markov's inequality see that there are at most points in P. such that
2 205 n
Σ
1--
min
z S'EP..ZEE
31

---

Removing those points we find a subset P' C C. such that [P'| 2 (1 7k) and for each 2 E p
26 205mm n
E 2 22-2'' 2'1--v1
d-2v
x²
Theorem D.8 (Freedman's 's inequality, Theorem 6.1 in Chung and Lu (2006)), Let M, be discrete martingale adapted to the filtration Fr with Mo 0 that satisfies for all i 2 0
M Mi 1 K
Var (M₂ F:-1) s oî.
Then
P (M, - (M,) Se 25 IRA/S.
E
Translating between Rd and Sd
Since the RKHS of the ReLU NTK and NNGP kernels mentioned in Theorem 4 are equivalent to the Sobolev spaces (d (S*) and H(2+3)/2 (S"), respectively (Chen and Xu, 2021, Bietti and Bach, 2021) (detailed summary in Appendix B.4). Inconsistency of functions in these RKHS that fulfiil Assumptions (O) and (N), in Theorem I, follows immediately by adapting Theorem I via Lemma E.1. In particular, inconsistency holds for the gradient flow and gradient descent estimators ft.p and [t.p as soon as they overfit with lower bounded probability.
For arbitrary open sphere caps T == {a E S
za-1 < v), (-1,1). and the open unit ball Bi (0) = (y E RRd yyll 1}, define the scaled stereographic projection Φ T B1 (0) C Rd as
Cy
Cd
Φ . xd+11
Jd+1
2.4
where the normalization constant
1-v 1+
ensures surjectivity.
Straightforward calculations show that & defines a diffeomorphism. Its inverse d-1 1 Bi(0) + T' given by
20, 91
20,
(3) .U...... Ma)
Cv 1
We can translate kernel learning with the kernel on Sd and the probability distribution P, where Px is supported on T, to kernel learning with transformed kernel k and P using a sufficiently smooth diffeomorphism like Φ T + B₁ C Rd. If the RKHS of k is equivalent to H (Sd) then the RKHS of i is equivalent Hº H+B; (0)). We formalize this argument in the following lemma. As a consequence it suffices to prove all inconsistency results for Sobolev kernels on B1)
Lemma E.1 (Transfer to sphere eaps). Let be a kernel on &d whose RKHS is equivalent to Sobolev space HS*))). For fixed E 1), consider
"open sphere cap" T == {x Sd Jd+1 < v). Furthermore, consider distribution P such that Px is supported on T and has lower and upper bounded density px on T, i.e. 0 < Ci S px(x)) S C. < oo for all T. Then
k(xxx') == (x), (or)),o110 (x')) defines positive definite kernel on (1 S R whose RKHS is equivalent to the Sobolev space H² (O),,).
P = P a --- with (xx y) (0(x), y) defines a probability distribution such that P has lower and upper bounded density on B (0) S Rdd
and kernel learning with (ks P) with (ke, P) is equivalent in the following sense:
For every function f H.(kl)))) the transformed function f = f o x- 1 E (H()) has the same RKHS norm, i.e. [[ = [| Furthermore, the excess risks of over P and of f over P coincide, i.e.
Emp Px (f(x) - ff(())) Eg-Py (f(() f(()))
f))()))
where fz(() -EX (81 .)) denotes the Bayes optimal predictor under P.
32

---

Remark E.2. Many kernel regression estimators can be explicitly written as fz(x) (k(a,, x), ( X), y) where fn IR 2 x RR R denotes measurable function
for all n E Then the explicit form is preserved under the transformation, i.c. f oo = = with the transformed data D {(o(z)), me)))
Proof of Lemma I. Step I: Bounded density. For i E [d].j E [d + 1]. the partial derivatives are given by
for = j,
Za+1
0z)))(x)=
Calls
for i E [d], j = d +
otherwise.
Given arbitrary multi-index a, the partial derivatives daΦ; (T), Oz0j' E (Br bounded for all E [d], (d + 1), using s4+1 v and the inverse function theorem.
Now define k(x,, x') - (a)), o - (a')), (xx, y) (Φ(æ)), y) and P = P o -- Then using integration by substitution (Stroock et al., 2011, Theorem 5.2.16), the Lebesgue density of Px is given by
px( = px (a))Jo
where
J6 (3) = [det
(a)) geti (E (......).))))) )13 1/2
Jó and J can be continuously extended to T and B1 (0). respectively. Then, since Jø is continuous on a compact set and because & with the extended domain remains a diffcomorphism so that JΦ J cannot attain the value 0, there exists constant C. such that C, $ Jo ()) Co for all æ E (0). Hence, Px is lower and upper bounded.
Step 2: Excess risks coincide. If (X,8) ~ P. the Bayes predictor of ý given X is given by f*( = [ = x) = (
Let क (æ. = x: be the projection onto the first component. Then, (FI( v)) = x(x)) = Ti ()(()))))) (vb 8)) and hence
Exnpy (f(x)) (=))²
E (f))
Ex (f(z) (x))
Step 3: Transformed RKHS. We want to show that 7((kl)) + H(k),f + fo Φ-1 defines an isometric isomorphism, which especially shows the statement || [ = [[ from the proposition. For this, we use the following theorem characterizing RKHSs:
Theorem E.3 (Theorem 4.21 in Steinwart and Christmann (2008)). Let k X XxX - R be a positive
definite kernel function with feature space Ho and feature map & : X - Ho. Then
H (f: X + R Ee E Ho f (w, (b()) H,) with || == [] Ho f = (w. 2 H.)
is the only RKHS for which k is reproducing kernel.
feature map for kely is given by T + H(kk) ((x) = k(x,)) :). Hence a feature map for is given by & o -- (0) + H(k),)) Theorem E.3 states that
H(k),) = { + R Bw E H((),)) f f= (w, (-)))((())))) with || (((l)))()))) = inf [((())))))))) f (w, 2 (()))(())))))
(E.1)
33

---

as well as
H(K)) = { (0) - IR| Ew E H(k)))) f f= (w, t o 2000'1())0)) ()H(m) with (E.2)
(())) = inf [nl[lwll f = (w, 1 o ())(())))))
As Φ-1 is bijective, this characterization induces an isometric isomorphism between H(kl)) and H(kk by mapping f = (w, (()) H((k)p) =fo foo (w, -o000)1()))))) ()) E H(k). This shows (((),))(() = 11 [lfl)
Step 4: RKHS of k. We now show that the RKHS of in, denoted as H(k)), is equivalent to (B (0))
To this end, denoting A o = o @ I E A} and AlT = {fln f E A}. we show the following equality of sets (ignoring the norms):
(kk Φ 2 H(k
1 H(H))2 (II) (S)) T (B))
Since & is bijective, this implies H(k) (B: as sets, and the norm equivalence then follows from Lemma F.7.
Equality (I) follows from Step 3. Equality (II) follows from Theorem E.3 by observing that if & is a feature map for k, then / is feature map for k/ Equality (III) holds by assumption. To show (IV), we need characterization of HS*) that allows to work with charts like ø.
Step 4.1: Chart-based characterization of H HS")). A trivialization of a Riemannian manifold (M,g) with bounded geometry of dimension d consists of a locally finite open covering {Ua Joer of M, smooth diffeomorphisms Ki Va C Rd + U.. also called charts, and partition of unity {ha]aer of M that fulfills supp(ha) S Ua. S ha S 1 and Eaer ha 1. An admissible trivialization of (M.g) geodesic coordinates, for details see (Schneider and Große, 2013, Definition 12).
uniformly locally finite trivialization of M that compatible with
In our case, define an open neighborhood of T by U1 = (a E gd ra+1 < + E} with some e E (0, 1-11) arbitrary but fixed, and U22 == {a E Sd [e41 > e e/2). It holds that U1 UU, Sd Moreover, there exists an appropriate partition of unity consisting of C functions h1, h2 Sd + Br (0) denote the stereographic projection with respect to Zo = (0,.... 0,1) as above, scaled such that Φ1lr = and hence (7) = (0). Similarly, let 02 : U2 + (0) denote an arbitrarily scaled stereographic projection with respect to 3% (0,...,0, 0, 1). Then ((U1, U2), { Φ1 (h,, h2)) yields an admissible trivialization of Sd consisting of only two charts. A detailed derivation can be found in (Hubbert al., 2015, Section 1.7). Therefore (Schneider and Große, 2013, Theorem 14) lets define the Sobolev norm on Sd (up to equivalence) as?
[0, 1]. Especially, we have (T) C (Ug)
{1}. Let :::
1/2
|191| (89)
Σ ((hhaag) o Ka (1l112r(22) Lael
(11(h19) o o 1| (R)) + (1(22) oz ((2) 1/2
for any distribution g E D' (s() (i.e. any continuous linear functional on C² (S+). Then g E (S*) if and only if [[))) < 00.
Step 4.2: Showing (IV), First, let g E HSd).. Then, as we saw in Step 4.1, we must have [[(h1g) o oं (14) and thus (hıg) o of E (R.). By our discussion in Appendix B. we then have
( ((hig) o5 + BBB( E (O),
which shows g/T (H) σ6
Now, let f (O) Then, again following our discussion in Appendix B.1, there exists an extension f (RR) with fl (0) f. The set B d (U, U2) is closed ball (O) of radius
'Here, the norms are taken on H " since the respective functions can be extended to ga by zero outside of their domain of definition, thanks to the properties of the partition of unity.
34

---

I<r<r Hence, we can find C (R") with (( = {1} and (((B,(0)) {0). Since +p smooth with compact support, we have sp ʃ E (R()). Define
(10 ()(x)) (0
x U1
Jst S aR
x & U1
By construction, we have (x) for all a e U2. Hence, the equivalent Sobolev norm from Step 4.1 is
1/2
Il 11 = (1()) o1 "1 (1 + 11b2580) o 02 (l) = [h1 o ) + / ((d)) < 00
which shows fae E (S*). But then, o à farr H²( In total, we obtain H*(S") = (B: o, which shows (IV).
F Spectral lower bound
F.1
General lower bounds
common first step to analyze the expected excess risk caused by label noise is to perform a bias- variance decomposition and integrate over y first (see c.g. Liang and Rakhlin, 2020, Hastic et al., 2022, Holzmüller, 2021), which also used in the following lemma.
Lemma F.1. Consider an estimator of the form (x.) = (vx,a) y. If Varr(ul)) 2 o² for Px-almost all x. then the expected excess risk satisfies
Rp - R2 2 o
Proof. A standard biri-vari decomposition lets us lower-bound the expected excess risk by the estimator variance due the label noise, which can then be further simplified:
Ep EpRr((x..) - Rp Ex.= (Ewix [xx,v(=))]] (Eyix(/x
Ex, x (fx,v(a) Ex)x(xx(x=))
Ex. (Ux (y EyIxui(u - Eyjxy T Ux
Ex,,(UX,x))
Ey - Ey E 1 ux..
=Ex,a Cov(y) X Ux
Here, the conditional covariance matrix can be lower bounded in terms of the Loewner order (which defined as + B positive semi-definite:
Var(y1 (21)
Cov(y|X)
2 o² I,
Var x.n))
since the labels y are conditionally independent given X. We therefore obtain
EDRr(fx - Rp 2 (Ux,=)) Cov(y)X) X)xx,
2 p²Ex x tr((Ux.a) ux.a)
=o²Ex ( (vx
Proposition (Spectral lower bound). Assume that the kernel matrix k(X, X) is almost surely positive definite, and that Var(ylæ) 2 ²² for Px-almost all x. Then, the expected excess risk satisfies
n
(X_ X)/n) (1-e-2()(((xxxX)//)))
EpRp(Se,p) - R2
n x
(3)
(x(k(XX))/m) p)
35

---

Proof. Recall from Eq. (1) that
[t))(x)) kk(,,, X) (t)
( A (x) = - xxx
(B(X, pml
By setting (Ux (Ux,*)T )T= = k(x, X) A we can write fx,x)t,(()) = fx, = (ux,.) yy. Using
Lemma F.1, we then obtain
Ri 2 o2 lr( (UXxx,(UXX
o -x ir (X)) k( (x 00) ()cae,))AAnn x)A
Since
2x)x(x2))((z X)); E,b( k. (2, (X,,
we conclude
EpRp(fxxtt.)) Rip 2 x tr (x,
= =x (k: (X; X p (x)))
Richter (1958) showed (see also Mirsky, 1959) that for two symmetric matrices B, C, we have tr(BC) Ei= ((())x+t-+(()) We therefore conclude
ED EDRp(fxxyt..)
Rp 2
Ex
(I)
As At.p ( (X) X) built only out of the matrices 6(X, X) and I,,, is not hard see that
Ar, (X) At,p (X has the same eigenbasis as ((X,X] with eigenvalues
(xX xx) x()+ 2
2UA, = (1 1 n
1
A = Ax(k((X
pm
(k(KX, +
remains to order these eigenvalues correctly. To this end, we observe that for 0, the function g(A) = 1- 21
satisfies
g((A)= 2t 2tA e1-a-211)
(2t) + 1)e-2td 21A -
221e 221
0.
X2
X²
X2
Therefore, is nonincreasing, hence the sequence (Å:) is nondecreasing and thus
Antp- d
from which the claim follows.
Theorem F.2. Let k be a kernel on a compact set Q and let Px be supported on Q. Suppose
that k(X XX) is almost surely positive definite and that Var(y x)) 2 o²r Px-almost all æ. Fix
constants O and q. C 2 1. Suppose that X, (T(Tx,Px) 2 ci- Let I(n) be the set of all i [n] for which
X//C S (((KX,XX//I S CA:
(F.1)
X & (X),
both hold at the same time with probability 2 1/2. Moreover, let I(n) = max(m E [n] [m] S I[m)]. Then, there exists constant e' > 0 depending only on C such that for all p 10, oc) and
t (0, oo), the following two bounds hold:
1
[(n)
EpRp(fxwe.) Rp 2 do²
1+ (p+ +++-lmm 1m
n
(p (p+tl))
(p t 1/q I(n)
Ef Rt 2 do² min
n
T
36

---

Remark F.3. Theorem F.2 provides two lower bounds, one for general "concentration sets" I(n) and one that applies if concentration holds for a sequence of "head eigenvalues" {I..... [n)] [(n.. If T(n) x [, the latter bound is stronger for larger regularization levels, and this bound would be particularly suitable for typical forms of relative concentration inequalities for kernel matrices. However, in this paper, we obtain concentration only for "middle eigenvalues" I(n) {i en S (1 =)nn,, and therefore we only use the first bound in the proof Theorem 6.
Proof of Theorem F.2. Step 1: Miscellaneous inequalities. For > 0,
T
1
1 1 =1 e
(F22
I x+
I ++1 1+x1
Moreover, since (1 a1+ < (1 a)) + (1 a)² = 2 2a², we have for a + -1:
2
2
(F.3
1+a 2(1 + a²)
Step Applying the eigenvalue bound. Define
S(X)= = (X, )/)) (1 - (1-e-2(00((xxxx//00))
(a(l(XX))/n)) p)2
By Proposition 5, we have
0² Sx
ED En
Rp 2
Σ SX)
(R.4)
TEI(M)
Since (x) is almost surely positive, can focus the case where (F.1) and (F.2) hold, which is true with probability 2 1/2 by assumption for E [n). Hence,
1 x//C..
e-20x//+p1)2 (F2)
X/CC
Ex (X)
2 (CAs +22
2 (C}: + p) (2((s
+))
We can upper-bound the denominator, using C² as
(C): + (1+ 2t(2s/C - )
C² SCA+pP p+
+
SC
(): CC)t
(A: + Cp)t
CC (A: + +
which yields
Ex)( 2 1
X?
(F3)
20 (hr + p +
+
20
(1+ (-
40
ptt-1
1+
x,
A
1
2
(F.5)
405
1 (ptt-119
Step 3: Analyzing the sum. We want to analyze the behavior the sum
S(3) = Σ
(Bir)2
(EZ(n))
for 3 = p++ 0. We first obtain the trivial bound
S(B) 2 [Z(m)
+ (Bna)²
Moreover, we can bound
1(m)
5(3) Σ
+ (Berga
1=1
and distinguish three cases:
37

---

(a) If 3 2 1, we bound
[(m]
1
(( 2
2
2(329)2
2,3
1=1
(b) If 3 E (7(m)=9,1) 1), we observe that
J(B) = 18- 1/9
2
[3
1/07
12
1
[
3-1/9
2
2
and therefore
J(
J(
J(B)
8 1/9
S(B) N Σ
2
1+ (B19)²
2
4
==1
(c) If 3 E (0, (0, we similarly find that
Kn)
1 T(n)
5(3)
Σ
1+1
i=1
Moreover, there is an absolute constant ci such that for any 0,
S(B) 2 C min [(n)),
(F.6)
because
(a) g-2 = min ( g-1/4 1/4 [(m]] for 3 2 1,
3-1// (b) 3-1// min(B-",8-110, [m)] for 3 E (I(n) and
(c) [(n) = min[{32,,8-1y) [[m]] for 3 E (0, (mm)-9).
Step 4: Putting it together. Combining the trivial bound in Step 3 with Eq. (F.4) and Eq. (F.5), we obtain
o²
En Rr(xxxxt - Rp 2
Σ (EI(N)
ExS:(X)
405 S(9)
S(9)
[(n)
2
(R7)
1 (p (p
) nm
n
for suitable constant d' > 0 depending only on and C. Moreover, from Eq. (F.6,, we obtain
5(3) 2 & min (3 2, , 1/1, [(n)] 2 z" min ((p + (p+t-) 1111// T(m)
for a suitable constant č" > 0 depending only on c. Again, (F.4) and (F.5) yield
En Rpp > x² 1
S(3)
4C5
(p (p+t-))2 (p (p+ ((n)
o² min
405
n
n
F.2 Equivalences of norms and eigenvalues
Later, will concentration inequalities for kernel matrix eigenvalues proved for specific kernels, which we then want to transfer to other kernels with equivalent RKHSs. In this subsection, we show that this possible.
Definition E.4 (C-equivalence of matrices and norms). Let > and let K, K gux= be symmetric. For C 2 1, we say that K and K are C-equivalent their ordered eigenvalues satisfy
C- (=K) A,(K) ())(K)
for all E In]. Moreover, we say that two norms || |A. || [| on vector space are C-equivalent
C ||ol|a & || l - Cl|ol|A
for all v E V.
38

---

Lemma F.5. Let 2 1 and let K, K E = be symmetric. Then, K and K are C-equivalent iff the Moore-Penrose pseudoinerses K* and K" are C-equivalent.
Proof. This follows from the fact that if K has eigenvalues Ai...., An, then K+ has eigenvalues 1 1/A1,.... ......... 1/An, where we define 1/0 = (A detailed proof would be bit technical due to the sorting of eigenvalues.)
Lemma F6. Let k X x X + R be a kernel on a set X. Then, for any E R",
yTk 1XX
where Hy is the RKHS associated with k and fk is the minimum-nomm regression solution
Fk argmin |1
JEB
10 (((a))- w1)) (1))== inf ( 23
B U=EE Ha.
SEAN i=1
Proof. is well-known that (x) = Eis osk((r, where a = K y (see e.g. Rangamani al., 2023). We then have
I 1:21s
Σ aak 1),
(a,k(oz,)) j=1
K 1503
H4
==
-y KKKK"K' y y
where the last step follows from a standard identity for the Moore- Penroee pseudoinverse (see e.g. Section 1.1.1 in Wang et al., 2018).
L
Lemma F.7. Let H4 and H2 be two RKHSs with Hi H2. Then there exists constant C > 0 such that Ilf Im S fll
Proof. Let I H1 H2 be the inclusion map, i.e. In = h for all h E Hi. Obviously, I is linear
and we need to show that I is bounded. To this end, let (h,)n21 C Hi be a sequence such that there exist h E H4 and g E H2 with h, h in Hi and Ih, g in H2. This implies h, h pointwise and ht, = Ih. + pointwise, which in turn gives g. The closed graph theorem, see e.g. (Megginson, 1998, Theorem 1.6. 1)), then shows that / bounded.
Applying Lemma F.7 twice shows that RKHSs Hi and H2 with Hi = H2 automatically have C- equivalent norms for suitable constant C 2 The following result investigates the corresponding kernels.
Proposition F8 (Equivalent kernels have equivalent kernel matrices). Let k. X'x IR be kernels such that their RKHSs equal sets and the corresponding RKHS-norms are C-equivalent as defined in Definition F.4. Then, for any n 2 and any T1...., In E X, the corresponding kernel are C equivvleett
matrices (X,
Proof. Let i [n]. For y E Rdd we have, using the notation of Lemma F.6:
ll 2 C 2-2115 lir 2 C -1. 12 C - X)+y.
Now, by the Courant-Fischer- Weyl theorem,
x((((xx))t)
sup inf V:dim veV:lllll y T X)+
2 C
sup inf y ((xxX))t Vidim V=i vEVilllll====
c > X)+).
By switching the roles of ls and i we obtain that & X, x) and ix x)* are C2 -quiivvall By Lemma F.5 k(X, X) and (x(X (XxX) X) then also C equivalent.
39

---

To prove Theorem 6 for arbitrary input distributions Px with lower and upper bounded densities, we need the following theorem investigating the corresponding eigenvalues of the integral operator.
Lemma F.9 (Integral operators for equivalent densities have equivalent eigenvalues). Let k X'X R be a kernel and let be finite measures on X' whose support is X' such that v has an lower and upper bounded density w.r.l μ.. Then, (T(T,.u) ()), (T)
Proof. Letp p be such an upper bounded density, that is, dv = dd and there exist c, C > such that S p(z) C for all X. For L2(v), we have
/ 13 du du sc Ppdu=C pdv= CI
llp. All
Hence, the linear operator
A: L2(() - 1
is well-defined and continuous. It is also easily verified that A is bijective. Moreover, we have
(Af, Af) = / PV Pu du 20 Ppdu= = c / fdv= = =c(f.))aaw)
and
1 (())) x') (a)((a'))(aaa)) du(a))d((aa) du(a')) (oo(a'))=0 (AS, A/)
( UTTTROlLLM
Since Tk. and TK. are compact, self-adjoint, and positive, we can use the Courant-Fischer minmax principle for operators (see e.g. Bell, 2014) to obtain
(T.T
(TTR.
max VC Lu())) subspace SEV\()) dim V=i
min
(f. L'
(AS, TR.n Af)
min L2() subspace feV SEV dim V=i
max
(AS, AS))
(g. (w. 12(1))
min VC Lo(v) subspace vEV)(0) dim V=i
max
{g. 9) Lz(n)
Here, have used that since A is bijective, the subspaces AV for dim(V) are exactly the i-dimensional subspaces [2)) Our calculation above shows that >; I ((T,(T..))) Since du p du with the lower and upper bounded density 1/p. we can reverse the roles v and μ to also obtain A:(Tk.u)= ((),T))))) which proves the claim.
Lemma F.10 (Integral operators of equivalent kernels have equivalent eigenvalues). Let k, ke X X -> be bounded kernels with RKHSs and H satisfying H = H as sets. Moreover, let C> 1 be constant such that the corresponding RKHS-norms are C-equivalent and let v be finite measure on X. If there exist constants g > O and e > with
121,
then also have
S C² Kg 19
i 121,
where Kg O is constant only depending on q.
Proof. We follow the ideas outlined (Steinwart, 2017, Section 3). To this end, let Tr, + (u)(v) be the embedding h + [A]_., which is defined and compact since l is bounded and v is finite, see e.g. (Steinwart and Scovel, 2012, Lemma 2.3). We write Sk := 1ī.- for its adjoint, which in turn gives J = - Then (Steinwart and Scovel, 2012, Lemma 2.2) shows Tk. S o Sk..- denote the i-th (dyadic) entropy number of JR., by ex ei(Tk.)), see e.g. Carl and Stephani (1990), (Edmunds and Triebel, 1996, Chapter 1.3.1), or (Steinwart and Christmann, 2008, Chapter 6) for
40

---

definition'. Moreover, we denote the i-approximation and singular numbers of IN.v by a; ai(Iue)) respectively s; (.x.)). Since I compactly acts between Hilbert spaces, we then have a, (I si(Tk,)), see e.g. (Pietsch, 1987, Chapter 2.11). This implies
A₂ (T&..)) a² (Ia.))
(F.8)
for all by the very definition of singular numbers. Finally, analogous definitions and con- siderations are made for the kernel k. From C-11|- 11x s ll ll S C l1x we then conclude that
C S ( S Cei(Luu),
i 1,
(F99
by the multiplicativity of entropy numbers, e.g. (Edmunds and Triebel, 1996, Chapter 1.3.1). Now, (F.8) and eigenvalue assumption yield
aT(Tt.)) S Vo.1-9/2
12 1,
and Carl's inequality, see e.g. (Carl and Stephani, 1990, Theorem 3.1.1) then gives
e: ei(Iu.)) S Ve- Kg i-
i2 1,
where Kg is a constant only depending on By (Carl and Stephani, 1990, Inequality (3.0.9) and (F.9) we then obtain
a, a,(4i,u) S (e;( S ( s 20 R 4/2 9//2
i i2
Another application of (F.8) then yields the assertion for Kg = 4K2.
F33 Kernel matrix eigenvalue bounds
For upper bounds on the eigenvalues of kernel matrices, we use the following result: Proposition F.11 (Kernel matrix eigenvalue upper bound in expectation). For m. 2 1, we have
Ex
Aa(k X)/n)
Ar(Tk))
(K.10)
Proof. Theorem 7.29 in Steinwart and Christmann (2008) shows that
E E
Σ XT & Σ (TTT.u)
(F.11)
where Th. I2(μ1) L2(1), J (fx)))(()) du(x)) is the integral operator corresponding to the measure μ and Tg,D the corresponding discrete version thereof. We set μ Px and need to show that ko X, X)/n has the same eigenvalues as TE, if D and X' contain the same data points B1,..... En. Consider a fixed Then, we can write T = n ABB, where
A Rd L2(D),
Σ ,;((
B L2 + R"
f(x.))
Then, x(X,X) is the matrix representation of -1 BA with respect the standard basis of I... But AB and B.A have the same non-zero eigenvalues, which means that
X(K(X,X)/m
Σ (TTT.))))
from which the claim follows.
Usuallyy dyadic entropy numbers are denoted by ec(.). but since this symbol is already used for eigenfunc- tions, e-).) instead.
41

---

To obtain a lower bound, we want to leverage the lower bound by Buchholz (2022) for certain radial basis function kernel with data generated from an open subset of R However, we want consider different kernels and distributions on the whole sphere. The following theorem bridges the gap by going to subsets of the data on a sphere cap, projecting them to Rd and using the kernel equivalence results from Appendix F.2:
Theorem F.12 (Kernel matrix eigenvalue lower bound for Sobolev kernels on the sphere). Let k be a kernel on Sd such that its RKHS H. is equivalent to a Sobolev space ( with smoothness >> d/2. Moreover, let Px be probability distribution on 3 with lower and upper bounded density. Let the rows of Raxd are drawn independently from Px. Then, for (0, 1/20), there exists constant 0 and E N such that for all no.
Am X, X))n) 2 en 2s/dd
holds with probability 2 4/5 for all m E N with S m S (1 11E)n.
Proof. We can choose a suitably large sphere cap such that Px (T) 2 21 E. Define the conditional distribution Pr(()) = Px (-I)). Out of the points X = (æ1...... ). we can consider the submatrix XT = (Z,,...... Biy _ of the points lying in T. Conditioned on N, these points are i..dd samples from Pr. Moreover, by applying Markov's inequality
Bernuulli distribution, we obtain N Z (1 (1-100 (1=10 with probability 2 9/ 9/10. We fix value of N 2 (1 - 10 in in the following and condition on it.
We denote the centered unit ball in Rdd by B1 (IR).. Using a construction as in Lemma E.1, we can transport and Pr from T to the unit ball B1 (Rd) using a rescaled stereographic projection feature map é, such that we obtain kernel KG and distribution Pa (Pr)s B1 (R2) that generate the same distribution of kernel matrices of X e (Xx) are i.i.d. samples from Pg. Moreover, we know that Ps has lower and upper bounded density w.r.t. the Lebesgue measure B1 (R.).
with Pr, and such that Hr. = H7 BB (TE The rows
In order apply the results from Buchholz (2022), we define a translation-invarian reference kernel on Rd through the Fourier transform
(g) (1 ((13)
see Eq. (3) in Buchholz (2022). The RKHS of kref on Rd is equivalent to the Sobolev space H (IR.). Therefore, the RKHS of krofl B, (R"), is H (B, (R))), ef. the remarks in Appendix B. and Lemma F.7.
Now, let 1 < m S (1 - 11s)n, which implies
1 < m S (1 - 11s)n S (1 - s1 - 10e)n S (1 -)NN.
We apply Theorem 12 by Buchholz (2022) with bandwidth y = 1 and a = 2s to Am and obtain with
probability least 1 2/N:
N2(a--8/4 (N m) d)/dd// + +1) s c3 (eN)iaa-)/e +1
(2(a-d)/d
Am Okree (X p. xx))
< c3
s <n 1)
as long as N is large enough such that (1- < N - enough. Here, the constant from Buchholz (2022) does not depend on N or m, but only on o, d, and the upper and lower bounds on the density, which in case depend through the choice of T. Since = 2s > d, we have n a/d-1 > 1 and therefore
32 In(),,,, which is the case if n is large
Am (Kref X X xn) 2 can afdd c5n 2s/d
Now, we want to translate this the kernel k. Since the RKHSs of kg and kyef B (TR.) are both equivalent to HB, (Rd)). the kernels themselves are C-equivalent for some constant C' > 1 as defined in Definition F.4. Therefore, Proposition F.8 shows that the corresponding kernel matrices are C- -e-equivalent, which implies
xn)/n) 2g 2n 2s/d
42

---

By Cauchy's interlacing theorem, we therefore have
Am (k. X)/n) 2 (m (X X x = (k. X x))/n) 2 csC' 22/d
Denoting the event where Am (ki. (x, X m)) 05 2 22/d by A, we thus have
9
P(A) = P(AN 2 (1 10 P(N 2 (1 10e)m) 2 P(AN 2 (1 - 10e)m)
10
9
Σ
P(N NIN 2 (1 PA N)
Ñ 10c)m]
9
P(N = NIN 2 - 10c)m)(1 (122)
10
1=1(1-10))n
n Σ
1
P(N= NIN 2 10e)m)
10
(1 - 10
[=(((-10e)a]
1
10 (1 10
5
where the last step holds for sufficiently large n.
F.4 Spectral lower bound for dot-product kernels on the sphere
An application of the spectral generalization bound in Proposition 5 requires lower bound on cigenvalues of the kernel matrix k, (X,, X). To achieve this, we need to understand the properties of the convolution kernel k, Since the eigenvalues of .P are the squared eigenvalues of Px one might hope that if H4 is equivalent to Sobolev space H then Hk. is equivalent to a Sobolev space H Unfortunately, this is not the case general, as Hr. might be smaller space that involves additional boundary conditions (Schaback, 2018) 8). However, perhaps since the sphere is a manifold without boundary, the desired characterization of H4. holds for dot dot-product kernels on the sphere:
.Px
Lemma F.13 (RKHS of convolution kernels). Let k be a dot-product kernel on gd such that its RKHS Hy is equivalent to Sobolev space H (S") with smoothness d/22, and let Px be distribution on Sd with lower and upper bounded density. Then, the RKHS Hi. of the kernel
k, : x gd + (x, = M(x x") x')dPx(z")
is equivalent to the Sobolev space (g))
Proof. Define
Ri anii (x. x') = M(z, x" kaa""" x²) (s"))
For the corresponding integral operator, we have
Th. ((34) T
k()))
This means that the corresponding eigenvalues are the squares of the eigenvalues of the corresponding integral operator of k. Especially, we obtain the Mercer representations
N
k(x,
14
(x,
1=0
oc
Ni,
k. ka (Iz, .z))
(z.
1=0
where Lemma B.1 yields μn = (((+1) 1)2o), hence of = @(1 + 1)-4r) and hence He. (gd))
43

---

Next, we show the equality of the ranges of the integral operators:
R(TRM(S4)) = R(Tx,Px)
Let px be density of Px w.r.t. the uniform distribution U(S"). f E R(Tru184)) there exists
g E (z()()))) with f = (B) But then, since px is lower bounded, we have g/px E (2x)x) and therefore
Px E R(TE,Px)
An analogous argument shows that P(Tx,Px) S R(T))) since px is upper bounded.
The equality of the ranges yields for the RKHSs (as sets)
H.s. unif (( = R(TR,Px) = =Hk,,
Applying Lemma F.7 twice then shows Hk. HH*).
Theorem 6 (Inconsistencyy for Sobolev dot-product kernels on the sphere). Let k be a dot-product kernel on S4, ie., a kernel of the form k(x, x²) x(( x.) x²)), such that its RKHS Hy is equivalent a Sobolev space (S*), Px has lower and upper bounded density w.E.t. the uniform distribution (( and such that Var(ylar) 2 o² > foror Px-almost all x E 34. Then, for every C. > O, there exists >> O independent of o² such for all 2 1, (C-1n22fd 28/d, ool, and E [0, On -22/dd), the expected excess risk satisfies
d/2. Moreover let P be a distribution on S R such that
EpRp(fe.)) Rp 2 0 >0
Proof. Step 0: Preparation. Since the Sobelev space (Sa) is dense in the space of continuous functions Sd + R. the kernel k is universal. Applying (Steinwart and Christmann, 2008, Corollary 5.29 and Corollary 5.34) for the least squares loss thus shows that is strictly positive definite. If we have mutually distinct ZI..... Ln. the corresponding Gram matrix l<( x;) [))){== is therefore invertible. Now, our assumptions on P guarantee that consists almost surely of mutually distinct observations, and therefore k [X XX) is almost surely invertible.
By Proposition 5, we know that
Ex XX, (1 -1- -0000((XXXXXXX/))))) (x) D)²
E [f
R2.
(X, (1- (0000,""
Ex
(Ilk(XXx)//1 On Cn-22/dj2
for a suitable constant Ca 0 depending on n but not on 0², t,, p. since the kernel matrix cigenvalues are nonzero almost surely. therefore sufficient show the desired statement (with independent of n, o², ,t, p) for sufficiently large
In the following, we assume 2 40 and set E = 1/100.
Step 1: Eigenvalue decay for the integral operator. From Lemma B.1, we know that
((TRu(S))) O(i (2/d).
Therefore, by Lemma F.9, know that
A.TT,,px) - (6/-///).
Step 2: Eigenvalue upper bound. Next, want to upper-bound suitable eigenvalues of the form (k(,(,, X)/n) using Proposition F. Using Step 1, we derive
2
Ar(T.,P) C
22/d < SO2
-2/d dx = 2-2//
t=m
i=m
m
44

---

with constants independent of m 2 1. For sufficiently large n, we can choose m E N21 such that en I 2=n. Then, Proposition F.11 yields
2c (r(Te) C3m I C4m2-2s/4
Ex (, X)/m)
1
t=
Since Ex X /n) is decreasing with i, we have for i 2 4en 2m: 2x/d S Co)r(Te,Px)
Ex (A(X, S Can' / Con-2sfd
Step 3: Eigenvalue lower bounds. From Lemma F.13, we know that Ha. = (S*) Therefore, we can apply Lemma F.13 to both and ki and obtain for sufficiently large n and suitable constants c1, c2 > 0 that
(,(,(,, X)/n) 2 an 22/d (=k /))n) c2n 1s/d
-ls/
individually hold with probability 2 4/5 for all E with sis (1-11(m) By the union bound, both bounds hold at the same time with probability 2 3/5.
Step 4: Final result. Now. using the value of m from Step 2, consider an index i with 2m S <i S (1 11 Since 2m I 4en and E = 1/100, there are at least n/2 such indices. By combining Step 3 and Step 1, we have
\ (Tx.(T.
(x, (X, ca)x(Tk,Px))
with probability 2 3/5. By applying Markov's inequality Step 2, we obtain
( X)nn) < 10C,Ar(Tk.Px)
with probability 2 9/10. Therefore, by the union bound, all three inequalities hold simultaneously with probability 1/2. Moreover, for q = 2s/d, we have (e(Te,,x) cz a by Step We can thus apply the first lower bound from Theorem F.2 to obtain
1
[(n)
Ep Rr Rp 2 d'
1+ (p+ 1 2)n2o/d
n/2
2 d'o²
1 1+ (Cn 2n/d + On Cn-22/d)n22//
02.
+ 20
G Proof of Theorem 8
Here we denote the solution of kernel ridge regression on D with the kernel function and regular- ization parameter > as
(²) = k(xx
(kXX kkr, X
pT) y.
and write (x) k(cc X)A(X, x)+y for the minimum-norm interpolant in the RKHS of k.
While Theorem 1 states that overfitting kernel ridge regression using Sobolev kernels is always inconsistent as long as the derivatives remain bounded by the derivatives of the minimum-nome interpolant of the fixed kernel (Assumption (N)), here show that consistency over a large class of distributions is achievable by designing a kernel sequence, which can have Sobolev RKHS, that consists of smooth component for generalization and spiky component for interpolation.
Recall that & denotes any universal kernel function for the smooth component, and ke denotes the kernel function of the spiky component with bandwidth y. Then we define the p-regularized spoky-smooth kernel with spike bandwidth ry as
kp (x, x²) = i(x x²) + (x, (x))
Let (x)x) = 1y dd
[ yl - t} denote the Euclidean ball of radius 2 around IRd.
45

---

(D2) There exists constant 0x > 0 and a continuous function Ø (0) + [0, 1] with e(0) = 0 such that Px (B)())) I ((t) = ((1x)) for all æ E f2 and all 2 0.
The kernel ky of the spiky component should fulfill the following weak assumption on its decay behaviour. For example, Laplace, Matérn, and Gaussian kernels all fulfill Assumption (SK).
(SK) There exists function : (0, oo) o0) [0, 1] such that for any bandwidth >> 0 and
any > 0 holds that
(i) E( 0) 1.
(ii) E( 5) is monotonically increasing in %
(iii For all æ, y E Q2 if |- y 2 then (x, y) S E(7, 8),
(iv) For any rates 8x 3x > there exists a rate By > such that, if ó, = 22(n (xx and Tn = O(n Pr). then E(T.. 6n) ((n=&)))
Theorem G.1 (Consistency of spiky-smooth ridgeless kernel regression). Assume that the training set D consists of n iidd pairs (x.y) ~ P such that the marginal Px fulfills (D2) and Ey²² < oc. Let the kernel components satisfy:
k denotes an arbitrary universal kernel, and Pn. - 0 and r.p + c0. 00.
hnn denotes a kernel function that fulfills Assumption (SK) with sequence of positive bandwidths (7hx) fulfilling 7/n O(exp(-Bri) for some arbitrary B >
Then the minimum-norm interpolant of the Pr pegreaularized spiky- kernel sequence kn kipn. is consistent for P.
Remark G.2 (Spike handwidth scaling). Under stronger assumptions on & and E in assumptions (D2) and (SK), the spike bandwidths in be chosen converge to much slower rate. For example, if choose k. to be the Laplace kernel, choosing bandwidths 0 < Ytu Blnn yields, for
8
separated points x y 2 5,
(-o² 7/
ky (z. v) S cxp
n
For probability measures with upper bounded Lebesgue density, we can choose 8, n 2 and 3 = 4
9 + 2 for consistency or 8 = 11 for optimal convergence rates, for any fixed a: > 0, in
the proof of Theorem 8. Hence the Laplace kernel only requires slow bandwidth decay rate of
In Ω
where >> 0 arbitrary. For the Gaussian kernel an analogous argument yields
[n(
4+20
7n Ω
The larger the dimension d, the slower the required bandwidth decay.
In(m)
Remark G.3 (Generalizations) If one does not care about continuous kernels, one could simply take Dirac kernel as the spike and then obtain consistency for all atom-free Px. However, we need a continuous kernel to be able to translate it to an activation function for the NTK. Beyond kernel regression, the spike component k, does not even need to be a kernel, it just needs to fulfill Assumption (SK) similar decay criterion. Then estimator's + (K- prkk,.) ) (x, X) (K + P, ,,,), +
could still use the 'quasi minimum-norm
Remark G.4 (Consistency with single kernel function). Without resorting to kernel sequences as we do, there seems to be no rigorous proof showing that ridgeless kernel regression can be consistent in fixed dimension. In future work, can analytical expression of such kernel be found? According to the semi-righ cemi-rigorous results Mallinar et al. (2022) a spectral decay like d = O(k log" (k)). could lead such kernel.
Proof of Theorem G. Given any universal kernel, (Steinwart, 2001, Theorem 3.11 or Example 4.6) implies universal consistency of kernel ridge regression if p.. - 0 and npt co. Hence, for any
& >> O holds that
lim pd (DE X R)" RP(f Rp(ff) = Eg (F 2 (E/2)²) =
12 12000
Due to the triangle inequality in L2 (Px), know
= (fp) Ex (ftt (x) fx())
46

---

((Ra (z)) fbr. (1)))²) 1/2 + (B (BolS (z)) (m) [)(x))))) ( 1/2) 2
It is left show that kn fulfills
lim P" ( ( +20000
Eg - (5 - (p (x))) 2 (c/2)²) = 0.
For this purpose we decompose the above difference into the difference of K y/n := koyn X) and || and the Euclidean
I and remainder term depending on kn... We denote the 2-operator norm by norm in R. by | I. For any x E R. it holds that
k(x, X): 1 (z) foxm (x) - (6 + Pakkn X): (K Pnr xn) --yaa
(K + pattn)
| x) (K + p kn) (K + pmtt)) y
+pn | (I,, () + +Pa PukKy (K,,)))
$ (k(x X)|| | + Pnn k,,,)~ 11.))-1-A -(K + Pp pn PnIn)-+11 1-1111111
+pn 11ky, (ze, x)11 |1( KK + pn K xxn.)-11 -1yl-
Consequently we get
E. (f fr. Em k(F, x|| +2 E l k (I. x)1 [|(K + Pn 1112 1/12.
| (K + P kg,)
(K + I,) [ 11y (G.1)
(G.2)
We now bound the individual terms in Eq. (G.1) and (G.2). To this end, fix any >> 0. Bounding Eq. (G.1):
Since we assumed y i.i.d and Eyy < co, the Markov inequality implies, with bn Byy n2,
Eyi bn
P(|y 2 bn S
Stated differently, with probability at least n na holds that |y/ s Ey² n 1+
In order to bound the spectrum of K Lemma G.7 implies that there exists positive sequence 2
5. (n)
Fx such that with probability at least 1 O(n=a) it holds that [ x, 2 (n).
min {
O(n-*) ()) for any B, > 0. by Assumption (SK) there exists a sequence en = o(p,n -2 8) such that s(7h, 8, (n)) S En. Assumption (SK) further implies that whenever ming,je | - æ,I 8 (n) it holds that (K,,).: = 1 and 0 < (K v,, )a S 6(7ng 8, (n)) S en for & j. Then Gershgorin's 's theorem (Gerschgorin, 1931) implies that for all eigenvalues of KT,.
Since (1h) fulfills 7n O(n
(,( - 1 S (n 1)en for all i e [n].
This in turn implies
[K,, To - -nlll S (n - 1)Ens
Amax (Kr.) 11+ (n - 1)ens
Amia (Ka)) 2 1 1 (n 1)
Using [[K + PP
Amin (K)mp I Pp and || ym -I (n L)E,, Lemma G.8 implies
||ck + Pn KrnK
(KK + (n
|1(K p., In)
11In)_11'3 -112 Pm K Inll
1 - ||KK + Pn II.) - Pa K In
Pr (n 1)en
1 (n - 1)5n
47

---

Using 11( x;) I 1 for all i E [ra] yields the naive bound [ S n.
Combining all terms in Eq. (G.1) yields its convergence to 0 as the product satifies the rate O(n*tap Pn 2 = o(1) with probability at least 2n na
Bounding Eq. (G.2):
The analysis below is restricted to the event of probability at least - 2n ", on which the bound on Eq. (G.1) holds.
Since (n 1)en + O. for any C it holds for n large enough,
Pu. II(K + Pn K Tm 51s Amin (K) Pn (n 1)En)
Pn
1)8,) SC
Finally we show sup ERE Eg Eyc (at, x²)² < 2n (2+a) for n large enough. Fix an arbitrary x' R.. Then by construction of (n) and en it holds that Ey (x, x²)² S 1. Px E Rdd hy,, (ær, x²)² 2 e..) + E
S Px E TR | r'1 < 6 (m))) + o
< (n)) ten S ((+aa + En
Since eh = o(pnn (0pppnnt10) 4-0), we get Eghi, (æe, x²)² - 2n (2+a) for n large enough.
Combining all terms in Eq. (G.2) yields its convergence to 0 with the rate O(n (2+=))+)).... n 2a) O(n-1) with probability at least 1 2n-a which concludes the proof.
The following theorem shows that the minimum- norm interpolants of the spiky-smooth kernel sequence can achieve optimal convergence rates for Sobolev target functions, as long as is properly chosen. We therefore introduce Assumption (D3), which resembles Assumption (D1) but allows more general target functions I* H² HH* (IIMO), s* >> that may lie outside of the RKHS.
(D3) Let = Sd or let Ω C Rd be a bounded open Lipschitz domain. Let Px be a distribution Q with lower- and upper-bounded Lebesgue density. Consider i.i.d. data sets D { (1),..... (In, Bn)} S Ω x R. where æ; Px, f (xx Elyla> xc] H (2))())
8" >> O, with ||["|| < Ba for some constant B 0, Ey do and there are constants o, L >> such that
1 m
E yy
(x)
m
S
d² mm
for Px-almost all æ E Ω and all m 2 2.
The above moment condition holds for additive Gaussian noise with variance 0² 0. Hence Assumption (DI) is strictly stronger than Assumption (D3). The spike components ky, can also be chosen in Theorem G.I.
Theorem G.5. Assume Assumption (D3) holds and that the kernel components satisfy:
the RKHS H of k satisfies H 11 as sets with max(s", d/2), kn, denotes the Laplace kernel with a sequence of positive bandwidths (7n) fulfilling in 2 (14 + 2)) Inn) 1 where a >> 0 is arbitrary.
Then there exists constant C' > independent of n and there sequence (Pr) of order -n//((=*dpp such that the minimum-nove norm interpolant Jpn.in of the pu-regularized spiky-smooth kernel sequence kin = kp fulfills, with probability at least -(1ha),,, for n large enough,
Rp(Soam Rp(s*) C - (n)..
Proof. Step 1: Kernel ridge regression fi. with optimal regularization achieves the desired convergence rate, with high probability.
We slightly modify the proof of Theorem Instead of using (Steinwart, 2001, Theorem 3.11 1. or Example 4.6), we use results of Fischer and Steinwart (2020). Here we first note that in the case
48

---

H. ( R' as RKHSs, we could directly use (Fischer and Steinwart, 2020, Corollary 5). Since we only have equivalent norms and also want to consider f2 = $ see Lemma F.7, we need to resort to the underlying more general result (Fischer and Steinwart, 2020, Theorem 1). To this end, we first need to verify its Assumptions (EMB), (EVD), (SRC), and (MOM).
Verifying (MOM). The moment condition (MOM) on the noise distributions holds since we assumed in Assumption (D3).
Step 1.1:
Step 1.2: Simpler equivalent spaces, We verify the remaining conditions by analyzing them for a nicer equivalent RKHS H. and with uniform distribution on f2. For the non-spherical case St C R we choose H = H (S2). For the case Q S", we choose H. as an RKHS associated to a dot-product kernel with μ4 = @(( + 1)-22), such that H = H = H by Lemma B.1. In each case, H. = H with equivalent norms, and L2(1)= L2(xx) with equivalent norms since we assumed in (D3) that Px has an upper- and lower-bounded density.
Step 1.3: Verifying (EVD+). It suffices to verify the eigenvalue decay condition (EVD+) for H and v. since Lemma F.10 and Lemma F.9 then allow to transfer it to H. and Px.
For Ω S R&d as pointed out in front of (Fischer and Steinwart, 2020, Conollary 5), it is well-known that H. satisfies the polynomial eigenvalue decay assumption (EVD+) for p== d. 2.'
For Ω =S, our definition of H. together with Lemma B.1 directly yields (EVD+) for and v with d 28
p =
Step 1.4: Verifying (EMB) and (SRC). The remaining two conditions of (Fischer and Steinwart, 2020, Theorem 1) are stated in terms of so-called power spaces, which in turn can be described by interpolation spaces of the real method. We therefore quickly recall these spaces. To this end, let us assume that we have two Banach spaces E and F such that F C E and the corresponding inclusion map is continuous. Then the so-called K-ffnctional of an x E E is defined by
K(x, 1, E, F)
inf (4]lv]| + || yl1=), #EF
1>
For q E (0, 1) and E then define
( 1-20-1 (
||
and [F, Fl,2 == fo E F: ||=1|1,22 < oo). Let us now consider the cases (F,, F) = (T2( H) and (E, F) (Lz(Px), H).. Now, for suitable constant C, H and H. are C-equivalent, and L2(v) and (2(Pa) are also C-equivalent. We then find
C- ((,,(f,,,L)))) H) S ((f,,,L2(90) H) S CK(f,t, H)
for all L 0 and f E L21),, and consequently we have
[La(v), H],,2 [L2(Px), H)q.2
for all g E (0, 1) with C-equivalent norms. Now, (Steinwart and Scovel, 2012, Theorem 4.6) shows that the power space [H]] defined in (Steinwart and Scovel, 2012, Equation (36)) satisfies
[H] [L2(M), H/
with equivalent norms, and an analogous result true for H and Px. Moreover, H. is dense in Lz(v). and therefore (Steinwart and Scovel, 2012, Equations (36) and (18)) together with (Steinwart and
Scovel, 2012, Lemma 2.2) show [7[]]- = Le(v) as spaces. Again, we analogously find [70 =
(2xxx) Consequently, for all 0 S q < 1 we have
[H]
[7
with equivalent norms. From this we easily deduce that the Assumptions (EMB) and (SRC) are satisfied for (H, Px) if and only if they are satisfied for (H, v).
Step 1.4.1: Non-spherical case. Now, let Ω C Rdd Then, (EMB) and (SRC) are satisfied for (H, v) for 3 5²/s and an arbitrary but fixed a E (p, min(1,y (1,p+ B3) as outlined in front of (Fischer and Steinwart, 2020, Corollary 5). Applying Part ii) of (Fischer and Steinwart, 2020, Theorem for
49

---

0 then shows that there exists a sequence (PN)NEN of order n =/(s=/////)) and constant K₃ > independent of such that, for n large enough,
0
ud (D (12 x R)) Ex (J. (x) (x))) Kin Fe lng)(n) S 4n (G.3)
Step 1.4.2: Spherical case. Suppose Z = @d. Using the differently normalized spherical harmonics Y2, and Vi, from Appendix B.3, we obtain for the power spaces:
Nea
[H]]
amp; 0/2 2 Di.
(an) E l2
Ni.
ala(l + 13 [Yi,l (ar) E l
NLa
Nia
bi +1+ 1)200
< 00
}
1=0
(S*)
where the first equation follows from (Steinwart and Scovel, 2012, Eq. (36)), the second one from our definition of the μi in Step 1.2, and the last one from (Hubbert et al., 2023, Section 3). Again, we can choose an arbitrary but fixed that [H]] = Has is an RKHS with bounded kernel (De Vito et al., 2021, Theorem 8), hence the embedding condition (EMB) holds. Similarly, (SRC) holds for B 8 and the result follows as above.
(p, min p+ B}). Then, as > ps d/2, which means
Step 2: for and fü. close in L2(Px), with high probability. 5' [d*+d/2] < 1, it suffices to show that kn fulfills, for some constant K₂ > 0,
Since
pm (D E (Rd x R)"
E_ (f (x) fh. (x))² 2 K2n ) < 2n -a
(G.4)
9) In 1ammm)"". holds that 1k (xx, y)1 S En = P.n - (cf. Remark G.2). Then the product of all terms Eq. (G.1) satisfies On 4+a Pm 2 En = o(n with probability at least
Since 7n S -n- (1
1 2n -a On the same event, the bound Eq. (G.2) remains of order O(n-²), which shows Eq.
(G.4). Combining (G.3) and (G.4) with the triangle inequality in L2(Px concludes the proof. O
Remark G.6 (Optimality of the rates). In the setting of Theorem G.5, can apply (Fischer and Steinwart, 2020, Theorrm 2) in order to obtain lower bounds on the achievable rates. We have already verified the conditions (MOM), (EVD+), (EMB), and (SRC) in the proof of Theorem G.5. In the case s* > d/2, we have 3 = / 8 >> (2s) and can therefore choose E (p, 8) such that B > a. Then, (Fischer and Steinwart, 2020, Theorem yields a lower bound on the rate of the form (with constant probability)
7 PTP = n
which matches the rates in Theorem G.5 up log terms.
G.1 Auxiliary results for the proof of Theorem 8
The distributional Assumption (D2) immediately implies that the training points are separated with high probability.
Lemma G.7. Assume (D2) is fulfiilld with Bx > 0. Then with probability at least 1 - OOn
21
min
a;;
xz 2 2x
i.jE(n)
Proof. For any E [n], the union bound implies
P( min JE(n]17j
| - x, S = P
U (o, Bo(x,))
jElnlsizti
50

---

Another union bound yields
P min
[ 1 50 S n(n 1))(6).
2 Choosing 8, (n) 5x yields (n)) = 0 ( (Ą..)))) which concludes the proof.
The following lemma bounds ||A B via ||- and ||A Bl|. Similar results can for example be found (Horn and Johnson, 2013, Section 5.8).
Lemma G.8. Let A, B E IRax" be invertible matrices and let || be submultiplicative matrix < 1, then it holds that
norm with |n 1. If A and B fulfill A
A B
||
A 1| A B
|B - A-
1 <
A
| B
Proof. Because of | (A- B| & A |||| A B| < 1 we get
| A A (A B)
A A Bl|-
Writing B=A(I -1 (A B)) yields B- = (I - (A 11-Bi B)) 'A which implics
||~
B
1 | | |||||| A B|
Now write B
- A A B get
1|
S |
|||| |
B B-
Combining the last two inequalities concludes the proof.
G.2 RKHS norm bounds
Here we show that if & and k., have RKHS equivalent to some Sobolev space 11", d/2, then the RKHS of the spiky-smooth kernel kp.y is also equivalent to H for any fixed p. > 0. Hence all members of the spiky-smooth kernel sequence may have RKHS equivalent a Soboley space H and are individually inconsistent due to Theorem 1; yet the sequence is consistent. This shows that when arguing about generalization properties based on RKHS equivalence, the constants matter and the narrative that depth does not matter in the NTK regime as in Bietti and Bach (2021) is too simplified.
The following proposition states that the sum of kernels with equivalent RKHS yields an RKHS that is equivalent to the RKHS of the summands. For example, the spiky-smooth kernel with Laplace components possesses an RKHS equivalent to the RKHS of the Laplace kernel.
Proposition G.9. Let Hi and H2 denote the RKHS of kı and lz respectively. If the RKHS H of = k1 + k2 fulfills H. = H4, Moreover, if C 2 is a constant with 1 Il & CII then we have A 1111l, S [1 < ||
H2 then
C fllfll, S
Proof. The RKHS of k = K1 + h2 is given by H H, + H2 with norm
|| = min (I.f1 2. + 12 / - f2, fi E H1, E H2)
To see this we consider the map + X Hi x H2 defined by ((x) = (#, -), Φ2 (z. -)) for all X, where the set, the spaces H. live on and Φ;(x)) = k2 (, :). The reproducing property of hi and kn immediately ensures that t is feature map of kn + hi and Theorem E.3 then shows
H. = (w, 4 ((-)) Hi HH
H. H22
(w1, L (1))). (wy, 12(.)) wi H1,w0, H2) = H1 + H2
as well as the formula for the norm H. Now let f E H. Considering the decomposition f f1 +0 then gives |lʃ l I ||] Moreover, for ʃ fi f2 with fs Hi we have
I|, < f1,, + Ilfell,, I 1, + Cllfelln, S (2C(1 + llfalle,,) 1/2
Taking the infimum over all decomposition then yields the estimate || S 2201ffllx
51

---

H
Spiky-smooth activation functions induced by Gaussian components
Here we explore the properties of the NNGP and NTK activation functions induced by spiky-smooth kernels with Gaussian components.
To offer some more background, it is well-known that NNGPs and NTKs the sphere S are dot-product kernels, i.e., kernels of the form ku x') x((2, [2, x') x²)). where the function A has series representation x(t) Ei=o b,t' with b; 2 0 and Σ b3 cc. The function is independent of the dimension d of the sphere. Conversely, all such kernels can be realized as NNGPs or NTKs (Simon et al., 2022, Theorem 3.1).
As dot-product kernel k(r,, y) xa( (ar, y)) the sphere, the Gaussian kernel has the simple analytic expression,
2(z (2(=-1)
Gauss exp
Mey
7
with Taylor expansion
Kiy
Gause
(2)
exp( 22/7) 2²
1=
For spiky-smooth kernels = ke + pky with Gaussian components i and k, of width ÿ and ? respectively, get Taylor series coefficients
exp(-2/5) b; i!
2 exp(-22/) (2)
(H.1)
i!
Now Theorem 11 states that as soon induces a dot-product kernel for every input dimension then the dot-product kernels can be written as the NNGP kernel of a 2-layer fully-connected network without biases and with the induced activation function
t xN))P(T) = Σ 8 1/2 hx)),,
or as the NTK of a 2-layer fully-connectio network without biases and with the induced activation function
1/2
TTK (x)
Σ 1=0
8i
bj
hx(#),
where h; denotes the i-th Probabilist's Hermite polynomial normalized such that ||/s|le = and 8; (-1,+1) are arbitrarily chosen for all i E No-
Now we can study the induced activation functions if we know the kernel's Taylor coefficients (be ).N, If infinitely many b, >> O. then infinitely many activation functions induce the same dot- product kernel, with different choices of the signs s;. For alternating signs s; = (-1)², the symmetry property h:(-2) = (x)) of the Hermite polynomials implies
ØNNGP, (x) = dNNOP, (-xx,
ΦNTK (x) ΦNTK, (-x).
To form an orthonormal basis of (2,N( 1)) the unnormalized Probabilist's Hermite polynomials He; have to be normalized by hx(x)) = vo (e) We can use the identity exp(xl - 5 =
Ee ( with t= 227 to analytically express the NNGP activation of the Gaussian kernel with all s; -1 as the exponential function
2
hx(x) = exp ( 2
Gaues ONNGP. (x) exp(-1/1)
(H.2)
Remarkably, the Gaussian kernel can not only be induced by an exponential activation function, but also by single shifted sine activation function. This is shown in the following proposition.
52

---

Proposition H.1 (Trigonometric Gaussian NNGP activation functions). For any > O and the bi-alternating choice of signs ((-1) the Gaussian kernel of bandwidth y can be realized the NNGP kernel of two-layer fully-connected network without biases and with activation function
Gause PNNGP.+ (ar) = sin((iin((/))))))) cc0((//)))))))
Proof. We write 2/7. We need to show that
- 1))1//2 ea/2
sin(c + cos(c!/22)) = -0/2
i! Hc((z).
1=0
We will use the fact that
2 2²
H((x),
with the choices 21 = i/c/2 and c/2 c/2. Now, using e gaaxtb = cl(cos(ax) + ssi((az)). observe that
sin( (cx) = sinsssinnnsssieie //0///////// (22 = 2iee/2
( - ee
(iVe/2)
- (((e/22(1-(-111))
22
i!
c/2)2i+1
=/- 2/2
(2i 1)!
An analogous calculation yields cos(
D6 -0 Σ 1)
2/)222
1122 cos(c
H2,(1/ V2).
(2))
1=0
Finally, using H+(x/v2) 21/2 22/2)1e;(z), we get
20 (11111/2] (c/2)//2 Hx(x/v2)
sin(c2/22)) + cos(c2 6/2 6/2
i!
2/2
= -0
(-1)
11/2)
/! He,
1=0
For ΦNNGP(*) = E si (z),, we get 1l = Σ b, invariant to the choice
fsihien For Gaussian NNGP activation components with bandwidth > 0 this yields
Gauss | IoNNGrlli
exp(-2/1)
=1, =1
(H.3)
because tiiti is an ONB of (2( 1)). Analogously, for Gaussian NTK activation components, get
(2)
Gauss (I exp(-2/7)
Σ
(i + 1)!
77
exp(--2/7)
7 2 1!
Σ
2
7 1 1-exp exp (-2)
(H.4)
2
This implies that the average amplitude of NNGP activation functions does not depend on 7, while the average amplitude of NTK activation functions decays with - 0.
53

---

By the fact (x) = /nhnn1(x),, we know that any activation function 6(x) Ei=o i=0 s,a;h;(2) has the derivative o' (((x) = Ei=o 8:0--1vi+1 I (x) as long as Li=o | < oc.
The following proposition formalizes the additive approximation of 2 o² 11/200 and quantifies the necessary scaling of y for any demanded precision of the approximation.
Proposition H.2. Fix 7: p > arbitrary. Let k = k + phiy denote the spiky-smooth kernel where i and K are Gaussian kernels of bandwidth & and 7, respectively. Assume that we choose the activation functions @NTK. dYTK and ΦNTK in Theorem 11 with same signs (SiLER. Then, for y > small enough, it holds that
+ 4 + 7)
11 - (DNNK + Tp-ONIR) Beoooo.1 221
3/2 exp
8 (1 + 4)
|1 (Øt (DNNOP + vp ( 2 12 exp
7/2
denote the Taylor coefficients the Gaussian kernel. All consid- ered infinite series converge absolutely.
Proof. Let = ..
NNOP - (ØNNGP + vp-
8: si bus + hib)) - Σ
si(v
si(Vbi,5 +
1=0
(bba + pban - (Vbig + vpbin)) ?
< 2 Σ
(Vbia pbin - 11/2/2 +2p
04,5
bi +2 Σ
(Vbig +
pbb,
+2
Σ
6i.99
k=
1=1+1
i=
(T)
(IT)
(111)
(1V)
for any I E N. To bound (I) observe
Σ (vbb + pbin 61/212 Σ
pbio
pbi, + 22b,44
1- 1
p
bi.
by.5
An analogous calculation for (II1) yields
8
8
Σ
(vbs + pbin- -p 11/201/2332 < Σ
i=1+1
So overall we get the bound
2
N - (ØNNOP + 1p-oxNaplllswwo...
S 4p Σ
bin + Σ
6
(H.5)
1=
i=1+1
Now, defining c== 127,,,
P([+1,c) c
bin = exp( -c)
I!
k=0
where [[k: + 1, denotes the upper incomplete Gamma function. Choosing I
1 (Pinelis,
2020, Theorem 1.1) yields, for c 2 121,
[(I + 1,c) S exp((-) (c+ (I + 1)1//1144 1II (1+ 1)1/7
S exp(-c)(c+ 1
(1 1)!(+11/11
$ exp(-c)(c+ 1)
- 11)2//1 (L# (141)//T
54

---

1
- -c (7 + (1)++(((n((t+ 1) - In(1 + 1) + 1))
exp
V
/ +11
exp
-c+
c
+ +1](
In(
2 +
c) ln[ -
+ - +1)
Ve
2T
_ 1
exp
-cc+
- + (n(
c
+ 11+
exp ( - 5 Vē
(H.6)
Ve
2T
where we used + 1)! ] I for 1 3 in the first line, Stirling's s approximation in the second line,
and ( + (2 + 1) + v c/2 for e 2 121 in the last line.
It is obvious that
b - 0, for 1, 2m
+ 00.
To quantify the rate of convergence, we use the bound [ + 1, co) 2 2 co + 1)),
which follows from applying Jensen's inequality to [(I + 1, = /IE + m/G)), where G ~ r(I+ + 1, 1) and EG = I++1 1. Defining Co 2/5,, it holds that
M( + 1,)))
S - e -0 (1+
CD 1+11
(1 1+ T+1
Co
1+1
UiA 1
<1-e
I!
1=++1
Taking the first two terms of the Laurent series expansion of n + (1+ m))
about n oo yields
(1 +
1-1 > 60
for / large enough (where we demand E o((2)), thus 21+11)
1+1
1+1
(1+
b, 1 - -00
[1 1+11
(1
CO
1+1
1+1
co/ + 1) e/ /2/(2(1 1))
Cu
c
4T
4x
< I+1
(H.7)
1 co/ (1 1)
2(1 + 1)
πc
7²c
Plugging (H.6) and (H.7) into (H.5) yields, for 7 S 1/61,
(-1)
8 + 7)
1/2 exp I (ØNNGP + vp. (NNCP) 23 p/
+
7
7/2
For the NTK we get
10 1ONTK + Vo- (2xx))120(00111
bi, + pbin hx(2)) - Es; s; (v
20
big
pbin
V.
i+1
Wi+11
Vi+1
(VbL + pbin - (vb. + v Vpbe.)) 2
i+1
1=0
We proceed exactly as for the NNGP, but choose I = 2r
1 to get
bin exp(-c) Σ
exp(-c)
exp(-c/22 c3/2
exp(-c)
1
(i+1). 1)!
c
c
and replace (H.7) with
b,
exp(-co)
of 1
Ty(1 + +
Σ
Σ
i+1
Co
I+2 2)
3
1=12
55

---

I Additional experimental results
The code to reproduce all our experiments is provided in the supplementary material and under
spikes
Our implementations rely on PyTorch (Paszke et al., 2019) for neural networks and mpmath (Johans- son et al., 2023) for high-precision calculations.
L1 Experimental details of Figure 1
For the kernel experiment (Figure la), we used the Laplace kernel with bandwidth 0.4 and the smiky-smooth kernel (4) with Laplace components with p 1, 1, 0.01.
For the neural network experiment (Figure 1b,c) initialize 2-layer networks with NTK parametriza- tion (Jacot et al., 2018) 8) and He initialization (He et al., 2015). Using the antisymmetric initialization trick from Zhang al. (2020) doubles the network width from 10000 20000 and helps pre- vent errors induced by the random initialization function. It might also be helpful to increase the initialization variance (Chizat al., 2019). We train the network with stochastic gradient descent of batch size over the 15 training samples with learning rate 0.04 for 2500 epochs. Training with gradient descent and learning rate 0.4 produces similar results. We use the spiky-smooth activa- tion function given by x + (x) + 0.01 (sin( 100z) + cos(100z)), which corresponds to + (x) WNTK (z, 5000). including both even and uneven Hermite coefficients.
1.2 Disentangling signal from noise in neural networks with spiky-smooth activation functions
Since our smoky-smooth activation function has the additive form oppam (z) = ReLU(x) +
WNTK K (i;; 500n) ) can dissect the learned neural network
Sspsm(2)
W2 Sspsm (W, x + b1) + by fReL (ax) + (spikes(())
(I.1)
into its ReLU-component
(R) = W2. ReLU x ++bb b1) b2.
and its spike component
(x)
W2 WNTK W, x b 5000
If the analogy to the spiky-smooth kernel holds and fepikes fits the noise in the labels while having small L2-norm, then fRELU would have learned the signal in the data. Indeed Figure I. demonstrates that this simple decomposition is useful to disentangle the learned signal from the spike component in our setting. The figure also suggests that the oscillations in the activations of the hidden layer constructively interfere interpolate the training points, while the differing frequencies and phases approximately destructively interfere on most of the remaining covariate support. Figure I.2 shows some of the functions generated by the hidden layer neurons of the spike component fspikes- Both the phases and frequencies vary. Destructive interference in sums of many oszillations occurs, for example, under uniform phase distribution.
An exciting direction of future work will be understand when and why the neural networks with smiky-smooth activation functions learn the target function well, and when the decomposition into ReLU- and spike component succeeds to disentangle the noise from the signal. Particular challenges will be to design architectures and learning algorithms that provably work on complex data sets and determine their statistical convergence rates. A different line of work could evaluate whether there exist useful spike components for deep and narrow networks beyond the pure infinite-width limit. Maybe for deep architectures suffices to apply spiky-smooth activation functions only between the penultimate and the last layer.
56

---

a.
b.
Prediction
0.3
0.0
-0.
-1
smiky-smooth
Signal network
-1.0
-2
M/N
Angle (radians)
Angle (radians)
Figure 1.1: The -cepp--cm RRLL (blue) and the full spiky-smooth network Sspsm (orange) of the learned neural network from Figure 1. b. The spike component Sspikes of the learned neural network from Figure against the label noise in the training set, derived by subtracting the signal from the training points. Observe that the ReLLU--copooen has learned the signal, while the spike component has fitted the noise in the data while regressing between data points.
0.015
0.02
0.02
0.005
0.010
0.01
0,002
0.001
0.01
0.000
0.00
0,000
0.00
0.005
0..0
0.001
0..11
0.002
0.015
0.02
0.001
0.01
0.002
0.00
0.000
00002
0.02
0.004
0.015
0.006
0.002
0.01
0.010
0.003
0.001
0.005
0.000
0.00-
0.000
0.002
0.001
0.01
0.003
0.02
0.000
Angle (radians)
Angle (radians)
Angle (radians)
Angle (radians)
Figure I.2: Here we plot the functions learned by 12 random hidden layer neurons of the spike component network fapikes corresponding to Figure 1.
Of course an analogous additive decomposition exists for the minimum-norm interpolant fö of the spiky-smooth kernel,
[o (ke (xt, X). .).(0 (K Pn K y (signat(w)) + S (2:),
(1.2)
where
fsignat( = k0,x, X) (K pn K K (s))koo(()) pakin, (xx x). (K pn pna)a
We plot the results in Figure I.3, Observe that the spikes fspikes regress to more reliably than in the neural network.
Although smooy estimators can be consistent, any method that interpolates noise cannot be adversarially robust. The signal component fsignat may simple correction towards robust estimators. Figure 1.4 suggests that the signal components of smiky-smooth estimators behave more robustly than ReLU networks or minimum-norm interpolants of Laplace kernels terms of Umite-sample variance.
57

---

a.
b.
Prediction
0.3
0.0
-0.
-1
Spiky-smouth
Spsm signal
-1.0
-2
M/N
Angle (radians)
Angle (radians)
Figure L.3: a. The signal component fsignol (blue) and the full minimum-norm interpolant fo (orange) of the spiky-smooth kernel from Figure b. The spike component fepikes of the spiky-smooth kernel from Figure I against the label noise in the training set, derived by subtracting the signal from the training points.
1.3 Repeating the finite-sample experiments
We repeat the experiment from Figure 100 times, both randomizing with respect to the training set and with respect neural network initialization.
For the kernels (Figure 1.4a), observe that all minimum-norm kernel interpolants are biased towards O. While the Laplace kernel and the signal component (I.2) of the spiky-smooth kernel have similar averages, the spiky-smooth kernel has a slightly larger bias. However, both the spiky-smooth kernel well its signal component produces lower variance estimates than the Laplace kernel.
Considering the trained neural networks (Figure 1.4b), the ReLU networks approximately unbiased, but have large variance. The neural networks with spiky-smooth activation function as well as the extracted signal network (I.1) are similar average: They slighly biased towards 0, but have much smaller variance than the ReLU networks.
1.2
Prediction
Prediction
RMSE
Spiky smooth
Laplace Spily-smooth
RcLU Smikty
0.6
-1
Signal
Signal
-2
0.0
10P
10
108
Angle (radians)
Angle (radians)
Epechs
Figure 1.4: We repeat the experiment from Figure/ 100 times and report the mean values (lines). Confidence bands denote the interval between the empirical 2.5% and 97, 97.5%-qusssssss from the 100 independent runs.
The training curves (Figure I.4c) offer similar conclusions as Figure 1: While the ReLU networks harmfully overfit over the course of training, the neural networks with spiky-smooth activation function quickly overfit to 0 training error with monotonically decreasing test error, which on average almost optimal, already with only training points. The spiky-smooth networks have smaller confidence bands, indicating increased robustness compared to the ReLU networks. If the ReLU networks would be carly-stopped with perfect timing, they would generalize similarly well as the networks with spiky-smooth activation function.
1.4 Spiky-smooth activation functions
Figures I.5 and 1.6 we plot the 2-layer NTK activation functions induced by spiky-smooth kernels with Gaussian components, where & has bandwidth 1, and the first figure p while in the second figure p 0.1.
58

---

-2 -1
1.0
10
100
0.5
0.5
0.0
0.5
15-
15
-20
-25
26
Random
2
-5
-2
7
7
Figure 1.5: The 2-layer NTK activation functions for Gaussian-Gaussian spiky-smooth kernels with varying 7 (columns) with kmazz = 1000, 7: has bandwidth 1, = Top: 8; +1, middle: +. -...-..-0 t.... bottom: Random +1 and -. 1. Although the activation function induced by the spiky-smooth kernel is not exactly the sum the activation functions induced by its components, this approximation is accurate because the spike components approximately live in a subspace of higher frequency in the Hermite basis orthogonal the low-frequency subspace of smooth component.
1.0
300
0.0
30
0.0
-35
-35
1.0
2.0
-30
200
Randon
-5
22
-5
22
0.1
0.05
0.05
0.01
0.005
Figure L.6: Same as above but p 0.1. The high-freyuency fluctuations are much smaller compared to Figure I.5.
In Figure 1.7 we plot the corresponding 2-layer NNGP activation functions with p = In contrast to the NTK activation functions the amplitudes of the fluctuations only depends p and not 7 Our intuition is the following: Since the first layer weights are not learned in case of the NNGP, the first layer cannot learn constructive interference, that the oscillations in the activation function need to be larger.
The additive approximation d² ot 2 remains accurate in all considered cases (Ap- pendix 1.6).
59

---

-2 -1
2 -1
WMW
Figure 1.7: Same as above but NNGP and p= 1. expected from the isolated spike plots: Spikes essentially add fluctuations that increase in frequency and stay constant in amplitude for - 0, p regulates the amplitude.
1,5 Isolated spike activation functions
Figure 1.8 is the equivalent of Figure 3 for the NNGP.
By plotting the NTK activation components corresponding to Gaussian spikes &h with varying choices of the signs 8; in Figure 1.9, we observe the following properties:
1. All 8; +1 leads to exponentially exploding activation functions, cf. Eq. (H.2).
2. If the signs 8; alternate every second i, i.e. 8; +1 iff 1 even, &i is approximately single shifted sin-curve with increasing frequency and decreasing/constant amplitude for NTK/NNGP activation functions, cf. Eq. (6).
If 8; is chosen uniformly at random, with high probability, sh both oscillates at a high frequency around ( and explodes for [x| + co.
4.
b
Coefficient value
c.
0.2
1.0
0.5
0.1
0.2
7 0.07
0.04
0.5
0.05
0.1
0.02
1.0
0.0
125 150
Index
Figure 1.8: Same as Figure 3 but for the NNGP. In contrast to the NTK, the amplitudes of the oscillations in a. do shrink with 7 - Otherwise the behaviour is analogous. For example, the Hermite coefficients peak at 2/7. The squared coefficients sum to (Eq. (6)).
60

---

62-
WW
MMA
0.25
1.25
1.0
Kankm
-05
0.0
7
Figure 1.9: The spike activation components of 2-layer NTK for Gaussian spikes with varying Y (columns), kmaz = 1000, top: all +1, middle: signs alternate every second index, bottom: 3 draws from uniformly random signs. With y the amplitude shrinks, while the frequency increases.
Figure 1.10 visualizes NNGP activation functions induced by Gaussian spikes with varying bandwidth y. Observe similar behaviour as for the NTK but amplitudes invariant to as predicted by Eq. (6). For smaller the explosion of (all+) activation functions starts at larger x, but appears sharper as can be seen in the analytic expression (H.2).
Figure 1.11 resembles Figure 1.9 but plotted on a larger range to visualize the exploding behaviour for [x]] co.
10-
01100
0000
0.000
10-
Rundom--
22
-00
0.2
011
0.075
0.05
Figure I.10: Spike activation components as in Figure 1.9, but for the NNGP with between [-4,4].
61

---

11.03
0.007
0.891
0.00
0:35
0.2-
0.23
-02-
22
22
6.0
50-
Random--
2.-
20-
23
20
-00
Figure 1.11: Spike NTK activation components as Figure 1.9 but with x between [-4,4]. The all+
NTK activation explodes exponentially. While random sign activations explode as well, + + activations remain stable sin-fluctuations with slowly decaying amplitude for |ar| 00.
I.6 Additive decomposition and sin-fit
Here we quantify the error of the sin-approximation (8) of Gaussian NTK activation components. The additive decomposition Ø² = of + p²/²0f quickly becomes accurate in the limit - (Figures 1.12 and I.13), the sin-approximation seems to converge pointwise rate ((xrly), where a good approximation can be expected when | < 1/7. The error at large |xc arises because the spike component decays for |2|| oc. For (1) inputs, we conjecture that this inaccuracy does not dramatically affect the test error of neural networks when 7 is chosen to be small.
0.10
0
0,05
SIRI
-01
62
0.45
00.05
0..04
00002
70001
Figure I.12: The isolated NTK spike activation function (orange), the difference between spiky- smooth and smooth activation function (blue) and fitted sin-curve (8) (green). All curves roughly align, in particular for + 0.
0.00
6.0
M MA
ODI
M
ILIZ
MM
0:2-
0.2-
3:000
0:00
0
6622-
-000
0.64-
-0.1
-3.100
Sp621 SaI Isp
5p6d1 (581 156
0.005
0.04
0=0002
700.01
Figure 1.13: The error of the additive decomposition d² ~ of //2 of (blue) and the sin-fit (8) (or-
ange) for the NTK. While the additive decomposition makes emrors of order 10-3, 10-4, 10-9, 10-15 (from left to right) in the domain [-4, 4]. the sin-fit is increasingly inaccurate for |x]] - and increasingly accurate for 7 + 0.
Now we evaluate the numerical approximation quality of the sin-fits (7) and (8) to the isolated spike activation components d²², As expected by Proposition H.1, 1, the NNGP oscillating activation function
de of Gaussian spike component corresponds Eq. (7) up numerical errors. Both for the
NNGP and for the NTK, the approximations become increasingly accurate with smaller bandwidths
7 + (Figure I. 1.1.). Again the approximation quality suffers for | - oc, since PNrx slowly
decay to 0 for [x] +
62

---

a.
b.
Absolute error
10"
10-"
10
10
n 0.075
10-1
0.05
0.04
0.025
0.01
-2
-2
2
NNGP
NTK
Figure I.14: Absolute numerical enror between the oscillating activation function @t of a Gaussian spike component and its analytical expression Eq. (7) for the NNGP and b. the approximation Eq. (8) for the NTK with varying bandwidth
1.7 Spiky-smooth kernel
selection
To understand the empirical performance of spiky-smooth kernels finite data sets, generate i..dd data where x (S4) and
d+11
2 + x + sin (wa)
II i=1
x;
+,
with e N/O, o²) independent of æ and evaluate the least squares excess risk of the minimum-non norm interpolant. Figure I.15 shows that
the smaller the spike bandwidth y, the better. At some point, the improvement saturates, p should be carefully tuned, has large impact. As with 7 - 0 ridgeless regression with the spiky-smooth kernel approximates ridge regression with k and regularization p. simply choose the optimal regularization pore of ridge regression.
The spiky-smooth kernel with Gaussian components exhibits catastrophic overfitting, when y is too large (cf. Mallinar et al. (2022)), the Laplace kernel is more robust with respect to With sufficiently thin spikes and properly tuned p. spiky-smooth kernels with Gaussian components outperform the Laplace counterparts.
We repeat the experiment in Figure 1.16 with slightly more complex generating function and come to the same conclusions.
laplace
gaussian
0.25
1od5
0.25
0.023
0.028
0.039
lods
0.11
0.017
0.018
0.02
0.024
Spake bandwidsh 122
cand 0.001
0.25
0.023
0.028
0.039
0.088
0.17
handwidth
0.21
0.088
0.087
0.089
0.094
0.099
0.8
0.25
0.024
0.029
0.041
0.09
0.17
coms
0.94
0.95
0.95
0.96
0.97
0.6
0.08 0.01
0.24
0.029
0.033
0.047
0.096
0.1.8
0.10
4.4
4.4
4.4
4.4
4.5
0.05
5.1e+02
5.le+02
5.le+02 5.1e+02 5.1e+02 5.1e+02
100
10
0.5
0.1
100
10
0.1
061
Quasi-ceularrsstionn
Quasi-rogalaiiaaionn
Figure 1.1: Least squares excess risk for spiky-smooth kernel ridgeless regression with Laplace components (lefi) and Gaussian components (righ),, with 1000, 2, estimated on 10000 independent test points, o² 0.5, 7 The smaller the spike bandwidth ?, the better. Properly
tuning p is important.
63

---

laplace
0.52
0.27
0.085
0.075
0.11
0.19
0,005 (.))) 1c-45
00.52
0.37
0.22
0.16
0.084
0.055
Spike hundwiith "
nos 0.11 0.005 n.00)
0.52
0.27
0.085
0.074
0.11
0.19
0.4
Spike hundwitth
0.45
0.34
0.25
0.21
0.15
0.13
0.51
0.27
0.086
0.076
0.11
0.48
0.081
0.2
(.01
0.4
0.23
0.19
0.15
0.15
0,18
0.21
-28cc403
2.8c+433 2.8c=03
2 2.8c+03
2.8c+03
2.8c+03
Quasi regulurisation
regularissationn P
Figure 1.16:
Same as Figure I.15 but with the more complex generating function =
2c
+
a
sin (2mw=a) + [
d++1_ + The emrors are larger compared to Figure I.15 and the optimal values of are smaller, but the conceptual conclusions remain the same.
64


Reviews:
[{"review_id": "XKI31nNojb", "reviewer": "Reviewer_m3mo", "summary": "This paper explains that benign overfitting when the dimensionality of data is fixed is possible if one looks for estimators differently from conventional minimal norm. If one allows the estimator to be spiky, benign overfitting can still be possible. These results are extended via NTK to two-layer infinite-width neural networks. The authors showed that a nearly imperceptible sinusoid added to a RELU nonlinearity allows the trained neural network to overfit noisy data without compromising generalization.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "(Please note that I could not have proofread the submission as well as I would have liked, due to various external obligations.) This paper extends the results on consistency / inconsistency for infinite-dimensional data to the finite dimensional data case. Although the main points - allowing the estimator to go out of its \"smooth\" way to fit noisy data - could have been argued to be expected, actually seeing this established is still a contribution of remark. The other main point - replacing commonly used non-linearity with one that contains tiny level of sinusoidal perturbation - is not expected by me, that's a very nice way of understanding the non-linearity for neural networks.", "weaknesses": "(Please note that I could not have proofread the submission as well as I would have liked, due to various external obligations.) This paper promotes benign overfitting, but it still leaves open whether not allowing overfitting is better or worse than going into benign overfitting, and within the space of benign overfitting how to reach good results, for a given (n,d). \n\nIn Section 6.2 I felt that the noise standard deviation of 0.25 and the neural tangent kernel of gamma = 1/5000, these two quantities are somehow linked. It could turn out that claiming that such a network can be trained to overfit without regularization might be a dangerous overstatement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for carefully reading our paper and for providing detailed feedback.\n\n**Q1: Is regularization better than benign overfitting?**\n\nWe would like to emphasize that we do not promote overfitting. Instead this paper is the first to show that benign overfitting of kernels and neural networks is possible in the classical limit $d$ fixed, $n\\to\\infty$, in which traditional statistics had suggested that training and test error should be balanced via explicit regularization.\n\nIndeed the question of when overfitting to noise can be helpful is an interesting one, but difficult to answer. From a theoretical perspective, when considering convergence rates for Sobolev target functions, kernel ridge regression already achieves optimal rates, as discussed in the detailed related work (Appendix A). In the updated version, we will show that our estimator achieves the same convergence rates if the spike bandwidth $\\gamma$ converges to zero slightly faster, achieving benign overfitting with optimal rates in Sobolev spaces. This is easy to see since our estimator already mimics kernel ridge regression. From this perspective, we show that both explicitly regularized as well as interpolating estimators can be optimal and bad generalization is not implied by $0$ training error alone.\n\nFrom a practical perspective, there are two aspects: For kernel regression, our spiky-smooth kernels mimic ridge regularization and we do not expect them to perform better than kernel ridge regression.\nFor neural networks, our approach to benign overfitting is not yet practical on realistic data set sizes, more complex architectures, or outside of the kernel regime (as we mention in the future work section), therefore a comparison would be premature.\n\n**Q2: Within the space of benign overfitting, how should one reach good results for given $(n, d)$?**\n\nThe quasi-regularization $\\rho$ can be chosen as in kernel ridge regression, for example via cross-validation, as we discuss in Appendix A. Since the typical distance between training points scales as $n^{-1/d}$ for continuous random variables in $\\mathbb{R}^d$ (see for example Lemma 7 in Buchholz, 2022), the spike bandwidth $\\gamma$ can always be chosen as for the most challenging case $d=1$. With increasing dimension it can be chosen to decay slower as $\\gamma_{n,d}=\\Omega(n^{-(2+\\alpha)/d})$, $\\alpha>0$, as explained in Remark G.2 (see also our global response). This leaves open some parameters such as layer width and learning rate, but this paper should rather be seen as a first possibility result than proposing a fully practical neural method.\n\nRegarding neural networks (Section 6.2), the value $\\gamma = 1/5000$ still determines the width of the spike in the NTK. The spike should be thin enough but it still needs to be possible to approximate it with finite-width neural networks. The optimal width of the spike is not influenced by the noise standard deviation, but the ``regularization'' parameter $\\rho$ that corresponds to the height of the spike should be.\n"}, {"review_id": "mb9p2krRSE", "reviewer": "Reviewer_P771", "summary": "In this paper, the authors studied the problem of benign overfitting for kernels and wide neural networks (in kernel regime) in fixed dimension. The authors showed that benign overfitting is possible if and only if the learner model has large derivatives. This implies that benign overfitting is not possible for those models with small derivatives (including ReLU NTK). On the other hand, they showed that for certain spiky-smooth activations/kernels, benign overfitting is achievable. Experiments are provided in the paper to verify the results.", "questions": "1.\tI was wondering what the dependency on dimension $d$ would be in the results such as Theorem 1.", "limitations": "The limitation is discussed in the paper. This is a theoretical work and therefore does not seem to have negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe paper is clearly written and easy-to-follow. The proof sketch is given to help the readers to understand the proof easier.\n2.\tUnderstanding benign overfitting phenomenon is an important problem for deep learning. The current paper focuses on the kernel regression setting and connects to neural networks via the neural tangent kernel (NTK) theory\n3.\tThe idea of introducing spiky terms in NTK seem to be interesting. The observation in the proof that such spiky term in NTK behaves like regularization term so that the whole solution is now approximating kernel ridge regression also seems to be interesting.\n\n", "weaknesses": "1.\tThe current paper focuses on kernel regression and neural networks in the kernel regime. It would be more interesting to go beyond the kernel regime to see if similar results would also hold (e.g., in feature learning regime).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for carefully reading our paper and for providing detailed feedback.\n\n**Remark: The results only cover the kernel regime.**\n\nWe would like to point out that this paper is the first to establish benign overfitting with a neural model in the challenging regime of low dimension, and the first to rigorously establish benign overfitting in fixed dimension for kernel regression. This regime is very different from the high-dimensional setting, in which feature-learning neural networks usually excel. For Sobolev function spaces, kernel ridge regression achieves optimal non-parametric convergence rates, so that asymptotically there is no need to propose a feature learning neural method, but it was unclear whether benign overfitting can be achieved. In the updated version, we will show that our method matches the convergence rate of kernel ridge regression (see the global response for more details). This shows that benign overfitting is not only possible with kernels and wide neural networks, but can even be rate-optimal.\n\nWe agree that benign overfitting results beyond the kernel regime would also constitute an interesting line of future work, but they are beyond the scope of this paper. We will mention the feature learning regime in the future work section (see the global response). You can find another perspective in our response to Reviewer jpYR.\n\n**Question: What is the dependency on the dimension $d$?**\n\nSee the global response."}, {"review_id": "yuVZxG77iA", "reviewer": "Reviewer_jpYR", "summary": "This paper extends previous results on the inconsistency of ridgeless kernel regression in fixed dimension by showing that non-interpolating estimators whose norm grows comparably to the minimum-norm interpolator are also inconsistent. On the other hand, it is shown that so-called spiky-smooth kernels whose derivatives grow with the number of samples are able to interpolate training data consistently. These results are further specialized to Neural Tangent Kernels and Neural Network Gaussian Processes, and experimental results support the theory.", "questions": "* I believe it can be helpful to add a discussion on the possibility of initializing the weights of a neural network such that training remains in the NTK regime, while the initial predictor is 0, which is an assumption throughout the work.\n\n* In Equation (2) of Theorem 1, is there a hidden dependence on $\\sigma$ in $c$? In particular, is this intuition incorrect that in the noiseless setting of $\\sigma = 0$, consistent estimation ($c = 0$) must be possible?\n\n* In line 232, it is mentioned that Section 5 achieves consistency by violating Assumption (N). To my understanding, it seems like Section 5 takes advantage of having the norm (of any estimator) depend on the number of samples. On the other hand, the specific statement of Assumption (N) seems to still hold in Theorem 7, as it is stated for the minimum-norm interpolant (hence $C_\\text{norm} = 1$).\n\nMinor questions/comments:\n\n* In line 88, it is mentioned that training infinitely wide NNs with gradient flow corresponds to learning with the NTK. Perhaps it is worth mentioning that this is only true under a certain scaling that leads to the \"lazy training\" regime [2], and other smaller initialization scalings that lead to the \"mean field/feature learning\" regime can have better generalization performance [1].\n\n* In line 95, rotation-invariant kernels are suddenly discussed without prior context. It could be useful to mention their importance given that under standard initializations the NTK is rotation-invariant.\n\n[1] Malach et al. \"Quantifying the benefit of using differentiable learning over tangent kernels.\" ICML 2021.\n\n[2] Chizat et al. \"On Lazy Training in Differentiable Programming.\" NeurIPS 2019.", "limitations": "Please see \"Weaknesses\".", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is generally well-written with understandable and insightful theorem statements and proof ideas, even for non-experts.\n* Modifying the kernel to achieve consistency in fixed dimension via inspirations from high-dimensional benign overfitting seems novel and interesting.\n* The assumptions seem to be transparent and clearly stated in the main text.", "weaknesses": "* Having explicit rate estimates in addition to asymptotic consistency guarantees could provide further insight into how the spiky-smooth kernels/activations must be designed to achieve optimal performance.\n* While mathematically exciting and valuable, the results might have limited applicability in modern settings with typically high-dimensional datasets.\n* The results concerning the NTK can be applied to networks in the kernel regime (a.k.a. \"lazy training\"), which can only provide a partial picture as there is increasing evidence that in certain settings, neural networks can generalize better in the \"feature learning\" regime, see e.g. [1].\n\n[1] Malach et al. \"Quantifying the benefit of using differentiable learning over tangent kernels.\" ICML 2021.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for carefully reading our paper and for providing detailed feedback. We agree that all of your suggestions are important clarifications and will include them in the updated version. They will certainly improve the updated version of the paper. Concretely, we will:\n\n- add a discussion on how we configure our NNs to stay close to the NTK limit, with an initial predictor that is zero, and mention feature learning limits.\n\n- add the sentence \"The above kernels as well as NTKs and NNGPs of standard fully-connected neural networks are rotationally invariant.\" before mentioning rotation-invariant kernels.\n\n**Remark 1: Explicit convergence rates.**\n\nWe agree that providing explicit convergence rates constitutes a valuable addition to the paper. Since the minimum-norm estimator of our spiky-smooth kernel sequence mimics kernel ridge regression, it achieves optimal convergence rates for Sobolev target functions. See the global response for more details. We agree that an analysis beyond the asymptotic limit will constitute an interesting line of future work, in particular to understand when and how finite neural networks can overfit benignly on small datasets.\n\n**Remark 2: Limited applicability on high-dimensional datasets.**\n\nNote that the task of benign overfitting is more challenging in fixed dimension, and that this paper is the first one to show that it can be achieved by a neural network. We show that standard ReLU networks (in the NTK parametrization) cannot overfit benignly in this setting and present first ideas on how to enable nearly optimal generalization while overfitting to noise.\n\n**Remark 3: The results only cover the kernel regime.**\n\nWe agree that analysing feature learning neural networks constitutes an interesting line of future work beyond the scope for this paper. We will add a sentence in the future work section (see global response).\n\nAt least for kernel regression, we will show in the updated version that the minimum-norm interpolant w.r.t. our spiky-smooth kernel sequence achieves optimal convergence rates for Sobolev spaces $H^s, s > d/2$. Hence, in fixed dimension, rate-optimal benign overfitting can already be achieved without feature learning.\n\nFrom a theoretical standpoint, it is not clear which function classes to study that represent real datasets more accurately to be able resolve the question how to design feature learning that outperforms kernel regression.\n\nYou can find another perspective in our corresponding answer to Reviewer P771.\n\n**Question 1: Hidden dependence on $\\sigma$ in $c$?**\n\nWithout adaptive bandwidths, as in the formulation of Theorem 1 and for NTKs and NNGPs, or in the large bandwidth case, the dependence is of the form $c\\sigma^2$. We will make the dependence on $\\sigma$ explicit in the updated paper. However, for the more general bandwidth-independent version in Theorem D.1, the low-bandwidth case lower-bounds the estimator bias instead of the estimator variance, and this bias should in principle not depend on $\\sigma^2$ but rather on something like $||f^*||$.\n\n**Question 2: Consistency in the noiseless setting?**\n\nWe mostly study the estimator variance due to label noise in our lower bounds, which of course is zero when $\\sigma^2 = 0$, but this does not say anything about the estimator bias. Whether kernel interpolation is consistent in the noiseless setting is, to our knowledge, an open question. While the kernel interpolation community often studies deterministic covariates $\\boldsymbol{x}_i$, it should be possible to get consistency under relatively weak assumptions from classical theory (see e.g. Wendland, 2005) as long as $f^* \\in \\mathcal{H}_k$. There are also some results for functions $f^*$ in Sobolev spaces that are slightly less smooth than the RKHS (e.g. Theorem 4.2 in Narcowich et al., 2006), but these results require stronger assumptions on the separation distance of the $\\boldsymbol{x}_i$, and it is unclear to us if this would be satisfied for random samples.\n\n**Remark 5: Violating Assumption (N).**\n\nIndeed we have $C_{\\mathrm{norm}} = 1$ when comparing to the RKHS norm of the corresponding spiky-smooth kernel that depends on the number of samples, but $C_{\\mathrm{norm}}$ grows unbounded when comparing to a fixed Sobolev norm. In the updated version, we will replace the sentence \"The key is to violate Assumption (N) and allow for quickly exploding derivatives\" by \"The key is to violate Assumption (N) for every fixed Sobolev RKHS norm $||\\cdot||_{H_k}$ and introduce an inductive bias towards learning spiky-smooth functions\".\n\n**References:**\n\nFischer and Steinwart \"Sobolev Norm Learning Rates for Regularized Least-Squares\", JMLR 2020.\n\nNarcowich et al. \"Sobolev error estimates and a Bernstein inequality for scattered data interpolation via radial basis functions\", Constructive Approximation, 2006. \n\nWendland ``Scattered Data Approximation'', Cambridge University Press, 2005.\n"}, {"review_id": "AUNR8FrNLx", "reviewer": "Reviewer_GSDW", "summary": "This work studies the generalization behavior of overfitting methods in terms of the smoothness of the estimator, showing that only non-smooth estimators can interpolate benignly. They give a discussion of this result in the context of NTKs and their corresponding infinite-width architectures.", "questions": "The authors argue that the key object to consider is estimator smoothness, not input dimension. Given that there exists a body of results that do find that input dimension is important, is it clear how to reconcile the author's new results with these old ones? For example, do the smoothness requirements get more relaxed as dimension increases?\n\nNote: I think an activation fn corresponding to the Gaussian NNGP kernel can be written down in closed form. (I do not know if this is true for the NTK, and would be curious to know if it can.)\n\nNote: a high-frequency sinusoidal activation function can also give you a spiky kernel!\n\nNote for future research: this smooth + spiky kernel thing seems like a hack. However, the results of Mallinar et al. suggest that if you could write down any kernel with an eigendecay like $\\lambda_i \\sim i^{-1} \\log^{-\\alpha} i$ for $\\alpha > 1$, you'd get a consistent estimator without the need to scale down the kernel. It seems plausible to me that by taking a sort of exponent-equals-zero limit of Bietti and Bach's analysis, you could construct a kernel that actually gives you this decay (even on the unit circle), and it'd be consistent while being (a) a continuous function and (b) not needing to be scaled with dataset size. Could be an interesting thing to look into.", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality and quality: this work seems to shed some new light on a well-studied problem. I'm not very familiar with background results on asymptotic risk w.r.t. function smoothness, so it's difficult for me to assess the first several theorem statements. I'm quite familiar with the latter results on NTKs, and to my knowledge this observation about spikiness in activation functions is new, and I find it well-explained.\n\nClarity: the paper seems pretty clear and well-written.\n\nSignificance: the math here is nice, and it seems like this might lead to some more clarity regarding exotic activation functions.", "weaknesses": "On significance: it's sort of unclear to me how this matters, or where we go from here. For example: the results of Mallinar et al. suggest that early stopping in nets (or including a ridge parameter in KRR, as shown by prior work too) is enough to make fitting consistent. These questions like \"how do we design our model so it overfits benignly?\" seem like they're actually missing some motivation -- why do we need to do that? Can't we just use a ridge parameter or optimal stopping?\n\nThe results around spike-inducing kernels seem quite hacky. The fact that the spike has to get smaller with dataset size makes it clear that this is just effectively adding a ridge. (The authors acknowledge this, but it's still not a surprising conclusion in my view.) It's also not useful -- the authors do not try to train their Hermite-polynomial nets, and (based on my own attempts to do such things) I suspect this may be because they're unstable, even at moderately large width!\n\nAs stated above, I'm unfamiliar with prior art around function smoothness and overfitting behavior, so there's a fair bit of uncertainty in my assessment here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for carefully reading our paper and for providing detailed feedback.\n\n**Remark 1: Benign overfitting lacks motivation.**\n\nThe considerable interest in benign overfitting is mainly motivated by the great successes of overfitted NNs. In this sense, overfitting is motivated by empirical results, even though this overfitting might not be consistent or benign in a theoretical sense. A more detailed discussion of related work is provided in Appendix A. Since the community does not yet understand precisely why overfitting is often beneficial for NNs, it seems premature to dismiss approaches that can enable benign overfitting. On the other hand, it is not our main goal to improve overfitting in NNs, but rather to understand the conditions under which benign overfitting can occur. To the best of our knowledge, this paper is the first to show benign overfitting of a neural model in the challenging regime of low dimension, and rigorously establishing both consistency and inconsistency results for kernel regression posed several technical challenges. In the future work section, we acknowledge that we have not yet provided a neural method that is meant for practical use.\n\n**Remark 2: Spiky-smooth kernels seem hacky and not surprising.**\n\nExploiting the connection to ridge regression is precisely what enables optimal nonparametric convergence rates. We will include this result in the updated version. More details can be found in the global response. Constructing our spiky-smooth kernel sequence as we do allows us to plug in Gaussian kernels and apply Theorem 3.1 of Simon et al. (2022). Spiky-smooth kernels are a simple idea and might not be surprising in hindsight, but we would argue that the consistency properties they can achieve are not obvious, and the simplicity is helpful in understanding their properties and the resulting implications, for example in deriving optimal rates for benign overfitting.\n\n**Remark 3: We do not train Hermite polynomial nets.**\n\nThe Hermite polynomial basis only serves us as a tool to understand which activation functions give rise to benign overfitting. Since the shifted sine function emerges as a more practical solution, there is no need to train neural networks with Hermite polynomial activation functions. When training fully connected networks with the spiky-smooth activation function in Figure 1, we observe quite stable training trajectories at large widths. However, we acknowledge in the future work section that the spiky-smooth activation functions do not yet scale to large datasets. Identifying the right architectural inductive bias for moderate widths also poses an exciting opportunity for future work. Maybe this involves more than purely adapting the activation function. The goal of this theoretical study is rather to rigorously establish when and how benign overfitting with kernels and neural networks is possible in fixed dimension.\n\n**Question 1: What is the interplay between smoothness and input dimension?**\n\nLet us discuss this question from several angles.\n\n1) **Order of smoothness.** Other papers find that input dimension is important for a \"typical'' sequence of kernels $(k_d)_{d \\in \\mathbb{N}}$. Our results show that the dimension is not the single decisive quantity because one can also achieve benign overfitting in fixed dimension, even in Sobolev RKHS of arbitrary smoothness. Mallinar et al. (2022) consider, for example, Laplace-like kernels and semi-rigorously show that they overfit more benignly (tempered with decreasing constant in $d$) in high dimension. However, it is unclear how to compare their smoothness across dimensions: The Sobolev space smoothness $s = (d+1)/2$ increases with $d$, but the eigenvalue decay $\\lambda_n = \\Theta(n^{-(d+1)/d})$ gets slower.\n\n2) **Smoothness in the sense of the magnitude of derivatives.** Here we refer to the global response. In short, the spike bandwidth is allowed to decay slower in high dimension. The order of smoothness of the RKHS is irrelevant, we achieve benign overfitting even by composing Gaussian kernels.\n\n**Remark 4: An activation function corresponding to the Gaussian NNGP kernel can be written down in closed form.**\n\nThank you for pointing this out. We will include the derivation of Eq. (7) in the updated version. It just requires $e^{2xz-z^2}=\\sum_{n=0}^\\infty z^n H_n(x)/n!$ with $z=\\pm i\\sqrt{1/\\gamma}$ and some elementary calculations. When choosing all signs in the Hermite expansion positive, the corresponding activation function was stated in closed from in Eq. (H.2). The problem with the spiky-smooth activation functions is that the corresponding Hermite coefficients are of the form $\\pm\\sqrt{a_n + b_n}$, where $a_n$ and $b_n$ are the Taylor coefficients of the smooth and spiky parts, respectively. So we cannot just add up the spiky and smooth activation functions. We do not see how one could write Gaussian NTK activation functions in closed form.\n\n**Remark 5: A high-frequency sinusoidal activation function induces a spiky kernel.**\n\nYes, a high-frequency sinusoidal activation function induces a spiky kernel. This is the idea behind adding it to a low-frequency activation function to get a spiky-smooth kernel. Similar to the small bandwidth case in the proof of Theorem 1, a pure spiky kernel will not overfit benignly.\n\n**Remark 6: Consistency with a single kernel function.**\n\nIndeed this is an interesting question, though it might well be that the resulting convergence rates would be terrible. We have mentioned this idea in Remark G.4.\n\n**References:**\n\nMallinar et al. \"Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting\", NeurIPS 2022.\n\nSimon et al. \"Reverse engeneering the neural tangent kernel\", ICML 2022."}, {"review_id": "2SV2FAVI6k", "reviewer": "Reviewer_Si3s", "summary": "This paper generalize existing inconsistency results to non-interpolating models and more kernels to show that benign overfitting with moderate derivatives is impossible in fixed dimension.\nMoreover, this paper proves that interpolation with spiky-smooth kernels can be consistent and such kernels can be induced by certain activation functions.\nThere are also experiments supporting the authors' claims.", "questions": "1. Can Theorem 5 be extended to $H^s(\\Omega)$, $\\Omega \\subset \\mathbb{R}^d$ ?\nIf not, could the authors explain the difficulties here?\n\n2. Is it possible to derive optimal rates for interpolation with spiky-smooth kernels?", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and easy to follow.\nIt also provides us with novel understandings of the benign overfitting phenomenon: the smoothness of the estimators, and not the dimension, matters.\nIn particular, by considering spiky-smooth kernels, the authors find that interpolation with kernels can be consistent in fixed dimension.\nThis new result is very interesting.\n\nOn the technical side, the authors improve previous inconsistency results for RKHS equivalent to Sobolev RKHS of smoothness $s > d/2$ on the sphere $\\mathbb{S}^d$. The techniques here are solid.\n\n", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank you for carefully reading our paper and for providing detailed feedback.\n\n**Question 1: Can Theorem 5 be extended to $H^s(\\Omega)$, $\\Omega\\subset \\mathbb{R}^d$?**\n\nThere is a technical obstacle to generalizing Theorem 5 to open bounded sets $\\Omega \\subseteq \\mathbb{R}^d$, which could perhaps be overcome with additional technical contributions. This is discussed before Proposition F.12 in the appendix. Our proof uses that if $H_k \\cong H^s$, then the RKHS $H_{k_*} \\cong H^{2s}$, which is true for dot-product kernels on the sphere as shown in Proposition F.12. This allows us to apply kernel matrix eigenvalue bounds for Sobolev kernels to $k_*$. However, for kernels on open bounded sets $\\Omega \\subseteq \\mathbb{R}^d$, this is in general not true, as the space $H_{k_*}$ will be slightly smaller than $H^{2s}$ due to some extra ``boundary conditions''. Intuitively, the sphere is a manifold without boundary and therefore less problematic in this regard. However, with a better understanding of the spaces $H_{k_*}$ for such $\\Omega$, it might be possible to extend our proof to this setting. We will add a short discussion on this issue in the updated version of our manuscript.\n\n**Question 2: Is it possible to derive optimal rates for interpolation with spiky-smooth kernels?**\n\nYes, very good point. Since minimum-norm interpolation with spiky-smooth kernels mimics ridge regression with smooth kernels, the rates from kernel ridge regression can be easily transferred. We agree that this is a valuable addition to the paper and will include this result in the updated version. More details can be found in the global response.\n"}]

Author rebuttal:
We want to thank all reviewers for their detailed feedback. The following remarks have been raised multiple times and we will include a discussion in the revised version of our paper:

**Question 1: Can benign overfitting with spiky-smooth kernels achieve optimal rates?**

Since minimum norm interpolation with the spiky-smooth kernel sequence mimics kernel ridge regression with the smooth kernel component, it is easy to see that our estimator achieves the same convergence rates as kernel ridge regression, if the spike bandwidth $\gamma$ converges to zero slightly faster. By choosing the quasi-regularisation $\rho$ as for kernel ridge regression, we can therefore achieve benign overfitting with optimal nonparametric rates in Sobolev spaces (up to a $\log^2(n)$ term) (Fischer and Steinwart, 2020). As discussed in the detailed related work Appendix A, $\rho$ can for example be chosen via cross-validation. We will include this result in the updated version, which resolves the question whether benign overfitting with optimal nonparametric convergence rates is possible with kernel regression in fixed dimension.

**Question 2: What is the dependency on the dimension $d$?**

This question can be posed for our inconsistency results and for our consistency result. 

For our inconsistency results, the constant $c$ in the lower bound can depend on the dimension $d$ as well as the specific choice of the kernel $k = k_d$ for different dimensions $d$. For specific sequences of kernels $(k_d)_{d \in \mathbb{N}}$, there are results by Liang and Rakhlin (2020) and Liang et al. (2020) which show a convergence to zero for $d \to \infty$, and a more quantitative but semi-rigorous result by Mallinar et al. (2022). In our case, obtaining an explicit dependency on $d$ would require at least stronger assumptions and very careful reworking of previous works. Specifically, it would require at least

- to consider how the constants of equivalence behave for varying $d$ in assumption (K)

- to fix one definition of the Sobolev norm, since the constants of equivalence between different equivalent Sobolev norm definitions might grow with $d$,

- to track the dependence of the constants on $d$ in our proofs and all previous works, especially Buchholz (2022) and the literature on Sobolev spaces he builds upon.

Now we discuss our consistency result. For continuous covariate distributions with upper bounded Lebesgue density, the typical distance between training points scales as $n^{-1/d}$ (see e.g. Lemma 7 in Buchholz (2022)). The spike bandwidth $\gamma$ has to decay to $0$ faster than this typical distance. For the example of the Laplace kernel, we can choose the spike bandwidth $\gamma_{n,d}=\Omega(n^{-(2+\alpha)/d})$, $\alpha>0$, as previously explained in Remark G.2. Hence, the spikes are indeed allowed to be less sharp with increasing dimension. When $d$ and $n$ have the same order of magnitude, the minimum-norm interpolants of common kernels suffice to achieve benign overfitting - under stronger, favorable distributional assumptions (Liang and Rakhlin, 2020). Irrespective of the dimension $d$, we achieve benign overfitting with estimators in RKHS of arbitrary degrees of smoothness.

**Limitation: Our results only cover the kernel regime.**

Since our analysis only covers the kernel regime, we will add the following sentence in the future work section: "Finite-sample analyses of moderate-width neural networks with feature learning parametrizations and other initializations could enable to understand how to induce a spiky-smooth inductive bias in feature learning neural architectures."

**References:**

S. Buchholz "Kernel interpolation in Sobolev spaces is not consistent in low dimensions", COLT 2022.

Fischer and Steinwart "Sobolev Norm Learning Rates for Regularized Least-Squares", JMLR 2020.

Liang and Rakhlin "Just Interpolate: Kernel “Ridgeless” Regression Can Generalize", Annals of Statistics, 2020.

Liang et al. "On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels", COLT 2020.

Mallinar et al. "Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting", NeurIPS 2022.

Meta-review: The paper provides a refined perspective on the phenomenon of benign overfitting for kernels, highlighting the key role played by the smoothness of the estimator. While prior work emphasizes the role of the dimension, the paper shows that the dimension is not the single decisive quantity (one can also achieve benign overfitting in fixed dimension as highlighted by the authors). This is to my knowledge a novel perspective, which is recognized by all the reviewers.

Most reviewers were positive prior to the discussion period, some even increased their scores after discussing with the authors. Overall, the paper makes a novel contribution which is appreciated by the reviewers, I therefore recommend acceptance.
Decision: Accept (poster)