Uniform Generalization Bounds for Overparameterized Neural Networks
Authors: Sattar Vakili
Michael Bromberg
Jezabel R Garcia
Da-shan Shiu
Alberto Bernacchia
Venue: ICLR 2022 Submitted (2022)
Keywords: Information Gain
Effective Dimension
Overparameterized Neural Networks
Neural Tangent Kernel
Random Feature Kernel
RKHS
Matérn
Uniform Error Bounds

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.

Under review as a conference paper at ICLR 2022
UNIFORM GENERALIZATION BOUNDS FOR OVERPA- RAMETERIZED NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
An interesting observation in artificial neural networks is their favorable gener- alization emror despite typically being extremely overparameterizze. It is well known that the classical statistical learning methods often result vacuous gen- eralization errors in the case of overparameterized neural networks. Adopting the recently developed Neural Tangent (NT) kernel theory. we prove uniform gener- alization 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, act 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 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 byproduct of our results, we show the equivalence between the RKHS corresponding to the NT kernel and its coun- terpart 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.
bounds capture the ex-
INTRODUCTION
Neural networks have shown an unprecedented success in the hands of practitioners in several fields. Examples of successful applications include classification (Krizhevsky al., 2012; LeCun et al., 2015) and generative modeling (Goodfellow et al., 2014; Brown et al., 2020). This practical effi- ciency has accelerated developing analytical tools for understanding the properties of neural net- works. A long standing dilemma in the analysis of neural networks is their favorable generaliza- tion error despite typically being extremely overparameterized. It is well known that the classical statistical learning methods for bounding the generalization error, such as Vapnik Senik-Chervvonnniss (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 overparam- eterized neural networks. In particular, let D, = { y;) be a possibly noisy dataset collected from a true model f: be the learnt model using a gradient based training of an overparameterizee neural network on D,,- We are interested in bounding (=) fx() uniformly all test points x belonging to particular domain X. recent line of work has shown that gradient based learning of certain overparameterizedd neural networks can be analyzed using projection on the tangent space at random initialization. This leads to the equivalence of the solution 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 al., 2019).
f(z;) + e;, where e; are well behaved zero mean noise terms. Let fr.

---

Under review as a conference paper at ICLR 2022
1.1 CONTRIBUTIONS
Here, we summarize our contributions. We propose the maximal information gain (MIG), denoted by y) (n), of the NT kemel k, as a measure of complexity of the learning problem for overparam- eterized 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 the MIG of the NT kernel. Using these bounds, for networks with infinite number of parameters, we analytically prove novel gener- alization error bounds decaying with respect to the dataset size n. Furthermore, 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 the surface of the hypersphere; 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 1 times differentiable activation functions 0, (2) = (max(00, u))", E N. We show that, with these activation functions and a dimensional hyperspherical support, the eigenvalues X of the corresponding NT kernel decay at the rate X; ii- d12 special cases; see Section 2 for details).
(up to certain parity constraints on in
We then use the cigendecay of the NT kernel to establish novel bounds on its MIG, which are of the Then, we show this implies high probability error bounds of the form 2e=1
form 7h (1) = Ö(n====2) d-1
sup=ex [f(x) - (z) = O(nzzTa5 when f belongs to the corresponding reproducing kernel Hilbert space (RKHS), and D,, is distributed over X' in 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 a.(.) is equivalent to the RKHS of a Matérn kernel with smoothness parameter V = s 2. 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 func- tion, a, (.), and that of the Matérn kernel with v = 2 (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 Matérn kernel with the corresponding smoothness (see Section 3.2). We note that the members of the RKHS of Matérn family of kernels 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 conjugate kernel or neural networks Gaussian process (NNGP) (Cho& & Saul, 2009; Daniely et al., 2016; Lee et al., 2018; de G. Matthews al., 2018 8), this model corresponds the case where only the last layer of the neural network is trained (see Section for details).
Table 1: The bounds MIG and generalization error for RF and NT kernels, with (.). activation functions, when the true model f belongs to the RKHS of the corresponding kernel and is supported on the hypersphere gd-1 Rd.
Kernel
MIG, (n)
Error bound, 1f(x) fn
NT
1 n -==2--2
(log(n))
2041 a42m12
O 2d444-44
(log(n))
2d44a-4
RF
O
d-1
(n)(
-Pa-1
(log(n))
'The general notations used in this paper are defined in Appendix A.
2

---

Under review as a conference paper at ICLR 2022
We note that the decay rate of the enror bound is faster in the of RF kernel with the same activation function. Also, the decay rate the error bound is faster when s larger, for both NT and RF kernels. In interpreting these results, corresponding kernels. The RKHS of the RF kernel smaller than the RKHS of the NT kernel. Also, when is larger, the RKHS is smaller for both NT and RF kernels.
should however take into account the RKHS of the
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 (c.g., Yang et al., 2020; Gu et al., 2021).
2 OVERPARAMETERZES NEURAL NETWORKS IN KERNEL REGIMES
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 neural network with a large width m parameterized by W. The model can be approximated with its linear projection on the tangent space random initialization Wo,
f(x W) = (xx Wo) + (W Wo, Vw Wo)).
The approximation error can be bounded by the second order term f I Woll and shown be diminishing as m grows, where S.. 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 al., 2018), given by k(x,x')=
= lim (Vw Wo). [w Wo))
m=0000
2.1 NEURAL KERNELS FOR A 2 LAYER NETWORK
Consider the following layer neural network with width m and a proper normalization
f(x, W)
uya(wfx)) x),
(1)
where a(.) is the activation function, e is constant, x X' is d dimensional input to the net- work, wy E Rd are the weights in the first layer, and oy E R are the weights in the second layer. The weights // are initialized randomly according to (Oa, Ia) and vj are initialized randomly
according to (0, 1). Then, the NT kernel this network can be expressed as (Jacot et al., 2018)
kxr(z, (xx T New (w TwTTa 1:)a (w Ta))] + d'Em aa(w" x))(w" x')]. (2)
When Wj are fixed at initialization, and only vy are trained with 6² regularization, the model is equivalent to a certain Gaussian process (GP) (Neal, 2012) that is often referred to as random feature (RF) model. The RF kernel is given as (Rahimi et al., 2007)
k(r,,²) eF [a(w] x))(w" ()))wTTa)))
Note that the RF kernel is the same as the second term in the expression the NT kernel given in equation 2.
2.2 ROTATIONAL INVARIANCE
When the input domain is the hypersphere Sd-1, by the spherical symmetry of the Gaussian distribution, the neural kernels are invariant to unitary transformations" and can be expressed as
Rotationally invariant kemels also sometimes referred dot product zonal kemness
3

---

Under review as a conference paper at ICLR 2022
function of Txx'. RF kernels, as defined in equation 2 and equation 3, respectively. In this notation, s specifies the smoothness of the activation function, au(u) (max(0, u))².
x'. We thus the notations Kyr,a (2' ToTTo 2') and (2 refer to the NT and
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.
(N) = ( - arccos(u)) + k1(u), π
(1(
1 π
[u(T= arccos(u)) + v1-
In deriving the expressions above, the constant in equations 2 and 3 is set to v2. In general, (2a-1)1!* that normalizes the maximum value of the RF kernel to 1: Kg (1 = 1, Vs 2 1.
choose
2.3 NEURAL KERNELS MUL.TILAYER NETWORKS
For an / >> 2 layer network, the NT kernel is recursively given as (see, Jacot et al., 2018, Theorem 1) (u) c² N (N) (w)) + r,)(
(u) = (n (u)).
(4)
Here, (.).)) corresponds to the RF kernel of an I 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 / = 2. we drop the layer index from the superscript, as in the previous subsection. An expression for the derivative x-) of the RF kernel in 2 layer network, based Kg-1, is given in Lemma 1. That is needed to see the equivalence of the expressions equation 4 to the one given in Theorem 1 of Jacot et al. (2018).
3 THE RKHS OF THE NEURAL KERNELS
When the domain is gd-1, as discussed car- lier, the neural kernels have rotationally in- variant (dot product) form. The rotationally in- variant kernels can be diagonalized in the basis of spherical harmonics, which are special func- tions on the surface the hypersphere. Specif- ically, the Mercer decomposition of the kernels (for all 2 2 and s 2 1) can be given as
0.4
d2s
dyg
dys
deg
dys
0.0
Ná.1 A (2))))))))))
<(x x')
Σ
02
du
d122
d1s
du.
d1s
where the eigenfunction ã., is the j'th spher- ical harmonic of degree i, 7₂ is the corre- sponding eigenvalue, Na,; = 2i+d-2 (+==))) the multiplicity of A; (meaning the number of spherical harmonics of degree which all share the same eigenvalue λ,), and the conver-
Figure The spherical harmonics of degrees
1,2,3, 4, on 8?, The function value given by color.
gence of the series holds uniformly on X' X'x X. As a consequence of Mercer's representation theorem, the corresponding RKHS can be written as
Hrs { f()
Na.s
Na.i w
-
Wi A (.)(+)) Way ER, 11.1
<
j=l
Formal statements of Mercer's 's theorem and Mercer's representation theorem, as well as a formal definition of Mercer eigenvalues and eigenfunctions are given in Appendix B.
4

---

Under review as a conference paper at ICLR 2022
We use the notation A (in contrast to À₂) to denote the decreasingly ordered eigenvalues, when their multiplicity is taken into account (for all i Ei= Na."" <is Ei== Na,", we define X; = X )
3.1 THE DECAY RATE OF THE EIGENVALUES
As discussed, both RF and NT kernels 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 Å ~ i-d cigendecay for the NT kernel on the hypersphere gd-1, In this work, we use a recent result from Bictti & 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 decomposi- tion the basis of spherical harmonics. Then, the eigendecays are as reported in Table 2.
Table The eigendecays of the neural kernels.
For of the same parity of s: År i-d-20+2 di 1 21
1 1= 2
NT
For i of the opposite parity of s: X o(i o(i-d-2)t)), A; = oli
d=2y-2
d-1
>>> 2
X i d- 2s+2
di d=22222
0+20-2
For i of the opposite parity of _, ~ i- A, ~
1=2x
d=1
1 1= 2
RF
For of the same parity of s: À = oli d(2), d o(t _T)
A ~ii i- A d+2a
1> 2
Proof Sketch. The proof follows from Theorem of Bietti & Bach (2020), which proved that the eigendecay rotationally invariant kernel x(.) [-1, > R can be determined based on its asymptotic expansions around the endpoints, +1. In particular, when
x(1 -) = (t) + c+1 + x(-1+t) = p-1(t) + c +o(t))
for polynomial P11 and non-integer 0, the eigenvalues decay at the rate \; ~ (c41+ 20++ for even i, and X; (c+1 dd-)2=--20+1 for odd i. A formal statement of this result is given 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 1 times differentiable activation functions, in the case of I and > 2 layer networks. Our derivations is based on the following Lemma.
Lemma For the RF kernel defined in equation 3, with activation function (.).). and c (2s-1)!! have
8²
(((u)
2 Ke-1(u).
The proof is given in Appendix D. Lemma allows to recursively derive the endpoint expansions of K2 from those of Kg-1, through integration. We thus obtain 0 and c+1 for s > 1, when 2, using recursive relation s. We then the compositional forms given in equation 4 to obtain the same, when > 2, resulting in the eigendecays reported in Table 2.
Remark 1 The parity constraints in Table 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
5

---

Theorem On a hyperspherical domain, when 1 2, Hei (Hrt) ) is equivalent to HK., and, when (v + 2 The statement is sunmarized in Under review as a conference paper at ICLR 2022
representation power of the neural kernels, it does not affect analysis of MIG and error rates, since for that analysis only use X; = 2.
Remark 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 I, for s > 1 (see Appendix E for the expressions of the constants). When shown in Bietti & Buch, 2020).
however, the constants grow at most as fast as 1 (as
3.2 EQUIVALENCE OF THE RKHSS OF NEURAL AND MATÉRN KERNELS
Our bounds on the eigendecay of the neural kernels show the connection between the RKHS of the neural kernels, and that of Metérn family of kernels. Let Hx. denote the RKHS of the Matérn kernel with smoothness parameter
1 ==2 2, Hwim. Hk. (His, C Hkuh where
Table
Table 3: The relation between the RKHSS corresponding the neural and Matérn kernels.
Kernel
1=
1> 2
NT
HoNT, HH,,
HENT. H%. Hr, = Hk,t
RF
Ha, C Hb.
The formal definition of equivalence (=) and subset (C) 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 cigendecay of the Matérn family of kernels on manifolds proven in Borovitskiy et al. (2020), and the Mercer's s representation theorem. Details are given Appendix F.
= 2, we only have Hyin. Ha and not vice versa, is result of parity constraints in Table 2. The subset relation can change to equivalence, with bias term which removes the parity constraints (see, Ronen al., 2019).
Remark 3
The observations that when
special case Theorem 1, when = 1, was recently proven in (Geifman et al., 2020; Chen & Xu, 2021). This special case pertains the ReLU activation function and the Matérn kernel with smoothness parameter v = that is also referred to as the Laplace kerne.
Remark 4 It is known that the RKHS of Matérn kernel with smoothness parameter is equivalent to a Sobolev space with parameter v + (e.g.. see. Kanagawa et al., 2018, Section 4). This obser- vation provides intuitive interpretation for the RKHS of the neural kernels consequence of [[f Il (Ilflleet) is proportional to the cumulative I2² norm of the weak deriva- rives of up to d-1 (s d+ order. l.e., J E Heiy (f E Hyr) translates to the existence of weak derivatives of f up to + ايك (s+ order, which can be understood as a versatile measure controlled by For the details the definition of weak derivatives and Sobolev spaces see, e.g., Hunter & Nachtergaele (2011).
Theorem 1. That is
for the smoothness
4 MAXIMAL INFORMATION GAIN OF THE NEURAL KERNELS
In this section, the eigendecay of the neural kemnlss shown in the previous section to de- rive bounds on their information gain, which will then be used to prove uniform bounds on the generalization emror.

---

Under review as a conference paper at ICLR 2022
4.1 INFORMATION GAIN: MEASURE OF COMPLEXITY
To define information gain, we need to introduce a fictitious GP model. Assume F a zero mean GP indexed X' with kernel k. Information gain then refers to the mutual information I(Y,; between the data values y = [yl and F. From the closed from expression of mutual information between two multivariate Gaussian distributions (Cover, 1999), it follows that
log det I(,;; F) 2
In
Kn X
Here K,, is the kernel matrix [Kn] ka xy), and À O regularization parameter. We also define the data independent and kernel specific maximal information gain (MIG) as follows.
r*(n) sup I(Yn;F) X,CX
(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 significant impact on the regression model can be finite. The effective dimension of a kernel often defined as (Zhang, 2005; Valko et al., 2013)
de(n) = Tr (K,, + 1²)
is known that the information gain and the effective dimension are the same up to logarithmic factors. Specifically, (n) s I(Yx; F), and F) = Odd (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 the ones for a linear model, which has a feature dimension of d, (n).
4.2 BOUNDING THE INFORMATION GAIN OF THE NEURAL KERNELS
In the following theorem, provide a bound on the maximal information gain of the neural kernels.
Theorem For the neural kernels with all 1 2 2, on a hyperspherical domain X = =dd-1, we have
Tieo.. (n) O n an (log(n)) =fz)") in the case of NT kernel, 7kd (n)
n nd=zi (log (n)
20m1 the case of RF kernel.
A special case of our Theorem 2, for the special case of the ReL.U activation function, was recently proved 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 (Maleček Nádeník, 2001). Details are given in Appendix G.
UNIFORM BOUNDS ON THE GENERALIZATION ERROR
In this section, we use the bound on MIG from previous section to establish uniform bounds on the generalization error.
5.1 IMPLICIT ERROR BOUNDS
We first overview the implicit (data dependent) enror bounds for the kernel methods under the fol- lowing assumptions.

---

Under review as a conference paper at ICLR 2022
Assumption Assume the true data generating model f is in the RKHS corresponding neural kernel K. In particular, Il. ll. I B. for some B > 0. In addition, assume that the observation noise are independent R Gau-Gaasiinn random variables. That is E[exp(ne:)] S exp( "² R² Vn E R, vi 2 1, where yi [(x;) + Ei, vi 2 1.
Under Assumption 1, for fixed æ E X, we have, with probability least 1 8 (Vakili et al., 2021a),
(f(z) - fx)) = (2))
where [x(x) = k (R), + 13 is the solution to the kernel ridge regression using k and D, o
k(x,z) (z) ( , + I²) k,, k,j (x) [<(x 2;)]ā=1+ and 3(6)
B+ + X 2 log( Equation provides high probability bound on [f(x) (x)).. The decay rate
of this bound based on n, however, is not explicit.
5.2 EXPLICIT ERROR BOUNDS
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 clear that with assumption the distribution of the data, generalization error cannot be nontrivially bounded. For example, all the data points collected from 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 data collection module which collects the data points based on the current uncertainty level of the kernel model. In particular, consider dataset D, collected as follows: x; = arg maxzex Oz- (z), where o.(.) is defined above. We have the following result.
Theorem Consider the neural kernels with 1 2 2. on a hyperspherical domain gd-1 Con- sider model fn trained on Dn. Under Assumption 1, with probability least 8, uniformly in E X.
d- 1))
[f(x) - (())) =
22+1 n 122444--
(lo((n)) 264-e- (Log(
in the case of NT kernel,
nd
[f(x) - fnx)))(()) o
21-1 (Iog(n))
(log( 20447
2++1
8 1)8)
in the case of RF kernel.
(8)
Proof Sketch. The proof follows the same steps as the proof of Theorem of Vakili et al. (2021a). The key step is bounding the total uncertainty in the model with the information gain I(Y,:: F)) (Srinivas al., 2010). This allows us to bound the o,
that is ΣØ (x,) I 3)
in the right hand side of equation by (n)(n)) up multiplicative absolute constants. Plugging in the bounds on 7xx (n) from Theorem 2, and using the implicit error bound given in equation (with a union bound on a discretization of the domain with size (ndd))), we obtain equation 8. A detailed proof is given in Appendix H.
EXPERIMENTS
In this section, we provide experimental results the error rates. In our experiments, we create synthetic data from a true model / that belongs to the RKHS of a NT kernel k. For this purpose, we create two random vectors Xn, E 2 and Y... RR and let f(.) = KT (.)(K,,. + + no> where kn. and Kr, are defined similar to k,, and K,, in Subsection 5.1. We then generate datasets D, of various sizes = 2*, with i = 1, 1,2.... ....., 13, according to the underlying model f. We train the model obtain f.. Figure 2 shows the error rate versus the size 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- saarall-aangetss library (Novak et al., 2019). See Appendix for more details.
8

---

Under review as a conference paper at ICLR 2022
2
d=2
0.6
Error Exporeen
d
-0.8
d= d=
-1.0
-1.2
mnn If
16
120
2 1021
Figure 2: Left: the exponent of the error rate versus and d. As expected, larger values of and d result in, respectively, faster and slower error decays. The bars show the standard deviation. Right: rates for 2, and d = 2,3, 4, shown in separate panels. Both axes are in log scale that the slope of the line represents the exponent of the error rate. Experimental error rates are consistent with the analytically predicted results.
7 DISCUSSION
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 (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 7hk (n), leaving the regret bounds implicit. A consequence of our bounds on 7ik (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 TIxt... (n) into the existing
regret bounds, we get Onn -=2)-2) ), which is sublinear only when 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 al. (2021c), 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 RI. and bandit problems were not considered in this work. Our remark is mainly concerned with the consequences of our bound on MIG, which appears the regret bounds.
& (that, e.g., excludes the
The recent work of Wang et al. (2020) proved that the 1 norm of the error is bounded as |If 111 O(n - for two layer neural network with ReLU activation functions in kernel regimes. Bordelon et al. (2020) decomposed the 7,2 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 L norm. In addition, provide explicit error bounds depending on differentiability of the activation functions.
The MIG has been studied for popular GP kernels such Matérn and Squared Exponential (Srinivas et al., 2010; Vakili et al., 2021b). Our proof technique is similar to that Vakili et al. (2021b). Their analysis however does not directly apply the NT kernel the hypersphere. The reason 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 proof technique similar Srinivas et al. (2010) results suboptimal bounds in our case.
Our work may be relevant to the recent developments in the field of implicit neural representations (Mildenhall al., 2020: Sitzmann et al., 2020; Fathony al., 2020). this line of work. the input to a neural network often represents the coordinates of a plane (image), 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 ReL.U in these applications, since the models are also smooth (Sitzmann et al., 2020).

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundtttin cambridge university press, 2009.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Peter L Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions on Information Theory, 44(2):225-536, 1998.
Peter L Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-44) 44222222222222- 2002.
Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. arXiv preprint arXiv:2009. 14397, 2020.
Blake Bordelon, Abdulkadir Canatar, and Cengiz. Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 1024-1034. PMLR, 2020.
Viacheslav Borovitskiy, Alexander Terenin, Peter Mostowsky, and Mare Deisenroth. Matérn Gaus- sian processes Riemannian manifolds. In Advances in Neural Information Processing Systems, volume 33, pp. 12426-12437, 2020.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, and Skye Wanderman-Milme Jax: composable transformations of python+ numpy programs. Version 0.1, 55, 2018. URL https::t//// /tttps://gtthbb.. httggttthuuu...g.ggg com/ google/jax.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint 200.::2000.111155. 2020.
Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Gaussian process optimization with adaptive sketching: scalable and no regret. In Proceedings of the Thirty-Secone Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, Phoenix, USA, 25-28 Jun 2019. PMLR.
Lin Chen and Sheng Xu. Deep neural tangent kernel and Laplace kernel have the same RKHS. In International Conference on Learning Representations, 2021.
Louis HY Chen, Larry Goldstein, and Qi-Man Shao. Multivariate normal approximation. In Normal Approximation by Stein's Method, pp. 313-341. Springer, 2011.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, volume 32, 2019.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems, volume 22, 2009.
Sayak Ray Chowdhury and Aditya Gopalan. On kemelized multi-armed bandits. In International Conference on Machine Learning, pp. 844-853, 2017.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power initialization and a dual view on expressivity. Advances Neural Information Processing Systems, 29:2253-2266 2016.
Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018.
10

---

Under review as a conference paper at ICLR 2022
Vincent Dutordoir, Nicolas Durrande, and James Hensman. Sparse gaussian processes with spherical harmonic features. In International Conference on Machine Learning, pp. 2793-2802 PMLR, 2020.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXhv:1703.11000, 2017.
Rizal Fathony, Anit Kumar Sahu, Devin Willmott, and J Zico Kolter. Multiplicative filter networks. In International Conference on Learning Representations, 2020.
Amnon Geifiman, Abbay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the Laplace and neural tangent kernels. In Advances in Neural Information Processing Systems, volume 33, pp. 1451-1461, 2020.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched neural bandits. arXiv preprint 102.::22022.3020 2021.
John K. Hunter and Bruno Nachtergaele. Applied Analysis. World Scientific, 2011.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems, volume 31, 2018.
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaussian processes and kernel methods: A review on connections and equivalences. Available at Arxiv, 2018.
Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret. arXiv preprint arXiv:2107.03144 2021.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 15:1097- 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436 2015.
Jaehoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep neural networks as Gaussian processes. In International Conference on Learning Representations, 2018
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. On the linearity of large non-linear models: when and why the tangent kernel constant. Advances Neural Information Processing Systems, 33, 2020.
Kamil Maleček and Zbyněk Nádeník. On the inductive proof of Legendre addition theorem. Studia Geophysica et Geodaetica, 15-11, 2001.
J Mercer. Functions of positive and negative type and their commection with the theory of integral equations. Philos. Trinsdictions Rogyal Soc, 415: 1909.
Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng. Nerf: Representing scenes as neural radiance fields for view synthesis. In European conference on computer vision, pp. 405-421. Springer, 2020.
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015.

---

Under review as a conference paper at ICLR 2022
Ivan Nourdin and Giovanni Peccati. Stein's method wiener chaos. Probability Theory and Related Fields, 145(1-2):55-118,, 2009.
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A Alemi, Jascha Sohl-Dickstein, and Samuel Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. arXiv preprint 1rXiv:19/2.02803, 2019. URL https: htap::///gthhle com/ google/ neuzal-tangents.
Ali Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. In NIPS, volume 3, pp. 5. Citeseer, 2007.
Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural net- works for learned functions of different frequencies. Advances in Neural Information Processing Systems, 32:4761 47711, 2019.
Vincent Sitzmann, Julien Martel, Alexander Bergman, David Lindell, and Gordon Wetzstein. Im- plicit neural representations with periodic activation functions. Advances in Neural Information Processing Systems, 33, 2020.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias W. Seeger. Gaussian process op- timization in the bandit setting: No regret and experimental design. In ICML, pp. 1015-1022, 2010.
Charles Stein. Miscellaneous frontmatter. In Approximate computation of expectations, pp. i-iii. Institute of Mathematical Statisties, 1986.
Elias M Stein and Guido Weiss. Introduction to Fourier Analysis on Euclidean Spaces (PMS-32),
Volume 32. Princeton university press, 2016.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer, 2008
Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da-shan Shiu. Optimal order simple regret for Gaussian process bandits. arXiv preprint 0rXiv:2108.09266 2021a.
Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pp. 82-90.
PMLR, 2021b.
Sattar Vakili, Jonathan Scarlett, and Tara Javidi. Open problem: Tight online confidence intervals for RKHS elements. Conference on Learning Theory, pp. 4647-4652. PMLR, 2021c
Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time anal- ysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference Un- certainty in Artificial Intelligence, UAI'13, pp. 654-663, Arlington, Virginia, USA, 2013. AUAI Press.
Wenjia Wang, Tianyang Hu, Cong Lin, and Guang Cheng. Regularization matters: A nonparametric perspective on overparametrized neural network. 2020.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan. On function approx- imation in reinforcement learning: Optimism the face large state spaces. In Advances in Neural Information Processing Systems, 2020.
Tong Zhang. Learning bounds for kemel regression using effective data dimensionality. Neural Computation, 1799):0777-0088, 2005.
Weitong ZHANG, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural Thompson sampling. In International Conference on Learning Representations, 2021.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based explo- ration. In International Conference Machine Learning, pp. 11492-11502 PMLR, 2020.
12

---

Under review as a conference paper at ICLR 2022
A GENERAL NOTATION
In this section, we formally define our general notations. We use the notations O,, and I, to denote the zero vector and the square identity matrix of dimension respectively. For matrix M (a vector v), M (e denotes its transpose. In addition, det and log det are used to denote determinant of and its logarithm, respectively. The notation ||ø||aa is used to denote the 12 norm of vector For v E R and a symmetric positive definite matrix Σ E Rddd (N, Σ) denotes a normal distribution with mean and covariance E. The Kronecker delta is denoted by ö.gi The notation gd-1 denotes the d dimensional hypersphere in R.d. For example, $ C TR3 is the usual sphere. The notations and O denote the standard mathematical orders, while O is used to denote O up logarithmic factors. For two sequences Gn b + R. we use the notation an ~ bn. when On = (b,,) and bn - (an). For E N, we define (2s 1)!! I (2i 1). For example, 3!! and 5!! 15.
For normed space H. we use ||-1|z to denote the norm associated with H. For two normed spaces conditions are satisfied. First, Hi C H2 sets. Second, there exist constant C1 > O, such that Ilffl S cillfllH, for all f E H1. We also write Hi H2, when both Hi H2 and H2 Hi.
H1, H2, we write Hi H2, if the following
The derivative of a : R + R is denoted by a'. We define 0" = 0, so that (x()) = (mmax(02))) corresponds to the step function: az(z) = 0, when r S and ax(x) 1, when x > 0.
B MERCER'S S THEOREM
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 spectral decomposition of the kernel in terms of an infinite dimensional feature map (see, e.g. Stein- wart & Christmann (2008), Theorem 4.49).
Theorem 4 (Mercer's Theorem ) Let X' be compact domain. Let k be continuous square inte- grable kernel with respect to a finite Borel measure p. Define a positive definite operator Tū
(T&f)() ((.)))(()dd.
Then, there exists a sequence of ceanraaueeeegenfunntioon pairs {(A,, such that Xs E R and T& = Xyos, for i 2 1. Moreover, the kernel function can be represented as
k(x,x') Σ (=0((2)0.(z)),
where the convergence of the series holds uniformly on x X.
The X; and o; defined in Mercer's theorem are referred to as Mercer eigenvalues and Mercer eigen- functions, respectively.
Let Hr denote the RKHS corresponding to k defined Hilbert space equipped with an inner product {., .)e satisfying the following: x) E Hy. Vx e X, and (f. (f, = f(x), Vr X,, V. Hr (reproducing property). As consequence of Mercer's theorem, H4 can be represented terms of ((Ai, g that is often referred to as Mercer's 's representation theorem (see, e.g., Steinwart & Christmann (2008), Theorem 4.51).
Theorem (Mercer's Representation Theorem) Let ((), (1) be the Mercer eigenvalue- eigenfunction pairs. Then, the RKHS corresponding is is given by
Hss { (() 11= = Σ wi dx()) w E ER = Σ
w < 00
1=1
Mercer's representation theorem indicates that 1 form an orthonormal basis for H4: (A, oi A3 0z.r. It also provides a constructive definition for the RKHS as the span of this orthonormal basis, and a constructive definition for the || as the norm of the weights [wx]ee se, vector.
13

---

Under review as a conference paper at ICLR 2022
C CLASSICAL APPROACHES TO BOUNDING THE GENERALIZATION ERROR
There are classical statistical learning methods which address the generalization error in machine learning models. Two notable approaches VC dimension (Bartlett, 1998; Anthony & Bartlett, 2009) and Rademacher complexity (Bartlett & Mendelson, 2002; Neyshabur et al., 2015). In the former, the expected generalization loss 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. the case of layer neural network of width m, it is shown (0ym///
that both of these approaches result in generalization bound of O m/mm// m/)n that is vacuous for overparameterized neural networks with very large m.
more recent approach studying the generalization error is PAC Bayes. provides vac-uucuous enror bounds that depend on the distribution of parameters (Dziugaite & Roy, 2017). However, the distribution of parameters must be known or estimated order to use those bounds. Taking a different approach, Arora et al. (2019) provides bounds on expected generalization error of well- conditioned 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 x.
D PROOF OF LEMMA
Lemma 1 offers a recursive relation over s for the RF kernel. We prove the lemma by taking the derivative of (-). and applying the Stein's 's lemma (given at the end of this section).
Let x (0.0......0. O, 1] and x' ................................ VI - u², u/ T, so that x x' TTx
and x' Sd-1
We have
ww 1 Ou Bw-N(oodde [as(w" x))s(w x')] = Ew-Ni0e.a) ax ()(war)s,,_1 xa))saa11(0 (w xx' '') v1 u²
0
sBwnNi0.La) 80,-1 (w xx)))-1 1 (w) xz)
+(s - ()) 2'))) aai)]
(s 1)u VI u² 1))a-2(ul 2'))
sE (B
v1 u²
s² Ben
|a--l(w" (t)a--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 [la,(w' r)sa (w T "x' (ra),a), where wa is the normally distributed random variable, also to E(a, (wi 1))aa-1((0) iww x') awa-1 normally distributed random variable.
VI-ual where wa-1 is the
Taking into account the constant normalization of the RF kernel c²
2 1]!!
we have
2 ①
K'g (u)
(2s 1)!! Du E Ew [as(w) x))a( [2']]
2x²
Bww (a (o-I((Tx)aa--0 x))x-1(w' Ta")
E
(2s 1)!!
82
2s 1s
which proves the lemma.
Lemma (Stein's Lemma) Suppose X No 1) is normally distributed random variable. Consider a function R - IR such that both [X)] and Elg' (X)) exist. We then have
[[Xg(X)] Elg' (X)].
The proof Stein's 's lemma follows from an integration by parts (see, e.g., Stein, 1986; Nourdin & Peccati, 2009; Chen et al., 2011).
14

---

Under review as a conference paper at ICLR 2022
E PROOF OF PROPOSITION 1
This proposition follows from Theorem of Bietti & Bach (2020), which proved that the eigendecay of a rotationally invariant kernel к [-1.1] + oo can be determined based on its asymptotic expansions around the endpoints +1. Recall that rotationally invariant kernel & can be represented as n(x x') = k(x,,') Their result is formally given in the following lemma.
Lemma (Theorem in Bietti & Bach (2020)) Assume K [-1,1] is C and has the fol- lowing asymptotic expansions around =1
x(1 - t) = -P+((t) + c42t + t x(-1+t) = p-1(t) 1t + o(t))
fort >> O. where P=1 are polynomials, and 0 is not integer. Also, assume that the derivatives of &. admit similar expansions obtained by differentiating the above ones. Then, there exists Ca.s such that, when is even, if c+1 # -c-1: x4 (C+1 + Ca d-22++1, and, when i is odd, if C+1 + C_1: Xi (c+1 -a.i) o(l-d-20+)) one of the two parities. If k is infinitely disserentiable on [-1, 1] so that such O exists, the >; decays faster than any polynomial.
In the case |c+1| = le-1l then have 2s
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 times differentiable activation functions (.).
Recall that for 2 layer network, the corresponding RF and NT kernels are given by
KNT, (x x²) _ Nr (w x)), T a')] + kx(x Ta)) (x x²) = la (wa 2')].
For the special cases of and 1, the following closed form expressions be derived by taking the expectations.
ku(u)
= E 1ooo xz)o 2²)] [2])]= = ( arccos(u)),
(u) a (u(f-arccossf + v1 u2
where u = TTx. At the endpoints +1, (u) ni (u) have the following asymptotic expansions.
ko(1 -t) 1 V2 + +((1),
v2 3 + o(t?),
xo(-1+t)
π
2/2
k1(1 -t) -1 1-1+
t2 + o(12),
3x
2V2
x1(-1+t)
レ t
(9)
3π
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 the endpoint expansions and the eigendecay to layer neural network with s > 1, in Subsection E. Then, we extend the derivation to > 2 layer neural networks, in Subsection E.2. In Subsection E.3, we show how the eigendecays terms of A can be translated to the ones in terms of A
15

---

Under review as a conference paper at ICLR 2022
E. ENDPOINT EXPANSIONS FOR LAYER NETWORKS WITH >
We first note that the normalization constant - 126-1 suggested in Section 2, ensures Ki k.(
1, for all 2 1. The reason is that, by the well known values for the even moments of the normal distribution, we have
(or.W x)a,(2' x')] (2s 1)!!
when x Tx' Also notice that K₂ (-1) = 0, for all 2 1. The reason is that when x Tx' = -1, 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²
K-- 11))
This is key component in deriving the endpoint expansions for 1. In particular, this allows us to recursively obtain the endpoint expansions of (-) from those of K. v.-1(.), by integration. That results in the following expansions for Ks..
K2 () (t),a(t) ct 20t1 + o(t 2411 )
x-(-1+1) -P-1,o(1) + 1 2n + o(t 2001
(10)
22 2 f p (t)dt, subject to (0) 1 (that follows form k.(1) 1). Thus, (t) can be obtained recursively, starting from p+), 1 (see equation 9). For example,
Here, (f)
3
t²
P+1,((t)
+
4
36
15
3
P+1,((t)
2
15 36
2
and so on.
-t) subject to (0) 0 (that follows from K.s (=(-1) = 0), and starting from p1 0, VZ (see equation 9).
24-1 J p-1,s-12 (t)dt Similarly, (t) can be expressed in closed form using (t),
5²
That leads to (t) = 0, Vs t,
The exact expressions of p+ (t) however do not affect the eigendecay. Instead, the constants C+ are important for the eigendecay, based on Lemma 3. The constants can also be obtained recursively.
Starting from C+1,1
2v2
-20 Also starting from C-1,1 (see equation 9), C+1,s (2s-1)(2++1)
2v2
3x
3r
(see equation 9), C-1,a
20 c+1
This recursive relation leads to
(2s
(){+11)
22
22
C-1,8
(11)
π
(4r
1)
and C+1,a =--1)=-1c_1. c-1.s-
In the case RF kernel, applying Lemma 3, we have π i-d-2s for having the opposite parity of s, and \ oii d-22 for having the same parity of s.
For the NT kernel. using 2, we have
-t) KNT, +1) = + 1) (-1
KN 1 1)
=c²(1 1)s² 1
(12)
16

---

Under review as a conference paper at ICLR 2022
Using the expansion of the RF kernel, we get
KN (1 - P+110(t) + ct 2011 + oot x²
KNT,o(-1++ = -P"1,a(t) + d" 1t _ + olt =
(13)
where
(1) = -c(11 - ((1-1)sp441ee -),spp+1,,-101) + pp
("),,(t) cc(-1 t)s²p)pppppp p-1 + ---10(11+))
and
41, C+1,--1
d
C-1,3-1-
Thus, in the case of NT kernel, applying Lemma 3, we have ); i-d-2++2 for i having the same parity of and X o(i o(i-d-2xt2) for i having the opposite parity of
E.2 ENDPOINT EXPANSIONS FOR / > 2 LAYER NETWORKS
We here extend the endpoint expansions and the eigendecays to > 2 later networks. Recall (u) = R2 (N, (u)). Using this recursive relation over I, prove the following expressions
<1, t) (t) e42,0t بيي + o(t 2 <$ (-1--+ = (1) + L
2042 + oll 2nt1
where Pl. are polynomials and c_i. are constants.
The notations P+1. and C+1,s in Subsection E.1 correspond to pł1,. e22,00 where we drop the superscript specifying the number of layers, for 2 layer networks.
For the endpoint expansion at 1, we have
ko(ket-(11 t))
= k,(1- 11 p (f) + 1-1 2nd + oft 21
= -P11, - p (t)
2 oft -
+c+1,0 - 1-1 (t) c41.
olt " للجة
to -1- 11-,, (t) - 1-1 2 oft اليية )
-41.8
Thus, we have
41.= = (- 20-1 21 C41,5 441.
(14)
where 941. is the coefficient t' (t),,(t). For these coefficients, we have
f+1, - 44..941.5
1-1,1
(15)
2.1 x² Starting from 4+1..
(which can be seen from the recursive expression of p+1,s given in
I
Section E. get
111
(28-1)i-1.
((11)
We thus have
((2++1)
s²
41,5=
C+1, +
C+1.8
I-1
(16)
(2s
28
That implies
1-2
g(2++1)
21i ~
(17)
(2s (2:11)
17

---

Under review as a conference paper at ICLR 2022
when 1.
The characterization of c+1 shows that our results do not apply to deep neural networks when > 1, in the sense that the constants grow exponentially in / (as stated in Remark 2).
For the endpoint expansion at -1, we have
R² (-1++) Ki (Kg ( (-1+1)) ())
= k.
20+1
+ oot 2
= (a(('=t))) + ki (
1-1 +
20+1
+ oll
where o is the coefficient of ( in (t). From the expression above can that
L = (1
(18)
Thus, 0-1 1.0 S In addition, the expression above implies = c "i
(19)
From Lemma 1, (u) I 2 for all u. Therefore,
82
1-2
d_ -
C-1,8
28
olc olc42.0)
when, s 1.
Comparing Ci we can see that for > 2, we have 1c41,1l # 1c',,ul. Thus, for the RF kernel with >> 2, applying Lemma 3, we have Ào i ddd-2s
For the NT kernel, recall
- (2) 1-1 (N) (w)) (w)
(u)
The second term is exactly the from Lemma 1. To find the endpoint expansions of the first term, we prove the following expressions for ( (u)).
the RF kernel. Recall the expression of K' based Ks-1
Ky 1 (1 (1- = (t) + 1,ttt 2 + oct 21
Kg (NL 1-1 (-1++)) = (1) + E1 2041 + oft 2
We use the notation used for the RF kernel to write the following expansion around 1 c 2 + o(t 2++²) )) Na-1 - 1 pi:
K-- (1--- (1 t))
(1---111---11-1
4 2041 oott 2x4)
+C41,-- - (4.
1-1
- 1-1 - 2بع1 oll ((12111) 2011
+o (1 (1 -1--Pt1. 1-1 (1) d 2041 oll - ) |
Thus, we have
41. = (-11-111) 2am1
C+1.8-1 - 441,8- C+,s
(20)
Recall, form the analysis the RF kernel that 441.6
21(1-)
We thus have
[24 1)
1-2
(2+-1)
(s - 1)2
41.- =
(2s -
12-11
C41,811 +
2s - 3
1,s
(21)
18

---

Under review as a conference paper at ICLR 2022
That implies
1-2
8(25-1)
$1.
12
c+1,8-1-
(22)
(28 - 1)
2
For the endpoint expansion 1, we have
Kg- (kk (x- (-1+ = K (p- + c - + o(t -1)=) ))
(1-11 + N2ا ( (p (1) - 1,1
+ +
2nt2
+ oll (())))
We thus have
-
(23)
Since k/-1 S 28-3.
(x-1)²
we have
s²
1-2
1,8
2s
-3-3) 3
c-1,8-1.
Now use the end point expansions of ni and Kig- 1 (kt- to obtain the following endpoint expan- sions for N'NT.s'
RiyT, (1 -)) = (1),0(1) (1) + + + o )
A N ( (11 = pm (t) + c 1
2 + ot 2
We have
c2
222
+1,8
2s
q 41,
4.0
1||
+1,
+
2s
9+1,2 6 1,87
11-1,0
n1
and,
c²
411s
11.0
911,5 9+1,s +4118*
1- 11 1.. 1.0
(24)
2s
Since (1) 1, by induction we have (1) = 2 2. In addition, Kg-1 (x)
(1- = 1. v/ 2 3. Therefore 1+ 9+1, = Thus,
1.0 1.0
c² 11-1, 1,0
4+1,
01.0
2s 9-1.
+ 1.
(25)
#2.0 Starting from 4+1. 2--
32
n1.0 + 1, we can derive the following expression for 44i, when s
1,
i-1
11.0
2
1-1
2--1
941,8
2s
-
2252
-1
28-1
1
222
c²
2s
When s = 1, 441. = I, that consistent with the results in Bietti & Bach (2020).
For e'it 1,1.s. we thus have
252
252
n
R-1
11-10 1!
+1,8
28
C
+1.8
41,
C+1,
19

---

Under review as a conference paper at ICLR 2022
11-1,0 Replacing the expressions for 9+1,5 and d1 derived above, we obtain
41. ~ (g)) )-
c²22
(2+1 (1-2)+1
C+1,s-1-
(26)
2s -
For the constant in the expansion around -1, we have
C²8²
11.
28
1 1,0
1100 11-
C
1,87
(27)
where 9-1.0 = ( is bounded between and 1. Thus, starting from c=1. = c-1,8-1, we obtain
d S (<1 c²8² 1-2
-
1-1,8-1
(28)
Comparing di
we can see that for > 2, we have 1c71,ol A 1e"1,01 Thus, the NT kernel with >> 2, applying Lemma 3, we have X; i d-222+2
E.3 THE EIGENDECAYS TERMS OF X;
((td)) Recall the multiplicity Na,; 2 2 (1+d-3) of X; Here take into account this multiplicity give the eigendecay expressions in terms of X;- Using
(*)* I
( k $ (%))* for all k, n. E N. we have, for all i > and > 2.
1-110 pd= Na. (d (d+ 2)e
1 1 jd-2
2(i - 1)--2 2
(i (i-1) 1)==
d
where we used 2 < 2i+d-2
<
4+2 2
We thus have Na.1 ~ (i 1)d-2, 2, for the scaling of Na. with i,
with constants given above.
Recall we define A = Åv, for i and i' which satisfy Σ Na < i S E Na.". Using Na, ~ (i - 1)d=2 we have Eiem Na." rd-1, Thus A; ~ X X a Replacing i with य in the expressions derived for 2 in this section, obtain the eigendecay expressions for X reported in Table 2.
F PROOF OF THEOREM 1
The Matérn kernel can also decomposed in the basis of spherical harmonies. In particular, Borovitskiy et al. (2020) proved the following expression for the Matérn kernel with smoothness parameter y on the hypersphere gd-1 (see, also Dutordoir et al., 2020, Appendix B)
NA. 2v
+ i(i
d 2)) (ut - (1)())))))(')),
R2
where diyy the spherical harmonics.
Theorem implies that the RKHS of Metérn kernel is also constructed as span of spherical har- monics. Thus, in order to show the equivalence of the RKHSs of the neural kemelss with various activation functions and a Matérn kernel with the corresponding smoothness, we show that the ratio between their norms is bounded by absolute constants.
20

---

Under review as a conference paper at ICLR 2022
Let HlyT... with 1 2. As result of Mercer's 's representation theorem, we have
Na.
1()
Waij X (.)
i=1
Na.i
2v x²
+ i(i +iii+ d 2)) ( $1 1))))))))
Wh.t
ili + d 214
Note that
X
= =0(-
+ i(i + dl - 2)) (u+ (1+
j- 222
62
For the NT kernel, from Proposition 1, 2i = =((i--22t+2) Thus, when v 8 2'
O(1.
xa + i(i + d - (d)- -
So, with =-- we have
20 Na.1
A
|/
W 1.
22
i(i + d 2)) (1++
1=1
xc
Na.1
o
>>>>>
=
That proves HyS C Hk..
A similar proof shows that when + 1.2 Ht, He, Now, let f E He.,- As result of Mercer's representation theorem, we have
Na
f(-) =
Wij
2v R²
+ +i(i+ d 2)) (v+ (v+ (., (-)
1=1
Na.
22
+i(1 + d 2)) (
X $))(
Wi.j
For the NT kernel with 1 > 2, from Proposition 1, A1- 1 20+2 Thus, when
2y +
111
+ 2)) (w+ (1+)
0(1)
So, with v = 8 we have
80
Na.
2v
+ i(i d d-2)) 2)) d
(ut -1+ (
||
w f.j
j=1
00 Nu.i
1=1
).
21

---

Under review as a conference paper at ICLR 2022
That proves, for 1 > 2, when v = H&, C. H . A similar proof shows that for / >> 2, when = =st 2 Hk. C Hy, which completes the proof of Theorem 1.
G
PROOF OF THEOREM
Recall the definition of the information gain for kernel K.
I(,;: F) log det
kn
X2
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
Na.
RxxTx)) x:)
Σ
(t)
Na.
(( x)
E
(29)
We present the proof for the NT kernel. similar proof applies to the RF kernel.
The truncated kennel at M eigenvalues, R(x² R(xTx:). x)), corresponds to the projection of the RKHS of onto finite dimensional space with dimension Σ E/=1-
We use the notations K, and K, to denote the kernel matrices corresponding to & and ,, respec- tively.
As proposed in Vakili et al. (2021b), we write
In kn log det (In + 12 (KC, + +km))
log det
= log del
In + x2
1 K..) + log (In+ 1 (I J.k.) 1 K,,
- -
(30)
The analysis in Vakili al. (2021b) crucially relies assumption that the eigenfunctions uniformly bounded. the case of spherical harmonics however (see, e.g., Stein & Weiss, 2016, Corollary 2.9)
sup
(1,(()) = 30.
(31)
N
BEX
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 R(æ, x²) approaches M grows (uniformly in and x'), with certain rate.
Lemma For the NT kernel, we have R(x x') (MM)++11) ) for all x, x' E X.
Proof of Lemma Recall that the eigenspace corresponding to A, has dimension Na.; and consists of spherical harmonics of degree i. Legendre addition theorem (Maleček & Nádeník, 2001) states
Na. Σ
(1)()))1
C.. (cos(((0)) x'))),
(32)
22

---

Under review as a conference paper at ICLR 2022
where d is the geodesic distance on the hypersphere, C: C/d-2)/2 Gegenbauer polynomials (those are the same as Legendre polynomials up to scaling factor), and the constant Ci,d is
((d 2)/2)
Ci 2z(d 27(d-2)/2( 2) (d-2)) (1)
(33)
We thus have
Na.i
k(xx T x¹)
Σ
X
22 (x))))())))
i= M+1
J=1
Σ
.!d (d- 21/2 (dd221/2 (c05((((222 A
M=
NgN T((d-2)/2)
-
(xd(2-2)/2)
i= M+1
2-
i= M+1
M M-2s+1
Here, the inequality follows from c/ (d-21/22 21/2 (cos(d 2'))) I (1)- because the Gegenbauer polynomials attain their maximum at the endpoint 1. For the fourth line we used Na, id The implied constants include the implied constants in Na,i jd- given in Section E.3, and [[[d 21/2)
2n
We also introduce a notation NM Σ M Di= Na,s for the number of eigenvalues corresponding to the spherical harmonics of degree up to M, taking into account their multiplicities, that satisfies Nas ~ d (see Section E.3).
We are now ready to bound the two terms on the right hand side of equation 30. Let us define 4 PR,NN = ( (51), NN (x2).... NN (an)) an n Na matrix which stacks the feature = 1...., n, at the observation points, as its rows. Notice that K, a Na. AN $ N..
vectors ΦN.,. (#x) =
where ANa is the diagonal matrix of the eigenvalues defined as [ANses = Aror.g-
Now, consider the Gram matrix
A $ N. Nn,NN Nar NM As it was shown in Vakili et al. (2021b), by matrix determinant lemma, we have
G
log (I, + X2 K,) = log (I + X² G)
tr([NNr 1
< Ny log
+
G)
NM
x2
NM log(1 +
n
X2NM
To upper bound the second term on the right hand side of equation 30, we use Lemma 4. In particular, since
(((1, (In + Kr
kr) kr,) -'K, s tr((Ka),
tr
and [Kn]
-20M110+1). we have
1 k2, -1k,
=0((1
+ T M 20t1))
1
tr I, + x2
[I, +
1
23

---

Under review as a conference paper at ICLR 2022
Therefore
log det
In + 1t
(In
+
x kn)
kn))
-Rn
< n log (011 + 12 M M
nM-20+1 +0(1),
A
where for the last line we used log(1 + 2) S which holds for all = R.
We thus have (x(()) = O log(n) + n.M t=+1)) Choosing M ~ ~o (log(n)) 2+20-2 we obtain
7 (n) O ( (log(n)) 2i20'2
(34)
For example, with ReLU activation functions, we have
T (n) = O (n - (log(n))*))
H PROOF OF THEOREM
As stated in the paper, the proof follows the same steps in the proof of Theorem 3 of Vakili 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 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, bound the uncertainty estimate (x) in terms of (n). Our novel bounds on (%(()) of neural kernels given in Theorem allow us to derive explicit bounds on (x)) Then, we bound the error [f(x) fn (x)) in terms of o (2r,, using implicit error bounds.
Recall the way that the dataset D, is collected: Vx E X. 1z)1(x) < (x4). Due to positive definiteness of the kernel matrix, conditioning on a larger dataset reduces the uncertainty, Thus Va E X and Vi n, (x(x) oz)x) Therefore o (x) upper bounded by the average of o² over i: Va E X
arg max (zr). This ensures that,
(x)
Σ o (x,). t=1
(35)
It is shown that (e.g., see, Srinivas al., 2010, Lemmas 5.3, 5.4)
2I(Y,; F)
Σ oL
(36)
log(1 + }
Thus, combining equation and equation 36, and by definition of (n)), we have, Vor
(n)) (x(x) mloo(1+ }
(37)
Now, inserting our bounds on Vakt. (n) and Tie (n) of the neural kernels from Theorem 2, we obtain,
Vx E X
(x) <
2
(log(1))
24-1 Tap
2
in the case of NT kernel,
log(1 + x
(x)
(og(n))
2011 22-44
2 in the case of RF kemel.
(38)
log(1 + +
The second component of the proof is summarized in the following lemma.
24

---

Under review as a conference paper at ICLR 2022
Lemma 5 Under Assumption 1, we have, with probability at least - 8, Vx E X
If(z) - fn(x)l < (
(B BB+ Cllog(
nd -
2
on(I))
(39)
VTi
where C' is absolute constant, and B is the upper bound on the RKHS norm of f given in As- sumption 1.
Lemma follows from equation 7, and a probability union bound over discretization of the domain. A detailed proof of this lemma is given at the end of this section.
Inserting the bounds on (z) from equation 38 in Lemma we have, with probability at least 1 - 6, uniformly in æ,
nd-1 (log(
[f(z) fn(x)]
O
2011 n क (log(n) (n)) 2al
2x
1)$
in the case of NT kernel,
n (log(
[f(x) f.(w)
o 2d:
(log(n))
20+1 2d
1)²²
in the of RF kernel.
That completes the proof.
Proof of Lemma 5:
Recall the implicit error bound given in equation 7: For a fixed æ E X, under Assumption we have, with probability at least 1 - 8 (Vakili et al., 2021a),
If(z) - (x)) (())
(40)
where B(8) B
V 2 log( ( Lemma 5 extends this inequality a uniform bound in æ, using probability union bound over discretization of the domain.
For f HA. with I[ Nr I B, and for E N. there exists fine discretization X,, of X with size [x,|| such that f(x) [(x=))) S Vn where [z),. arg min || x||ı2 is the closest point in Xn, to and |x,l S (n 12/2 where is absolute constant independent of and B (Chowdhury & Gopalan, 2017; Vakili et al., 2021a).
Under Assumption 1, it can be shown that: with probability at least 1 5/2 (Vakili al., 2021a, Lemma 4)
Rva X
4n
1l, SB+
2
log
(41)
5
U(6)
Note that f. is random function, where the randomness comes from the randomness observation noise.
We thus conclude that there discretization Xn with size | S c(U(6))d-1n(d-1))) such that [f(x) f(())x) x / and with probability at least 1 - 8/2,
[fx(x) - (1)()))))
1
(42)
Vn
Let 8' = ( A probability union bound over the discretization X, implies that: With probability at least 1 - 8/2, uniformly in x E X..
If(x) fa(()) < ((0')a
(43)
Accounting for the discretization error from equation 42, and a probability union bound over equa- tion 41 and equation 43, have, with probability at least uniformly in X,
25

---

Under review as a conference paper at ICLR 2022
( v (f(x) -((+)]+++++ - + - - (x)) I [f((a)) - fa((xn)) + vn
2 Vn
S ((0))o())) +
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+ Ryn A
2lgg 2n in 8' and the value of 8 (c( nn 1772
in 3()) B + V 2 log( we arrive at the lemma.
I DETAILS ON THE EXPERIMENTS
In this section, we provide further details 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 KNT,, (.), with 2 layer neural networks with activation functions ax(-). In the first step, we create a synthetic function f belonging erate no 100 points on the hypersphere gd-1, Let Xno
2,2,3, which correspond to wide fully connected
the RKHS of NT kernel K. For this purpose, randomly gen-
[ denote the vector of these points. We also randomly sample Yn,, = [ from a multivariate Gaussian distribution (O Kn where [Kny = x(a] 2y). We define function g(.) kT, (-) -
where 8² 0.01 and [K (z)], <(x 2z). We then normalize g with its range to obtain f()) maxsex gf.) applications of the kernel. Thus g is in the RKHS of H, and its RKHS norm can be bounded as follows.
g(ø)" For fixed Xno and Yno. is linear combination of partial
11g11 =
KT TTT, (-)(nn + +TIIno) KT, (R) + I -1
Koo
Hhe
T (Kno + + -'K
"nn (Rno + 822 -18 ynno
no
28 = T (Kno + + 1 no (K 82I -280
T-T (Kno -82I -18
no
| l|?
82
The second line follows from the reproducing property. We thus can see that for each fixed Xn, and Yngo 9 (and consequently f) belong to the RKHS of k.
The values of max g(z) and mingex g(z) 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 D, of the sizes 2', with i 1,2..... 13, by sam- pling n points X, = [ on the hypersphere, uniformly at random. The values Y, = | are generated according to f. We then train the neural network model to obtain f.(.). The error max (x) - f.,( (a:) then numerically approximated by sampling 10, 000 random points the hypersphere and choosing the maximum 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 KNTT.. s = 1, 3 on Sd-1 d = 2, 3, In addition, each one of these 9 experiments is repeated 20 times (180 experiments in total).
26

---

Under review as a conference paper at ICLR 2022
In Figure 2 we plot maxzex If(x) fz(2 versus averaged 20 repetitions, for each one of the experiments. Note that for max If(x) f()) ~ n², we have log(maXeex' If(x) [x())) = log(n) + constant. Thus, in our log scale plots, the slope of 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 is larger or 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 (-) corresponding to the ReLU activation function. We thus made an amendment by directly feeding the expressions of the RF kernels, Ka. 2,3, to the stax. Elementwise layer provided in the library. Below we give these expressions
(2(u) = 3π
(fn cos + (π - 0) + co0s
ka(u) =
15sin(0) - 11 sin + (गr
+ 6 coss (0))
15x
where 0 = arccos(u).
We derived these expressions using Lemma in recursive way starting from K3 (-). Also, see Cho & Saul (2009), which provides a similar expression for k2(-) and a general method to obtain k.(.) for other values of s. We note that only need to supply (.).) to the neural-tangente library. The NT kernel (-) will then be automatically created.
Our experiments run on single GPU machine (GeForce RTX 2080 Tî) with 11 GB of VRAM memory. Each one of the 180 experiments described above takes approximately 4 minutes to run.
27


Reviews:
[{"review_id": "w_pJA2AHBp8", "reviewer": "Reviewer_Enyd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and the results make non-trivial extensions over the state-of-the-art. That being said, it is worth pointing out that the work is mostly of purely mathematical interest (which is fine): the case of ReLU activation functions was already treated in earlier work. Nevertheless, the extra difficulty involved in the case here is what motivates the use of Stein's Lemma, which makes the paper (moderately) interesting from the technical point of view. The exposition of the concepts is very good in general, though some references and some (minor) aspects appear to be missing.  Overall, I am happy to recommend acceptance. \n\nBelow are some more specific comments. \n\n\n// =======after rebuttal======\nAfter reading the other reviews and thee rebuttal, I would incline to slightly lower my score to (6).\n\nI notice that reviewer gYma and I both complained about the general context of \"uniform generalization bounds\". Contrary to reviewer gYma, I don't think the restrictions imposed make the paper unworthy of publication in itself. However, I believe the authors should try harder to explain the enormous difference between the setting they study and classic \"generalization bounds\". The rebuttal is slightly dismissive in that respect.\n\nMore importantly, the issue pointed out by reviewer gYma about Theorem 3 is quite serious. The proof the authors added is not that short, which indicates the paper was somewhat rushed in terms of making the deadline.\n\nI still stand with the authors in terms of originality, but with low confidence.\n\nIn conclusion, this remains a valuable paper from the purely mathematical point of view (with limited practical applicability, though that is not of great importance), but some parts are a bit rushed and the placement of the paper within the broader literature and other pedagogical aspects are somewhat neglected. I think it is still above the borderline but not by as far as I originally thought.\n\n\n/\n======================\nGeneral comments/questions about the content\n======================\n\n1. On page 6, when it is claimed that the relevant kernels are equivalent to a Matérn family of kernels, it would be nice to point the reader to the definition of the \"equivalence\" between kernels (which is at the beginning of the supplementary), since otherwise it sounds a bit like the two learning problems are completely equivalent (which is not the case). \n\n\n2. The part of the related works which deals with \"Classical approaches\" (in the introduction and in the rather bizarre Section C) is not very complete. It is really not fair for the present paper to present itself as one of the only ones that exploited the NTK regime for generalization purposes! At the absolute least it is imperative to cite [4]. In a more general discussion of pre-NTK work it would be natural to cite [3] as well, though it is less required,  \n\n3. On a related note, it should be made much clearer in the \"generalization bounds\" part of the paper that the rate is worse than existing rates because of the lack of an i.i.d. assumption: a rate of $1/\\sqrt{n}$ is pretty much known under such assumptions. \n\n4. In page 15, I really appreciate the fact that the exact result from [1] was written again here. To make things even better, it would be nice to explain that one can construct a rotationally invariant kernel $k$ from $\\kappa$ via $k(x,y)=\\kappa(y^\\top x)$, rather than simply saying \"let $\\kappa:[-1,1]\\rightarrow \\mathbb{R}$ be a rotationally invariant kernel. I know these concepts are explained in the main paper but it doesn't hurt to help the reader a bit. \n\n\n5. The RL connection is slightly oversold. \n\n\n6. It is rather strange that you are not citing any paper when using Stein's lemma. There is a whole branch of literature that uses Stein's lemma in many different areas of statistics and probability. Relevant references are [5,6,7] to name but a few. \n\n\n\n\n\n\n/\n===================\n(Very) Minor Comments/typos (non exhaustive)\n===================\n\n\n\n1.  Around the middle of page 2: \"That we show to imply...\" =====> \"Then we show this implies...\"\n\n2. Bottom of page 4: \"...share the same eigenvalue $\\tilde{\\lambda}$, is $N$...\" ====> \"...share the same eigenvalue $\\tilde{\\lambda}$, i.e. $N$...\"\n\n3. Middle of page 5: \"They derived those expansions for the case of ReLU activarion function.\" ===> \"They derived those expansions for the case of the ReLU activarion function.\"\n\n4. Beginning of Section 3.2 on page 6: \"Our bounds...shows\" ====> \"Our bounds...show\"\n\n\n5. Bottom of page 6: it would be nice to say (at least once) that \"GP\" stands for \"Gaussian Process\".\n\n6. Beginning of section 5.2 on page 8: \"provide explicit bounds on error\" ====>\"provide explicit bounds on the error\"\n\n7. Discussion (around the middle) on page 9: \"...the corresponding eigenvalues. our...\" ====>  \"...the corresponding eigenvalues. Our...\"\n\n8. Beginning of Section B in the supplementary (page 13): \"we overview the Mercer's Theorem\" ====>\"we give an overview of Mercer's Theorem\"\n\n9. Below the main equations in Section D (proof of Lemma 1): \"applying the Stein's Lemma\"===> \"applying Stein's Lemma\" \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n/\n==================\nReferences\n==================\n\n[1] Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. ICLR 2021. \n\n[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. \n\n[3] Peter L. Bartlett, Dylan J. Foster, Matus J. Telgarsky. Spectrally-normalized margin bounds for neural networks. NeurIPS 2017. \n\n[4] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang.  Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. ICML 2019. \n\n[5] Charles Stein. Approximate computation of expectations. Institute of Mathematical Statistics Lecture Notes, Monograph Series, 7. 1986.\n\n[6] Louis H.Y. Chen, Larry Goldstein, Qi-Man Shao. Normal Approximation by Stein’s Method. Probability and Its Applications. 2011.\n\n[7] Ivan Nourdin & Giovanni Peccati. Stein’s method on Wiener chaos. Probability Theory and Related Fields. 2009. \n\n\n\n\n", "summary_of_the_paper": "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. \n\n\n\n\n/\n==================\nReferences\n==================\n\n[1] Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. ICLR 2021. \n\n[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. \n\n\n", "summary_of_the_review": "This is a well-written paper with a non trivial advance over the state of the art and a reasonably large number of computations, with one semi-novel technique involved. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "qMBn61-HRFv", "reviewer": "Reviewer_KpGF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "By now, there is an established line of research that tries to understand the performance of NTK regression by understanding its associated RKHS and the decay of eigenvalues. The current papers expands on this direction in an elegant way by capturing the interplay between smoothness of activations and smoothness of learnable functions.\n\nHowever, I do feel that the scope of the paper is somewhat limited. Perhaps it's not even fair to say that the paper deals with generalization bounds of overparametrized neural networks, since the main focus is on their infitely wide limit. \nAs the genralization bounds themselves follow from previous work, the main contribution is the equivalence between the RKHS of the Matern kernels and those of NTKs associated to the powers of ReLU. The latter activations is not very common and so the applications are restricted.\n\nSome comments:\n- The test set $\\mathcal{X}$ is never fully identified. Persumably it's the sphere, but this is never mentioned explicitly in Theorems 2 and 3, which makes it hard to appreciate the result.\n\n- The definition of the Maximal Information Gain is confusing. In Section 4 it would be a good idea to say exactly which Gaussian process is being considered and which vector Y is considered, even though their identity can be infered from the previous context. Spefically it is not clear how the parameter $\\lambda$, which can be arbitrary, can be part of this definition. Perhaps it would be better to simply define it by the formula that appears at the top of page 7. This is the form which is needed at the end.", "summary_of_the_paper": "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. \n\nPrevious 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.\n\nUsing the above results the authors establish uniform bounds on the generalization error when learning a function from the appropriate RKHS with kernel regression.\n\n", "summary_of_the_review": "The paper makes important contributions to the study of RKHS associated to the NTK. The main drawback, in my eyes, is that the scope of the paper is limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "c5mO3pLX0Pk", "reviewer": "Reviewer_V82Y", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presented uniform generalization bound for kernel ridge regression in the reproducing kernel Hilbert spaces (RKHSs) generated by neural tangent kernels and the maximum information gain (MIG) approach are of interest. The first theorem is about the equivalence of the RKHSs of the neural tangent and Matern kernels over the hyperspherical domain. To bound the generalization error, the authors provide a bound on the MIG of neural tangent kernels and random feature kernels in Theorem 2. Then convergence rates for the generalization error are presented by considering a special data collection module. Overall, the paper is well-written and technically sound. I vote for acceptance. I have some concerns as follows:\n\n1. The assumption that the approximation error is zero is kind of strong.\n\n2. The benefit of using ReLU with $s>1$ is not so clear to me. Is it possible to consider other more general activation functions and derive similar MIG bounds?\n\n3. In Section 6, why choose $\\hat{Y}\\subset\\mathbb{R}^d$? Is $d$ the dimension of the input space? It is also a little bit strange that you let $f$ depend on $\\hat{k}_{n_0}$, i.e., $s$, when you are trying to compare the error exponent over $s$.\n\n4. Are the rates derived in Theorem 3 minimax optimal?", "summary_of_the_paper": "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. ", "summary_of_the_review": "The approach based on maximum information gain is very interesting. The uniform generalization bound for overparameterized neural networks given in this paper is neat.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NtdUAoWaAnz", "reviewer": "Reviewer_kUxi", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Theorem 1 is a trivial corollary of Lemma 1 and Proposition 1. Lemma 1 is nice though it is an easy consequence of a recursive relation (4) given by Jacot et al. Proposition 1 follows directly from a nice asymptotic expression of eigenvalues of the integral operator associated with a Mercer kernel on [-1, 1] which is C^\\infty on (-1, 1) but has  singularities of the same order at -1 and 1. \n\nTheorem 2 can be easily obtained from the bound O(d_k(n) log(n)) for the maximal information gain in terms of the effective dimension d_k(n): the effective dimension d_k(n) can be easily bounded from its definition by the decay of the eigenvalues. \n\nTheorem 3 is stated for the data tilde{D}_n = (x_i)_{i=1}^n defined in terms of the functions (sigma_i)_{i=1}^n. Since each function sigma_i is defined in terms of the original data (x_j)_{j=1}^i, the independence of the new data is not known, at least to this reviewer. Note that the function trained with the new data in Theorem 3 is different from that in (7). The proof of Theorem 3 is not trivial at all and is not included in the appendix. This reviewer believes that Theorem 3 is wrong. \n\nIn summary, Lemma 1 is a nice observation. Theorems 1 and 2 are trivial. Theorem 3 is not proved and should not be claimed as a theorem. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "Though Lemma 1 is a nice observation, Theorems 1 and 2 are trivial. Theorem 3 is not proved and should be wrong, to this reviewer's opinion. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1B3hBrw0J8S", "reviewer": "Reviewer_gYma", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strength:\n\nThis is a very well-written and coherent paper.\n\n## Weaknesses: \n\n**Theorem 3**: The authors assume $D_n = \\set{x_i,y_i}, i < n$   is constructed using a special non-i.i.d sampling procedure often referred to as Uncertainty Sampling [1] within the field of Active Learning.  Adopting the Bayesian prior assumption  $f \\sim GP(0,NTK) , x_i = \\underset{{x \\in X}}{argmax} \\\\  \\sigma_{i-1}(x) $ are picked by maximizing the posterior variance of $f$. \n\nA number of comments regarding the relevance and novelty of Theorem 3 follows.\n\n1. A proof of this theorem is not given in the main text or the appendix, hence I am not able to verify the correctness of the statement. \n\n2. The assumption on the dataset does not apply to any supervised learning task with i.i.d data. \n\n3. Without any assumptions on the dataset, Theorem 3.2 of [2] proves a similar statement. They show that for a fixed x, $| f_{ntk}(x)- \\hat f(x) | < Poly(n, log(1/\\delta))$ with probability greater than $1- \\delta$. Here, $f_{ntk}$ is the kernel regression predictor, using the NTK, on the same dataset, and $\\hat f(x)$ is an MLP trained using gradient descent on dataset $D_n$. Using a basic least squares error bound for kernel regression, e.g. Theorem 13.5 [3], and the triangle inequality, one can produce a bound similar to Theorem 3 of this paper, which holds for any fixed dataset, without further restrictive assumptions on how the data needs to be acquired. My point here is that, to me this bound deems incremental taking into account the restrictive problem setting, and considering the existence of powerful results such as Theorem 3.2 [2], or Section 5 of [4]. \n\n4. This theorem may be useful as a lemma within the literature of Bandit Optimization and Active Learning, however Lemma 4.2 [6] and Lemma 5.2 [5] establish very similar results under less restrictive assumptions on the dataset. These papers have no assumption over how $x_i$ are collected and only assume that $y_i$ are independent, conditioned on $x_i$.\n\n5. Lastly, I find the title uniform generalization bound to be somewhat deceiving, as Theorem 3 holds with high probability for a fixed $f \\in \\mathcal{H}_k$, and not uniformly for all members of this RKHS. A uniform bound (e.g. Glivenko Cantelli-type theorems) is often referred to as a bound that holds simultaneously for all functions in the hypothesis class. I can not see how this bound can be extended to hold uniformly over $\\mathcal{H}_k$.\n\n\n**Experiments**: The code for the experiments was not given by the authors, so I can't verify the correctness of the experiments. Also, theorem 3 assumes the dataset is collected using a non-i.i.d sampling procedure often referred to as uncertainty sampling. However, in the experiments the authors collect the data randomly which breaks their assumption. This inconsistency is not explained in the paper. \n\n**Other contributions**: As stated by the paper, the presented results for Theorem 1 already exist for $s = 1$ in [7], and this paper contribution is to generalize it for $s > 1$. The techniques used for generalizing to $s > 1$ are not novel, and it is the same used as in [7] and [8]. Although these results could have an interesting theoretical value, it is not practical since DNNs do not use activation function  for $s > 1$  as correctly stated by the authors in the Remark 2. \n\n**Literature review**: Theorem 2 of this paper is an extension of Theorem 3.1 of [6] which bounds the MIG for $s=1$ to the $s >1$ case, however there is no reference to [6]. Moreover, Lemma 4.2 of [6] presents a similar generalization bound for MLPs for a general i.i.d dataset in the case of $s=1$, yet despite the similarity it is not mentioned.\n\n \n\n ", "summary_of_the_paper": "In this paper, the authors provide a more generalized equivalence of the NT and NNGP (referred as RF in this paper) kernels of MLPs and Matern kernels for activation functions of form $max(0,x)^s$ by analysing the eigen decay of the kernels corresponding Gram matrices. Later they use this eigen decay to bound the maximal information gain (MIG) of the kernels and finally present a generalization bound with respect to the number of the samples. ", "summary_of_the_review": "I think the contributions of this paper are incremental, and is limited to using already known techniques to generalize results in [7] and [6] for $s > 1$. Another contribution is to derive the bounds in Theorem 1, 2 and 3 for RF kernels in addition to NT kernels. However the results for RF kernels are implicit in the other works.\n\n## References \n\n[1] David D Lewis and Jason Catlett.  Heterogeneous uncertainty sampling for supervised learning.  In Machine learning proceedings 1994, pp. 148–156. Elsevier, 1994.\n\n[2] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang.  On exact computation with an infinitely wide neural net. arXiv preprint arXiv:1904.11955, 2019.\n\n[3] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint , volume 48.  Cambridge University Press, 2019.\n\n[4] Arthur Jacot, Franck Gabriel, and Clement Hongler.  Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv:1806.07572, 2018.\n\n[5] Dongruo  Zhou,  Lihong  Li,  and  Quanquan  Gu.   Neural  contextual  bandits  with  UCB-based  exploration.    In  Hal  Daume  III  and  Aarti  Singh  (eds.),Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research,pp. 11492–11502. PMLR, 13–18 Jul 2020.\n\n[6] Kassraie, Parnian, and Andreas Krause. \"Neural Contextual Bandits without Regret.\" arXiv preprint arXiv:2107.03144 (2021).\n\n[7] Geifman, Amnon, et al. \"On the similarity between the laplace and neural tangent kernels.\" arXiv preprint arXiv:2007.01580 (2020).\n\n[8] Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. arXiv preprint arXiv:2009.14397, 2020.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a uniform generalization bound for overparameterized neural networks using the notion of maximal information gain. The analysis relies on the eigendecay of the eigenvalues of the NTK, which has recently been the object of a lot of work in the literature, including the work of Bietti and Bach (the proof actually uses one of their key lemma).

The paper originally received a set of reviews with a large disagreement between the reviewers (including two reviewers with a negative opinion and three reviewers being more positive). After the discussion period, two reviewers kept a very negative opinion, while other reviewers slightly lowered their score. Some of the problems raised by the reviewers include the restrictions imposed on the data, a missing proof (which was eventually added by the authors), the discussion of prior work being inadequate (including for instance the differences with more classical generalization bounds), and the novelty of the analysis.

Overall, the paper clearly has some merits but some of the concerns above are too important at this stage to accept the paper. I recommend the authors address the concerns mentioned in the reviews before re-submission.
Decision: Reject