{'fraction_non_alphanumeric': 0.04159277768821538, 'fraction_numerical': 0.015593627716793927, 'mean_word_length': 4.058117123795404, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
How rotational invariance of common kernels prevents generalization in high dimensions

Kernel ridge regression is well-known to achieve minimax optimal rates in low-dimensional settings. However, its behavior in high dimensions is much less understood. Recent work establishes consistency for kernel regression under certain assumptions on the ground truth function and the distribution of the input data. In this paper, we show that the rotational invariance property of commonly studied kernels (such as RBF, inner product kernels and fully-connected NTK of any depth) induces a bias towards low-degree polynomials in high dimensions. Our result implies a lower bound on the generalization error for a wide range of distributions and various choices of the scaling for kernels with different eigenvalue decays. This lower bound suggests that general consistency results for kernel ridge regression in high dimensions require a more refined analysis that depends on the structure of the kernel beyond its eigenvalue decay.


Introduction
Traditional analysis establishes good generalization properties of kernel ridge regression when the dimension d is relatively small compared to the number of samples n. These minimax optimal and consistency results however become less powerful for modern data sets with large d close to n. High-dimensional asymptotic theory [7,42] aims to fill this gap by providing bounds that assume d, n → ∞ and are often much more predictive of practical observations even for finite d.
While recent work [2,12,19] establishes explicit asymptotic upper bounds for the bias and variance for high-dimensional linear regression, the results for kernel regression are less conclusive in the regime d/n β → c with β ∈ (0, 1). In particular, even though several papers [17,18,27] show that the variance decreases with the dimensionality of the data, the bounds on the bias are somewhat inconclusive. On the one hand, Liang et al. [27] prove asymptotic consistency for ground truth functions with asymptotically bounded Hilbert norms for neural tangent kernels (NTK) and inner product (IP) kernels. In contrast, Ghorbani et al. [17,18] show that for uniform distributions on the product of two spheres, consistency cannot be achieved unless the ground truth is a low-degree polynomial. This polynomial approximation barrier can also be observed for random feature and neural tangent regression [17,31,32].
Notably, the two seemingly contradictory consistency results hold for different distributional settings and are based on vastly different proof techniques. While [27] proves consistency for general input distributions including isotropic Gaussians, the lower bounds in the papers [17,18] are limited to data that is uniformly sampled from the product of two spheres. Hence, it is a natural question to ask whether the polynomial approximation barrier is a more general phenomenon or restricted to the explicit settings studied in [17,18]. Concretely, this paper addresses the following question Can we overcome the polynomial approximation barrier when considering different high-dimensional input distributions, eigenvalue decay rates or scalings of the kernel function?
We unify previous distributional assumptions in one proof framework and thereby characterize how the rotational invariance property of common kernels induces a bias towards low-degree polynomials. Specifically, we show that the polynomial approximation barrier persists for • a broad range of common rotationally invariant kernels such as radial basis functions (RBF) with vastly different eigenvalue decay rates, inner product kernels and NTK of any depth [21].
• general input distributions including anisotropic Gaussians where the degree of the polynomial depends only on the growth of d eff := tr(Σ d )/ ||Σ d || op and not on the specific structure of Σ d . In particular, we cover the distributions studied in previous related works [17,18,27,28,29].
As a result, this paper demonstrates that the polynomial approximation barrier is a general highdimensional phenomenon for rotationally invariant kernels, restricting the set of functions for which consistency can at most be reached to low degree polynomials.
Rotationally invariant kernels are a natural choice if no prior information on the structure of the ground truth is available, as they treat all dimensions equally. Since our analysis covers a broad range of distributions, eigenvalue decays and different scalings, our results motivate future work to focus on the symmetries respectively asymmetries of the kernel incorporating prior knowledge on the structure of the high-dimensional problem, e.g. [1,33,39].
This paper is organized as follows. First of all, we show in Section 2.2 that the bounded norm assumption that previous consistency results [27,28] rely on is violated as d → ∞ even for simple functions such as f (x) = e 1 x. We then introduce our generalized setting in Section 2 and present our main results in Section 3 where we show a lower bound on the bias that increases with the dimensionality of the data. Finally, in Section 4 we empirically illustrate how the bias dominates the risk in high dimensions and therefore limits the performance of kernel regression. As a result, we argue that it is crucial to incorporate prior knowledge of the ground truth function (such as sparsity) in high-dimensional kernel learning even in the noiseless setting and empirically verify this on real-world data.

Problem setting
In this section, we briefly introduce kernel regression estimators in reproducing kernel Hilbert spaces and subsequently introduce our assumptions on the kernel, data distribution and high-dimensional regime.

Kernel ridge regression
We consider nonparametric regression in a reproducing kernel Hilbert space (RKHS, see e.g. [40,41]) with functions on the domain X ⊂ R d induced by a positive semi-definite kernel k : X × X → R. That is, for any set of input vectors {x 1 , · · · , x m } in X , the empirical kernel matrix K with entries K i,j = k(x i , x j ,) is positive semi-definite. We denote by ., . k the corresponding inner product of the Hilbert space and by . H := ., . k the corresponding norm. We observe tuples of input vectors and response variables (x, y) with x ∈ X and y ∈ R. Given n samples, we consier the ridge regression estimator with λ > 0 and the minimum norm interpolator (also called the kernel "ridgeless" estimate) that can be obtained as the limit of the ridge estimatef 0 = lim λ→0fλ for fixed n. It is well-known that the ridge estimator can attain consistency as n → ∞ for some sequence of λ such that λ n → 0. Recently, some works [17,18,27,28] have also analyzed the consistency behavior of ridgeless estimates motivated by the curiously good generalization properties of neural networks with zero training error.
For evaluation, we assume that the observations are i.i.d. samples from a joint distribution (x i , y i ) n i=1 ∼ P XY and refer to f (x) := E[y | X = x] as the ground truth function that minimizes the population square loss E(Y − f (X)) 2 . We evaluate the estimator using the population risk conditioned on the input data X where E Y is the conditional expectation over the observations y i ∼ P(Y |X = x i ). In particular, when y = f (x) + , E Yfλ is equivalent to the noiseless estimator with = 0. Note that consistency in terms of R(f λ ) → 0 as n → ∞ can only be reached if the bias vanishes. In this paper, we lower bound the bias B which, in turn, implies a lower bound on the risk and the inconsistency of the estimator. The theoretical results in Section 3 hold for both ridge regression and minimum norm interpolation. However, it is well known that the ridge penalty controls the bias-variance trade-off, and hence we are primarily interested in lower bounds of the bias for the minimum norm interpolant.

Prior work on the consistency of kernel regression
For ridge regression estimates in RKHS, a rich body of work shows consistency and rate optimality when appropriately choosing the ridge parameter λ both in the non-asymptotic setting, e.g. [8], and the classical asymptotic setting, e.g. [10], as n → ∞.
Similar results have also been shown for high-dimensional asymptotics, where recent papers on minimum norm interpolation in kernel regression [27,28] explicitly show how the bias vanishes when the ground truth function has bounded Hilbert norm as d, n → ∞. Even though this assumption is perfectly reasonable for a fixed ground truth and Hilbert space, its plausibility is less clear for a sequence of functions as d → ∞. 1 After all, the Hilbert space and thus also the norm change with d. In fact, we now show that even innocuous functions have diverging Hilbert norm as the dimension increases. In particular, for tensor product kernels including exponential inner product kernels (also studied in [27,28]) defined on x, x ∈ X ⊗d ⊂ R d , we can show the following lemma.
. For any f that is a non-constant sparsely parameterized product function In words, for simple sequences of sparse product functions, the Hilbert norm diverges as the dimension d → ∞. The precise conditions on the kernel and sequence H d of induced Hilbert spaces can be found in Appendix B. Figure 1 illustrates this phenomenon for f (x) = e 1 x for the Laplace and exponential inner product kernel.
The discussion so far implies that generalization upper bounds that rely on the bounded Hilbert norm assumption become void even for simple ground truth functions. A natural follow-up question is hence: Do we actually fail to learn sparsely parameterized functions consistently or is it simply a loose upper bound? A recent line of work by Ghorbani et al. [17,18] shows that kernel regression estimates can indeed only consistently learn polynomials of degree at most log n log d eff as d, n → ∞ (which we refer to as the polynomial approximation barrier ). While the results provide some intuition for the behavior of kernel regression, the proofs heavily rely on significant simplifications that hold for the specific distributional assumptions on the sphere. It is a priori unclear whether they apply to more general settings including the ones considered in [27]. In the next sections, relying on a different proof technique we show that the polynomial approximation barrier indeed holds for a broad spectrum of data distributions that also capture the distributions studied in the papers [27,28] and for an entire range of eigenvalue decay rates of the kernel functions (e.g. polynomial and exponential decay rates) and choices of the scaling τ . As a consequence, our results suggest that the polynomial approximation barrier is strongly tied to the rotational invariance of the kernel function and not specific to the settings studied so far.

Our problem setting
The framework we study in this paper covers random vectors that are generated from a covariance matrix model, i.e. X = Σ 1/2 d W with vector W consisting of i.i.d entries and their projections onto the d−1-dimensional unit sphere. We now specify all relevant assumptions on the kernel and data distribution.
Kernels Throughout this paper, we focus on continuous and rotationally invariant kernels. They include a vast majority of the commonly used kernels such as fully connected NTK, RBF and inner product kernels as they only depend on the squared Euclidean norm of x and x and the inner product x x . We first present one set of assumptions on the kernel functions that are sufficient for our main results involving local regularity of k around the sphere where the data concentrates in high dimensions.
(A.1) Rotational invariance and local power series expansion: The kernel function k is rotationally invariant and there is a function g such that k(x.x ) = g( x 2 2 , x 2 2 , x x ). Furthermore, g can be expanded as a power series of the form Furthermore, all g i are positive semi-definite kernels.
We show in Corollary 3.2 that the kernels for which our main results hold cover a broad range of commonly studied kernels in practice. In particular, Theorem 3.1 also holds for α-exponential kernels defined as k(x, x ) = exp(− x − x α 2 ) for α ∈ (0, 2) even though we could not yet show that they satisfy Assumptions A.1-A.2. In Appendix C, we show how the proof of Theorem 3.1 crucially relies on the rotational invariance Assumption C.1 and the fact that the eigenvalues of the kernel matrix K are asymptotically lower bounded by a positive constant. Both conditions are also satisfied by the α-exponential kernels and the separate treatment is purely due to different proof technique used to lower bound the kernel matrix eigenvalues.
Data distribution and scaling We impose the following assumptions on the data distribution.
(B.1) Covariance model : We assume that the input data distribution is from one of the following sets In words, when P X ∈ Q, the data has covariance Σ d , and when P X ∈ Q S d−1 , the data can be generated by projecting Z ∼ P Z ∈ Q onto the sphere of radius √ d eff . Unlike Ghorbani et al. [17,18], we do not require the random vectors x i to be uniformly distributed on the sphere. Our distributional assumptions include and generalize previous works. A comparison can be found in Table 1. In the sequel, we assume without loss of generality that for simplicity ||Σ d || op = 1 and hence d eff = tr(Σ d ).
In our analysis, the kernel function g does not change for any d. However as d eff , n → ∞ we need to adjust the scaling of the input as the norm concentrates around E x 2 2 = d eff . Hence, as n → ∞, we consider the sequence of scale dependent kernels and parameterize the scaling by sequence of parameters τ dependent on n. In Section 3.1 we study the standard scaling τ d eff → c > 0, before discussing τ d eff → 0 and τ d eff → ∞ respectively in Section 3.2, where we show that the polynomial approximation barrier is not a consequence of the standard scaling.

Main Results
We now present our main results that hold for a wide range of distributions and kernels and show that kernel methods can at most consistently learn low-degree polynomials. Section 3.1 considers the case τ d eff while Section 3.2 provides lower bounds for the regimes τ d eff → 0 and τ d eff → ∞.

Inconsistency of kernel regression for τ d eff
For simplicity, we present a result for the case τ = d eff based on the assumptions A.1-A.2. The more general case τ d eff follows from the exact same arguments. In the sequel we denote by P ≤m the space of polynomials of degree at most m ∈ N.
Theorem 3.1 (Polynomial approximation barrier). Assume that the kernel k respectively its restriction onto the sphere satisfies A.1-A.2 or is an α-exponential kernel. Furthermore assume that the input distribution P X satisfies Assumptions B.1-B.2 and that the ground truth function f * is bounded. Then, for some m ∈ N specified below, the following results hold for both the ridge (1) and ridgeless estimator (2)f λ with λ ≥ 0.   (1) ) plotted in the direction (0, 1/2, · · · , 1/2) + αe1 when fitting noiseless observations with covariates drawn uniformly from [0, 1] d with n = 100 and varying d.
1. The bias of the kernel estimatorsf λ is asymptotically almost surely lower bounded for any > 0, 2. For bounded kernel functions on the support of P X the averaged estimator E Yfλ converges almost surely in L 2 (P X ) to a polynomial p ∈ P ≤m , → 0 a.s. as n → ∞.
Corollary 3.2 gives examples for kernels that satisfy the assumptions of the theorem. The almost sure statements refers to the sequence of matricies X of random vectors x i as n → ∞, but also hold true with probability ≥ 1 − n 2 exp(−C log(n) (1+ ) ) over the draws of X (see Lemma C.1 for further details).
The first statement in Theorem 3.1 shows that even with noiseless observations, the estimatorf λ can at most consistently learn ground truth functions f that are a polynomial of degree less than m. We refer to m as the β-dependent polynomial approximation barrier. Figure 2a and 2b illustrate this barrier on synthetic datasets drawn from different input data distributions. While the first statement only implies that the risk does not vanish if f is not a polynomial, the second part of Theorem 3.1 explicitly states that the averaged estimator E Yfλ converges in L 2 (P X ) to a polynomial of degree at most m when the kernel is bounded on the support of P X . 2 We refer to Theorem C.2 in Appendix C for slightly weaker statements which also apply to unbounded kernels. Figure 2c illustrates how the estimator degenerates to a linear function as dimension grows.
The attentive reader might notice that Ghorbani et al. [18] achieve a lower barrier m = 1/β for their specific setting which implies that our results are not tight. However, this is not the main focus in this work as we primarily intend to demonstrate that the polynomial approximation barrier persists for general covariance model data distributions (Ass. B.1-B.2) and hence asymptotic consistency in high-dimensional regimes is at most reachable for commonly used rotationally invariant kernels if the ground truth function is a low degree-polynomial. We leave tighter bounds as interesting future work. Finally, we remark that as β → 0 we enter again a classical asymptotic regime where n is much larger compared to d and hence m → ∞. This underlines the difference between classical and high-dimensional asymptotics and shows that our results are only meaningful in the latter.
We now present a short proof sketch to provide intuition for why the polynomial approximation barrier holds. The full proof can be found in Appendix C.
Proof sketch The proof of the main theorem is primarily based on the concentration of Lipschitz continuous functions of vectors with i.i.d entries. In particular, we show in Lemma C.1 that where we use tr(Σ d ) n β . Furthermore, Assumption A.1and hence the rotational invariance of the kernel function k, implies that for inner product kernels where g j are constants, with θ some constant such that 1 < θ < (m + 1) β 2 that exists because m ≥ 2/β . Hence, as n → ∞, k τ (x i , X) converge to low-degree polynomials. Using the closed form solution off λ based on the representer theorem we can hence conclude the first statement in Theorem 3.1 if K + λI cI for some constant c > 0. The result follows naturally for ridge regression with non vanishing λ > 0. However for the minimum norm interpolator, we need to show that the eigenvalues of the kernel matrix K themselves are asymptotically lower bounded by a positive non-zero constant. This follows from the additional assumption in Theorem 3.1 and the observation that (X X) •j → I n in operator norm with • being the Hadamard product. Finally, the case where g j depend on x i 2 2 and x j 2 2 requires a more careful analysis and constitute the major bulk of the proof in Appendix C.
The assumptions in Theorem 3.1 cover a broad range of commonly used kernels, including the ones in previous works. The following corollary summarizes some relevant special cases Corollary 3.2. Theorem 3.1 applies to 1. The exponential inner product kernel 2. The α-exponential kernel for α ∈ (0, 2], including Laplace (α = 1) and the Gaussian (α = 2) kernels 3. The fully-connected NTK of any depth with regular activation functions including the ReLU activation The precise regularity conditions of the activation functions for the NTK and the proof of the corollary can be found in Appendix C.3.

Inconsistency of kernel interpolation for τ d eff
As Section 3.1 establishes the polynomial approximation barrier for the classical scaling τ d eff 1, an important question remains unaddressed: can we avoid it with a different scaling? When τ d eff → 0, intuitively the estimates converge to the zero function almost everywhere and hence the bias is lower bounded by the L 2 (P x )norm of f . This implies that no function can be learned consistently with this scaling (see Appendix D.2 for  a rigorous statement). When τ increases faster than d eff , however, the behavior is unclear a priori. Simulations in Figure 3a, 3c suggest that the bias could in fact decrease for τ d eff and attain its minimum at the so called flat limit, when τ → ∞. To the best of our knowledge, the next theorem is the first to show that the polynomial approximation barrier persists in the flat limit for RBF kernels whose eigenvalues do not decay too fast. Theorem 3.3. Let k be an RBF kernel with Fourier transformk such that for any d, lim for some α ∈ (0, 2). Under the assumptions B.1-B.2 on the data distribution, the bias lower bound (5) and polynomial approximation (6) hold for the flat limit interpolator lim τ →∞f 0 with the same β-dependence for m as in Theorem 3.1, given that f is bounded on the support of P X .
In particular, the assumptions hold for instance for the α-exponential kernels with α ∈ (0, 2) (see [6]) and the popular Matern RBF kernels with ν < 2. The proof of the theorem can be found in Appendix D.1 and is based on the flat limit literature on RBFs [13,22,25,38]. Finally, we remark that Theorem 3.3 applies only for the interpolating estimatorf 0 . However, because the ridge penalty is well known to regulate the bias-variance tradeoff, we argue that the bias increases with the ridge penalty and hence attains its minimum at λ = 0.

Discussion of theoretical results
As a consequence of our unifying treatment, we cover most of the settings studied in the existing literature and show that the polynomial approximation barrier (5) is neither restricted to a few specific distributions nor to a particular choice of the scaling or the eigenvalue decay of the kernel function. We summarize our setting alongside those of previous works in Table 1.
Distribution The Assumptions B.1-B.2 allow very general distributions and include the ones in the current literature. In particular, we also cover the settings studied in the papers [27,28,29] and hence put their optimistic conclusions into perspective. Besides, our results hold true for arbitrary covariance matrices and only depend on the growth rate of the effective dimension, but are independent of the explicit structure of the covariance matrix. This stands in contrast to linear regression where consistency can (only) be guaranteed for spiky covariance matrices [2,35].
Scaling Our results do not only apply for the standard choice of the scaling τ /d eff → c > 0, but also apply to general RBF kernels in the flat limit scaling, i.e. where τ → ∞. This case is particularly important since  this is where we empirically find the bias to attain its minimum in Figure 3c. We therefore conjecture that the polynomial approximation barrier cannot be overcome with different choices of the scaling.
Eigenvalue decay Furthermore, by explicitly showing that the polynomial barrier persists for all αexponential kernels with α ∈ (0, 2] (that have vastly different eigenvalue decay rates), we provide a counterpoint to previous work that suggests consistency for α → 0. In particular, the paper [4] proves minimax optimal rates for the Nadaraya-Watson estimators with singular kernels for fixed dimensions and empirical work by [3,43] suggests that spikier kernels have more favorable performances. Our results suggest that in high dimensions, the effect of eigenvalue decay (and hence "spikiness") may be dominated by asymptotic effects of rotationally invariant kernels. We discuss possible follow-up questions in Section 5.
As a result, we can conclude that the polynomial approximation barrier is a rather general phenomenon that occurs for commonly used rotationally invariant kernels in high dimensional regimes. For ground truths that are inherently higher-degree polynomials that depend on all dimensions, our theory predicts that consistency of kernel learning with fully-connected NTK, standard RBF or inner product kernels is out of reach if the data is high-dimensional. In practice however, it is possible that not all dimensions carry equally relevant information. In Section 4.3 we show how feature selection can be used in such settings to circumvent the bias lower bound. On the other hand, for image datasets like CIFAR-10 where the ground truth is a complex function of all input dimensions, kernels that incorporate convolutional structures (such as CNTK [1,37] or compositional kernels [11,33,39]) and hence break the rotational symmetry can perform quite well.

Experiments
In this section we describe our synthetic and real-world experiments to further illustrate our theoretical results and underline the importance of feature selection in high dimensional kernel learning.

Hilbert space norm increases with dimension d
In Figure 1, we demonstrate how the Hilbert norm of the simple sparse linear function f (x) = x (1) grows with dimension d. We choose the scaling τ = d and consider the Hilbert space induced by the scaled ) and exponential inner product To estimate the norm, we draw 7500 i.i.d. random samples with noiseless observations from the uniform distribution on X = [0, 1] d .

Illustration of the polynomial approximation barrier
We now provide details for the numerical experiments in Figure 2,3 that illustrate the lower bounds on the bias in Theorem 3.1 and Theorem 3.3. For this purpose, we consider the following three different distributions that satisfy the assumptions of the theorems and are covered in previous works We primarily use the Laplace kernel 4 with τ = tr(Σ d ) unless otherwise specified and study two sparse monomials as ground truth functions, f 1 (x) = 2x 2 (1) and f 2 (x) = 2x 3 (1) . In order to estimate the bias of the minimum norm interpolant we generate noiseless observations and approximate the expected squared error using 10000 i.i.d. test samples.
In Figure 2a and 2b, we plot the dependence of the bias on the parameter β which captures the degree of high-dimensionality, i.e. how large dimension d is compared to the number of samples n. We vary β by fixing n and increasing d (see also Appendix for plots for fixed d and varying n). In Figure 2a we demonstrate the important consequence of our unifying framework that the polynomial barrier only depends on the growth of the effective dimension tr(Σ d ), parameterized by β independent of the specific choice of the distribution. 5 The horizontal lines that indicate the bias of the optimal linear fit f lin , show how for large β, kernel learning with the Laplace kernel performs just as well as a linear function. Figure 2b shows the bias curve as a function of β with inputs drawn from P 1 for different choices of n. The bias curves are identical from which we conclude that we already enter the asymptotic regime for d, n as low as d ∼ 50 and n ∼ 2000.
While our theoretical results only show lower bounds on the bias, Figure 2a and 2b suggest that as β increases, the bias in fact stepwise aligns with the best polynomial of lower and lower order. This has also been shown in [17,18] for the uniform distribution from the product of two spheres. Indeed, with decreasing β, for the cubic polynomial in Figure 2b we first learn linear functions (first descent in the curve). Since the best degree 2 polynomial approximation of f * 2 around 0 is a linear function, the curve then enters a plateau before descending to zero indicating that we successfully learn the ground truth. Figure 3 illustrates how the bias depends on the scaling τ for different β with n = 2000. We generate samples using P 1 and the ground truth f 2 and plot the bias of the minimum norm interpolator for the Laplace, exponential inner product and Gaussian kernel. For the latter, the minimum is obtained around τ = d. For the Laplace and exponential inner product kernel, the bias achieves its minimum at the flat limit τ → ∞. Given that our lower bounds hold for both τ = d and τ → ∞ (Theorems 3.1 and 3.3), we hypothesize that there might not exist an intermediate scaling regime for τ that can break the polynomial approximation barrier.

Feature selection for high-dimensional kernel learning
In this section, we demonstrate how the polynomial approximation barrier limits the performance in real world datasets and how one may overcome this issue using feature selection. How our theory motivates feature selection can be most cleanly illustrated for complex ground truth functions that only depend on a number of covariates that is much smaller than the input dimension (which we refer to as sparse) 6 :  Based on our theoretical results we expect that for sparse ground truths, the bias follows a U-shape as dimension increases: until all relevant features are included, the bias first decreases before it then starts to decrease due to the polynomial approximation barrier that holds for large d when asymptotics start to kick in. Since recent work shows that the variance vanishes in high-dimensional regimes (see e.g. [18,27]), we expect the risk to follow a U-shaped curve as well. Hence, performing feature selection could effectively yield much better generalization for sparse ground truth functions. We would like to emphasize that although the described curve may ring a familiar bell, this behavior is not due to the classical bias-variance trade-off, since the U-shaped curve can be observed even in the noiseless case where we have zero variance. We now present experiments that demonstrate the U-shape of the risk curve for both synthetic experiments on sparse ground truths and real-world data. We vary the dimensionality d by performing feature selection 7 using the algorithm proposed in the paper [9]. In order to study the impact of high-dimensionality on the variance, we add different levels of noise to the observations.
For the real-world experiments we are not able to decompose the risk to observe separate trends of the bias and the variance. However, we can argue that the ridge estimator should perform significantly better than the minimum norm interpolator whenever the variance dominates. Vice versa, if their generalization errors are close, the effect of the variance vanishes. This is due to the fact that the ridge penalty decreases the variance and increases the bias. Hence, for real-world experiments, we use the comparison between the risks of the ridge estimator and minimum norm interpolator to deduce that the bias is in fact dominating the risk for high dimensions.
Sparse functions For our synthetic experiments, we draw 500 input samples x 1 , . . . , x n from P 1 and compute the minimum norm interpolator for n = 100 different draws over noisy observations from a sparsely parameterized function y = 0.5 10]). We increase d by adding more dimensions (that are irrelevant for the true function value) and compute the bias and variance of the minimum norm interpolator. We approximate the L 2 (P x ) norm using Monte Carlo sampling from P 1 . In Figure 4a we observe that as we increase the number of selected features, the bias first decreases until all relevant information is included and then increases as irrelevant dimensions are added. This is in line with our asymptotic theory that predicts an increasing bias due to the progressively more restrictive polynomial approximation barrier. Furthermore, the variance monotonically decreases as expected from the literature and hence the risk in follows the U-shaped curve described above.
Real-world data We now explore the applicability of our results on real-world data where the assumptions of the theorems are not necessarily satisfied. For this purpose we select datasets where the number of features is large compared to the number of samples. In this section we show results on the regression dataset residential housing (RH) with n = 372 and d = 107 to predict sales prices from the UCI website [14]. Further datasets can be found in Appendix A.3. In order to study the effect of noise, we generate an additional dataset (RH-2) where we add synthetic i.i.d. noise drawn from the uniform distribution on [−1/2, 1/2] to the observations. The plots in Figure 4 are then generated as follows: we increase the number of features using a greedy forward selection procedure (see Appendix A.3 for further details ). We then plot the risk achieved by the kernel ridge and ridgeless estimate using the Laplace kernel on the new subset of features. Figure 4b shows that the risks of the minimum norm interpolator and the ridge estimator are identical, indicating that the risk is essentially equivalent to the bias. Hence our first conclusion is that, similar to the synthetic experiment, the bias follows a U-curve. For the dataset RB-2 in Figure 4c, we further observe that even with additional observational noise, the ridge and ridgeless estimator converge, i.e. the bias dominates for large d. We observe both trends in other high-dimensional datasets discussed in Appendix A.3 as well. As a consequence, we can conclude that even for some real-world datasets that do not necessarily satisfy the conditions of our bias lower bound, feature selection is crucial for kernel learning for noisy and noiseless observations alike. We would like to note that this conclusion does not necessarily contradict empirical work that demonstrates good test performance of RBFs on other high-dimensional data such as MNIST. In fact, the latter only suggests that linear or polynomial fitting would do just as well for these datasets which has indeed been suggested in [18].

Conclusion and future work
Kernel regression encourages estimators to have a certain structure by means of the RKHS norm induced by the kernel. For example, the eigenvalue decay of α-exponential kernels results in estimators that tend to be smooth (i.e. Gaussian kernel) or more spiky (i.e. small α < 1). A far less discussed fact is that many kernels implicitly incorporate additional structural assumptions. For example, rotational invariant kernels are invariant under permutations and hence treat all dimensions equally Even though rotational invariance is a natural choice when no prior information on the structure of the ground truth is available, this paper shows that the corresponding inductive bias in high dimensions is in fact restricting the average estimator to a polynomial. In particular, we show in Theorems 3.1 and 3.3 that the lower bound on the bias is simply the projection error of the ground truth function onto the space of polynomials of degree at most 2 2/β respectively 2/β . Apart from novel technical insights that result from our unified analysis (discussed in Sec. 3.3), our result also opens up new avenues for future research.
Future work Modern datasets which require sophisticated methods like deep neural networks to obtain good predictions are usually inherently non-polynomial and high-dimensional. Hence, our theory predicts that commonly used rotationally invariant kernels cannot perform well for these problems due to a high bias. In particular, our bounds are independent of properties like the smoothness of the kernel function and cannot be overcome by carefully choosing the eigenvalue decay. Therefore, in order to understand why certain highly overparameterized methods generalize well in these settings, our results suggest that it is at least equally important to understand how prior information can be incorporated to break the rotational symmetry of the kernel function. Examples for recent contributions in this direction are kernels relying on convolution structures (such as CNTK [1,37] or compositional kernels [11,33,39]) for image datasets.
Another relevant future research direction is to present a tighter non-asymptotic analysis that allows a more accurate characterization of the estimator in practice. The presented results in this paper are asymptotic statements, meaning that they do not provide explicit bounds for fixed n, d. Therefore, for given finite n, d it is unclear which high-dimensional regime provides the most accurate characterization of the estimator's statistical properties. For instance, our current results do not provide any evidence whether the estimator follows the bias lower bounds for n = d β with β = log(n)/ log(d) or n = γd. We remark that the methodology used to prove the statements in this paper could also be used to derive non-asymptotic bounds, allowing us to further investigate this problem. However, we omitted such results in this paper for the sake of clarity and compactness of our theorem statements and proofs and leave this for future work.

Acknowledgments
We would like to thank the anonymous reviewers for their helpful feedback, Xiao Yang for insightful discussions on the flat limit kernel and Armeen Taeb for his comments on the manuscript.

A Experiments
This section contains additional experiments not shown in the main text. 8

A.1 Polynomial Barrier
In this section, we provide additional experiments that discuss Theorem 3.1. In particular, we investigate kernels beyond the Laplace kernel and study the behaviour of the bias with respect to β when d is fixed and n varies. The experimental setting is the same as the one in Section 4.2.
Instead of comparing the bias curves for different input distribution as in Figure 2a, Figure 5 shows the bias with respect to β for the α-exponential kernel, i.e. k(x, x ) = exp(− x − x α 2 ), for different choices of α and hence for kernels with distinct eigenvalue decays (α = 2 results in an exponential eigenvalue decay while α < 2 in a polynomial eigenvalue decay). Clearly, we can see that the curves transition at a similar value for β which confirms the the discussion of Theorem 3.1 in Section 3.3 where we argue that the polynomial approximation barrier occurs independently of the eigenvalue decay. Figure 6 shows the bias of the minimum norm interpolant B(f 0 ) normalized by B(0) for the ground truth function f (x) = 2x 3 (1) and the Laplace kernel as in Section 4.2 with τ = d eff . We observe that the asymptotics already kick in for d ≈ 40 since all curves for d ≥ 40 resemble each other. This confirms the the trend in Figure 2b.

A.2 Feature selection -Synthetic
The goal of this experiment is to compare the bias variance trade-off of ridge regression and minimum norm interpolation. We use the same experimental setting as the ones used for Figure 4a (see Section 4.3). We set the bandwidth to τ = d eff and choose the ridge parameter λ using 5-fold cross validation. While for small dimensions d, ridge regularization is crucial to achieve good performance, the bias becomes dominant as the dimension grows and the difference of the risks of both methods shrinks. This aligns well with Theorem 3.1 which predicts that the bias starts to increase with d for fixed n once we enter the asymptotic regime.

A.3 Feature selection -Real world
We now present details for our real world experiments to emphasize the relevance of feature selection when using kernel regression for practical applications, as discussed in Section 4.3.
We consider the following data sets: 1. The residential housing regression data set from the UCI website [14] where we predict the sales prices and construction costs given a variety of features including the floor area of the building or the duration of construction.
2. The ALLAML classification data set from the ASU feature selection website [26] where we classify patients with acute myeloid leukemia (AML) and acute lymphoblastic leukemia (ALL) based on features gained from gene expression monitoring via DNA microarrays.
3. The CLL SUB 111 classification dataset from the ASU feature selection web-page [26] where we classify genetically and clinically distinct subgroups of B-cell chronic lymphocytic leukemia (B-CLL) based on features consisting of gene expressions from high density oligonucleotide arrays. While the original dataset contains three different classes, we only use the classes 2 and 3 for our experiment to obtain a binary classification problem.
Because the number of features in the ALLAML and CLL SUB 111 datasets massively exceed the number of samples, we run the feature selection algorithm in [9] and pre-select the best 100 features chosen by the algorithm. In order to reduce the computational expenses, we run the algorithm in batches of 2000 features and iteratively remove all features except for the best 200 features chosen by the algorithm. We do this until we reduce the total number of features to 2000 and then select in a last round the final 100 features used for the further procedure. Reducing the amount of features to 100 is important for the computational feasibility of greedy forward features selection in our experiments. The properties of the datasets are summarized in Table 2  The value in the brackets shows the number of features after a pre-selection using the algorithm presented in [9].
Experimental setting: As a first step, we normalise both the vectors containing the single input features and the observations separately using 1 normalization. We use the Laplace kernel for computing the ridge and ridgeless estimate in all experiments. For each setting, we pick the bandwidth τ and the penalty coefficient λ (for the ridge estimator) using cross validation. We increase the number of features by greedily adding the feature that results in the lowest 5-fold cross validation risk. In addition, in order to study the effect of noise, we generate additional data sets where we add synthetic i.i.d. noise drawn from the uniform distribution on [−1/2, 1/2] to the observations for the regression tasks and flip 20% of the label for the classification tasks.

Results of the experiments:
The following figures present the results of our experiments on all datasets except for the ones predicting the sales prices in the residential housing dataset, which we presented in Figure  4b,4c in the main text. Similar to the observations made in Section 4.3, Figure 8,9,10 show that the risk reaches its minimum around d ≈ 25, with significant differences to the right at d ≈ 100. In particular, this holds for both ridge regression and interpolation, which again shows that the bias becomes dominant as the dimension increases. Surprisingly, we also note that the relevance of ridge regularization seems to be much smaller for classification tasks than regression tasks.

B Bounded Hilbert norm assumption
This section gives a formal statement of Lemma 2.1. We begin with the conditions under which the lemma holds. We consider tensor product kernels of the form with inputs x, x ∈ X ⊗d ⊂ R d with X compact and ⊗d denotes the product space, for some kernel function q on X which may change with d (e.g. the scaling). In order to prevent the sequence of kernels k to diverge as d → ∞, assume that there exists some probability measure on X with full support such that the trace of the kernel operator is bounded by 1, i.e. q(x, x)dµ(x) ≤ 1. Let . H k be the Hilbert norm induced by k. Then, Lemma B.1 (Formal statement of Lemma 2.1). Let k satisfy the above conditions. Then, for any f that is a non-constant sparsely parameterized product function Proof. For any j > m, define f j = 1. First, we note that the proof follows trivially if any of the f j is not contained in the RKHS induced by q since this implies that the Hilbert norm f H k = ∞. Hence, we can assume that for all j, f j is contained in the RKHS for all d. Furthermore, because k is a product kernel, we can write f H k = d j=1 f j Hq where . Hq is the Hilbert norm induced by q on X . Because we are only interested to see whether the sequence of Hilbert norms diverge, without loss of generality we can assume that m = 1, and hence, Next, by Mercer's theorem there exists an orthonormal eigenbasis . Note that because the kernel q depends on d, λ i and φ i also depend on d. Next, because by assumption f (x) = 1 is contained in the RKHS, there exists α i such that for every x ∈ X , 1 = Combining these results, we get that . Again, because we are only interested to see whether the sequence of Hilbert norms diverge, without loss of generality we can assume that ∞ i=1 β 2 i = 1 and hence also f j Hq ≥ 1.
First, assume that there exists a subsequence such that 1 Hq → 1. This implies that there exists a sequence j d ∈ N such that α 2 j d → 1 and λ j d → 1. Next, because by assumption f 1 = 1, there exists some constant c 1 > 0 such that for all d, Together with the fact that α 2 j d → 1 it then follows that i =j d β 2 i has to be asymptotically lower bounded by some positive non-zero constant c 2 and hence This contradicts the assumption that f 1 Hq is upper bounded by some constant for every d. Hence, we are only left with the case where 1 Hq ≥ c > 1, however, this case diverges due to Equation 9. Hence, the proof is complete.

C Proof of Theorem 3.1
Before presenting the proof of the (generalized) theorem, we first state the key concentration inequalities used throughout the proof. It is an extension of Lemma A.2 in the paper [15], which iteself is a consequence of the concentration of Lipschitz continuous functions of i.i.d random vectors.
Lemma C.1. For any P X ∈ Q or Q S d−1 , let X ∈ R d×n consists of i.i.d. vectors x i ∼ P X and X ∼ P X be independent of x i . For any constants > 0, define the events Then, there exists some constant C > 0 such that for n sufficiently large, and P(E X|X |E X ) ≥ 1 − (n + 1) 2 exp(−C(log(n)) (1+ ) ) (13) In particular, the event E X holds almost surely with respect to the sequence of data sets X as n → ∞, that is the probability that for infinitely many n, E X does not hold, is zero.
The proof of the lemma can be found in Section E.1.

Proof of Theorem 3.1. The proof of the Theorem is primarily separated into two parts
• We first state Theorem C.2 which shows under the weaker Assumption C.1 that the results of 3.1 hold for the ridge estimatef λ for non-vanishing λ > 0 or the ridgeless estimate whenever the eigenvalues of K are asymptotically lower bounded.
• We finish the proof for the ridgeless estimate by invoking Theorem C.2 and showing that K indeed has asymptotically lower bounded eigenvalues under the stricter assumptions A.1-A.3 imposed in Theorem 3.1.
We start by introducing the following weaker assumptions that allows us to jointly treat α-exponential kernels and kernels satisfying Assumption A.1-A.3 when the kernel eigenvalues are lower bounded in Theorem C.2. Note that this assumption implies that the kernel is rotationally invariant.
The kernel function k is rotationally invariant and there exists a function g such that k(x.x ) = g( x 2 2 , x 2 2 , x x ). Furthermore, g can be expanded as a power series of the form (14) with m = 2/β that converges in a neighborhood N (δ, δ ) of the sphere for some δ, δ > 0 and where g i is ( 2/β + 1 − i)-times continuously differentiable in an neighborhood of (1, 1) and the remainder term r is a continuous function around the point (1, 1, 0).

Theorem C.2 (Polynomial approximation barrier).
Assume that the kernel k, respectively its restriction onto the unit sphere, satisfies Qssumption C.1 and that the eigenvalues of K + λI n are almost surely lower bounded by a positive constant with respect to the sequence of datasets X as n → ∞. Furthermore, assume that the ground truth f is bounded and the input distribution satisfies B.1-B.2. Then, for m = 2 2/β for P X ∈ Q and m = 2/β for P X ∈ Q S d−1 , the following results hold for both the ridge (1) and ridgeless estimator (2)f λ wiht λ ≥ 0.
1. The bias of the kernel estimatorsf λ is asymptotically lower bounded, for any > 0, 2. We can find a polynomial p such that for any , > 0, there exists C > 0 such that asymptotically with probability ≥ 1 − n 2 exp(−C(log(n)) 1+ ) over the draws of X, Furthermore, for bounded kernel functions on the support of P X the averaged estimator E Yfλ converges in L 2 (P X ) to a polynomial p ∈ P ≤m , The proof of this theorem can be found in Section C.1. Theorem C.2 states Theorem 3.1 under the assumption that (K + λI) has asymptotically lower bounded eigenvalues and the weaker Assumption C.1. Remark C.5. The almost sure statement in Proposition C.4 can also be replaced with an in probability statement as in Lemma C.1 and hence also the statements in Theorem 3.1.

C.1 Proof of Theorem C.2
As a result of Lemma C.1 it is sufficient to condition throughout the rest of this proof on the intersection of the events E X and the event where the eigenvalues of the kernel matrix K are lower bounded by a positive constant.
For simplicity of notation, we define z i = xi √ τ and let Z be the d × n matrix with column vectors z i . Define the random variable Z = X/ √ τ with X ∼ P X and denote with P Z the probability distributed of Z. Define the event E Z|Z in the same way as E X|X for the normalised inputs z i , Z and E Z like E X . In the latter, we denote with a b that there exists a constant C > 0 such that a ≤ Cb with C independent of n, d. Furthermore, we make heavily use of the closed form solution for the estimatorf λ , . This equation holds true for any λ ≥ 0 and is a well known consequence of the representer theorem.
The idea of the proof is to decompose the analysis into the term emerging from the error in the high probability region E Z|Z and the error emerging from the low probability region E c Z|Z . The proof essentially relies on the following lemma.
Lemma C.6. We can construct a polynomial p of degree ≤ m such that for n → ∞, The proof of the lemma can be found in Section E.

As a result, Equation 16 follows immediately and Equation 17 is a consequence of
The first two terms vanish due to Lemma C. 6. To see that the third term vanishes, note that for n sufficiently large, where we have used in the first inequality that by assumption |f | is bounded on the support of P X and that λ min (K + λI n ) ≥ c min > 0 and in the second inequality that |k| is bounded. Finally, the convergence to zero is due Lemma C.1. Next, the lower bound for the bias. Due to Lemma C.8, we have that and hence, for any γ 1 > 0 and n sufficiently large, Furthermore, due to the second statement in Lemma C.8, we know that E Z 1 Z / ∈E Z|Z (p(Z)) 2 → 0 and because f is bounded by assumption, we can see that Thus, as a result, for any γ 2 > 0, Thus, the result follows from the definition of the infimum.
C.2 Proofs for the lower bound of the eigenvalues We use the same notaiton as used in the proof of Theorem C.2. As a result of Lemma C.1 it is sufficent to condition on E X throughout the rest of this proof. The proof follows straight forwardly from the following Lemma C.7 which gives an asymptotic description of the kernel matrix K based on a similar analysis as the one used in the proof of Theorem 2.1 and 2.2 in the paper [15]. In essence, it is again a consequence of the concentration inequality from Lemma C.1 and the stronger Assumption A.1-A.3 and in particular the power series expansion of g. We denote with •i the i-times Hadamard product.
Lemma C.7. Given that the assumption in Proposition C.3 hold. For m = 2/β , where G gq is the positive semi-definite matrix with entries (G gq ) i,j = g l ( z i 2 2 , z j 2 2 ). The proof of the lemma can be found in Section E.3. The proof of Proposition C.3 then follows straight forwardly when using Schur's product theorem which shows that where we use that g i is positive semi-definite by Assumption A.1. To see that the eigenvalues are lower bounded, we thus simply need to show that g(1, 1, 1) − m q=0 g q (1, 1) > 0. This holds because the positive semi-definiteness of g q implies that g q (1, 1) ≥ 0 and hence g(1, 1, 1) = ∞ q=0 g q (1, 1) is a sum of positive coefficients and because by Assumption A.3 there exists j > 2/β such that g j (1, 1) > 0. Hence, there exists a positive constant c > 0 such that λ min (M ) ≥ c. We can conclude the proof when applying Lemma C.7, which implies that λ min (K) → λ min (M ) as n → ∞.

C.2.2 Proof of Proposition C.4
We use the same notaiton as used in the proof of Theorem C.2 and define D α to be the n × n matrix with entries (D α ) i,j = d α (z i , z j ) := z i − z j α 2 . We separate the proof into two steps. In a first step, we decompose k in the terms x )) and exp(k(x, x )) are both positive semi-definite kernel functions. In particular, we construct k such that the eigenvalues of the kernel matrix A of exp(k(x, x )) evaluated at Z are almost surely lower bounded by a positive constant. The proposition is then a straight forward consequence and shown in the last step.
Step 1: We can see from Chapter 3 Theorem 2.2 in [5] that d α is a conditionally negative semi-definite function, that is that for any m ∈ N \ 0 and any {x 1 , ..., x m }, the corresponding kernel matrix A is conditionally negative semi-definite. A matrix A is conditionally negative semi-definite if for every v ∈ R n with 1 v = 0, v Av ≤ 0. As shown in Chapter 3 Lemma 2.1 in [5], a kernel function φ(x, x ) is conditionally negative semi-definite, if and only if for any z 0 , (x, is a positive semi-definite function. Hence, for any z 0 ∈ R n , the kernel defined bỹ is positive semi-definite. The goal is now to show that we can find a vector z 0 such that the kernel matrix A ofk evaluated at Z has eigenvalues almost surely lower bounded by some positive constant. Essentially, the statement is a consequence of the following lemma, bounding the eigenvalues of D α .
Lemma C.8. Assume that P X satisfies the Assumption B.1-B.2. Conditioned on E X , for any n sufficiently large, all eigenvalues of the matrix D α are bounded away from zero by a positive constant c > 0, i.e. min The proof of the lemma can be found in Section E.4. In particular, note that we can use the same argument as used in Lemma C.1 to show that there exists almost surely over the draws of Z as n → ∞ an additional vector z 0 , such that for any two vectors z, z ∈ Z ∪ {z 0 }, Throughout the rest of this proof, we conditioned on the event E X and the additional event that Equation (21) holds, and remark that the intersection of these two events holds true almost surely as n → ∞. It is then straight forward to show that the eigenvalues of the matrix are also bounded away from zero by a positive constantc > 0. Therefore, for any v ∈ R n , where we have used that 1 T v T −1 v = 0. As a result, we can see that where A is exactly the kernel matrix ofk evaluated at Z. Hence, combining Equation (22) and (23) gives We can conclude the first step of the proof when applying the Courant-Fischer-Weyl min-max principle which shows that A has lower bounded eigenvalues ≥c.
Step 2: We can write exp . It is straight forward to verify that exp(φ(x, x )) is a positive semi-definite function. Hence, due to Schur's product theorem, the following sum is a sum of positive semi-definite functions It is sufficient to show that the eigenvalues of the kernel matrix M ofk(x, x ) exp(φ(x, x )), evaluated at Z, are lower bounded. Let B be the kernel matrix of exp(φ(x, x )) evaluated at Z, we have that M = A • B, where • is the Hadamard product and A the kernel matrix ofk from the previous step. We make the following claim from which the proof follows trivially using the fact shown in the first step that the eigenvalues of A are lower bounded by a positive constant.

C.3 Proof of Corollary 3.2
First, note that the Assumption A.1-A.3 straight forwardly hold true for the exponential inner product kernel with k(x, x ) = exp(x x ) = ∞ j=0 1 j! (x x ) j and for the Gaussian kernel with Next, note that the α-exponential kernel with α < 2 is already explicitly covered in Theorem 3.1. Hence, the only thing left to show is that Theorem 3.1 also applies to ReLU-NTK. We use the definition of the Neural Tangent Kernel presented in [1,24]. Let L be the depth of the NTK and σ : R → R the activation function which is assumed to be almost everywhere differentiable. For any i > 0, define the recursion whereσ is the derivative of σ. The NTK k NTK of depth L ≥ 1 is then defined as We call a function σ k-homogeneous, if for any x ∈ R and any a > 0, σ(ax) = a k σ(x). We can now show the following result from which the corollary follows.
Proposition C.9. Assume that the activation function σ is k-homogeneous and both the activation function and its derivative possess a Hermite-polynomial series expansion (see [11]) where there exits j ≥ 2/β such that the j -th coefficient a j = 0. Then, the NTK satisfies the Assumption A.1-A.3 and hence Theorem 3.1 applies.
In fact, we can easily see that any non linear activation function which is homogeneous and both the activation function and its derivative possesses a Hermite polynomial extension satisfies the assumptions in Proposition C.9. In particular, this includes the popular ReLU activation function σ(x) = max(x, 0) where the explicit expression for the Hermite polynomial extension can be found in [11].

C.3.1 Proof of Proposition C.9
Essentially, the proof follows from the power series expression of the NTK k NTK given in the following lemma.
Lemma C.10. The NTK k NTK possesses a power series expansion which converges for any x, x ∈ R d with x, x = 0. Furthermore, for any u, u ∈ R + , and η j,i ≥ 0.
The proof of the lemma can be found in Section E.5. It is straight forward to verify from the proof of Lemma C.10 that Σ (i) andΣ (i) are compositions of continuous functions and thus k NTK is also continuous for any x, x = 0. Next, note that the Lipschitz continuity (Assumption A.2) follows straight forwardly from Equation (31) in the proof of Lemma C.8. In order to show that any g j from Lemma C.10 is smooth, recall that Therefore, h j is a Puiseux power series with divisor 2. Furthermore, the functionh j (t) : (t) l is a Laurent series which converges for every t = 0. Hence, we can conclude thath j is smooth for any t = 0 and thus also h j . Finally, because (u, u ) → uu is trivially also a smooth function, we can conclude that any g j is a smooth function for any u, u = 0. Next, since for any l ∈ Z, (u, u ) → α(uu ) l/2 is trivially a positive semi-definite (PSD) function whenever α ≥ 0 and sums of PSD functions are again PSD, we can conclude that the g j (u, u ) = ∞ l=−∞ η (i+1) j,l (uu ) l/2 is PSD for any j. Therefore, we can conclude that Assumption A.1 holds as well.
The only thing left to show is Assumption A.3. While we have already shown that g j are smooth in a neighborhood of (1, 1), we still need to show that there exists j > 2/β such that g j (1, 1) > 0. However, this follows from the fact that by assumption there exists j > 2/β such that a j = 0 where a j are the Hermite coefficients of the activation function σ.

D Different scalings τ
In this section, we present results for different choices of the scaling beyond the standard choice τ d eff . In Subsection D.1, we give a proof of Theorem 3.3 describing the flat limit, i.e. the limit of the interpolant where for any fixed n, d, τ → ∞. Furthermore, in order to get a more comprehensive picture, we additionally present straight forward results for other choices of τ in Section D.2.

D.1 Proof of Theorem 3.3
We use again the same notation as used for the proof of Theorem C.2 where we set z i = x i / √ d eff and let Z = X/ √ d eff be the random variable with X ∼ P X . We can again condition throughout the proof on the event E X . In particular, we assume throughout the proof that n is sufficiently large since we are only interested in the asymptotic behaviour. Furthermore, recall the definition of D α , which is the n × n matrix with entries (D α ) i,j = z i − z j α 2 and denote with D −1 α its inverse. In addition, denote with d α Z the vector with entries (d α Z ) i = z i − Z α 2 and with d α the function d α (z, z ) = z − z α 2 . First, although the limit lim τ →∞ K −1 does not exists, we can apply Theorem 3.12 in [25] to show that the flat limit interpolator f FL := lim τ →∞f0 of any kernel satisfying the assumption in Theorem 3.3 exists and has the form Furthermore, for the α-exponential kernel, we use Theorem 2.1 in [6] to show that it satisfies the assumptions imposed on the eigenvalue decay in Theorem 3.3.
Remark D. 1. The estimator f FL is also called the polyharmonic spline interpolator. This estimator is invariant under rescalings of the input data which is also the reason why we can rescale the input data by d eff , i.e. consider z i = x i / d eff as input data points.
We already know from lemma C.8 that the matrix D α has n − 1 negative eigenvalues and one positive eigenvalue. In particular, we have shown that |λ i (D α )| ≥c > 0, for i, wherec is some positive constant. Next, note that because D α has full rank, we can conclude from Theorem 3.1 in [20] that the matrix −D α 1 1 T 0 has n positive eigenvalues and one negative. Hence, In particular, this allows us to use the block matrix inverse to show that and therefore, Next, using the Binomial series expansion, we can see that for any q ∈ N, Furthermore, by Lemma C.1 and the fact that z i − Z 2 2 = z i z i + Z Z − 2z i Z, we can see that for q = 2/β , Hence, assuming that the absolute eigenvalues |λ i (A)| of A are all upper bounded by a non-zero positive constant, we can use exactly the same argument as used in the proof of Theorem C.2 to conclude the proof. Thus, we only need to show that the eigenvalues |λ i (A)| are upper bounded. We already know from Lemma C.8 that there exists some constant c > 0 independent of n, such that D −1 α op ≤ c. Thus, we only need to show that is almost surely upper bounded. Because is a rank one matrix, we know that First, we show that 1 T D −2 α 1 = O(1) Let λ 2 , ..., λ n be the n − 1 negative eigenvalues of D −1 α and λ 1 the only positive eigenvalue. Furthermore, let v i be the corresponding orthonormal eigenvectors. Next, let α i ∈ R be such that 1 = n i=1 α i v i . Since 1 2 = √ n, we know that α i ≤ √ n. Then, where we use that 1 T D −1 α 1 > 0 which we already know from the discussion above. Because by the binomial n, for any n sufficiently large. Therefore, λ 1 ≥ n. Hence, there exists some constant c > 0 independent of n, such that α 2 1 1 λ1 ≤ c. As a consequence, where we use in the last inequality that |λ i | ≥c. Furthermore, α 2 In order to prove the result, we are only left to study the case where 1 T D −2 α 1 ≥ 1 T D −1 α 1 → 0. We prove by contradiction and assume that . We know that 1 T (v +ṽ) = 0 and hence, Next, note that our assumption imply that for n sufficiently large, v v − γ 2 ≥ 1/2v v . Therefore, and using the fact that γ = 1 T D −1 α 1 is positive, we get that 1 ≥c 2 v T v γ . However, this contradicts the assumption that v T v γ → ∞ and hence we can conclude the proof.

D.2 Additional results
In this section, we present some additional results for different choices of the scaling. The results presented in this section are straight forward but provide a more complete picture for different choices of the scaling τ . We use again the same notation as used in Appendix C.1. First, we show the case where τ → 0. We assume that k is the α-exponential kernel with α ∈ (0, 2], i.e. k(x, x ) = exp(− x − x α 2 ). Lemma D.2. Let P X satisfy Assumption B.1-B.2 and assume that the bandwidth τ /d eff = O(n −θ ) with θ > 0. Furthermore, assume that the ground truth function f is bounded. Then, conditioned on the event E X , for any λ ≥ 0, with probability ≥ 1 − (n + 1) 2 exp(−C(log(n)) 1+ ) over the draws of X ∼ P X , In fact, due to the assumption thatτ = O(n −θ ) with θ > 0, we can see that and with probability ≥ 1 − (n + 1) 2 exp(−C(log(n)) 1+ ) over the draws of X, Hence, the result follows immediately fromf λ (X) = y T (K + λI) −1 k τ (X, X).
We can also show a similar result for the case where τ → ∞ and λ does not vanish.
Lemma D.3. Let P X satisfy Assumption B.1-B.2 and assume that the bandwidth τ /d eff = O(n θ ) with θ > 2 α . Furthermore, assume that λ = Ω(1) and that the ground truth function f is bounded. Then, conditioned on the event E X , for any λ ≥ 0, with probability ≥ 1 − (n + 1) 2 exp(−C(log(n)) 1+ ) over the draws of X ∼ P X , with c = f (X) T (11 T + λI n ) −1 1 Proof. We use the same notation as in Lemma D.3. Again due to Lemma C.1, we find that As a result, we observe that the kernel matrix K converges asymptotically to the rank one matrix 11 T . We remark that such a phenomenon can also be observed in Theorem 2.1 and 2.2 in [15] when tr(Σ d )/d → 0. As a consequence, we observe that the eigenvalues of K −1 diverge as n → ∞. However, because by assumption, λ = Ω(1), we can still conclude that the eigenvalues of (K + λI n ) −1 are upper bounded by a constant independent of n. Hence, with probability ≥ 1 − (n + 1) 2 exp(−C(log(n)) 1+ ) over the draws of X ∼ P X , where we have used that θα/2 > 1.
E Technical lemmas E.1 Proof of Lemma C.1 We begin with the following Lemma, which is a direct consequence of the results in Appendix A in [15]. Case 1: Distribution P X ∈ Q Following the same argument as the one used in Corollary A.2 in [15], we can use Lemma E.1 to show that there exists constants C 2 , C 3 > 0 such that for n → ∞, We now make us of the Borel-Cantelli Lemma. For any > 0, let r(n) = 1 √ 2 n −β/2 (log(n)) (1+ )/2 and note that because tr(Σ d ) n β , ζ decays at rate n −β and in particular, for any n sufficiently large, r(n)/2 > ζ → 0. Hence, we can see that there exists some constant C > 0 such that for any n sufficiently large Next, using the union bound, we get And because > 0, for any N ∈ N + , we have that ∞ n=N n 2 exp(−C (log(n)) 1+ ) < ∞.
The rest of the proof then follows straight forwardly. We know that f is λ max (M + )/ tr(M + )-Lipschitz continuous and hence also a ||M || op / tr(M + )-Lipschitz continuous. For the case where the entries x are bounded i.i.d. random variables, we can use the simple fact that the norm is convex in order to apply Corollary 4.10 in [23] and Proposition 1.8 in in [23]. For the case where the entries are normally distributed we can apply Theorem V.I in [34]. As a result, we can see that there exists a constant C 4 > 0 independent of M , such that The proof then follows straight forwardly following line by line the proof of Lemma A.2 in [15].
As a result, we can make use of Assumption C.1. We are heavily going to make use of this fact throughout the proof. The proof is separated into two steps where we first show 1. and then 2. using the expression for p from the first step. (1, 1) where η l,i l1,l2 ∈ B r (1, 1) are points contained in the closed ball around the point (1, 1) with radius r 2 = ( z i 2 2 − 1) 2 + ( Z 2 2 − 1) 2 → 0. Hence, using the fact that g i is s + 1 − i-times continuously differentiable, we can see that any g (l1,l2) l (η l,i l1,l2 ) is almost surely upper bounded by some constant. Let v Z be the vector defined in Equation (25) We define the polynomial p as p(Z) := f (X) (K + λI n ) −1 v Z Note that p is a linear combination of the terms (Z Z) p1 (z i Z) p2 with p 1 + p 2 ≤ s, and hence a polynomial of Z of degree at most 2s. If g l are constant, i.e. the kernel is an inner product kernel, v Z contains only the terms (z i Z) l and hence p(Z) is a polynomial of Z of degree at most s.
Next, because by assumption |f | ≤ C f is bounded on the support of P X by some constant C f , all entries of f (X) are bounded, and hence, where we have used that E Yfλ ( √ τ Z) = f (X) (K + λI n ) −1 k Z . Further, by assumption λ min (K + λI n ) ≥ c min > 0, and hence, Equation (25) yields In order to conclude the first step of the proof, we only need to show that both terms go to zero. First, we show that the term n max i B i 1 → 0. Recall that g (l1,l2) q (η q,i l1,l2 ) is upper bounded as n → ∞ independent of i. Hence, we can apply Lemma C.1 which shows that for any integers q, l 1 and l 2 such that q + l 1 + l 2 = s + 1, where we have used that by assumption g is δ L -Lipschitz continuous on the restriction {(x, x, x)|x ∈ [1 − δ L , 1 + δ L ]} ⊂ Ω for some δ L > 0. Clearly T 1 → 0 due to Lemma C.1. Furthermore, by Assumption C.1, for any q ≤ m, g q is continuously differentiable and hence also Lipschitz continuous in a closed ball around (1, 1). Thus, T 3 → 0. Hence, it is only left to show that T 2 → 0, which is a consequence of the following claim.
Proof of the claim: In order to prove the claim, recall that due to Lemma C.1, for every q > 0 We prove the claim by induction. The case where q = 1 holds trivially with c 1 = 1. For q > 1, q−j ≤ (n −β/2 (log(n)) (1+ )/2 ) q .