Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS

Introduction

In the past few years, one of the most seminal discoveries in the theory of neural networks is the neural tangent kernel (NTK) . The gradient flow on a normally initialized, fully connected neural network with a linear output layer in the infinite-width limit turns out to be equivalent to kernel regression with respect to the NTK (This statement does not necessarily hold for a non-linear output layer, because the NTK is non-constant ). 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 , generalization , and loss landscape of overparametrized neural networks in the NTK regime.

While NTK has proved to be a powerful theoretical tool, a recent work posed an important question whether the NTK is significantly different from our repertoire of standard kernels. Prior work provided empirical evidence that supports a negative answer. For example, Belkin et al. 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 $K_{\textnormal{exp}}^{\gamma,\sigma}(x,y)=e^{-\|x-y\|^{\gamma}/\sigma}$, which include the Laplace kernel as a special case, outperform deep neural networks with even shorter training time . The experiments in 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) . The work considered the RKHS of the kernels restricted to the sphere $\bS^{d-1}\triangleq\{x\in\bR^{d}\mid\|x\|_{2}=1\}$ and presented a partial answer to the question by showing the following subset inclusion relation

where the four spaces denote the RKHS associated with the Gaussian kernel, Laplace kernel, the NTK of two-layer and $(k+1)$-layer ($k\geq 1$) fully connected neural networks, respectively. All four kernels are restricted to $\bS^{d-1}$. However, the relation between $\cH_{\textnormal{Lap}}(\bS^{d-1})$ and $\cH_{N_{k}}(\bS^{d-1})$ remains open in .

We make a final conclusion on 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 $\bS^{d-1}$. In other words, we prove the following theorem.

Let $\cH_{\textnormal{Lap}}(\bS^{d-1})$ and $\cH_{N_{k}}(\bS^{d-1})$ be the RKHS associated with the Laplace kernel $K_{\textnormal{Lap}}(x,y)=e^{-c\|x-y\|}$ ($c>0$) and the neural tangent kernel of a $(k+1)$-layer fully connected ReLU network. Both kernels are restricted to the sphere $\bS^{d-1}$. Then the two spaces include the same set of functions:

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 $\bS^{d-1}$ and when it is defined on the entire $\bR^{d}$.

Let $\cH_{K_{\textnormal{exp}}^{\gamma,\sigma}}(\bS^{d-1})$ and $\cH_{K_{\textnormal{exp}}^{\gamma,\sigma}}(\bR^{d})$ be the RKHS associated with the exponential power kernel $K_{\textnormal{exp}}^{\gamma,\sigma}(x,y)=\exp\left(-\frac{\|x-y\|^{\gamma}}{\sigma}\right)$ ($\gamma,\sigma>0$) when it is restricted to the unit sphere $\bS^{d-1}$ and defined on the entire $\bR^{d}$, respectively. Then we have the following RKHS inclusions:

If $0<\gamma_{1}<\gamma_{2}<2$ are rational,

If it is restricted to the unit sphere, the RKHS of the exponential power kernel with $\gamma<1$ is even larger than that of NTK. This result partially explains the observation in that the best performance is attained by a highly non-smooth exponential power kernel with $\gamma<1$. Geifman et al. 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.

Minh et al. showed the complete spectrum of the polynomial and Gaussian kernels on $\bS^{d-1}$. They also gave a recursive relation for the eigenvalues of the polynomial kernel on the hypercube $\{-1,1\}^{d}$. Prior to the NTK , Cho and Saul presented a pioneering study on kernel methods for neural networks. Bach studied the eigenvalues of positively homogeneous activation functions of the form $\sigma_{\alpha}(u)=\max\{u,0\}^{\alpha}$ (e.g., the ReLU activation when $\alpha=1$) in their Mercer decomposition with Gegenbauer polynomials. Using the results in , Bietti and Mairal analyzed the two-layer NTK and its RKHS in order to investigate the inductive bias in the NTK regime. They studied the Mercer decomposition of two-layer NTK with ReLU activation on $\bS^{d-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 on arc-cosine kernels of degree and $1$. Cao et al. improved the eigenvalue bound for the $k$-th eigenvalue derived in when $d\gg k$. Geifman et al. used the results in and considered the two-layer ReLU NTK with bias $\beta$ initialized with zero, rather than initialized with a normal distribution . However, neither nor went beyond two layers when they tried to characterize the RKHS of the ReLU NTK. This line of work is closely related to the Mercer decomposition with spherical harmonics. Interested readers are referred to for spherical harmonics on the unit sphere. The concurrent work analyzed the eigenvalues of the ReLU NTK.

Arora et al. presented a dynamic programming algorithm that computes convolutional NTK with ReLU activation. Yang and Salman analyzed the spectra of the conjugate kernel (CK) and NTK on the boolean cube. Fan and Wang 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.

Preliminaries

Let $\bC$ denote the set of all complex numbers and write $\mathbf{i}\triangleq\sqrt{-1}$. For $z\in\bC$, write $\Re z$, $\Im z$, $\arg z\in(-\pi,\pi]$ for its real part, imaginary part, and argument, respectively. Let $\bH^{+}\triangleq\{z\in\bC\mid\Im z>0\}$ denote the upper half-plane and $\bH^{-}\triangleq\{z\in\bC\mid\Im z<0\}$ denote the lower half-plane. Write $B_{z}(r)$ for the open ball $\{w\in\bC\mid|z-w|<r\}$ and $\bar{B}_{z}(r)$ for the closed ball $\{w\in\bC\mid|z-w|\leq r\}$.

Suppose that $f(z)$ has a power series representation $f(z)=\sum_{n\geq 0}a_{n}z^{n}$ around . Denote $[z^{n}]f(z)\triangleq a_{n}$ to be the coefficient of the $n$-th order term.

For two sequences $\{a_{n}\}$ and $\{b_{n}\}$, write $a_{n}\sim b_{n}$ if $\lim_{n\to\infty}\frac{a_{n}}{b_{n}}=1$. Similarly, for two functions $f(z)$ and $g(z)$, write $f(z)\sim g(z)$ as $z\to z_{0}$ if $\lim_{z\to z_{0}}\frac{f(z)}{g(z)}=1$. We also use big-$O$ and little-$o$ notation to characterize asymptotics.

Write $\mathscr{L}\{f(t)\}(s)\triangleq\int_{0}^{\infty}f(t)e^{-st}dt$ for the Laplace transform of a function $f(t)$. The inverse Laplace transform of $F(s)$ is denoted by $\mathscr{L}^{-1}\{F(s)\}(t)$.

For any positive definite kernel function $K(x,y)$ defined for $x,y\in E$, denote $\cH_{K}(E)$ its associated reproducing kernel Hilbert space (RKHS). For any two positive definite kernel functions $K_{1}$ and $K_{2}$, we write $K_{1}\preccurlyeq K_{2}$ if $K_{2}-K_{1}$ is a positive definite kernel. For a complete review of results on kernels and RKHS, please see .

In the sequel, we introduce two instances of the positive definite kernel that this paper will investigate.

The exponential power kernel with $\gamma>0$ and $\sigma>0$ is given by $K_{\textnormal{exp}}^{\gamma,\sigma}(x,y)=\exp\left(-\frac{\|x-y\|^{\gamma}}{\sigma}\right)$. If $x$ and $y$ are restricted to the sphere $\bS^{d-1}$, we have $K_{\textnormal{exp}}^{\gamma,\sigma}(x,y)=\exp\left(-\frac{(2(1-x^{\top}y))^{\gamma/2}}{\sigma}\right)$.

Given the input $x\in\bR^{d}$ (we define $d_{0}\triangleq d$) and parameter $\theta$, this paper considers the following network model with $(k+1)$ layers

where the parameter $\theta$ encodes $W_{l}\in\bR^{d_{l}\times d_{l-1}}$, $b_{l}\in\bR^{d_{l}}$ ($l=1,\dots,k$), $w\in\bR^{d_{k}}$, and $b_{k+1}\in\bR$. The weight matrices $W_{1},\dots,W_{k},w$ are initialized with $\cN(0,I)$ and the biases $b_{1},\dots,b_{k+1}$ are initialized with zero, where $\cN(0,I)$ is the multivariate standard normal distribution. The activation function is chosen to be the ReLU function $\sigma(x)\triangleq\max\{x,0\}$.

Geifman et al. and Bietti and Mairal presented the following recursive relations of the NTK $N_{k}(x,y)$ of the above ReLU network (1):

where $\kappa_{0}$ and $\kappa_{1}$ are the arc-cosine kernels of degree 0 and 1 given by

The NTKs defined in and are slightly different. There is no bias term $\beta^{2}$ in , while the bias term appears in . We adopt the more general setup with the bias term.

$\Sigma_{k}(x,x)=1$ for any $x\in\bS^{d-1}$ and $k\geq 0$.

where $\kappa_{1}^{(k)}(u)\triangleq\underbrace{\kappa_{1}(\kappa_{1}(\cdots\kappa_{1}(\kappa_{1}}_{k}(u))\cdots))$ is the $k$-th iterate of $\kappa_{1}(u)$. For example, $\kappa_{1}^{(0)}(u)=u$, $\kappa_{1}^{(1)}(u)=\kappa_{1}(u)$ and $\kappa_{1}^{(2)}(u)=\kappa_{1}(\kappa_{1}(u))$. We present a detailed derivation of (4) in Section A.2.

Results on Neural Tangent Kernel

In this section, we present an overview of our proof for Theorem 1. Since showed $\cH_{\textnormal{Lap}}(\bS^{d-1})\subseteq\cH_{N_{k}}(\bS^{d-1})$, it suffices to prove the reverse inclusion $\cH_{N_{k}}(\bS^{d-1})\subseteq\cH_{\textnormal{Lap}}(\bS^{d-1})$. We then relate positive definite kernels with their RKHS according to the following lemma.

Let $K_{1},K_{2}:\Omega\times\Omega\to\bC$ be two positive definite kernels. Then the Hilbert space $\cH_{K_{1}}$ is a subset of $\cH_{K_{2}}$ if and only if there exists some constant $\gamma>0$ such that

Lemma 4 implies that in order to show $\cH_{N_{k}}(\bS^{d-1})\subseteq\cH_{\textnormal{Lap}}(\bS^{d-1})$, it suffices to show $\gamma^{2}K_{\textnormal{Lap}}-N_{k}$ is a positive definite kernel for some $\gamma>0$. Note that both $K_{\textnormal{Lap}}$ and $N_{k}$ are positive definite kernels on the unit sphere. Then the Maclaurin series of $K_{\textnormal{Lap}}(u)$ and $N_{k}(u)$ have all non-negative coefficients by the classical approximation theory; see [28, Theorem 2], , and [13, Chapter 17]. Conversely, if the Maclaurin series of $K(u)$ have all non-negative coefficients, $K(x,y)=K(x^{\top}y)$ is a positive definite kernel on the unit sphere. To be precise, we have the following lemma.

Suppose that $K(x,y)=f(x^{\top}y)$ where $x,y\in\bS^{d-1}$ and $f$ is continuous on $$.When$x$and$y$live on the unit sphere (i.e.,$x^{\top}x=y^{\top}y=1$), their inner product$x^{\top}y$can be any real number in$$. Then$K$is a positive definite kernel on$\bS^{d-1}$for every$d$if and only if$f(u)=\sum_{k=0}^{\infty}a_{k}u^{k}$, in which$a_{k}\geq 0$and$\sum_{k=0}^{\infty}a_{k}<\infty$.

Thus, we turn to show that there exists $\gamma>0$ such that $\gamma^{2}[z^{n}]K_{\textnormal{Lap}}(z)\geq[z^{n}]N_{k}(z)$ holds for every $n\geq 0$.

Exact calculation of the asymptotic rate of the Maclaurin coefficients is intractable for $N_{k}$ due to its recursive definition. Instead, we apply singularity analysis tools in analytic combinatorics. We refer the readers to for a systematic introduction. We treat all (zonal) kernels, $K_{\textnormal{Lap}}(u)$, $N_{k}(u)$, $\kappa_{0}(u)$, and $\kappa_{1}(u)$, as complex functions of variable $u\in\bC$. To emphasize, we use $z\in\bC$ instead of $u$ to 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 , we introduce some additional definitions. For $R>1$ and $\phi\in(0,\pi/2)$, the $\Delta$-domain $\Delta(\phi,R)$ is defined by

For a complex number $\zeta\not=0$, a $\Delta$-domain at $\zeta$ is the image by the mapping $z\mapsto\zeta z$ of $\Delta(\phi,R)$ for some $R>1$ and $\phi\in(0,\pi/2)$. A function is $\Delta$-analytic at $\zeta$ if it is analytic on a $\Delta$-domain at $\zeta$.

Suppose the function $f(z)$ has only one dominant singularity and without loss of generality assume that it lies at $z=1$. We then have the following lemma.

If $f$ is $\Delta$-analytic at its dominant singularity $1$ and

with $\alpha\notin\{0,-1,-2,\dots\}$, we have

If the function has multiple dominant singularities, the influence of each singularity is added up (See [19, Theorem VI.5] for more details). Careful singularity analysis then gives

for some positive constants $C_{1},C_{2}>0$. We refer to Section 3.2 and Section A.4 for more detailed steps. They are indeed of the same order of decay rate $n^{-3/2}$, which implies that such $\gamma$ exists. This shows $\cH_{N_{k}}(\bS^{d-1})\subseteq\cH_{\textnormal{Lap}}(\bS^{d-1})$.

We present the $\Delta$-analyticity of the NTKs here. In light of (4), the NTKs $N_{k}$ are compositions of arc-cosine kernels $\kappa_{0}$ and $\kappa_{1}$. We analytically extend $\kappa_{0}$ and $\kappa_{1}$ to a complex function of a complex variable $z\in\bC$. Both complex functions $\arccos(z)$ and $\sqrt{1-z^{2}}$ have branch points at $z=\pm 1$. Therefore, the branch cut of $\kappa_{0}(z)$ and $\kappa_{1}(z)$ is $[1,\infty)\cup(-\infty,-1]$. They have a single-valued analytic branch on

where we use the principal value of the logarithm and square root. We then show the dominant singularities of $\kappa_{1}^{(k)}(z)$ are $\pm 1$ and that $\kappa_{1}^{(k)}(z)$ is $\Delta$-analytic at $\pm 1$ for any $k\geq 1$. We further have the following theorem on the $\Delta$-singularity for $N_{k}$.

For each $k\geq 1$, the dominant singularities of $N_{k}$ are $\pm 1$. There exists $R_{k}>1$ such that $N_{k}$ is analytic on $\{z\in\bC~{}|~{}|z|\leq R_{k}\}\cap D$, where $D=\bC\setminus[1,\infty)\setminus(-\infty,-1]$.

The following theorem demonstrates the asymptotic rates of Maclaurin coefficients for $N_{k}$.

The $n$-th order coefficient of the Maclaurin series of the $(k+1)$-layer NTK in (2) satisfies $[z^{n}]N_{k}(z)=O(n^{-3/2})$.

In the proof of Theorem 8, we show the following asymptotics

When $\beta=1$, the singularity at $z=-1$ will not provide a $\sqrt{1+z}$ term. The dominating term in (7) is a higher power of $\sqrt{1+z}$. As a result, the contribution of the singularity at $-1$ to the Maclaurin coefficients is $o(n^{-3/2})$ and dominated by the contribution of the singularity at $1$. The singularity at $z=1$ provides a $\sqrt{1-z}$ term and thus contributes to $O(n^{-3/2})$ decay rate of $[z^{n}]N_{k}(z)$. In addition, from (6), we deduce

When $\beta\neq 1$, both singularities $\pm 1$ contribute $\Theta(n^{-3/2})$ to the Maclaurin cofficients. The contribution of $z=1$ is

Based on Theorem 8, we are ready to prove Theorem 1.

Let $K_{\textnormal{Lap}}(z)=e^{-c\sqrt{1-z}}$, where $c>0$ is an arbitrary constant. We have $\cH_{K_{\textnormal{Lap}}}=\cH_{\textnormal{Lap}}$. The complex function $K_{\textnormal{Lap}}$ is analytic on $\bC\setminus[1,\infty)$. As $z\to 1$, we have

Note that $[z^{n}]N_{k}(z)=O(n^{-3/2})$ from Theorem 8. Therefore, there exists $\gamma>0$ such that $\gamma^{2}\cdot[z^{n}]K_{\textnormal{Lap}}(z)-[z^{n}]N_{k}(z)>0$ for all $n\geq 0$. This further implies $\gamma^{2}K_{\textnormal{Lap}}(x^{\top}y)-N_{k}(x^{\top}y)$ is a positive definite kernel. According to Lemma 4, we have $\cH_{N_{k}}(\bS^{d-1})\subseteq\cH_{\textnormal{Lap}}(\bS^{d-1})$. Note that, due to [20, Theorem 3], we also have $\cH_{\textnormal{Lap}}(\bS^{d-1})\subseteq\cH_{N_{k}}(\bS^{d-1})$. Therefore, for any $k\geq 1$, $\cH_{\textnormal{Lap}}(\bS^{d-1})=\cH_{N_{k}}(\bS^{d-1})$.

Results on Exponential Power Kernel

This section presents the proof of Theorem 2. We first show part (1) below by singularity analysis.

Recall that the exponential power kernel restricted to the unit sphere with $\gamma>0$ and $\sigma>0$ is given by $K_{\textnormal{exp}}^{\gamma,\sigma}(x,y)=\exp\left(-\frac{\|x-y\|^{\gamma}}{\sigma}\right)=\exp\left(-\frac{(2(1-x^{\top}y))^{\gamma/2}}{\sigma}\right)$. Let us study the decay rate of the Maclaurin coefficients of $K_{\textnormal{exp}}^{\gamma,\sigma}(z)\triangleq e^{-c(1-z)^{\gamma/2}}$, where $c=2^{\gamma/2}/\sigma$. The dominant singularity lies at $z=1$. As $z\to 1$, we get

Applying Lemma 6 gives $[z^{n}]K_{\textnormal{exp}}^{\gamma,\sigma}(z)\sim\frac{cn^{-\gamma/2-1}}{-\Gamma(-\gamma/2)}$. Therefore, a smaller $\gamma$ results in a larger RKHS. ∎

Part (2) of Theorem 2 requires more technical preparation. Recall that $\mathscr{L}$ and $\mathscr{L}^{-1}$ denote the Laplace transform and inverse Laplace transform, respectively. We explicitly calculate the inverse Laplace transform $\mathscr{L}^{-1}\{\exp(-s^{a})\}(t)$ using Bromwich contour integral and get the following lemma.

For $a\in(0,1)$, $f(t)\triangleq\mathscr{L}^{-1}\{\exp(-s^{a})\}(t)$ exists. Moreover, $f(t)$ is continuous in $-\infty<t<\infty$ and satisfies $f(0)=0$. If $t>0$, we have

Based on the series representation (11), we then analyze the asymptotic rate for $f(t)$ when $a$ is rational. Note that if $a\in(0,1)$, we have $-\frac{1}{\Gamma(-a)}>0$.

Let $f(t)$ be as defined in Lemma 9. For $a=\frac{p}{q}\in(0,1)$ ($p$ and $q$ are co-prime), we have $f(t)\sim-\frac{1}{t^{a+1}\Gamma(-a)}$ as $t\to+\infty$.

Thus, We have the following corollary for general exponential power kernel.

For $a=\frac{p}{q}\in(0,1)$ ($p$ and $q$ are co-prime) and $\sigma>0$, $\mathscr{L}^{-1}\{\exp(-s^{a}/\sigma)\}(t)$ is continuous in $t\in\bR$ and satisfies $\mathscr{L}^{-1}\{\exp(-s^{a}/\sigma)\}(0)=0$. Moreover, $\mathscr{L}^{-1}\{\exp(-s^{a}/\sigma)\}(t)\sim Ct^{-a-1}$ as $t\to+\infty$, for some constant $C>0$.

Use the property $\mathscr{L}^{-1}\{F(cs)\}(t)=\frac{1}{c}f\left(\frac{t}{c}\right)$, where $c>0$ and $F(s)=\mathscr{L}\{f(t)\}(s)$. ∎

Before completing the proof for part (2), we need two additional lemmas from the classical approximation theory. Recall that a function $f(t)$ is completely monotone if it is continuous on $[0,\infty)$, infinitely differentiable on $(0,\infty)$ and satisfies $(-1)^{n}\frac{d^{n}f(t)}{dt}\geq 0$ for every $n=0,1,2,\dots$ and $t>0$ [13, Chapter 14].

If $f$ is completely monotone but not constant on $[0,\infty)$, then for any $n$ distinct points $x_{1},x_{2},\dots,x_{n}$ in any inner-product space, the matrix $A_{ij}=f(\|x_{i}-x_{j}\|^{2})$ is positive definite.

A function $f:[0,\infty)\to[0,\infty)$ is completely monotone if and only if there is a nondecreasing bounded function $g$ such that $f(t)=\int_{0}^{\infty}e^{-st}dg(s)$.

By Lemma 12 and Lemma 4, we need to show that

is completely monotone but not constant on $[0,\infty)$ for some $c>0$. By Lemma 13, it suffices to check that (12) is the Laplace transform of a non-negative function on $[0,\infty)$. By 11, for rational $\gamma_{1},\gamma_{2}\in(0,1]$, there exists $c>0$ such that

is continuous and positive on $[0,\infty)$, which completes the proof. ∎

Numerical Results

We verify the asymptotics of the Maclaurin coefficients of the Laplace kernel and NTKs through numerical results.

Fig. 1 plots $\frac{[z^{n}]K(z)}{n^{-3/2}}$ versus $n$ for different kernels, including the Laplace kernel $K_{\textnormal{Lap}}(u)=e^{-\sqrt{2(1-u)}}$ and NTKs $N_{1},\dots,N_{4}$ with $\beta=0,1$. All curves converge to a constant as $n\to\infty$, which indicates that for every kernel $K(z)$ considered here, we have $[z^{n}]K(z)=\Theta(n^{-3/2})$. The numerical results agree with our theory in the proofs of Theorem 8 and Theorem 1.

Now we investigate the value of $[z^{n}]K(z)/n^{-3/2}$. Table 1 reports $[z^{100}]K(z)/100^{-3/2}$ for the Laplace kernel and NTKs with $\beta=0,1$. These numerical values are the final values of the curves in Fig. 1. The theoretical predictions are obtained through the asymptotic of $[z^{n}]K(z)/n^{-3/2}$, which we shall explain below. The theoretical prediction of $[z^{100}]N_{4}(z)/100^{-3/2}$ with $\beta=0$ is presented below due to the space limit in the table

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 $n$ (so that the lower order terms become negligible), while $n=100$ is clearly finite. Second, the numerical results for the Maclaurin series are obtained by numerical Taylor expansion and therefore numerical errors could be present.

In what follows, we explain how to obtain the theoretical predictions. First, (10) gives

As a result, the theoretical prediction for $[z^{100}]K_{\textnormal{Lap}}(z)/100^{-3/2}$ is $\frac{1}{2\sqrt{\pi}}$. Now we explain the thereotical predictions for NTKs. When $\beta=1$, the theoretical prediction is given by (8). We present it in the third column of Table 1 for $N_{1},\dots,N_{4}$. When $\beta=0$, we plug $\beta=0$ into (9) and obtain

The above expression (when $n=100$ on the right-hand side) is the theoretical value presented in the fifth column of Table 1 for NTKs.

Discussion

Our result provides further evidence that the NTK is similar to the existing Laplace kernel. However, the following mysteries remain open. First, if 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 $\bS^{d-1}$ and in the entire space $\bR^{d}$? 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 focuses on 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 a clean expression partly because the expectation over the Gaussian process in the general NTK can be computed exactly if the activation function is ReLU (which may not be true for other non-linearities, 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 a variety of machine learning tasks.

Moreover, we show that a less smooth exponential power kernel leads to 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 use the RKHS norm to provide an upper bound for it. We will study its generalization in future work.

We gratefully acknowledge the support of the Simons Institute for the Theory of Computing. We thank Peter Bartlett, Mikhail Belkin, Jason D. Lee, and Iosif Pinelis for helpful discussions and thank Mikhail Belkin and Alexandre Eremenko for introducing to us the works and , respectively.

References

Appendices

We show it by induction. It holds when $k=0$ by the initial condition (3). Assume that it holds for some $k\geq 0$, i.e., $\Sigma_{k}(x,x)=1$. Consider $k+1$. We have

A.2 Proof of Equation (4)

We plug $\Sigma_{k}(x,x)=1$ into (2) and obtain

Recall $\Sigma_{0}(x,y)=u$. By induction, we get

where $\kappa_{1}^{(k)}(u)\triangleq\kappa_{1}^{(k)}(u)=\underbrace{\kappa_{1}(\kappa_{1}(\cdots\kappa_{1}(\kappa_{1}}_{k}(u))\cdots))$ is the $k$-th iterate of $\kappa_{1}(u)$. Then it follows

A.3 Proof of Theorem 7

Lemma 14 and Lemma 15 demonstrate that $\pm 1$ are indeed singularities and analyze the asymptotics for $\kappa_{1}^{(k)}$ as $z$ tends to $\pm 1$, respectively. Our calculation is inspired by Pinelis , which only considers $k=2$.

For every $k\geq 1$, there exists $c_{k}(z)$ such that

We prove by induction on $k$. We first prove the statement for $k=1$. Let $z=1-re^{\mathbf{i}\theta}$. Taylor’s theorem around $1$ with integral form of remainder gives

where $\gamma:\to\bC$ is the simple straight line connecting $1$ and $z$ taking the form $\gamma(t)=1-tre^{\mathbf{i}\theta}$. It follows

Therefore, there exists $c_{1}(z)$ such that $\lim_{z\to 1}c_{1}(z)=\frac{2\sqrt{2}}{3\pi}\neq 0$ and

Next, assume that the desired equation holds for some $k\geq 1$. We then have

where $c_{k+1}(z)\sim c_{k}(z)+c_{1}(k_{1}^{(k)}(z))$. Recall that when $z\to 1$, we have $\kappa_{1}^{(k)}(z)\to 1$ as well. Therefore we deduce

For every $k\geq 1$, there exist $a_{k}\in\bR$ and a complex function $b_{k}(z)$ such that

We prove by induction on $k$. We first prove the statement for $k=1$. Let $z=-1+re^{\mathbf{i}\theta}$. Taylor’s theorem around $-1$ with integral form of remainder gives

where $\gamma:\to\bC$ is the simple straight line connecting $-1$ and $z$ taking the form $\gamma(t)=-1+tre^{\mathbf{i}\theta}$. Similar arguments as in the proof of Lemma 14 give

where $\lim_{z\to-1}b_{1}(z)=\frac{2\sqrt{2}}{3\pi}$.

Next, assume that the desired equation holds for some $k\geq 1$. Define $h_{k}\triangleq\kappa_{1}^{(k)}(-1)$. Since $\kappa_{1}$ is strictly increasing on $$,$\kappa_{1}(-1)=0$and$\kappa_{1}(1)=1$, we have$h_{1}=0$and$h_{k}\in(0,1)$for all$k>1$. Expanding$\kappa_{1}$around$h_{k}$ yields

where $\lim_{z\to h_{k}}p(z)=\kappa_{1}^{\prime}(h_{k})$. It follows that

where $a_{k+1}=h_{k+1}+\kappa_{1}^{\prime}(h_{k})(a_{k}-h_{k})$ and $\lim_{z\to-1}b_{k+1}(z)=\kappa_{1}^{\prime}(h_{k})\lim_{z\to-1}b_{k}(z)$. By induction, we can show that $a_{k}=h_{k}$ for all $k\geq 1$. Since $\kappa_{1}^{\prime}$ is strictly increasing on $$,$\kappa_{1}^{\prime}(-1)=0$, and$\kappa_{1}^{\prime}(1)=1$, we have$\kappa_{1}^{\prime}(h_{k})\geq\kappa_{1}^{\prime}(0)>0$. As a result,

In the sequel, we show that $\pm 1$ are the only dominant singularities of $\kappa_{1}^{(k)}$ and $\kappa_{1}^{(k)}$ is $\Delta$-analytic at $\pm 1$ (Lemma 19).

For any $z\in\bC$ with $\arg z\in(0,\pi/4)$, $\kappa_{1}(z)\in\bH^{+}$. For any $z\in\bC$ with $\arg z\in(-\pi/4,0)$, $\kappa_{1}(z)\in\bH^{-}$.

The second part of the statement follows from the first according to the reflection principle. We only prove the first part here. Let $z=re^{\mathbf{i}\theta}$ with $\theta\in(0,\pi/4)$. Taylor’s theorem with integral form of the remainder and direct calculation give

where $\gamma:\to\bC$ is the simple straight line connecting and $z$ taking the form $\gamma(t)=tre^{\mathbf{i}\theta}$. Then we have

Since $\theta\in(0,\pi/4)$, we have $\arg(1-t^{2}e^{2\mathbf{i}\theta})\in(-\pi,0)$. Further

Noting $\arg(e^{2\mathbf{i}\theta})\in(0,\pi/2)$, we get

which gives a positive imaginary part. Combining with $\Im(1/\pi+z/2)>0$ yields the desired statement. ∎

For every $k\geq 1$ and $\varepsilon>0$, there exists $\delta>0$ such that $\kappa_{1}^{(k)}$ is analytic on $B_{1}(\delta)\cap\bH^{+}$ and $B_{1}(\delta)\cap\bH^{-}$ with

We present the proof for $\bH^{+}$ here and that for $\bH^{-}$ can be shown similarly. We adopt an induction argument on $k$.

For $k=1$, $\kappa_{1}$ is analytic on $\bH^{+}$. Since $\kappa_{1}$ is continuous at $z=1$, for any $\varepsilon>0$, there exists $0<\delta<1/2$ such that

Lemma 16 implies $\kappa_{1}(B_{1}(\delta)\cap\bH^{+})\subseteq\bH^{+}$. Combining them yields

Now assume that the statement holds true for some $k\geq 1$. Note that for any $\varepsilon>0$, there exists $0<\delta<1/2$ such that (14) holds. Then by induction hypothesis, for this chosen $\delta$, there exists $\delta_{1}>0$ such that $\kappa_{1}^{(k)}$ is analytic on $B_{1}(\delta_{1})\cap\bH^{+}$ and

$|\kappa_{1}(z)|\leq 1$ for any $|z|\leq 1$, where the equality holds if and only if $z=1$.

The Taylor series of $\kappa_{1}$ around $z=0$ is

The equality holds if and only if $z=1$. ∎

For each $k\geq 1$, there exists $R>1$ such that $\kappa_{1}^{(k)}$ is analytic on $\{z\in\bC~{}|~{}|z|\leq R\}\cap D$, where $D=\bC\setminus[1,\infty)\setminus(-\infty,-1]$.

For any $0<\theta<\pi/2$, there exists $\delta_{\theta}>0$ such that for all $|z|\leq 1$ with $|\arg z|\geq\theta$, we have

To see this, we use an argument similar to . If we define $\phi\triangleq\arg z$, we have

for some $\delta_{\theta}>0$. Consider the Taylor series of $\kappa_{1}$ around $z=0$

Lemma 17 shows that there exists $0<\delta^{\prime}<1$ such that $\kappa_{1}^{(k)}$ is analytic on $B_{1}(\delta^{\prime})\cap D$. From the argument above, we know that $\kappa_{1}$ maps $A\triangleq\{z\in\bC\mid|z|=1,|\arg z|\geq\theta\}$ to inside of the open unit ball $B_{0}(1)$. Since $A$ is compact and Lemma 18 implies that $g$ maps $B_{0}(1)$ to $B_{0}(1)$, there exists $1<R_{\theta}<1+\delta^{\prime}$ such that $\kappa_{1}$ maps

to $B_{0}(1)$. It follows that $\kappa_{1}^{(k)}$ is analytic on $A_{\theta}$. Let us pick $\theta\in(0,\pi/2)$ such that $e^{\mathbf{i}\theta}\in B_{1}(\delta^{\prime})$. Then we conclude that $\kappa_{1}^{(k)}$ is analytic on $\{z\in\bC\mid|z|\leq R_{\theta}\}\cap D$. ∎

Since $\kappa_{0}$ and $\kappa_{1}$ are both analytic on $D=\bC\setminus[1,\infty)\setminus(-\infty,-1]$, similar arguments as in the proof of Lemma 19 shows that $\kappa_{0}(\kappa_{1}^{(k)}(z))$ is analytic on $\{z\in\bC\mid|z|\leq R\}\cap D$ for all $k\geq 1$ and some $R>1$. We then show, for any $k\geq 1$, there exists some $R_{k}>1$ such that $N_{k}(z)$ is analytic on $\{z\in\bC\mid|z|\leq R_{k}\}\cap D$ by induction. The function $N_{0}(z)=z+\beta^{2}$ is analytic on $D$. Assume $N_{k-1}(z)$ is analytic on $\{z\in\bC\mid|z|\leq R_{k-1}\}\cap D$ for some $R_{k-1}>1$. Recall that

Then we can find some $R_{k}>1$ such that $N_{k}(z)$ is analytic on $\{z\in\bC\mid|z|\leq R_{k}\}\cap D$. ∎

A.4 Proof of Theorem 8

We first analyze the behavior of $N_{k}(z)$ as $z\to 1$ for any $k\geq 1$. We aim to show, for any $k\geq 1$, there exists a sequence of complex functions $p_{k}(z)$ with $\lim_{z\to 1}p_{k}(z)=-\sqrt{2}(1+\beta^{2})k(k+1)/2\pi$ such that

The fundamental theorem of calculus then gives for any $z\in D$

where $\gamma:\to\bC$ is the simple straight line connecting $1$ and $z$. As $z\to 1$, we have $\frac{1}{\sqrt{1-z^{2}}}\sim\frac{1}{\sqrt{2}\sqrt{1-z}}$. Therefore, similar arguments as in the proof of Lemma 14 give

where $\lim_{z\to 1}h(z)=-\frac{\sqrt{2}}{\pi}$. Combining with Lemma 14 further gives, for any $k\geq 1$

where $\lim_{z\to 1}h_{k}(z)=-\frac{\sqrt{2}}{\pi}$. For $k=1$, we then have

where $\lim_{z\to 1}d_{1}(z)=\frac{2\sqrt{2}}{3\pi}$ and $\lim_{z\to 1}p_{1}(z)=-\sqrt{2}(1+\beta^{2})/\pi$. Assume $N_{k-1}(z)=k(z+\beta^{2})+p_{k-1}(z)\sqrt{1-z}$ with $\lim_{z\to 1}p_{k-1}(z)=-\sqrt{2}(1+\beta^{2})k(k-1)/(2\pi)$. We further have

where we set $p_{k}(z)=p_{k-1}(z)+k\cdot h_{k-1}(z)(z+\beta^{2})$ and $d_{k}(z)\to\frac{2\sqrt{2}k}{3\pi}$, $h_{k-1}(z)\to-\frac{\sqrt{2}}{\pi}$ as $z\to 1$. Moreover, we have

Next we study the behavior of $N_{k}(z)$ as $z\to-1$ for any $k\geq 1$. We aim to show, for any $k\geq 1$, there exists a sequence of complex functions $q_{k}(z)$ with $\lim_{z\to-1}q_{k}(z)=\sqrt{2}(\beta^{2}-1)\prod_{j=1}^{k-1}\kappa_{0}(a_{j})/\pi$ and $a_{k}\triangleq\kappa_{1}^{(k)}(-1)$ as defined in Lemma 15 such that

We again adopt induction on $k$. Taylor’s theorem gives

where $\lim_{z\to a_{k}}r_{k}(z)=\kappa^{\prime}_{0}(a_{k})>0$. Combining with Lemma 15 further gives, for any $k\geq 1$

where $\gamma:\to\bC$ is the simple straight line connecting $-1$ and $z$. As $z\to-1$, we have $\frac{1}{\sqrt{1-z^{2}}}\sim\frac{1}{\sqrt{2}\sqrt{1+z}}$. Therefore, similar arguments as in the proof of Lemma 14 give

where $g(z)\to\frac{\sqrt{2}}{\pi}$ as $z\to-1$. We then have

where $N_{1}(-1)=a_{1}+\beta^{2}$ $\lim_{z\to-1}q_{1}(z)=\frac{\sqrt{2}}{\pi}(\beta^{2}-1)$. Assume $N_{k-1}(z)=N_{k-1}(-1)+q_{k-1}(z)\sqrt{1+z}$ with $\lim_{z\to-1}q_{k-1}(z)=\sqrt{2}(\beta^{2}-1)\prod_{j=1}^{k-2}\kappa_{0}(a_{j})/\pi$. We further have

where we use the induction assumption in the fourth equation, use the fact $N_{k}(-1)=a_{k}+\beta^{2}+N_{k-1}(-1)\kappa_{0}(a_{k-1})$ in the fifth equation and define

Finally, according to Theorem 7, combining (15) and (16), applying [19, Theorem VI.5] with $\rho=1$, $r=2$, $\tau(z)=(1-z)^{1/2}$, $\zeta_{1}=1$, $\zeta_{2}=-1$, $\sigma_{1}(z)=(k+1)(z+\beta^{2})$, $\sigma_{2}(z)=N_{k}(-1)$, $\bfD=\{z\in\bC\mid|z|\leq R_{k}\}\cap D$, we conclude $[z^{n}]N_{k}(z)=O(n^{-3/2})$. ∎