On the Similarity between the Laplace and Neural Tangent Kernels

Introduction

Neural networks with significantly more parameters than training examples have been successfully applied to a variety of tasks. Somewhat contrary to common wisdom, these models typically generalize well to unseen data. It has been shown that in the limit of infinite model size, these neural networks are equivalent to kernel regression using a family of novel Neural Tangent Kernels (NTK) . NTK methods can be analyzed to explain many properties of neural networks in this limit, including their convergence in training and ability to generalize . Recent experimental work has shown that in practice, kernel methods using NTK perform similarly, and in some cases better, than neural networks , and that NTK can be used to accurately predict the dynamics of neural networks . This suggests that a better understanding of NTK can lead to new ways to analyze neural networks.

These results raise an important question: Is NTK significantly different from standard kernels? For the case of fully connected (FC) networks, provides experimental evidence that NTK is especially effective, showing that it outperforms the Gaussian kernel on a large suite of machine learning problems. Consequently, they argue that NTK should be added to the standard machine learning toolbox. has shown empirically that the dynamics of neural networks on randomly labeled data more closely resembles the dynamics of learning through stochastic gradient descent with the Laplace kernel than with the Gaussian kernel. In this paper we show theoretically and experimentally that NTK does closely resemble the Laplace kernel, already a standard tool of machine learning.

Related Works

The connection between neural networks and kernel methods has been investigated for over two decades. Early works have noted the equivalence between neural networks with single hidden layers of infinite width and Gaussian Processes (GP) , where GP prior can be used to achieve exact Bayesian inference. Recently have extended the results to deep fully-connected neural networks in which all but the last layer retain their initial values. In this context, introduced the Arc-cosine kernel, while showed a duality between neural networks and compositional kernels.

More recent work introduced the family of neural tangent kernels (NTK) . This work showed that for massively overparameterized and fully trained networks, their training dynamics closely follows the path of kernel gradient descent, and that training converges to the solution of kernel regression with NTK. Follow-up work defined analogous kernels for residual and convolutional networks . Recent work also showed empirically that classification with NTK achieves performance similar to deep neural networks with the corresponding architecture .

The equivalence between kernels and overparameterized neural networks opened the door to studying inductive bias in neural networks. For two layer, FC networks, investigated the spectral property of the NTK when the data is distributed uniformly on the hypersphere, showing in particular that with GD low frequencies are learned before higher ones. extended these results to non-uniform distributions. analyzed the eigenvalues of NTK over the Boolean cube, and analyzed its spectrum under approximate pairwise orthogonality. further leveraged the spectral properties of the kernels to investigate their RKHS in the case of bias-free two layer networks. Our results apply to deep networks with bias. studied approximation bounds for two layer neural networks, and studied generalization properties of kernel methods in the context of neural networks.

Recent work compares the performance of NTK to that of common kernels. Specifically, ’s experiments suggest that NTK is superior to the Gaussian and low degree polynomial kernels. compares the learning speed of GD for randomly mislabeled data, showing that NTK learns such data as fast as the Laplace kernel and much faster than the Gaussian kernel. Our analysis provides a theoretical justification of this result.

NTK vs. the Exponential Kernels

Our aim is to compare NTK to common kernels. In comparing kernels we need to consider two main properties: first, what functions are included in their respective RKHS and secondly, how their respective norms behave. (These concepts are reviewed below in Sec. 3.1.) The answer to the former question determines the set of functions considered for regression, while the answer to the latter determines the result of regression. Together, these will determine how a kernel generalizes to unseen data points. Below we see that on the hypersphere both NTK and exponential kernels (e.g., Gaussian and Laplace) give rise to the same set of eigenfunctions. Therefore, the answers to the questions above are determined fully by the corresponding eigenvalues. Moreover, the asymptotic decay rate of the eigenvalues of each kernel determines their RKHS.

For all $x\in\mathcal{X}$ we have that the $\boldsymbol{k}(\cdot,x)\in\mathcal{H}$.

Reproducing property: for all $x\in\mathcal{X}$ and for all $f\in\mathcal{H}$ it holds that $f(x)=\langle f,\boldsymbol{k}(\cdot,x)\rangle_{\mathcal{H}}$.

Moreover, RKHSs and positive definite kernels are uniquely paired.

According to Mercer’s theorem $\boldsymbol{k}$ can be written as

where $\{(\lambda_{i},\Phi_{i})\}_{i\in I}$ are the eigenvalues and eigenfunctions of $\boldsymbol{k}$ with respect to the measure $\mathcal{V}$, i.e.,

The RKHS ${\mathcal{H}}$ is the space of functions $f\in{\mathcal{H}}$ of the form $f(\mathbf{x})=\sum_{i\in I}\alpha_{i}\Phi_{i}(\mathbf{x})$ whose RKHS norm is finite, i.e., $\|f\|_{\mathcal{H}}=\sum_{i\in I}\frac{\alpha_{i}^{2}}{\lambda_{i}}<\infty$. The latter condition restricts the set of functions in an RKHS, allowing only functions that are sufficiently smooth in accordance with the asymptotic decay of $\lambda_{k}$.

Neural Tangent Kernel. Let $f(\theta,\mathbf{x})$ denote a neural network function with ReLU activation and trainable parameters $\theta$. Then the corresponding NTK is defined as

When $\lambda\rightarrow 0$ this problem is called minimum norm interpolant, and the solution satisfies

Deriving the eigenvalues for NTK for deep networks is complicated, due to its recursive definition. For a two-layer network without bias, proved that the eigenvalues decay at a rate of $O(k^{-d})$. With no bias, however, two-layer networks are nonuniversal, and in particular $\lambda_{k}=0$ for odd $k\geq 3$ . To avoid this issue Theorem 1 establishes that with bias NTK is universal for any number of layers $L\geq 2$, and its eigenvalues decay at a rate no faster than $O(k^{-d})$. Moreover, with $L=2$ the eigenvalues decay exactly at the rate of $O(k^{-d})$.

$\exists k_{0}$ and constants $C_{1},C_{2},C_{3}>0$ that depend on the dimension $d$ such that $\forall k>k_{0}$

$C_{1}k^{-d}\leq\lambda_{k}\leq C_{2}k^{-d}$ if $L=2$, and

$C_{3}k^{-d}\leq\lambda_{k}$ if $L\geq 3$.

The proof of this theorem for $L=2$ borrows techniques from . The proof for $L\geq 3$ relies mainly on showing that the algebraic operations in the recursive definition of NTK (including addition, product and composition) do not increase the rate of decay. The consequence of Theorem 1 is that NTK for FC networks gives rise to an infinite size feature space and that its eigenvalues decay no faster than $O(k^{-d})$. While our proofs only establish a bound for the case that $L\geq 3$, empirical results suggest that the eigenvalues for these kernels decay exactly as $\Theta(k^{-d})$, as can be seen in Figure 1.

shows that the Gaussian kernel restricted to the hypersphere yields eigenvalues that decay exponentially fast. In contrast we next prove that the eigenvalues of the Laplace kernel restricted to the hypersphere decay polynomially as $\Theta(k^{-d})$, the same decay rate shown for NTK in Theorem 1 and in Figure 1.

where $B_{1},B_{2}>0$ are constants that depend on the dimension $d$ and the parameter $c$.

Likewise, with $n$ training points and $f\in{\mathcal{H}}_{\boldsymbol{k}}$, derived the following lower bound

where $\alpha_{i}$ are the eigenvalues of $f$. Both of these bounds are equivalent asymptotically up to a constant for NTK (with bias) and the Laplace kernel.

While theoretical discussions of NTK largely assume the input data is normalized to lie on the sphere, such normalization is not the common practice in neural network applications. Instead, most often each feature is normalized separately by setting its mean to zero and variance to 1. Other normalizations are also common. It is therefore important to examine how NTK behaves outside of the hypersphere, compared to common kernels.

Below we derive the eigenfunctions of NTK for deep FC networks with ReLU activation with and without bias. We note that derived the eigenfunctions of NTK for two-layer FC networks with no bias. We will show that the same eigenfunctions are obtained with deep, bias-free networks, and that additional eigenfunctions appear when bias is added. We begin with a definition.

A kernel $\boldsymbol{k}$ is homogeneous of order $\alpha$ if $\boldsymbol{k}(\mathbf{x},\mathbf{z})=\|\mathbf{x}\|^{\alpha}\|\mathbf{z}\|^{\alpha}\boldsymbol{k}\left(\frac{\mathbf{x}^{T}\mathbf{z}}{\|\mathbf{x}\|\|\mathbf{z}\|}\right)$.

Let $\boldsymbol{k}(\mathbf{x},\mathbf{z})=\boldsymbol{k}_{0}(\mathbf{x},\mathbf{z})$ + $\boldsymbol{k}_{1}(\mathbf{x},\mathbf{z})$ so that $\boldsymbol{k}_{0}$ as in 1 and $\boldsymbol{k}_{1}$ is homogeneous of order 0. Then the eigenfunctions of $\boldsymbol{k}$ are of the form $\Psi_{k,j}=\left(a\left\lVert\mathbf{x}\right\rVert+b\right)Y_{k,j}\left(\frac{\mathbf{x}}{\|\mathbf{x}\|}\right)$.

In contrast to NTK, the Laplace kernel is shift invariant, and therefore its eigenfunctions are the Fourier transform. The two kernels hence cannot be compared merely by their eigenvalues. Figure 2 shows the eigenfunctions of NTK along with their correlation to the eigenfunctions of the Laplace kernel. While these differences are large, they seem to make only little difference in experiments, see Section 4 below. It is possible to produce a homogeneous version of the Laplace kernel as follows

Following Thm. 5 the eigenfunctions of this kernel are the scaled spherical harmonics and, following Thm. 2, its eigenvalues decay at the rate of $k^{-d}$, much like the NTK.

Experiments

We compare the performance of NTK with Laplace, Gaussian, and $\gamma$-exponential kernels on both small and large scale real datasets. Our goal is to demonstrate: a) Results with the Laplace kernel are quite similar to those obtained by NTK, and b) The $\gamma$-exponential kernel can achieve slightly better results than NTK. Experimental details are provided in the supplementary material.

We compare methods using the same set of 90 small scale UCI datasets (with less than 5000 data points) as in . The results are provided in Table 4 for the exponential kernels and their homogeneous versions, denoted by the "H-" prefix, as well as for NTK. For completeness, we also cite the results for Random forest (RF), the top classifier identified in , and neural networks from . Further comparison of the accuracies obtained with NTK vs. the H-Laplace kernel on each of the 90 datasets is shown in Figure 4.

We report the same metrics as used in : Friedman Ranking, Average Accuracy, P90/P95, and PMA. A superior classifier is expected to have lower Friedman rank and higher P90, P95, and PMA. Friedman Ranking reports the average ranking of a given classifier compared to other classifiers. P90/P95 denotes the fraction of datasets on which a classifier achieves more than $90/95\%$ of the maximum achievable accuracy (i.e., maximum accuracy among all the classifiers ). PMA represents the percentage of maximum accuracy.

From Table 4, one can observe that the H-Laplace kernel results are the closest to NTK on all the metrics. In fact, as seen in Figure 4, these methods seem to achieve highly similar accuracies in each of the 90 datasets. Furthermore, the H-$\gamma$-exponential outperforms all the classifiers including NTK on all metrics. Moreover, the homogeneous versions slightly outperform the standard kernels. All these methods have hyperparameters that can be optimized. In , they search $105$ hyperparameters for NTK. For a fair comparison, we search for the same number for the $\gamma$-exponential and fewer (70) for the Laplace kernels. We note finally that deeper networks yield NTK shapes that are more sharply peaked, corresponding to Laplace kernels with higher values of $c$. This is shown in Fig. 5 below.

2 Large scale datasets

We leverage FALKON , an efficient approximate kernel method to conduct large scale regression and classification tasks following the setup of . The results and datasets details are reported in Table 1. We searched for hyperparameters based on a small validation dataset for all the methods and used the standard train/test partition provided on the UCI repository. From Table 1, one can notice that NTK and H-Laplace perform similarly. For each dataset, either the $\gamma$-exponential or Gaussian kernels slightly outperforms these two kernels.

3 Hierarchical convolutional kernels

Convolutional NTKs (CNTK) were shown to express the limit of convolutional neural networks when the number of channels tends to infinity, and recent empirical results showed that the two achieve similar accuracy on test data . CNTK is defined roughly by recursively applying NTK to image patches. For our final experiment we constructed alternative hierarchical kernels, in the spirit of , by recursively applying exponential kernels in a manner similar to CNTK. The new kernel, denoted C-Exp, is applied first to pairs of $3\times 3$ image patches, then to $3\times 3$ patches of kernel values, and so forth. A detailed algorithm is provided in the supplementary material. We applied the kernel (using the homogeneous versions of the Laplace, Gaussian and $\gamma$-exponential kernels) to the Cifar-10 dataset and compared it to CNTK. Our experimental conditions and results for CNTK are identical to those of . (Note that these do not include global average pooling.) Consistent with our previous experiments, Table 2 shows that these kernels are on par with the CNTK with small advantage to the $\gamma$-exponential kernel. This demonstrates that the four kernels maintain similar performance even after repeated application.

Conclusions

Our paper has considered the relationship between NTK and the classic Laplace kernel. Our main result is to show that for data normalized on the unit hypersphere, these two kernels have the same RKHS. Experiments show that the two kernels perform almost identically on a wide range of real-world applications. Coupled with prior results that show that kernel methods using NTK mimic the behavior of FC neural networks, our results suggest that much insight about neural networks can be obtained from analysis of the well-known Laplace kernel, which has a simple closed form.

Neural networks do offer great flexibility not easily translated to kernel methods. They can naturally be applied to large data sets, and researchers have developed many techniques for training them, such as dropout and batch normalization, that improve performance but do not directly translate to kernel methods. Furthermore, while we study feed-forward fully connected networks, analyzing more complex architectures, such as CNNs, GANs, autoencoders and recurrent networks, or the effect of other activation functions, remains a significant challenge for future work. Comparing the eigenfunctions of NTK with those of classical kernels under non-uniform distribution is yet a further challenge.

Broader impact

This work explains the success of deep, fully connected networks through their similarity to exponential kernels. Such an analysis may allow for a better interpretability of deep network models.

Acknowledgements

The authors thank the U.S.- Israel Binational Science Foundation, grant number 2018680, the National Science Foundation, grant no. IIS-1910132, the Quantifying Ensemble Diversity for Robust Machine Learning (QED for RML) program from DARPA and the Guaranteeing AI Robustness Against Deception (GARD) program from DARPA for their support of this project.

References

Appendix A Formulas for NTK

We begin by providing the recursive definition of NTK for fully connected (FC) networks with bias initialized at zero. The formulation includes a parameter $\beta$ that when set to zero the recursive formula coincides with the formula given in for bias-free networks.

The recursive formula for NTK.

The recursive formula in assumes the bias is initialized with a normal distribution. Here we assume the bias is initialized at zero, yielding a sightly different formulation, which can be readily derived from ’s formulation.

By definition $|\lambda^{(h-1)}|\leq 1$, and for ReLU activation we have $c_{\sigma}=2$ and

To prove the next theorem, we recall several results on the the arithmetics of RKHS, following .

Aronszajn’s kernel sum theorem. The RKHS for $\boldsymbol{k}=\boldsymbol{k}_{1}+\boldsymbol{k}_{2}$ is given by ${\mathcal{H}}_{\boldsymbol{k}_{1}+\boldsymbol{k}_{2}}=\{f_{1}+f_{2}~{}|~{}f_{1}\in{\mathcal{H}}_{\boldsymbol{k}_{1}},~{}f_{2}\in{\mathcal{H}}_{\boldsymbol{k}_{2}}\}$

This yields the kernel sum inclusion. ${\mathcal{H}}_{\boldsymbol{k}_{1}},{\mathcal{H}}_{\boldsymbol{k}_{2}}\subseteq{\mathcal{H}}_{\boldsymbol{k}_{1}+\boldsymbol{k}_{2}}$

Norm addition inequality. $\left\lVert f_{1}+f_{2}\right\rVert_{{\mathcal{H}}_{\boldsymbol{k}_{1}+\boldsymbol{k}_{2}}}\leq\left\lVert f_{1}\right\rVert_{{\mathcal{H}}_{\boldsymbol{k}_{1}}}+\left\lVert f_{2}\right\rVert_{{\mathcal{H}}_{\boldsymbol{k}_{2}}}$

Norm product inequality. $\left\lVert f_{1}\cdot f_{2}\right\rVert_{{\mathcal{H}}_{\boldsymbol{k}_{1}\cdot\boldsymbol{k}_{2}}}\leq\left\lVert f_{1}\right\rVert_{{\mathcal{H}}_{\boldsymbol{k}_{1}}}\cdot\left\lVert f_{2}\right\rVert_{{\mathcal{H}}_{\boldsymbol{k}_{2}}}$

Aronszajn’s inclusion theorem. ${\mathcal{H}}_{\boldsymbol{k}_{1}}\subseteq{\mathcal{H}}_{\boldsymbol{k}_{2}}$ if and only if $\exists s>0$, such that $\boldsymbol{k}_{1}\ll s^{2}\boldsymbol{k}_{2}$, where the latter notation means that $s^{2}\boldsymbol{k}_{2}-\boldsymbol{k}_{1}$ is a positive definite kernel over $\mathcal{X}$.

B.2 The decay rate of the eigenvalues of NTK

$\exists k_{0}$ and constants $C_{1},C_{2},C_{3}>0$ that depend on the dimension $d$ such that $\forall k>k_{0}$

$C_{1}k^{-d}\leq\lambda_{k}\leq C_{2}k^{-d}$ if $L=2$, and

$C_{3}k^{-d}\leq\lambda_{k}$ if $L\geq 3$.

We split the theorem into the next two lemmas. The first lemma handles NTK of two-layer FC networks with bias, and the second lemma handles NTK for deep networks.

where $C_{1},C_{2}>0$ are constants that depend on the dimension $d$.

Furthermore, according to Proposition 5 in

To conclude, this implies that $\exists k_{0},C_{1}(d)>0$ and $C_{2}(d)>0$, such that for all $k\geq k_{0}$ it holds that

and also, unless $\beta=0$, for all $k\geq 0$

$\exists k_{0}$ such that $\forall k>k_{0}$ it holds that $C_{3}k^{-d}\leq\lambda_{k}$ in which $C_{3}>0$ depends on the dimension $d$

Now, following Lemma 17 in all of the eigenvalues of $\dot{\Sigma}^{(l)}$ are positive, including $\lambda_{0}>0$. This implies that the constant function $g(\mathbf{x})\equiv 1\in{\mathcal{H}}_{\dot{\Sigma}^{(l)}}$.

and for $k\rightarrow\infty$ it holds that

where $c>0$ is a tuning parameter. We next prove an asymptotic bound on its eigenvalues.

where $B_{1},B_{2}>0$ are constants that depend on the dimension $d$ and the parameter $c$.

Our proof relies on several supporting lemmas.

( Thm 1.14 page 6) For all $\alpha>0$ it holds that

where $c_{d}=\Gamma(\frac{d+1}{2})/(\pi^{(d+1)/2})$

To calculate the Fourier transform we need to calculate the following integral

According to the Lemma 5, plugging $\alpha=\frac{c}{2\pi}$ and $\mathbf{t}=\frac{\mathbf{w}}{2\pi}$ into (15) yields

Then, the eigenvalues in the spherical harmonic expansion $\lambda_{k}$ are related to the Fourier coefficients of $f$, $\Phi(t)$, as follows

where $J_{v}(t)$ is the usual Bessel function of the first kind of order $v$.

Having, these supporting Lemmas, we can now prove Theorem 7.

First, $\boldsymbol{k}(\cdot,\cdot)$ is a positive zonal kernel and hence can be written as

Next, to derive the bounds we plug the Fourier coefficients, $\Phi(\omega)$, computed in Lemma 6, into the expression for the harmonic coefficients, $\lambda_{k}$ (16), obtaining

Applying a change of variables $t=cx$ we get

We next bound this integral from both above and below. To get an upper bound we observe that for $x\in[0,\infty)$ $x^{2}<1+x^{2}$, implying that $x(1+x^{2})^{-(d+1)/2}<x^{-d}$, and consequently

The above integral $A(k,d,c)$ was computed in (Sec. 13.41 page 402 with $a:=c$, $\lambda:=d$, and $\mu=\nu:=k+(d-2)/2$) which gives

Using Stirling’s formula $\Gamma(x)=\sqrt{2\pi}x^{x-1/2}e^{-x}(1+O(x^{-1}))$ as $x\rightarrow\infty$. Consequently, for sufficiently large $k>>d$

where $B_{2}$ depends on $c$, $C$ and the dimension $d$.

We use again the relation (17) to derive a lower bound for $\lambda_{k}$. First, note that since $t,1+t^{2},J^{2}_{v}(t)$ are all non-negative for $t\in[0,\infty)$ and therefore

Applying Stirling’s formula we obtain $B(k,d,c)\leq O\left(\frac{(\frac{ce}{2})^{2(k+\frac{d}{2})}(k+d)}{(k+\frac{d}{2})^{2(k+\frac{d}{2})}}\right)$, which implies that as $k$ grows, $\frac{B(k,d,c)}{A(k,d,c)}\rightarrow 0$. Therefore, asymptotically for large $k$

from which we conclude that $\lambda_{k}>B_{1}k^{-d}$, where the constant $B_{1}$ depends on $c$, $C$, and $d$. We have therefore shown that there exists $k_{0}$ such that $\forall k>k_{0}$

Finally, to show that $\lambda_{k}>0$ for all $k\geq 0$ we use again (16) in Lemma 7 which states that

Note that in the interval $(0,\infty)$ it holds that $t>0$ and $\Phi(t)>0$ due to Lemma 6. Therefore $\lambda_{k}=0$ implies that $J^{2}_{k+\frac{d-2}{2}}(t)$ is identically 0 on $(0,\infty)$, contradicting the properties of the Bessel function of the first kind. Hence, $\lambda_{k}>0$ for all $k$. ∎

In this section we denote $r_{x}=\left\lVert\mathbf{x}\right\rVert$, $r_{z}=\left\lVert\mathbf{z}\right\rVert$ and by $\hat{\mathbf{x}}=\mathbf{x}/r_{x}$, $\hat{\mathbf{z}}=\mathbf{z}/r_{z}$. We first prove Theorem 9 and as a consequence Lemma 8 is proved.

To that end, we first prove the following supporting Lemma.

Assuming the induction hypothesis holds for $l$, i.e.,

we prove that those equalities are also true for $l+1$.

By the definition of $\lambda^{(l)}$ (7) and the induction hypothesis for $\Sigma^{(l)}$ we have that

Plugging this result in the definitions of $\Sigma$ (8) and $\dot{\Sigma}$ (9), using the induction hypothesis we obtain

Finally, using the recursion formula (6) ($\beta=0$) and the induction hypothesis for $\Theta^{(l)}$, we obtain

Let $\boldsymbol{k}(\mathbf{x},\mathbf{z})=\boldsymbol{k}_{0}(\mathbf{x},\mathbf{z})$ + $\boldsymbol{k}_{1}(\mathbf{x},\mathbf{z})$ so that $\boldsymbol{k}_{0}$ as in 1 and $\boldsymbol{k}_{1}$ is homogeneous of order 0. Then the eigenfunctions of $\boldsymbol{k}$ are of the form $\Psi_{k,j}=\left(ar_{x}+b\right)Y_{k,j}\left(\hat{\mathbf{x}}\right)$.

Since $\hat{\boldsymbol{k}}_{0}$ is zonal, its Mercer’s representation reads

where the spherical harmonics $Y_{k,j}$ are the eigenfunctions of $\hat{\boldsymbol{k}}_{0}$. Consequently, as noted also in ,

where the rightmost equality is due to the orthogonality of the spherical harmonics and by setting

Clearly this integral is positive, and the conditions of the theorem guarantee that it is finite.

By the conditions of the theorem we can write

where $\bar{Y}_{k}(\hat{\mathbf{x}})$ denote the zonal spherical harmonics. We next show that the space spanned by the functions $r_{x}\bar{Y}_{k}(\mathbf{x})$ and $\bar{Y}_{k}(\mathbf{x})$ is fixed under the following integral transform

We use (21) and (22) to substitute for the inner integral, obtaining

Together with (23), this can be written as

Appendix E Experimental Details

In this section, we provide experimental details for the UCI dataset. We use precisely the same pre-processed datasets, and follow the same performance comparison protocol as in .

We reproduced the results of using the publicly available codehttps://github.com/LeoYu/neural-tangent-kernel-UCI, and followed the same protocol as in . The total number of kernels evaluated in are $15$ and the SVM cost value parameter $\mathbf{C}$ is tuned from $10^{-2}$ to $10^{4}$ by powers of $10$. Hence, the total number of hyper-parameter combinations searched using cross-validation is $105~{}(15\times 7)$.

Exponential Kernels Specifications

For the Laplace and Gaussian kernels, we searched for $10$ kernel width values ($1/c$) from $2^{-2}\times\nu$ to $\nu$ in the log space with base $2$, where $\nu$ is chosen heuristically as the median of pairwise $l_{2}$ distances between data points (known as the median trick ). So, the total number of kernel evaluations is $10$. For $\gamma$-exponential, we searched through 5 equally spaced values of $\gamma$ from $0.5$ to $2$. Since we wanted to keep the number of the kernel evaluations the same as for NTK in , we searched through only three kernel bandwidth values ($1/c$) which are $1$, $\nu$ and #features (default value in the sklearn packagehttps://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.rbf_kernel.html). So, the total number of kernel evaluations is $15~{}(5\times 3)$.

For a fair comparison with , we swept the same range of SVM cost value parameter $\mathbf{C}$ as in , i.e., from $10^{-2}$ to $10^{4}$ by powers of $10$. Hence, the total number of hyper-parameter search using cross-validation is $70~{}(10\times 7)$ for Laplace and $105~{}(15\times 7)$ for $\gamma$-exponential which is the same as for NTK in .

E.2 Large scale datasets

We used the experimental setup mentioned in and the publicly available code https://github.com/LCSL/FALKON_paper. solves kernel ridge regression (KRR ) using the FALKON algorithm, which solves the following linear system

where $K$ is an $n\times n$ kernel matrix defined by $(K)_{ij}=K(x_{i},x_{j})$, $\hat{\mathbf{y}}=(y_{1},\dots y_{n})^{T}$, and $\lambda$ is the regularization parameter. Refer to for more details.

In Table 3, we provide the hyper parameters chosen with cross validation.

E.3 C-Exp: Convolutional Exponential Kernels

Let $\mathbf{x}=(x_{1},...,x_{d})^{T}$ and $\mathbf{z}=(z_{1},...,z_{d})^{T}$ denote two vectorized images. Let $P$ denote a window function (we used $3\times 3$ windows). Our hierarchical exponential kernels are defined by $\bar{\Theta}(\mathbf{x},\mathbf{z})$ as follows:

where $\beta\geq 0$ denotes the bias and the last step is analogous to a fully connected layer in networks, and we set

where $\boldsymbol{k}$ can be any kernel defined on the sphere. In the experiments we applied this scheme to the three exponential kernels, Laplace, Gaussian and $\gamma$-exponential.

C-Exp Laplace. $L=3,\beta=3$, $\boldsymbol{k}(\mathbf{x}^{T}\mathbf{z})=a+be^{-c\sqrt{2-2\mathbf{x}^{T}\mathbf{z}}}$ with $a=-11.491,b=12.606,c=0.048$.

C-Exp $\gamma-$exponential. $L=8,\beta=3$, $\boldsymbol{k}(\mathbf{x}^{T}\mathbf{z})=a+be^{-c(2-2\mathbf{x}^{T}\mathbf{z})^{\gamma/2}}$ with $a=-0.276,b=1.236,c=0.424,\gamma=1.888$.

C-Exp Gaussian. $L=12,\beta=3$, $\boldsymbol{k}(\mathbf{x}^{T}\mathbf{z})=a+be^{-c(2-2\mathbf{x}^{T}\mathbf{z})}$ with $a=-0.22,b=1.166,c=0.435$.

For the training phase we used 1-hot vectors from which we subtracted 0.1, as in . For the classification phase, as in , we normalized the kernel matrices such that all the diagonal elements are ones. To avoid ill conditioned kernel matrices we applied ridge regression with a regularization factor of $\lambda=5\cdot 10^{-5}$. Finally, to reduce overall running times, we parallelized the kernel computations on NVIDIA Tesla V100 GPUs.