Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS
Authors: Lin Chen
Sheng Xu
Venue: ICLR 2021 Poster (2021)
Keywords: Neural tangent kernel
Reproducing kernel Hilbert space
Laplace kernel
Singularity analysis

Abstract: We prove that the reproducing kernel Hilbert spaces (RKHS) of a deep neural tangent kernel and the Laplace kernel include the same set of functions, when both kernels are restricted to the sphere $\mathbb{S}^{d-1}$. Additionally, we prove that the exponential power kernel with a smaller power (making the kernel less smooth) leads to a larger RKHS, when it is restricted to the sphere $\mathbb{S}^{d-1}$ and when it is defined on the entire $\mathbb{R}^d$.

Published as a conference paper at ICLR 2021
DEEP NEURAL TANGENT KERNEL AND LAPLACE KERNEL HAVE THE SAME RKHS
Lin Chen
Sheng Xu
Simons Institute for the Theory of Computing University of California, Berkeley lin.chen @ berkeley.edu
Department of Statistics and Data Science
Yale University
theng.xu@yale.edd
A ABSTRACT
We prove that the reproducing kernel Hilbert spaces (RKHS) of deep neural tangent kernel and the Laplace kernel include the same set of functions, when both kernels restricted to the sphere S Additionally, exponential power kernel with a smaller power (making the kernel less smooth) leads to a larger RKHS, when it is restricted to the sphere gd-1 and when it is defined on the entire Rd
prove that the
INTRODUCTION
In the past few years, one of the most seminal discoveries in the theory of neural networks is the neural tangent kernel (NTK) (Jacot et al. 2018). The gradient flow on normally initialized, fully connected neural network with linear output layer in the iiftnite-width limit turns out to be equiv- alent to kernel regression with respect to the NTK (This statement does not necessarily hold for non-linear output layer, because the NTK is non-constant (Liu et al., (0200). Through the NTK, theoretical tools from kernel methods were introduced to the study of deep overparametrized neural networks. Theoretical results were thereby established regarding the convergence (Allen-Zhu al., 2019
Du et al. 2019b a Zou et al. 2020), generalization (Cao & Gu 2019 Arora et al. 2019b). and loss landscape Kuditipudi al. 2019)) of overparametrized neural networks in the NTK regime.
While NTK has proved to be a powerful theoretical tool, a recent work (Geifman et al. 2020) posed an important question whether the NTK is significantly different from our repertoire of standard kernels. Prior work provided empirical evidence that supports negative answer. For example, Belkin et al. (2018) showed experimentally that the Laplace kernel and neural networks had similar performance in fitting random labels. In the task of speech enhancement, exponential power kernels K3p (z, y) e -1==~=il'' / /or which include the Laplace kernel as special case, outperform deep neural networks with even shorter training time (Hui al. 2019). The experiments in (Geifman et al. 2020 also exhibited similar performance of the Laplace kernel and the NTK.
The expressive power of a positive definite kernel can be characterized by its associated reproducing kernel Hilbert space (RKHS) (Saitoh & Sawano 2016). The work (Geifman et al. 2020) considered
the RKHS of the kernels restricted to the sphere ga-1 A {o E 12 | 12 = 1} and presented
partial answer to the question by showing the following subset inclusion relation
HGasss (gd-1) C HL = H.N, (8d-1) S HN, (8d-1),
where the four spaces denote the RKHS associated with the Gaussian kernel, Laplace kernel, the NTK of two-layer and (A- + 1)llayer (k 2 1) fully connected neural networks, respectively. All four kernels are restricted to Sd-1 However, the relation between Hiap (Sd-1) and HN, (Sd-1) remains open in (Geifman et al. 2020).
We make a final conclusion this problem and show that the RKHS of the Laplace kernel and the NTK with any number of layers have the same set of functions, when they are both restricted to gd-1 In other words, we prove the following theorem.
Theorem 1. Let Hl.p ( and HN, (gd-1) be the RKHS associated with the Laplace kernel K1ap (x. y) -ellz-yl (c 0) and the neural tangent kernel of a (k + 1)-layer fully connected

---

Published as a conference paper at ICLR 2021
ReLU network. Both kernels restricted to the sphere gd- set of functions:
Then the two spaces include the same
HLap(S" HN, (S (8 )
14 21
Our second result is that the exponential power kernel with a smaller power (making the kernel less smooth) leads to a larger RKHS, both when it is restricted to the sphere gd-1 and when it is defined on the entire Rd
Theorem 2. Let HKz (S4-1) and H Has (IRd) be the RKHS associated with the exponential power (7,0 > 0) when it is restricted to the unit sphere 3d-1 and
kernel Kesp (x, v) exp -ا=ي)l")
defined on the entire RR, respectively. Then we have the following RKHS inclusions:
(1) If0 < n < 72 2,
H Rz
(S
S H Hggp.01 (St-1).
(2) 1f0 < m < <12 < 2 are rational,
H K2gg.2 (R:1) S. H Hazp (R.).
If it is restricted to the unit sphere, the RKHS of the exponential power kernel with 7 < is even larger than that of NTK. This result partially explains the observation in (Hui et al.] 2019) that the best performance is attained by a highly non-smooth exponential power kernel with y < I. Geifman jet al. (2020) applied the exponential power kernel and the NTK to classification and regression tasks on the UCI dataset and other large scale datasets. Their experiment results also showed that the exponential power kernel slightly outperforms the NTK.
1.1
FURTHER RELATED WORK
Minh et al. (0066 showed the complete spectrum of the polynomial and Gaussian kernels on Sd-1 They also gave a recursive relation for the eigenvalues of the polynomial kernel on the hypercube 1- Prior to the NTK (Jacot et al. 2018), (i18),CChr Cho & Saul (2009) presented pioneering study on kernel methods for neural networks. Bach (2017) studied the eigenvalues of positively homogencous activation functions of the form o. ()) max u, 0} (e.g.. the ReLU activation when
1) in their Mercer decomposition with Gegenbauer polynomials. Using the results in (Bach) 2017). ). Bietti & Mairal (2019) analyzed the two-layer NTK and its RKHS in order investigate the inductive bias in the NTK regime. They studied the Mercer decomposition of two-layer NTK with ReLU activation on gd-1 and characterized the corresponding RKHS by showing the asymptotic decay rate of the eigenvalues in the Mercer decomposition with Gegenbauer polynomials. In their derivation of a more concise expression of the ReLU NTK, they used the calculation of (Cho Saul 2009) on arc-cosine kernels of degree 0 and 1. Cao et al. (209)) improved the eigenvalue bound for the k-th eigenvalue derived in (Bietti Mairal (219)) when d k. Geifman al. (2020) used the results in (Bietti & Mairal 2019) and considered the two-layer ReLU NTK with bias 3 initialized with zero, rather than initialized with a normal distribution (Jacot et al. 2018). However, neither (Bietti & Mairal 2019) nor (Geifman et al. 2020) went beyond two layers when they tried to characterize the RKHS of the ReLU NTK. This line of work (Bach, 2017 Bietti & Mairal 2019 Geifman et al.) 2020) is closely related to the Mercer decomposition with spherical harmonics. Interested readers are referred to (Atkinson & Han 2012) for spherical harmonics on the unit sphere. The concurent work (Bietti & Bach 1 analyzed the eigenvalues of the ReLU NTK.
Arora et al. (019a) presented a dynamic programming algorithm that computes convolutional NTK with ReLU activation. (Yang& & Salman (2019) analyzed the spectra of the conjugate kernel (CK) and NTK on the boolean cube, Faan & Wang 2020) studied the spectrum of the gram matrix of training samples under the CK and NTK and showed that their eigenvalue distributions converge to a deterministic limit. The limit depends on the eigenvalue distribution of the training samples.
2 PRELIMINARIES
Let C denote the set of all complex numbers and write i _ V For E C, write Rz, 3z, arg (-T, ग, x] for its real part, imaginary part, and argument, respectively. Let Hi+ & (= C S 0)
2

---

Published as a conference paper at ICLR 2021
denote the upper half half-plane and H _ C 32 < 0) denote the lower half-plane Write (r) for the open ball {w E 22 - w < r) and (r) for the closed ball {w E C C - w S r}.
Suppose that f(z) has power series representation f(z) Envo an around O. Denote [=*][(=) _ an to be the coefficient of the n-th order term.
For two sequences {an) and (bn), write an bn if lim, occ bn
1. Similarly, for two functions
f()) and g(2), write f(z) g(2) as = 20 if lim=->20 notation to characterize asymptoties.
f(=) ((x)
We also big-O and little-o
Write {){())(s) & T0" f(t)e dt for the Laplace transform of a function f(t). The inverse Laplace transform of Fs)) denoted by ---1 (-1((((s){(t))
2.1 POSITIVE DEFINITE KERNELS
For any positive definite kernel function K(x,, y) defined for x. y E E, denote HK (E) F) its associated reproducing kernel Hilbert space (RKHS). For any two positive definite kernel functions K₁ and K2. we write K < K₂ if K2 K2 is a positive definite kernel. For a complete review of results on kernels and RKHS, please see (Saitoh & Sawano 2016).
We will study positive definite zonal kernels on the sphere gd-1 = {or E Rdd ||||| = 1}. For zonal kernel (xx, y). there exists real function K [-1, - R such that K K(x, y) = K (u), where = x: _ y. We abuse the notation and use K (()) to denote (u), i.., K(u) here is real function on [].
In the sequel, we introduce two instances of the positive definite kernel that this paper will investi- gate.
Laplace Kernel The Laplace kernel Kiap(a (r, = elll--vl with >> 0 restricted to the sphere gd-1 1 is given by Kiap(ar y) = e 2(1
- v) = -vVI- Kiap(u). where by our convention
x and ē é /2c >
O. We denote its associated RKHS by Hlap.
Exponential Power Kernel
The exponential power kernel (Hui et al. 2019) with >> 0 and o >> 0
given by Kaip (x, v) = exp
-===- æ and y are restricted to the sphere Sd-1, we have
Keg (x, v) = exp (- (2(1 (2(1-x=1))/22)
Neural Tangent Kernel Given the input x TRd (we define do - d) and parameter this paper considers the following network model with (k: + 1) layers
fo(x)
2 dx-1
2 dg 2
(Wix (bb) +Bb2) ...) + Bob + Bbbt1
w V dp
W
Way
di
(1)
where the parameter 0 encodes W₁ E Bdiid-1,, by E RR (1 1,..., k). w E Rdde and b E R. The weight matrices WI...., Wk. w are initialized with (0, 1) and the biases by.... by41 are initialized with zero, where (0,0, I) is the multivariate standard normal distribution. The activation function is chosen to be the ReLU function (Ix) A max(x, 0}.
Geifman et al. (2020) and Bietti & Mairal (2019) presented the following recursive relations of the NTK Na y) of the above ReL.U network
3

---

Published as a conference paper at ICLR 2021
Ex (I, y!
Ex(o,y) Ex 1)
1 (I, , I 2)2 13
(2)
Ex 1 (2i, y)
Na(2,y) Ex y) + MM-1(z,)) y)00
+ 82
Ek-1 1 (Ir, 2 ) (1/
where Ko and Ki are the arc-cosine kernels of degree 0 and (Cho & Saul 2009 given by
1 (- ar)cos(u)). ki(u)= (x arccos(u)) + v u²
(o(u)
The initial conditions are
y) B Eo(E, v) = u,
(3)
where u = =xy y by our convention.
The NTKs defined in (Bietti & MMairl 2019 and (Geffman al. 2020) are slightly different. There is no bias term 3 in (Bietti & Mairal 2019), while the bias term appears in (Geifman et al. 2020
We adopt the more general setup with the bias term.
Lemma (Proof Appendix A.I). [x 1 for any Sd-1 and k 2
Lemma simplifies and gives
(x( Ki (8) (u). Nu(u) K (u) + NN-1(4))o( (k-1)) (w)) + 32,
(4)
where (8) (1) - KI(Kl (K) (m)) is the k-th iterate of x (u). For example, K3 (0) (u) u.
(1) (u) = ku) and (2) (u) = Ki (mi(1)) We present a detailed derivation of (4) in Appendix A.2 K1
3 RESULTS ON NEURAL TANGENT KERNEL
In this section, we present overview of our proof for Theorem Since (Geifman et al. 2020 showed HLap S HN, (Sd-1), it suffices to prove the reverse inclusion HN, (S+ Hlap (dd-1). We then relate positive definite kernels with their RKHS according to the following lemma
354) and (Saitoh & Sawano 2016, Theorem 2.17)). Let K1, K2 Q Ω C be two positive definite kernels. Then the Hilbert space HK, is a subset of HKg if and only if there exists some constant y 0 such that
Lemma 4 (Arroszzajn) 1950
K1 7K2.
Lemma 4 limplies that in order to show H., (Sd-1) S HLap it suffices to show ?2 N₂ positive definite kernel for some 7 > Note that both KLap and N₂ are positive definite kernels on the unit sphere. Then the Maclaurin series of (u) and Ng(u)) have all negatvvee coefficients by the classical approximation theory; see (Schoenberg 1942, Theorem 2), Bingham (1973). and (Cheney & Light, 2009 Chapter 17). Conversely, if the Maclaurin series of K ((u) have all neg-niet coefficients, K K(x,y) = (<x y) is positive definite kernel on the unit sphere. To
be precise, we have the following lemma.
Lemma 5 (Schoenberg
(1942) Bingham 1973)). Suppose that K(x,v) f(x y) where y E Then K a positive definite kernel on 8d-1 for every d if
Sd-1 and is continuous on and only if f(u) Ex u in which aş 2 0 and Ex=o Ok
Thus, turn show that there exists y such that 22(2 KLap 1z Nx)) holds for every
n > 0.
'henn and y live on the unit sphere (i.e., xz y yT 1), their inner product x TTy can be any real number in (-1, 1].

---

Published as a conference paper at ICLR 2021
Exact calculation of the asymptotic rate of the Maclaurin coefficients is intractable for N₁ due to its recursive definition. Instead, we apply singularity analysis tools in analytic combinatorics. We refer the readers (Flajolet & Sedgewick 2009) for a systematic introduction. We treat all (zonal) kernels, Kiap(u) (u), (u), Kio(u), and Ki (u). as complex functions of variable u E C. To emphasize, C instead of denote the variable. The theory of analytic combinatorics states that the asymptotic of the coefficients of the Maclaurin series is determined by the local nature of the complex function at its dominant singularities (i.e., the singularities closest to z = 0).
To apply the methodology from (Flajolet & Sedgewick, 2009), we introduce some additional defi- nitions. For R. 1 and Φ E (0, x/2). the A-domain [ R) is defined by
( R) _
{2 E C 12 R, * 1, arg(2 1)1 > 6}
For complex number < 0, A-domain at ( is the image by the mapping - Ç= of ((b, R) for some and Φ (0, A function is A-analytic Ç if analytic on a A-domain at Ç.
Suppose the function f()) has only one dominant singularity and without loss of generality assume that it lies at 2 We then have the following lemma.
Lemma (Fajjolet & Sedgewick
2009 Corollary VI.1)). If f is A-analytic at its dominant singu-
larity 1 and
f(z) ~ (1-2)
as - 1,
with a & 10,-1,-22 22.... J. we have
[=)]{(z)~ ~ na-1
T(a)
If the function has multiple dominant singularities, the influence of each singularity is added up (See (Flajolet Sedgewick, 2009 Theorem VI.5) for more details). Careful singularity analysis then gives
LL)(2)) Cin 3/2 -3/2
[²"]N((z) S Cen 3/2
for some positive constants C1, C2 O. We refer Section 3.2 and Appendix/A.41 f.r more detailed steps. They are indeed of the same order of decay rate 3/2 which implies that such y exists. This shows H.. (Sd-1) S Hiap(Sdd1)
3.1 A-ANALYTICITY OF NEURAL TANGENT KERNELS
We present the A-analyticity the NTKs here. light of (4). the NTKs N₁ are compositions of arc-cosine kernels Kn and K1. We analytically extend Kg and kjj to complex function of complex variable E C. Both complex functions arccos(2) and v1 - z2 have branch points +1. Therefore, the branch cut (2) and (2(2) is (c) U (-o0- -1]. They have a single-valued analytic branch
D=C (-00,
(5)
On this branch, we have
ko(2)= π + ilog(2 111 22) -2)
1 π
z ( ilog(z +iv1-1111 V
where we use the principal value of the logarithm and square root. We then show the dominant singularities of ki (2) are +1 and that (x) (2) is A-analytic at +1 for any ls 2 We further have the following theorem on the A A-singularity for N₁-
Theorem 7 (Proof in Appendix A.3). For each k 2 1, the dominant singularities of N₂ +1. There exists R& > 1 such that N₂ is analytic on f E C |2| & R,) n D, where = [1, oc)
(-00,-1)
5

---

Published as a conference paper at ICLR 2021
3.2 ASYMPTOTIC RATES OF MACLAURIN COEFFICIENTS FOR N&
The following theorem demonstrates the asymptotic rates of Maclaurin coefficients for Ng.
Theorem 8 (Proof Appendix A.4). The n-th order coefficient of the Maclaurin series of the
(k 1y-layer NTK in (2 satisfies Nx(2) O( 3322).
In the proof of Theorem
8 show the following asymptotics
Nx(2) = (le 1) (9) (22(1 + 8z2
k(A: + 1)
+ +((1)
vI- as 11, (6)
2
V2( - 1)
k-1 (-1)) + (1)
Na(2) = Nx(-1)+
v1+z as -1
1=1
When 8 = 1. the singularity at ===-11 will not provide vI + term. The dominating term in a higher power of /1 + 2. As a result, the contribution of the singularity at -1 to the Maclaurin coefficients is 3/2) and dominated by the contribution of the singularity 1. The singularity provides v1 - z term and thus contributes to O(n -3/2) decay rate of [=)). In addition, from 66. we deduce
Na(=) n 3/2
2/2k(k: +1) k(k +)
(- 32
When 8 + 1, both singularities +1 contribute O(n 3/2) to the Maclaurin cofficients. The contribu- tion of is
v2(1 + f8)k(k + 1) 3322
(52 - 1) kok + 3/2
3/2
2T[ (-
2v 27/3/2
The contribution of = - is
V2 1) k-1 (o(x)(-1)) xT(-1/2) ==1
1- 32 k
n n13/2=
II
Ka (o((<((11)
n -3/22
3/2222
Combining them gives
2 (2)) n 3/2
(32 + 1)k((++ +
82 1-1
+ (-1)"
no (n( (-1)).
(9)
2/22m3/2
3/m
/=1
Based on Theorem we are ready to prove Theorem
Proof. Let K1ap(z) e -v- where > 0 is arbitrary constant. We have Hkup Hlap. The complex function KLap is analytic on C \ [1, oo). As + 1, we have
(zap(z) 1
V1 + p -1
By Lemma 6 obtain
Kiap(2) (2)
3/2
(10)
2/
Note that [2))) On 3322 from Theorem 8 Therefore, there exists 2 such that 72 (L)) - [x>) > for all n 2 This further implies 7² 22 (x y) N& y) is positive definite kernel. According to Lemma we have HM, (Sd-1) C Hlap (Sd-1.. Note that,
due to (Geifman et al. 2020 Theorem 3), we also have Hesp (Su-1)= C HN, (Sd-1). Therefore, for any t 2 1, Hiap (Sd HN, (8d-1).

---

Published as a conference paper at ICLR 2021
4 RESULTS ON EXPONENTIAL POWER KERNEL
This section presents the proof of Theorem We first show part below by singularity analysis.
Proof of part ( of Theorem 2 Recall that the exponential power kernel restricted to the unit sphere with 7 and
is given by Keip (z, v) exp - exp (2(1-x "[(1->">)))//> ")))"/²) Let
a us study the decay rate of the Maclaurin coefficients of Keip (z) _ e e -0)7-2)7// where = 27 /o. The dominant singularity lies at z As + 1, we get
K KT- (z) = (c o11)) -)
Applying Lemma gives [="] K3p (z) RKHS.
cn 7/2-1
Therefore, a smaller y results in a larger
--(-)
Part of Theorem 2 requires more technical preparation. Recall that L and L- 1 denote the Laplace transform and inverse Laplace transform. respectively. We explicitly calculate the inverse Laplace transform L - (exp((x*))])))) (() using Bromwich contour integral and get the following lemma.
Lemma 9 (Proof in Appendix B.
For E (0,1), f(t) (oxp((xx"(ss)pp))e exists. Moreover, ft) is continuous in -0 < oo and satisfies f(0) Ift > 0. we have
0a f(t)
-1)*+TT(akk 1) sin(Tak)
(11)
kltak+1
π
Based on the series representation we then analyze the asymptotic rate for f(() when a is rational. Note that if (0, 1). we have T[ 0.
Lemma 10 (Proof in Appendix B.2). Let (t) be as defined in Lemma 9 For E (0, 1) and
are co-prime), we have ((t) [+ as 1 - +00.
Thus, We have the following corollary for general exponential power kernel.
Corollary 11. For a E0, (0, (p and q are co-prime) and -6 - (cx)((x//o))(() is continuous f. E and satisfies - (exp( - /a)](0) = O. Moreover, of (exp((x((
Ct-a-1 as t - +00, for some constant C >
Proof. Use the property L (F)ss(())) = f (!), where >> and F(s) = L(f(t))(ss
Before completing the proof for part we need two additional lemmas from the classical ap- proximation theory. Recall that a function ftt) is completely monotone if it is continuous on [0, oo), 2 0 for every 0, 1, and f.
infinitely differentiable (0, oo) and satisfies (-1) d" f(t)
de
Cheney & Light 2009 Chapter 14).
Lemma 12 (Schoenberg interpolation theorem (Cheney & Light 2009 Theorem I of Chapter 15)).
If f is completely monotone but not constant on (0, 20), then for any n distinct points 3 ...,............................ in any inner-product space, the matrix Aij = f[[12; 2²2 is positive definite.
Lemma 13 (Bernstein-Widd Widder (Cheney & Light 2009. Theorem I of Chapter 14)). A function
o0) [0, xc) is completely monotone if and only if there is a nondecreasing bounded
function g such that [(() So dg(ss.
Now are ready to prove part
Proof part
2 of Theorem
By Lemma 12 and Lemma 4 we need to show that
2 exp( 1/2p/xm12//0 exp( exp(->na/2 /02)
(12)
7

---

Published as a conference paper at ICLR 2021
completely monotone but not constant [0, oo) for check that (12) is the Laplace transform of a non-negen non-negative function on [0, 00). By Corollary for rational 7 72 (0, 1), there exists > 0 such that
0. By Lemma B it suffices to
e [exp(- (01(->>1///0))) - - (exp((--->> /02))
continuous and positive on [0, oo), which completes the proof.
NUMERICAL RESULTS
[2"]
[z]K(2) 32
3.0
2.0
2.5
Lap
Lap
2.0
M
N.
1.5
1.0
No
No
1.0
0.5
20
40
60
80
100"
20
40
60
80
100
(a) B =
(b)
Figure
We plot [="] K(=)/n -122 versus n for the Laplace kernel Ki.a(()) e 2(1 2(1-u) and
3/2
NTKs NI....,N. N4 with 3 = 0,
((()) 3/2 = 1)
[s Kx))
Kernel K
Theory (3 =
Theory (B
100 3/2 (5 0)
Klap
0.28244
Rs 0.282095
2VE
N1 0.261069
V2
0.253975
0.261069
~ 0.253975
3/2
Na 0.776014
3v/2
R 0.761924
0.457426
2x/2// RJ 0.444455
7572
N3 1.54607
6v2
R 1.52385
0.821694
13t arccos(
2: 0.800218
T3/2
2/2x5/2
N4
2.56559
10v2 33/2
RJ 2.53975
1.32472
Equation
13
~ 1.29531
Table 1: We report the numerical values of [a 100 K(s)
100 8/2 for the Laplace kernel Ki (u)
- 2( ()
and NTKs , N₂ with Fig. We present the theoretical prediction by the asymptotic of [e]]((2/m)) 3322 alongside each numerical value. The choice of / does apply the Laplace kernel. Therefore, we only show the results of the Laplace kernel in the columns for 3 = 1 and leave blank the columns for B f==0 0.
0, These numerical values the final values of the curves in
We verify the asymptotics of the Maclaurin coefficients of the Laplace kernel and NTKs through numerical results.
[=)) 3-2 versus for different kernels, including the Laplace kernel KLap(u)
Fig.
plots
u1) and NTKs N,,...,N4 with 0, 1. All curves converge constant as co. which indicates that for every kernel K(2) considered here, have [2 K()) O 3/2)). The
numerical results agree with our theory in the proofs of Theorem 8 and Theorem
Now we investigate the value (=))/
3/2 for the Laplace kernel and NTKs with 3 = 0, These numerical values are the final values of the curves in Fig. The theoretical predictions are obtained through the asymptotic of [=*) 3322 -3/2, which
Table 1 reports
-/2
we shall explain below. The theoretical prediction of Na())/100000 with 0 is presented below due the space limit the table
20 π -2 2TT arcoos (T (1) arccos
areens
1.29531.
(13)
2/2
8

---

Published as a conference paper at ICLR 2021
We observe that the theoretical prediction by the asymptotic is close to the corresponding numerical value. There are two possible reasons that account for the minor discrepancy between them. First, the theoretical prediction reflects the situation for an infinitely large (so that the lower order terms become negligible), while n = 100 clearly finite. Second, the numerical results for the Maclaurin series obtained by numerical Taylor expansion and therefore numerical errors could be present.
In what follows, we explain how to obtain the theoretical predictions. First, TO gives [>"] KLap(())/ ///////n//////// 3/2
2/5- As a result, the theoretical prediction for [=100] (ap((()) (z)/100 3/2 is
2 Now we explain the thereotical predictions for NTKs. When 3 1, the theoretical prediction is given by (8. We present it in the third column of Table T for N.,..., N4. When 3 = 0. we plug
= into and obtain [="INa<=) 2v/23//2 v2=3/a I Ko (-1(-))) The above expres- 572
&(k+1) (-1)
sion (when 100 the right-hand side) is the theoretical value presented in the fifth column of Table for NTKs.
6 DISCUSSION
Our result provides further evidence that the NTK is similar to the existing Laplace kernel. However, the following mysteries remain open. First, we still restrict them to the unit sphere, do they have a similar learning dynamic when we perform kernelized gradient descent? Second, what is the behavior of the NTK and the Laplace kernel outside of $ and in the entire space IR Do they still share similarities in terms of the associated RKHS? If not, how far do they deviate from each other and is the difference significant? Third, this work along with (Bietti & Mairal 2019 Geifman et al. 2020) focuses the NTK with ReLU activation. It would be interesting to explore the influence of different activations upon the RKHS and other kernel-related quantities. We would like to remark that the ReLU NTK has clean expression partly because the expectation over the Gaussian process in the general NTK can be computed exactly if the activation function ReLU (which may not be true for other non con--inarisiiss, for example, it may require more work for sigmoid). Fourth, we showed that highly non-smooth exponential power kernels have an even larger RKHS than the NTK. It would be worthwhile comparing the performance of these non-smooth kernels and deep neural networks through more extensive experiments in variety of machine learning tasks.
Moreover, show that less smooth exponential power kernel leads a larger RKHS and therefore greater expressive power. Its generalization capability is a related but different topic. Analyzing the generalization error requires more efforts in general. Researchers often the RKHS norm to provide an upper bound for it. We will study its generalization in future work.
ACKNOWLEDGEMENTS
We gratefully acknowledge the support of the Simons Institute for the Theory of Computing. We thank Peter Bartlett, Mikhail Belkin, Jason D. Lee, and losif Pinelis for helpful discussions and thank Mikhail Belkin and Alexandre Eremenko for introducing to us the works (Hui et al. 2019 Liu et al. 2020) and (Flajolet & Sedgewick 2009), respectively.

---

Published as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning. pp. 242 252, 2019.
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68(3):337-404 1950.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems, pp. 8141 $141-8150, 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In 36th In- ternational Conference on Machine Learning, ICML 2019, pp. 477-502. International Machine Learning Society (IMLS), 2019b.
Kendall Atkinson and Weimin Han. Spherical harmonics and approximations on the unit sphere: an introduction, volume 2044. Springer Science & Business Media, 2012.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-61, 2017.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to under- stand kernel learning. In International Conference on Machine Learming, pp. 541-549, 2018.
Alberto Bietti and Francis Bach. Deep equals shallow for retu networks in kemee regimes. In ICLR, 2021.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In Advances in Neural Information Processing Systems, pp. 12994412004, 2019.
Nicholas H Bingham. Positive definite functions spheres. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 73, pp. 145-156. Cambridge University Press, 1973.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pp. 10836-10846, 2019.
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv:1912.01199 2019.
Elliott Ward Cheney and William Allan Light. course in approximation theory, volume 101. American Mathematical Soc., 2009.
Youngmin Cho and Lawrence K Saul. Kernel methods for deep learning. In Advances in neural information processing systems, pp. 342-350, 2009.
Gustav Doetsch. Introduction the theory and application of the Laplace transformation. Springer, 1974.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, 2019a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameteriizd neural networks. In International Conference on Learning Representations, 2019b.
Zhou Fan and Zhichao Wang. Spectra of the conjugate kernel and neural tangent kernel for linear- width neural networks. arXiv preprint arXiv:2005.11879, 2020.
Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. cambridge University press, 2009.
10

---

Published as a conference paper at ICLR 2021
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Ronen Basri. On the similarity between the laplace and neural tangent kernels. arXiv preprint arXiv:2007.01580, 2020.
Like Hui, Siyuan Ma, and Mikhail Belkin. Kernel machines beat deep neural networks on mask- based single-channel speech enhancement. Proc. Interspeech 2019, pp. 2748-2752, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, and Sanjeev Arora. Explaining landscape connectivity of low-cost solutions for multilayer nets. In Advances in Neural Information Processing Systems, pp. 14601-14610, 2019.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Toward theory of optimization for over- parameterized systems of non-linear equations: the lessons of deep learning. arXiv preprint 0rXiv:2003.00307,, 2020.
Ha Quang Minh, Partha Niyogi, and Yuan Yao. Mercer's theorem, feature maps, and smoothing. In International Conference Computational Learning Theory, pp. 154-168. Springer, 2006.
Iosif Pinelis. Analyzing the decay rate of taylor series coefficients when high-order derivatives intractable. MathOverflow, 2020. URL http:tttt///tahhwtetttt
Saburou Saitoh and Yoshihiro Sawano. Theory of reproducing kernels and applications. Springer, 2016.
I J Schoenberg. Positive definite functions on spheres. Duke Mathematical Journal, 91):96-108, 1942.
Murray R Spiegel. Laplace transforms. McGraw-Hill New York, 1965.
Greg Yang and Hadi Salman. A fine-grained spectral perspective neural networks. arXiv preprint 1rXiv:1907.10599, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 109(3):467-492, 2020.

---

Published as a conference paper at ICLR 2021
Appendices
Table of Contents
Proofs for Neural Tangent Kernel
12
A.1 Proof of Lemma B
12
A.2 Proof of Equattin
12
A.3 Proof Theorem
12
Prool Theorem
B
Proofs for Exponential Power Kernel
18
Proof of Lemma 9
18
B 2 Proof of Lemma
21
A PROOFS FOR NEURAL TANGENT KERNEL
A. PROOF OF LEMMA 3
Proof. We show it by induction. holds when i by the initial condition 3
Assume that
holds for some & 2 0, i.e., En Ex, 2) = 1. Consider &: 1. We have
E2t1 x) = Ki (Ex =)) = x (1) 11
A.2 PROOF EQUATION
Proof. We plug Ex(x, x) = 1 into (2) and obtain
Σx y) = H1 (2,
N* y) >x u) +
+ 3².
Recall Σo(r, y) u. By induction, we get
En(u)= x|
(4) (u).
where (1) 2 ni (w) = ki(Ml m (k) ... )) is the k-th iterate of ki (u). Then it follows
Na(u) = Ki (k) (u) + N (u)) (u)) + B².
A.3 PROOF OF THEOREM
Lemma 14 and Lemma 15 demonstrate that +1 are indeed singularities and analyze the asymptotics (k)
for R as z tends to +1, respectively. Our calculation inspired by Pinelis (2020), which only considers k: 2.
Lemma 14. For every 2 1, there exists es (z) such that
K (k) (2) (x 2)3/2
where
2v2k
lim en (=) 2-+1
3x
12

---

Published as a conference paper at ICLR 2021
Proof. We prove by induction on k. We first prove the statement for & 1. Let 1 ree Taylor's theorem around with integral form of remainder gives
N1 (2) = + J,
2 w
1V u dw,
where y: :0, - C is the simple straight line connecting and z taking the form 7()) = 1 tre It follows
(2) =2
2 w 7 v w
dw
VT 1
v2
dw +
1)dw
TT TTV211 w
AVVVVVI w
V1 + w
Since
2 V1 w(w 32 + 2)
w==
VI dw
(1 2)3/2
3
w=1
have
2v2
V2 1)dw.
(1)2) =
2)3/2
3T
TTTV2211 w
VI+ w
We then turn to show
V2 VI w
lim (1-
-- w TVV
1)dw 0.
Direct calculation gives
V2
lim (1 -3/2 x+1
2 w
1)dw }
7 vI w
VI + w
(1 - 1)r²
V2
lim (rel0) - r-0
1)tt)
Virele
V2 treid
1-1
1
lim
1)dt
r-00
Vt
11--trel trrtre0012
0.
Therefore, there exists ei (z) such that lim ci(z)= 33 f 0 and
2/
Ny (2)2) + c1(2)(1 - 2 2//22
Next, assume that the desired equation holds for some k > 1. We then have
(1+ (() (2) (x( (2))
R1
=s + (x) 2)3/2)
=2+a(=)(1 2)3/2 ta (nf* (1-2- cx(2)(1
- (1-=2-c(()(11-
=)3322 3/2
= = - 2)3/2,
where (2) cx(2) cı (k(xt) (z)). Recall that when z 1, we have n ((()(2)) well.
Therefore we deduce
2v2k
lim Gb+ (z) = lim ca + lim ei (k(())) 2-1
3x + 0.
2-21 2-+1
13

---

Published as a conference paper at ICLR 2021
Lemma 15. For every l 2 1, there exist aj E R and comple by (2) such that
Ki (z) on + (x
(k)
where
2 A-1 3
a2 Ki (-1) and
lim bx(2) 2--1
II j=1
Ki (-1)) 00.
Proof. We prove by induction on k. We first prove the statement for k = 1. Let 2 -1 + re Taylor's theorem around with integral form of remainder gives
x1)=) J, . w
dw
where 10 + C is the simple straight line connecting -1 and 2 taking the form 7(1)
-1 tre Similar arguments in the proof of Lemma give
K (z) = (= 1)3/2
where limz---1
2v2 3x
Next, assume that the desired equation holds for some h: 2 Define hes A ki (-1). Since &
(k)
strictly increasing on [-1, 1]. Kn (-1) 0 and ks (1) 1, we have h 0 and ha (0, 1) for all
Expanding 1n around fy yields
Ni <1(2) = x (ha) + p(=)(z - hx)) = hx+1 + (=
where limz-she p(=) = n1 (h+). follows that
K xx) = ka + bb(() + 1)3/2) hg+1 p(ni (x) (x) + (x(=)(=++))))) hxx)
a#41 + ( 1)
where ak+1 = het1 + Ni (1x) h&) and lim 1x+1(2) = <² (ha) lim (2).. By induction, we can show that as hx for all k Since Ki strictly increasing on |-1, 1]. wi (-1) 0, and (1) = 1, we have Ky (ha) 2 x (0) > 0. As result,
2V2
lim (2) = 3m 2--1
II R (~= 0.
In the sequel, we show that 11 are the only dominant singularities of (1))) and x/th) is A-analytic at +1 (Lemmal) 19p.
Lemma 16. For any z C with arg E 70,m/4), (=(=) HH For any = C with arg (-T/4,0), (
Proof. The second part of the statement follows from the first according to the reflection principle. We only prove the first part here. Let 2 r0 with 0 E 7444 Taylor's theorem with integral form of the remainder and direct calculation give
Ki (=) ki (0) (0)=
[=-- w))"(w)dw + 2
w
dw
TV
where 7 [0, 1] C is the simple straight line connecting 0 and taking the form 7(t) tre
Then we have
Z w
du 2 210
1
210 [
12 dl
2
π
212
TV
14

---

Published as a conference paper at ICLR 2021
Since 8 E (0, x/4), we have arg(1 - - (-x, 0). Further
arg (% r
arg vI f2
E (0, 7/2) and
E (0, m/2).
12
Noting arg( E (0, 12),, we get
arg
w TV w²
dw E (0,
which gives positive imaginary part. Combining with 3(1/T + 2/2) > 0 yields the desired statement.
Lemma 17. For every k 2 1 and e > 0, there exists 8 > such that K1 (k) and (6) n H. with
is analytic on (6) nH
B1 (6) n _ (
Ki (0) C (1
(k)
Proof. We present the proof for H here and that for H can be shown similarly. We adopt induction argument on
1, for any 0, there exists For k 1, Kj is analytic on H Since Ki is continuous
0 < 8 < 1/2 such that
Ki (8) n n ç (s)..
Lemma 16 implies xi (B) H++ H+ Combining them yields
K1 [ (2) S (e)
(14)
Now assume that the statement holds true for some k > 1. Note that for any >> 0, there exists < 8 1/2 such that (14) holds. Then by induction hypothesis, for this chosen 8, there exists
61 0 such that (k) is analytic on B, (51) HH+ and
(1) (B.()) n
follows
(k+11 (Bi K1 (B(()))))))))))))))))) H+) s nHr
This completes the proof.
Lemma 18. [x](2) < 1 for any |z| < 1, where the equality holds if and only if z 1.
Proof. The Taylor series of Ki around is
1
0c
(2n 3)!!
(2)
2n
π
22n 1)n!2"
Therefore, for |2| < 1, we have
(2n 3)!!
[x](2) <
+
2n k1 1.
2
(2n
1)m!22m
The equality holds if and only if
Lemma 19. For each & 2 1, there exists >> 1 such that K is analytic on E & R)
where D = C \ [1, 00) \( (-00, -1).
15

---

Published as a conference paper at ICLR 2021
Proof. For any 0 n/2, there exists 60 such that for all |2| with arg 2|
8, we have
[m1(2)] - 6g.
To see this, we use an argument similar to Piinelis 2020). If we define @ - arg 2, we have
1
2
| cos Φ
π
COS
1
2
COS 8
1
+
80
π2
2
2
for some 6g 0. Consider the Taylor series of Ku around 0
(2n 3)!!
(=)
2n
2 n
(2n 1 )n!2n
We obtain
0C
(2n
3)!!
00 +
(2n 3)!!
+ 2
|/|
2m
1
+
89
1 - 60
(2n 1
2
(2n 1)m!2nX
n=
Lemma 17 shows that there exists < 8 < 1 such that K] is analytic on B1 (8') n D. From the
argument above, we know that ア₁ maps A {a E C |a| = 1, arg 2| 2 0} to inside of the open unit ball (1).. Since A compact and Lemma 18 implies that y maps (1) (1)),, there exists 1 < Rg < 1 + 8' such that 11 maps
Aa (1z E C |1|
/ 2 03 n D) Ba(1)
to (1). It follows that ma is analytic on Ag. Let us pick 0 E (0, T/2) such that e (8)). (k) Then we conclude that ni is analytic on {2 E C |a| S Ro} n D.
Now are ready to prove Theorem
Proof. Since Ro and 11 are both analytic on D (C(1,,0)\((55 -1], similar arguments as in the proof of Lemma 19 shows that No (n (k)
(2)) is analytic on {= E C |>| < R} D for all k 2 1 and some R > 1. We then show, for any k 2 1, there exists some R₂
such that Nx(2) is analytic
on {= E C |z| < R D by induction. The function No(z) = + 3 is analytic on D. Assume
NR-
(=) (z) is analytic {2 E C
| R D for some RE-1 1. Recall that
N&(2)
Ki (k) (z) + N (k-
(z)) + 3
Then we can find some R2 > 1 such that (z) is analytic on fa C | & Rk) N.
A.4 PROOF OF THROREM g
Proof. We first analyze the behavior N&(2) as + for any & 2 1. We aim to show, for any
2 1, there exists sequence of complex functions (x(2) with lim Pp())) = (2)
1)/27 such that
N*(2) (k + 1)(2 + Px
(15)
We prove by induction on k. Recall
Ro(2) log(( + 1V1 22
The fundamental theorem of calculus then gives for any 2 E D
xo(2)) + T 2 dw
16

---

Published as a conference paper at ICLR 2021
where 7 [0,1] - C is the simple straight line connecting 1 and 2. As 1, have
vI-
v2v1-2' Therefore, similar arguments as in the proof of Lemma 14 give
ko(2) 1 + +
where lim h(2) v2 Combining with Lemma 14 further gives, for any k
(o( (k) (z)) 1 + h(Ri
(xx)((())) (z)) 1 cx(x)(1 2)3/2 (x(2) -2,
where lim 1u (z) = --2 For k = 1, we then have
12,
- (=)=) = <1)))) + (z + (o) + 32 = - (2 (=)))))(((+)(((+ B
= =[ ()) =-
where lim;-111(2) 2/² and lim;-111 = - -V2(1+ /3) Assume N2-1 = k(2 +
3r
88) + 12)v/ with lim = -2((1 + =
(-)=(k-- 12x. We further have
(x(2)= =x² nx (z) + N ( (K- (z)) - 32
=2+d 2)3// (1(2 88) + Ph- 1x-1 - (1 hh-hha-122 (x-1(t)/11)
= +k++ 1)(++ (2) + (Pk-1 (2) + k. h1 (=) 11)
(k + 1)(2 (²) + +px(=)v] z.
where we set (z) 1 (2) + k. (2) + B²) and (z) + 3x
2y2k
12) - y2 as
2 + 1. Moreover, we have
.imm (x()) lim (p-- 12) + 1h-1 +137}
=-1
22(1 + )B) - 1)
V2 (1 + B2)
k
2x
v2(1 )at + +1)
2n
which is desired. This proves
15
Next we study the behavior of (2) -1 for any 1: 2 1. We aim to show, for any k 2 1, there
exists a sequence of complex functions (=) with lim (2) = - 1)
ka(a))/T
(k) and ag e naj (-1) as defined in Lemma 15 such that
Nx(2) = Na(-1) + on (=)
(16)
We again adopt induction on k. Taylor's theorem gives
Ko(2) = ko(ax) + rx(2)(2 - -x),
where lim rx(2)) m(g) > 0. Combining with Lemma 15 further gives, for any
NO(K1 (2) = ko(a)) + rx(
(k) (z))bx (z)(2 + 1)3/2 ko(ax) [= 1)3/2
where bx(2) 2/ II =
k-1 (ax) and (x(2)) 2 (1)( (ax) 0 -1 by
Lemma [5] For lo 1, the fundamental theorem of calculus gives for any D
ko(2) = / TVII dw,
where y: [0. 1] -> C is the simple straight line connecting -1 and 2. As - -1, have
vi-z2 V2.14=" Therefore, similar arguments as in the proof of Lemma 14 14ve
<o(=) =(=)vT+2,,
17

---

Published as a conference paper at ICLR 2021
where g(z) v
1. We then have
N1(2) (2+
a1 +))(((((++)))+++++0 (2+ (2+ (9(3)/+++++
= (a1 + + -
(1
where (i(-1) ai + 3 lim;---19( L2
* (3² - 1). Assume Nz- = N +
2h (ee=(=) + with lim lim=--1 12 -1)[T
ko(a;)/mT We further have
[x(2) = (x) (3) (2)) + +32
= ax + bx(2) + - (z) (Ro(a=-1) + (000==))))---(((++))))))+) + 3²
(ux + 8² No
Ne- + 1)3/2 + (bx(2) + Nz-1
(ax B 1--
+ + N
(2
-Na(-1) + (2) 1V (ba(2) Nk-1 Ne-1 (2 1)3/2
(-1 + qb (2)
where we use the induction assumption in the fourth equation, use the fact N&(-1) = ax B (1-1(-1)r((ax-11) in the fifth equation and define
@ (x) = Ok- (z) (ax-1) (bx(2) + (2-
in the last equation. We also have
lim (x(2)= lim + 5--1
{9x- ( + (ba(2) Nk- (2)
= lim
= 19--1 (2))o((x-)))
12 k
(o)))
π
which is desired. This proves
16]
Finally, according to Theorem
combining (1) and [6]. applying (Flajolet & Sedgewick 2009
Theorem VI.5) with p = r 7(2) (1 22 Ci C2 (2, (k + 1) +
(2(2) = (-1) D (2 E C ||] R D. we conclude [>*] O(n 3/2).
B PROOFS FOR EXPONENTIAL POWER KERNEL
B. PROOF OF LEMMA 9
Proof. According to DDetschh 1974
Theorem 28.2), we have, for 0 < a < 1,
f(()
lim 2ni T T
exp(ts
ds
(xn 2 0).
20-IT
Also (Deetsch 1974 Theorem 28.2) implies that f(1) is continuous in -00 <t <t< < toc and f(0)
Next explicitly calculate f(t) using Bromwich contour integral. We denote each part of the Bromwich contour by Io....,Is I''s as depicted in Fig 2 Denote the radius of the outer and inner are by R and r. When + co, we have R TT² + o + oo. Also we let + 0 and Pz, Ia tend to (-o0, 0) from above and below respectively in the limit. By the residue theorem, we have
(L. +...+ [
exp(ts sn)ds = 0,
18

---

Published as a conference paper at ICLR 2021
32
F1
Jo + i7
R
12
To
Rz
Ta
F4
17
I's
Figure 2: Bromwich contour that circumvents the branch cut (-o0, 0]
which implies
+o+
exp(ts - 5 = lim / exp(ts 5d)ds
lim T T-000 Bo-IT
T-00 /ro
- lim (/- +...+ (() exp(ts - ss
=-lim
limml1 + ... + 1s),
where the last two limits are taken R 0o, and I'2, 14 tend (-o0, 0J. We then calculate each part separately.
Part I: We calculate the parts for I1 and F We follow the similar idea as in the proof of (Spiegel Theorem 7.1). Along 11 since Re.8 with Oo n, 0o arccos(z0o R),
1965
1 Be e Re -
"R f t Ra i9e d0
1/2
111 + 112.
For I11,
1//
In
<
le R le- R cos(a8) Rd0
90
1/2
Iit cos e
R8 cos(ar/2) Rda
9n
R
e Rt 0
1o co0c(2a0
Ho
R
Rt dd
Ro.cos (2)
where do = x/2 - 00 = arcsin(zo) (2o/ R). Since sin o < sin do S xo/ R, we have
Inl < [ocos(an/22 Tot
not arcsin(zo/ R).
Ra Racos(an/22
As R - D0, we have lim p I = 0.
For I12.
1
x
112 S
Et cos e RR cos(a8) Rdo
1/2
19

---

Published as a conference paper at ICLR 2021
First, consider the case 0 1/2. We have ab I am < //2 and cos(a0) 2 cos(aa)) 0. lt follows
Rt cos
e R² cos(a!) Rd0
e
1/22
Re R cos(ox)
e cos 8
d0
n/2
T/2
RR cos(az)
Ritii de
T//2
S Re Re- cos(ax)
2-2166// do
0
=e" cos(an) π (1-e-1t
21
where in the last inequality we use the fact sin ø 2 20/T for Φ [0, /22. Thus, lim I12 = 0.
Next, we consider 1/2 < 1. Define
p(0) & Rt cos 0 R cos(at).
We then have its second derivative as follows
p0( a² R cos(att) Rt cos(O).
Choose ò to be fixed constant in (0, { 1)). Since 2 1/2, then n 1f 2 n
p²()) 2 aa² Rt cos( क / + 6) = a R (t))
Since 1, there exists some large Rı such that p²( a2 RD Rtsin(() > 0 holds for all R > Rj. If n 2/2 < 0 < 7 + 6,
p"(0) a R cos(a(1/22)) 8)).
Since aTT/2 - 8) < T/2 by the choice of 8, we get cos(a( 2 + 6)) > 0. Then we also have (0) 0. Therefore, if R R1, p(0) convex 0 E [T/2, x]. As result, get
p(0) m (2) p(m)) 0
Write
h(R, 0) Ro e e -R" cos(at) (8)
Then we have
M(R,0) max (Rx, h,) 0 m
Rmaxfe - R² coa( 30 RR cos(Te)
Rmaxfe - 11 cos( 24)
R Rtt -R-
which goes to 0 as R + 00. Therefore, h(R, 0) converges to uniformly (as a function of 0 E [m/2, .] with index R), which implies
[" A(R,0)d8 0. a/2
lim R
Hence, we establish lim 112 = 0 for all E 1).
Combining these above, conclude lim J 0. Similarly, lim Is 0.
20

---

Published as a conference paper at ICLR 2021
Part II: We calculate the parts for D2 and T4. By the dominated convergence theorem, have, for
y
>
lim
lim
exp(ts) exp(-s"
r-50
R+iy
y-+0
y-+0
rtt
(-1)% yak
lim R-000 r-0
exp(ts)
ds
k!
RRii
y-
(-1)
-r+ty
lim R
k!
_R+4y
exp(ts)s
ds
k=
y
We then calculate the limit of the summand.
f 0 _ do exp(ts)s ds
him
R+iy
0
e tt a da
tak+I [(ak 1)
Similarly, we obtain the corresponding part in I'4:
R+iy
exp(ts)s ds = / 1 1[-=xe -mrjak dx
lim
R R-000
ritiy
r-0
V0+
-lakk fab+1 I'aak + 1)e -mok
Combining the parts of D2 and 14 together, we get
(-1)*
(ak + 1) sin (Tak)
lim + +1)
k!
1ak-1
k=0
Part III: We get the limit for I33 is 0 as
Combining the three parts above, we conclude
1)
21l (ak + 1) sin (Tak)
((1)
2mi
hd
pak+1
k=0
6+ I(k + 1) sin (Tak)
k!tak+1
B.2 PROOF OF LEMMA 10
Proof. Euler's reflection formula gives
['1 + ka)l (-ka) = sin(
π
ka $ Z.
21

---

Published as a conference paper at ICLR 2021
According to Lemma
we have
f(t) 1
(-1)
P(ak 1) sin(Tak)
kltak+1
k=0
(-1)
kltak+ Ttaak+T((aal) (-aak)
(17)
== (ng (()ltttoot))(I((---0 j))
First, we show that the series in 17 converges absolutely:
(ng + [])l[[a +
-p (nq (- + j))
|t n=0
mp i= (aj + i)
(18)
(ng + +
The inner summation in (88 convergence is co. Define
power series in P. We would like to show that its radius of
up (aj +
bn 1=1
(nq + j)!
We have
bn+
Impers(attp(1) (aj+ +
Il
ajtnpti j+nq+i
bn
Ingeis(mt1ig (j i)
1= (j+
+ (j ii) (j Ui+nq p + 1)8-0 0.
As result, the radius of convergence is Then have
9-1 1(1)
(-1)m(+ta)+3 pm [ (aj +1)
aj
(ng + +
(-1)
1)n(pto)ts1 pm I (aj +1) (ng + t))!
1ai- IT(
-aj)
j!
Notice that the quantity A goes to as t too. Therefore deduce
(-1)
1(1)
1os+1]l((aa))
[a+l[(-a)
as t + +00.
22


Reviews:
[{"review_id": "nckpNsGN1Sn", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper compares the reproducing kernel Hilbert spaces (RKHSes) generated by a deep neural tangent kernel (NTK), a Laplacian kernel, and an exponential power kernel. The main result is twofold: 1) the RKHSes associated with a NTK and a Laplacian kernel  contain the same set of functions when restricted to the sphere S^{d-1}; and 2) the RKHS generated by the exponential kernel with a smaller power contains more functions when restricted to the sphere S^{d-1} or R^d.\n\nThe key proof idea involves an analysis  the asymptotic rates of the Maclaurin coefficients of the kernels. Aronszajn’s lemma is then used to establish the inclusion of the RKHS. A notable contribution in the proof is the application of analytic combinatorics to obtain the asymptotic rate O(n^{-3/2}) of the Maclaurin coefficients of the NTK which is intractable due to its recursive definition.  The authors also provide numerical results showing the empirical rate matches the theoretical asymptotic rate of the Maclaurin coefficients of the Laplace kernel and NTKs.\n\nOverall, I think the paper is well-written, and the proof is solid.  The proof technique using analytic combinatorics seems novel, and the main results are useful for theoretical understanding of neural networks.", "extra_scores": {}, "extra_text": {}}, {"review_id": "fl4O5Z2MbnZ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper uses singularity analysis developed in the context of analytic combinatorics to study the relationship between the reproducing kernel Hilbert spaces of the NTK in a deep fully connected ReLU network, the Laplace kernel, and exponential power kernels. The main results are when these kernels are restricted to the unit sphere. In particular, the authors show that, as vector spaces, the RKHS on the unit sphere of the NTK for a ReLU network of any fixed depth are the same and in fact coincides with that of the Laplace kernel. The authors also compare the RKHS for exponential power kernels, demonstrating that larger powers lead to smaller Hilbert spaces. \n\nStrong Points: \n1. Understanding the NTK of a deep ReLU networks is a popular and important topic. \n2. The NTK is defined via non-linear recursions, meaning that obtaining quantitative results for deep networks is both technically and conceptually challenging. \n3. Proving that the RKHS of the Laplace and ReLU kernels coincides as vectors spaces is a substantial result.  \n4. The authors are the first, to my knowledge, to apply the rather elegant singularity analysis of Flajolet-Sedgewick to study the NTK. Perhaps the closes prior work used free probability to study the spectrum of the NTK. \n5. The paper is clearly written.\n\nWeak Points:\n1. As the authors themselves allude to in the discussion, showing that two RKHS are the same as vector spaces ignores the Hilbert spaces structure and can still lead to different inductive biases in kernel regression.\n2. The present work applies only to ReLU networks, while the recursive definition of the NTK is valid for rather general non-linearities. \n\nOverall, this article is a solid theoretical contribution to our understanding of the NTK. In addition to proving concrete results comparing the Laplace, NTK, and exponential power kernels, it is serves as a proof-of-concept for potentially using the tools of singularity analysis to understand neural networks. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "byvLOZa1SqV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The goal of this paper is to complete the theoretical subset inclusion relationships given in (Geifman et al., 2020).\nThe authors proved that the RKHS of the the neural tangent kernel (NTK) with any number of layers\nis a subset of the RKHS of the Laplace kernel.\nCombined with the results in (Geifman et al., 2020),\nif the input domain is restricted to the sphere of $(d-1)$-dimensional real space,\nthe RKHS of NTK with any number of layers\nis equal to the RKHS of the Laplace kernel.\n\nThe writing of this paper is very clear.\nI can easily get what the authors intend to express.\nHowever, I still have some doubts about the details.\n\nIn Section 2.1,\nthe original Laplace kernels and exponential power kernels are all classic shift-invariant kernels.\nHere the authors provided the dot-product versions of these two kernels.\nWhy do the authors need to do these changes?\nFor the sphere $\\mathbb{S}^{d-1}$, the shift-invariant versions are equivalent to the dot-product kernels?\n\nUnder Lemma 3,\nif $\\Sigma_k(x, x) = 1$,\nwe can only get $\\Sigma_k(u) = \\Sigma_{k-1}(u)$.\nWhat does the notation $\\kappa_1^{(k)}$ means here?\n\nTheorem 1 in (Aronszajn, 1950, p. 354) just stated that if $K_1 \\preccurlyeq K_2$, then $\\mathcal{K}_1 \\subseteq \\mathcal{K}_2$.\nI am very curious and doubting about Lemma 4.\nFor any positive constant $\\gamma > 0$,\ndoes Lemma 4 always exist?\n\nUnder Lemma 4, the authors stated that:\n1. \"Then the Maclaurin series of $K_{\\mathrm{Lap}}(u)$ and $N_k(u)$ have all non-negative coefficients by the classical approximation theory.\"\n2. \"If the Maclaurin series of $K(u)$ have all non-negative coefficients,\n$K$ is a positive definite kernel on the unit sphere.\n\nI cannot find the original documents of (Schoenberg, 1942) and (Cheney and Light, 2009).\nCould you please provide these results in the Appendix such that we can check the correctness of these results?\nThis is because, in the following part, all the proofs will be focused on $\\gamma^{2}\\left[z^{n}\\right] K_{\\text {Lap }}(z) \\geq\\left[z^{n}\\right] N_{k}(z)$.\n\nIn Section 3,\nI have two doubting points.\n1. The first one is under the definition of $\\Delta$-domain.\nThe authors used $z$ to replace $u$ and $u=x^{\\top} y$ as shown Section 2.1.\nIf we put $u=x^{\\top} y = 1$,\nthe Laplace kernels and exponential power kernels given in Section 2.1 will all become constant.\nCould the authors explain more about this assumption?\n2. The second one is under Lemma 5.\nThe authors stated that \"Careful singularity analysis then gives ...\".\nIt is very difficult for me to easily get these two results about Maclaurin coefficients.\nCould you give the detailed steps for the derivation of these results?\n\nIn Theorem 2,\nI am very curious about the seemingly contrary results:\n$\\mathcal{H}_{K_{\\text {exp }}^{\\gamma_1, \\sigma_1}} \\left(\\mathbb{S}^{d-1}\\right) \\subseteq \\mathcal{H}_{K_{\\text {exp }}^{\\gamma_2, \\sigma_2}}\\left(\\mathbb{S}^{d-1}\\right)$, and \n$\\mathcal{H}_{K_{\\mathrm{exp}}^{\\gamma_2, \\sigma_2}}\\left(\\mathbb{R}^{d}\\right) \\subseteq \\mathcal{H}_{K_{\\mathrm{exp}}^{\\gamma_1, \\sigma_1}}\\left(\\mathbb{R}^{d}\\right).$\nCould you provide more explanations about this point in Section 4.\nThe superficial explanations cannot help us understand this point.\nWe need to go deeper into the proof sketch to figure out what makes this phenomenon happen.\n\nI didn't go much deeper into the Appendix,\nso it is hard for me to check the correctness of the whole paper.\nSince ICLR is a highly selective conference,\nI will give a score 5 at present.\nAfter the authors solved my concerns and other reviewers verifies the correctness of all proofs,\nI may raise my score to 6 or 7.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ij5nD_wwWPy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proves that the reproducing kernel Hilbert spaces of a deep neural tangent kernel and the Laplace kernel have the same set of functions when they restricted to the sphere $S^{d-1}$, which improves the results established in Geifman et al., 2020. Moreover, the paper proves that more non-smooth of the exponential power kernel leads to a larger RKHS with restriction on the sphere $S^{d-1}$ and the entire $R^d$. Furthermore, the authors conduct numerical experiments to verify the asymptotics of the Maclaurin coefficients of the Laplace kernel and NTKs kernel. In summary, the paper is well-written and organized logically. The proof of theoretical results of this paper seems to be correct and reasonable, resulting from the full details of the proof provided in the appendices. \nThe contribution of this paper includes two parts. Firstly, it aims to explain why the Laplace kernel and NTK have similar performance in experiments from theoretical point of view by showing that the space of the Laplace kernel and NTK are the same when limited to a sphere. On the other hand, the author reveals the relationship between the smoothness of the exponential power kernel and the corresponding RKHS to explain the better performance of the exponential kernel with a smaller power in the experiments. \nNow I would like to give some comments, 1. Do Laplace kernel and NTK have a similar learning dynamic when we perform kernelized gradient decent in real-world dataset? 2. It is necessary to study the behavior of the NTK and the Laplace kernel outside of $S^{d-1}$. I wonder whether the theoretical results proposed are helpful to improve the performance of Laplace kernel or NTK. 3. The author demonstrates that a non-smooth exponential power kernel leads to a larger RKHS, but whether this indicates that the model obtained by adopting a non-smooth kernel has greater generalization capability. I think the author needs to further theoretically illustrate the relationship between them.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper closes an important gap in our understanding of neural tangent kernels. 
In addition, the used techniques are novel. 
My low confidence is mainly based on the fact, that the review process at conference is not perfectly suited to deal with such papers, since their review would actually require both expert reviewers and substantially longer reviewing periods.
Decision: Accept (Poster)