Scaling Neural Tangent Kernels via Sketching and Random Features

Introduction

Recent results have shown that over-parameterized Deep Neural Networks (DNNs), generalize surprisingly well. In an effort to understand this phenomena, researchers have studied ultra-wide DNNs and shown that in the infinite width limit, a fully connected DNN trained by gradient descent under least-squares loss is equivalent to kernel regression with respect to the Neural Tangent Kernel (NTK) . This connection has shed light on DNNs’ ability to generalize and optimize (train) their parameters efficiently . More recently, Arora et al. proved an analogous equivalence between convolutional DNNs with infinite number of channels and Convolutional NTK (CNTK). Beyond the aforementioned theoretical purposes, several papers have explored the algorithmic use of this kernel. Arora et al. and Geifman et al. showed that NTK based kernel models can outperform trained DNNs (of finite width). Additionally, CNTK kernel regression sets an impressive performance record on CIFAR-10 for kernel methods without trainable kernels . The NTK has also been used in experimental design and predicting training time .

There is a rich literature on kernel approximations for large-scale learning. One of the most popular approaches is the random features method which works by randomly sampling the feature space of the kernel function, originally due to the seminal work of Rahimi and Recht . Another popular approach which is developed in linear sketching literature , works by designing sketches that can be efficiently applied to the feature space of a kernel without needing to explicitly form the high dimensional feature space. This approach has been successful at designing efficient subspace embeddings for the polynomial kernel . In this paper, we propose solutions for scaling the NTK and CNTK by building on both of these kernel approximations techniques and designing efficient feature maps that approximate the NTK/CNTK evaluation. Consequently, we can simply transform the input dataset to these feature spaces, and then apply fast linear learning methods to approximate the answer of the corresponding nonlinear kernel method efficiently. The performance of such approximate methods is similar or sometimes better than the exact kernel methods due to implicit regularization effects of the approximation algorithms .

One of our results is an efficient random features construction for the NTK. Our starting point is the explicit NTK feature map suggested by Bietti and Mairal based on tensor product of the feature maps of arc-cosine kernels. We obtain our random features, by sampling the feature space of arc-cosine kernels . However, the naïve construction of the features would incur an exponential cost in the depth of the NTK, due to the tensor product of features generated in consecutive layers. We remedy this issue, by utilizing an efficient sketching algorithm for tensor products known as TensorSRHT which can effectively approximate the tensor products of vectors while preserving their inner products. We provide a rigorous error analysis of the proposed scheme in Theorem 2.

Our next results are sketching methods for both NTK and CNTK using a runtime that is linearly proportional to the sparsity of the input dataset (or number of pixels of images). Our methods rely on the arc-cosine kernels’ feature space defined by their Taylor expansion. By careful truncation of their Taylor series, we approximate the arc-cosine kernels with bounded-degree polynomial kernels. Because the feature space of a polynomial kernel is the tensor product of its input space, its dimensionality is exponential in the degree of the kernel. Fortunately, Ahle et al. have developed a linear sketch known as PolySketch that can reduce the dimensionality of high-degree tensor products very efficiently, therefore, we can sketch the resulting polynomial kernels using this technique. We then combine the transformed features from consecutive layers by further sketching their tensor products. In case of CNTK, we have an extra operation which sketches the direct sum of the features of neighbouring pixels at each layer that precisely corresponds to the convolution operation in CNNs. We carefully analyze the errors introduced by polynomial approximations and various sketching steps in our algorithms and also bound their runtimes in Theorems 1 and 4.

Furthermore, we improve the arc-cosine random features to spectrally approximate the entire kernel matrix, which is advocated in recent literature for ensuring high approximation quality in downstream tasks . Our construction is based on leverage score sampling, which entertains better convergence bounds . However, computing this distribution is as expensive as solving the kernel methods exactly. We propose a simple distribution that tightly upper bounds the leverage scores of arc-cosine kernels and for further efficiency, use Gibbs sampling to generate random features from our proposed distribution. We provide our spectral approximation guarantee in Theorem 3.

Finally, we empirically benchmark our proposed methods on various classification/regression tasks and demonstrate that our methods perform similar to or better than exact kernel method with NTK and CNTK while running extremely faster. In particular, we classify CIFAR-10 dataset 150$\times$ faster than exact CNTK and at the same time achieve higher test accuracy.

2 Related Works

There has been a long line of work on the correspondence between DNN and kernel machines . Furthermore, there has been many efforts in understanding a variety of NTK properties including optimization , generalization , loss surface , etc.

A popular line of work on kernel approximation problem is based on the Fourier features method , which works well for shift-invariant kernels and with some modifications can embed the Gaussian kernel near optimally . Other random feature constructions have been suggested for a variety of kernels, e.g., arc-cosine kernels , polynomial kernels . In linear sketching literature, Avron et al. proposed a subspace embedding for the polynomial kernel which was recently extended to general dot product kernels . The runtime of this method, while nearly linear in sparsity of the input dataset, scales exponentially in kernel’s degree. Recently, Ahle et al. improved this exponential dependence to polynomial which enabled them to sketch high-degree polynomial kernels and led to near-optimal embeddings for Gaussian kernel. In fact, this sketching technology constitutes one of the main ingredients of our proposed methods. Additionally, combining sketching with leverage score sampling can improve the runtime of the polynomial kernel embeddings .

3 Preliminaries: PolySketch and TensorSRHT Transforms

ReLU Neural Tangent Kernel

Let $\kappa_{0}(\alpha)$ and $\kappa_{1}(\alpha)$ be $0^{th}$ and $1^{st}$ order arc-cosine kernels defined as follows,

The connection between ReLU-NTK function $K_{\tt relu}^{(L)}$ and the NTK kernel $\Theta_{\tt ntk}^{(L)}$ is formalized bellow,

Sketching and Random Features for NTK

The main results of this section are efficient oblivious sketching as well as random features for the fully-connected NTK. As shown in ?? and ??, the NTK $\Theta_{\tt ntk}^{(L)}$, is constructed by recursive composition of arc-cosine kernels $\kappa_{1}(\cdot)$ and $\kappa_{0}(\cdot)$. So, to design efficient sketches for the NTK we crucially need efficient methods for approximating these functions. Generally, there are two main approaches to approximating these functions; one is random features sampling and the other is truncated Taylor series expansion coupled with fast sketching. We design algorithms by exploiting both of these techniques.

Our main tool is approximating the arc-cosine kernels with low-degree polynomials, and then applying PolySketch to the resulting polynomial kernels. The features for multi-layer NTK are the recursive tensor product of arc-cosine sketches at consecutive layers, which in turn can be sketched efficiently using PolySketch. We present our oblivious sketch in ??.

Now we present our main theorem on NTKSketch algorithm as follows.

For a proof, see ??. One can observe that the runtime of our NTKSketch is faster than the gradient features of an ultra-wide random DNN, studied by Arora et al. , by a factor of $L^{3}/\varepsilon^{2}$.

2 NTK Random Features

The proof of ?? is provided in ??. Arora et al. proved that the gradient of randomly initialized ReLU network with finite width can approximate the NTK, but their feature dimension should be $\Omega\left(\frac{L^{13}}{\varepsilon^{8}}\log^{2}\frac{L}{\delta}+\frac{L^{6}}{\varepsilon^{4}}\cdot\log\frac{L}{\delta}\cdot d\right)$ which is larger than ours by a factor of $\frac{L^{7}}{\varepsilon^{4}}\log\frac{L}{\delta}$. In ??, we also empirically show that ?? requires far fewer features than random gradients.

3 Spectral Approximation for NTK via Leverage Scores Sampling

Although the above NTK approximations can estimate the kernel function itself, it is still questionable how it affects the performance of downstream tasks. Several works on kernel approximation adopt spectral approximation bound with regularization $\lambda>0$ and approximation factor $\varepsilon>0$, that is,

where $\bm{\Psi}^{(L)}:=\left[\Psi^{(L)}(x_{1}),\dots,\Psi^{(L)}(x_{n})\right]$ and $[{\bm{K}}^{(L)}_{\tt ntk}]_{i,j}=\Theta_{\tt ntk}^{(L)}(x_{i},x_{j})$. The spectral bound can provide rigorous guarantees for downstream applications including kernel ridge regression , clustering and PCA . We first provide spectral bounds for arc-cosine kernels, then we present our spectral approximation bound for two-layer ReLU networks, which is the first in the literature.

To guarantee that the arc-cosine random features in ?? provide spectral approximation, we will use the leverage score sampling framework of . We reduce the variance of random features by performing importance sampling. The challenge is to find a proper modified distribution that certainly reduces the variance. It turns out that the original $0^{th}$ order arc-cosine random features has a small enough variance. More precisely, let ${\bm{K}}_{0}$ be the $0^{th}$ order arc-cosine kernel matrix, i.e., $[{\bm{K}}_{0}]_{i,j}=\kappa_{0}\left(\frac{\langle x_{i},x_{j}\rangle}{\|x_{i}\|_{2}\|x_{j}\|_{2}}\right)$, and $\bm{\Phi}_{0}:=\left[\Phi_{0}(x_{1}),\ldots,\Phi_{0}(x_{n})\right]$, where $\Phi_{0}(x)$ is defined in ??. If the number of features $m_{0}\geq\frac{8}{3}\frac{n}{\lambda\varepsilon^{2}}\log\left(\frac{16s_{\lambda}}{\delta}\right)$, then

The details are provided in ?? and ??. We are now ready to state our spectral approximation bound for our modified random features.

For a proof see ??. To generalize the current proof technique to deeper networks, one needs a monotone property of arc-cosine kernels, i.e., $\kappa_{1}({\bm{X}})\preceq\kappa_{1}({\bm{Y}})$ for ${\bm{X}}\preceq{\bm{Y}}$. However, this property does not hold in general and we leave the extension to deeper networks to future work.

Sketching Convolutional Neural Tangent Kernel

Similar to NTKSketch our method relies on approximating the arc-cosine kernels with low-degree polynomials via Taylor expansion, and then applying PolySketch to the resulting polynomial kernels. Our sketch computes the features for each pixel of the input image, by tensor product of arc-cosine sketches at consecutive layers, which in turn can be sketched efficiently using PolySketch . Additionally, the features of pixels that lie in the same patch get locally combined at each layer via direct sum operation. This precisely corresponds to the convolution operation in neural networks. We present our CNTKSketch algorithm in ?? and give its performance guarantee in the following theorem.

The proof is in ??. Runtime of our CNTKSketch is only linear in the number of image pixels $d_{1}d_{2}$, which is in stark contrast to quadratic scaling of the exact CNTK computation .

Experiments

In this section, we empirically show that running least squares regression on the features generated by our methods is extremely fast and effective for learning with NTK and CNTK kernel machines. We run experiments on a system with an Intel E5-2630 CPU with 256 GB RAM and a single GeForce RTX 2080 GPUs with 12 GB RAM. Codes are available at https://github.com/insuhan/ntk-sketch-rf.

We first benchmark our proposed NTK approximation algorithms on MNIST dataset and compare against gradient-based NTK random features (GradRF) as a baseline method. To apply our methods and GradRF into classification task, we encode class labels into one-hot vectors with zero-mean and solve the ridge regression problem. We search the ridge parameter with a random subset of training set and choose the one that achieves the best validation accuracy. We use the ReLU network with depth $L=1$. In ??, we observe that our random features (NTKRF ) achieves the best test accuracy. The NTKSketch narrowly follows the performance of NTKRF and the Grad-RF is the worst method which confirms the observations of Arora et al. , i.e., gradient of a finite width network degrades practical performances.

As shown in ??, the NTK is a normalized dot-product kernel characterized by the function $K^{(L)}_{\tt relu}(\alpha)$. This function can be easily computed using $\mathcal{O}(L)$ operations at any desired $\alpha\in$, therefore, we can efficiently fit a polynomial to this function using numerical methods (for instance, it is shown in ?? that a degree-$8$ polynomial can tightly approximate the depth-$3$ ReLU-NTK function $K_{\tt relu}^{(3)}$). Then, we can efficiently sketch the resulting polynomial kernel using PolySketch , as was previously done for Gaussian and general dot-product kernels . Therefore, we can accelerate our NTKSketch for deeper networks ($L>2$), using this heuristic.

2 CNTK Classification on CIFAR-10

Next we test our CNTKSketch on CIFAR-10 dataset . We choose a convolutional network of depth $L=3$ and compare CNTKSketch and GradRF for various feature dimensions. We borrow results of both CNTK and CNN from Arora et al. . The results are provided in ?? and ??. Somewhat surprisingly, CNTKSketch even performs better than the exact CNTK regression by achieving $72.06\%$ when feature dimension is set to $16{,}384$. The likely explanation is that CNTKSketch takes advantages of implicit regularization effects of approximate feature map and powerful expressiveness of the CNTK. Moreover, computing the CNTK matrix takes over 250 hours (12 days) under our setting which is at least $150\times$ slower than our CNTKSketch.

3 Regression on Large-scale UCI Datasets

Discussion and Conclusion

In this work, we propose efficient low-rank feature maps for the NTK and CNTK kernel matrices based on both sketching and random features. Computing NTK have been raised severe computational problems when they apply to practical applications. Our methods runs remarkably faster than the NTK with performance improvement.

Potential negative societal impact. This is a technical work proposing provable algorithms which stand alone independently of data, e.g., do not learn any private information of input data. We think there is no particular potential negative societal impact due to our work.

Limitations. This paper only considers fully-connected and convolutional neural networks, and our ideas are not directly applicable to scale up NTK of other deep networks, e.g., transformers .

Acknowledgments and Disclosure of Funding

Amir Zandieh was partially supported by the Swiss NSF grant No. P2ELP2_195140. Haim Avron and Neta Shoham were partially supported by BSF grant 2017698 and ISF grant 1272/17. Jinwoo Shin was partially supported by the Engineering Research Center Program through the National Research Foundation of Korea (NRF) funded by the Korean Government MSIT (NRF_2018R1A5A1059921) and Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No.2019_0_00075, Artificial Intelligence Graduate School Program (KAIST)).

References

Appendix A ReLU-NTK Expression

For $h=1,2,\ldots L$, define the derivative covariance as,

Let $\Theta_{\tt ntk}^{(0)}(y,z):=\Sigma^{(0)}(y,z)$ and for every integer $L\geq 1$, the depth-$L$ NTK expression is defined recursively as:

First note that the main component of the DP given in ??, ??, and ?? is the Activation Covariances:

Proof of ??: Consider the NTK expression given in ??, ??, and ??. We first prove by induction on $h=0,1,2,\ldots L$ that the covariance function $\Sigma^{(h)}(y,z)$ defined in ?? satisfies:

The base of induction is trivial for $h=0$ due to $\Sigma^{(0)}(y,z)=\langle y,z\rangle=\|y\|_{2}\|z\|_{2}\cdot\Sigma_{\tt relu}^{(0)}\left(\frac{\langle y,z\rangle}{\|y\|_{2}\|z\|_{2}}\right)$.

To prove the inductive step, suppose that the inductive hypothesis holds for $h-1$, i.e.,

Using a similar argument we have $\|g\|_{2}^{2}=\|z\|_{2}^{2}$. Therefore, by ??, we can write

Since we assumed that $\Lambda^{(h)}(y,z)=\begin{pmatrix}f^{\top}\\ g^{\top}\end{pmatrix}\cdot\begin{pmatrix}f&g\end{pmatrix}$, we have $\langle f,g\rangle=\Sigma^{(h-1)}(y,z)$. By inductive hypothesis along with ??, we find that

which completes the induction and proves that for every $h=0,1,\dots,L$,

Since we assumed that $\Lambda^{(h)}(y,z)=\begin{pmatrix}f^{\top}\\ g^{\top}\end{pmatrix}\cdot\begin{pmatrix}f&g\end{pmatrix}$, $\langle f,g\rangle=\Sigma^{(h-1)}(y,z)=\|y\|_{2}\|z\|_{2}\cdot\Sigma_{\tt relu}^{(h-1)}\left(\frac{\langle y,z\rangle}{\|y\|_{2}\|z\|_{2}}\right)$. Therefore, by ??, for every $h\in\{1,2,\dots L\}$,

Now we prove by induction on integer $L$ that the NTK with $L$ layers and ReLU activation given in ?? satisfies

The base of induction, trivially holds because, by ??:

To prove the inductive step, suppose that the inducive hypothesis holds for $L-1$, that is $\Theta_{\tt ntk}^{(L-1)}(y,z)=\|y\|_{2}\|z\|_{2}\cdot K_{\tt relu}^{(L-1)}\left(\frac{\langle y,z\rangle}{\|y\|_{2}\|z\|_{2}}\right)$. Now using the recursive definition of $\Theta_{\tt ntk}^{(L)}(y,z)$ given in ?? along with ?? and ?? we can write,

Appendix B Sketching Preliminaries: PolySketch and SRHT

Our sketching algorithms use the Subsampled Randomized Hadamard Transform (SRHT) to reduce the dimensionality of the intermediate vectors that arise in our computations. Next lemma gives the performance of SRHT sketches which is proved, for instance, in Theorem 9 of ,

Now we restate the ?? and present the proof,

This immediately proves the first statement of the lemma.

As shown in , the sketch ${\bm{Q}}^{p}$ can be applied to tensor product vectors of the form $v_{1}\otimes v_{2}\otimes\ldots v_{p}$ by recursive application of $\mathcal{O}(p)$ independent instances of OSNAP transform and a novel variant of the SRHT , proposed in called TensorSRHT, on vectors $v_{i}$ and their sketched versions. The sketch ${\bm{Q}}^{p}$, as shown in ??, can be represented by a binary tree with $p$ leaves where the leaves are OSNAP sketches and the internal nodes are the TensorSRHT. The use of OSNAP in the leaves of this sketch structure ensures excellent runtime for sketching sparse input vectors. However, note that if the input vectors are not sparse, i.e., ${\rm nnz}(v_{i})=\widetilde{\Omega}(d)$ for input vectors $v_{i}$, then we can simply remove the OSNAP transforms from the leaves of this structure and achieve improved runtime, without hurting the approximation guarantee. Therefore, the sketch ${\bm{Q}}^{p}$ that satisfies the statement of the lemma is exactly the one introduced in for sparse input vectors and for non-sparse inputs is obtained by removing the OSNAP transforms from the leaves of the sketch structure given in ??.

Furthermore, the sketch ${\bm{Q}}^{p}$ can be applied to tensor product of any collection of $p$ vectors. The time to apply ${\bm{Q}}^{p}$ to the tensor product $v_{1}\otimes v_{2}\otimes\ldots v_{p}$ consists of time of applying OSNAP to each of the vectors $v_{1},v_{2}\ldots v_{p}$ and time of applying $\mathcal{O}(p)$ instances of TensorSRHT to intermediate vectors which are of size $m$. This runtime can be upper bounded by $\mathcal{O}\left(\frac{p^{2}\log\frac{p}{\varepsilon}}{\varepsilon^{2}}\log^{3}\frac{1}{\varepsilon\delta}+\frac{p^{3/2}}{\varepsilon}d\cdot\log\frac{1}{\delta}\right)$, which proves the third statement of the ??. ∎

Appendix C NTK Sketch: Claims and Invariants

We start by proving that the polynomials $P_{\tt relu}^{(p)}(\cdot)$ and $\dot{P}_{\tt relu}^{(p^{\prime})}(\cdot)$ defined in ?? of ?? closely approximate the arc-cosine functions $\kappa_{1}(\cdot)$ and $\kappa_{0}(\cdot)$ on the interval $$.

Remark. Observe that $\kappa_{0}(\alpha)=\frac{d}{d\alpha}\left(\kappa_{1}(\alpha)\right)$.

If we let $\kappa_{1}(\cdot)$ and $\kappa_{0}(\cdot)$ be defined as in ?? of ??, then for any integer $p\geq\frac{1}{9\varepsilon^{2/3}}$, the polynomial $P_{\tt relu}^{(p)}(\cdot)$ defined in ?? of ?? satisfies,

Moreover, for any integer $p^{\prime}\geq\frac{1}{26\varepsilon^{2}}$, the polynomial $\dot{P}_{\tt relu}^{(p^{\prime})}(\cdot)$ defined as in ?? of ??, satisfies,

Proof of ??: We start by Taylor series expansion of $\kappa_{0}(\cdot)$ around $\alpha=0$, $\kappa_{0}(\alpha)=\frac{1}{2}+\frac{1}{\pi}\cdot\sum_{i=0}^{\infty}\frac{(2i)!}{2^{2i}\cdot(i!)^{2}\cdot(2i+1)}\cdot\alpha^{2i+1}$. Therefore, we have

To prove the second part of the lemma, we consider the Taylor expansion of $\kappa_{1}(\cdot)$ at $\alpha=0$. Since $\kappa_{0}(\alpha)=\frac{d}{d\alpha}\left(\kappa_{1}(\alpha)\right)$, the Taylor series of $\kappa_{1}(\alpha)$ can be obtained from the Taylor series of $\kappa_{0}(\alpha)$ as follows,

Therefore, it is possible to approximate the function $\kappa_{0}(\cdot)$ up to error $\varepsilon$ using a polynomial of degree $\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\right)$. Also if we want to approximate $\kappa_{1}(\cdot)$ using a polynomial up to error $\varepsilon$ on the interval $$, it suffices to use a polynomial of degree$\mathcal{O}\left(\frac{1}{\varepsilon^{2/3}}\right)$. One can see that since the Taylor expansions of$\kappa_{1}$and$\kappa_{0}$contain non-negative coefficients only, both of these functions are positive definite. Additionally, the polynomial approximations$P_{\tt relu}^{(p)}$and$\dot{P}_{\tt relu}^{(p^{\prime})}$ given in ?? of ?? are positive definite functions.

In order to prove ??, we also need the following lemma on the error sensitivity of polynomials $P_{\tt relu}^{(p)}$ and $\dot{P}_{\tt relu}^{(p^{\prime})}$,

For any integer $p\geq 3$, any $\alpha\in$, and any $\alpha^{\prime}$ such that $|\alpha-\alpha^{\prime}|\leq\frac{1}{6p}$, if we let the polynomials $P_{\tt relu}^{(p)}(\alpha)$ and $\dot{P}_{\tt relu}^{(p)}(\alpha)$ be defined as in ?? of ??, then

Proof of ??: Note that an $\alpha^{\prime}$ that satisfies the preconditions of the lemm, is in the range $\left[-1-\frac{1}{6p},1+\frac{1}{6p}\right]$. Now we bound the derivative of the polynomial $\dot{P}_{\tt relu}^{(p)}$ on the interval $\left[-1-\frac{1}{6p},1+\frac{1}{6p}\right]$,

therefore, the second statement of lemma holds.

To prove the first statement of lemma, we bound the derivative of the polynomial $P_{\tt relu}^{(p)}$ on the interval $\left[-1-\frac{1}{6p},1+\frac{1}{6p}\right]$ as follows,

therefore, the second statement of the lemma follows. This completes the proof of ??. ∎

For the rest of this section, we need two basic properties of tensor products and direct sums:

for vectors $x,y,z,w$ with conforming sizes.

Now we are in a position to analyze the invariants that are maintained throughout the execution of NTKSketch (??):

The mapping $\phi^{(h)}(\cdot)$ computed by NTKSketch in line 4 and ?? of ?? satisfy

The mapping $\psi^{(h)}(\cdot)$ computed by NTKSketch in line 5 and ?? of ?? satisfy

Proof of ??: The proof is by induction on the value of $h=0,1,2,\ldots L$. More formally, consider the following statements for every $h=0,1,2,\ldots L$:

Additionally, by induction, we prove that for every $h=1,2,\ldots L$,

(1) Base of induction ($h=0$): By line 4 of ??, $\phi^{(0)}(y)=\frac{1}{\|y\|_{2}}\cdot{\bm{S}}\cdot{\bm{Q}}^{1}\cdot y$ and $\phi^{(0)}(z)=\frac{1}{\|z\|_{2}}\cdot{\bm{S}}\cdot{\bm{Q}}^{1}\cdot z$, thus, ?? implies the following

By using the above together with ?? and union bound as well as triangle inequality, we have

Using union bound, this proves the base of induction for statement $P_{1}(0)$, i.e.,

Moreover, by line 5 of ??, $\psi^{(0)}(y)={\bm{V}}\cdot\phi^{(0)}(y)$ and $\psi^{(0)}(z)={\bm{V}}\cdot\phi^{(0)}(z)$, thus, ?? implies that,

By conditioning on $P_{1}(0)$ and using the above together with triangle inequality it follows that,

Similarly we can prove that with probability $1-\mathcal{O}\left(\frac{\delta}{L}\right)$ we have $\left|\left\|\psi^{(0)}(y)\right\|_{2}^{2}-K_{\tt relu}^{(0)}(1)\right|\leq\frac{\varepsilon}{10L}$ and $\left|\left\|\psi^{(0)}(z)\right\|_{2}^{2}-K_{\tt relu}^{(0)}(1)\right|\leq\frac{\varepsilon}{10L}$, which proves the base of induction for the second statement, i.e., $\Pr[P_{2}(0)|P_{1}(0)]\geq 1-\mathcal{O}\left({\delta}/{L}\right)$. This completes the base of induction.

(2) Inductive step: Assume that the inductive hypothesis holds for $h-1$. First, note that by ?? and using ?? we have the following,

where $A:=\sqrt{\sum_{j=0}^{2p+2}c_{j}\|Z^{(h)}_{j}(y)\|_{2}^{2}}\cdot\sqrt{\sum_{j=0}^{2p+2}c_{j}\|Z^{(h)}_{j}(z)\|_{2}^{2}}$ and the collection of vectors $\left\{Z^{(h)}_{j}(y)\right\}_{j=0}^{2p+2}$ and $\left\{Z^{(h)}_{j}(z)\right\}_{j=0}^{2p+2}$ and coefficients $\{c_{j}\}_{j=0}^{2p+2}$ are defined as per ?? and ??, respectively.

By ?? together with union bound, the following inequalities simultaneously hold for all $j=0,\dots,2p+2$, with probability at least $1-\mathcal{O}\left(\delta/L\right)$:

Therefore, by plugging ?? to ?? and using union bound, triangle inequality and Cauchy–Schwarz inequality we find that,

where $B:=\sqrt{P^{(p)}_{\tt relu}\left(\|\phi^{(h-1)}(y)\|_{2}^{2}\right)\cdot P^{(p)}_{\tt relu}\left(\|\phi^{(h-1)}(z)\|_{2}^{2}\right)}$ and $P^{(p)}_{\tt relu}(\alpha)=\sum_{j=0}^{2p+2}c_{j}\cdot\alpha^{j}$ is the polynomial defined in ??. Using the inductive hypothesis $P_{1}(h-1)$, we have that

Therefore, by ?? we have $\left|P_{\tt relu}^{(p)}\left(\|\phi^{(h-1)}(y)\|_{2}^{2}\right)-P_{\tt relu}^{(p)}(1)\right|\leq h\cdot\frac{\varepsilon^{2}}{60L^{3}}$ and $\left|P_{\tt relu}^{(p)}\left(\|\phi^{(h-1)}(z)\|_{2}^{2}\right)-P_{\tt relu}^{(p)}(1)\right|\leq h\cdot\frac{\varepsilon^{2}}{60L^{3}}$. Consequently, since $P_{\tt relu}^{(p)}(1)\leq P_{\tt relu}^{(+\infty)}(1)=1$, we obtain that $B\leq\frac{11}{10}.$ By plugging this into ?? we have,

Furthermore, the inductive hypothesis $P_{1}(h-1)$ implies that

By incorporating the above inequality into ?? using triangle inequality we find that,

Now, by invoking ?? and using the fact that $p=\left\lceil 2L^{2}/{\varepsilon}^{4/3}\right\rceil$ we have,

By combining the above inequality with ?? using triangle inequality and using the fact that $\kappa_{1}\left(\Sigma_{\tt relu}^{(h-1)}\left(\frac{\langle y,z\rangle}{\|y\|_{2}\|z\|_{2}}\right)\right)=\Sigma_{\tt relu}^{(h)}\left(\frac{\langle y,z\rangle}{\|y\|_{2}\|z\|_{2}}\right)$ (by ??), we get the following bound,

This is sufficient to prove the inductive step by union bound, i.e., $\Pr[P_{1}(h)|P_{1}(h-1)]\geq 1-\mathcal{O}\left(\frac{\delta}{L}\right)$.

Now we prove the inductive step for statement $P_{2}(h)$, that is, we prove that conditioned on $P_{2}(h-1),P_{1}(h),P_{1}(h-1)$, statement $P_{2}(h)$ holds with probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$. First, note that by ?? and using ?? we have,

where $\widehat{A}:=\sqrt{\sum_{j=0}^{2p^{\prime}+1}b_{j}\|Y^{(h)}_{j}(y)\|_{2}^{2}}\cdot\sqrt{\sum_{j=0}^{2p^{\prime}+1}b_{j}\|Y^{(h)}_{j}(z)\|_{2}^{2}}$ and the collection of vectors $\left\{Y^{(h)}_{j}(y)\right\}_{j=0}^{2p^{\prime}+1}$ and $\left\{Y^{(h)}_{j}(z)\right\}_{j=0}^{2p^{\prime}+1}$ and coefficients $\{b_{j}\}_{j=0}^{2p^{\prime}+1}$ are defined as per ?? and ??, respectively. By invoking ?? along with union bound, with probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$, the following inequalities hold true simultaneously for all $j=0,1,\ldots 2p^{\prime}+1$

Therefore, by plugging ?? into ?? and using union bound, triangle inequality and Cauchy–Schwarz inequality we find that,

where $\widehat{B}:=\sqrt{\dot{P}^{(p^{\prime})}_{\tt relu}\left(\|\phi^{(h-1)}(y)\|_{2}^{2}\right)\cdot\dot{P}^{(p^{\prime})}_{\tt relu}\left(\|\phi^{(h-1)}(z)\|_{2}^{2}\right)}$ and $\dot{P}^{(p^{\prime})}_{\tt relu}(\alpha)=\sum_{j=0}^{2p^{\prime}+1}b_{j}\cdot\alpha^{j}$ is the polynomial defined in ??. By inductive hypothesis $P_{1}(h-1)$ we have $\left|\left\|\phi^{(h-1)}(y)\right\|_{2}^{2}-1\right|\leq h\cdot\frac{\varepsilon^{2}}{60L^{3}}$ and $\left|\left\|\phi^{(h-1)}(z)\right\|_{2}^{2}-1\right|\leq h\cdot\frac{\varepsilon^{2}}{60L^{3}}$. Therefore, using the fact that $p^{\prime}=\left\lceil 9L^{2}/\varepsilon^{2}\right\rceil$ and ??, $\left|\dot{P}_{\tt relu}^{(p^{\prime})}\left(\|\phi^{(h-1)}(y)\|_{2}^{2}\right)-\dot{P}_{\tt relu}^{(p^{\prime})}(1)\right|\leq\frac{h\cdot\varepsilon}{20L^{2}}$ and $\left|\dot{P}_{\tt relu}^{(p^{\prime})}\left(\|\phi^{(h-1)}(z)\|_{2}^{2}\right)-\dot{P}_{\tt relu}^{(p^{\prime})}(1)\right|\leq\frac{h\cdot\varepsilon}{20L^{2}}$. Consequently, since $\dot{P}_{\tt relu}^{(p^{\prime})}(1)\leq\dot{P}_{\tt relu}^{(+\infty)}(1)=1$, we find that $\widehat{B}\leq\frac{11}{10}.$ By plugging this into ?? we have,

Furthermore, inductive hypothesis $P_{1}(h-1)$ implies $\left|\left<\phi^{(h-1)}(y),\phi^{(h-1)}(z)\right>-\Sigma_{\tt relu}^{(h-1)}\left(\frac{\langle y,z\rangle}{\|y\|_{2}\|z\|_{2}}\right)\right|\leq h\cdot\frac{\varepsilon^{2}}{60L^{3}}$, hence, by invoking ?? we find that,

By plugging the above inequality into ?? using triangle inequality, we find that,

Now, by invoking ?? and using the fact that $p^{\prime}=\left\lceil 9L^{2}/{\varepsilon}^{2}\right\rceil$ we have,

By combining the above inequality with ?? using triangle inequality and using the fact that $\kappa_{0}\left(\Sigma_{\tt relu}^{(h-1)}\left(\frac{\langle y,z\rangle}{\|y\|_{2}\|z\|_{2}}\right)\right)=\dot{\Sigma}_{\tt relu}^{(h)}\left(\frac{\langle y,z\rangle}{\|y\|_{2}\|z\|_{2}}\right)$ (by ??), we get the following bound,

Now let $f:=\psi^{(h-1)}(y)\otimes\dot{\phi}^{(h)}(y)$ and $g:=\psi^{(h-1)}(z)\otimes\dot{\phi}^{(h)}(z)$. Then by ?? and using ?? we have the following,

where $D:=\left\|{\bm{Q}}^{2}f\oplus\phi^{(h)}(y)\right\|_{2}\left\|{\bm{Q}}^{2}g\oplus\phi^{(h)}(z)\right\|_{2}$. By the fact that we conditioned on $P_{1}(h)$,

By ??, we can further obtain an upper bound:

Now note that because we conditioned on $P_{2}(h-1)$ and using ??, with probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$ the following holds:

Similarly, $\left\|g\right\|_{2}^{2}\leq\frac{11}{10}h$ with probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$, thus, by union bound:

Therefore, by combining the above with ?? via union bound we find that,

Now note that $\left<{\bm{Q}}^{2}f\oplus\phi^{(h)}(y),{\bm{Q}}^{2}g\oplus\phi^{(h)}(z)\right>=\left<{\bm{Q}}^{2}f,{\bm{Q}}^{2}g\right>+\left<\phi^{(h)}(y),\phi^{(h)}(z)\right>$. We proceed by bounding the term $\left|\left<{\bm{Q}}^{2}f,{\bm{Q}}^{2}g\right>-\left<f,g\right>\right|$ using ??, as follows,

We proved that conditioned on $P_{2}(h-1)$ and $P_{1}(h-1)$, $\left\|f\right\|_{2}^{2}\leq 11h/10$ and $\left\|g\right\|_{2}^{2}\leq 11h/10$ with probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$. Hence, by union bound we find that,

Note that $\left<f,g\right>=\left<\psi^{(h-1)}(y),\psi^{(h-1)}(z)\right>\cdot\left<\dot{\phi}^{(h)}(y),\dot{\phi}^{(h)}(z)\right>$, thus by conditioning on inductive hypothesis $P_{2}(h-1)$ and ?? we have,

By combining the above inequality with ??, $P_{1}(h)$, and ?? using triangle inequality and union bound we get the following inequality,

By noting that $K_{\tt relu}^{(h-1)}\left(\alpha\right)\cdot\dot{\Sigma}_{\tt relu}^{(h)}\left(\alpha\right)+\Sigma_{\tt relu}^{(h)}\left(\alpha\right)=K_{\tt relu}^{(h)}\left(\alpha\right)$ (see ??) we have proved that

Similarly we can prove the following inequalities hold with probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$,

This proves the inductive step for the statement $P_{2}(h)$ follows, i.e.,

Therefore, by union bounding over all $h=0,1,2,\ldots L$, it follows that the statements of the lemma hold simultaneously for all $h$ with probability at least $1-\delta$. This completes the proof of ??. ∎

We now analyze the runtime of the NTKSketch algorithm:

Proof of ??: There are three main components to the runtime of this procedure that we have to account for. The first is the time to apply the sketch ${\bm{Q}}^{1}$ to $x$ in line 4 of ??. By ??, the runtime of computing ${\bm{Q}}^{1}\cdot x$ is $\mathcal{O}\left(\frac{L^{6}}{\varepsilon^{4}}\cdot\log^{3}\frac{L}{\varepsilon\delta}+\frac{L^{3}}{\varepsilon^{2}}\cdot\log\frac{L}{\varepsilon\delta}\cdot{\rm nnz}(x)\right)$. The second heavy operation corresponds to computing vectors $Z_{j}^{(h)}(x)={\bm{Q}}^{2p+2}\cdot\left(\left[\phi^{(h-1)}(x)\right]^{\otimes j}\otimes{e}_{1}^{\otimes 2p+2-j}\right)$ for $j=0,1,2,\ldots 2p+2$ and $h=1,2,\ldots L$ in ??. By ??, the time to compute $Z_{j}^{(h)}(x)$ for a fixed $h$ and all $j=0,1,2,\ldots 2p+2$ is bounded by,

The total time to compute vectors $Z_{j}^{(h)}(x)$ for all $h=1,2,\ldots L$ and all $j=0,1,2,\ldots 2p+2$ is thus $\mathcal{O}\left(\frac{L^{11}}{\varepsilon^{6.7}}\cdot\log^{3}\frac{L}{\varepsilon\delta}\right)$. Finally, the last computationally expensive operation is computing vectors $Y_{j}^{(h)}(x)={\bm{Q}}^{2p^{\prime}+1}\cdot\left(\left[\phi^{(h-1)}(x)\right]^{\otimes j}\otimes{e}_{1}^{\otimes 2p^{\prime}+1-j}\right)$ for $j=0,1,2,\ldots 2p^{\prime}+1$ and $h=1,2,\ldots L$ in ??. By ??, the runtime of computing $Y_{j}^{(h)}(x)$ for a fixed $h$ and all $j=0,1,2,\ldots 2p^{\prime}+1$ is bounded by,

Hence, the total time to compute vectors $Y_{j}^{(h)}(x)$ for all $h=1,2,\ldots L$ and all $j=0,1,2,\ldots 2p^{\prime}+1$ is $\mathcal{O}\left(\frac{L^{9}}{\varepsilon^{6}}\cdot\log^{3}\frac{L}{\varepsilon\delta}\right)$. The total runtime of the NTK Sketch is obtained by summing up these three contributions. This completes the proof of ??. ∎

Now we are ready to prove the main theorem on NTKSketch. See 1

Because ${\bm{G}}$ is a matrix of i.i.d normal entries with $s^{*}=C\cdot\frac{1}{\varepsilon^{2}}\cdot\log\frac{1}{\delta}$ rows, for a large enough constant $C$, ${\bm{G}}$ is a JL transform and hence $\Psi_{\tt ntk}^{(L)}$ satisfies the following,

where $A:={\|y\|_{2}}{\|z\|_{2}}\left\|\psi^{(L)}({y})\right\|_{2}\left\|\psi^{(L)}({z})\right\|_{2}$. By ?? and using the fact that $K_{\tt relu}^{(L)}(1)=L+1$, the following bounds hold with probability at least $1-\mathcal{O}(\delta)$:

Additionally, by ??, the following holds with probability at least $1-\mathcal{O}(\delta)$:

Hence by union bound and triangle inequality we have,

Now note that by ??, ${\|y\|_{2}}{\|z\|_{2}}\cdot K_{\tt relu}^{(L)}\left(\frac{\langle y,z\rangle}{\|y\|_{2}\|z\|_{2}}\right)=\Theta_{\tt ntk}^{(L)}(y,z)$, and also note that for every $L\geq 2$ and any $\alpha\in$, $K_{\tt relu}^{(L)}\left(\alpha\right)\geq(L+1)/9$, therefore,

Remark on the fact that $K_{\tt relu}^{(L)}\left(\alpha\right)\geq(L+1)/9$ for every $L\geq 2$ and any $\alpha\in$. Note that from the definition of $\Sigma_{\tt relu}^{(h)}$ in ??, we have that for any $\alpha\in$: $\Sigma_{\tt relu}^{(0)}(\alpha)\geq-1$, $\Sigma_{\tt relu}^{(1)}(\alpha)\geq 0$, $\Sigma_{\tt relu}^{(2)}(\alpha)\geq\frac{1}{\pi}$, and $\Sigma_{\tt relu}^{(h)}(\alpha)\geq\frac{1}{2}$ for every $h\geq 3$ because $\kappa_{1}(\cdot)$ is a monotonically increasing function on the interval $$. Moreover, using the definition of$\dot{\Sigma}_{\tt relu}^{(h)}$in ??, we have that for any$\alpha\in$:$\dot{\Sigma}_{\tt relu}^{(1)}(\alpha)\geq 0$,$\dot{\Sigma}_{\tt relu}^{(2)}(\alpha)\geq\frac{1}{2}$, and$\dot{\Sigma}_{\tt relu}^{(h)}(\alpha)\geq\frac{3}{5}$for every$h\geq 3$because$\kappa_{0}(\cdot)$is a monotonically increasing function on the interval$$. By an inducive proof and using the definition of$K_{\tt relu}^{(L)}$in ??, we can show that$K_{\tt relu}^{(L)}\left(\alpha\right)\geq(L+1)/9$for every$L\geq 2$and any$\alpha\in$

Runtime analysis: By ??, runtime to compute the NTKSketch is

Appendix D NTK Random Features: Claims and Proofs

In this section we prove ??. We first restate the theorem: See 2

In the proof of this theorem we use the following results from the literature,

and note that $\Delta_{0}=0$. Recall that, by ?? and ??:

We use the recursive relation to approximate:

For notational simplicity, we define the following events:

Our proof is based on the following claims:

First we claim that, there exists a constant $C_{1}>0$ such that for any $m_{1}\geq C_{1}\frac{L^{6}}{\varepsilon^{4}}\log\left(\frac{L}{\delta}\right)$:

which directly follows by invoking ?? with $(x,x^{\prime})\in\left\{\left(\frac{y}{\|y\|_{2}},\frac{z}{\|z\|_{2}}\right),\left(\frac{y}{\|y\|_{2}},\frac{y}{\|y\|_{2}}\right),\left(\frac{z}{\|z\|_{2}},\frac{z}{\|z\|_{2}}\right)\right\}$ and setting $\varepsilon_{1}=\frac{\varepsilon^{2}}{100L^{2}}$ and $\delta_{1}=\frac{\delta}{9L}$ and applying union bound over choices of $(x,x^{\prime})$.

Our second claim is that there exists a constant $C_{0}>0$ such that if $m_{0}\geq C_{0}\frac{L^{2}}{\varepsilon^{2}}\log\left(\frac{L}{\delta}\right)$ then

The above statement is a direct consequence of invoking ?? with $(x,x^{\prime})\in\left\{\left(\frac{y}{\|y\|_{2}},\frac{z}{\|z\|_{2}}\right),\left(\frac{y}{\|y\|_{2}},\frac{y}{\|y\|_{2}}\right),\left(\frac{z}{\|z\|_{2}},\frac{z}{\|z\|_{2}}\right)\right\}$ and union bounding over choices of $(x,x^{\prime})$. In ??, we choose $\varepsilon_{2}=\frac{\varepsilon}{10L},\delta_{2}=\frac{\delta}{9L}$ and $m_{0}\geq\frac{3200L^{2}}{\varepsilon^{2}}\log\left(\frac{54L}{\delta}\right)$ for $\varepsilon,\delta\in(0,1)$ to obtain ?? by union bound.

If the events in ??, ?? and ?? hold, then

When $L\geq 2$, we showed in the proof of ?? that $K_{\tt relu}^{(L)}(\cdot)\geq\frac{L+1}{9}$, therefore,

Since ${\Psi}_{\tt rf}^{(L)}(x)=\|x\|_{2}\cdot{\psi}^{(L)}(x)$ and ${\Psi}_{\tt rf}^{(L)}(x^{\prime})=\|x^{\prime}\|_{2}\cdot{\psi}^{(L)}(x^{\prime})$, this implies that,

D.2 Proof of Auxiliary Claims

See 1 Proof of ??: The proof is based on ?? that provides an upper bound on variance of the PolySketch. By using the definition of $f(x),f(x^{\prime})$ and ??, with probability at least $1-\frac{\delta}{9L}$, we have

Union bounding over the choices of $(x,x^{\prime})$ completes the proof of ??. ∎

Furthermore, the assumption that ?? holds, implies that,

For the third part in ??, we observe that

Appendix E Spectral Approximation via Leverage Scores Sampling

The proofs here rely on Theorem 3.3 in which states spectral approximation bounds of random features for general kernels equipped with the leverage score sampling. This result is a generalization of on the Random Fourier Features.

If $m\geq\frac{8}{3}\varepsilon^{-2}s_{\widetilde{\tau}}\log\left(16s_{\lambda}/\delta\right)$ then

holds with probability at least $1-\delta$.

We now ready to provide spectral approximation guarantee for arc-cosine kernels of order zero.

In order to utilize ??, we need an upper bound of $\tau_{\lambda}(w)$ as below:

E.2 First Order Arc-Cosine Kernels

Now note that by definition of ${\bm{K}}_{1}$, we have $[{\bm{K}}_{1}]_{i,j}=\|x_{i}\|_{2}\|x_{j}\|_{2}\cdot\kappa_{1}\left(\frac{\langle x_{i},x_{j}\rangle}{\|x_{i}\|_{2}\|x_{j}\|_{2}}\right)$. Therefore, using the Taylor expansion of the function $\kappa_{1}(\alpha)=\frac{1}{\pi}+\frac{\alpha}{2}+\frac{1}{\pi}\cdot\sum_{i=0}^{\infty}\frac{(2i)!}{2^{2i}\cdot(i!)^{2}\cdot(2i+1)\cdot(2i+2)}\cdot\alpha^{2i+2}$ and the fact that its Taylor coefficients are all non-negative, we have,

Using the above inequality along with ??, we can write,

To obtain an upper bound of the third term in ??, we consider the singular value decomposition of ${\bm{X}}={\bm{V}}\bm{\Sigma}{\bm{U}}^{\top}$. And we have

Therefore, plugging this into ?? and ?? gives,

and recall that the modified random features are defined as

Putting all together into ??, we derive the result. This completes the proof of ??. ∎

E.3 Proof of ??

Our proof relies on spectral approximation bounds of PolySketch given in the fourth part of ??.

Proof of ??: Note that the NTK of two-layer ReLU network can be formulated as

where ${\bm{K}}_{0}$ and ${\bm{K}}_{1}$ are the arc-cosine kernel matrices of order and $1$ with dataset ${\bm{X}}$, respectively.

Let $\bm{\Phi}_{0}$ and $\bm{\Phi}_{1}$ be the random features of ${\bm{K}}_{0}$ and ${\bm{K}}_{1}$, defined as per ?? and ??, respectively. Also let $\bm{\Psi}_{\tt rf}$ be the feature matrix that ?? outputs, that is each column of this matrix is obtained by applying this algorithm on the dataset ${\bm{X}}$. By basic properties of tensor products we have,

Our proof is a combination of spectral analysis of $\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0},\bm{\Phi}_{1}^{\top}\bm{\Phi}_{1}$ and $\left({\bm{Q}}^{2}\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)\right)^{\top}\cdot{\bm{Q}}^{2}\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)$ which are stated in ??, ?? and ??, respectively.

From ??, if $m_{0}\geq 48\frac{n}{\lambda\varepsilon^{2}}\log\left(\frac{48s_{\lambda}}{\delta}\right)$ then with probability at least $1-\frac{\delta}{3}$ it holds that,

Now we bound the trace of $\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)^{\top}\cdot\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)=\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0}\odot{\bm{X}}^{\top}{\bm{X}}$:

To guarantee spectral approximation of $\left({\bm{Q}}^{2}\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)\right)^{\top}\cdot{\bm{Q}}^{2}\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)$, we will use the result of ??. Using ?? along with ?? and the fact that $m_{s}\geq\frac{C}{\varepsilon^{2}}\cdot\frac{n}{1+\lambda}\log^{3}\frac{n}{\varepsilon\delta}$ for some constant $C$, and union bound, with probability at least $1-\frac{\delta}{2}$, we have

where the inequality in second line follows from ?? and the fourth line follows from the assumption $\left\|{\bm{X}}_{(:,i)}\right\|_{2}\leq 1$ for all $i\in[n]$ which leads that ${\bm{I}}\odot({\bm{X}}^{\top}{\bm{X}})\preceq{\bm{I}}$. The last inequality holds since $\varepsilon\in(0,1/2)$.

Similarly, we can obtain the following lower bound:

Furthermore, by taking a union bound over all events, ?? holds with probability at least $1-\delta$. This completes the proof of ??. ∎

E.4 Auxiliary Lemmas

If ${\bm{A}},{\bm{B}},{\bm{C}}$ are positive semi-definite matrices of conforming sizes such that ${\bm{B}}\preceq{\bm{C}}$, then,

Proof of ??: We want to show that for any vector $v$, $v^{\top}{\bm{A}}\odot{\bm{B}}v\preceq v^{\top}{\bm{A}}\odot{\bm{C}}v$. Because the matrices ${\bm{A}},{\bm{B}},{\bm{C}}$ are PSD, there exist matrices ${\bm{X}},{\bm{Y}},{\bm{Z}}$ of appropriate sizes such that we can decompose these matrices as follows,

Using this and basic properties of tensor products, we have the following for any vector $v$,

Appendix F ReLU-CNTK: Expression and Main Properties

The final CNTK expressions is defined as:

Now we show how to recursively compute the ReLU-CNTK as follows,

For every positive integers $q,L$, the $L$-layer CNTK for ReLU activation function and convolutional filter size of $q\times q$ is defined as follows

The final CNTK expressions for ReLU activation is:

In what follows we prove that the procedure in ?? precisely computes the CNTK kernel function corresponding to ReLU activation and additionally, we present useful corollaries and consequences of this fact.

To prove the inductive step, suppose that the inductive hypothesis $N^{(h-1)}_{i,j}(x)=\Sigma^{(h-2)}_{i,j,i,j}(x,x)$ holds for some $h\geq 2$. Now we show that conditioned on the inductive hypothesis, the inductive claim holds. By ??, we have,

Therefore, this proves that $N^{(h)}_{i,j}(x)\equiv\Sigma^{(h-1)}_{i,j,i,j}(x,x)$ for every $x$ and every integer $h\geq 1$.

where the third line follows from ?? and fourth line follows because we have $\langle f,g\rangle=\Sigma^{(h-1)}_{i,j,i^{\prime},j^{\prime}}(y,z)$. The fifth line above follows from ??. This proves the equivalence between the tensor covariance defined in ?? and the one defined in ?? of ??. Similarly, by using ??, we can prove the statement of the lemma about $\dot{\Gamma}^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)$ as follows,

We describe some of the basic properties of the function $\Gamma^{(h)}(y,z)$ defined in ?? in the following lemma,

Cauchy–Schwarz inequality: $\left|\Gamma_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\right|\leq\frac{\sqrt{N_{i,j}^{(h)}(y)\cdot N_{i^{\prime},j^{\prime}}^{(h)}(z)}}{q^{2}}$.

Norm value: $\Gamma_{i,j,i,j}^{(h)}(y,y)=\frac{N_{i,j}^{(h)}(y)}{q^{2}}\geq 0$.

Proof of ??: We prove the lemma by induction on $h$. The base of induction corresponds to $h=0$. In the base case, by ?? and ?? and Cauchy–Schwarz inequality, we have

This proves the base for the first statement. Additionally we have, $\Gamma_{i,j,i,j}^{(0)}(y,y)=\sum_{l=1}^{c}y_{i,j,l}^{2}=\frac{N^{(0)}_{i,j}(y)}{q^{2}}\geq 0$ which proves the base for the second statement of the lemma. Now, in order to prove the inductive step, suppose that statements of the lemma hold for $h-1$, where $h\geq 1$. Then, conditioned on this, we prove that the lemma holds for $h$. First note that by conditioning on the inductive hypothesis, applying Cauchy–Schwarz inequality, and using the definition of $N^{(h)}$ in ??, we can write

where the second line above follows because of the fact that $\kappa_{1}(\cdot)$ is a monotonically increasing function. This completes the inductive step for the first statement of lemma. Now we prove the inductive step for the second statement as follows,

where we used ?? to conclude that $\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\Gamma^{(h-1)}_{i+a,j+b,i+a,j+b}(y,y)=N^{(h)}_{i,j}(y)$ and then used the fact that $N^{(h)}_{i,j}(y)$ is non-negative. This completes the inductive proof of the lemma. This completes the proof of ??. ∎

We also describe some of the main properties of the function $\dot{\Gamma}^{(h)}(y,z)$ defined in ?? in the following lemma,

Cauchy–Schwarz inequality: $\left|\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\right|\leq\frac{1}{q^{2}}$.