1: Input: ${\bm{X}}\in{\mathbb{R}}^{d\times n}$, feature dimension $m$, Gibbs
iterations $T$

2: Draw i.i.d. $w_{i}\sim\mathcal{N}({\bf 0},{\bm{I}}_{d})$ for $i\in[m]$

3: for $i=1$ to $m$ do

4: $q(x,z)\leftarrow$ inverse of
$\frac{\mathrm{erf}\left({x}/{\sqrt{2}}\right)+1}{2}-\frac{x\exp\left(-x^{2}/2\right)}{\sqrt{2\pi}(z+1)}$
(i.e., CDF of $\Pr([w_{i}]_{j}|[w_{i}]_{\setminus\\{j\\}})$)

5: for $t=1$ to $T$ do

6: for $j=1$ to $d$ do

7: $u\leftarrow$ sample from $[0,1]$ at uniformly random

8: $[w_{i}]_{j}\leftarrow
q\left(u,\sum_{k\in[d]\setminus\\{j\\}}[w_{i}]_{k}^{2}\right)$

9: return
$\sqrt{\frac{2d}{m}}\left[\frac{\mathrm{ReLU}({\bm{X}}^{\top}w_{1})}{\left\|w_{1}\right\|_{2}},\
\dots\
,\frac{\mathrm{ReLU}({\bm{X}}^{\top}w_{m})}{\left\|w_{m}\right\|_{2}}\right]$

###  E.3 Proof of ??

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

See 3

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

$\displaystyle{\bm{K}}_{\tt
ntk}={\bm{K}}_{1}+{\bm{K}}_{0}\odot({\bm{X}}^{\top}{\bm{X}})$ (95)

where ${\bm{K}}_{0}$ and ${\bm{K}}_{1}$ are the arc-cosine kernel matrices of
order $0$ 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,

$\displaystyle\bm{\Psi}_{\tt
rf}:=\bm{\Phi}_{1}\oplus{\bm{Q}}^{2}\cdot\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right).$
(96)

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_{1}\geq\frac{16}{3}\frac{d}{\varepsilon^{2}}\min\left\\{\mathrm{rank}({\bm{X}})^{2},\frac{\left\|{\bm{X}}\right\|_{2}^{2}}{\lambda}\right\\}\log\left(\frac{48s_{\lambda}}{\delta}\right)$
then with probability at least $1-\frac{\delta}{3}$ the following holds,

$\displaystyle(1-\varepsilon)\left({\bm{K}}_{1}+\frac{\lambda}{2}{\bm{I}}\right)\preceq\bm{\Phi}_{1}^{\top}\bm{\Phi}_{1}+\frac{\lambda}{2}{\bm{I}}\preceq(1+\varepsilon)\left({\bm{K}}_{1}+\frac{\lambda}{2}{\bm{I}}\right).$
(97)

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,

$\displaystyle\left(1-\frac{\varepsilon}{3}\right)\left({\bm{K}}_{0}+\frac{\lambda}{2}{\bm{I}}\right)\preceq\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0}+\frac{\lambda}{2}{\bm{I}}\preceq\left(1+\frac{\varepsilon}{3}\right)\left({\bm{K}}_{0}+\frac{\lambda}{2}{\bm{I}}\right)$
(98)

Rearranging ??, we get

$\displaystyle\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0}\preceq\left(1+\frac{\varepsilon}{3}\right){\bm{K}}_{0}+\frac{\varepsilon}{6}\lambda{\bm{I}}.$

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}}$:

$\displaystyle\mathtt{tr}\left(\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0}\odot{\bm{X}}^{\top}{\bm{X}}\right)$
$\displaystyle=\sum_{j\in[n]}[\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0}]_{j,j}\cdot[{\bm{X}}^{\top}X]_{j,j}$
$\displaystyle\leq\sum_{j\in[n]}[\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0}]_{j,j}$
$\displaystyle\leq n.$

Now note that, we can write,

$\displaystyle
s_{\lambda}\left(\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)^{\top}(\bm{\Phi}_{0}\otimes{\bm{X}})\right)\leq\frac{\mathtt{tr}\left(\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0}\odot{\bm{X}}^{\top}{\bm{X}}\right)}{\mathtt{tr}\left(\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0}\odot{\bm{X}}^{\top}{\bm{X}}\right)/n+\lambda}\leq\frac{n}{1+\lambda}.$
(99)

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

$\displaystyle\left({\bm{Q}}^{2}\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)\right)^{\top}{\bm{Q}}^{2}\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)+\frac{\lambda}{2}{\bm{I}}$
$\displaystyle\preceq\left(1+\frac{\varepsilon}{3}\right)\left(\bm{\Phi}_{0}^{\top}\bm{\Phi}_{0}\odot{\bm{X}}^{\top}{\bm{X}}+\frac{\lambda}{2}{\bm{I}}\right)$
$\displaystyle\preceq\left(1+\frac{\varepsilon}{3}\right)\left(\left[\left(1+\frac{\varepsilon}{3}\right){\bm{K}}_{0}+\frac{\varepsilon}{6}\lambda{\bm{I}}\right]\odot{\bm{X}}^{\top}{\bm{X}}+\frac{\lambda}{2}{\bm{I}}\right)$
$\displaystyle=\left(1+\frac{\varepsilon}{3}\right)\left(\left(1+\frac{\varepsilon}{3}\right)\left({\bm{K}}_{0}\odot{\bm{X}}^{\top}{\bm{X}}\right)+\frac{\varepsilon}{6}\lambda({\bm{I}}\odot{\bm{X}}^{\top}{\bm{X}})+\frac{\lambda}{2}{\bm{I}}\right)$
$\displaystyle\preceq\left(1+\frac{\varepsilon}{3}\right)\left(1+\frac{\varepsilon}{3}\right)\left({\bm{K}}_{0}\odot{\bm{X}}^{\top}{\bm{X}}+\frac{\lambda}{2}{\bm{I}}\right)$
$\displaystyle\preceq\left(1+\varepsilon\right)\left({\bm{K}}_{0}\odot{\bm{X}}^{\top}{\bm{X}}+\frac{\lambda}{2}{\bm{I}}\right)$
(100)

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:

$\displaystyle\left({\bm{Q}}^{2}\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)\right)^{\top}{\bm{Q}}^{2}\left(\bm{\Phi}_{0}\otimes{\bm{X}}\right)+\frac{\lambda}{2}{\bm{I}}\succeq\left(1-\varepsilon\right)\left({\bm{K}}_{0}\odot{\bm{X}}^{\top}{\bm{X}}+\frac{\lambda}{2}{\bm{I}}\right).$
(101)

Combining ??, ?? and ?? gives

$\displaystyle(1-\varepsilon)\left({\bm{K}}_{\tt
ntk}+\lambda{\bm{I}}\right)\preceq\bm{\Psi}_{\tt rf}^{\top}\bm{\Psi}_{\tt
rf}+\lambda{\bm{I}}\preceq(1+\varepsilon)\left({\bm{K}}_{\tt
ntk}+\lambda{\bm{I}}\right).$ (102)

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

######  Lemma 9.

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

${\bm{A}}\odot{\bm{B}}\preceq{\bm{A}}\odot{\bm{C}}.$

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,

${\bm{A}}={\bm{X}}^{\top}{\bm{X}},~{}~{}~{}~{}{\bm{B}}={\bm{Y}}^{\top}{\bm{Y}},~{}~{}~{}~{}{\bm{C}}={\bm{Z}}^{\top}{\bm{Z}}.$

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

$\displaystyle v^{\top}{\bm{A}}\odot{\bm{B}}v$
$\displaystyle=\|{\bm{X}}\otimes{\bm{Y}}v\|_{2}^{2}$
$\displaystyle=\|{\bm{X}}\cdot\text{\tt
diag}(v)\cdot{\bm{Y}}^{\top}\|_{F}^{2}$
$\displaystyle=\sum_{i}({\bm{X}}_{(i,:)}\odot
v)^{\top}\cdot{\bm{B}}\cdot({\bm{X}}_{(i,:)}\odot v)$
$\displaystyle\leq\sum_{i}({\bm{X}}_{(i,:)}\odot
v)^{\top}\cdot{\bm{C}}\cdot({\bm{X}}_{(i,:)}\odot v)$
$\displaystyle=v^{\top}{\bm{A}}\odot{\bm{C}}v.$

This completes the proof of ??. ∎

##  Appendix F ReLU-CNTK: Expression and Main Properties

In this section we prove that the depth-$L$ CNTK corresponding to ReLU
activation is highly structured and can be fully characterized in terms of
tensoring and composition of arc-cosine kernel functions $\kappa_{1}(\cdot)$
and $\kappa_{0}(\cdot)$. We refer to this kernel function as ReLU-CNTK. First
we start by restating the DP proposed by Arora et al. [5] for computing the
$L$-layered CNTK kernel corresponding to an arbitrary activation function
$\sigma:\mathbb{R}\to\mathbb{R}$ and convolutional filters of size $q\times
q$, with GAP:

  1. 1.

Let $y,z\in\mathbb{R}^{d_{1}\times d_{2}\times c}$ be two input images, where
$c$ is the number of channels ($c=3$ for RGB images). Define
$\Gamma^{(0)}:\mathbb{R}^{d_{1}\times d_{2}\times
c}\times\mathbb{R}^{d_{1}\times d_{2}\times c}\to\mathbb{R}^{d_{1}\times
d_{2}\times d_{1}\times d_{2}}$ and $\Sigma^{(0)}:\mathbb{R}^{d_{1}\times
d_{2}\times c}\times\mathbb{R}^{d_{1}\times d_{2}\times
c}\to\mathbb{R}^{d_{1}\times d_{2}\times d_{1}\times d_{2}}$ as follows for
every $i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$:

$\begin{split}&\Gamma^{(0)}(y,z):=\sum_{l=1}^{c}y_{(:,:,l)}\otimes
z_{(:,:,l)},\\\
&\Sigma^{(0)}_{i,j,i^{\prime},j^{\prime}}(y,z):=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\Gamma^{(0)}_{i+a,j+b,i^{\prime}+a,j^{\prime}+b}(y,z).\end{split}$
(103)

  2. 2.

For every layer $h=1,2,\ldots,L$ of the network and every
$i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$, define
$\Gamma^{(h)}:\mathbb{R}^{d_{1}\times d_{2}\times
c}\times\mathbb{R}^{d_{1}\times d_{2}\times c}\to\mathbb{R}^{d_{1}\times
d_{2}\times d_{1}\times d_{2}}$ recursively as:

$\begin{split}&\Lambda^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z):=\begin{pmatrix}\Sigma^{(h-1)}_{i,j,i,j}(y,y)&\Sigma^{(h-1)}_{i,j,i^{\prime},j^{\prime}}(y,z)\\\
&\\\
\Sigma^{(h-1)}_{i^{\prime},j^{\prime},i,j}(z,y)&\Sigma^{(h-1)}_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}(z,z)\end{pmatrix},\\\
&\Gamma^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z):=\frac{1}{q^{2}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,1)}\left[|\sigma(w)|^{2}\right]}\cdot\mathbb{E}_{(u,v)\sim\mathcal{N}\left(0,\Lambda^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)\right)}\left[\sigma(u)\cdot\sigma(v)\right],\\\
&\Sigma^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z):=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\Gamma^{(h)}_{i+a,j+b,i^{\prime}+a,j^{\prime}+b}(y,z),\end{split}$
(104)

  3. 3.

For every $h=1,2,\ldots L$, every $i,i^{\prime}\in[d_{1}]$ and
$j,j^{\prime}\in[d_{2}]$, define
$\dot{\Gamma}^{(h)}(y,z)\in\mathbb{R}^{d_{1}\times d_{2}\times d_{1}\times
d_{2}}$ as:

$\dot{\Gamma}^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z):=\frac{1}{q^{2}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,1)}\left[|\sigma(w)|^{2}\right]}\cdot\mathbb{E}_{(u,v)\sim\mathcal{N}\left(0,\Lambda^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)\right)}\left[\dot{\sigma}(u)\cdot\dot{\sigma}(v)\right].$
(105)

  4. 4.

Let $\Pi^{(0)}(y,z):=0$ and for every $h=1,2,\ldots,L-1$, every
$i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$, define
$\Pi^{(h)}:\mathbb{R}^{d_{1}\times d_{2}\times c}\times\mathbb{R}^{d_{1}\times
d_{2}\times c}\to\mathbb{R}^{d_{1}\times d_{2}\times d_{1}\times d_{2}}$
recursively as:

$\begin{split}\Pi^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)&:=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\left[\Pi^{(h-1)}(y,z)\odot\dot{\Gamma}^{(h)}(y,z)+\Gamma^{(h)}(y,z)\right]_{i+a,j+b,i^{\prime}+a,j^{\prime}+b},\\\
\Pi^{(L)}(y,z)&:=\Pi^{(L-1)}(y,z)\odot\dot{\Gamma}^{(L)}(y,z).\end{split}$
(106)

  5. 5.

The final CNTK expressions is defined as:

$\Theta_{\tt
cntk}^{(L)}(y,z):=\frac{1}{d_{1}^{2}d_{2}^{2}}\cdot\sum_{i,i^{\prime}\in[d_{1}]}\sum_{j,j^{\prime}\in[d_{2}]}\Pi_{i,j,i^{\prime},j^{\prime}}^{(L)}(y,z).$
(107)

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

######  Definition 2 (ReLU-CNTK).

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

  1. 1.

For $x\in\mathbb{R}^{d_{1}\times d_{2}\times c}$, every $i\in[d_{1}]$ and
$j\in[d_{2}]$ let
$N_{i,j}^{(0)}(x):=q^{2}\cdot\sum_{l=1}^{c}\left|x_{i+a,j+b,l}\right|^{2}$,
and for every $h\geq 1$, recursively define,

$N^{(h)}_{i,j}(x):=\frac{1}{q^{2}}\cdot\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}N^{(h-1)}_{i+a,j+b}(x).$
(108)

  2. 2.

Define $\Gamma^{(0)}(y,z):=\sum_{l=1}^{c}y_{(:,:,l)}\otimes z_{(:,:,l)}$. Let
$\kappa_{1}:[-1,1]\to\mathbb{R}$ be the function defined in ?? of ??. For
every layer $h=1,2,\ldots,L$, every $i,i^{\prime}\in[d_{1}]$ and
$j,j^{\prime}\in[d_{2}]$, define $\Gamma^{(h)}:\mathbb{R}^{d_{1}\times
d_{2}\times c}\times\mathbb{R}^{d_{1}\times d_{2}\times
c}\to\mathbb{R}^{d_{1}\times d_{2}\times d_{1}\times d_{2}}$ recursively as:

$\Gamma^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z):=\frac{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\kappa_{1}\left(\frac{\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^{\prime}+a,j^{\prime}+b}(y,z)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right).$ (109)

  3. 3.

Let $\kappa_{0}:[-1,1]\to\mathbb{R}$ be the function defined in ?? of ??. For
every $h=1,2,\ldots L$, every $i,i^{\prime}\in[d_{1}]$ and
$j,j^{\prime}\in[d_{2}]$, define
$\dot{\Gamma}^{(h)}(y,z)\in\mathbb{R}^{d_{1}\times d_{2}\times d_{1}\times
d_{2}}$ as:

$\dot{\Gamma}^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z):=\frac{1}{q^{2}}\cdot\kappa_{0}\left(\frac{\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^{\prime}+a,j^{\prime}+b}(y,z)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right).$ (110)

  4. 4.

Let $\Pi^{(0)}(y,z):=0$ and for every $h=1,2,\ldots,L-1$, every
$i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$, define
$\Pi^{(h)}:\mathbb{R}^{d_{1}\times d_{2}\times c}\times\mathbb{R}^{d_{1}\times
d_{2}\times c}\to\mathbb{R}^{d_{1}\times d_{2}\times d_{1}\times d_{2}}$
recursively as:

$\Pi^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z):=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\left[\Pi^{(h-1)}(y,z)\odot\dot{\Gamma}^{(h)}(y,z)+\Gamma^{(h)}(y,z)\right]_{i+a,j+b,i^{\prime}+a,j^{\prime}+b}.$
(111)

Furthermore, for $h=L$ define:

$\Pi^{(L)}(y,z):=\Pi^{(L-1)}(y,z)\odot\dot{\Gamma}^{(L)}(y,z).$ (112)

  5. 5.

The final CNTK expressions for ReLU activation is:

$\Theta_{\tt
cntk}^{(L)}(y,z):=\frac{1}{d_{1}^{2}d_{2}^{2}}\cdot\sum_{i,i^{\prime}\in[d_{1}]}\sum_{j,j^{\prime}\in[d_{2}]}\Pi_{i,j,i^{\prime},j^{\prime}}^{(L)}(y,z).$
(113)

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.

######  Lemma 10.

For every positive integers $d_{1},d_{2},c$, odd integer $q$, and every
integer $h\geq 0$, if the activation function is ReLU, then the tensor
covariances $\Gamma^{(h)},\dot{\Gamma}^{(h)}(y,z):\mathbb{R}^{d_{1}\times
d_{2}\times c}\times\mathbb{R}^{d_{1}\times d_{2}\times
c}\to\mathbb{R}^{d_{1}\times d_{2}\times d_{1}\times d_{2}}$ defined in ?? and
??, are precisely equal to the tensor covariances defined in ?? and ?? of ??,
respectively.

Proof of ??: To prove the lemma, we first show by induction on $h=1,2,\ldots$
that $N^{(h)}_{i,j}(x)\equiv\Sigma^{(h-1)}_{i,j,i,j}(x,x)$ for every
$x\in\mathbb{R}^{d_{1}\times d_{2}\times c}$ and every $i\in[d_{1}]$ and
$j\in[d_{2}]$, where $\Sigma^{(h-1)}(x,x)$ is defined as per ?? and ??. The
base of induction trivially holds for $h=1$ because by definition of
$N^{(1)}(x)$ and ?? we have,

$N^{(1)}_{i,j}(x)=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{l=1}^{c}\left|x_{i+a,j+b,l}\right|^{2}\equiv\Sigma^{(0)}_{i,j,i,j}(x,x).$

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,

$\displaystyle\Sigma^{(h-1)}_{i,j,i,j}(x,x)$
$\displaystyle=\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}(x,x)$
$\displaystyle=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{\mathbb{E}_{(u,v)\sim\mathcal{N}\left(0,\Lambda^{(h-1)}_{i+a,j+b,i+a,j+b}(x,x)\right)}\left[\sigma(u)\cdot\sigma(v)\right]}{q^{2}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,1)}\left[|\sigma(w)|^{2}\right]}$
$\displaystyle=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{\mathbb{E}_{u\sim\mathcal{N}\left(0,\Sigma_{i+a,j+b,i+a,j+b}^{(h-2)}(x,x)\right)}\left[|\max(0,u)|^{2}\right]}{q^{2}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,1)}\left[|\max(0,w)|^{2}\right]}$
$\displaystyle=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{1}{q^{2}}\cdot\Sigma^{(h-2)}_{i+a,j+b,i+a,j+b}(x,x)$
$\displaystyle=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{1}{q^{2}}\cdot
N^{(h-1)}_{i+a,j+b}(x)\equiv
N^{(h)}_{i,j}(x).\text{~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(by
\leavevmode{\mbox{??}})}$

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$.

Now, note that the $2\times 2$ covariance matrix
$\Lambda^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)$, defined in ??, can be
decomposed as
$\Lambda^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)=\begin{pmatrix}f^{\top}\\\
g^{\top}\end{pmatrix}\cdot\begin{pmatrix}f&g\end{pmatrix}$, where
$f,g\in\mathbb{R}^{2}$. Also note that
$\|f\|_{2}^{2}=\Sigma^{(h-1)}_{i,j,i,j}(y,y)$ and
$\|g\|_{2}^{2}=\Sigma^{(h-1)}_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}(z,z)$,
hence, by what we proved above, we have,

$\|f\|_{2}^{2}=N^{(h)}_{i,j}(y),\text{ and
}\|g\|_{2}^{2}=N^{(h)}_{i^{\prime},j^{\prime}}(z).$

Therefore, by ??, we can write:

$\displaystyle\Gamma^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)$
$\displaystyle=\frac{1}{q^{2}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,1)}\left[|\sigma(w)|^{2}\right]}\cdot\mathbb{E}_{(u,v)\sim\mathcal{N}\left(0,\Lambda^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)\right)}\left[\sigma(u)\cdot\sigma(v)\right]$
$\displaystyle=\frac{1}{q^{2}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,1)}\left[|\sigma(w)|^{2}\right]}\cdot\mathbb{E}_{u\sim\mathcal{N}\left(0,I_{d}\right)}\left[\sigma(u^{\top}f)\cdot\sigma(u^{\top}g)\right]$
$\displaystyle=\frac{2\cdot\|f\|_{2}\cdot\|g\|_{2}}{q^{2}\cdot\kappa_{1}(1)}\cdot\frac{1}{2}\cdot\kappa_{1}\left(\frac{\langle
f,g\rangle}{\|f\|_{2}\cdot\|g\|_{2}}\right)$
$\displaystyle=\frac{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\kappa_{1}\left(\frac{\Sigma^{(h-1)}_{i,j,i^{\prime},j^{\prime}}(y,z)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right)$
$\displaystyle=\frac{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\kappa_{1}\left(\frac{\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^{\prime}+a,j^{\prime}+b}(y,z)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right),$

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,

$\displaystyle\dot{\Gamma}^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)$
$\displaystyle=\frac{1}{q^{2}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,1)}\left[|\sigma(w)|^{2}\right]}\cdot\mathbb{E}_{(u,v)\sim\mathcal{N}\left(0,\Lambda^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)\right)}\left[\dot{\sigma}(u)\cdot\dot{\sigma}(v)\right]$
$\displaystyle=\frac{1}{q^{2}\cdot\mathbb{E}_{w\sim\mathcal{N}(0,1)}\left[|\sigma(w)|^{2}\right]}\cdot\mathbb{E}_{u\sim\mathcal{N}\left(0,I_{d}\right)}\left[\dot{\sigma}(u^{\top}f)\cdot\dot{\sigma}(u^{\top}g)\right]$
$\displaystyle=\frac{2}{q^{2}\cdot\kappa_{1}(1)}\cdot\frac{1}{2}\cdot\kappa_{0}\left(\frac{\langle
f,g\rangle}{\|f\|_{2}\cdot\|g\|_{2}}\right)$
$\displaystyle=\frac{1}{q^{2}}\cdot\kappa_{0}\left(\frac{\Sigma^{(h-1)}_{i,j,i^{\prime},j^{\prime}}(y,z)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right)$
$\displaystyle=\frac{1}{q^{2}}\cdot\kappa_{0}\left(\frac{\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^{\prime}+a,j^{\prime}+b}(y,z)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right).$

This completes the proof of ??. ∎

######  Corollary 1 (Consequence of ??).

Consider the preconditions of ??. For every $x\in\mathbb{R}^{d_{1}\times
d_{2}\times c}$,
$N^{(h)}_{i,j}(x)\equiv\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}(x,x)$.

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

######  Lemma 11 (Properties of $\Gamma^{(h)}(y,z)$).

For every images $y,z\in\mathbb{R}^{d_{1}\times d_{2}\times c}$, every integer
$h\geq 0$ and every $i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$ the
following properties are satisfied by functions $\Gamma^{(h)}$ and $N^{(h)}$
defined in ?? and ?? of ??:

  1. 1.

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}}$.

  2. 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

$\displaystyle\left|\Gamma_{i,j,i^{\prime},j^{\prime}}^{(0)}(y,z)\right|$
$\displaystyle\equiv\left|\sum_{l=1}^{c}y_{i,j,l}\cdot
z_{i^{\prime},j^{\prime},l}\right|$
$\displaystyle\leq\sqrt{\sum_{l=1}^{c}|y_{i,j,l}|^{2}\cdot\sum_{l=1}^{c}|z_{i^{\prime},j^{\prime},l}|^{2}}$
$\displaystyle=\frac{\sqrt{N_{i,j}^{(0)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(0)}(z)}}{q^{2}}.$

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

$\begin{split}\left|\frac{\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^{\prime}+a,j^{\prime}+b}(y,z)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right|&\leq\frac{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sqrt{\frac{N^{(h-1)}_{i+a,j+b}(y)}{q^{2}}\cdot\frac{N^{(h-1)}_{i^{\prime}+a,j^{\prime}+b}(z)}{q^{2}}}}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\\\ &\leq 1.\end{split}$

Thus, by monotonicity of the function $\kappa_{1}:[-1,1]\to\mathbb{R}$, we can
write,

$\displaystyle\left|\Gamma_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\right|$
$\displaystyle\equiv\frac{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\kappa_{1}\left(\frac{\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^{\prime}+a,j^{\prime}+b}(y,z)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right)$
$\displaystyle\leq\frac{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\kappa_{1}(1)$
$\displaystyle=\frac{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}},$

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,

$\displaystyle\Gamma_{i,j,i,j}^{(h)}(y,y)$
$\displaystyle\equiv\frac{N^{(h)}_{i,j}(y)}{q^{2}}\cdot\kappa_{1}\left(\frac{\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)}\right)$
$\displaystyle=\frac{N^{(h)}_{i,j}(y)}{q^{2}}\cdot\kappa_{1}(1)$
$\displaystyle=\frac{N^{(h)}_{i,j}(y)}{q^{2}}\geq 0,$

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,

######  Lemma 12 (Properties of $\dot{\Gamma}^{(h)}(y,z)$).

For every images $y,z\in\mathbb{R}^{d_{1}\times d_{2}\times c}$, every integer
$h\geq 0$ and every $i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$ the
following properties are satisfied by function $\dot{\Gamma}^{(h)}$ defined in
?? of ??:

  1. 1.

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

  2. 2.

Norm value: $\dot{\Gamma}_{i,j,i,j}^{(h)}(y,y)=\frac{1}{q^{2}}\geq 0$.

Proof of ??: First, note that by ?? and the definition of $N^{(h)}$ in ?? we
have,

$\begin{split}\left|\frac{\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^{\prime}+a,j^{\prime}+b}(y,z)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right|&\leq\frac{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sqrt{\frac{N^{(h-1)}_{i+a,j+b}(y)}{q^{2}}\cdot\frac{N^{(h-1)}_{i^{\prime}+a,j^{\prime}+b}(z)}{q^{2}}}}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\\\ &\leq 1.\end{split}$

Thus, by monotonicity of function $\kappa_{0}:[-1,1]\to\mathbb{R}$ and using
??, we can write,
$\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\leq\frac{1}{q^{2}}\cdot\kappa_{0}(1)=\frac{1}{q^{2}}$.
Moreover, the equality is achieved when $y=z$ and $i=i^{\prime}$ and
$j=j^{\prime}$. This proves both statements of the lemma. ∎

We also need to use some properties of $\Pi^{(h)}(y,z)$ defined in ?? and ??.
We present these propertied in the next lemma,

######  Lemma 13 (Properties of $\Pi^{(h)}$).

For every images $y,z\in\mathbb{R}^{d_{1}\times d_{2}\times c}$, every integer
$h\geq 0$ and every $i\in[d_{1}]$ and $j\in[d_{2}]$ the following properties
are satisfied by the function $\Pi^{(h)}$ defined in ?? and ?? of ??:

  1. 1.

Cauchy–Schwarz inequality:
$\Pi_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\leq\sqrt{\Pi_{i,j,i,j}^{(h)}(y,y)\cdot\Pi_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(h)}(z,z)}$.

  2. 2.

Norm value: $\Pi_{i,j,i,j}^{(h)}(y,y)=\begin{cases}h\cdot
N_{i,j}^{(h+1)}(y)&\text{if }h<L\\\ \frac{L-1}{q^{2}}\cdot
N_{i,j}^{(L)}(y)&\text{if }h=L\end{cases}$.

Proof of ??: The proof is by induction on $h$. The base of induction
corresponds to $h=0$. By definition of $\Pi_{i,j,i,j}^{(0)}\equiv 0$ in ??,
the base of induction for both statements of the lemma follow immediately.

Now we prove the inductive hypothesis. Suppose that the lemma statement holds
for $h-1$. We prove that conditioned on this, the statements of the lemma hold
for $h$. There are two cases. The first case corresponds to $h<L$. In this
case, by definition of $\Pi_{i,j,i,j}^{(h)}(x,x)$ in ?? and using ?? and ?? we
can write,

$\displaystyle\left|\Pi^{(h)}_{i,j,i^{\prime},j^{\prime}}(y,z)\right|\equiv\left|\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\left[\Pi^{(h-1)}(y,z)\odot\dot{\Gamma}^{(h)}(y,z)+\Gamma^{(h)}(y,z)\right]_{i+a,j+b,i^{\prime}+a,j^{\prime}+b}\right|$
$\displaystyle\leq\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{\sqrt{\Pi^{(h-1)}_{i+a,j+b,i+a,j+b}(y,y)\cdot\Pi^{(h-1)}_{i^{\prime}+a,j^{\prime}+b,i^{\prime}+a,j^{\prime}+b}(z,z)}}{q^{2}}+\frac{\sqrt{N^{(h)}_{i+a,j+b}(y)\cdot
N^{(h)}_{i^{\prime}+a,j^{\prime}+b}(z)}}{q^{2}}$
$\displaystyle\leq\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sqrt{\frac{\Pi^{(h-1)}_{i+a,j+b,i+a,j+b}(y,y)+N^{(h)}_{i+a,j+b}(y)}{q^{2}}}\cdot\sqrt{\frac{\Pi^{(h-1)}_{i^{\prime}+a,j^{\prime}+b,i^{\prime}+a,j^{\prime}+b}(z,z)+N^{(h)}_{i^{\prime}+a,j^{\prime}+b}(z)}{q^{2}}}$
$\displaystyle\leq\sqrt{\Pi^{(h)}_{i,j,i,j}(y,y)}\cdot\sqrt{\Pi^{(h)}_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}(z,z)},$

where the second line above follows from inductive hypothesis along with ??
and ??. The third and fourth lines above follow by Cauchy–Schwarz inequality.
The second case corresponds to $h=L$. In this case, by definition of
$\Pi_{i,j,i^{\prime},j^{\prime}}^{(L)}(y,z)$ in ?? and using ?? and ?? along
with the inductive hypothesis we can write,

$\displaystyle\left|\Pi^{(L)}_{i,j,i^{\prime},j^{\prime}}(y,z)\right|$
$\displaystyle\equiv\left|\Pi^{(L-1)}_{i,j,i^{\prime},j^{\prime}}(y,z)\cdot\dot{\Gamma}^{(L)}_{i,j,i^{\prime},j^{\prime}}(y,z)\right|$
$\displaystyle\leq\frac{\sqrt{\Pi^{(L-1)}_{i,j,i,j}(y,y)\cdot\Pi^{(L-1)}_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}(z,z)}}{q^{2}}$
$\displaystyle=\sqrt{\Pi^{(L)}_{i,j,i,j}(y,y)}\cdot\sqrt{\Pi^{(L)}_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}(z,z)},$

where the second line above follows from inductive hypothesis along with ??.
This completes the inductive step and in turn proves the first statement of
the lemma.

To prove the inductive step for the second statement of lemma we consider two
cases again. The first case is $h<L$. In this case, note that by using
inductive hypothesis together with ?? and ?? we can write,

$\displaystyle\Pi^{(h)}_{i,j,i,j}(y,y)$
$\displaystyle\equiv\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\left[\Pi^{(h-1)}(y,y)\odot\dot{\Gamma}^{(h)}(y,y)+\Gamma^{(h)}(y,y)\right]_{i+a,j+b,i+a,j+b}$
$\displaystyle=\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{(h-1)\cdot
N_{i+a,j+b}^{(h)}(y)}{q^{2}}+\frac{N_{i+a,j+b}^{(h)}(y)}{q^{2}}$
$\displaystyle=h\cdot\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{N^{(h)}_{i+a,j+b}(y)}{q^{2}}$
$\displaystyle=h\cdot N^{(h+1)}_{i,j}(y),$

where the last line above follows from definition of $N^{(h)}$ in ??. The
second case corresponds to $h=L$. In this case, by inductive hypothesis
together with ?? and ?? we can write,

$\displaystyle\Pi^{(L)}_{i,j,i,j}(y,y)$
$\displaystyle\equiv\Pi^{(L-1)}_{i,j,i,j}(y,y)\cdot\dot{\Gamma}^{(L)}_{i,j,i,j}(y,y)$
$\displaystyle=\frac{(L-1)\cdot N_{i,j}^{(L)}(y)}{q^{2}}.$

This completes the inductive step for the second statement and in turn proves
the second statement of the lemma. This completes the proof of ??. ∎

##  Appendix G CNTK Sketch: Algorithm, Claims and Invariants

In this section we give our sketching algorithm for the CNTK kernel and prove
our main theorem for this algorithm, i.e., ??. We start by introducing our
CNTKSketch algorithm in the following definition:

######  Definition 3 (CNTKSketch Algorithm).

For every image $x\in\mathbb{R}^{d_{1}\times d_{2}\times c}$, we compute the
CNTKSketch , $\Psi_{\tt cntk}^{(L)}(x)$, recursively as follows,

  1. $\bullet$

Let $s=\widetilde{\mathcal{O}}\left(\frac{L^{2}}{\varepsilon^{2}}\right)$,
$r=\widetilde{\mathcal{O}}\left(\frac{L^{6}}{\varepsilon^{4}}\right)$,
$n_{1}=\widetilde{\mathcal{O}}\left(\frac{L^{4}}{\varepsilon^{4}}\right)$,
$m=\widetilde{\mathcal{O}}\left(\frac{L^{8}}{\varepsilon^{16/3}}\right)$, and
$s^{*}=\mathcal{O}(\frac{1}{\varepsilon^{2}}\log\frac{1}{\delta})$ and
$P^{(p)}_{\tt relu}(\alpha)=\sum_{l=0}^{2p+2}c_{l}\cdot\alpha^{l}$ and
$\dot{P}^{(p^{\prime})}_{\tt
relu}(\alpha)=\sum_{l=0}^{2p^{\prime}+1}b_{l}\cdot\alpha^{l}$ be the
polynomials defined in ??.

  2. 1.

For every $i\in[d_{1}]$, $j\in[d_{2}]$, and $h=0,1,2,\ldots L$ compute
$N_{i,j}^{(h)}(x)$ as per ?? of ??.

  3. 2.

Let ${\bm{S}}\in\mathbb{R}^{r\times c}$ be an SRHT. For every $i\in[d_{1}]$
and $j\in[d_{2}]$, compute $\phi_{i,j}^{(0)}(x)\in\mathbb{R}^{r}$ as,

$\phi_{i,j}^{(0)}(x)\leftarrow{\bm{S}}\cdot x_{(i,j,:)}.$ (114)

  4. 3.

Let ${\bm{Q}}^{2p+2}\in\mathbb{R}^{m\times\left(q^{2}r\right)^{2p+2}}$ be a
degree-$2p+2$ PolySketch , and ${\bm{T}}\in\mathbb{R}^{r\times(2p+3)\cdot m}$
be an SRHT. For every $h\in[L]$, every $i\in[d_{1}]$ and $j\in[d_{2}]$, and
$l=0,1,2,\ldots 2p+2$ compute:

$\begin{split}&\mu^{(h)}_{i,j}(x)\leftarrow\bigoplus_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\bigoplus_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{\phi_{i+a,j+b}^{(h-1)}(x)}{\sqrt{N^{(h)}_{i,j}(x)}},\\\
&\left[Z^{(h)}_{i,j}(x)\right]_{l}\leftarrow{\bm{Q}}^{2p+2}\cdot\left(\left[\mu^{(h)}_{i,j}(x)\right]^{\otimes
l}\otimes{e}_{1}^{\otimes 2p+2-l}\right),\\\
&\phi_{i,j}^{(h)}(x)\leftarrow\frac{\sqrt{N^{(h)}_{i,j}(x)}}{q}\cdot{\bm{T}}\cdot\left(\bigoplus_{l=0}^{2p+2}\sqrt{c_{l}}\left[Z^{(h)}_{i,j}(x)\right]_{l}\right).\end{split}$
(115)

  5. 4.

Let
${\bm{Q}}^{2p^{\prime}+1}\in\mathbb{R}^{n_{1}\times\left(q^{2}r\right)^{2p^{\prime}+1}}$
be a degree-$2p^{\prime}+1$ PolySketch , and
${\bm{W}}\in\mathbb{R}^{s\times(2p^{\prime}+2)\cdot n_{1}}$ be an SRHT. For
every $h\in[L],i\in[d_{1}],j\in[d_{2}]$, and $l=0,1,\ldots 2p^{\prime}+1$
compute:

$\left[Y^{(h)}_{i,j}(x)\right]_{l}\leftarrow{\bm{Q}}^{2p^{\prime}+1}\left(\left[\mu^{(h)}_{i,j}(x)\right]^{\otimes
l}\otimes{e}_{1}^{\otimes
2p^{\prime}+1-l}\right),~{}\dot{\phi}_{i,j}^{(h)}(x)\leftarrow\frac{1}{q}\cdot{\bm{W}}\left(\bigoplus_{l=0}^{2p^{\prime}+1}\sqrt{b_{l}}\left[Y^{(h)}_{i,j}(x)\right]_{l}\right).$
(116)

  6. 5.

Let ${\bm{Q}}^{2}\in\mathbb{R}^{s\times s^{2}}$ be a degree-$2$ PolySketch ,
and ${\bm{R}}\in\mathbb{R}^{s\times q^{2}(s+r)}$ be an SRHT. Let
$\psi^{(0)}_{i,j}(x)\leftarrow 0$ and for every $h\in[L-1]$, and
$i\in[d_{1}],j\in[d_{2}]$, compute $\psi^{(h)}_{i,j}(x)\in\mathbb{R}^{s}$ as:

$\begin{split}&\eta^{(h)}_{i,j}(x)\leftarrow{\bm{Q}}^{2}\left(\psi_{i,j}^{(h-1)}(x)\otimes\dot{\phi}_{i,j}^{(h)}(x)\right)\oplus\phi_{i,j}^{(h)}(x),\\\
&\psi^{(h)}_{i,j}(x)\leftarrow{\bm{R}}\left(\bigoplus_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\bigoplus_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\eta_{i+a,j+b}^{(h)}(x)\right).\end{split}$
(117) $\text{(For $h=L$:)
}~{}~{}~{}~{}~{}~{}~{}~{}~{}\psi^{(L)}_{i,j}(x)\leftarrow{\bm{Q}}^{2}\cdot\left(\psi^{(L-1)}_{i,j}(x)\otimes\dot{\phi}_{i,j}^{(L)}(x)\right).$
(118)

  7. 6.

Let ${\bm{G}}\in\mathbb{R}^{s^{*}\times s}$ be a random matrix of i.i.d.
normal entries with distribution $\mathcal{N}(0,1/s^{*})$. The CNTKSketch is
the following:

$\Psi_{\tt
cntk}^{(L)}(y,z):=\frac{1}{d_{1}d_{2}}\cdot{\bm{G}}\cdot\left(\sum_{i\in[d_{1}]}\sum_{j\in[d_{2}]}\psi^{(L)}_{i,j}(x)\right).$
(119)

In the following lemma, we analyze the correctness of the CNTKSketch algorithm
by giving the invariants that the algorithm maintains at all times,

######  Lemma 14 (Invariants of the CNTKSketch ).

For every positive integers $d_{1},d_{2},c$, and $L$, every
$\varepsilon,\delta>0$, every images $y,z\in\mathbb{R}^{d_{1}\times
d_{2}\times c}$ , if we let $N^{(h)}:\mathbb{R}^{d_{1}\times d_{2}\times
c}\to\mathbb{R}^{d_{1}\times d_{2}}$,
$\Gamma^{(h)}(y,z)\in\mathbb{R}^{d_{1}\times d_{2}\times d_{1}\times d_{2}}$
and $\Pi^{(h)}(y,z)\in\mathbb{R}^{d_{1}\times d_{2}\times d_{1}\times d_{2}}$
be the tensor functions defined in ??, ??, ??, and ?? of ??, respectively,
then with probability at least $1-\delta$ the following invariants are
maintained simultaneously for all $i,i^{\prime}\in[d_{1}]$ and
$j,j^{\prime}\in[d_{2}]$ and every $h=0,1,2,\ldots L$:

  1. 1.

The mapping $\phi_{i,j}^{(h)}(\cdot)$ computed by the CNTK Sketch algorithm in
?? and ?? of ?? satisfy the following,

$\left|\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\Gamma_{i,j,i^{\prime},j^{\prime}}^{(h)}\left(y,z\right)\right|\leq({h+1})\cdot\frac{\varepsilon^{2}}{60L^{3}}\cdot\frac{\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}}{q^{2}}.$

  2. 2.

The mapping $\psi_{i,j}^{(h)}(\cdot)$ computed by the CNTK Sketch algorithm in
?? and ?? of ?? satisfy the following,

$\left|\left<\psi_{i,j}^{(h)}(y),\psi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\Pi_{i,j,i^{\prime},j^{\prime}}^{(h)}\left(y,z\right)\right|\leq\begin{cases}\frac{\varepsilon}{10}\cdot\frac{h^{2}}{L+1}\cdot\sqrt{N^{(h+1)}_{i,j}(y)\cdot
N^{(h+1)}_{i^{\prime},j^{\prime}}(z)}&\text{if }h<L\\\
\frac{\varepsilon}{10}\cdot\frac{L-1}{q^{2}}\cdot\sqrt{N^{(L)}_{i,j}(y)\cdot
N^{(L)}_{i^{\prime},j^{\prime}}(z)}&\text{if }h=L\end{cases}.$

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$:

  1. ${\bf P_{1}(h):}$

Simultaneously for all $i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$:

$\begin{split}&\left|\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\Gamma_{i,j,i^{\prime},j^{\prime}}^{(h)}\left(y,z\right)\right|\leq({h+1})\cdot\frac{\varepsilon^{2}}{60L^{3}}\cdot\frac{\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}}{q^{2}},\\\
&\left|\left\|\phi_{i,j}^{(h)}(y)\right\|_{2}^{2}-\Gamma_{i,j,i,j}^{(h)}\left(y,y\right)\right|\leq\frac{({h+1})\cdot\varepsilon^{2}}{60L^{3}}\cdot\frac{N_{i,j}^{(h)}(y)}{q^{2}},\\\
&\left|\left\|\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2}-\Gamma_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(h)}\left(z,z\right)\right|\leq\frac{({h+1})\cdot\varepsilon^{2}}{60L^{3}}\cdot\frac{N_{i^{\prime},j^{\prime}}^{(h)}(z)}{q^{2}}.\end{split}$

  2. ${\bf P_{2}(h):}$

Simultaneously for all $i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$:

$\begin{split}&\left|\left<\psi_{i,j}^{(h)}(y),\psi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\Pi_{i,j,i^{\prime},j^{\prime}}^{(h)}\left(y,z\right)\right|\leq\begin{cases}\frac{\varepsilon}{10}\cdot\frac{h^{2}}{L+1}\cdot\sqrt{N^{(h+1)}_{i,j}(y)\cdot
N^{(h+1)}_{i^{\prime},j^{\prime}}(z)}&\text{if }h<L\\\
\frac{\varepsilon}{10}\cdot\frac{L-1}{q^{2}}\cdot\sqrt{N^{(L)}_{i,j}(y)\cdot
N^{(L)}_{i^{\prime},j^{\prime}}(z)}&\text{if }h=L\end{cases},\\\ &{(\text{only
for
}h<L):}~{}~{}~{}\left|\left\|\psi_{i,j}^{(h)}(y)\right\|_{2}^{2}-\Pi_{i,j,i,j}^{(h)}\left(y,y\right)\right|\leq\frac{\varepsilon}{10}\cdot\frac{h^{2}}{L+1}\cdot
N^{(h+1)}_{i,j}(y),\\\ &{(\text{only for
}h<L):}~{}~{}~{}\left|\left\|\psi_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2}-\Pi_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(h)}\left(z,z\right)\right|\leq\frac{\varepsilon}{10}\cdot\frac{h^{2}}{L+1}\cdot
N^{(h+1)}_{i^{\prime},j^{\prime}}(z).\end{split}$

We prove that probabilities $\Pr[P_{1}(0)]$ and $\Pr[P_{2}(0)|P_{1}(0)]$ are
both greater than $1-\mathcal{O}(\delta/L)$. Additionally, for every
$h=1,2,\ldots L$, we prove that the conditional probabilities
$\Pr[P_{1}(h)|P_{1}(h-1)]$ and $\Pr[P_{2}(h)|P_{2}(h-1),P_{1}(h),P_{1}(h-1)]$
are greater than $1-\mathcal{O}(\delta/L)$.

The base of induction corresponds to $h=0$. By ??,
$\phi_{i,j}^{(0)}(y)={\bm{S}}\cdot y_{(i,j,:)}$ and
$\phi_{i^{\prime},j^{\prime}}^{(0)}(z)={\bm{S}}\cdot
z_{(i^{\prime},j^{\prime},:)}$, thus, ?? implies the following

$\Pr\left[\left|\left<\phi_{i,j}^{(0)}(y),\phi_{i^{\prime},j^{\prime}}^{(0)}(z)\right>-\left<y_{(i,j,:)},z_{(i^{\prime},j^{\prime},:)}\right>\right|\leq\mathcal{O}\left(\varepsilon^{2}/L^{3}\right)\cdot\|y_{(i,j,:)}\|_{2}\|z_{(i^{\prime},j^{\prime},:)}\|_{2}\right]\geq
1-\mathcal{O}\left(\frac{\delta}{d_{1}^{2}d_{2}^{2}L}\right),$

therefore, by using ?? and ?? we have

$\Pr\left[\left|\left<\phi_{i,j}^{(0)}(y),\phi_{i^{\prime},j^{\prime}}^{(0)}(z)\right>-\Gamma_{i,j,i^{\prime},j^{\prime}}^{(0)}(y,z)\right|\leq\mathcal{O}\left(\varepsilon^{2}/L^{3}\right)\cdot\frac{\sqrt{N^{(0)}_{i,j}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(0)}(z)}}{q^{2}}\right]\geq
1-\mathcal{O}\left(\frac{\delta}{d_{1}^{2}d_{2}^{2}L}\right).$

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

$\begin{split}&\left|\left\|\phi_{i,j}^{(0)}(y)\right\|_{2}^{2}-\Gamma_{i,j,i,j}^{(0)}\left(y,y\right)\right|\leq\mathcal{O}\left(\varepsilon^{2}/L^{3}\right)\cdot\frac{N^{(0)}_{i,j}(y)}{q^{2}},\\\
&\left|\left\|\phi_{i^{\prime},j^{\prime}}^{(0)}(z)\right\|_{2}^{2}-\Gamma_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(0)}\left(z,z\right)\right|\leq\mathcal{O}\left(\varepsilon^{2}/L^{3}\right)\cdot\frac{N^{(0)}_{i^{\prime},j^{\prime}}(z)}{q^{2}}.\end{split}$

By union bounding over all $i,i^{\prime}\in[d_{1}]$ and
$j,j^{\prime}\in[d_{2}]$, this proves the base of induction for statement
$P_{1}(h)$, i.e., $\Pr[P_{1}(0)]\geq 1-\mathcal{O}(\delta/L)$.

Moreover, by ??, we have that $\psi_{i,j}^{(0)}(y)=0$ and
$\psi_{i^{\prime},j^{\prime}}^{(0)}(z)=0$, thus, by ??, it trivially holds
that $\Pr[P_{2}(0)|P_{1}(0)]=1\geq 1-\mathcal{O}(\delta/L)$. This completes
the base of induction.

Now, we proceed to prove the inductive step. That is, by assuming the
inductive hypothesis for $h-1$, we prove that statements $P_{1}(h)$ and
$P_{2}(h)$ hold. More precisely, first we condition on the statement
$P_{1}(h-1)$ being true for some $h\geq 1$, and then prove that $P_{1}(h)$
holds with probability at least $1-\mathcal{O}(\delta/L)$. Next we show that
conditioned on statements $P_{2}(h-1),P_{1}(h),P_{1}(h-1)$ being true,
$P_{2}(h)$ holds with probability at least $1-\mathcal{O}(\delta/L)$. This
will complete the induction.

First, note that by ??, union bound, and using ??, the following holds
simultaneously for all $i,i^{\prime}\in[d_{1}]$ and all
$j,j^{\prime}\in[d_{2}]$, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$,

$\left|\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\frac{\sqrt{N^{(h)}_{i,j}(y)N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\sum_{l=0}^{2p+2}c_{l}\left<\left[Z^{(h)}_{i,j}(y)\right]_{l},\left[Z^{(h)}_{i^{\prime},j^{\prime}}(z)\right]_{l}\right>\right|\leq\mathcal{O}\left(\frac{\varepsilon^{2}}{L^{3}}\right)\cdot
A,$ (120)

where
$A:=\frac{\sqrt{N^{(h)}_{i,j}(y)N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\sqrt{\sum_{l=0}^{2p+2}c_{l}\left\|\left[Z^{(h)}_{i,j}(y)\right]_{l}\right\|_{2}^{2}}\cdot\sqrt{\sum_{l=0}^{2p+2}c_{l}\left\|\left[Z^{(h)}_{i^{\prime},j^{\prime}}(z)\right]_{l}\right\|_{2}^{2}}$
and the collection of vectors
$\left\\{\left[Z^{(h)}_{i,j}(y)\right]_{l}\right\\}_{l=0}^{2p+2}$ and
$\left\\{\left[Z^{(h)}_{i^{\prime},j^{\prime}}(z)\right]_{l}\right\\}_{l=0}^{2p+2}$
and coefficients $c_{0},c_{1},c_{2},\ldots c_{2p+2}$ are defined as per ?? and
??, respectively. Additionally, by ?? and union bound, the following
inequalities hold, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$, simultaneously for all
$l=0,1,2,\ldots 2p+2$, all $i,i^{\prime}\in[d_{1}]$ and all
$j,j^{\prime}\in[d_{2}]$:

$\displaystyle\left|\left<\left[Z^{(h)}_{i,j}(y)\right]_{l},\left[Z^{(h)}_{i^{\prime},j^{\prime}}(z)\right]_{l}\right>-\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>^{l}\right|\leq
O\left(\frac{\varepsilon^{2}}{L^{3}}\right)\left\|\mu_{i,j}^{(h)}(y)\right\|_{2}^{l}\left\|\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{l}$
$\displaystyle\left\|\left[Z^{(h)}_{i,j}(y)\right]_{l}\right\|_{2}^{2}\leq\frac{11}{10}\cdot\left\|\mu_{i,j}^{(h)}(y)\right\|_{2}^{2l}$
(121)
$\displaystyle\left\|\left[Z^{(h)}_{i^{\prime},j^{\prime}}(z)\right]_{l}\right\|_{2}^{2}\leq\frac{11}{10}\cdot\left\|\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2l}$

Therefore, by plugging ?? back to ?? and using union bound and triangle
inequality as well as Cauchy–Schwarz inequality, we find that with probability
at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$, the following holds
simultaneously for all $i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$

$\left|\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\frac{\sqrt{N^{(h)}_{i,j}(y)N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot
P^{(p)}_{\tt
relu}\left(\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>\right)\right|\leq\mathcal{O}\left(\frac{\varepsilon^{2}}{L^{3}}\right)\cdot
B,$ (122)

where
$B:=\frac{\sqrt{N^{(h)}_{i,j}(y)N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\sqrt{P^{(p)}_{\tt
relu}\left(\|\mu^{(h)}_{i,j}(y)\|_{2}^{2}\right)\cdot P^{(p)}_{\tt
relu}\left(\|\mu^{(h)}_{i^{\prime},j^{\prime}}(z)\|_{2}^{2}\right)}$ and
$P^{(p)}_{\tt relu}(\alpha)=\sum_{l=0}^{2p+2}c_{l}\cdot\alpha^{l}$ is the
polynomial defined in ??. By using the definition of $\mu_{i,j}^{(h)}(\cdot)$
in ?? we have,

$\begin{split}&\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>=\frac{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\left<\phi_{i+a,j+b}^{(h-1)}(y),\phi_{i^{\prime}+a,j^{\prime}+b}^{(h-1)}(z)\right>}{\sqrt{N^{(h)}_{i,j}(y)N^{(h)}_{i^{\prime},j^{\prime}}(z)}},\\\
&\left\|\mu_{i,j}^{(h)}(y)\right\|_{2}^{2}=\frac{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\left\|\phi_{i+a,j+b}^{(h-1)}(y)\right\|_{2}^{2}}{N^{(h)}_{i,j}(y)},\\\
&\left\|\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2}=\frac{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\left\|\phi_{i^{\prime}+a,j^{\prime}+b}^{(h-1)}(z)\right\|_{2}^{2}}{N^{(h)}_{i,j}(z)}.\end{split}$
(123)

Hence, by conditioning on the inductive hypothesis $P_{1}(h-1)$ and using ??
and ?? we have,

$\left|\left\|\mu_{i,j}^{(h)}(y)\right\|_{2}^{2}-1\right|\leq
h\cdot\frac{\varepsilon^{2}}{60L^{3}},\text{ and
}\left|\left\|\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2}-1\right|\leq
h\cdot\frac{\varepsilon^{2}}{60L^{3}}.$

Therefore, by invoking ??, it follows that $\left|P_{\tt
relu}^{(p)}\left(\|\mu^{(h)}_{i,j}(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(\|\mu^{(h)}_{i^{\prime},j^{\prime}}(z)\|_{2}^{2}\right)-P_{\tt
relu}^{(p)}(1)\right|\leq h\cdot\frac{\varepsilon^{2}}{60L^{3}}$.
Consequently, because $P_{\tt relu}^{(p)}(1)\leq P_{\tt
relu}^{(+\infty)}(1)=1$, we find that

$B\leq\frac{11}{10}\cdot\frac{\sqrt{N^{(h)}_{i,j}(y)N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}.$

For shorthand we use the notation
$\beta:=\frac{\sqrt{N^{(h)}_{i,j}(y)N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}$.
By plugging this into ?? and using the notation $\beta$, we find that the
following holds simultaneously for all $i,i^{\prime}\in[d_{1}]$ and all
$j,j^{\prime}\in[d_{2}]$, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$,

$\left|\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\beta\cdot
P^{(p)}_{\tt
relu}\left(\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>\right)\right|\leq\mathcal{O}\left(\frac{\varepsilon^{2}}{L^{3}}\right)\cdot\beta.$
(124)

Furthermore, by conditioning on the inductive hypothesis $P_{1}(h-1)$ and
combining it with ?? and applying Cauchy–Schwarz inequality and invoking ?? we
find that,

$\begin{split}&\left|\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\frac{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\Gamma_{i+a,j+b,i^{\prime}+a,j^{\prime}+b}^{(h-1)}\left(y,z\right)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\right|\\\
&\qquad\leq\frac{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sqrt{N_{i+a,j+b}^{(h-1)}(y)\cdot
N_{i^{\prime}+a,j^{\prime}+b}^{(h-1)}(z)}}{q^{2}\cdot\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\cdot
h\cdot\frac{\varepsilon^{2}}{60L^{3}}\\\
&\qquad\leq\frac{\sqrt{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{N_{i+a,j+b}^{(h-1)}(y)}{q^{2}}}\cdot\sqrt{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{N_{i^{\prime}+a,j^{\prime}+b}^{(h-1)}(z)}{q^{2}}}}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}\cdot\frac{h\cdot\varepsilon^{2}}{60L^{3}}\\\
&\qquad=h\cdot\frac{\varepsilon^{2}}{60L^{3}},\end{split}$ (125)

where the last line follows from ??.

For shorthand, we use the notation
$\gamma:=\frac{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\Gamma_{i+a,j+b,i^{\prime}+a,j^{\prime}+b}^{(h-1)}\left(y,z\right)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}$. Note that by ?? and ??,
$-1\leq\gamma\leq 1$. Hence, we can invoke ?? and use ?? to find that,

$\left|P^{(p)}_{\tt
relu}\left(\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>\right)-P^{(p)}_{\tt
relu}\left(\gamma\right)\right|\leq h\cdot\frac{\varepsilon^{2}}{60L^{3}}.$

By incorporating the above inequality into ?? using triangle inequality we
find that, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$, the following holds
simultaneously for all $i,i^{\prime}\in[d_{1}]$ and all
$j,j^{\prime}\in[d_{2}]$:

$\left|\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\beta\cdot
P^{(p)}_{\tt
relu}\left(\gamma\right)\right|\leq\left(\mathcal{O}\left(\frac{\varepsilon^{2}}{L^{3}}\right)+\frac{h\cdot\varepsilon^{2}}{60L^{3}}\right)\cdot\beta.$
(126)

Additionally, since $-1\leq\gamma\leq 1$, we can invoke ?? and use the fact
that $p=\left\lceil 2L^{2}/{\varepsilon}^{4/3}\right\rceil$ to conclude,

$\left|P_{\tt
relu}^{(p)}\left(\gamma\right)-\kappa_{1}(\gamma)\right|\leq\frac{\varepsilon^{2}}{76L^{3}}.$

By combining the above inequality with ?? via triangle inequality and using
the fact that, by ??,
$\beta\cdot\kappa_{1}(\gamma)\equiv\Gamma_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)$
we get the following inequality, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$,

$\left|\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\Gamma_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\right|\leq(h+1)\cdot\frac{\varepsilon^{2}}{60L^{3}}\cdot\frac{\sqrt{N^{(h)}_{i,j}(y)N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}.$

Similarly, we can prove that with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$ the following hold,
simultaneously for all $i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$,

$\begin{split}&\left|\left\|\phi_{i,j}^{(h)}(y)\right\|_{2}^{2}-\Gamma_{i,j,i,j}^{(h)}(y,y)\right|\leq\frac{(h+1)\varepsilon^{2}}{60L^{3}}\cdot\frac{N^{(h)}_{i,j}(y)}{q^{2}},\\\
&\left|\left\|\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2}-\Gamma_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(h)}(z,z)\right|\leq\frac{(h+1)\varepsilon^{2}}{60L^{3}}\cdot\frac{N^{(h)}_{i^{\prime},j^{\prime}}(z)}{q^{2}}.\end{split}$

This is sufficient to prove the inductive step for statement $P_{1}(h)$, i.e.,
$\Pr[P_{1}(h)|P_{1}(h-1)]\geq 1-\mathcal{O}(\delta/L)$.

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)$, $P_{2}(h)$ holds with
probability at least $1-\mathcal{O}(\delta/L)$. First, note that by ?? and
using ?? and union bound, we have the following simultaneously for all
$i,i^{\prime}\in[d_{1}]$ and all $j,j^{\prime}\in[d_{2}]$, with probability at
least $1-O\left(\frac{\delta}{L}\right)$,

$\left|\left<\dot{\phi}_{i,j}^{(h)}(y),\dot{\phi}_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\frac{1}{q^{2}}\sum_{l=0}^{2p^{\prime}+1}b_{l}\left<\left[Y^{(h)}_{i,j}(y)\right]_{l},\left[Y^{(h)}_{i^{\prime},j^{\prime}}(z)\right]_{l}\right>\right|\leq\mathcal{O}\left(\frac{\varepsilon}{L}\right)\widehat{A},$
(127)

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

$\displaystyle\left|\left<\left[Y^{(h)}_{i,j}(y)\right]_{l},\left[Y^{(h)}_{i^{\prime},j^{\prime}}(z)\right]_{l}\right>-\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>^{l}\right|\leq\mathcal{O}\left(\frac{\varepsilon}{L}\right)\cdot\left\|\mu_{i,j}^{(h)}(y)\right\|_{2}^{l}\left\|\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{l}$
$\displaystyle\left\|\left[Y^{(h)}_{i,j}(y)\right]_{l}\right\|_{2}^{2}\leq\frac{11}{10}\cdot\left\|\mu_{i,j}^{(h)}(y)\right\|_{2}^{2l}$
(128)
$\displaystyle\left\|\left[Y^{(h)}_{i^{\prime},j^{\prime}}(z)\right]_{l}\right\|_{2}^{2}\leq\frac{11}{10}\cdot\left\|\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2l}$

Therefore, by plugging ?? into ?? and using union bound and triangle
inequality as well as Cauchy–Schwarz inequality, we find that with probability
at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$, the following holds
simultaneously for all $i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$

$\left|\left<\dot{\phi}_{i,j}^{(h)}(y),\dot{\phi}_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\frac{1}{q^{2}}\cdot\dot{P}^{(p^{\prime})}_{\tt
relu}\left(\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>\right)\right|\leq\mathcal{O}\left(\frac{\varepsilon}{L}\right)\cdot\widehat{B},$
(129)

where $\widehat{B}:=\frac{1}{q^{2}}\cdot\sqrt{\dot{P}^{(p^{\prime})}_{\tt
relu}\left(\|\mu_{i,j}^{(h)}(y)\|_{2}^{2}\right)\cdot\dot{P}^{(p^{\prime})}_{\tt
relu}\left(\|\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\|_{2}^{2}\right)}$ and
$\dot{P}^{(p)}_{\tt
relu}(\alpha)=\sum_{l=0}^{2p^{\prime}+1}b_{l}\cdot\alpha^{l}$ is the
polynomial defined in ??. By conditioning on the inductive hypothesis
$P_{1}(h-1)$ and using ?? and ?? we have
$\left|\left\|\mu_{i,j}^{(h)}(y)\right\|_{2}^{2}-1\right|\leq
h\cdot\frac{\varepsilon^{2}}{60L^{3}}$ and
$\left|\left\|\mu_{i^{\prime},j^{\prime}}^{(h)}(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 by invoking
??, it follows that $\left|\dot{P}_{\tt
relu}^{(p^{\prime})}\left(\|\mu^{(h)}_{i,j}(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(\|\mu^{(h)}_{i^{\prime},j^{\prime}}(z)\|_{2}^{2}\right)-\dot{P}_{\tt
relu}^{(p^{\prime})}(1)\right|\leq\frac{h\cdot\varepsilon}{20L^{2}}$.
Consequently, because $\dot{P}_{\tt relu}^{(p^{\prime})}(1)\leq\dot{P}_{\tt
relu}^{(+\infty)}(1)=1$, we find that

$\widehat{B}\leq\frac{11}{10\cdot q^{2}}.$

By plugging this into ?? we get the following, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$,

$\left|\left<\dot{\phi}_{i,j}^{(h)}(y),\dot{\phi}_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\frac{1}{q^{2}}\cdot\dot{P}^{(p^{\prime})}_{\tt
relu}\left(\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>\right)\right|\leq\mathcal{O}\left(\frac{\varepsilon}{q^{2}\cdot
L}\right).$ (130)

Furthermore, recall the notation
$\gamma=\frac{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\Gamma_{i+a,j+b,i^{\prime}+a,j^{\prime}+b}^{(h-1)}\left(y,z\right)}{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}$ and note that by ?? and ??,
$-1\leq\gamma\leq 1$. Hence, we can invoke ?? and use the fact that
$p^{\prime}=\lceil 9L^{2}/\varepsilon^{2}\rceil$ to find that ?? implies the
following,

$\left|\dot{P}^{(p^{\prime})}_{\tt
relu}\left(\left<\mu_{i,j}^{(h)}(y),\mu_{i^{\prime},j^{\prime}}^{(h)}(z)\right>\right)-\dot{P}^{(p^{\prime})}_{\tt
relu}\left(\gamma\right)\right|\leq\frac{h\cdot\varepsilon}{20L^{2}}.$

By incorporating the above inequality into ?? using triangle inequality, we
find that, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$, the following holds
simultaneously for all $i,i^{\prime}\in[d_{1}]$ and all
$j,j^{\prime}\in[d_{2}]$:

$\left|\left<\dot{\phi}_{i,j}^{(h)}(y),\dot{\phi}_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\frac{1}{q^{2}}\cdot\dot{P}^{(p^{\prime})}_{\tt
relu}\left(\gamma\right)\right|\leq\mathcal{O}\left(\frac{\varepsilon}{q^{2}L^{2}}\right)+\frac{h}{q^{2}}\cdot\frac{\varepsilon}{20L^{2}}.$
(131)

Since $-1\leq\gamma\leq 1$, we can invoke ?? and use the fact that
$p^{\prime}=\left\lceil 9L^{2}/{\varepsilon}^{2}\right\rceil$ to conclude,

$\left|\dot{P}_{\tt
relu}^{(p^{\prime})}\left(\gamma\right)-\kappa_{0}\left(\gamma\right)\right|\leq\frac{\varepsilon}{15L}.$

By combining above inequality with ?? via triangle inequality and using the
fact that, by ??,
$\frac{1}{q^{2}}\cdot\kappa_{0}(\gamma)\equiv\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)$
we get the following bound simultaneously for all $i,i^{\prime}\in[d_{1}]$ and
all $j,j^{\prime}\in[d_{2}]$, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$:

$\left|\left<\dot{\phi}_{i,j}^{(h)}(y),\dot{\phi}_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\right|\leq\frac{1}{q^{2}}\cdot\frac{\varepsilon}{8L}.$
(132)

Similarly we can prove that with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$, the following hold
simultaneously for all $i,i^{\prime}\in[d_{1}]$ and all
$j,j^{\prime}\in[d_{2}]$,

$\left|\left\|\dot{\phi}_{i,j}^{(h)}(y)\right\|_{2}^{2}-\dot{\Gamma}_{i,j,i,j}^{(h)}(y,y)\right|\leq\frac{1}{q^{2}}\cdot\frac{\varepsilon}{8L},\text{
and
}\left|\left\|\dot{\phi}_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2}-\dot{\Gamma}_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(h)}(z,z)\right|\leq\frac{1}{q^{2}}\cdot\frac{\varepsilon}{8L}.$
(133)

We will use ?? and ?? to prove the inductive step for $P_{2}(h)$.

Next, we consider two cases for the value of $h$. When $h<L$, the vectors
$\psi_{i,j}^{(h)}(y),\psi_{i^{\prime},j^{\prime}}^{(h)}(z)$ are defined in ??
and when $h=L$, these vectors are defined differently in ??. First we consider
the case of $h<L$. Note that in this case, if we let $\eta_{i,j}^{(h)}(y)$ and
$\eta_{i^{\prime},j^{\prime}}^{(h)}(z)$ be the vectors defined in ??, then by
?? and union bound, the following holds simultaneously for all
$i,i^{\prime}\in[d_{1}]$ and all $j,j^{\prime}\in[d_{2}]$, with probability at
least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$:

$\left|\left<\psi_{i,j}^{(h)}(y),\psi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\left<\eta_{i+a,j+b}^{(h)}(y),\eta_{i^{\prime}+a,j^{\prime}+b}^{(h)}(z)\right>\right|\leq\mathcal{O}\left({\varepsilon}/{L}\right)\cdot
D,$ (134)

where
$D:=\sqrt{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\|\eta_{i+a,j+b}^{(h)}(y)\|_{2}^{2}}\cdot\sqrt{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\|\eta_{i^{\prime}+a,j^{\prime}+b}^{(h)}(z)\|_{2}^{2}}$.
Now, if we let
$f_{i,j}:=\psi^{(h-1)}_{i,j}(y)\otimes\dot{\phi}_{i,j}^{(h)}(y)$ and
$g_{i^{\prime},j^{\prime}}:=\psi^{(h-1)}_{i^{\prime},j^{\prime}}(z)\otimes\dot{\phi}_{i^{\prime},j^{\prime}}^{(h)}(z)$,
then by ??, $\eta_{i,j}^{(h)}(y)=\left({\bm{Q}}^{2}\cdot
f_{i,j}\right)\oplus\phi_{i,j}^{(h)}(y)$ and
$\eta_{i^{\prime},j^{\prime}}^{(h)}(z)=\left({\bm{Q}}^{2}\cdot
g_{i^{\prime},j^{\prime}}\right)\oplus\phi_{i^{\prime},j^{\prime}}^{(h)}(z)$.
Thus by ?? and union bound, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$, we have the following
inequalities simultaneously for all $i,i^{\prime}\in[d_{1}]$ and
$j,j^{\prime}\in[d_{2}]$:

$\displaystyle\left|\left<\eta^{(h)}_{i,j}(y),\eta^{(h)}_{i^{\prime},j^{\prime}}(z)\right>-\langle
f_{i,j},g_{i^{\prime},j^{\prime}}\rangle-\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>\right|\leq\mathcal{O}\left(\frac{\varepsilon}{L}\right)\cdot\left\|f_{i,j}\right\|_{2}\left\|g_{i^{\prime},j^{\prime}}\right\|_{2}$
$\displaystyle\left\|\eta^{(h)}_{i,j}(y)\right\|_{2}^{2}\leq\frac{11}{10}\cdot\|f_{i,j}\|_{2}^{2}+\left\|\phi_{i,j}^{(h)}(y)\right\|_{2}^{2}$
(135)
$\displaystyle\left\|\eta^{(h)}_{i^{\prime},j^{\prime}}(z)\right\|_{2}^{2}\leq\frac{11}{10}\cdot\|g_{i^{\prime},j^{\prime}}\|_{2}^{2}+\left\|\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2}$

Therefore, if we condition on inductive hypotheses $P_{1}(h)$ and
$P_{2}(h-1)$, then by using ??, ??, the inequality ?? and ?? along with the
fact that
$\|f_{i,j}\|_{2}^{2}=\|\psi^{(h-1)}_{i,j}(y)\|_{2}^{2}\cdot\|\dot{\phi}_{i,j}^{(h)}(y)\|_{2}^{2}$,
we have:

$\displaystyle\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\|\eta_{i+a,j+b}^{(h)}(y)\|_{2}^{2}$
$\displaystyle\qquad\leq\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{11}{10}\|f_{i+a,j+b}\|_{2}^{2}+\Gamma_{i+a,j+b,i+a,j+b}^{(h)}(y,y)+\frac{N_{i+a,j+b}^{(h)}(y)}{10q^{2}}$
$\displaystyle\qquad=\frac{11}{10}\cdot\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\|\psi^{(h-1)}_{i+a,j+b}(y)\|_{2}^{2}\cdot\|\dot{\phi}_{i+a,j+b}^{(h)}(y)\|_{2}^{2}+\Gamma_{i+a,j+b,i+a,j+b}^{(h)}(y,y)$
$\displaystyle\qquad\leq\frac{12}{10}\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\Pi^{(h-1)}_{i+a,j+b,i+a,j+b}(y,y)\cdot\dot{\Gamma}_{i+a,j+b,i+a,j+b}^{(h)}(y,y)+\Gamma_{i+a,j+b,i+a,j+b}^{(h)}(y,y)$
$\displaystyle\qquad=\frac{12}{10}\cdot\Pi^{(h)}_{i,j,i,j}(y,y)=\frac{12}{10}\cdot
h\cdot N^{(h+1)}_{i,j}(y),$

where the fourth line above follows from the inductive hypothesis $P_{2}(h-1)$
along with ?? and ?? and ??. The last line above follows from ?? and ??.
Similarly we can prove,
$\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\|\eta_{i^{\prime}+a,j^{\prime}+b}^{(h)}(z)\|_{2}^{2}\leq\frac{12}{10}\cdot
h\cdot N^{(h+1)}_{i^{\prime},j^{\prime}}(z)$, thus conditioned on
$P_{2}(h-1),P_{1}(h),P_{1}(h-1)$, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$:

$D\leq\frac{12}{10}\cdot h\cdot\sqrt{N^{(h+1)}_{i,j}(y)\cdot
N^{(h+1)}_{i^{\prime},j^{\prime}}(z)}.$

By incorporating this into ?? it follows that if we condition on
$P_{2}(h-1),P_{1}(h),P_{1}(h-1)$, then, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$, the following holds
simultaneously for all $i,i^{\prime}\in[d_{1}]$ and all
$j,j^{\prime}\in[d_{2}]$,

$\begin{split}&\left|\left<\psi_{i,j}^{(h)}(y),\psi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\left<\eta_{i+a,j+b}^{(h)}(y),\eta_{i^{\prime}+a,j^{\prime}+b}^{(h)}(z)\right>\right|\\\
&\qquad\qquad\leq\mathcal{O}\left(\varepsilon
h/{L}\right)\cdot\sqrt{N^{(h+1)}_{i,j}(y)\cdot
N^{(h+1)}_{i^{\prime},j^{\prime}}(z)}.\end{split}$ (136)

Now we bound the term
$\left|\left<\eta^{(h)}_{i,j}(y),\eta^{(h)}_{i^{\prime},j^{\prime}}(z)\right>-\langle
f_{i,j},g_{i^{\prime},j^{\prime}}\rangle-\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>\right|$
using ??, ??, and ?? along with inductive hypotheses $P_{2}(h-1)$ and ??. With
probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$ the
following holds simultaneously for all $i,i^{\prime}\in[d_{1}]$ and all
$j,j^{\prime}\in[d_{2}]$:

$\begin{split}&\left|\left<\eta^{(h)}_{i,j}(y),\eta^{(h)}_{i^{\prime},j^{\prime}}(z)\right>-\langle
f_{i,j},g_{i^{\prime},j^{\prime}}\rangle-\left<\phi_{i,j}^{(h)}(y),\phi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>\right|\\\
&\qquad\leq\mathcal{O}\left(\frac{\varepsilon}{L}\right)\cdot\sqrt{\Pi_{i,j,i,j}^{(h-1)}(y,y)\cdot\dot{\Gamma}_{i,j,i,j}^{(h)}(y,y)\cdot\Pi_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(h-1)}(z,z)\cdot\dot{\Gamma}_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(h)}(z,z)}\\\
&\qquad=\mathcal{O}\left(\frac{\varepsilon\cdot
h}{L}\right)\cdot\frac{\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}}{q^{2}},\end{split}$

where the last line above follows from ?? together with the fact that
$\dot{\Gamma}_{i,j,i,j}^{(h)}(y,y)=\dot{\Gamma}_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(h)}(z,z)=\frac{1}{q^{2}}$.

By combining the above with inductive hypotheses $P_{1}(h),P_{2}(h-1)$ and ??
via triangle inequality and invoking ?? we get that the following holds
simultaneously for all $i,i^{\prime}\in[d_{1}]$ and all
$j,j^{\prime}\in[d_{2}]$, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$,

$\displaystyle\left|\left<\eta^{(h)}_{i,j}(y),\eta^{(h)}_{i^{\prime},j^{\prime}}(z)\right>-\Pi_{i,j,i^{\prime},j^{\prime}}^{(h-1)}(y,z)\cdot\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)-\Gamma_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\right|$
$\displaystyle\leq\frac{\varepsilon}{10}\cdot\frac{(h-1)^{2}}{L+1}\cdot\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}\cdot\left(\left|\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\right|+\frac{1}{q^{2}}\cdot\frac{\varepsilon}{8L}\right)+\frac{1}{q^{2}}\cdot\frac{\varepsilon}{8L}\cdot\left|\Pi_{i,j,i^{\prime},j^{\prime}}^{(h-1)}(y,z)\right|$
$\displaystyle+\frac{(h+1)\cdot\varepsilon^{2}}{60L^{3}}\cdot\frac{\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}}{q^{2}}+\mathcal{O}\left(\frac{\varepsilon\cdot
h}{L}\right)\cdot\frac{\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}}{q^{2}}$
$\displaystyle\leq\frac{\varepsilon}{10}\cdot\frac{(h-1)^{2}}{L+1}\cdot\frac{\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}}{q^{2}}\cdot\left(1+\frac{\varepsilon}{8L}\right)+\frac{h-1}{q^{2}}\cdot\frac{\varepsilon}{8L}\cdot\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}$
$\displaystyle+\left(\frac{(h+1)\cdot\varepsilon^{2}}{60L^{3}}+\mathcal{O}\left(\frac{\varepsilon\cdot
h}{L}\right)\right)\cdot\frac{\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}}{q^{2}}$
$\displaystyle\leq\frac{\varepsilon}{10}\cdot\frac{h^{2}-h/2}{L+1}\cdot\frac{\sqrt{N_{i,j}^{(h)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h)}(z)}}{q^{2}}.$

By plugging the above bound into ?? using triangle inequality and using ?? we
get the following, with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$:

$\begin{split}&\left|\left<\psi_{i,j}^{(h)}(y),\psi_{i^{\prime},j^{\prime}}^{(h)}(z)\right>-\Pi_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\right|\\\
&\leq\mathcal{O}\left(\varepsilon
h/{L}\right)\cdot\sqrt{N^{(h+1)}_{i,j}(y)\cdot
N^{(h+1)}_{i^{\prime},j^{\prime}}(z)}\\\
&\qquad+\frac{\varepsilon}{10}\cdot\frac{h^{2}-h/2}{L+1}\cdot\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{\sqrt{N_{i+a,j+b}^{(h)}(y)\cdot
N_{i^{\prime}+a,j^{\prime}+b}^{(h)}(z)}}{q^{2}}\\\
&\leq\mathcal{O}\left(\varepsilon
h/{L}\right)\cdot\sqrt{N^{(h+1)}_{i,j}(y)\cdot
N^{(h+1)}_{i^{\prime},j^{\prime}}(z)}\\\
&\qquad+\frac{\varepsilon}{10}\cdot\frac{h^{2}-h/2}{L+1}\cdot\sqrt{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{N_{i+a,j+b}^{(h)}(y)}{q^{2}}}\cdot\sqrt{\sum_{a=-\frac{q-1}{2}}^{\frac{q-1}{2}}\sum_{b=-\frac{q-1}{2}}^{\frac{q-1}{2}}\frac{N_{i^{\prime}+a,j^{\prime}+b}^{(h)}(z)}{q^{2}}}\\\
&\leq\frac{\varepsilon}{10}\cdot\frac{h^{2}}{L+1}\cdot\sqrt{N^{(h+1)}_{i,j}(y)\cdot
N^{(h+1)}_{i^{\prime},j^{\prime}}(z)}.\end{split}$ (137)

Similarly, we can prove that with probability at least
$1-\mathcal{O}\left(\frac{\delta}{L}\right)$ the following hold simultaneously
for all $i,i^{\prime}\in[d_{1}]$ and all $j,j^{\prime}\in[d_{2}]$,

$\begin{split}&\left|\left\|\psi_{i,j}^{(h)}(y)\right\|_{2}^{2}-\Pi_{i,j,i,j}^{(h)}(y,y)\right|\leq\frac{\varepsilon}{10}\cdot\frac{h^{2}}{L+1}\cdot
N^{(h+1)}_{i,j}(y),\\\
&\left|\left\|\psi_{i^{\prime},j^{\prime}}^{(h)}(z)\right\|_{2}^{2}-\Pi_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(h)}(z,z)\right|\leq\frac{\varepsilon}{10}\cdot\frac{h^{2}}{L+1}\cdot
N^{(h+1)}_{i^{\prime},j^{\prime}}(z).\end{split}$

This is sufficient to prove the inductive step for statement $P_{2}(h)$, in
the case of $h<L$, i.e., $\Pr[P_{2}(h)|P_{2}(h-1),P_{1}(h),P_{1}(h-1)]\geq
1-\mathcal{O}(\delta/L)$.

Now we prove the inductive step for $P_{2}(h)$ in the case of $h=L$. Similar
to before, if we let
$f_{i,j}:=\psi^{(L-1)}_{i,j}(y)\otimes\dot{\phi}_{i,j}^{(L)}(y)$ and
$g_{i^{\prime},j^{\prime}}:=\psi^{(L-1)}_{i^{\prime},j^{\prime}}(z)\otimes\dot{\phi}_{i^{\prime},j^{\prime}}^{(L)}(z)$,
then by ??, we have $\psi_{i,j}^{(L)}(y)={\bm{Q}}^{2}\cdot f_{i,j}$ and
$\psi_{i^{\prime},j^{\prime}}^{(L)}(z)={\bm{Q}}^{2}\cdot
g_{i^{\prime},j^{\prime}}$. Thus by ?? and union bound, we find that, with
probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$, the
following inequality holds simultaneously for all $i,i^{\prime}\in[d_{1}]$ and
$j,j^{\prime}\in[d_{2}]$:

$\left|\left<\psi^{(L)}_{i,j}(y),\psi^{(L)}_{i^{\prime},j^{\prime}}(z)\right>-\langle
f_{i,j},g_{i^{\prime},j^{\prime}}\rangle\right|\leq\mathcal{O}\left(\frac{\varepsilon}{L}\right)\cdot\left\|f_{i,j}\right\|_{2}\left\|g_{i^{\prime},j^{\prime}}\right\|_{2}.$

Therefore, using ?? and ?? along with inductive hypotheses $P_{2}(L-1)$ and
??, with probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$,
the following holds simultaneously for all $i,i^{\prime}\in[d_{1}]$ and
$j,j^{\prime}\in[d_{2}]$,

$\begin{split}\left|\left<\psi^{(L)}_{i,j}(y),\psi^{(L)}_{i^{\prime},j^{\prime}}(z)\right>-\langle
f_{i,j},g_{i^{\prime},j^{\prime}}\rangle\right|&\leq\mathcal{O}\left(\frac{\varepsilon}{L}\right)\sqrt{\Pi_{i,j,i,j}^{(L-1)}(y,y)\cdot\dot{\Gamma}_{i,j,i,j}^{(L)}(y,y)\cdot\Pi_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(L-1)}(z,z)\cdot\dot{\Gamma}_{i^{\prime},j^{\prime},i^{\prime},j^{\prime}}^{(L)}(z,z)}\\\
&=\mathcal{O}\left({\varepsilon}\right)\cdot\frac{\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}}{q^{2}}.\end{split}$

By combining the above with inductive hypotheses $P_{1}(L),P_{2}(L-1)$ and ??
via triangle inequality and invoking ?? and also using the definition of
$\Pi^{(L)}(y,z)$ given in ??, we get that the following holds, simultaneously
for all $i,i^{\prime}\in[d_{1}]$ and $j,j^{\prime}\in[d_{2}]$, with
probability at least $1-\mathcal{O}\left(\frac{\delta}{L}\right)$,

$\displaystyle\left|\left<\psi^{(L)}_{i,j}(y),\psi^{(L)}_{i^{\prime},j^{\prime}}(z)\right>-\Pi_{i,j,i^{\prime},j^{\prime}}^{(L)}(y,z)\right|$
$\displaystyle\leq\frac{\varepsilon}{10}\cdot\frac{(L-1)^{2}}{L+1}\cdot\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}\cdot\left(\left|\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(L)}(y,z)\right|+\frac{1}{q^{2}}\cdot\frac{\varepsilon}{8L}\right)+\frac{1}{q^{2}}\cdot\frac{\varepsilon}{8L}\cdot\left|\Pi_{i,j,i^{\prime},j^{\prime}}^{(L-1)}(y,z)\right|$
$\displaystyle+\frac{(L+1)\cdot\varepsilon^{2}}{60L^{3}}\cdot\frac{\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}}{q^{2}}+\mathcal{O}\left({\varepsilon}\right)\cdot\frac{\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}}{q^{2}}$
$\displaystyle\leq\frac{\varepsilon}{10}\cdot\frac{(L-1)^{2}}{L+1}\cdot\frac{\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}}{q^{2}}\cdot\left(1+\frac{\varepsilon}{8L}\right)+\frac{\varepsilon}{8q^{2}}\cdot\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}$
$\displaystyle+\left(\frac{(L+1)\cdot\varepsilon^{2}}{60L^{3}}+\mathcal{O}\left({\varepsilon}\right)\right)\cdot\frac{\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}}{q^{2}}$
$\displaystyle\leq\frac{\varepsilon\cdot(L-1)}{10}\cdot\frac{\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}}{q^{2}}.$

This proves the inductive step for statement $P_{2}(h)$, in the case of $h=L$,
i.e., $\Pr[P_{2}(L)|P_{2}(L-1),P_{1}(L),P_{1}(L-1)]\geq
1-\mathcal{O}(\delta/L)$. The induction is complete and hence the statements
of lemma are proved by union bounding over all $h=0,1,2,\ldots L$. This
completes the proof of ??. ∎

In the following lemma we analyze the runtime of the CNTK Sketch algorithm,

######  Lemma 15 (Runtime of the CNTK Sketch).

For every positive integers $d_{1},d_{2},c$, and $L$, every
$\varepsilon,\delta>0$, every image $x\in\mathbb{R}^{d_{1}\times d_{2}\times
c}$, the time to compute the CNTK Sketch $\Psi_{\tt
cntk}^{(L)}(x)\in\mathbb{R}^{s^{*}}$, for
$s^{*}=\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\cdot\log\frac{1}{\delta}\right)$,
using the procedure given in ?? is bounded by
$\mathcal{O}\left(\frac{L^{11}}{\varepsilon^{6.7}}\cdot(d_{1}d_{2})\cdot\log^{3}\frac{d_{1}d_{2}L}{\varepsilon\delta}\right)$.

Proof of ??: First note that the total time to compute $N_{i,j}^{(h)}(x)$ for
all $i\in[d_{1}]$ and $j\in[d_{2}]$ and $h=0,1,\ldots L$ as per ?? is bounded
by $\mathcal{O}\left(q^{2}L\cdot d_{1}d_{2}\right)$. Besides the time to
compute $N_{i,j}^{(h)}(x)$, there are two other main components to the runtime
of this procedure. The first heavy operation corresponds to computing vectors
$\left[Z_{i,j}^{(h)}(x)\right]_{l}={\bm{Q}}^{2p+2}\cdot\left(\left[\mu_{i,j}^{(h)}(x)\right]^{\otimes
l}\otimes{e}_{1}^{\otimes 2p+2-l}\right)$ for $l=0,1,2,\ldots 2p+2$ and
$h=1,2,\ldots L$ and all indices $i\in[d_{1}]$ and $j\in[d_{2}]$, in ??. By
??, the time to compute $\left[Z_{i,j}^{(h)}(x)\right]_{l}$ for a fixed $h$,
fixed $i\in[d_{1}]$ and $j\in[d_{2}]$, and all $l=0,1,2,\ldots 2p+2$ is
bounded by,

$\mathcal{O}\left(\frac{L^{10}}{\varepsilon^{20/3}}\cdot\log^{2}\frac{L}{\varepsilon}\cdot\log^{3}\frac{d_{1}d_{2}L}{\varepsilon\delta}+q^{2}\cdot\frac{L^{8}}{\varepsilon^{16/3}}\cdot\log^{3}\frac{d_{1}d_{2}L}{\varepsilon\delta}\right)=\mathcal{O}\left(\frac{L^{10}}{\varepsilon^{6.7}}\cdot\log^{3}\frac{d_{1}d_{2}L}{\varepsilon\delta}\right).$

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

$\mathcal{O}\left(\frac{L^{6}}{\varepsilon^{6}}\cdot\log^{2}\frac{L}{\varepsilon}\log^{3}\frac{d_{1}d_{2}L}{\varepsilon\delta}+\frac{q^{2}\cdot
L^{8}}{\varepsilon^{6}}\cdot\log^{3}\frac{d_{1}d_{2}L}{\varepsilon\delta}\right)=\mathcal{O}\left(\frac{L^{8}}{\varepsilon^{6}}\log^{2}\frac{L}{\varepsilon}\cdot\log^{3}\frac{d_{1}d_{2}L}{\varepsilon\delta}\right).$

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

Now we are ready to prove ??. See 4 Proof of ??: Let
$\psi^{(L)}:\mathbb{R}^{d_{1}\times d_{2}\times c}\to\mathbb{R}^{d_{1}\times
d_{2}\times s}$ for
$s=\mathcal{O}\left(\frac{L^{4}}{\varepsilon^{2}}\cdot\log^{3}\frac{d_{1}d_{2}L}{\varepsilon\delta}\right)$
be the mapping defined in ?? of ??. By ??, the CNTK Sketch $\Psi_{\tt
cntk}^{(L)}(x)$ is defined as

$\Psi_{ntk}^{(L)}(x):=\frac{1}{d_{1}d_{2}}\cdot{\bm{G}}\cdot\left(\sum_{i\in[d_{1}]}\sum_{j\in[d_{2}]}\psi^{(L)}_{i,j}(x)\right).$

The matrix ${\bm{G}}$ is defined in ?? to be a matrix of i.i.d. normal entries
with $s^{*}=C\cdot\frac{1}{\varepsilon^{2}}\cdot\log\frac{1}{\delta}$ rows for
large enough constant $C$. [15] shows that ${\bm{G}}$ is a JL transform and
hence $\Psi_{\tt cntk}^{(L)}$ satisfies the following,

$\Pr\left[\left|\left<\Psi_{\tt cntk}^{(L)}(y),\Psi_{\tt
cntk}^{(L)}(z)\right>-\frac{1}{d_{1}^{2}d_{2}^{2}}\cdot\sum_{i,i^{\prime}\in[d_{1}]}\sum_{j,j^{\prime}\in[d_{2}]}\left<\psi_{i,j}^{(L)}(y),\psi_{i^{\prime},j^{\prime}}^{(L)}(z)\right>\right|\leq\mathcal{O}(\varepsilon)\cdot
A\right]\geq 1-\mathcal{O}(\delta),$

where
$A:=\frac{1}{d_{1}^{2}d_{2}^{2}}\cdot\left\|\sum_{i\in[d_{1}]}\sum_{j\in[d_{2}]}\psi_{i,j}^{(L)}(y)\right\|_{2}\cdot\left\|\sum_{i\in[d_{1}]}\sum_{j\in[d_{2}]}\psi_{i,j}^{(L)}(z)\right\|_{2}$.
By triangle inequality together with ?? and ??, the following bounds hold with
probability at least $1-\mathcal{O}(\delta)$:

$\begin{split}&\left\|\sum_{i\in[d_{1}]}\sum_{j\in[d_{2}]}\psi_{i,j}^{(L)}(y)\right\|_{2}\leq\frac{11}{10}\cdot\frac{\sqrt{L-1}}{q}\cdot\sum_{i\in[d_{1}]}\sum_{j\in[d_{2}]}\sqrt{N^{(L)}_{i,j}(y)},\\\
&\left\|\sum_{i\in[d_{1}]}\sum_{j\in[d_{2}]}\psi_{i,j}^{(L)}(z)\right\|_{2}\leq\frac{11}{10}\cdot\frac{\sqrt{L-1}}{q}\cdot\sum_{i\in[d_{1}]}\sum_{j\in[d_{2}]}\sqrt{N^{(L)}_{i,j}(z)},\end{split}$

Therefore, by union bound we find that, with probability at least
$1-\mathcal{O}(\delta)$:

$\begin{split}&\left|\left<\Psi_{\tt cntk}^{(L)}(y),\Psi_{\tt
cntk}^{(L)}(z)\right>-\frac{1}{d_{1}^{2}d_{2}^{2}}\cdot{\sum_{i,i^{\prime}\in[d_{1}]}\sum_{j,j^{\prime}\in[d_{2}]}\left<\psi_{i,j}^{(L)}(y),\psi_{i^{\prime},j^{\prime}}^{(L)}(z)\right>}\right|\\\
&\qquad\leq\mathcal{O}\left(\frac{\varepsilon L}{q^{2}\cdot
d_{1}^{2}d_{2}^{2}}\right)\cdot\sum_{i,i^{\prime}\in[d_{1}]}\sum_{j,j^{\prime}\in[d_{2}]}\sqrt{N^{(L)}_{i,j}(y)\cdot
N^{(L)}_{i^{\prime},j^{\prime}}(z)}.\end{split}$

Be combining the above with ?? using triangle inequality and union bound and
also using ??, the following holds with probability at least
$1-\mathcal{O}(\delta)$:

$\left|\left<\Psi_{\tt cntk}^{(L)}(y),\Psi_{\tt
cntk}^{(L)}(z)\right>-\Theta_{\tt
cntk}^{(L)}(y,z)\right|\leq\frac{\varepsilon\cdot(L-1)}{9q^{2}\cdot
d_{1}^{2}d_{2}^{2}}\cdot\sum_{i,i^{\prime}\in[d_{1}]}\sum_{j,j^{\prime}\in[d_{2}]}\sqrt{N^{(L)}_{i,j}(y)\cdot
N^{(L)}_{i^{\prime},j^{\prime}}(z)}.$ (138)

Now we prove that $\Theta_{\tt
cntk}^{(L)}(y,z)\geq\frac{L-1}{9q^{2}d_{1}^{2}d_{2}^{2}}\cdot\sum_{i,i^{\prime}\in[d_{1}]}\sum_{j,j^{\prime}\in[d_{2}]}\sqrt{N^{(L)}_{i,j}(y)\cdot
N^{(L)}_{i^{\prime},j^{\prime}}(z)}$ for every $L\geq 2$. First note that, it
follows from ?? that $\Gamma_{i,j,i^{\prime},j^{\prime}}^{(1)}(y,z)\geq 0$ for
any $i,i^{\prime},j,j^{\prime}$ because the function $\kappa_{1}$ is non-
negative everywhere on $[-1,1]$. This also implies that
$\Gamma_{i,j,i^{\prime},j^{\prime}}^{(2)}(y,z)\geq\frac{\sqrt{N^{(2)}_{i,j}(y)\cdot
N^{(2)}_{i^{\prime},j^{\prime}}(z)}}{\pi\cdot q^{2}}$ because
$\kappa_{1}(\alpha)\geq\frac{1}{\pi}$ for every $\alpha\in[0,1]$. Since,
$\kappa_{1}(\cdot)$ is a monotone increasing function, by recursively using ??
and ?? along with ??, we can show that for every $h\geq 1$, the value of
$\Gamma_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)$ is lower bounded by
$\frac{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\Sigma_{\tt relu}^{(h)}(-1)$,
where $\Sigma_{\tt relu}^{(h)}:[-1,1]\to\mathbb{R}$ is the function defined in
??.

Furthermore, it follows from ?? that
$\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(1)}(y,z)\geq 0$ for any
$i,i^{\prime},j,j^{\prime}$ because the function $\kappa_{0}$ is non-negative
everywhere on $[-1,1]$. Additionally,
$\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(2)}(y,z)\geq\frac{1}{2q^{2}}$
because $\kappa_{0}(\alpha)\geq\frac{1}{2}$ for every $\alpha\in[0,1]$. By
using the inequality
$\Gamma_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\geq\frac{\sqrt{N^{(h)}_{i,j}(y)\cdot
N^{(h)}_{i^{\prime},j^{\prime}}(z)}}{q^{2}}\cdot\Sigma_{\tt relu}^{(h)}(-1)$
that we proved above along with the fact that $\kappa_{0}(\cdot)$ is a
monotone increasing function and recursively using ?? and ??, it follows that
for every $h\geq 1$, we have
$\dot{\Gamma}_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\geq\frac{1}{q^{2}}\cdot\dot{\Sigma}_{\tt
relu}^{(h)}(-1)$.

By using these inequalities and Definition of $\Pi^{(h)}$ in ?? together with
??, recursively, it follows that, for every $i,i^{\prime},j,j^{\prime}$ and
$h=2,\ldots L-1$:

$\displaystyle\Pi_{i,j,i^{\prime},j^{\prime}}^{(h)}(y,z)\geq\frac{h}{4}\cdot\sqrt{N_{i,j}^{(h+1)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(h+1)}(z)},$

Therefore, using this inequality and ?? we have that for every $L\geq 2$:

$\displaystyle\Pi_{i,j,i^{\prime},j^{\prime}}^{(L)}(y,z)$
$\displaystyle\geq\frac{L-1}{4}\cdot\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}\cdot\frac{\dot{\Sigma}_{\tt
relu}^{(L)}(-1)}{q^{2}}$
$\displaystyle\geq\frac{L-1}{9q^{2}}\cdot\sqrt{N_{i,j}^{(L)}(y)\cdot
N_{i^{\prime},j^{\prime}}^{(L)}(z)}.$

Now using this inequality and ??, the following holds for every $L\geq 2$:

$\Theta_{\tt
cntk}^{(L)}(y,z)\geq\frac{L-1}{9q^{2}d_{1}^{2}d_{2}^{2}}\cdot\sum_{i,i^{\prime}\in[d_{1}]}\sum_{j,j^{\prime}\in[d_{2}]}\sqrt{N^{(L)}_{i,j}(y)\cdot
N^{(L)}_{i^{\prime},j^{\prime}}(z)}.$

Therefore, by incorporating the above into ?? we get that,

$\Pr\left[\left|\left<\Psi_{\tt cntk}^{(L)}(y),\Psi_{\tt
cntk}^{(L)}(z)\right>-\Theta_{\tt
cntk}^{(L)}(y,z)\right|\leq\varepsilon\cdot\Theta_{\tt
cntk}^{(L)}(y,z)\right]\geq 1-\delta.$

Runtime analysis: By ??, time to compute the CNTK Sketch is
$\mathcal{O}\left(\frac{L^{11}}{\varepsilon^{6.7}}\cdot(d_{1}d_{2})\cdot\log^{3}\frac{d_{1}d_{2}L}{\varepsilon\delta}\right)$.

This completes the proof of ??. ∎