Year: 2021

Abstract:
An interesting observation in artificial neural networks is their favorable generalization error despite typically being extremely overparameterized. It is well known that the classical statistical learning methods often result in vacuous generalization errors in the case of overparameterized neural networks. Adopting the recently developed Neural Tangent (NT) kernel theory, we prove uniform generalization bounds for overparameterized neural networks in kernel regimes, when the true data generating model belongs to the reproducing kernel Hilbert space (RKHS) corresponding to the NT kernel. Importantly, our bounds capture the exact error rates depending on the differentiability of the activation functions. In order to establish these bounds, we propose the information gain of the NT kernel as a measure of complexity of the learning problem. Our analysis uses a Mercer decomposition of the NT kernel in the basis of spherical harmonics and the decay rate of the corresponding eigenvalues. As a byproduct of our results, we show the equivalence between the RKHS corresponding to the NT kernel and its counterpart corresponding to the Matérn family of kernels, showing the NT kernels induce a very general class of models. We further discuss the implications of our analysis for some recent results on the regret bounds for reinforcement learning and bandit algorithms, which use overparameterized neural networks.

heading: 1 INTRODUCTION
text: Neural networks have shown an unprecedented success in the hands of practitioners in several fields. Examples of successful applications include classification (Krizhevsky et al., 2012; LeCun et al., 2015) and generative modeling (Goodfellow et al., 2014; Brown et al., 2020). This practical efficiency has accelerated developing analytical tools for understanding the properties of neural networks. A long standing dilemma in the analysis of neural networks is their favorable generalization error despite typically being extremely overparameterized. It is well known that the classical statistical learning methods for bounding the generalization error, such as Vapnik–Chervonenkis (VC) dimension (Bartlett, 1998; Anthony & Bartlett, 2009) and Rademacher complexity (Bartlett & Mendelson, 2002; Neyshabur et al., 2015), often result in vacuous bounds in the case of neural networks (Dziugaite & Roy, 2017).
Motivated with the problem mentioned above, we investigate the generalization error in overparameterized neural networks. In particular, let Dn = {(xi, yi)}ni=1 be a possibly noisy dataset collected from a true model f : yi = f(xi) + i, where i are well behaved zero mean noise terms. Let f̂n be the learnt model using a gradient based training of an overparameterized neural network on Dn. We are interested in bounding |f(x)− f̂n(x)| uniformly at all test points x belonging to a particular domain X . A recent line of work has shown that gradient based learning of certain overparameterized neural networks can be analyzed using a projection on the tangent space at random initialization. This leads to the equivalence of the solution of the neural network model to a kernel ridge regression, that is a linear regression in the possibly infinite dimensional feature space of the corresponding kernel. The particular kernel arising from this approach is called the neural tangent (NT) kernel (Jacot et al., 2018). This equivalence is based on the observation that, during training, the parameters of the neural network remain within a close vicinity of the random initialization. This regime is sometimes referred to as lazy training (Chizat et al., 2019).

heading: 1.1 CONTRIBUTIONS
text: Here, we summarize our contributions. We propose the maximal information gain (MIG), denoted by γk(n), of the NT kernel k, as a measure of complexity of the learning problem for overparameterized neural networks in kernel regimes. The MIG is closely related to the effective dimension of the kernel (for the formal definition of the MIG and its connection to the effective dimension of the kernel, see Section 4). We provide kernel specific bounds on the MIG of the NT kernel. Using these bounds, for networks with infinite number of parameters, we analytically prove novel generalization error bounds decaying with respect to the dataset size n. Furthermore, our results capture the dependence of the decay rate of the error bound on the smoothness properties of the activation functions.
Our analysis crucially uses Mercer’s theorem and the spectral decomposition of the NT kernel in the basis of spherical harmonics (which are special functions on the surface of the hypersphere; see Section 3). We derive bounds on the decay rate of the Mercer eigenvalues (referred to hereafter as eigendecay) based on the differentiability of the activation functions. These eigendecays are obtained by careful characterization of a recent result relating the eigendecay to the asymptotic endpoint expansions of the kernel, given in (Bietti & Bach, 2020). In particular, we consider s − 1 times differentiable activation functions as(u) = (max(0, u))s, s ∈ N. We show that, with these activation functions and a d dimensional hyperspherical support, the eigenvalues λi of the corresponding NT kernel decay at the rate λi ∼ i− d+2s−2 d−1 1 (up to certain parity constraints on i in special cases; see Section 2 for details).
We then use the eigendecay of the NT kernel to establish novel bounds on its MIG, which are of the form γk(n) = Õ(n d−1 d+2s−2 ). Then, we show this implies high probability error bounds of the form supx∈X |f(x) − f̂n(x)| = Õ(n −2s+1
2d+4s−4 ), when f belongs to the corresponding reproducing kernel Hilbert space (RKHS), and Dn is distributed over X in a sufficiently informative way. In particular, we consider a Dn that is collected sequentially in a way that maximally reduces the uncertainty in the model. That results in a quasi-uniform dataset over the entire domain X (see Section 5.2 for details). A summary of our results on MIG and error bounds is reported in Table 1.
As a byproduct of our results, we show that the RKHS of the NT kernel with activation function as(.) is equivalent to the RKHS of a Matérn kernel with smoothness parameter ν = s − 12 . This result was already known for a special case. In particular, Geifman et al. (2020); Chen & Xu (2021) recently showed the equivalence between the RKHS of the NT kernel with ReLU activation function, a1(.), and that of the Matérn kernel with ν = 12 (also known as the Laplace kernel). Our contribution includes generalizing this result to the equivalence between the RKHS of the NT kernel under various activation functions and that of a Matérn kernel with the corresponding smoothness (see Section 3.2). We note that the members of the RKHS of Matérn family of kernels can uniformly approximate almost all continuous functions (Srinivas et al., 2010). Therefore, our results suggest that the NT kernels induce a very general class of models.
As an intermediate step, we also consider the simpler random feature (RF) model which is the result of partial training of the neural network. Also referred to as conjugate kernel or neural networks Gaussian process (NNGP) (Cho & Saul, 2009; Daniely et al., 2016; Lee et al., 2018; de G. Matthews et al., 2018), this model corresponds to the case where only the last layer of the neural network is trained (see Section 2 for details).
We note that the decay rate of the error bound is faster in the case of RF kernel with the same activation function. Also, the decay rate of the error bound is faster when s is larger, for both NT and RF kernels. In interpreting these results, we should however take into account the RKHS of the corresponding kernels. The RKHS of the RF kernel is smaller than the RKHS of the NT kernel. Also, when s is larger, the RKHS is smaller for both NT and RF kernels.
In Section 6, we provide experimental results on the error rate for synthetic functions belonging to the RKHS of the NT kernel, which are consistent with the analytically predicted behaviors.
Our bounds on MIG may be of independent interest. In Section 7, we comment on the implications of our results for the regret bounds in reinforcement learning (RL) and bandit problems, which use overparameterized neural network models (e.g., Yang et al., 2020; Gu et al., 2021).

heading: 2 OVERPARAMETERIZED NEURAL NETWORKS IN KERNEL REGIMES
text: In this section, we briefly overview the equivalence of overparameterized neural network models to kernel methods. It has been recently shown that, in overparameterized regimes, gradient based training of a neural network reaches a global minimum, where the weights remain within a close vicinity of the random initialization (Jacot et al., 2018). In particular, let f(x,W ) denote a neural network with a large width m parameterized by W . The model can be approximated with its linear projection on the tangent space at random initialization W0, as
f(x,W ) ≈ f(x,W0) + 〈W −W0,∇W f(x,W0)〉. The approximation error can be bounded by the second order term ξm‖W −W0‖2, and shown to be diminishing as m grows, where ξm is the spectral norm of the Hessian matrix of f (Liu et al., 2020). The approximation becomes an equality when the width of the hidden layers approaches infinity. Known as lazy training regime (Chizat et al., 2019), this model is equivalent to the NT kernel (Jacot et al., 2018), given by
k(x, x′) = lim m→∞ 〈∇W f(x,W0),∇W f(x′,W0)〉.

heading: 2.1 NEURAL KERNELS FOR A 2 LAYER NETWORK
text: Consider the following 2 layer neural network with width m and a proper normalization
f(x,W ) = c√ m m∑ j=1 vja(w > j x), (1)
where a(.) is the activation function, c is a constant, x ∈ X is a d dimensional input to the network, wj ∈ Rd are the weights in the first layer, and vj ∈ R are the weights in the second layer. The weights wj are initialized randomly according to N (0d, Id) and vj are initialized randomly according to N (0, 1). Then, the NT kernel of this network can be expressed as (Jacot et al., 2018)
kNT(x, x ′) = c2(x>x′)Ew∼N (0d,Id)[a ′(w>x)a′(w>x′)] + c2Ew∼N (0d,Id)[a(w >x)a(w>x′)]. (2)
When wj are fixed at initialization, and only vj are trained with `2 regularization, the model is equivalent to a certain Gaussian process (GP) (Neal, 2012) that is often referred to as a random feature (RF) model. The RF kernel is given as (Rahimi et al., 2007)
k(x, x′) = c2Ew∼N (0d,Id)[a(w > j x)a(w >x′)]. (3)
Note that the RF kernel is the same as the second term in the expression of the NT kernel given in equation 2.

heading: 2.2 ROTATIONAL INVARIANCE
text: When the input domain X is the hypersphere Sd−1, by the spherical symmetry of the Gaussian distribution, the neural kernels are invariant to unitary transformations2 and can be expressed as
2Rotationally invariant kernels are also sometimes referred to as dot product or zonal kernels.
a function of x>x′. We thus use the notations κNT,s(x>x′) and κs(x>x′) to refer to the NT and RF kernels, as defined in equation 2 and equation 3, respectively. In this notation, s specifies the smoothness of the activation function, as(u) = (max(0, u))s.
The particular form of the neural kernels depends on s. For example, for the special case of s = 1, which corresponds to the ReLU activation function, the following closed form expressions can be derived from the expressions given in equation 2 and equation 3.
κNT,1(u) = u
π (π − arccos(u)) + κ1(u),
κ1(u) = 1
π
( u(π − arccos(u)) + √ 1− u2 ) .
In deriving the expressions above, the constant c in equations 2 and 3 is set to √
2. In general, we choose c2 = 2(2s−1)!! , that normalizes the maximum value of the RF kernel to 1: κs(1) = 1, ∀s ≥ 1.

heading: 2.3 NEURAL KERNELS FOR MULTILAYER NETWORKS
text: For an l > 2 layer network, the NT kernel is recursively given as (see, Jacot et al., 2018, Theorem 1)
κlNT,s(u) = c 2κl−1NT,s(u)κ ′ s(κ l−1(u)) + κls(u),
κls(u) = κs(κ l−1 s (u)). (4)
Here, κls(.) corresponds to the RF kernel of an l layer network, as shown in Cho & Saul (2009); Daniely et al. (2016); Lee et al. (2018); de G. Matthews et al. (2018). In our notation, when l = 2, we drop the layer index l from the superscript, as in the previous subsection. An expression for the derivative κ′s(.) of the RF kernel in a 2 layer network, based on κs−1, is given in Lemma 1. That is needed to see the equivalence of the expressions in equation 4 to the one given in Theorem 1 of Jacot et al. (2018).

heading: 3 THE RKHS OF THE NEURAL KERNELS
text: When the domain is Sd−1, as discussed earlier, the neural kernels have a rotationally invariant (dot product) form. The rotationally invariant kernels can be diagonalized in the basis of spherical harmonics, which are special functions on the surface of the hypersphere. Specifically, the Mercer decomposition of the kernels (for all l ≥ 2 and s ≥ 1) can be given as
κ(x>x′) = ∞∑ i=1 Nd,i∑ j=1 λ̃iφ̃i,j(x)φ̃i,j(x ′),
where the eigenfunction φ̃i,j is the j’th spherical harmonic of degree i, λ̃i is the corresponding eigenvalue, Nd,i = 2i+d−2i ( i+d−3 d−2 ) is the multiplicity of λ̃i (meaning the number of spherical harmonics of degree i, which all share the same eigenvalue λ̃i), and the conver-
gence of the series holds uniformly onX×X . As a consequence of Mercer’s representation theorem, the corresponding RKHS can be written as
Hκ = f(·) = ∞∑ i=1 Nd,i∑ j=1 wi,j λ̃ 1 2 i φ̃i,j(·) : wi,j ∈ R, ||f || 2 Hκ = ∞∑ i=1 Nd,i∑ j=1 w2i,j <∞  . Formal statements of Mercer’s theorem and Mercer’s representation theorem, as well as a formal definition of Mercer eigenvalues and eigenfunctions are given in Appendix B.
We use the notation λi (in contrast to λ̃i) to denote the decreasingly ordered eigenvalues, when their multiplicity is taken into account (for all i : ∑i′−1 i′′=1Nd,i′′ < i ≤ ∑i′ i′′=1Nd,i′′ , we define λi = λ̃i′ ).

heading: 3.1 THE DECAY RATE OF THE EIGENVALUES
text: As discussed, both RF and NT kernels can be represented in the basis of spherical harmonics. Our analysis of the MIG relies on the decay rate of the corresponding eigenvalues. In this section, we derive the eigendecay depending on the particular activation functions.
In the special case of ReLU activation function, several recent works (Geifman et al., 2020; Chen & Xu, 2021; Bietti & Bach, 2020) have proven a λ̃i ∼ i−d eigendecay for the NT kernel on the hypersphere Sd−1. In this work, we use a recent result from Bietti & Bach (2020) to derive the eigendecay based on the differentiability properties of the activation functions.
Proposition 1 Consider the neural kernels on the hypersphere Sd−1, and their Mercer decomposition in the basis of spherical harmonics. Then, the eigendecays are as reported in Table 2.
Proof Sketch. The proof follows from Theorem 1 of Bietti & Bach (2020), which proved that the eigendecay of a rotationally invariant kernel κ(.) : [−1, 1] → R can be determined based on its asymptotic expansions around the endpoints, ±1. In particular, when
κ(1− t) = p+1(t) + c+1tθ + o(tθ), κ(−1 + t) = p−1(t) + c−1tθ + o(tθ),
for polynomial p±1 and non-integer θ, the eigenvalues decay at the rate λ̃i ∼ (c+1 + c−1)i−d−2θ+1, for even i, and λ̃i ∼ (c+1 − c−1)i−d−2θ+1, for odd i. A formal statement of this result is given in Appendix E. They derived these expansions for the case of the ReLU activation function. For completeness, we derive the asymptotic endpoint expansions for the neural kernels with s− 1 times differentiable activation functions, in the case of l = 2 and l > 2 layer networks. Our derivations is based on the following Lemma.
Lemma 1 For the RF kernel defined in equation 3, with activation function as(.), and c = 2(2s−1)!! , we have
κ′s(u) = s2
2s− 1 κs−1(u).
The proof is given in Appendix D. Lemma 1 allows us to recursively derive the endpoint expansions of κs from those of κs−1, through integration. We thus obtain θ and c±1 for s > 1, when l = 2, using a recursive relation over s. We then use the compositional forms given in equation 4 to obtain the same, when l > 2, resulting in the eigendecays reported in Table 2.
Remark 1 The parity constraints in Table 2 may imply undesirable behavior for 2 layer infinitely wide networks. Ronen et al. (2019) studied this behavior and showed that adding a bias term removes these constraints, for the NT kernel. Although the parity constrained eigendecay affects the
representation power of the neural kernels, it does not affect our analysis of MIG and error rates, since for that analysis we only use λ̃i = O(i−d−2s+2).
Remark 2 We note that our results do not necessarily apply to deep neural networks in the sense that the implied constants in Table 2 grow exponentially in l, for s > 1 (see Appendix E for the expressions of the constants). When s = 1, however, the constants grow at most as fast as l2 (as shown in Bietti & Bach, 2020).

heading: 3.2 EQUIVALENCE OF THE RKHSS OF THE NEURAL AND MATÉRN KERNELS
text: Our bounds on the eigendecay of the neural kernels show the connection between the RKHS of the neural kernels, and that of Metérn family of kernels. LetHkν denote the RKHS of the Matérn kernel with smoothness parameter ν.
Theorem 1 On a hyperspherical domain, when l > 2,HκlNT,s (Hκls ) is equivalent toHkν , and, when l = 2,HκlNT,s ⊂ Hkν (Hκls ⊂ Hkν ), where ν = s− 1 2 (ν = s+ 1 2 ). The statement is summarized in Table 3.
The formal definition of equivalence (≡) and subset (⊂) relation between two normed spaces is given in Appendix A.
Proof Sketch. The proof follows from the eigendecay of the neural kernels given in Table 2, the eigendecay of the Matérn family of kernels on manifolds proven in Borovitskiy et al. (2020), and the Mercer’s representation theorem. Details are given in Appendix F.
Remark 3 The observations that when l = 2, we only haveHκlNT,s ⊂ Hks− 12 , and not vice versa, is a result of parity constraints in Table 2. The subset relation can change to equivalence, with a bias term which removes the parity constraints (see, Ronen et al., 2019).
A special case of Theorem 1, when s = 1, was recently proven in (Geifman et al., 2020; Chen & Xu, 2021). This special case pertains to the ReLU activation function and the Matérn kernel with smoothness parameter ν = 12 , that is also referred to as the Laplace kernel.
Remark 4 It is known that the RKHS of a Matérn kernel with smoothness parameter ν is equivalent to a Sobolev space with parameter ν + d2 (e.g., see, Kanagawa et al., 2018, Section 4). This observation provides an intuitive interpretation for the RKHS of the neural kernels as a consequence of Theorem 1. That is ‖f‖κlNT,s (‖f‖κls ) is proportional to the cumulative L 2 norm of the weak derivatives of f up to s + d−12 (s + d+1
2 ) order. I.e., f ∈ HκlNT,s (f ∈ Hκls ) translates to the existence of weak derivatives of f up to s+ d−12 (s+ d+1 2 ) order, which can be understood as a versatile measure for the smoothness of f controlled by s. For the details on the definition of weak derivatives and Sobolev spaces see, e.g., Hunter & Nachtergaele (2011).

heading: 4 MAXIMAL INFORMATION GAIN OF THE NEURAL KERNELS
text: In this section, we use the eigendecay of the neural kernels shown in the previous section to derive bounds on their information gain, which will then be used to prove uniform bounds on the generalization error.

heading: 4.1 INFORMATION GAIN: A MEASURE OF COMPLEXITY
text: To define information gain, we need to introduce a fictitious GP model. Assume F is a zero mean GP indexed on X with kernel k. Information gain then refers to the mutual information I(Yn;F ) between the data values Yn = [yi]ni=1 and F . From the closed from expression of mutual information between two multivariate Gaussian distributions (Cover, 1999), it follows that
I(Yn;F ) = 1
2 log det
( In + 1
λ2 Kn
) .
Here Kn is the kernel matrix [Kn]i,j = k(xi, xj), and λ > 0 is a regularization parameter. We also define the data independent and kernel specific maximal information gain (MIG) as follows.
γk(n) = sup Xn⊂X
I(Yn;F ). (5)
The MIG is also closely related to the effective dimension of the kernel. In particular, although the feature space of the neural kernels are infinite dimensional, for a finite dataset, the number of features with a significant impact on the regression model can be finite. The effective dimension of a kernel is often defined as (Zhang, 2005; Valko et al., 2013)
d̃k(n) = Tr ( Kn(Kn + λ 2In) −1) . (6)
It is known that the information gain and the effective dimension are the same up to logarithmic factors. Specifically, d̃k(n) ≤ I(Yn;F ), and I(Yn;F ) = O(d̃k(n) log(n)) (Calandriello et al., 2019).
Relating the information gain to the effective dimension provides some intuition into why it can capture the complexity of the learning problem. Roughly speaking, our bounds on the generalization error are analogous to the ones for a linear model, which has a feature dimension of d̃k(n).

heading: 4.2 BOUNDING THE INFORMATION GAIN OF THE NEURAL KERNELS
text: In the following theorem, we provide a bound on the maximal information gain of the neural kernels.
Theorem 2 For the neural kernels with all l ≥ 2, on a hyperspherical domain X = Sd−1, we have γκlNT,s(n) = O ( n d−1 d+2s−2 (log(n)) 2s−1 d+2s−2 ) , in the case of NT kernel,
γκls(n) = O ( n d−1 d+2s (log(n)) 2s+1 d+2s ) , in the case of RF kernel.
A special case of our Theorem 2, for the special case of the ReLU activation function, was recently proved in Kassraie & Krause (2021).
Proof Sketch. The main components of the analysis include the eigendecay given in Proposition 1, a projection on a finite dimensional RKHS technique proposed in Vakili et al. (2021b), and a bound on the sum of spherical harmonics of degree i determined by the Legendre polynomials, that is sometimes referred to as the Legendre addition theorem (Maleček & Nádenı́k, 2001). Details are given in Appendix G.

heading: 5 UNIFORM BOUNDS ON THE GENERALIZATION ERROR
text: In this section, we use the bound on MIG from previous section to establish uniform bounds on the generalization error.

heading: 5.1 IMPLICIT ERROR BOUNDS
text: We first overview the implicit (data dependent) error bounds for the kernel methods under the following assumptions.
Assumption 1 Assume the true data generating model f is in the RKHS corresponding to a neural kernel κ. In particular, ‖f‖Hκ ≤ B, for some B > 0. In addition, assume that the observation noise i are independent R sub-Gaussian random variables. That is E[exp(η i)] ≤ exp(η 2R2
2 ), ∀η ∈ R,∀i ≥ 1, where yi = f(xi) + i, ∀i ≥ 1.
Under Assumption 1, for a fixed x ∈ X , we have, with probability at least 1−δ (Vakili et al., 2021a),
|f(x)− f̂n(x)| ≤ β(δ)σn(x), (7)
where f̂n(x) = k>n (x)(Kn + λ 2In) −1Yn is the solution to the kernel ridge regression using κ and Dn, σ2n(x) = k(x, x) − k>n (x)(Kn + λ2In)−1kn(x), k>n (x) = [κ(x>xi)]ni=1, and β(δ) = B + Rλ √ 2 log( 2δ ). Equation 7 provides a high probability bound on |f(x)− f̂n(x)|. The decay rate of this bound based on n, however, is not explicit.

heading: 5.2 EXPLICIT ERROR BOUNDS
text: In this section, we use the bounds on MIG and the implicit error bounds from the previous subsection to provide explicit (in n) bounds on the error. It is clear that with no assumption on the distribution of the data, generalization error cannot be nontrivially bounded. For example, if all the data points are collected from a small region of the input domain, it is not expected for the error to be small far from this small region. We here consider a dataset that is distributed over the input space in a sufficiently informative way. For this purpose, we introduce a data collection module which collects the data points based on the current uncertainty level of the kernel model. In particular, consider a dataset D̃n collected as follows: xi = arg maxx∈X σi−1(x), where σi(.) is defined above. We have the following result.
Theorem 3 Consider the neural kernels with l ≥ 2, on a hyperspherical domain X = Sd−1. Consider a model f̂n trained on D̃n. Under Assumption 1, with probability at least 1 − δ, uniformly in x ∈ X ,
|f(x)− f̂n(x)| = O ( n −2s+1 2d+4s−4 (log(n)) 2s−1 2d+4s−4 (log( nd−1
δ ))
1 2 ) , in the case of NT kernel,
|f(x)− f̂n(x)| = O ( n −2s−1 2d+4s (log(n)) 2s+1 2d+4s (log( nd−1
δ ))
1 2 ) , in the case of RF kernel. (8)
Proof Sketch. The proof follows the same steps as in the proof of Theorem 3 of Vakili et al. (2021a). The key step is bounding the total uncertainty in the model with the information gain that is ∑n i=1 σ 2 i−1(xi) ≤ 2log(1+ 1
λ2 ) I(Yn;F ) (Srinivas et al., 2010). This allows us to bound the σn in the right hand side of equation 7 by √ γκ(n)/n up to multiplicative absolute constants. Plugging in the bounds on γκ(n) from Theorem 2, and using the implicit error bound given in equation 7 (with a union bound on a discretization of the domain with size O(nd−1)), we obtain equation 8. A detailed proof is given in Appendix H.

heading: 6 EXPERIMENTS
text: In this section, we provide experimental results on the error rates. In our experiments, we create synthetic data from a true model f that belongs to the RKHS of a NT kernel κ. For this purpose, we create two random vectors X̂n0 ∈ Xn0 and Ŷn0 ∈ Rn0 , and let f(.) = k̂>n0(.)(K̂n0 + δ 2In0) −1Ŷn0 , where k̂n0 and K̂n0 are defined similar to kn and Kn in Subsection 5.1. We then generate datasets Dn of various sizes n = 2i, with i = 1, 2, . . . , 13, according to the underlying model f . We train the model to obtain f̂n. Figure 2 shows the error rate versus the size n of the dataset for various d and s. The experiments show that the error converges to zero at a rate satisfying the bounds given in Theorem 3. In addition, as analytically predicted, the absolute value of the error rate exponent increases with s and decreases with d. Our experiments use the neural-tangents library (Novak et al., 2019). See Appendix I for more details.

heading: 7 DISCUSSION
text: Our bounds on MIG may be of independent interest in other problems. Recent works on RL and bandit problems, which use overparameterized neural network models, derived an Õ(γk(n) √ n) regret bound (see, e.g., Zhou et al., 2020; Yang et al., 2020; ZHANG et al., 2021; Gu et al., 2021). These works however did not characterize the bound on γk(n), leaving the regret bounds implicit. A consequence of our bounds on γk(n) is an explicit (in n) regret bound for these RL and bandit problems. Our results however have mixed implications by showing that the existing regret bounds are not necessarily sublinear in n. In particular, plugging in our bound on γκNT,s(n) into the existing regret bounds, we get Õ(n 1.5d+s−2 d+2s−2 ), which is sublinear only when s > d2 (that, e.g., excludes the ReLU activation function). Our analysis of various activation functions is thus essential in showing sublinear regret bounds for at least some cases. As recently formalized in Vakili et al. (2021c), it remains an open problem whether the analysis of RL and bandit algorithms in kernel regimes can improve to have an always sublinear regret bound. We note that this open problem and the analysis of RL and bandit problems were not considered in this work. Our remark is mainly concerned with the consequences of our bound on MIG, which appears in the regret bounds.
The recent work of Wang et al. (2020) proved that the L2 norm of the error is bounded as ‖f − f̂n‖L2 = O(n− d 2d−1 ), for a two layer neural network with ReLU activation functions in kernel regimes. Bordelon et al. (2020) decomposed the L2 norm of the error into a series corresponding to eigenfunctions of the NT kernel and provided bounds based on the corresponding eigenvalues. Our results are stronger as they are given in terms of absolute error instead of L2 norm. In addition, we provide explicit error bounds depending on differentiability of the activation functions.
The MIG has been studied for popular GP kernels such as Matérn and Squared Exponential (Srinivas et al., 2010; Vakili et al., 2021b). Our proof technique is similar to that of Vakili et al. (2021b). Their analysis however does not directly apply to the NT kernel on the hypersphere. The reason is that Vakili et al. (2021b) assume uniformly bounded eigenfunctions. In our analysis, we use a Mercer decomposition of the NT kernel in the basis of spherical harmonics. Those are not uniformly bounded. Technical details are provided in the analysis of Theorem 2. Applying a proof technique similar to Srinivas et al. (2010) results in suboptimal bounds in our case.
Our work may be relevant to the recent developments in the field of implicit neural representations (Mildenhall et al., 2020; Sitzmann et al., 2020; Fathony et al., 2020). In this line of work, the input to a neural network often represents the coordinates of a plane (image), a camera position or angle, and the function to be approximated is the image or the scene itself. Interestingly, it has been observed that smooth activation functions perform better than ReLU in these applications, since the models are also smooth (Sitzmann et al., 2020).

heading: A GENERAL NOTATION
text: In this section, we formally define our general notations. We use the notations 0n and In to denote the zero vector and the square identity matrix of dimension n, respectively. For a matrixM (a vector v),M> (v>) denotes its transpose. In addition, det and log det are used to denote determinant ofM and its logarithm, respectively. The notation ‖v‖l2 is used to denote the l2 norm of a vector v. For v ∈ Rd and a symmetric positive definite matrix Σ ∈ Rd×d, N (v,Σ) denotes a normal distribution with mean v and covariance Σ. The Kronecker delta is denoted by δi,j . The notation Sd−1 denotes the d dimensional hypersphere in Rd. For example, S2 ⊂ R3 is the usual sphere. The notations o and O denote the standard mathematical orders, while Õ is used to denote O up to logarithmic factors. For two sequences an, bn : N → R, we use the notation an ∼ bn, when an = O(bn) and bn = O(an). For s ∈ N, we define (2s− 1)!! = ∏s i=1(2i− 1). For example, 3!! = 3 and 5!! = 15.
For a normed space H, we use ‖.‖H to denote the norm associated with H. For two normed spaces H1,H2, we write H1 ⊂ H2, if the following two conditions are satisfied. First, H1 ⊂ H2 as sets. Second, there exist a constant c1 > 0, such that ‖f‖H2 ≤ c1‖f‖H1 , for all f ∈ H1. We also write H1 ≡ H2, when bothH1 ⊂ H2 andH2 ⊂ H1. The derivative of a : R → R is denoted by a′. We define 00 = 0, so that a0(x) = (max(0, x))0 corresponds to the step function: a0(x) = 0, when x ≤ 0, and a0(x) = 1, when x > 0.

heading: B MERCER’S THEOREM
text: In this section, we give an overview of Mercer’s theorem, as well as the the reproducing kernel Hilbert spaces (RKHSs) associated with the kernels. Mercer’s theorem (Mercer, 1909) provides a spectral decomposition of the kernel in terms of an infinite dimensional feature map (see, e.g. Steinwart & Christmann (2008), Theorem 4.49).
Theorem 4 (Mercer’s Theorem ) Let X be a compact domain. Let k be a continuous square integrable kernel with respect to a finite Borel measure µ. Define a positive definite operator Tk
(Tkf)(.) = ∫ X k(., x)f(x)dµ.
Then, there exists a sequence of eigenvalue-eigenfunction pairs {(λi, φi)}∞i=1 such that λi ∈ R+, and Tkφi = λiφi, for i ≥ 1. Moreover, the kernel function can be represented as
k(x, x′) = ∞∑ i=1 λiφi(x)φi(x ′),
where the convergence of the series holds uniformly on X × X .
The λi and φi defined in Mercer’s theorem are referred to as Mercer eigenvalues and Mercer eigenfunctions, respectively.
Let Hk denote the RKHS corresponding to k, defined as a Hilbert space equipped with an inner product 〈., .〉Hk satisfying the following: k(., x) ∈ Hk, ∀x ∈ X , and 〈f, k(., x)〉Hk = f(x), ∀x ∈ X ,∀f ∈ Hk (reproducing property). As a consequence of Mercer’s theorem, Hk can be represented in terms of {(λi, φi)}∞i=1, that is often referred to as Mercer’s representation theorem (see, e.g., Steinwart & Christmann (2008), Theorem 4.51).
Theorem 5 (Mercer’s Representation Theorem) Let {(λi, φi)}∞i=1 be the Mercer eigenvalueeigenfunction pairs. Then, the RKHS corresponding to k is given by
Hk = { f(·) =
∞∑ i=1 wiλ 1 2 i φi(·) : wi ∈ R, ||f || 2 Hk := ∞∑ i=1 w2i <∞
} .
Mercer’s representation theorem indicates that {λ 1 2 i φi}∞i=1 form an orthonormal basis for Hk: 〈λ 1 2 i φi, λ 1 2
i′φi′〉Hk = δi,i′ . It also provides a constructive definition for the RKHS as the span of this orthonormal basis, and a constructive definition for the ‖f‖Hk as the l2 norm of the weights [wi] ∞ i=1 vector.

heading: C CLASSICAL APPROACHES TO BOUNDING THE GENERALIZATION ERROR
text: There are classical statistical learning methods which address the generalization error in machine learning models. Two notable approaches are VC dimension (Bartlett, 1998; Anthony & Bartlett, 2009) and Rademacher complexity (Bartlett & Mendelson, 2002; Neyshabur et al., 2015). In the former, the expected generalization loss is bounded by the square root of the VC dimension divided by the square root of n. In the latter, the expected generalization loss scales with the Rademacher complexity of the hypothesis class. In the case of a 2 layer neural network of width m, it is shown that both of these approaches result in a generalization bound of O( √ m/n) that is vacuous for overparameterized neural networks with a very large m.
A more recent approach to studying the generalization error is PAC Bayes. It provides non-vacuous error bounds that depend on the distribution of parameters (Dziugaite & Roy, 2017). However, the distribution of parameters must be known or be estimated in order to use those bounds. Taking a different approach, Arora et al. (2019) provides bounds on expected generalization error of wellconditioned 2 layer neural networks based on the Gram matrix of the input data, which does not depend on the distribution of model parameters as in PAC Bayes. In contrast to all of these results, our bounds are explicit and are much stronger in the sense that they hold uniformly in x.

heading: D PROOF OF LEMMA 1
text: Lemma 1 offers a recursive relation over s for the RF kernel. We prove the lemma by taking the derivative of κs(.), and applying the Stein’s lemma (given at the end of this section). Let x = [0, 0, . . . , 0, 1]> and x′ = [0, 0, . . . , √
1− u2, u]>, so that x>x′ = u, and x, x′ ∈ Sd−1. We have ∂ ∂u Ew∼N (0d,Id) [ as(w >x)as(w >x′) ] = Ew∼N (0d,Id) [ as(w >x)sas−1(w >x′)(wd − uwd−1√ 1− u2 ) ] = sEw∼N (0d,Id) [ sas−1(w >x)as−1(w >x′)
+(s− 1)uas(w>x)as−2(w>x′) ] − sEw∼N (0d,Id) [ (s− 1)u√ 1− u2 √ 1− u2as(w>x)as−2(w>x′) ]
= s2Ew∼N (0d,Id) [ as−1(w >x)as−1(w >x′) ] .
The first equation is obtained by taking derivative of the term inside the expectation. The second equation is obtained by applying Stein’s lemma to E[as(w>x)sas−1(w>x′)wd], where wd is the normally distributed random variable, also to E[as(w>x)sas−1(w>x′) uwd−1√1−u2 ], where wd−1 is the normally distributed random variable.
Taking into account the constant normalization of the RF kernel c2 = 2(2s−1)!! , we have
κ′s(u) = 2 (2s− 1)!! ∂ ∂u Ew∼N (0d,Id)
[ as(w >x)as(w >x′) ] = 2s2
(2s− 1)!! Ew∼N (0d,Id)
[ as−1(w >x)as−1(w >x′) ] = s2
2s− 1 κs−1,
which proves the lemma.
Lemma 2 (Stein’s Lemma) Suppose X ∼ N (0, 1) is a normally distributed random variable. Consider a function g : R→ R such that both E[Xg(X)] and E[g′(X)] exist. We then have
E[Xg(X)] = E[g′(X)].
The proof of Stein’s lemma follows from an integration by parts (see, e.g., Stein, 1986; Nourdin & Peccati, 2009; Chen et al., 2011).

heading: E PROOF OF PROPOSITION 1
text: This proposition follows from Theorem 1 of Bietti & Bach (2020), which proved that the eigendecay of a rotationally invariant kernel κ : [−1, 1] → ∞ can be determined based on its asymptotic expansions around the endpoints±1. Recall that a rotationally invariant kernel k can be represented as κ(x>x′) = k(x, x′). Their result is formally given in the following lemma.
Lemma 3 (Theorem 1 in Bietti & Bach (2020)) Assume κ : [−1, 1] → R is C∞ and has the following asymptotic expansions around ±1
κ(1− t) = p+1(t) + c+1tθ + o(tθ), κ(−1 + t) = p−1(t) + c−1tθ + o(tθ),
for t > 0, where p±1 are polynomials, and θ > 0 is not an integer. Also, assume that the derivatives of κ admit similar expansions obtained by differentiating the above ones. Then, there exists Cd,θ such that, when i is even, if c+1 6= −c−1: λ̃i ∼ (c+1 + c−1)Cd,θi−d−2θ+1, and, when i is odd, if c+1 6= c−1: λ̃i ∼ (c+1 − c−1)Cd,θl−d−2θ+1. In the case |c+1| = |c−1|, then we have λ̃i = o(l−d−2θ+1) for one of the two parities. If κ is infinitely differentiable on [−1, 1] so that no such θ exists, the λ̃i decays faster than any polynomial.
Building on this result, the eigendecays can be obtained by deriving the endpoint expansions for the RF and NT kernels. That is derived in Bietti & Bach (2020) for the ReLU activation function. For completeness, here, we derive the endpoint expansions for RF and NT kernels associated with s− 1 times differentiable activation functions as(.).
Recall that for a 2 layer network, the corresponding RF and NT kernels are given by
κNT,s(x >x′) = c2(x>x′)Ew∼N (0d,Id)[a ′ s(w >x)a′s(w >x′)] + κs(x >x′),
κs(x >x′) = c2Ew∼N (0d,Id)[as(w >x)as(w >x′)].
For the special cases of s = 0 and s = 1, the following closed form expressions can be derived by taking the expectations.
κ0(u) := Ew∼N (0d,Id)[a0(w >x)a0(w
>x′)] = 1
π (π − arccos(u)),
κ1(u) = 1
π
( u(π − arccos(u)) + √ 1− u2 ) ,
where u = x>x′. At the endpoints ±1, κ0(u), κ1(u) have the following asymptotic expansions.
κ0(1− t) = 1− √ 2
π t 1 2 + o(t 1 2 ),
κ0(−1 + t) = √ 2
π t 1 2 + o(t 1 2 ),
κ1(1− t) = 1− t+ 2 √ 2
3π t 3 2 + o(t 3 2 ),
κ1(−1 + t) = 2 √ 2
3π t 3 2 + o(t 3 2 ). (9)
These endpoint expansions where used in Bietti & Bach (2020) to obtain the eigendecay of the RF and NT kernels with ReLU activation functions.
We first extend the results on the endpoint expansions and the eigendecay to a 2 layer neural network with s > 1, in Subsection E.1. Then, we extend the derivation to l > 2 layer neural networks, in Subsection E.2. In Subsection E.3, we show how the eigendecays in terms of λ̃i can be translated to the ones in terms of λi.
E.1 ENDPOINT EXPANSIONS FOR 2 LAYER NETWORKS WITH s > 1
We first note that the normalization constant c2 = 2(2s−1)!! , suggested in Section 2, ensures κs(1) = 1, for all s ≥ 1. The reason is that, by the well known values for the even moments of the normal distribution, we have
Ew∼N (0d,Id)[as(w >x)as(w
>x′)] = (2s− 1)!!
2 ,
when x>x′ = 1. Also notice that κs(−1) = 0, for all s ≥ 1. The reason is that when x>x′ = −1, at least one of w>x and w>x′ is non-positive.
We note that the normalization constant is considered only for the convenience of some calculations, and does not affect the exponent in the eigendecays. Specifically, scaling the kernel with a constant factor, scales the corresponding Mercer eigenvalues with the same constant. The constant factor scaling does not affect the Mercer eigenfunctions.
From Lemma 1, recall
κ′s(.) = s2
2s− 1 κs−1(.).
This is a key component in deriving the endpoint expansions for s > 1. In particular, this allows us to recursively obtain the endpoint expansions of κs(.) from those of κs−1(.), by integration. That results in the following expansions for κs.
κs(1− t) = p+1,s(t) + c+1,st 2s+1 2 + o(t 2s+1 2 ),
κs(−1 + t) = p−1,s(t) + c−1,st 2s+1 2 + o(t 2s+1 2 ), (10)
Here, p+1,s(t) = − s 2 2s−1 ∫ p+1,s−1(t)dt, subject to p+1,s(0) = 1 (that follows form κs(1) = 1). Thus, p+1,s(t) can be obtained recursively, starting from p+1,1(t) = 1 − t (see equation 9). For example,
p+1,2(t) = − 4 3 (−3 4 + t− t
2
2 ),
p+1,3(t) = 36 15 ( 15 36 − 3 4 t+ 1 2 t2 − 1 6 t3),
and so on.
Similarly, p−1,s(t) can be expressed in closed form using p−1,s(t) = s 2 2s−1 ∫ p−1,s−1(t)dt subject to p−1,s(0) = 0 (that follows from κs(−1) = 0), and starting from p−1,1(t) = 0, ∀t (see equation 9). That leads to p−1,s(t) = 0, ∀s > 1, t. The exact expressions of p±1,s(t) however do not affect the eigendecay. Instead, the constants c±1,s are important for the eigendecay, based on Lemma 3. The constants can also be obtained recursively. Starting from c+1,1 = 2 √ 2 3π (see equation 9), c+1,s = −2s2c+1,s−1 (2s−1)(2s+1) . Also starting from c−1,1 = 2 √ 2 3π (see equation 9), c−1,s = 2s2c+1,s−1
(2s−1)(2s+1) . This recursive relation leads to
c−1,s = 2s √ 2
π s∏ r=1
r2
(4r2 − 1) , (11)
and c+1,s = (−1)s−1c−1,s.
In the case of RF kernel, applying Lemma 3, we have λ̃i ∼ i−d−2s, for i having the opposite parity of s, and λ̃i = o(i−d−2s) for i having the same parity of s.
For the NT kernel, using 2, we have
κNT,s(1− t) = c2(1− t)s2κs−1(1− t) + κs(1− t) κNT,s(−1 + t) = c2(−1 + t)s2κs−1(−1 + t) + κs(−1 + t) (12)
Using the expansion of the RF kernel, we get
κNT,s(1− t) = p′′+1,s(t) + c′′+1,st 2s−1 2 + o(t 2s−1 2 ),
κNT,s(−1 + t) = p′′−1,s(t) + c′′−1,st 2s−1 2 + o(t 2s−1 2 ), (13)
where
p′′+1,s(t) = c 2(1− t)s2p+1,s−1(t) + ps(t), p′′−1,s(t) = c 2(−1 + t)s2p−1,s(t) + p−1,s(−1 + t),
and
c′′+1,s = c+1,s−1, c′′−1,s = c−1,s−1.
Thus, in the case of NT kernel, applying Lemma 3, we have λ̃i ∼ i−d−2s+2, for i having the same parity of s, and λ̃i = o(i−d−2s+2) for i having the opposite parity of s.
E.2 ENDPOINT EXPANSIONS FOR l > 2 LAYER NETWORKS
We here extend the endpoint expansions and the eigendecays to l > 2 later networks. Recall κls(u) = κs(κ l−1 s (u)). Using this recursive relation over l, we prove the following expressions
κls(1− t) = pl+1,s(t) + cl+1,st 2s+1 2 + o(t 2s+1 2 )
κls(−1 + t) = pl−1,s(t) + cl−1,st 2s+1 2 + o(t 2s+1 2 )
where pl±1,s are polynomials and c l ±1,s are constants.
The notations p+1,s and c+1,s in Subsection E.1 correspond to p2+1,s c 2 +1,s, where we drop the superscript specifying the number l of layers, for 2 layer networks.
For the endpoint expansion at 1, we have
κls(1− t) = κs(κl−1s (1− t)) = κs(1− 1 + pl−1+1,s(t) + c l−1 +1,st 2s+1 2 + o(t 2s+1 2 ))
= p+1,s(1− pl−1+1,s(t)− c l−1 +1,st 2s+1 2 − o(t 2s+1 2 ))
+c+1,s(1− pl−1+1,s(t)− c l−1 +1,st 2s+1 2 − o(t 2s+1 2 )) 2s+1 2 +o (
(1− pl−1+1,s(t)− c l−1 +1,st 2s+1 2 − o(t 2s+1 2 )) 2s+1 2 ) Thus, we have
cl+1,s = (−q l−1,1 +1,s ) 2s+1 2 c+1,s − q2,1+1,sc l−1 +1,s, (14)
where ql,i+1,s is the coefficient of t i in pl+1,s(t). For these coefficients, we have
ql,1+1,s = −q 2,1 +1,sq l−1,1 +1,s . (15)
Starting from q2,1+1,s = − s 2 2s−1 (which can be seen from the recursive expression of p+1,s given in Section E.1), we get ql,1+1,s = − s 2(l−1) (2s−1)l−1 . We thus have
cl+1,s =
( s(2s+1)
(2s− 1) (2s+1) 2
)l−2 c+1,s + s2
2s− 1 cl−1+1,s. (16)
That implies
cl+1,s ∼
( s(2s+1)
(2s− 1) (2s+1) 2
)l−2 c+1,s, (17)
when s > 1.
The characterization of cl+1,s shows that our results do not apply to deep neural networks when s > 1, in the sense that the constants grow exponentially in l (as stated in Remark 2).
For the endpoint expansion at −1, we have
κls(−1 + t) = κs(κl−1s (−1 + t)) = κs(p l−1 −1,s(t) + c l−1 −1,st 2s+1 2 + o(t 2s+1 2 ))
= κs(q l−1,0 −1,s ) + κ ′ s(q l−1,0 −1,s )(p l−1 −1,s(t)− q l−1,0 −1,s + c l−1 −1,st 2s+1 2 ) + o(t 2s+1 2 ).
where ql,i−1,s is the coefficient of t i in pl−1,s(t). From the expression above we can see that
ql,0−1,s = κs(q l−1,0 −1,s ) (18)
Thus, 0 ≤ ql,0−1,s ≤ 1. In addition, the expression above implies
cl−1,s = c l−1 −1,sκ ′ s(q l−1,0 −1,s ). (19)
From Lemma 1, κ′s(u) ≤ s 2 2s−1 , for all u. Therefore,
cl−1,s ≤ ( s2
2s− 1
)l−2 c−1,s
= o(cl+1,s),
when, s > 1.
Comparing cl±1,a, we can see that for l > 2, we have |cl+1,s| 6= |cl−1,s|. Thus, for the RF kernel with l > 2, applying Lemma 3, we have λ̃i ∼ i−d−2s.
For the NT kernel, recall
κlNT,s(u) = c 2κl−1NT,s(u)κ ′ s(κ l−1 s (u)) + κ l s(u).
The second term is exactly the same as the RF kernel. Recall the expression of κ′s based on κs−1 from Lemma 1. To find the endpoint expansions of the first term, we prove the following expressions for κs−1(κl−1s (u)).
κs−1(κ l−1 s (1− t)) = p′l+1,s(t) + c′l+1,st 2s−1 2 + o(t 2s−1 2 )
κs−1(κ l−1 s (−1 + t)) = p′l−1,s(t) + c′l−1,st 2s+1 2 + o(t 2s+1 2 )
We use the notation used for the RF kernel to write the following expansion around 1
κs−1(κ l−1 s (1− t)) = κs−1(1− 1 + pl−1+1,s(t) + c l−1 +1,st 2s+1 2 + o(t 2s+1 2 ))
= p+1,s−1(1− pl−1+1,s(t)− c l−1 +1,st 2s+1 2 − o(t 2s+1 2 ))
+c+1,s−1(1− pl−1+1,s(t)− c l−1 +1,st 2s+1 2 − o(t 2s+1 2 )) 2s−1 2 +o (
(1− pl−1+1,s(t)− c l−1 +1,st 2s+1 2 − o(t 2s+1 2 )) 2s−1 2
) .
Thus, we have
c′l+1,s = (−q l−1,1 +1,s ) 2s−1 2 c+1,s−1 − q2,1+1,s−1c l−1 +1,s (20)
Recall, form the analysis of the RF kernel that ql,1+1,s = − s2(l−1) (2s−1)l−1 . We thus have
c′l+1,s =
( s(2s−1)
(2s− 1) (2s−1) 2
)l−2 c+1,s−1 + (s− 1)2
2s− 3 cl−1+1,s. (21)
That implies
c′l+1,s ∼
( s(2s−1)
(2s− 1) (2s−1) 2
)l−2 c+1,s−1. (22)
For the endpoint expansion at −1, we have
κs−1(κ l−1 s (−1 + t)) = κs−1(pl−1−1,s(t) + c l−1 −1,st 2s+1 2 + o(t 2s+1 2 ))
= κs−1(q l−1,0 −1,s ) + κ ′ s−1(q l−1,0 −1,s )(p l−1 −1,s(t)− q l−1,0 −1,s + c l−1 −1,st 2s+1 2 ) + o(t 2s+1 2 ).
We thus have
c′l−1,s = c l−1 −1,s−1κ ′ s−1(q l−1,0 −1,s ). (23)
Since κ′s−1 ≤ (s−1)2 2s−3 , we have
c′l−1,s ≤ ( s2
2s− 3
)l−2 c−1,s−1.
Now we use the end point expansions of κls and κs−1(κ l−1 s ) to obtain the following endpoint expansions for κlNT,s.
κlNT,s(1− t) = p′′l+1,s(t) + c′′l+1,st 2s−1 2 + o(t 2s−1 2 ),
κlNT,s(−1 + t) = p′′l−1,s(t) + c′′l−1,st 2s−1 2 + o(t 2s−1 2 ).
We have
c′′l+1,s = c2s2
2s− 1 q′l,0+1,sc ′′l−1 +1,s +
c2s2
2s− 1 q′′l−1,0+1,s c ′l +1,s,
and,
q′′l,0+1,s = c2s2
2s− 1 q′′l−1,0+1,s q ′l,0 +1,s + q l,0 +1,s. (24)
Since κs(1) = 1, by induction we have κls(1) = 1, ∀l ≥ 2. In addition, κs−1(κl−1s (1)) = κs−1(1) = 1, ∀l ≥ 3. Therefore q′l,0+1,s, q l,0 +1,s = 1. Thus,
q′′l,0+1,s = c2s2
2s− 1 q′′l−1,0+1,s + 1. (25)
Starting from q′′2,0+1,s = s2 2s−1 + 1, we can derive the following expression for q ′′l,0 +1,s, when s > 1,
q′′l,0+1,s = 1
c2
( c2s2
2s− 1
)l−1 +
( c2s2
2s−1 )l−1 − 1(
c2s2 2s−1
) − 1
∼ 1 c2
( c2s2
2s− 1
)l−1 .
When s = 1, q′′l,0+1,s = l, that is consistent with the results in Bietti & Bach (2020).
For c′′l+1,s, we thus have
c′′l+1,s = c2s2
2s− 1 c′′l−1+1,s +
c2s2
2s− 1 q′′l−1,0+1,s c ′l +1,s.
Replacing the expressions for q′′l−1,0+1,s and c ′l +1,s derived above, we obtain
c′′l+1,s ∼ ( 1
c2 )(
2s−1 2 )(l−2)+1
( c2s2
2s− 1
)( 2s+12 )(l−2)+1 c+1,s−1. (26)
For the constant in the expansion around −1, we have
c′′l−1,s = c2s2
2s− 1 q′l,0−1,sc ′′l−1 −1,s , (27)
where q′l,0−1,s = κs−1(q l−1,0 −1,s ) is bounded between 0 and 1. Thus, starting from c ′′2 −1,s = c−1,s−1, we obtain
c′′l−1,s ≤ ( c2s2
2s− 1
)l−2 c−1,s−1 (28)
Comparing c′′l±1,a, we can see that for l > 2, we have |c′′l+1,s| 6= |c′′l−1,s|. Thus, for the NT kernel with l > 2, applying Lemma 3, we have λ̃i ∼ i−d−2s+2.
E.3 THE EIGENDECAYS IN TERMS OF λi Recall the multiplicity Nd,i = 2i+d−2i ( i+d−3 d−2 ) of λ̃i. Here we take into account this multiplicity to give the eigendecay expressions in terms of λi.
Using (nk ) k ≤ ( n k ) ≤ (nek ) k, for all k, n ∈ N, we have, for all i > 1 and d > 2,
2(i− 1)d−2( 1 d− 2 + 1 i− 1 )d−2 ≤ Nd,i ≤
(d+ 2)ed−2
2 (i− 1)d−2( 1 d− 2 + 1 i− 1 )d−2,
where we used 2 < 2i+d−2i < d+2 2 . We thus have Nd,i ∼ (i− 1) d−2, for the scaling of Nd,i with i, with constants given above.
Recall we define λi = λ̃i′ , for i and i′ which satisfy ∑i′−1 i′′=1Nd,i′′ < i ≤ ∑i′ i′′=1Nd,i′′ . Using
Nd,i ∼ (i − 1)d−2, we have ∑i′ i′′=1Nd,i′′ ∼ i′d−1. Thus λi ∼ λ̃i′ = λ̃i 1d−1 . Replacing i with i 1 d−1 , in the expressions derived for λ̃i in this section, we obtain the eigendecay expressions for λi reported in Table 2.

heading: F PROOF OF THEOREM 1
text: The Matérn kernel can also be decomposed in the basis of spherical harmonics. In particular, Borovitskiy et al. (2020) proved the following expression for the Matérn kernel with smoothness parameter ν on the hypersphere Sd−1 (see, also Dutordoir et al., 2020, Appendix B)
kν(x, x ′) = ∞∑ i=1 Nd,i∑ j=1 ( 2ν κ2 + i(i+ d− 2))−(ν+ d−1 2 )φ̃i,j(x)φ̃i,j(x ′),
where φ̃i,j are the spherical harmonics.
Theorem 5 implies that the RKHS of Metérn kernel is also constructed as a span of spherical harmonics. Thus, in order to show the equivalence of the RKHSs of the neural kernels with various activation functions and a Matérn kernel with the corresponding smoothness, we show that the ratio between their norms is bounded by absolute constants.
Let f ∈ HlkNT,s , with l ≥ 2. As a result of Mercer’s representation theorem, we have
f(·) = ∞∑ i=1 Nd,i∑ j=1 wi,j λ̃ 1 2 i φ̃i,j(·)
= ∞∑ i=1 Nd,i∑ j=1 wi,j λ̃ 1 2 i ( 2νκ2 + i(i+ d− 2)) − 12 (ν+ d−1 2 ) ( 2ν κ2 + i(i+ d− 2))− 12 (ν+ d−1 2 )φ̃i,j(·).
Note that
λ̃i
( 2νκ2 + i(i+ d− 2)) −(ν+ d−12 )
= O( λ̃i i−2ν−d+1 ).
For the NT kernel, from Proposition 1, λ̃i = O(i−d−2s+2). Thus, when ν = s− 12 ,
λ̃i
( 2νκ2 + i(i+ d− 2)) −(ν+ d−12 )
= O(1).
So, with ν = s− 12 we have
‖f‖2Hkν = ∞∑ i=1 Nd,i∑ j=1 w2i,j λ̃i ( 2νκ2 + i(i+ d− 2)) −(ν+ d−12 )
= O( ∞∑ i=1 Nd,i∑ j=1 w2i,j)
= O(‖f‖2H κlNT,s ).
That provesHklNT,s ⊂ Hkν .
A similar proof shows that when ν = s+ 12 ,H l ks ⊂ Hkν .
Now, let f ∈ Hkν . As a result of Mercer’s representation theorem, we have
f(·) = ∞∑ i=1 Nd,i∑ j=1 wi,j( 2ν κ2 + i(i+ d− 2))− 12 (ν+ d−1 2 )φ̃i,j(·)
= ∞∑ i=1 Nd,i∑ j=1 wi,j ( 2νκ2 + i(i+ d− 2)) − 12 (ν+ d−1 2 ) λ̃ 1 2 i λ̃ 1 2 i φ̃i,j(·).
For the NT kernel with l > 2, from Proposition 1, λ̃l ∼ l−d−2s+2. Thus, when ν = s− 12 ,
( 2νκ2 + l(l + d− 2)) −(ν+ d−12 )
λ̃l = O(1).
So, with ν = s− 12 we have
‖f‖2H κlNT,s = ∞∑ i=1 Nd,i∑ j=1 w2i,j ( 2νκ2 + i(i+ d− 2)) −(ν+ d−12 ) λ̃i
= O( ∞∑ i=1 Nd,i∑ j=1 w2i,j)
= O(‖f‖2Hkν ).
That proves, for l > 2, when ν = s− 12 ,Hkν ⊂ H l kNT,s . A similar proof shows that for l > 2, when ν = s+ 12 ,Hkν ⊂ H l ks , which completes the proof of Theorem 1.

heading: G PROOF OF THEOREM 2
text: Recall the definition of the information gain for a kernel κ,
I(Yn;F ) = 1
2 log det
( In + 1
λ2 Kn
) .
To bound the information gain, we define two new kernels resulting from the partitioning of the eigenvalues of the neural kernels to the first M eigenvalues and the remainder. In particular, we define
κ̃(x>x) = M∑ i=1 Nd,i∑ j=1 λ̃iφ̃i,j(x)φ̃i,j(x ′),
˜̃κ(x>x) = ∞∑ i=M+1 Nd,i∑ j=1 λ̃iφ̃i,j(x)φ̃i,j(x ′). (29)
We present the proof for the NT kernel. A similar proof applies to the RF kernel.
The truncated kennel at M eigenvalues, κ̃(x>x), corresponds to the projection of the RKHS of κ onto a finite dimensional space with dimension ∑M i=1 ∑Nd,i j=1 .
We use the notations K̃n and ˜̃Kn to denote the kernel matrices corresponding to κ̃ and ˜̃κ, respectively.
As proposed in Vakili et al. (2021b), we write
log det ( In + 1
λ2 Kn
) = log det ( In + 1
λ2 (K̃n +
˜̃Kn) ) = log det ( In + 1
λ2 K̃n
) + log det ( In + 1
λ2 (In +
1
λ2 K̃n)
−1 ˜̃Kn ) . (30)
The analysis in Vakili et al. (2021b) crucially relies on an assumption that the eigenfunctions are uniformly bounded. In the case of spherical harmonics however (see, e.g., Stein & Weiss, 2016, Corollary 2.9)
sup i=1,2,...,
j=1,2,...,Nd,i, x∈X
φ̃i,j(x) =∞. (31)
Thus, their analysis does not apply to the case of neural kernels on the hypersphere.
To bound the two terms on the right hand side of equation 30, we first prove in Lemma 4 that ˜̃κ(x, x′) approaches 0 as M grows (uniformly in x and x′), with a certain rate.
Lemma 4 For the NT kernel, we have ˜̃κ(x>x′) = O(M−2s+1), for all x, x′ ∈ X .
Proof of Lemma 4: Recall that the eigenspace corresponding to λ̃i has dimension Nd,i and consists of spherical harmonics of degree i. Legendre addition theorem (Maleček & Nádenı́k, 2001) states
Nd,i∑ j=1 φi,j(x)φi,j(x ′) = ci,dC (d−2)/2 i (cos(d(x, x ′))), (32)
where d is the geodesic distance on the hypersphere, C(d−2)/2i are Gegenbauer polynomials (those are the same as Legendre polynomials up to a scaling factor), and the constant ci,d is
ci,d = Nd,iΓ((d− 2)/2)
2π(d−2)/2C (d−2)/2 k (1)
. (33)
We thus have
˜̃κ(x>x′) = ∞∑ i=M+1 λ̃i Nd,i∑ j=1 φi,j(x)φi,j(x ′)
= ∞∑ i=M+1 λ̃ici,dC (d−2)/2 i (cos(d(x, x ′)))
≤ ∞∑
i=M+1
λ̃iNd,i Γ((d− 2)/2) 2π((d−2)/2)
∼ ∞∑
i=M+1
i−d−2s+2id−2
∼ M−2s+1.
Here, the inequality follows from C(d−2)/2i (cos(d(x, x ′))) ≤ C(d−2)/2i (1), because the Gegenbauer polynomials attain their maximum at the endpoint 1. For the fourth line we used Nd,i ∼ id−2. The implied constants include the implied constants inNd,i ∼ id−2 given in Section E.3, and Γ((d−2)/2)2π((d−2)/2) . We also introduce a notation NM = ∑M i=1Nd,i for the number of eigenvalues corresponding to the spherical harmonics of degree up to M , taking into account their multiplicities, that satisfies NM ∼Md−1 (see Section E.3). We are now ready to bound the two terms on the right hand side of equation 30. Let us define Φn,NM = [φNM (x1),φNM (x2), . . . ,φNM (xn)]
>, an n × NM matrix which stacks the feature vectors φNM (xi) = [φj(xi)] NM j=1, i = 1, . . . , n, at the observation points, as its rows. Notice that
K̃n = Φn,NMΛNMΦ > n,NM ,
where ΛNM is the diagonal matrix of the eigenvalues defined as [ΛNM ]i,j = λiδi,j .
Now, consider the Gram matrix
G = Λ 1 2 NM Φ>n,NMΦn,NMΛ 1 2 NM .
As it was shown in Vakili et al. (2021b), by matrix determinant lemma, we have
log det(In + 1
λ2 K̃n) = log det(INM +
1
λ2 G) ≤ NM log ( 1
NM tr(INM +
1
λ2 G) ) = NM log(1 + n
λ2NM ).
To upper bound the second term on the right hand side of equation 30, we use Lemma 4. In particular, since
tr ( (In + 1
λ2 K̃n)
−1 ˜̃Kn ) ≤ tr( ˜̃Kn),
and [ ˜̃Kn]i,i = O(M−2s+1), we have
tr ( In + 1
λ2 (In +
1
λ2 K̃n)
−1 ˜̃Kn ) = O ( n(1 + 1
λ2 M−2s+1)
) .
Therefore
log det ( In + 1
λ2 (In +
1
λ2 K̃n)
−1 ˜̃Kn ) ≤ n log ( O(1 + 1
λ2 M−2s+1) ) ≤ nM −2s+1
λ2 +O(1),
where for the last line we used log(1 + z) ≤ z which holds for all z ∈ R.
We thus have γk(n) = O(Md−1 log(n) +nM−2s+1). Choosing M ∼ n 1 d+2s−2 (log(n)) −1
d+2s−2 , we obtain
γκlNT,s(n) = O ( n d−1 d+2s−2 (log(n)) 2s−1 d+2s−2 ) . (34)
For example, with ReLU activation functions, we have γκlNT,1(n) = O ( n d−1 d (log(n)) 1 d ) .

heading: H PROOF OF THEOREM 3
text: As stated in the paper, the proof follows the same steps as in the proof of Theorem 3 of Vakili et al. (2021a). Their theorem holds for general kernels, provided the bound on MIG. We have adopted their theorem for the special case of neural kernels, inserting our novel bounds on MIG of the neural kernels given in Theorem 2. For completeness, we include a detailed proof here.
The proof consists of tow components. First, we bound the uncertainty estimate σn(x) in terms of γk(n). Our novel bounds on γk(n) of neural kernels given in Theorem 2 allow us to derive explicit bounds on σn(x). Then, we bound the error |f(x) − f̂n(x)| in terms of σn(x), using implicit error bounds.
Recall the way that the dataset D̃n is collected: xi = arg maxx∈X σi−1(x). This ensures that, ∀x ∈ X , σi−1(x) ≤ σi−1(xi). Due to positive definiteness of the kernel matrix, conditioning on a larger dataset reduces the uncertainty. Thus ∀x ∈ X and ∀i ≤ n, σn(x) ≤ σi(x). Therefore σ2n(x) is upper bounded by the average of σ2i−1(xi) over i: ∀x ∈ X
σ2n(x) ≤ 1
n n∑ i=1 σ2i−1(xi). (35)
It is shown that (e.g., see, Srinivas et al., 2010, Lemmas 5.3, 5.4) n∑ i=1 σ2i−1(xi) ≤ 2I(Yn;F ) log(1 + 1λ2 ) . (36)
Thus, combining equation 35 and equation 36, and by definition of γk(n), we have, ∀x ∈ X
σn(x) ≤
√ 2γk(n)
n log(1 + 1λ2 ) . (37)
Now, inserting our bounds on γκlNT,s(n) and γκls(n) of the neural kernels from Theorem 2, we obtain, ∀x ∈ X
σn(x) ≤ n −2s+1 2d+4s−4 (log(n)) 2s−1 2d+4s−4
√ 2
log(1 + 1λ2 ) , in the case of NT kernel,
σn(x) ≤ n −2s−1 2d+4s (log(n)) 2s+1 2d+4s
√ 2
log(1 + 1λ2 ) , in the case of RF kernel. (38)
The second component of the proof is summarized in the following lemma.
Lemma 5 Under Assumption 1, we have, with probability at least 1− δ, ∀x ∈ X |f(x)− f̂n(x)| ≤ ( B + C(log( nd−1
δ ))
1 2 ) σn(x) +
2√ n , (39)
where C is an absolute constant, and B is the upper bound on the RKHS norm of f given in Assumption 1.
Lemma 5 follows from equation 7, and a probability union bound over a discretization of the domain. A detailed proof of this lemma is given at the end of this section.
Inserting the bounds on σn(x) from equation 38 in Lemma 5, we have, with probability at least 1− δ, uniformly in x,
|f(x)− f̂n(x)| = O ( n −2s+1 2d+4s−4 (log(n)) 2s−1 2d+4s−4 (log( nd−1
δ ))
1 2 ) , in the case of NT kernel,
|f(x)− f̂n(x)| = O ( n −2s−1 2d+4s (log(n)) 2s+1 2d+4s (log( nd−1
δ ))
1 2 ) , in the case of RF kernel.
That completes the proof.
Proof of Lemma 5:
Recall the implicit error bound given in equation 7: For a fixed x ∈ X , under Assumption 1, we have, with probability at least 1− δ (Vakili et al., 2021a),
|f(x)− f̂n(x)| ≤ β(δ)σn(x), (40) where β(δ) = B + Rλ √
2 log(2δ ). Lemma 5 extends this inequality to a uniform bound in x, using a probability union bound over a discretization of the domain.
For f ∈ Hk, with ‖f‖Hk ≤ B, and for n ∈ N, there exists a fine discretization Xn of X with size |Xn| such that f(x) − f([x]n) ≤ 1√n , where [x]n = arg minx′∈Xn ‖x
′ − x‖l2 is the closest point in Xn to x, and |Xn| ≤ cBd−1n(d−1)/2, where c is an absolute constant independent of n and B (Chowdhury & Gopalan, 2017; Vakili et al., 2021a).
Under Assumption 1, it can be shown that: with probability at least 1 − δ/2 (Vakili et al., 2021a, Lemma 4)
‖f̂n‖Hk ≤ B + R √ n
λ
√ 2 log( 4n
δ )︸ ︷︷ ︸
U(δ)
. (41)
Note that f̂n is a random function, where the randomness comes from the randomness in observation noise.
We thus conclude that there is a discretization X̃n with size |X̃n| ≤ c(U(δ))d−1n(d−1)/2 such that |f(x)− f([x]n)| ≤ 1√n , and with probability at least 1− δ/2,
|f̂n(x)− f̂n([x]n)| ≤ 1√ n . (42)
Let δ′ = δ 2c(U(δ))d−1n(d−1)/2 . A probability union bound over the discretization X̃n implies that: With probability at least 1− δ/2, uniformly in x ∈ X̃n,
|f(x)− f̂n(x)| ≤ β(δ′)σn(x). (43)
Accounting for the discretization error from equation 42, and a probability union bound over equation 41 and equation 43, we have, with probability at least 1− δ, uniformly in x ∈ X ,
|f(x)− f̂n(x)| ≤ |f(x)− f([x]n)|+ |f([x]n)− f̂n([x]n)|+ |f̂n([x]n)− f̂n(x)|
≤ |f([xn])− f̂n([xn])|+ 2√ n
≤ β(δ′)σn(x) + 2√ n .
The first line holds by triangle inequality, the second line comes from the discretization error, and the third line holds by equation 43.
Inserting the value of U(δ) = B + R √ n
λ √ 2 log(2nδ ) in δ ′, and the value of δ′ = δ 2c(U(δ))d−1n(d−1)/2
in β(·) = B + Rλ √ 2 log(2· ), we arrive at the lemma.

heading: I DETAILS ON THE EXPERIMENTS
text: In this section, we provide further details on the experiments shown in the main text, Section 6. The code will be made available upon the acceptance of the paper.
We consider NT kernels κNT,s(.), with s = 1, 2, 3, which correspond to wide fully connected 2 layer neural networks with activation functions as(.). In the first step, we create a synthetic function f belonging to the RKHS of a NT kernel κ. For this purpose, we randomly generate n0 = 100 points on the hypersphere Sd−1. Let X̂n0 = [x̂i] n0 i=1 denote the vector of these points. We also randomly sample Ŷn0 = [ŷi] n0 i=1 from a multivariate Gaussian distribution N (0n0 ,Kn0), where [K̂n0 ]i,j = κ(x̂>i x̂j). We define a function g(.) = k̂>n0(.)(K̂n0+δ 2In0)
−1Ŷn0 , where δ2 = 0.01 and [K̂n0(x)]i = κ(x
>x̂i). We then normalize g with its range to obtain f(.) = g(.)maxx∈X g(x)−minx∈X g(x) . For a fixed X̂n0 and Ŷn0 , g is a linear combination of partial applications of the kernel. Thus g is in the RKHS of κ, and its RKHS norm can be bounded as follows.
‖g‖2Hκ = 〈 k̂>n0(.)(K̂n0 + δ 2In0) −1Ŷn0 , k̂ > n0(.)(K̂n0 + δ 2In0) −1Ŷn0 〉 Hκ
= Ŷ >n0(K̂n0 + δ 2In0) −1K̂n0(K̂n0 + δ 2In0) −1Ŷn0 = Ŷ >n0(K̂n0 + δ 2In0) −1Ŷn0 − Ŷ >n0(K̂n0 + δ 2In0) −2Ŷn0 ≤ Ŷ >n0(K̂n0 + δ 2In0) −1Ŷn0
≤ ‖Ŷn0‖2l2 δ2 .
The second line follows from the reproducing property. We thus can see that for each fixed X̂n0 and Ŷn0 , g (and consequently f ) belong to the RKHS of κ.
The values of maxx∈X g(x) and minx∈X g(x) are numerically approximated by sampling 10, 000 points on the hypersphere, and choosing the maximum and minimum over the sample.
We then generate the training datasets Dn of the sizes n = 2i, with i = 1, 2, . . . , 13, by sampling n points Xn = [xi]ni=1 on the hypersphere, uniformly at random. The values Yn = [yi] n i=1 are generated according to f . We then train the neural network model to obtain f̂n(.). The error maxx∈X |f(x) − f̂n(x)| is then numerically approximated by sampling 10, 000 random points on the hypersphere and choosing the maximum of the sample.
We have considered 9 different cases for the pairs of the kernel and the input domain. In particular, the experiments are run for each κNT,s, s = 1, 2, 3 on all Sd−1, d = 2, 3, 4. In addition, each one of these 9 experiments is repeated 20 times (180 experiments in total).
In Figure 2 we plot maxx∈X |f(x) − f̂n(x)| versus n, averaged over 20 repetitions, for each one of the 9 experiments. Note that for maxx∈X |f(x) − f̂n(x)| ∼ nα, we have log(maxx∈X |f(x) − f̂n(x)|) = α log(n) + constant. Thus, in our log scale plots, the slope of the line represents the exponent of the error rate. As predicted analytically, we see all the exponents are negative (the error converges to 0). In addition, the absolute value of the exponent is larger, when s is larger or d is smaller. The bars in the plot on the left in Figure 2, show the standard deviation of the exponents.
For training of the model, we have used neural-tangents library (Novak et al., 2019) that is based on JAX (Bradbury et al., 2018). The library is primarily suitable for κNT,1(.) corresponding to the ReLU activation function. We thus made an amendment by directly feeding the expressions of the RF kernels, κs, s = 2, 3, to the stax.Elementwise layer provided in the library. Below we give these expressions
κ2(u) = 1
3π
[ 3 sin(θ) cos(θ) + (π − θ)(1 + 2 cos2(θ)) ] ,
κ3(u) = 1
15π
[ 15 sin(θ)− 11 sin3(θ) + (π − θ)(9 cos(θ) + 6 cos3(θ)) ] ,
where θ = arccos(u).
We derived these expressions using Lemma 1 in a recursive way starting from κ1(.). Also, see Cho & Saul (2009), which provides a similar expression for κ2(.) and a general method to obtain κs(.) for other values of s. We note that we only need to supply κs(.) to the neural-tangents library. The NT kernel κNT,s(.) will then be automatically created.
Our experiments run on a single GPU machine (GeForce RTX 2080 Ti) with 11 GB of VRAM memory. Each one of the 180 experiments described above takes approximately 4 minutes to run.

Review summaries:
The main contribution of this paper is to characterise the eigenvalue decay of the Neural Tangent Kernels associated with fully-connected neural networks evaluated on the hypersphere when the activation functions of the form $Relu^{s}$ where $s$ is a parameter that regulates the smoothness of the activation functions. The results generalise existing results for the particular case $s=1$, i.e. the case of ReLU activations [1,2]. The idea of the proof is to rely on a recent result from [1] which bounds the eigenvalye decay of an arbitrary rotationally invariant kernel based on smoothness and end-point asymptotic properties of the kernel written as a function from $[-1,1]$  to $\mathbb{R}$ where $[-1,1]$ corresponds to the inner product between the two arguments of the kernel function. The computation of the  asymptotics relies on an elegant use of Stein's Lemma as well as the recurrent relation between the NTK and RFK (random feature kernel) of various layers. Results for the eigenvalue decay of the RFK are also provided. Similarly to other works, once eigenvalue decay is obtained, various results can be obtained which further characterise the kernel and the learning problem: (1) it is shown that the kernel is equivalent to a Matérn family of kernels (which itself is equivalent to a sobolev space approach), (2) data-dependent generalisation bounds are shown where the distance between the empirical estimate and the groudn truth is bounded by a term that depends on the relationship between the test point and the training points (3) generalization bounds in $L^\infty$ norm with some strong assumption on the training points (they essentially have to be chosen in a "perfect" way). Applications to reinforcement learning are hinted at in a discussion at the end.      / ================== References ==================  [1] Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. ICLR 2021.   [2] Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the Laplace and neural tangent kernels. NeurIPS 2020.    

The paper provides a uniform generalization bound for overparameterized neural networks by assuming that the target function resides in the reproducing kernel Hilbert spaces generated by Neural Tangent (NT) kernels associated with general ReLU activation functions.  The approach is based on so-called maximum information gain, which is neat. The equivalence of the RKHSs generated by NT kernels and Matern kernels are discussed. 

The authors consider neural tangent kernels (NTKs) kappa_{NT, s}^l of the neural networks of depth l associated with ReLU a and its powers a_s with a positive integer s. Theorem 1 gives relations between the RKHSs generated by the NTKs and those generated by Matern kernels. Theorem 2 gives bounds for the maximal information gain of the NTKs. Theorem 3 provides some uniform generalization bounds for kernel ridge regression with the NTKs. 

The paper studies over-parametrized neural networks when the size of the network goes to infinity. In this regime, it is known that training the network via gradient descent type algorithms is equivalent to learning via the Neural Tangent Kernel (NTK) and the main focus is on this problem.   Previous results have shown that when one takes ReLU as the activation function, the RKHS associated with the NTK is equivalent to the RKHS of the Laplace kernel. The current paper generalizes this result to powers of ReLU and shows that as the activation function becomes smoother, so do the functions in the RKHS. Moreover, the exact decay of the eigenfunctions is also identified, in this extended case.  Using the above results the authors establish uniform bounds on the generalization error when learning a function from the appropriate RKHS with kernel regression.