$\displaystyle\leq\sum_{i=1}^{I}\eta_{i}\big{\|}\psi_{i}\otimes\psi_{i}-\widehat{\psi}_{i}\otimes\widehat{\psi}_{i}\big{\|}_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}$
$\displaystyle\leq\sum_{i=1}^{I}\eta_{i}\,\Bigg{\\{}2M\frac{\epsilon}{{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{1}(4M+2)}+\bigg{(}\frac{\epsilon}{{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{1}(4M+2)}\bigg{)}^{2}\Bigg{\\}}~{}~{}~{}~{}\text{(by
\eqref{eq:universal_approximation_bound_L2} and
\eqref{eq:product_difference_bound_L2})}$
$\displaystyle\leq\sum_{i=1}^{I}\eta_{i}\frac{\epsilon}{{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{1}(4M+2)}(2M+1)~{}~{}~{}~{}~{}(\text{since
}\epsilon<1)$
$\displaystyle=\frac{\epsilon}{2{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|C\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{1}}\sum_{i=1}^{I}\eta_{i}\leq\frac{\epsilon}{2}.$
(B.6)

Finally, combining (B.2) and (B.1), we get

$\displaystyle\|c-\widehat{c}_{R}\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\leq\|c-c_{I}\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}+\|c_{I}-\widehat{c}_{R}\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\leq\epsilon,$

as intended.

Now, if in addition $c$ is continuous, then it admits a similar decomposition
as in (B.1), where the sum converges absolutely and uniformly (Hsing and
Eubank, 2015, Theorem 4.6.5). So, we can find an integer $I$ such that

$\bigg{\|}c-\sum_{i=1}^{I}\eta_{i}\,\psi_{i}\otimes\psi_{i}\bigg{\|}_{\mathcal{L}_{\infty}(\mathcal{Q}\times\mathcal{Q})}<\frac{\epsilon}{2}.$

Also, the eigenfunctions $\psi_{1},\ldots,\psi_{I}$ are now continuous on a
compact set $\mathcal{Q}$. So, there exists a positive constant $M$ such that
$\max_{i=1,\ldots,I}\|\psi_{i}\|_{\mathcal{L}_{\infty}(\mathcal{Q})}\leq M$.
Since $\sigma$ is a sigmoidal function, we can find neural networks
$\widehat{\psi}_{i}$ of the form (B.3) such that

$\|\psi_{i}-\widehat{\psi}_{i}\|_{\mathcal{L}_{\infty}(\mathcal{Q})}<\frac{\epsilon}{{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{1}(4M+2)},$

see Lemma 16.1 in Györfi et al. (2002). The rest of the proof follows
similarly to the previous case upon using a bound similar to (B.5) for the
$\mathcal{L}_{\infty}$ norm. ∎

Next, we briefly discuss the universal approximation property of the deep and
the deepshared models.

###### Proof of Theorem 2.

Recall that the deep CovNet kernel is of the form

$c_{\rm d}(\text{\bf u},\text{\bf
v})=\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,g_{r}(\text{\bf
u})\,g_{s}(\text{\bf v}),$

where each of the functions $g_{1},\ldots,g_{R}$ are individual deep neural
networks. To prove the universal approximation property of this structure, we
proceed similarly to the case of the shallow CovNet structure. Namely, we
decompose $c$ as

$c(\text{\bf u},\text{\bf v})=\sum_{i=1}^{I}\eta_{i}\,\psi_{i}(\text{\bf
u})\,\psi_{i}(\text{\bf v})+\sum_{i=I+1}^{\infty}\eta_{i}\,\psi_{i}(\text{\bf
u})\,\psi_{i}(\text{\bf v})=:c_{I}(\text{\bf u},\text{\bf v})+e_{I}(\text{\bf
u},\text{\bf v}),$

where
$\|c-c_{I}\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\leq\epsilon/2$.
Now, for each $i=1,\ldots,I$, we can find deep neural network
$\widehat{\psi}_{i}=\sum_{r=1}^{R_{i}}a_{i,r}\,g_{i,r}(\cdot)$ of the required
form such that $\|\psi_{i}-\widehat{\psi}_{i}\|<\delta$ (follows from the
universal approximation property of the deep neural network with sigmoid
activation, see Funahashi (1989)). Also, the depth of all these networks can
be taken to be the same (see Funahashi, 1989, Corollary 1). Now, by defining
$\widehat{c}_{R}(\text{\bf u},\text{\bf
v})=\sum_{i=1}^{I}\eta_{i}\,\widehat{\psi}_{i}(\text{\bf
u})\,\widehat{\psi}_{i}(\text{\bf v})$, it is easy to verify that
$\widehat{c}_{R}$ has the deep CovNet structure and approximates $c$ up to the
desired precision.

Next, consider the deepshared structure. Observe that for any deep CovNet
kernel with depth $L$ and number of nodes $R$, we can find a deepshared CovNet
kernel with depth $L$ and number of nodes $R^{\prime}$, such that the two
structures are the same (by considering a wider network and deleting some of
the connections, see Figures 2 and 3). Thus, for a fixed depth, the complexity
of the deep and the deepshared structures is the same (when we allow the
number of nodes to vary). Thus, the result for the deepshared CovNet model
follows from the universal approximation of the deep CovNet model. ∎

######  Remark 11.

The results that we have proved establish the universal approximation property
of the three CovNet models without any restriction on the parameters. But, to
establish consistency of the estimators and their rates of convergence
(Section 6), we need to impose restrictions on the eigenstructure of the
matrix $\Lambda$. Therefore, we need to control the bias for this restricted
class of operators. The universal approximation property for the restricted
class follows easily. By the universal approximation property of the
unrestricted class, for a given $\mathcal{C}$ and $\epsilon>0$, we can find a
CovNet operator $\mathcal{G}$ (of any of the three types) such that
${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}<\epsilon$.
Now, let $\Lambda$ be the matrix associated with $\mathcal{G}$. Since
$\Lambda$ is a positive semi-definite matrix, we can find $\lambda_{0}>0$ such
that $\Lambda\preceq\lambda_{0}\,\mathrm{I}$ (e.g., by takings $\lambda_{0}$
to be the largest eigenvalue of $\Lambda$). This shows that for any
$\mathcal{C}$, we can find a CovNet operator from the restricted class that
can approximate $\mathcal{C}$ up to arbitrary precision, thus establishing the
universal approximation property with the additional condition.

###  B.2 Rate of convergence of the bias term

Here, we will derive the rate of convergence of the bias for the (possibly
restricted) class of CovNet operators. We will describe two possible ways to
obtain the rates – (a) by imposing conditions on the eigenstructure of
$\mathcal{C}$ or (b) by imposing conditions on the observation $\mathcal{X}$.

####  B.2.1 Restrictions on the covariance

By the eigendecomposition, we can write
$\mathcal{C}=\sum_{i=1}^{\infty}\eta_{i}\,\psi_{i}\otimes\psi_{i}$, where
$(\eta_{i})_{i\geq 1}$ is the sequence of non-increasing eigenvalues of
$\mathcal{C}$ and $(\psi_{i})_{i\geq 1}$ is the corresponding sequence of
eigenfunctions. For $I\in\mathbb{N}$, define
$\mathcal{C}_{I}=\sum_{i=1}^{I}\eta_{i}\,\psi_{i}\otimes\psi_{i}$ to be the
truncated version of $\mathcal{C}$. Then,

${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\mathcal{C}_{I}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}=\sum_{i>I}\eta_{i}^{2}=\mathcal{O}(a_{I}),$

where $a_{I}$ depends on the _eigen-decay_ of $\mathcal{C}$. Now, for each
$i=1,\ldots,I$, suppose that we can find (shallow/deep/deepshared) neural
networks $\widehat{\psi}_{1},\ldots,\widehat{\psi}_{K}$ such that

$\|\psi_{i}-\widehat{\psi}_{i}\|=\mathcal{O}(b_{L_{i},R_{i}}),\qquad
i=1,\ldots,I,$

where $L_{i},R_{i}$ are the parameters (depth and/or width) of
$\widehat{\psi}_{i}$. The rate of the approximation error $b_{L_{i},R_{i}}$
depends on additional structural assumptions on the eigenfunctions (e.g.,
Mhaskar, 1996; Bauer and Kohler, 2019; Ohn and Kim, 2019; Schmidt-Hieber,
2020; Langer, 2021), which can be imposed by means of additional structural
assumptions on the kernel $c$. Now, if we define
$\widehat{\mathcal{C}}=\sum_{i=1}^{I}\eta_{i}\,\widehat{\psi}_{i}\otimes\widehat{\psi}_{i}$,
then it is easy to see that $\widehat{\mathcal{C}}$ is a CovNet operator with
$R$ nodes (and possibly of depth $L$) such that

${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\leq
2\Big{\\{}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\mathcal{C}_{I}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}+{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}_{I}-\widehat{\mathcal{C}}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{\\}}=\mathcal{O}(a_{I})+\mathcal{O}(b_{I,L,R}),$

where $b_{I,L,R}$ can be obtained from the $b_{L_{i},R_{i}}$’s using (B.5).
Here, the parameters $R$ and $L$ of the CovNet operator depend on
$I,L_{i},R_{i}$. Finally, the exact rate of convergence of the bias term can
be obtained by carefully scrutinizing the terms $a_{I}$ and $b_{I,L,R}$ as
functions of $I,L,R$, and choosing $I$ appropriately.

####  B.2.2 Restrictions on the observations

The idea here is similar to the one used before. Instead of the
eigendecomposition, we will make use of a different type of approximation
result. The following lemma will be instrumental in our derivation, which is a
suitable adaptation of Lemma 16.7 in Györfi et al. (2002). The proof follows
easily from the proof of Lemma 16.7 in Györfi et al. (2002), so we omit it.

######  Lemma 1.

Let $\mathcal{T}$ be an index set, and $\\{\phi_{t}:t\in\mathcal{T}\\}$ be a
collection of real-valued functions on a compact domain $\mathcal{Q}$ such
that $\|\phi_{t}\|\leq B$ for all $t\in\mathcal{T}$. Let
$f:\mathcal{Q}\to\mathbb{R}$ be a function such that there exists a
probability measure $b$ on $\mathcal{T}$ satisfying

$f(\text{\bf u})=\int_{\mathcal{Q}}\phi_{t}(\text{\bf
u})\,\mathrm{d}\mu(t)\quad\forall\,\text{\bf u}\in\mathcal{Q}.$

Then, for every $I\in\mathbb{N}$, there exists a function $f_{I}(\text{\bf
u})=\sum_{i=1}^{I}w_{i}\phi_{t_{i}}(\text{\bf u})$ such that

$\|f-f_{I}\|\leq\frac{B}{\sqrt{I}}.$

Moreover, the coefficients $w_{i}$ are non-negative and
$\sum_{i=1}^{I}w_{i}=1$.

Now, suppose that the random field $\mathcal{X}$ satisfies
$\mathbb{P}(\|\mathcal{X}\|^{2}\leq\beta)=1$. Recall that the covariance
kernel $c$ of $\mathcal{X}=(X(\text{\bf u}):\text{\bf u}\in\mathcal{Q})$ is
defined as

$c(\text{\bf u},\text{\bf v})=\mathrm{Cov}(X(\text{\bf u}),X(\text{\bf
v}))=\mathbb{E}(X(\text{\bf u})X(\text{\bf v}))=\int_{\Omega}X(\text{\bf
u},\omega)X(\text{\bf v},\omega)\,\mathrm{d}\mathbb{P}(\omega),\quad\text{\bf
u},\text{\bf v}\in\mathcal{Q},$

for some set $\Omega$ and the probability measure $\mathbb{P}$ on $\Omega$.
Thus, by defining $\mathcal{T}=\Omega$ and $\phi_{\omega}(\text{\bf
u},\text{\bf v})=X(\text{\bf u},\omega)X(\text{\bf v},\omega)$ for
$\omega\in\Omega$, we see that

$\|\phi_{\omega}\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}^{2}=\iint_{\mathcal{Q}\times\mathcal{Q}}X^{2}(\text{\bf
u},\omega)X^{2}(\text{\bf v},\omega)\,\mathrm{d}\text{\bf
u}\,\mathrm{d}\text{\bf
v}=\|\mathcal{X}(\omega)\|^{4}\leq\beta^{2}~{}~{}\text{almost surely}.$

Also, $c(\text{\bf u},\text{\bf v})=\int_{\Omega}\phi_{\omega}(\text{\bf
u},\text{\bf v})\,\mathrm{d}\mathbb{P}(\omega)$. So, using Lemma 1, for every
$I\in\mathbb{N}$, we can find $\omega_{1},\ldots,\omega_{I}\in\Omega$ and non-
negative constants $\gamma_{1},\ldots,\gamma_{I}$ such that, defining
$c_{I}(\text{\bf u},\text{\bf
v})=\sum_{i=1}^{I}\gamma_{i}\,\phi_{\omega_{i}}(\text{\bf u},\text{\bf v})$,
we get

${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\mathcal{C}_{I}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}=\|c-c_{I}\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}^{2}=\iint_{\mathcal{Q}\times\mathcal{Q}}\\{c(\text{\bf
u},\text{\bf v})-c_{I}(\text{\bf u},\text{\bf v})\\}^{2}\,\mathrm{d}\text{\bf
u}\,\mathrm{d}\text{\bf v}\leq\frac{\beta^{2}}{I}=\mathcal{O}(I^{-1}),$ (B.7)

where $\mathcal{C}_{I}$ is the integral operator associated with the kernel
$c_{I}$. Observe that

$c_{I}(\text{\bf u},\text{\bf
v})=\sum_{i=1}^{I}\gamma_{i}\phi_{\omega_{i}}(\text{\bf u},\text{\bf
v})=\sum_{i=1}^{I}\gamma_{i}\,X_{i}(\text{\bf u})\,X_{i}(\text{\bf
v}),\quad\text{\bf u},\text{\bf v}\in\mathcal{Q},$

where the functions $\mathcal{X}_{i}:=\mathcal{X}(\omega_{i})$. Thus,
proceeding as in the previous section, we can obtain (a bound on) the rate of
convergence of the bias of the CovNet operator. The exact rate, in this case,
will depend on additional structural assumptions on the functions
$\mathcal{X}_{1},\ldots,\mathcal{X}_{I}$, or equivalently on $\mathcal{X}$.

We demonstrate this by deriving the rate for the restricted shallow CovNet
operator. Suppose that $\mathcal{X}$ takes values in
$\mathcal{S}^{\alpha}(\mathcal{Q})$, the _Sobolev space_ of order $\alpha$ in
$\mathcal{L}_{2}(\mathcal{Q})$. Further, let
$\|\mathcal{X}\|_{\mathcal{S}^{\alpha}(\mathcal{Q})}^{2}\leq\beta$ almost
surely (if $\alpha\geq 2$, this also implies that
$\|\mathcal{X}\|^{2}\leq\beta$ almost surely). Thus, for every $i=1,\ldots,I$,
$\mathcal{X}_{i}\in\mathcal{S}^{\alpha}(\mathcal{Q})$. By Theorem 2.1 in
Mhaskar (1996), for every $R\in\mathbb{N}$, we can find weights
$\mathbf{w}_{1},\ldots,\mathbf{w}_{R}$, bias $b$, and continuous functionals
$f_{1},\ldots,f_{R}$ on $\mathcal{S}^{\alpha}(\mathcal{Q})$ such that,
defining $\widehat{\mathcal{X}}_{i}(\text{\bf
u})=\sum_{r=1}^{R}f_{r}(\mathcal{X}_{i})\,\sigma(\mathbf{w}_{r}^{\top}\text{\bf
u}+b)$, we get

$\|\mathcal{X}_{i}-\widehat{\mathcal{X}}_{i}\|\lesssim
R^{-\alpha/d}\|\mathcal{X}_{i}\|_{\mathcal{S}^{\alpha}(\mathcal{Q})}\lesssim
R^{-\alpha/d}.$

Since the functionals $f_{1},\ldots,f_{R}$ are continuous, there exist finite
constants $a_{1},\ldots,a_{R}$ such that

$|f_{r}(\mathcal{X}_{i})|\leq
a_{r}\|\mathcal{X}_{i}\|_{\mathcal{S}^{\alpha}(\mathcal{Q})}\leq
a_{r}\sqrt{\beta},\quad r=1,\ldots,R.$

Thus, by defining $\widetilde{c}_{I,R}(\text{\bf u},\text{\bf
v})=\sum_{i=1}^{I}\gamma_{i}\,\widehat{\mathcal{X}}_{i}(\text{\bf
u})\,\widehat{\mathcal{X}}_{i}(\text{\bf v})$, we get

$\displaystyle\big{\|}c_{I}-\widetilde{c}_{I,R}\big{\|}_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}$
$\displaystyle\leq\sum_{i=1}^{I}\gamma_{i}\Big{\|}\widehat{\mathcal{X}}_{i}\otimes\widehat{\mathcal{X}}_{i}-\mathcal{X}_{i}\otimes\mathcal{X}_{i}\Big{\|}_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}$
$\displaystyle\leq\sum_{i=1}^{I}\gamma_{i}\Big{\\{}\big{\|}\widehat{\mathcal{X}}_{i}-\mathcal{X}_{i}\big{\|}^{2}+2\big{\|}\mathcal{X}_{i}\big{\|}\big{\|}\widehat{\mathcal{X}}_{i}-\mathcal{X}_{i}\big{\|}\Big{\\}}~{}~{}~{}~{}\text{(using
\eqref{eq:product_difference_bound_L2})}$ $\displaystyle\lesssim
R^{-2\alpha/d}+R^{-\alpha/d}\asymp R^{-\alpha/d}.$ (B.8)

Here, we have used that $\sum_{i=1}^{I}\gamma_{i}=1$, and $\alpha\geq 1,R\geq
1$ implies
$R^{-2\alpha/d}={\scriptstyle\mathcal{O}}\big{(}R^{-\alpha/d}\big{)}$. Now,
combining (B.7) and (B.2.2), we get

$\displaystyle\big{\|}c-\widetilde{c}_{I,R}\big{\|}_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\leq\big{\|}c-c_{I}\big{\|}_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}+\big{\|}c_{I}-\widetilde{c}_{I,R}\big{\|}_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\lesssim
I^{-1/2}+R^{-\alpha/d}.$

By choosing $I\asymp R^{2\alpha/d}$, we get that

$\big{\|}c-\widetilde{c}_{I,R}\big{\|}_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\lesssim
R^{-\alpha/d}.$ (B.9)

Now, observe that

$\displaystyle\widetilde{c}_{I,R}(\text{\bf u},\text{\bf v})$
$\displaystyle=\sum_{i=1}^{I}\gamma_{i}\,\widehat{\mathcal{X}}_{i}(\text{\bf
u})\,\widehat{\mathcal{X}}_{i}(\text{\bf v})$
$\displaystyle=\sum_{i=1}^{I}\gamma_{i}\sum_{r=1}^{R}\sum_{s=1}^{R}\beta_{i,r}\,\beta_{i,s}\,\sigma(\mathbf{w}_{r}^{\top}\text{\bf
u}+b)\,\sigma(\mathbf{w}_{s}^{\top}\text{\bf v}+b)~{}~{}(\text{where
}\beta_{i,r}=f_{r}(\mathcal{X}_{i}))$
$\displaystyle=\sum_{r=1}^{R}\sum_{s=1}^{R}\Bigg{(}\sum_{i=1}^{I}\gamma_{i}\,\beta_{i,r}\,\beta_{i,s}\Bigg{)}\sigma(\mathbf{w}_{r}^{\top}\text{\bf
u}+b)\,\sigma(\mathbf{w}_{s}^{\top}\text{\bf v}+b)$
$\displaystyle=\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,\sigma(\mathbf{w}_{r}^{\top}\text{\bf
u}+b)\,\sigma(\mathbf{w}_{s}^{\top}\text{\bf v}+b).$ (B.10)

Thus, $\widetilde{c}_{I,R}$ is a shallow CovNet kernel. Since $\gamma_{i}\geq
0$ for each $i$, the matrix $\Lambda=(\lambda_{r,s})$ is positive semi-
definite. Also, $\Lambda\preceq\lambda_{R}{\rm I}_{R}$, where
$\lambda_{R}=\beta\sum_{r=1}^{R}a_{r}^{2}$. This follows from the following
facts.

  1. (i)

For a matrix
$A=\mbox{\boldmath$\beta$}\mbox{\boldmath$\beta$}^{\top}\in\mathbb{R}^{R\times
R}$, $\text{\bf x}^{\top}A\text{\bf
x}=(\mbox{\boldmath$\beta$}^{\top}\text{\bf
x})^{2}\leq\|\mbox{\boldmath$\beta$}\|^{2}\|\text{\bf x}\|^{2}$ for every x,
implying that $A\preceq\|\mbox{\boldmath$\beta$}\|^{2}{\rm I}_{R}$.

  2. (ii)

For a collection of matrices $(A_{i})_{i=1}^{I}$ and $(B_{i})_{i=1}^{I}$
satisfying $0\preceq A_{i}\preceq B_{i}$, and non-negative scalars
$\gamma_{1},\ldots,\gamma_{I}$,
$\sum_{i=1}^{I}\gamma_{i}A_{i}\preceq\sum_{i=1}^{I}\gamma_{i}B_{i}$.

  3. (iii)

By (i) and (ii), for non-negative scalars $\gamma_{1},\ldots,\gamma_{I}$ and
vectors
$\mbox{\boldmath$\beta$}_{1},\ldots,\mbox{\boldmath$\beta$}_{I}\in\mathbb{R}^{R}$,
$\sum_{i=1}^{I}\gamma_{i}\mbox{\boldmath$\beta$}_{i}\mbox{\boldmath$\beta$}_{i}^{\top}\preceq\big{(}\sum_{i=1}^{I}\gamma_{i}\|\mbox{\boldmath$\beta$}_{i}\|^{2}\big{)}\,{\rm
I}_{R}$.

  4. (iv)

$\Lambda=\sum_{i=1}^{I}\gamma_{i}\mbox{\boldmath$\beta$}_{i}\mbox{\boldmath$\beta$}_{i}^{\top}$,
where $\mbox{\boldmath$\beta$}_{i}=(\beta_{i,1},\ldots,\beta_{i,R})^{\top}$.
For each $i=1,\ldots,I$,
$\|\mbox{\boldmath$\beta$}_{i}\|^{2}=\sum_{i=1}^{R}\beta_{i,r}^{2}=\sum_{i=1}^{R}f_{r}^{2}(\mathcal{X}_{i})\leq\beta\sum_{r=1}^{R}a_{r}^{2}$.
Also, $\sum_{i=1}^{I}\gamma_{i}=1$ implies that
$\sum_{i=1}^{I}\gamma_{i}\|\mbox{\boldmath$\beta$}_{i}\|^{2}\leq\beta\sum_{r=1}^{R}a_{r}^{2}$.

Using this along with (B.9) and (B.2.2), it follows that if we choose
$\lambda_{N}=\beta\sum_{r=1}^{R}a_{r}^{2}$, then

$\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{R,\lambda_{N}}}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}-\mathcal{G}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\lesssim
R^{-\alpha/d}.$ (B.11)

##  Appendix C Further details on the implementation of the CovNet models

In this section, we present further details on the implementation of the
CovNet models. We start by proving Proposition 1, which justifies the use of
the alternative formulation for estimating the CovNet models.

###### Proof of Proposition 1.

By construction, it is clear that $\widetilde{\mathscr{F}}^{\rm
NN}_{R,N}\subseteq\widetilde{\mathscr{F}}_{R}$ for every $N\geq 1$. So, we
will only show that for $N>R$, the other inclusion holds, i.e.,
$\widetilde{\mathscr{F}}_{R}\subseteq\widetilde{\mathscr{F}}_{R,N}^{\rm NN}$.
This amounts to showing that for every positive semi-definite matrix
$\Lambda=(\lambda_{r,s})\in\mathbb{R}^{R\times R}$, we can find $\xi_{n,r}$
for $n=1,\ldots,N$, $r=1,\ldots,R$, such that
$\lambda_{r,s}=N^{-1}\sum_{n=1}^{N}(\xi_{n,r}-\bar{\xi}_{r})(\xi_{n,s}-\bar{\xi}_{s})$.

For $N>R$, we can always find $N$ vectors
$\bm{\zeta}_{1},\ldots,\bm{\zeta}_{N}\in\mathbb{R}^{R}$ such that the rank of
the empirical covariance based of these vectors is $R$. For instance, one can
take $\bm{\zeta}_{i}=\mathbf{e}_{i}$, the $i$-th canonical vector in
$\mathbb{R}^{R}$ for $i=1,\ldots,R$, $\bm{\zeta}_{R+1}=-\textrm{{1}}$, and
$\bm{\zeta}_{i}=\mathbf{0}$ for $i=R+2,\ldots,N$, to check that the
corresponding empirical covariance matrix is of the form
$N^{-1}(\mathrm{I}_{R}+\textrm{{1}}\textrm{{1}}^{\top})$, which is of rank
$R$. Let us denote this empirical covariance by $\widehat{\Sigma}_{N}$. Thus,
$\widehat{\Sigma}_{N}$ is of full rank, and hence positive definite. So, we
can find a positive definite matrix $\widehat{\Sigma}_{N}^{-1/2}$, so that
$\widehat{\Sigma}_{N}^{-1/2}\widehat{\Sigma}_{N}\widehat{\Sigma}_{N}^{-1/2}=\mathrm{I}_{R}$.
Again, since $\Lambda=(\Lambda_{r,s})$ is positive semi-definite, we can find
a positive semi-definite matrix $\Lambda^{1/2}$ such that
$\Lambda^{1/2}\Lambda^{1/2}=\Lambda$. Define,
$\bm{\xi}_{n}=\Lambda^{1/2}\widehat{\Sigma}_{N}^{-1/2}\bm{\zeta}_{n}$ for
$n=1,\ldots,N$. Then, it is easy to verify that the empirical covariance of
$\bm{\xi}_{1},\ldots,\bm{\xi}_{N}$ is $\Lambda$. Now, let $\xi_{n,r}$ be the
$r$-th component of $\bm{\xi}_{n}$. For $n=1,\ldots,N$, define
$\mathcal{X}^{\rm NN}_{n}(\text{\bf
u})=\sum_{r=1}^{R}\xi_{n,r}\,g_{r}(\text{\bf u})$. It can be easily verified
that the empirical covariance of $\mathcal{X}_{1}^{\rm
NN},\ldots,\mathcal{X}_{N}^{\rm NN}$ is the operator with kernel
$\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,g_{r}(\text{\bf
u})\,g_{s}(\text{\bf v})$. This establishes the other inclusion. ∎

Next, we give a detailed derivation of the equivalence between the original
loss functions, and the loss functions expressed in terms of the observations
$\mathcal{X}_{1},\ldots,\mathcal{X}_{N}$ and the fitted networks
$\mathcal{X}_{1}^{\rm NN},\ldots,\mathcal{X}_{N}^{\rm NN}$.

###  C.1 Detailed derivation of the loss function

Let $\mathcal{X}_{1},\ldots,\mathcal{X}_{N}$ be the observed fields and
$\mathcal{X}_{1}^{\rm NN},\ldots,\mathcal{X}_{N}^{\rm NN}$ be the fitted
networks:

$\mathcal{X}_{n}^{\rm NN}(\text{\bf
u})=\sum_{r=1}^{R}\xi_{n,r}\,g_{r}(\text{\bf u}),\qquad n=1,\ldots,N.$

To begin with, we assume that all the fields are centered, so that
$\sum_{n=1}^{N}\mathcal{X}_{n}=0=\sum_{n=1}^{N}\mathcal{X}_{n}^{\rm NN}$. The
loss function is defined as

$\displaystyle\ell:=\ell(\Theta)={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widehat{\mathcal{C}}_{N}-\frac{1}{N}\sum_{n=1}^{N}\mathcal{X}_{n}^{\rm
NN}\otimes\mathcal{X}_{n}^{\rm
NN}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2},$

where $\Theta$ denotes all the _learnable parameters_ of the model. Now,
$\ell$ can be written as

$\displaystyle\ell$
$\displaystyle={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widehat{\mathcal{C}}_{N}-\frac{1}{N}\sum_{n=1}^{N}\mathcal{X}_{n}^{\rm
NN}\otimes\mathcal{X}_{n}^{\rm
NN}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\frac{1}{N}\sum_{n=1}^{N}(\mathcal{X}_{n}\otimes\mathcal{X}_{n}-\mathcal{X}_{n}^{\rm
NN}\otimes\mathcal{X}_{n}^{\rm
NN})\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}$
$\displaystyle=\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{X}_{n}\otimes\mathcal{X}_{n}-\mathcal{X}_{n}^{\rm
NN}\otimes\mathcal{X}_{n}^{\rm
NN},\mathcal{X}_{m}\otimes\mathcal{X}_{m}-\mathcal{X}_{m}^{\rm
NN}\otimes\mathcal{X}_{m}^{\rm
NN}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2},$
(C.1)

where
${\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\cdot,\cdot\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}$
is the Hilbert-Schmidt inner-product. Now, the inner product in the last step
equals

$\displaystyle{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{X}_{n}\otimes\mathcal{X}_{n},\mathcal{X}_{m}\otimes\mathcal{X}_{m}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}+{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{X}_{n}^{\rm
NN}\otimes\mathcal{X}_{n}^{\rm NN},\mathcal{X}_{m}^{\rm
NN}\otimes\mathcal{X}_{m}^{\rm
NN}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}$
$\displaystyle\kern
172.22168pt-{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{X}_{n}\otimes\mathcal{X}_{n},\mathcal{X}_{m}^{\rm
NN}\otimes\mathcal{X}_{m}^{\rm
NN}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}-{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{X}_{n}^{\rm
NN}\otimes\mathcal{X}_{n}^{\rm
NN},\mathcal{X}_{m}\otimes\mathcal{X}_{m}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}$
$\displaystyle=\langle\mathcal{X}_{n},\mathcal{X}_{m}\rangle^{2}+\langle\mathcal{X}_{n}^{\rm
NN},\mathcal{X}_{m}^{\rm
NN}\rangle^{2}-\langle\mathcal{X}_{n},\mathcal{X}_{m}^{\rm
NN}\rangle^{2}-\langle\mathcal{X}_{n}^{\rm NN},\mathcal{X}_{m}\rangle^{2}.$

Here, we have used that
${\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{X}_{1}\otimes\mathcal{X}_{2},\mathcal{Y}_{1}\otimes\mathcal{Y}_{2}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}=\langle\mathcal{X}_{1},\mathcal{Y}_{1}\rangle\,\langle\mathcal{X}_{2},\mathcal{Y}_{2}\rangle$.
Plugging this back into (C.1), we get that

$\ell=\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}\langle\mathcal{X}_{n},\mathcal{X}_{m}\rangle^{2}+\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}\langle\mathcal{X}_{n}^{\rm
NN},\mathcal{X}_{m}^{\rm
NN}\rangle^{2}-\frac{2}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}\langle\mathcal{X}_{n},\mathcal{X}_{m}^{\rm
NN}\rangle^{2}.$

Thus, the loss $\ell$ can be obtained from the inner products
$\langle\mathcal{X}_{n},\mathcal{X}_{m}\rangle$, $\langle\mathcal{X}_{n}^{\rm
NN},\mathcal{X}_{m}^{\rm NN}\rangle$ and
$\langle\mathcal{X}_{n},\mathcal{X}_{m}^{\rm NN}\rangle$, without forming the
high-order objects $\widehat{\mathcal{C}}_{N}$ or
$\mathcal{X}_{n}\otimes\mathcal{X}_{n}$. When the fields are not centered, one
can first center them by subtracting the mean and work with the centered
fields. Any mean estimation method can be used for this purpose. We can also
use a different approach, which allows us to simultaneously estimate the mean.

###  C.2 Simultaneous estimation of the mean

In the previous derivations, we assumed that the fields
$\mathcal{X}_{1},\ldots,\mathcal{X}_{N}$ as well as the fitted fields
$\mathcal{X}_{1}^{\rm NN},\ldots,\mathcal{X}_{N}^{\rm NN}$ are centered, i.e.,
$\bar{\mathcal{X}}_{N}=\bar{\mathcal{X}}_{N}^{\rm NN}=0$. When this is not the
case, the loss function can be written as

$\displaystyle\ell$
$\displaystyle={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\frac{1}{N}\sum_{n=1}^{N}\mathcal{X}_{n}\otimes\mathcal{X}_{n}-\bar{\mathcal{X}}_{N}\otimes\bar{\mathcal{X}}_{N}-\frac{1}{N}\sum_{n=1}^{N}\mathcal{X}_{n}^{\rm
NN}\otimes\mathcal{X}_{n}^{\rm NN}+\bar{\mathcal{X}}_{N}^{\rm
NN}\otimes\bar{\mathcal{X}}_{N}^{\rm
NN}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}$
$\displaystyle\leq
2\,\Bigg{\\{}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\frac{1}{N}\sum_{n=1}^{N}\mathcal{X}_{n}\otimes\mathcal{X}_{n}-\frac{1}{N}\sum_{n=1}^{N}\mathcal{X}_{n}^{\rm
NN}\otimes\mathcal{X}_{n}^{\rm
NN}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}+{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bar{\mathcal{X}}_{N}\otimes\bar{\mathcal{X}}_{N}-\bar{\mathcal{X}}_{N}^{\rm
NN}\otimes\bar{\mathcal{X}}_{N}^{\rm
NN}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}\Bigg{\\}}$
$\displaystyle=2\,\big{\\{}\widetilde{\ell}+{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bar{\mathcal{X}}_{N}\otimes\bar{\mathcal{X}}_{N}-\bar{\mathcal{X}}_{N}^{\rm
NN}\otimes\bar{\mathcal{X}}_{N}^{\rm
NN}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}\big{\\}},$

where $\widetilde{\ell}$ is the loss function without centering. In this case,
instead of minimizing the loss functions $\ell$, one can minimize

$\widetilde{\ell}+{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bar{\mathcal{X}}_{N}\otimes\bar{\mathcal{X}}_{N}-\bar{\mathcal{X}}^{\rm
NN}_{N}\otimes\bar{\mathcal{X}}^{\rm
NN}_{N}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}.$ (C.2)

Of course, this is an upper bound to the actual criterion. But, in practice,
this gives a reasonable approximation and produces reasonable results. As
already demonstrated, $\widetilde{\ell}$ can be computed efficiently, without
forming the high-order objects. Using similar techniques, it can be shown that

$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bar{\mathcal{X}}_{N}\otimes\bar{\mathcal{X}}_{N}-\bar{\mathcal{X}}_{N}^{\rm
NN}\otimes\bar{\mathcal{X}}_{N}^{\rm
NN}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}$
$\displaystyle=\bigg{(}\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}\langle\mathcal{X}_{n},\mathcal{X}_{m}\rangle\bigg{)}^{2}+\bigg{(}\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}\langle\mathcal{X}_{n}^{\rm
NN},\mathcal{X}_{m}^{\rm NN}\rangle\bigg{)}^{2}$ $\displaystyle\kern
172.22168pt-2\bigg{(}\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}\langle\mathcal{X}_{n},\mathcal{X}_{m}^{\rm
NN}\rangle\bigg{)}^{2},$

which again depends on the inner products, thus allowing for efficient
computation of the criterion (C.2). Moreover, as a by-product, we get an
estimate of the mean as follows. As before, we minimize the criterion w.r.t.
the parameters of $g_{1},\ldots,g_{R}$, and the new parameters $\xi_{n,r}$, to
get estimated fields

$\mathcal{X}^{\rm NN}_{n}(\text{\bf
u})=\sum_{r=1}^{R}\hat{\xi}_{n,r}\,\widehat{g}_{r}(\text{\bf u}),\qquad
n=1,\ldots,N.$

The mean field is then obtained as the empirical mean based on the fitted
fields, i.e.,

$\widehat{m}(\text{\bf
u})=\sum_{r=1}^{R}\bar{\hat{\xi}}_{r}\,\widehat{g}_{r}(\text{\bf
u}),\qquad\text{\bf u}\in\mathcal{Q},$

where $\bar{\hat{\xi}}_{r}=N^{-1}\sum_{n=1}^{N}\hat{\xi}_{n,r}$. Thus, once we
estimate the parameters of the model, we can get an estimate of the mean with
negligible computational overhead.

(a) Ex 1 with $I=5$
---
(b) Ex 1 with $I=10$
(c) Ex 1 with $I=20$
Figure 11: Estimated mean surfaces by different CovNet models in the Fourier
basis example with different choices of $I$. The empirical mean surfaces are
also shown. The relative estimation errors (in %) are shown at the bottom of
every figure. The plots are heatmaps of the 2D mean surfaces.

We demonstrate the usefulness of this method by means of a simulation study.
We generated $500$ observations from the Gaussian process on $[0,1]^{2}$ with
mean surface $m$ and covariance kernel $c$ on a regular grid of resolution
$25\times 25$. We took $c$ to be the Matérn covariance kernel (Ex 5 in Section
5) with $\nu=0.01$. For the mean function, we considered two different setups:

  1. Ex 1

_Fourier basis_ :
$m(s,t)=1+\sum_{i=1}^{I}(-1)^{i}i^{-2}\phi_{i}(s)\,\phi_{i}(t)$, where
$\phi_{i}(t)=\sqrt{2}\cos(i\pi t)$ for $i\geq 1$.

  2. Ex 2

_Legendre basis_ :
$m(s,t)=1+\sum_{i=1}^{I}(-1)^{i}(2i+1)\phi_{i}(s-0.5)\,\phi_{i}(t-0.5)$, where
$\phi_{i}$ is the Legendre polynomial of degree $i$.

In both the cases, the number of components $I$ controls the complexity of the
mean. The estimated mean surfaces using different CovNet models, along with
the true mean and the empirical mean, for different choices of $I$ are shown
in Figures 11 and 12. For the CovNet models, we used cross-validation to
select the hyperparameters. We also calculated the estimation error
$\|m-\widehat{m}\|/\|m\|$ for all the estimators using Monte-Carlo
integration, which are shown in the figures. These results clearly exhibit the
usefulness of the proposed mean estimation technique. The estimated mean
surfaces using the shallow and the deepshared models are very close to the
truth. The advantage of having a purely functional form over the discretized
empirical estimator is also visible in the figures and is reflected in the
estimation errors. The results for the deep CovNet model are, however, not
very promising. The deep CovNet model is not able to capture the truth at all.
This is perhaps due to the complexity of the deep model, which suggests the
need to regularize the deep CovNet model. Further evidence on the need for
regularization is furnished by the deepshared model, which has the best
performance in all the scenarios. In particular, the deepshared model is able
to capture minute details which the shallow model has missed (see Figures
11(b), 11(c), 12(c)).

One can notice that in (C.2), the criterion is composed of two components, one
accounting for the covariance, while the other accounting for the mean.
Instead of simply adding these two components, one may consider a weighted
average of the two, depending on their importance. However, we will not pursue
this idea further in this article.

(a) Ex 2 with $I=5$
---
(b) Ex 2 with $I=10$
(c) Ex 2 with $I=20$
Figure 12: Estimated mean surfaces by different CovNet models in the Legendre
basis example with different choices of $I$. The empirical mean surfaces are
also shown. The relative estimation errors (in %) are shown at the bottom of
every figure. The plots are heatmaps of the 2D mean surfaces.

###  C.3 Computing cost

We end this section with details on implementing the method for measurements
on a grid and related computing costs. Recall the generic version of a CovNet
kernel (3.1)

$\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,g_{r}(\text{\bf
u})\,g_{s}(\text{\bf v}),\qquad\text{\bf u},\text{\bf v}\in\mathcal{Q}.$

During fitting the CovNet model, using the alternate formulation (3.2)–(3.3),
we need to form the $N\times D$ matrix $\mathbf{X}^{\rm
NN}=(\mathcal{X}_{n}^{\rm NN}(\text{\bf u}_{i}))_{n,i}$, where $\text{\bf
u}_{1},\ldots,\text{\bf u}_{D}$ are the grid points (see the discussion after
Remark 5). This can be done as follows:

$\displaystyle\underbrace{\mathrm{U}}_{D\times
d}\mapsto\underbrace{\mathrm{Z}}_{D\times
R}=[\underbrace{g_{1}(\mathrm{U})}_{D\times
1},\ldots,\underbrace{g_{R}(\mathrm{U})}_{D\times 1}],\quad\mathbf{X}^{\rm
NN}=\Xi\,\mathrm{Z}^{\top},$

where $\mathrm{U}=(\text{\bf u}_{1}^{\top},\ldots,\text{\bf
u}_{D}^{\top})^{\top}$ is the matrix with $\text{\bf u}_{i}$ in its $i$-th
row, $g_{r}(\mathrm{U})=(g_{r}(\text{\bf u}_{1}),\ldots,g_{r}(\text{\bf
u}_{D}))^{\top}$, i.e., $g_{r}$ is applied row-wise for a matrix, and
$\Xi=(\xi_{n,r})$ is the matrix of coefficients. Also, to compute the
eigendecomposition of the fitted CovNet, we need to find the matrix
$\widetilde{\mathrm{G}}=(\widetilde{g}(r,s))$ with
$\widetilde{g}(r,s)=\int_{\mathcal{Q}}g_{r}(\text{\bf u})\,g_{s}(\text{\bf
u})\,\mathrm{d}\text{\bf u}$. As shown in Section 4, we approximate

$\displaystyle\widetilde{\mathrm{G}}\simeq\bigg{(}\frac{1}{M}\sum_{j=1}^{M}g_{r}(\text{\bf
u}_{j})\,g_{s}(\text{\bf u}_{j})\bigg{)}_{r,s},$

where $\text{\bf u}_{1},\ldots,\text{\bf u}_{M}$ are i.i.d. uniformly
distributed over $\mathcal{Q}$. Now, with the conventions above, the
approximation to $\widetilde{\mathrm{G}}$ can be obtained as:

$\displaystyle\underbrace{\mathrm{U}}_{M\times
d}\mapsto\mathrm{Z}=\underbrace{[g_{1}(\mathrm{U}),\ldots,g_{R}(\mathrm{U})]}_{M\times
R},\quad\widetilde{\mathrm{G}}=M^{-1}\mathrm{Z}^{\top}\mathrm{Z},$

where $\mathrm{U}=(\text{\bf u}_{1}^{\top},\ldots,\text{\bf
u}_{M}^{\top})^{\top}$ and $g_{r}(\mathrm{U})=(g_{r}(\text{\bf
u}_{1}),\ldots,g_{r}(\text{\bf u}_{M}))^{\top}$. Thus, in all practical
implementations, the computational cost depends crucially on the cost
associated with the evaluation
$\mathrm{U}\mapsto[g_{1}(\mathrm{U}),\ldots,g_{R}(\mathrm{U})]$ for a matrix
$\mathrm{U}$.

Recall that, for the shallow CovNet model, $g_{r}(\text{\bf
u})=\sigma(\mathbf{w}_{r}^{\top}\text{\bf u}+b_{r})$ for $r=1,\ldots,R$.
Writing
$\mathrm{W}=(\mathbf{w}_{1}^{\top},\ldots,\mathbf{w}_{R}^{\top})^{\top}$ and
$\mathbf{b}=(b_{1},\ldots,b_{R})^{\top}$, it is easy to see that

$\displaystyle\mathrm{U}\mapsto\mathrm{Z}=[g_{1}(\mathrm{U}),\ldots,g_{R}(\mathrm{U})]\quad\Leftrightarrow\quad\mathrm{Z}=\sigma(\mathrm{U}\,\mathrm{W}^{\top}+\mathbf{b}^{\top}),$

where the activation $\sigma$ is applied component-wise. This amounts to a
computing cost of $\mathcal{O}(DRd)$.

For the deep CovNet model, $g_{r}$ is defined recursively as in (2.2) (the
parameters depend on $r$). In this case, $g_{r}(\mathrm{U})$ can be obtained
from $\mathrm{U}$ recursively as

$\displaystyle\mathrm{U}_{1}$
$\displaystyle=\sigma(\mathrm{U}\,\mathrm{W}_{1,r}^{\top}+\mathbf{b}_{1,r}^{\top}),$
$\displaystyle\mathrm{U}_{l+1}$
$\displaystyle=\sigma(\mathrm{U}_{l}\,\mathrm{W}_{l+1,r}^{\top}+\mathbf{b}_{l+1,r}^{\top}),\quad
l=1,\ldots,L-1,$ $\displaystyle g_{r}(\mathrm{U})$
$\displaystyle=\sigma(\mathrm{U}_{L}\mathbf{w}_{L+1,r}+b_{L+1,r}),$

where $\mathrm{W}_{1,r}\in\mathbb{R}^{p_{1}\times d}$,
$\mathrm{W}_{2,r}\in\mathbb{R}^{p_{2}\times
p_{1}},\ldots,\mathrm{W}_{L,r}\in\mathbb{R}^{p_{L}\times p_{L-1}}$,
$\mathbf{b}_{1,r}\in\mathbb{R}^{p_{1}},\ldots,\mathbf{b}_{L,r}\in\mathbb{R}^{p_{L}},\mathbf{w}_{L+1,r}\in\mathbb{R}^{p_{L}}$,
$b_{L+1,r}\in\mathbb{R}$ are the parameters associated with $g_{r}$. Thus, the
computing cost for the evaluation $\mathrm{U}\mapsto g_{r}(\mathrm{U})$ is
$\mathcal{O}\big{(}D\sum_{l=0}^{L}p_{l}p_{l+1}\big{)}$, where $p_{0}=d$ and
$p_{L+1}=1$. However, this needs to be done for $r=1,\ldots,R$. Thus, the
total cost for computing
$\mathrm{U}\mapsto[g_{1}(\mathrm{U}),\ldots,g_{R}(\mathrm{U})]$ for the deep
CovNet model is $\mathcal{O}\big{(}DR\sum_{l=0}^{L}p_{l}p_{l+1}\big{)}$.

Finally, consider the deepshared CovNet model, where $g_{1},\ldots,g_{R}$ are
defined recursively as in (2.2). In this case
$\mathrm{Z}=[g_{1}(\mathrm{U}),\ldots,g_{R}(\mathrm{U})]$ can be computed
recursively as follows:

$\displaystyle\mathrm{U}_{1}$
$\displaystyle=\sigma(\mathrm{U}\,\mathrm{W}_{1}^{\top}+\mathbf{b}_{1}^{\top}),$
$\displaystyle\mathrm{U}_{l+1}$
$\displaystyle=\sigma(\mathrm{U}_{l}\,\mathrm{W}_{l+1}^{\top}+\mathbf{b}_{l+1}^{\top}),\quad
l=1,\ldots,L-1,$ $\displaystyle\mathrm{Z}$
$\displaystyle=\sigma(\mathrm{U}_{L}\,\mathrm{W}^{\top}+\mathbf{b}^{\top}),$

where $\mathrm{W}_{1}\in\mathbb{R}^{p_{1}\times
d},\mathrm{W}_{2}\in\mathbb{R}^{p_{2}\times
p_{1}},\ldots,\mathrm{W}_{L}\in\mathbb{R}^{p_{L}\times p_{L-1}}$,
$\mathbf{b}_{1}\in\mathbb{R}^{p_{1}},\ldots,\mathbf{b}_{L}\in\mathbb{R}^{p_{L}}$,
$\mathrm{W}=(\bm{\omega}_{1}^{\top},\ldots,\bm{\omega}_{R}^{\top})^{\top}\in\mathbb{R}^{R\times
p_{L}}$, and $\mathbf{b}=(\beta_{1},\ldots,\beta_{R})^{\top}\in\mathbb{R}^{R}$
are the parameters associated with $g_{1},\ldots,g_{R}$. Thus, the cost for
the evaluation $\mathrm{U}\mapsto[g_{1}(\mathrm{U}),\ldots,g_{R}(\mathrm{U})]$
in this case is
$\mathcal{O}\big{(}D\big{(}\sum_{l=0}^{L-1}p_{l}p_{l+1}+Rp_{L}\big{)}\big{)}$,
where $p_{0}=d$.

After obtaining
$\mathrm{Z}=[g_{1}(\mathrm{U}),\ldots,g_{R}(\mathrm{U})]\in\mathbb{R}^{D\times
R}$, we require an additional $\mathcal{O}(NDR)$ computations to get
$\mathbf{X}^{\rm NN}=\Xi\,\mathrm{Z}^{\top}$. Similarly, for
$\widetilde{\mathrm{G}}=M^{-1}\mathrm{Z}^{\top}\mathrm{Z}$, an additional
$\mathcal{O}(MR^{2})$ computations are required after obtaining
$\mathrm{Z}\in\mathbb{R}^{M\times R}$ (in this case, all the previous
complexities should be understood with $D=M$). We summarize these in Table 2
for the special case when $p_{1}=\cdots=p_{L}=R$ for the deep and the
deepshared CovNet models (as used in our numerical studies). Note that the
complexities are always linear in the grid size $D$ or $M$.

Table 2: Computational complexities associated with different tasks for
different CovNet models.
For the deep and the deepshared models, we consider the case when $p_{1}=\cdots=p_{L}=R$. |  |  |  | Method |  |
---|---|---|---|---|---|---
Complexity |  | Shallow CovNet |  | Deep CovNet |  | Deepshared CovNet
Evaluation |  | $\mathcal{O}\big{(}DRd\big{)}$ |  | $\mathcal{O}\big{(}DR^{2}(LR+d)\big{)}$ |  | $\mathcal{O}\big{(}DR(LR+d)\big{)}$
Obtaining $\mathbf{X}^{\rm NN}$ |  | $\mathcal{O}\big{(}DR(N+d)\big{)}$ |  | $\mathcal{O}\big{(}DR(LR^{2}+dR+N)\big{)}$ |  | $\mathcal{O}\big{(}DR(LR+d+N)\big{)}$
Approximating $\widetilde{\mathrm{G}}$ |  | $\mathcal{O}\big{(}MR(R+d)\big{)}$ |  | $\mathcal{O}\big{(}MR^{2}(LR+d)\big{)}$ |  | $\mathcal{O}\big{(}MR(LR+d)\big{)}$

##  Appendix D Covering numbers

In this section, we derive certain covering numbers that will be instrumental
in the proofs of our asymptotic results. We give a brief overview of covering
numbers and derive bounds on the covering numbers of some classes of functions
useful in our context. The main results of this section are Lemmas 5, 6 and 7,
which give upper bounds on the covering numbers for the restricted classes of
shallow, deep and deepshared CovNet operators, respectively. The reader can
skip this section and go to the next section without loss of continuation.

We start with the definition of covering numbers for general metric spaces.
More details can be found in Anthony and Bartlett (1999, Chapter 10), Györfi
et al. (2002, Chapter 9), Wainwright (2019, Chapter 5). Let $(S,\rho)$ be a
metric space, and let $T$ be a subset of $S$. For $\epsilon>0$, a finite
subset $T^{\prime}$ of $T$ is called an $\epsilon$-cover of $T$ w.r.t. the
metric $\rho$ if for every $t\in T$ we can find an $t^{\prime}\in T^{\prime}$
such that $\rho(t,t^{\prime})\leq\epsilon$. The $\epsilon$-covering number of
$T$ w.r.t. $\rho$ is the cardinality of the smallest $\epsilon$-cover of $T$.
We denote the covering number by $\mathcal{N}(\epsilon,T,\rho)$. If no finite
$\epsilon$-cover of $T$ exists, then the covering number is defined to be
$\infty$.

In our present context, we are interested in the covering numbers of the
restricted classes of CovNet operators (6.1) w.r.t. the Hilbert-Schmidt norm.
Because of the equivalence between an operator $\mathcal{G}$ and the
associated kernel $g$, we get
${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}=\|g\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}$.
This shows that if we define $\mathscr{F}$ to be a class of non-negative
definite kernels and $\widetilde{\mathscr{F}}$ to be the corresponding class
of integral operators, then

$\mathcal{N}(\epsilon,\widetilde{\mathscr{F}},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2})=\mathcal{N}(\epsilon,\mathscr{F},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}).$
(D.1)

Thus, it is enough to find an upper bound on the covering numbers of the
classes of CovNet kernels w.r.t. the
$\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})$ norm. We start by deriving a
general bounding result.

######  Theorem 7.

Let $G$ be a class of functions from $\mathcal{Q}$ to $\mathbb{R}$ with
$\|g\|\leq M$ for every $g\in G$. For a positive real number $\lambda_{N}$ and
an integer $R$, define the following class of functions from
$\mathcal{Q}\times\mathcal{Q}$ to $\mathbb{R}$:

$\mathscr{F}_{R,G,\lambda_{N}}=\Bigg{\\{}\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,g_{r}(\text{\bf
u})\,g_{s}(\text{\bf v}):g_{r}\in
G,0\preceq\Lambda=(\lambda_{r,s})\preceq\lambda_{N}\mathrm{I}_{R}\Bigg{\\}}.$

Then, the $\mathcal{L}_{2}$ covering number of $\mathscr{F}_{R,G,\lambda_{N}}$
is bounded as

$\mathcal{N}\left(\epsilon,\mathscr{F}_{R,G,\lambda_{N}},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\right)\leq\left[\frac{M^{2}R^{2}\lambda_{N}+\epsilon}{\epsilon}\times\left\\{\frac{2e(4M^{2}R^{2}\lambda_{N}+\epsilon)}{\epsilon}\times\mathcal{N}\left(\frac{\epsilon}{8MR^{2}\lambda_{N}},G,\|\cdot\|\right)\right\\}^{R}\right]^{R}.$

We first state and prove a few lemmas, which will be used in the proof of the
theorem.

######  Lemma 2.

Let $\mathcal{I}$ be a compact set and $\mathcal{H}$ be a collection of
functions from $\mathcal{I}$ to $\mathbb{R}$ such that
$\|h\|_{\mathcal{L}_{2}(\mathcal{I})}\leq M$ for all $h\in\mathcal{H}$. Define
$\mathcal{E}_{R,\mathcal{H},\gamma}=\big{\\{}\sum_{i=1}^{R}\alpha_{i}h_{i}:h_{i}\in\mathcal{H},0\leq\alpha_{i}\leq\gamma\big{\\}}$.
Then, for any $\epsilon_{1},\epsilon_{2}>0$,

$\mathcal{N}(\epsilon_{1}+\epsilon_{2},\mathcal{E}_{R,\mathcal{H},\gamma},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})})\leq\left\\{\left(\frac{MR\gamma}{2\epsilon_{2}}+1\right)\times\mathcal{N}\left(\frac{\epsilon_{1}}{R\gamma},\mathcal{H},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})}\right)\right\\}^{R}.$

###### Proof.

Without loss of generality, we assume that all the covering numbers defined
subsequently are finite. Fix $\epsilon_{1},\epsilon_{2}>0$ and let
$N_{1}=\mathcal{N}(\epsilon_{1},\mathcal{H},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})})$,
$N_{2}=\mathcal{N}(\epsilon_{2},[0,\gamma],|\cdot|)$. Thus, we can find a set
${\mathcal{H}}^{\prime}_{\epsilon_{1}}\subset\mathcal{H}$ of cardinality
$N_{1}$ and a set of real numbers $A^{\prime}_{\epsilon_{2}}\subset[0,\gamma]$
of cardinality $N_{2}$ such that for every $h\in\mathcal{H}$ and every
$\alpha\in[0,\gamma]$, there exists
$h^{\prime}\in{\mathcal{H}}^{\prime}_{\epsilon_{1}}$ and $\alpha^{\prime}\in
A^{\prime}_{\epsilon_{2}}$ such that
$\|h-h^{\prime}\|_{\mathcal{L}_{2}(\mathcal{I})}\leq\epsilon_{1}$ and
$|\alpha-\alpha^{\prime}|\leq\epsilon_{2}$. Now, let
$\sum_{i=1}^{R}\alpha_{i}h_{i}$ be an element of $\mathcal{E}_{R,\gamma}$. Let
$h_{1}^{\prime},\ldots,h_{R}^{\prime}\in{\mathcal{H}}^{\prime}_{\epsilon_{1}}$
and $\alpha_{1}^{\prime},\ldots,\alpha_{R}^{\prime}\in
A^{\prime}_{\epsilon_{2}}$ be such that
$\|h_{i}-h_{i}^{\prime}\|_{\mathcal{L}_{2}(\mathcal{I})}\leq\epsilon_{1}$ and
$|\alpha_{i}-\alpha_{i}^{\prime}|\leq\epsilon_{2}$ for $i=1,\ldots,R$. Now,

$\displaystyle\left\|\sum_{i=1}^{R}\alpha_{i}h_{i}-\sum_{i=1}^{R}\alpha_{i}^{\prime}h_{i}^{\prime}\right\|_{\mathcal{L}_{2}(\mathcal{I})}$
$\displaystyle=\left\|\sum_{i=1}^{R}(\alpha_{i}-\alpha_{i}^{\prime})h_{i}+\sum_{i=1}^{R}\alpha_{i}^{\prime}(h_{i}-h_{i}^{\prime})\right\|_{\mathcal{L}_{2}(\mathcal{I})}$
$\displaystyle\leq\sum_{i=1}^{R}\underbrace{|\alpha_{i}-\alpha_{i}^{\prime}|}_{\leq\epsilon_{2}}\,\underbrace{\|h_{i}\|_{\mathcal{L}_{2}(\mathcal{I})}}_{\leq
M}+\sum_{i=1}^{R}\underbrace{\alpha_{i}^{\prime}}_{\leq\gamma}\,\underbrace{\|h_{i}-h_{i}^{\prime}\|_{\mathcal{L}_{2}(\mathcal{I})}}_{\leq\epsilon_{1}}$
$\displaystyle=R(\gamma\epsilon_{1}+M\epsilon_{2}).$

This shows that
${\mathcal{E}}^{\prime}_{\epsilon_{1},\epsilon_{2}}:=\big{\\{}\sum_{i=1}^{R}\alpha_{i}^{\prime}h_{i}^{\prime}:\alpha_{i}^{\prime}\in
A_{\epsilon_{2}}^{\prime},h_{i}^{\prime}\in{\mathcal{H}}_{\epsilon_{1}}^{\prime}\big{\\}}$
is an $\mathcal{L}_{2}$-cover for $\mathcal{E}_{R,\gamma}$ of size
$R(\gamma\epsilon_{1}+M\epsilon_{2})$. Thus,

$\mathcal{N}\big{(}R(\gamma\epsilon_{1}+M\epsilon_{2}),\mathcal{E}_{R,\gamma},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})}\big{)}\leq|{\mathcal{E}}^{\prime}_{\epsilon_{1},\epsilon_{2}}|=(N_{1}N_{2})^{R}.$

Note that
$N_{2}=\mathcal{N}(\epsilon_{2},[0,\gamma],|\cdot|)\leq\gamma/(2\epsilon_{2})+1$
(Wainwright, 2019, Example 5.2), which shows that

$\mathcal{N}\big{(}R(\gamma\epsilon_{1}+M\epsilon_{2}),\mathcal{E}_{R,\gamma},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})}\big{)}\leq\left\\{\left(\frac{\gamma}{2\epsilon_{2}}+1\right)\times\mathcal{N}(\epsilon_{1},\mathcal{H},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})}\right\\}^{R}.$

The proof is complete after transforming
$\epsilon_{1}\mapsto\epsilon_{1}/(R\gamma)$ and
$\epsilon_{2}\mapsto\epsilon_{2}/(RM)$. ∎

As a corollary, taking $\epsilon_{1}=\epsilon_{2}=\epsilon/2$, we get the
following.

######  Corollary 1.

With $\mathcal{E}_{R,\mathcal{H},\gamma}$ defined as in Lemma 2, for any
$\epsilon>0$,

$\mathcal{N}(\epsilon,\mathcal{E}_{R,\mathcal{H},\gamma},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})})\leq\left\\{\left(\frac{MR\gamma}{\epsilon}+1\right)\times\mathcal{N}\left(\frac{\epsilon}{2R\gamma},\mathcal{H},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})}\right)\right\\}^{R}.$

We will also use a modified version of Lemma 16.6 in Györfi et al. (2002). The
proof follows straightforwardly from the proof in Györfi et al. (2002). We
give a brief sketch of the proof here for completeness.

######  Lemma 3.

Let $\mathcal{I}$ be a compact set and $\mathcal{H}$ be a class of functions
from $\mathcal{I}$ to $\mathbb{R}$ with
$\|h\|_{\mathcal{L}_{2}(\mathcal{I})}\leq M$ for all $h\in\mathcal{H}$. For a
positive real number $\gamma$ and an integer $R$, define the class of
functions

$\mathcal{E}_{R,\mathcal{H},\gamma}=\left\\{\sum_{i=1}^{R}\alpha_{i}\,h_{i}:h_{i}\in\mathcal{H},\sum_{i=1}^{R}|\alpha_{i}|\leq\gamma\right\\}.$

Then, for any $\epsilon_{1},\epsilon_{2}>0$, we have

$\mathcal{N}(\epsilon_{1}+\epsilon_{2},\mathcal{E}_{R,\mathcal{H},\gamma},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})})\leq\left\\{\frac{e(M\gamma+2\epsilon_{2})}{\epsilon_{2}}\times\mathcal{N}\left(\frac{\epsilon_{1}}{\gamma},\mathcal{H},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})}\right)\right\\}^{R}.$

###### Proof.

Assume without loss of generality that all the covering numbers defined
subsequently are finite. Let
$N=\mathcal{N}(\epsilon_{1},\mathcal{H},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})})$.
Then, we can find a subset
${\mathcal{H}}^{\prime}_{\epsilon_{1}}\subset\mathcal{H}$ of cardinality $N$
such that for every $h\in\mathcal{H}$, we can find
$h^{\prime}\in{\mathcal{H}}^{\prime}_{\epsilon_{1}}$ such that
$\|h-h^{\prime}\|_{\mathcal{L}_{2}(\mathcal{I})}\leq\epsilon_{1}$. Now, let
$S_{\gamma}=\\{(\alpha_{1},\ldots,\alpha_{R})\in\mathbb{R}^{R}:\sum_{i=1}^{R}|\alpha_{i}|\leq\gamma\\}$,
and $S_{\gamma,\epsilon_{2}}^{\prime}$ be a finite subset of $\mathbb{R}^{R}$
such that for every $(\alpha_{1},\ldots,\alpha_{R})\in S_{\gamma}$ we can find
$(\alpha_{1}^{\prime},\ldots,\alpha_{R}^{\prime})\in
S_{\gamma,\epsilon_{2}}^{\prime}$ with
$\sum_{i=1}^{R}|\alpha_{i}-\alpha_{i}^{\prime}|\leq\epsilon_{2}$. Define,
${\mathcal{E}}_{\epsilon_{1},\epsilon_{2}}^{\prime}:=\big{\\{}\sum_{i=1}^{R}\alpha_{i}\,h_{i}:(\alpha_{1},\ldots,\alpha_{R})\in
S_{\gamma,\epsilon_{2}}^{\prime},h_{i}\in{\mathcal{H}}^{\prime}_{\epsilon_{1}}\big{\\}}$.
Then, for
$\sum_{i=1}^{R}\alpha_{i}h_{i}\in\mathcal{E}_{R,\mathcal{H},\gamma}$, we can
find
$\sum_{i=1}^{R}\alpha_{i}^{\prime}h_{i}^{\prime}\in{\mathcal{E}}_{\epsilon_{1},\epsilon_{2}}^{\prime}$
such that

$\displaystyle\left\|\sum_{i=1}^{R}\alpha_{i}h_{i}-\sum_{i=1}^{R}\alpha_{i}^{\prime}h_{i}^{\prime}\right\|_{\mathcal{L}_{2}(\mathcal{I})}$
$\displaystyle=\left\|\sum_{i=1}^{R}\alpha_{i}(h_{i}-h_{i}^{\prime})+\sum_{i=1}^{R}(\alpha_{i}-\alpha_{i}^{\prime})h_{i}^{\prime}\right\|_{\mathcal{L}_{2}(\mathcal{I})}$
$\displaystyle\leq\underbrace{\sum_{i=1}^{R}|\alpha_{i}|}_{\leq\gamma}\,\underbrace{\left\|h_{i}-h_{i}^{\prime}\right\|_{\mathcal{L}_{2}(\mathcal{I})}}_{\leq\epsilon_{1}}+\underbrace{\sum_{i=1}^{R}|\alpha_{i}-\alpha_{i}^{\prime}|}_{\leq\epsilon_{2}}\,\underbrace{\|h_{i}^{\prime}\|_{\mathcal{L}_{2}(\mathcal{I})}}_{\leq
M}$ $\displaystyle\leq\gamma\epsilon_{1}+M\epsilon_{2}.$

This shows that ${\mathcal{E}}_{\epsilon_{1},\epsilon_{2}}^{\prime}$ is an
$\mathcal{L}_{2}$ cover for $\mathcal{E}_{R,\mathcal{H},\gamma}$ of size
$(\gamma\epsilon_{1}+M\epsilon_{2})$. Thus,

$\mathcal{N}(\gamma\epsilon_{1}+M\epsilon_{2},\mathcal{E}_{R,\mathcal{H},\gamma},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})})\leq
N^{R}\times|S_{\gamma,\epsilon_{2}}^{\prime}|.$

Now, as shown in the proof of Lemma 16.6 in Györfi et al. (2002),

$|S_{\gamma,\epsilon_{2}}^{\prime}|\leq\left(\frac{e(\gamma+2\epsilon_{2})}{\epsilon_{2}}\right)^{R},$

which shows that

$\mathcal{N}(\gamma\epsilon_{1}+M\epsilon_{2},\mathcal{E}_{R,\mathcal{H},\gamma},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})})\leq\left(\frac{e(\gamma+2\epsilon_{2})}{\epsilon_{2}}\right)^{R}\times\mathcal{N}\big{(}\epsilon_{1},\mathcal{H},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})}\big{)}^{R}.$

The proof is complete upon transforming
$\epsilon_{1}\mapsto\epsilon_{1}/\gamma$ and
$\epsilon_{2}\mapsto\epsilon_{2}/M$. ∎

With $\epsilon_{1}=\epsilon_{2}=\epsilon/2$, we get the following corollary.

######  Corollary 2.

With $\mathcal{E}_{R,\mathcal{H},\gamma}$ defined as in Lemma 3, for any
$\epsilon>0$

$\mathcal{N}(\epsilon,\mathcal{E}_{R,\mathcal{H},\gamma},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})})\leq\left\\{\frac{2e(M\gamma+\epsilon)}{\epsilon}\times\mathcal{N}\left(\frac{\epsilon}{2\gamma},\mathcal{H},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})}\right)\right\\}^{R}.$

We will also need the following result about the covering number of the space
of product functions.

######  Lemma 4.

Let $\mathcal{I}$ be a compact set and $\mathcal{H}$ be a collection of
functions from $\mathcal{I}$ to $\mathbb{R}$ such that
$\|h\|_{\mathcal{L}_{2}(\mathcal{I})}\leq M$ for every $h\in\mathcal{H}$.
Define $\mathcal{E}=\big{\\{}e:\mathcal{I}\times\mathcal{I}\to\mathbb{R}\text{
with }e(\text{\bf u},\text{\bf v})=h(\text{\bf u})\,h(\text{\bf v}),\text{
where }h\in\mathcal{H}\big{\\}}$. Then,

$\mathcal{N}\big{(}\epsilon,\mathcal{E},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I}\times\mathcal{I})}\big{)}\leq\mathcal{N}\left(\frac{\epsilon}{2M},\mathcal{H},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{I})}\right).$

###### Proof.

Let $e_{1}=h_{1}\otimes h_{1}$ and $e_{2}=h_{2}\otimes h_{2}$ be two functions
in $\mathcal{E}$. Then,

$\displaystyle\|e_{1}-e_{2}\|_{\mathcal{L}_{2}(\mathcal{I}\times\mathcal{I})}$
$\displaystyle=\|h_{1}\otimes h_{1}-h_{2}\otimes
h_{2}\|_{\mathcal{L}_{2}(\mathcal{I}\times\mathcal{I})}$
$\displaystyle=\|h_{1}\otimes(h_{1}-h_{2})+(h_{1}-h_{2})\otimes
h_{2}\|_{\mathcal{L}_{2}(\mathcal{I}\times\mathcal{I})}$
$\displaystyle\leq\|h_{1}-h_{2}\|_{\mathcal{L}_{2}(\mathcal{I})}\big{(}\|h_{1}\|_{\mathcal{L}_{2}(\mathcal{I})}+\|h_{2}\|_{\mathcal{L}_{2}(\mathcal{I})}\big{)}$
$\displaystyle\leq 2M\|h_{1}-h_{2}\|_{\mathcal{L}_{2}(\mathcal{I})}.$

This shows that an $\mathcal{L}_{2}$-cover for $\mathcal{H}$ of size
$\epsilon$ provides an $\mathcal{L}_{2}$-cover for $\mathcal{E}$ of size
$2M\epsilon$, proving the lemma. ∎

We now proceed to prove Theorem 7.

###### Proof of Theorem 7.

Since $\Lambda=(\lambda_{r,s})$ is positive semi-definite, we can find
orthonormal vectors $\mathbf{e}_{1},\ldots,\mathbf{e}_{R}\in\mathbb{R}^{R}$
and non-negative real numbers $\eta_{1},\ldots,\eta_{R}$ such that
$\Lambda=\sum_{i=1}^{R}\eta_{i}\,\mathbf{e}_{i}\,\mathbf{e}_{i}^{\top}$.
Moreover, since $\Lambda\preceq\lambda_{N}{\rm I}_{R}$, we also get that
$\eta_{i}\leq\lambda_{N}$ for $i=1,\ldots,R$. Using this, we can write

$\displaystyle\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,g_{r}(\text{\bf
u})\,g_{s}(\text{\bf v})$
$\displaystyle=\sum_{r=1}^{R}\sum_{s=1}^{R}\left(\sum_{i=1}^{R}\eta_{i}\,e_{i,r}\,e_{i,s}\right)g_{r}(\text{\bf
u})\,g_{s}(\text{\bf v})$
$\displaystyle=\sum_{i=1}^{R}\eta_{i}\left(\sum_{r=1}^{R}e_{i,r}\,g_{r}(\text{\bf
u})\right)\left(\sum_{s=1}^{R}e_{i,s}\,g_{s}(\text{\bf
v})\right)=\sum_{i=1}^{R}\eta_{i}\,\widetilde{g}_{i}(\text{\bf
u})\,\widetilde{g}_{i}(\text{\bf v}),$

where $e_{i,r}$ is the $r$-th coordinate of $\mathbf{e}_{i}$ and
$\widetilde{g}_{i}(\text{\bf u})=\sum_{r=1}^{R}e_{i,r}g_{r}(\text{\bf u})$.
Since $\mathbf{e}_{i}$’s are orthonormal, $\sum_{r=1}^{R}e_{ir}^{2}=1$ for
every $i=1,\ldots,R$. This shows that we can rewrite
$\mathscr{F}_{R,G,\lambda_{N}}$ as

$\mathscr{F}_{R,G,\lambda_{N}}=\left\\{\sum_{i=1}^{R}\eta_{i}\,f_{i}(\text{\bf
u})\,f_{i}(\text{\bf v}):f_{i}\in
G_{R}^{(0)},0\leq\eta_{i}\leq\lambda_{N}\right\\},$

where

$G_{R}^{(0)}=\left\\{\sum_{r=1}^{R}a_{r}\,g_{r}(\text{\bf u}):g_{r}\in
G,\sum_{r=1}^{R}a_{r}^{2}=1\right\\}.$

Now, for any $f\in G_{R}^{(0)}$,

$\|f\|=\left\|\sum_{r=1}^{R}a_{r}\,g_{r}\right\|\leq\sum_{r=1}^{R}|a_{r}|\,\underbrace{\|g_{r}\|}_{\leq
M}\leq M\sum_{r=1}^{R}|a_{r}|\leq\sqrt{R}M,$

where we have used that $\sum_{r=1}^{R}a_{r}^{2}=1$ implies
$\sum_{r=1}^{R}|a_{r}|\leq\sqrt{R}$ by the Cauchy-Schwarz inequality. So, for
$f\in G_{R}^{(0)}$, $\|f\otimes
f\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}=\|f\|^{2}\leq RM^{2}$.
Now, using Corollary 1,

$\mathcal{N}(\epsilon,\mathscr{F}_{R,G,\lambda_{N}},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})})\leq\left\\{\left(\frac{M^{2}R^{2}\lambda_{N}}{\epsilon}+1\right)\times\mathcal{N}\left(\frac{\epsilon}{2R\lambda_{N}},\big{\\{}f\otimes
f:f\in
G_{R}^{(0)}\big{\\}},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\right)\right\\}^{R}.$

Also, using Lemma 4, we get

$\mathcal{N}\left(\epsilon,\big{\\{}f\otimes f:f\in
G_{R}^{(0)}\big{\\}},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\right)\leq\mathcal{N}\left(\frac{\epsilon}{2\sqrt{R}M},G_{R}^{(0)},\|\cdot\|\right).$

Plugging this into the previous equation, we get

$\mathcal{N}(\epsilon,\mathscr{F}_{R,G,\lambda_{N}},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})})\leq\left\\{\left(\frac{M^{2}R^{2}\lambda_{N}}{\epsilon}+1\right)\times\mathcal{N}\left(\frac{\epsilon}{4MR^{3/2}\lambda_{N}},G_{R}^{(0)},\|\cdot\|\right)\right\\}^{R}.$
(D.2)

Now, $\sum_{r=1}^{R}a_{r}^{2}=1$ implies $\sum_{r=1}^{R}|a_{r}|\leq\sqrt{R}$,
and thus

$G_{R}^{(0)}=\left\\{\sum_{r=1}^{R}a_{r}g_{r}:g_{r}\in
G,\sum_{r=1}^{R}a_{r}^{2}=1\right\\}\subset\left\\{\sum_{r=1}^{R}a_{r}g_{r}:g_{r}\in
G,\sum_{r=1}^{R}|a_{r}|\leq\sqrt{R}\right\\}.$

Now, using Corollary 2, we bound the covering number of $G_{R}^{(0)}$ as

$\mathcal{N}(\epsilon,G_{R}^{(0)},\|\cdot\|)\leq\left\\{\frac{2e(M\sqrt{R}+\epsilon)}{\epsilon}\times\mathcal{N}\left(\frac{\epsilon}{2\sqrt{R}},G,\|\cdot\|\right)\right\\}^{R}.$

The proof follows by plugging this into (D.2). ∎

We will use Theorem 7 to derive upper bounds on the covering numbers of the
shallow and the deep CovNet kernel classes, respectively.

###  D.1 Covering number of the shallow CovNet class

Recall that the (restricted) shallow CovNet class of kernels is defined as

$\mathscr{F}_{R,\lambda_{N}}^{\rm
sh}=\left\\{\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,\sigma(\mathbf{w}_{r}^{\top}\text{\bf
u}+b_{r})\,\sigma(\mathbf{w}_{s}^{\top}\text{\bf
v}+b_{s}):\mathbf{w}_{r}\in\mathbb{R}^{d},b_{r}\in\mathbb{R},0\preceq\Lambda=(\lambda_{r,s})\preceq\lambda_{N}\mathrm{I}_{R}\right\\},$

which has the form $\mathscr{F}_{R,G,\lambda_{N}}$, where
$G=\big{\\{}\sigma(\mathbf{w}^{\top}\text{\bf
u}+b):\mathbf{w}\in\mathbb{R}^{d},b\in\mathbb{R}\big{\\}}$. Since the
activation function $\sigma$ is sigmoidal, in particular $0\leq\sigma(t)\leq
1$ for all $t\in\mathbb{R}$, $\|g\|\leq\sqrt{|\mathcal{Q}|}$ for all $g\in G$.
Again, since $\sigma$ is non-decreasing, the VC dimension of $G$ is bounded by
$d+2$ (see Györfi et al., 2002, page 314). Since $\mathcal{Q}$ is a compact
set, the measure $\nu$ defined as $\nu(A):=|\mathcal{Q}\cap A|/|\mathcal{Q}|$
for $A\subset\mathbb{R}^{d}$, is a probability measure on $\mathbb{R}^{d}$.
So, using Theorem 9.4 in Györfi et al. (2002), we get that

$\mathcal{N}\big{(}\epsilon,G,\|\cdot\|_{\mathcal{L}_{2}(\nu)}\big{)}\leq
3\bigg{(}\frac{2e}{\epsilon^{2}}\log\frac{3e}{\epsilon^{2}}\bigg{)}^{d+2}.$

Now, $\|f\|=\sqrt{|\mathcal{Q}|}\,\|f\|_{\mathcal{L}_{2}(\nu)}$ implies that

$\displaystyle\mathcal{N}\big{(}\epsilon,G,\|\cdot\|\big{)}$
$\displaystyle=\mathcal{N}\bigg{(}\frac{\epsilon}{\sqrt{|\mathcal{Q}|}},G,\|\cdot\|_{\mathcal{L}_{2}(\nu)}\bigg{)}\leq
3\bigg{(}\frac{2e|\mathcal{Q}|}{\epsilon^{2}}\log\frac{3e|\mathcal{Q}|}{\epsilon^{2}}\bigg{)}^{d+2}.$
(D.3)

Using this in Theorem 7 (with $M=\sqrt{|\mathcal{Q}|}$), we get that

$\displaystyle\mathcal{N}\left(\epsilon,\mathscr{F}_{R,\lambda_{N}}^{\rm
sh},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\right)$
$\displaystyle\leq\left[\frac{|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon}{\epsilon}\times\left\\{\frac{2e(4|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon)}{\epsilon}\times\mathcal{N}\left(\frac{\epsilon}{8\sqrt{|\mathcal{Q}|}R^{2}\lambda_{N}},G,\|\cdot\|\right)\right\\}^{R}\right]^{R}$
$\displaystyle\leq\left[\frac{|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon}{\epsilon}\times\left\\{\frac{2e(4|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon)}{\epsilon}\times
3\bigg{(}\frac{128e|\mathcal{Q}|^{2}R^{4}\lambda_{N}^{2}}{\epsilon^{2}}\log\frac{192e|\mathcal{Q}|^{2}R^{4}\lambda_{N}^{2}}{\epsilon^{2}}\bigg{)}^{d+2}\right\\}^{R}\right]^{R}$
$\displaystyle=\left[\frac{|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon}{\epsilon}\times\left\\{\frac{6e(4|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon)}{\epsilon}\times\bigg{(}\frac{256e|\mathcal{Q}|^{2}R^{4}\lambda_{N}^{2}}{\epsilon^{2}}\log\frac{\sqrt{192e}|\mathcal{Q}|R^{2}\lambda_{N}}{\epsilon}\bigg{)}^{d+2}\right\\}^{R}\right]^{R}$
$\displaystyle\leq\left[\frac{|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon}{\epsilon}\times\left\\{\frac{6e(4|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon)}{\epsilon}\times\bigg{(}\frac{256e\times\sqrt{192e}\times(|\mathcal{Q}|R^{2}\lambda_{N})^{3}}{\epsilon^{3}}\bigg{)}^{d+2}\right\\}^{R}\right]^{R}~{}(\text{using
}\log(x)\leq x)$
$\displaystyle\leq\left(\frac{6e\times(16\sqrt{e}\,|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon)}{\epsilon}\right)^{(3d+7)R^{2}+R}.$

We summarize this in the following Lemma.

######  Lemma 5.

For the shallow CovNet class of operators
$\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm sh}$, the
${|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}$-covering
number is bounded as

$\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm
sh},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}\leq\left(\frac{c_{0}\times(c_{1}|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon)}{\epsilon}\right)^{(3d+7)R^{2}+R},$

where $c_{0}$ and $c_{1}$ are constants independent of all the other
parameters. In particular, when $R,\lambda_{N}\to\infty$, we get

$\log\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm
sh},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}=\mathcal{O}\bigg{(}dR^{2}\log\Big{(}\frac{R^{2}\lambda_{N}+\epsilon}{\epsilon}\Big{)}\bigg{)}.$

###  D.2 Covering number of the deep CovNet class

The (restricted) deep CovNet class of kernels is defined as

$\mathscr{F}_{R,L,\mathbf{p},\lambda_{N}}^{\rm
d}=\left\\{\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,g_{r}(\text{\bf
u})\,g_{s}(\text{\bf
v}):g_{r}\in\mathcal{D}_{L,\mathbf{p}},0\preceq\Lambda=(\lambda_{r,s})\preceq\lambda_{N}\mathrm{I}_{R}\right\\},$

which is again of the form $\mathscr{F}_{R,G,\lambda_{N}}$, where
$G=\mathcal{D}_{L,\mathbf{p}}$ is the class of deep neural networks with depth
$L$ and layer-wise widths $p_{1},\ldots,p_{L}$ (2.2).

Let $K=p_{1}+\cdots+p_{L}$ be the number of _computation units_ of a network
from the class $\mathcal{D}_{L,\mathbf{p}}$ and
$W=\sum_{\ell=1}^{L}p_{\ell}(p_{\ell-1}+1)+p_{L}$ be the number of _adjustable
parameters_ (see Anthony and Bartlett, 1999, Chapter 6 for details). Now, by
Anthony and Bartlett (1999, Theorem 18.8), we can find constants
$\alpha_{1},\alpha_{2},\alpha_{3}$ such that for any probability distribution
$\nu$ on $\mathbb{R}^{d}$,

$\log\mathcal{N}(\epsilon,\mathcal{D}_{L,\mathbf{p}},\|\cdot\|_{\mathcal{L}_{2}(\nu)})\leq\alpha_{1}\textrm{fat}_{\mathcal{D}_{L,\mathbf{p}}}(\alpha_{2}\epsilon)\log^{2}\left(\frac{\textrm{fat}_{\mathcal{D}_{L,\mathbf{p}}}(\alpha_{2}\epsilon^{2})}{\epsilon}\right),$

where $\textrm{fat}_{\mathscr{F}}(\cdot)$ is the _fat-shattering dimension_ of
the class of functions $\mathscr{F}$ (see Anthony and Bartlett, 1999, Chapter
11). Thus, using (D.3)

$\displaystyle\log\mathcal{N}(\epsilon,\mathcal{D}_{L,\mathbf{p}},\|\cdot\|)$
$\displaystyle=\log\mathcal{N}\left(\frac{\epsilon}{\sqrt{|\mathcal{Q}|}},\mathcal{D}_{L,\mathbf{p}},\|\cdot\|_{\mathcal{L}_{2}(\nu)}\right)$
$\displaystyle\leq\alpha_{1}\textrm{fat}_{\mathcal{D}_{L,\mathbf{p}}}\left(\alpha_{2}\frac{\epsilon}{\sqrt{|\mathcal{Q}|}}\right)\log^{2}\left(\frac{\textrm{fat}_{\mathcal{D}_{L,\mathbf{p}}}(\alpha_{2}\epsilon^{2}/|\mathcal{Q}|)\sqrt{|\mathcal{Q}|}}{\epsilon}\right).$

Again, for any $\delta>0$,
$\textrm{fat}_{\mathscr{F}}(\delta)\leq\textrm{Pdim}(\mathscr{F})$, where
$\textrm{Pdim}(\mathscr{F})$ is the _pseudo-dimension_ of the class of
functions $\mathscr{F}$ (see Anthony and Bartlett, 1999, Theorem 11.13(i)).
Using this in the previous equation, we get

$\log\mathcal{N}(\epsilon,\mathcal{D}_{L,\mathbf{p}},\|\cdot\|)\leq\alpha\,\textrm{Pdim}(\mathcal{D}_{L,\mathbf{p}})\log^{2}\left(\frac{\textrm{Pdim}(\mathcal{D}_{L,\mathbf{p}})\sqrt{|\mathcal{Q}|}}{\epsilon}\right),$

for some positive constant $\alpha$. Finally, since the activation function is
sigmoidal, using Theorem 14.2 in Anthony and Bartlett (1999), we get

$\textrm{Pdim}(\mathcal{D}_{L,\mathbf{p}})\leq\big{(}(W+2)K\big{)}^{2}+11(W+2)K\log_{2}\big{(}18(W+2)K^{2}\big{)}=:d_{W,K}.$

Now, Theorem 7 gives us that

$\displaystyle\log\mathcal{N}(\epsilon,\mathscr{F}^{\rm
d}_{R,L,\mathbf{p},\lambda_{N}},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})})$
$\displaystyle\kern 21.52771pt\leq
R\left[\log\bigg{(}\frac{|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon}{\epsilon}\bigg{)}+R\left\\{\log\bigg{(}\frac{2e(4|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon)}{\epsilon}\bigg{)}+\log\mathcal{N}\bigg{(}\frac{\epsilon}{8\sqrt{|\mathcal{Q}|}R^{2}\lambda_{N}},\mathcal{D}_{L,\mathbf{p}},\|\cdot\|\bigg{)}\right\\}\right]$
$\displaystyle\kern 21.52771pt\leq
R\left[\log\bigg{(}\frac{|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon}{\epsilon}\bigg{)}+R\left\\{\log\bigg{(}\frac{2e(4|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon)}{\epsilon}\bigg{)}+\alpha\,d_{W,K}\log^{2}\bigg{(}\frac{8|\mathcal{Q}|d_{W,K}R^{2}\lambda_{N}}{\epsilon}\bigg{)}\right\\}\right]$
$\displaystyle\kern 21.52771pt\leq
R\Big{\\{}1+R\big{(}1+\alpha\,d_{W,K}\big{)}\Big{\\}}\log^{2}\bigg{(}\frac{c_{0}|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon}{\epsilon}\bigg{)}$
$\displaystyle\kern
21.52771pt=\Big{\\{}\big{(}1+\alpha\,d_{W,K}\big{)}R^{2}+R\Big{\\}}\log^{2}\bigg{(}\frac{c_{0}d_{W,K}|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon}{\epsilon}\bigg{)},$

for some constant $c_{0}$ and $\alpha$. We summarize it in the following
lemma.

######  Lemma 6.

Consider the deep CovNet class of operators $\widetilde{\mathscr{F}}^{\rm
d}_{R,L,\mathbf{p},\sigma}$, where $L$ is the number of hidden layers and
$\mathbf{p}=(p_{1},\ldots,p_{L})$ are the number of nodes at each of the
hidden layers, $\sigma$ is the sigmoidal activation function, and $R$ is the
number of components of the model. Then, there exist constants $\alpha$ and
$c_{0}$ such that

$\log\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}^{\rm
d}_{R,L,\mathbf{p},\sigma},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}\leq\big{\\{}(1+\alpha\,d_{W,K})R^{2}+R\big{\\}}\,\log^{2}\bigg{(}\frac{c_{0}d_{W,K}|\mathcal{Q}|R^{2}\lambda_{N}+\epsilon}{\epsilon}\bigg{)},$

where $W=\sum_{\ell=1}^{L}p_{\ell}(p_{\ell-1}+1)+p_{L}$,
$K=\sum_{\ell=1}^{L}p_{\ell}$, and
$d_{W,K}=\big{(}(W+2)K\big{)}^{2}+11(W+2)K\log_{2}\big{(}18(W+2)K^{2}\big{)}$.

######  Remark 12.

If we define $p_{\rm max}=\max\\{d,p_{1},\ldots,p_{L}\\}$, then
$W=\mathcal{O}(Lp_{\rm max}^{2})$, $K=\mathcal{O}(Lp_{\rm max})$, and hence
$d_{W,K}=\mathcal{O}(L^{4}p_{\max}^{6})$. This shows that

$\log\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}^{\rm
d}_{R,L,\mathbf{p},\sigma},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}=\mathcal{O}\bigg{(}L^{4}R^{2}p_{\rm
max}^{6}\,\log^{2}\Big{(}\frac{L^{4}R^{2}\lambda_{N}p_{\rm
max}^{6}+\epsilon}{\epsilon}\Big{)}\bigg{)}.$

In particular, when $p_{1},\ldots,p_{L}=R$ and $R>d$, we get that

$\log\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}^{\rm
d}_{R,L,\mathbf{p},\sigma},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}=\mathcal{O}\bigg{(}L^{4}R^{8}\,\log^{2}\Big{(}\frac{L^{4}R^{8}\lambda_{N}+\epsilon}{\epsilon}\Big{)}\bigg{)}.$

###  D.3 Covering number of the deepshared CovNet class

Although the deepshared CovNet kernel has a similar structure to the deep
CovNet kernel, unfortunately, Theorem 7 is not useful to bound the covering
number of the deepshared CovNet class of operators. This is due to the fact
that the shared structure of the constituents $g_{1},\ldots,g_{R}$ of a
deepshared CovNet kernel
$\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,g_{r}(\text{\bf
u})\,g_{s}(\text{\bf v})$ cannot be catered for using Theorem 7. So, here, we
proceed in a different way.

First, consider a kernel $g$ from the deepshared CovNet class of kernels
$\mathscr{F}^{\rm ds}_{R,L,\mathbf{p},\sigma}$ (see (2.2)). We have
demonstrated that the kernel $g$ is a neural network (see Figure 3). For
constants $\theta$ and $\mu$, we define another kernel $g^{\prime}$ associated
to $g$ as follows:

$g^{\prime}(\text{\bf u},\text{\bf v})=\textrm{{1}}\\{\theta\,g(\text{\bf
u},\text{\bf v})+\mu>0\\},~{}~{}\text{\bf u},\text{\bf v}\in\mathcal{Q}.$

The kernel $g^{\prime}$ also has the neural network structure (see Figure 13).
It has one additional input and one additional layer than $g$, and the output
has the _linear threshold_ activation function. We define
$\mathscr{F}^{\prime}$ to be the class of all derived kernels from the
deepshared CovNet kernel class $\mathscr{F}^{\rm ds}_{R,L,\mathbf{p},\sigma}$.

Figure 13: A schematic representation of the network $g^{\prime}$ derived from
a deepshared network $g$.

By construction, using Theorem 14.1 in Anthony and Bartlett (1999), we get
that

$\displaystyle\textrm{Pdim}(\mathscr{F}^{\rm
ds}_{R,L,\mathbf{p},\sigma})\leq\textrm{VCdim}(\mathscr{F}^{\prime}),$ (D.4)

where $\textrm{VCdim}(\mathscr{F})$ is the Vapnik-Cherbonenkis dimension of
the class of functions $\mathscr{F}$. Let $\bm{\theta}\in\mathbb{R}^{W}$
denote all the free parameters of the kernel $g^{\prime}$ (i.e., the weights
and biases of the different layers). It is not difficult to see that
$W=\sum_{l=1}^{L}p_{l}(p_{l-1}+1)+R(p_{L}+1)+R(R+1)/2+2$, where $p_{0}=d$.
Thus, $g^{\prime}$ can be viewed as a function from $\mathbb{R}^{2d\times W}$
to $\mathbb{R}$, which maps an element $\text{\bf w}=(\text{\bf
u}^{\top},\text{\bf v}^{\top})^{\top}\in\mathbb{R}^{2d}$ and
$\bm{\theta}\in\mathbb{R}^{W}$ to $g^{\prime}(\text{\bf u},\text{\bf v})$.
Also, the function can be evaluated using
$t:=4\sum_{l=1}^{L}p_{l}(p_{l-1}+1)+4R(p_{L}+1)+2R^{2}+2$ basic operations of
the form:

  * •

the exponential function $x\mapsto\exp(x)$,

  * •

the arithmetic operations $+,-,\times,\div$ on real numbers,

  * •

jumps conditioned on $>,\geq,<,\leq,=,\neq$ and comparisons of real numbers,

and the output is $\\{0,1\\}$-valued. Moreover, only
$K=2\sum_{l=1}^{L}p_{l}+2R$ of these operations involve the application of the
exponential function. Thus, from Theorem 8.14 in Anthony and Bartlett (1999),
we get that

$\displaystyle\mathrm{VCdim}(\mathscr{F}^{\prime})\leq(W(K+1))^{2}+11W(K+1)(t+\log_{2}(9W(K+1)).$
(D.5)

Combining (D.4) and (D.5), we get that

$\displaystyle\mathrm{Pdim}(\mathscr{F}^{\rm
ds}_{R,L,\mathbf{p},\sigma})\leq(W(K+1))^{2}+11W(K+1)(t+\log_{2}(9W(K+1))=:d_{W,K,t}.$
(D.6)

Now, using the same derivations used for the deep CovNet class, we get

$\displaystyle\log\mathcal{N}\big{(}\epsilon,\mathscr{F}^{\rm
ds}_{R,L,\mathbf{p},\sigma},\|\cdot\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\big{)}=\log\mathcal{N}\bigg{(}\frac{\epsilon}{|\mathcal{Q}|},\mathscr{F}^{\rm
ds}_{R,L,\mathbf{p},\sigma},\|\cdot\|_{\mathcal{L}_{2}(\nu)}\bigg{)}$
$\displaystyle\leq\alpha_{1}\mathrm{fat}_{\mathscr{F}^{\rm
ds}_{R,L,\mathbf{p},\sigma}}\bigg{(}\alpha_{2}\frac{\epsilon}{|\mathcal{Q}|}\bigg{)}\,\log^{2}\Bigg{(}\frac{\mathrm{fat}_{\mathscr{F}^{\rm
ds}_{R,L,\mathbf{p},\sigma}}\Big{(}\frac{\alpha_{2}\epsilon^{2}}{|\mathcal{Q}|^{2}}\Big{)}|\mathcal{Q}|}{\epsilon}\Bigg{)}~{}~{}\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{anthony1999}{\@@citephrase{,
}}{}, Theorem~{}18.8)}}$
$\displaystyle\leq\alpha_{1}\mathrm{Pdim}(\mathscr{F}^{\rm
ds}_{R,L,\mathbf{p},\sigma})\,\log^{2}\bigg{(}\frac{|\mathcal{Q}|\,\mathrm{Pdim}(\mathscr{F}^{\rm
ds}_{R,L,\mathbf{p},\sigma})}{\epsilon}\bigg{)}~{}~{}\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{anthony1999}{\@@citephrase{,
}}{}, Theorem~{}11.13(i))}}$
$\displaystyle\leq\alpha_{1}\,d_{W,K,t}\,\log^{2}\bigg{(}\frac{|\mathcal{Q}|\,d_{W,K,t}}{\epsilon}\bigg{)}.~{}~{}~{}~{}\text{(by
\eqref{eq:cover_deepshared_pdim_bound2})}$

We summarize this in the following lemma.

######  Lemma 7.

Consider the deepshared CovNet class of operators
$\widetilde{\mathscr{F}}^{\rm ds}_{R,L,\mathbf{p},\sigma}$, where $L$ is the
number of hidden layers and $\mathbf{p}=(p_{1},\ldots,p_{L})$ are the number
of nodes at each of the hidden layers, $\sigma$ is the sigmoidal activation
function, and $R$ is the number of components of the model. Then, there exists
$\alpha>0$ such that

$\log\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}^{\rm
ds}_{R,L,\mathbf{p},\sigma},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}\leq\alpha\,d_{W,K,t}\,\log^{2}\bigg{(}\frac{|\mathcal{Q}|\,d_{W,K,t}}{\epsilon}\bigg{)},$

where $W=\sum_{l=1}^{L}p_{l}(p_{l-1}+1)+R(p_{L}+1)+R(R+1)/2+2$,
$K=2\sum_{l=1}^{L}p_{l}+2R$,
$t=4\sum_{l=1}^{L}p_{l}(p_{l-1}+1)+4R(p_{L}+1)+2R^{2}+2$, and
$d_{W,K,t}=\big{(}W(K+1)\big{)}^{2}+11W(K+1)\,\big{(}t+\log_{2}(9W(K+1)\big{)}$.

######  Remark 13.

By defining $p_{\rm max}=\max\\{d,p_{1},\ldots,p_{L}\\}$, we get
$W=\mathcal{O}(Lp_{\rm max}^{2}+Rp_{\max}+R^{2})$, $K=\mathcal{O}(Lp_{\rm
max}+R)$ and $t=\mathcal{O}(Lp_{\rm max}^{2}+Rp_{\rm max}+R^{2})$. Thus,
$d_{W,K,t}=\mathcal{O}(L^{4}p_{\rm max}^{6}+R^{6}+L^{2}R^{2}p_{\rm
max}^{4}+L^{2}R^{4}p_{\rm max}^{2}+LR^{3}p_{\rm max}^{3})$. In particular,
when $p_{1}=\ldots=p_{L}=R$ and $R\geq d$, we get that
$d_{W,K,t}=\mathcal{O}(L^{4}R^{6})$, and hence

$\log\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}^{\rm
ds}_{R,L,\mathbf{p},\sigma},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}=\mathcal{O}\bigg{(}L^{4}R^{6}\,\log^{2}\Big{(}\frac{LR}{\epsilon}\Big{)}\bigg{)}.$

##  Appendix E Proofs of the asymptotic results

Here, we provide detailed proofs of the asymptotic properties of the CovNet
estimators, as laid out in Section 6. We will first derive our results for a
general class of models, and then obtain the corresponding results for the
CovNet structures as special cases. To be precise, consider a general class of
operators $\widetilde{\mathscr{F}}_{N}$ (depending on $N$ and possibly on
other parameters, which we suppress for ease of exposition) satisfying
${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}\leq\gamma_{N}$
for every $\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$. Define the following
estimator based on $\widetilde{\mathscr{F}}_{N}$:

$\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}\in\operatornamewithlimits{arg\,min}_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{N}-\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2},$

where
$\widehat{\mathcal{C}}_{N}=N^{-1}\sum_{n=1}^{N}\mathcal{X}_{n}\otimes\mathcal{X}_{n}$
is the empirical covariance operator based on
$\mathcal{X}_{1},\ldots,\mathcal{X}_{N}$. We will prove two types of results
for this estimator based on two _bias-variance-type_ decomposition.

  1. (A)

Consistency: We will show that
${|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\leq
B_{N}+2V_{N}$, where
$B_{N}:=\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}-\mathcal{C}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}$
is the _bias_ of the estimator and $V_{N}$ is the _variance_ term, defined as
$V_{N}=\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\Big{|}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{|}$.
We will derive conditions for convergence of $V_{N}$ to $0$ in terms of $N$,
$\gamma_{N}$, $\beta_{N}$ and
$\mathcal{N}(\cdot,\widetilde{\mathscr{F}}_{N},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2})$,
the covering number of $\widetilde{\mathscr{F}}_{N}$ w.r.t. the
${|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}$
norm (see Appendix D for details). This will be used to establish weak (in
probability) or strong (almost sure) convergence of the estimator.

  2. (B)

Rate of convergence: Here, we will show that
${|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\leq\widetilde{B}_{N}+\widetilde{V}_{N}$,
where the bias term satisfies
$\mathbb{E}\widetilde{B}_{N}=2\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}$.
The variance term in this case is
$\widetilde{V}_{N}=\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-2\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}$.
We will derive an upper bound on $\mathbb{P}(\widetilde{V}_{N}>\epsilon)$ in
terms of $N$, $\gamma_{N}$, $\beta_{N}$ and the covering number of
$\widetilde{\mathscr{F}}_{N}$. This will be used to derive an upper bound for
$\mathbb{E}\widetilde{V}_{N}$ and subsequently, the rate of convergence.

###  E.1 Consistency

We start with the consistency. In what follows, we denote by $\mathscr{X}_{N}$
the data at hand, i.e.,
$\mathscr{X}_{N}=\\{\mathcal{X}_{1},\ldots,\mathcal{X}_{N}\\}$. Since
$\widehat{\mathcal{C}}_{N}$ is an unbiased estimator of $\mathcal{C}$, for any
operator $\mathcal{G}$,

$\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}-\mathcal{C}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}.$
(E.1)

Now, let $\widetilde{\mathcal{C}}_{N}$ be a random element distributed
identically to $\widehat{\mathcal{C}}_{N}$ and independent of
$\mathscr{X}_{N}$ (e.g., generated as the empirical covariance of i.i.d.
observations distributed identically to
$\mathcal{X}_{1},\ldots,\mathcal{X}_{N}$, but independent of
$\mathscr{X}_{N}$). Then, using (E.1) we obtain

$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}$
$\displaystyle=\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\,|\,\mathscr{X}_{N}\Big{)}-\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}$
$\displaystyle=\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\,|\,\mathscr{X}_{N}\Big{)}-\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}+\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}.$

Now,

$\displaystyle\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}=\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\Big{\\{}\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{\\}}=\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}=B_{N},$

where we have used (E.1). For the other part, we write

$\displaystyle\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\,|\,\mathscr{X}_{N}\Big{)}-\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}$
$\displaystyle=\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{\\{}\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\,|\,\mathscr{X}_{N}\Big{)}-\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}\bigg{\\}}$
$\displaystyle\leq\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{\\{}\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\,|\,\mathscr{X}_{N}\Big{)}-{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}+{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}\bigg{\\}}$
$\displaystyle\leq
2\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}-\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\bigg{|}=:2V_{N},$

where we have used that
$\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}\in\widetilde{\mathscr{F}}_{N}$,
${|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\leq{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}$
and
$\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}=\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}$
for $\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$. Using these, we get the
_bias-variance_ type decomposition

$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\leq
B_{N}+2V_{N},$ (E.2)

where
$B_{N}=\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}$
and
$V_{N}=\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\big{|}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}-\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\big{|}$.
The bias term $B_{N}$ converges to $0$, which follows from the universal
approximation property of the different CovNet models. To control the variance
term $V_{N}$, we use the following lemma which gives conditions under which it
converges to $0$.

######  Lemma 8.

Let $\widetilde{\mathscr{F}}_{N}$ be a class of operators with
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\leq\gamma_{N}$
for every $\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$. Let
$\mathcal{X}_{1},\ldots,\mathcal{X}_{N}\overset{{\rm
i.i.d.}}{\sim}\mathcal{X}$, with
$\mathbb{P}(\|\mathcal{X}\|^{2}\leq\beta_{N})=1$ and
$\mathbb{E}(\mathcal{X})=0$. Define
$V_{N}=\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\big{|}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\big{|}$.
If for every $u>0$,

$\frac{(\beta_{N}+\gamma_{N})^{4}}{N}\times\log\mathcal{N}\bigg{(}\frac{u}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\to
0\text{ as }N\to\infty,$

then $V_{N}\overset{P}{\to}0$ as $N\to\infty$. If in addition
$(\beta_{N}+\gamma_{N})^{4}/N^{1-\delta}\to 0$ for some $\delta\in(0,1)$, then
$V_{N}\overset{a.s.}{\to}0$ as $N\to\infty$.

###### Proof.

The proof is divided into two parts. First, we derive conditions under which
$V_{N}-\mathbb{E}V_{N}$ converges to $0$, in probability or almost surely
(Corollary 3). Then, we derive conditions under which $\mathbb{E}V_{N}$
converges to $0$ (Corollary 4). We start with the following lemma.

######  Lemma 9.

Consider the setup of Lemma 8. Then, for all $t\geq 0$,

$\mathbb{P}\big{(}|V_{N}-\mathbb{E}V_{N}|>t\big{)}\leq
2\exp\bigg{\\{}-\frac{Nt^{2}}{8\beta_{N}^{2}(\beta_{N}+\gamma_{N})^{2}}\bigg{\\}}.$

As a consequence, we get the following.

######  Corollary 3.

Consider the setup of Lemma 8.

  1. (a)

If $\beta_{N}^{2}(\beta_{N}+\gamma_{N})^{2}/N\to 0$, then
$V_{N}-\mathbb{E}V_{N}\overset{P}{\to}0$ as $N\to\infty$.

  2. (b)

If $\beta_{N}^{2}(\beta_{N}+\gamma_{N})^{2}/N^{1-\delta}\to 0$ for some
$\delta\in(0,1)$, then $V_{N}-\mathbb{E}V_{N}\overset{a.s.}{\to}0$ as
$N\to\infty$.

###### Proof.

Part (a) about convergence in probability is easy. For part (b), note that for
any $t\geq 0$,

$\sum_{n=1}^{\infty}\mathbb{P}\big{(}|V_{N}-\mathbb{E}V_{N}|\geq t\big{)}\leq
2\sum_{n=1}^{\infty}\exp\bigg{\\{}-\frac{Nt^{2}}{8\beta_{N}^{2}(\beta_{N}+\gamma_{N})^{2}}\bigg{\\}}=2\sum_{n=1}^{\infty}\exp\bigg{\\{}-N^{\delta}\frac{N^{1-\delta}t^{2}}{8\beta_{N}^{2}(\beta_{N}+\gamma_{N})^{2}}\bigg{\\}}<\infty.$

The result now follows from the Borel-Cantelli lemma. ∎

###### Proof of Lemma 9.

For any $\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$,

${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}=\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}-\mathcal{X}_{n}\otimes\mathcal{X}_{n},\mathcal{G}-\mathcal{X}_{m}\otimes\mathcal{X}_{m}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}.$
(E.3)

For $\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$, define
$h_{\mathcal{G}}:\mathcal{L}_{2}(\mathcal{Q})\times\mathcal{L}_{2}(\mathcal{Q})\to\mathbb{R}$
as

$h_{\mathcal{G}}(x,y)={\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}-x\otimes
x,\mathcal{G}-y\otimes
y\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2},~{}x,y\in\mathcal{L}_{2}(\mathcal{Q}).$

Then, for any $x,y\in\mathcal{L}_{2}(\mathcal{Q})$ with
$\|x\|^{2},\|y\|^{2}\leq\beta_{N}$, we get

$\displaystyle\big{|}h_{\mathcal{G}}(x,x)-h_{\mathcal{G}}(y,y)\big{|}$
$\displaystyle=\Big{|}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-x\otimes
x|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-y\otimes
y|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{|}=\Big{|}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle
y\otimes y-x\otimes x,2\mathcal{G}-x\otimes x-y\otimes
y\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}\Big{|}$
$\displaystyle\leq\big{(}\|x\|^{2}+\|y\|^{2}\big{)}\,\big{(}2{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}+\|x\|^{2}+\|y\|^{2}\Big{)}\leq
4\beta_{N}(\beta_{N}+\gamma_{N}).$

Also, for any $x,y,z\in\mathcal{L}_{2}(\mathcal{Q})$ with
$\|x\|^{2},\|y\|^{2},\|z\|^{2}\leq\beta_{N}$

$\displaystyle\big{|}h_{\mathcal{G}}(x,z)-h_{\mathcal{G}}(y,z)\big{|}$
$\displaystyle=\Big{|}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}-x\otimes
x,\mathcal{G}-z\otimes
z\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}-{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}-y\otimes
y,\mathcal{G}-z\otimes
z\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}\Big{|}$
$\displaystyle=\Big{|}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle
y\otimes y-x\otimes x,\mathcal{G}-z\otimes
z\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}\Big{|}\leq\big{(}\|x\|^{2}+\|y\|^{2}\big{)}\,\big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}+\|z\|^{2}\big{)}\leq
2\beta_{N}(\beta_{N}+\gamma_{N}).$

Now, for $\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$, define
$f_{\mathcal{G}}:\mathcal{L}_{2}(\mathcal{Q})^{N}\to\mathbb{R}$ as
$f_{\mathcal{G}}(x_{1},\ldots,x_{N})=\sum_{n=1}^{N}\sum_{m=1}^{N}h_{\mathcal{G}}(x_{n},x_{m})$.
The function $f_{\mathcal{G}}$ is symmetric in its arguments, and for any
$x,x^{\prime},x_{2},\ldots,x_{N}\in\mathcal{L}_{2}(\mathcal{Q})$ with squared
norm bounded by $\beta_{N}$,

$\big{|}f_{\mathcal{G}}(x,x_{2},\ldots,x_{N})-f_{\mathcal{G}}(x^{\prime},x_{2},\ldots,x_{N})\big{|}\leq
4N\beta_{N}(\beta_{N}+\gamma_{N}).$

Then, by defining $g:\mathcal{L}_{2}(\mathcal{Q})^{N}\to\mathbb{R}$ as

$g(x_{1},\ldots,x_{N})=\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\Big{|}\sum_{n=1}^{N}\sum_{m=1}^{N}\big{\\{}h_{\mathcal{G}}(x_{n},x_{m})-\mathbb{E}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})\big{\\}}\Big{|}=\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\Big{|}f_{\mathcal{G}}(x_{1},\ldots,x_{N})-\mathbb{E}f_{\mathcal{G}}(\mathcal{X}_{1},\ldots,\mathcal{X}_{N})\Big{|},$

we get that $g$ is a symmetric function in its arguments, and for any
$\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$,

$\displaystyle\Big{|}f_{\mathcal{G}}(x,x_{2},\ldots,x_{N})-\mathbb{E}f_{\mathcal{G}}(\mathcal{X}_{1},\ldots,\mathcal{X}_{N})\Big{|}-g(x^{\prime},x_{2},\ldots,x_{N})$
$\displaystyle\leq\Big{|}f_{\mathcal{G}}(x,x_{2},\ldots,x_{N})-\mathbb{E}f_{\mathcal{G}}(\mathcal{X}_{1},\ldots,\mathcal{X}_{N})\Big{|}-\Big{|}f_{\mathcal{G}}(x^{\prime},x_{2},\ldots,x_{N})-\mathbb{E}f_{\mathcal{G}}(\mathcal{X}_{1},\ldots,\mathcal{X}_{N})\Big{|}$
$\displaystyle\leq\Big{|}f_{\mathcal{G}}(x,x_{2},\ldots,x_{N})-f_{\mathcal{G}}(x^{\prime},x_{2},\ldots,x_{N})\Big{|}\leq
4N\beta_{N}(\beta_{N}+\gamma_{N}).$

This, upon taking supremum over $\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$
and interchanging the roles of $x,x^{\prime}$, gives us

$|g(x,x_{2},\ldots,x_{N})-g(x^{\prime},x_{2},\ldots,x_{N})|\leq
4N\beta_{N}(\beta_{N}+\gamma_{N}).$

Now, using the method of bounded difference (Wainwright, 2019, Corollary
2.21), we get that, for all $t\geq 0$,

$\mathbb{P}\big{(}|g(\mathcal{X}_{1},\ldots,\mathcal{X}_{N})-\mathbb{E}g(\mathcal{X}_{1},\ldots,\mathcal{X}_{N})|>t\big{)}\leq
2\exp\bigg{\\{}-\frac{t^{2}}{8N^{3}\beta_{N}^{2}(\beta_{N}+\gamma_{N})^{2}}\bigg{\\}}.$

The proof is complete upon noting that
$V_{N}=g(\mathcal{X}_{1},\ldots,\mathcal{X}_{N})/N^{2}$ (cf. (E.3)). ∎

Next, we derive bounds on $\mathbb{E}V_{N}$.

######  Lemma 10.

Consider the setup of Lemma 8. Then, for every $u>0$,

$\displaystyle\mathbb{E}V_{N}\leq 4u$
$\displaystyle+\frac{16(\beta_{N}+\gamma_{N})^{2}}{N^{3}u}\times\mathcal{N}\bigg{(}\frac{Nu}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\times\exp\bigg{\\{}-\frac{N^{3}u^{2}}{4(\beta_{N}+\gamma_{N})^{2}}\bigg{\\}}$
$\displaystyle+\frac{128(\beta_{N}+\gamma_{N})^{4}}{Nu}\times\mathcal{N}\bigg{(}\frac{u}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\times\exp\bigg{\\{}-\frac{Nu^{2}}{32(\beta_{N}+\gamma_{N})^{4}}\bigg{\\}}.$

This gives us the following condition for the convergence of $\mathbb{E}V_{N}$
to $0$.

######  Corollary 4.

Consider the setup of Lemma 8. If for every $u>0$,

$\frac{(\beta_{N}+\gamma_{N})^{4}}{N}\times\log\mathcal{N}\bigg{(}\frac{u}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\to
0\text{ as }N\to\infty,$

then $\mathbb{E}V_{N}\to 0$ as $N\to\infty$.

###### Proof.

The condition ensures that for every $u>0$,
$\lim_{N\to\infty}\mathbb{E}V_{N}\leq 4u$. The proof is completed upon taking
limit as $u$ goes to $0$. ∎

###### Proof of Lemma 10.

Let $\mathcal{X}_{1}^{\prime},\ldots,\mathcal{X}_{N}^{\prime}\overset{{\rm
i.i.d.}}{\sim}\mathcal{X}$ be independent of
$\mathcal{X}_{1},\ldots,\mathcal{X}_{N}$. Now,

$\displaystyle\mathbb{E}V_{N}$
$\displaystyle=\mathbb{E}\Bigg{\\{}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})-\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}\mathbb{E}h_{\mathcal{G}}(\mathcal{X}_{n}^{\prime},\mathcal{X}_{m}^{\prime})\bigg{|}\Bigg{\\}}$
$\displaystyle=\mathbb{E}\Bigg{[}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\Bigg{\\{}\mathbb{E}\bigg{|}\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})-\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}h_{\mathcal{G}}(\mathcal{X}_{n}^{\prime},\mathcal{X}_{m}^{\prime})\bigg{|}\,\Big{|}\mathcal{D}_{N}\Bigg{\\}}\Bigg{]}$
$\displaystyle\leq\mathbb{E}\Bigg{[}\mathbb{E}\Bigg{\\{}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})-\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}h_{\mathcal{G}}(\mathcal{X}_{n}^{\prime},\mathcal{X}_{m}^{\prime})\bigg{|}\,\Big{|}\mathcal{D}_{N}\Bigg{\\}}\Bigg{]}~{}~{}(\text{by
Fatou's lemma})$
$\displaystyle=\mathbb{E}\Bigg{\\{}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})-\frac{1}{N^{2}}\sum_{n=1}^{N}\sum_{m=1}^{N}h_{\mathcal{G}}(\mathcal{X}_{n}^{\prime},\mathcal{X}_{m}^{\prime})\bigg{|}\Bigg{\\}}$
$\displaystyle\leq\frac{1}{N^{2}}\mathbb{E}\Bigg{[}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\sum_{n=1}^{N}\Big{\\{}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})-h_{\mathcal{G}}(\mathcal{X}_{n}^{\prime},\mathcal{X}_{n}^{\prime})\Big{\\}}\bigg{|}+\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\operatorname*{\sum\sum}_{1\leq
n\neq m\leq
N}\Big{\\{}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})-h_{\mathcal{G}}(\mathcal{X}_{n}^{\prime},\mathcal{X}_{m}^{\prime})\Big{\\}}\bigg{|}\Bigg{]}$
$\displaystyle=:E_{1}+E_{2}.$ (E.4)

By symmetry, we can show that

$\displaystyle
E_{1}\leq\frac{2}{N^{2}}\mathbb{E}\bigg{[}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\sum_{n=1}^{N}\zeta_{n}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})\bigg{|}\bigg{]}\text{
and
}E_{2}\leq\frac{2}{N^{2}}\mathbb{E}\bigg{[}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\operatorname*{\sum\sum}_{1\leq
n\neq m\leq
N}\zeta_{n}\zeta_{m}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})\bigg{|}\bigg{]},$
(E.5)

where $\zeta_{1},\ldots,\zeta_{N}$ are i.i.d.  _Rademacher_ random variables,
which take the values $\pm 1$ with equal probability, independent of all the
other variables. Next, we derive upper bounds on

$\mathbb{E}\bigg{[}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\sum_{n=1}^{N}\zeta_{n}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})\bigg{|}\bigg{]}\text{
and
}\frac{2}{N^{2}}\mathbb{E}\bigg{[}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\operatorname*{\sum\sum}_{1\leq
n\neq m\leq
N}\zeta_{n}\zeta_{m}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})\bigg{|}\bigg{]}.$

For any $\mathcal{G}_{1},\mathcal{G}_{2}\in\widetilde{\mathscr{F}}_{N}$,

$\displaystyle\bigg{|}\frac{1}{N}\sum_{n=1}^{N}\zeta_{n}\big{\\{}h_{\mathcal{G}_{1}}(\mathcal{X}_{n},\mathcal{X}_{n})-h_{\mathcal{G}_{2}}(\mathcal{X}_{n},\mathcal{X}_{n})\big{\\}}\bigg{|}$
$\displaystyle=\bigg{|}\frac{1}{N}\sum_{n=1}^{N}\zeta_{n}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}_{1}-\mathcal{G}_{2},\mathcal{G}_{1}+\mathcal{G}_{2}-2\mathcal{X}_{n}\otimes\mathcal{X}_{n}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}\bigg{|}$
$\displaystyle\leq{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}_{1}-\mathcal{G}_{2}|\kern-1.07639pt|\kern-1.07639pt|}_{2}\times\frac{1}{N}\sum_{n=1}^{N}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}_{1}+\mathcal{G}_{2}-2\mathcal{X}_{n}\otimes\mathcal{X}_{n}|\kern-1.07639pt|\kern-1.07639pt|}_{2}$
$\displaystyle\leq
2(\beta_{N}+\gamma_{N})\times{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}_{1}-\mathcal{G}_{2}|\kern-1.07639pt|\kern-1.07639pt|}_{2}.$

Now, for $\delta>0$, let $\widetilde{\mathscr{F}}_{N}(\delta)$ be an
$\delta$-cover of the least possible size for $\widetilde{\mathscr{F}}_{N}$
w.r.t. the
${|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}$
norm. Then, using the previous equation, for all $t>0$,

$\displaystyle\mathbb{P}\Bigg{\\{}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\frac{1}{N}\sum_{n=1}^{N}\zeta_{n}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})\bigg{|}>t\Bigg{\\}}$
$\displaystyle=\mathbb{E}\,\mathbb{P}\Bigg{\\{}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\frac{1}{N}\sum_{n=1}^{N}\zeta_{n}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})\bigg{|}>t\,\Big{|}\,\mathscr{X}_{N}\Bigg{\\}}$
$\displaystyle\leq\mathbb{E}\,\mathbb{P}\Bigg{\\{}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}\big{(}\frac{t}{4(\beta_{N}+\gamma_{N})}\big{)}}\bigg{|}\frac{1}{N}\sum_{n=1}^{N}\zeta_{n}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})\bigg{|}>\frac{t}{2}\,\Big{|}\,\mathscr{X}_{N}\Bigg{\\}}$
$\displaystyle\leq\Big{|}\widetilde{\mathscr{F}}_{N}\Big{(}\frac{t}{4(\beta_{N}+\gamma_{N})}\Big{)}\Big{|}\times\mathbb{E}\Bigg{[}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}\big{(}\frac{t}{4(\beta_{N}+\gamma_{N})}\big{)}}\mathbb{P}\bigg{\\{}\bigg{|}\frac{1}{N}\sum_{n=1}^{N}\zeta_{n}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})\bigg{|}>\frac{t}{2}\,\Big{|}\,\mathscr{X}_{N}\bigg{\\}}\Bigg{]}.$

Note that the cardinality of $\widetilde{\mathscr{F}}_{N}(\delta)$ is
$\mathcal{N}(\delta,\widetilde{\mathscr{F}}_{N},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2})$.
Also, $\sum_{n=1}^{N}h_{\mathcal{G}}^{2}(\mathcal{X}_{n},\mathcal{X}_{n})\leq
N(\beta_{N}+\gamma_{N})^{2}$ for all
$\mathcal{G}\in\widetilde{\mathscr{F}}_{N}(t/(4(\beta_{N}+\gamma_{N})))$. So,
using the Bernstein’s inequality we get that for all
$\mathcal{G}\in\widetilde{\mathscr{F}}_{N}(t/(4(\beta_{N}+\gamma_{N})))$,

$\displaystyle\mathbb{P}\bigg{\\{}\bigg{|}\frac{1}{N}\sum_{n=1}^{N}\zeta_{n}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})\bigg{|}>\frac{t}{2}\,\Big{|}\,\mathscr{X}_{N}\bigg{\\}}\leq
2\,\exp\bigg{\\{}-\frac{Nt^{2}}{4(\beta_{N}+\gamma_{N})^{2}}\bigg{\\}},$

where the bound is free of $\mathscr{X}_{N}$. All these give us that for all
$t>0$,

$\displaystyle\mathbb{P}\Bigg{\\{}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\frac{1}{N}\sum_{n=1}^{N}\zeta_{n}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})\bigg{|}>t\Bigg{\\}}\leq
2\times\mathcal{N}\bigg{(}\frac{t}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\times\exp\bigg{\\{}-\frac{Nt^{2}}{4(\beta_{N}+\gamma_{N})^{2}}\bigg{\\}}.$
(E.6)

Again, for any
$\mathcal{G}_{1},\mathcal{G}_{2}\in\widetilde{\mathscr{F}}_{N}$,

$\displaystyle\bigg{|}\frac{1}{N^{2}}\operatorname*{\sum\sum}_{1\leq m\neq
n\leq
N}\zeta_{n}\zeta_{m}\big{\\{}h_{\mathcal{G}_{1}}(\mathcal{X}_{n},\mathcal{X}_{m})-h_{\mathcal{G}_{2}}(\mathcal{X}_{n},\mathcal{X}_{m})\big{\\}}\bigg{|}$
$\displaystyle=\bigg{|}\frac{1}{N^{2}}\operatorname*{\sum\sum}_{1\leq m\neq
n\leq
N}\zeta_{n}\zeta_{m}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}_{1}-\mathcal{G}_{2},\mathcal{G}_{1}+\mathcal{G}_{2}-\mathcal{X}_{n}\otimes\mathcal{X}_{n}-\mathcal{X}_{m}\otimes\mathcal{X}_{m}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}\bigg{|}$
$\displaystyle\leq{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}_{1}-\mathcal{G}_{2}|\kern-1.07639pt|\kern-1.07639pt|}_{2}\times\frac{1}{N^{2}}\operatorname*{\sum\sum}_{1\leq
n\neq m\leq
N}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}_{1}+\mathcal{G}_{2}-\mathcal{X}_{n}\otimes\mathcal{X}_{n}-\mathcal{X}_{m}\otimes\mathcal{X}_{m}|\kern-1.07639pt|\kern-1.07639pt|}_{2}$
$\displaystyle\leq
2\,(\beta_{N}+\gamma_{N})\,{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}_{1}-\mathcal{G}_{2}|\kern-1.07639pt|\kern-1.07639pt|}_{2}.$

Using this, and proceeding in a similar way as before, we can show that for
all $t>0$,

$\displaystyle\mathbb{P}\Bigg{\\{}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\frac{1}{N^{2}}\operatorname*{\sum\sum}_{1\leq
m\neq n\leq
N}\zeta_{n}\zeta_{m}h_{\mathcal{G}}(\mathcal{X}_{m},\mathcal{X}_{n})\bigg{|}>t\Bigg{\\}}$
$\displaystyle\leq\mathcal{N}\bigg{(}\frac{t}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\bigg{)}\times\mathbb{E}\Bigg{[}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}\big{(}\frac{t}{4(\beta_{N}+\gamma_{N})}\big{)}}\mathbb{P}\bigg{\\{}\bigg{|}\frac{1}{N^{2}}\operatorname*{\sum\sum}_{1\leq
m\neq n\leq
N}\zeta_{n}\zeta_{m}h_{\mathcal{G}}(\mathcal{X}_{m},\mathcal{X}_{n})\bigg{|}>\frac{t}{2}\,\Big{|}\,\mathscr{X}_{N}\bigg{\\}}\Bigg{]}.$

Note that
$|h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})|\leq(\beta_{N}+\gamma_{N})^{2}$
almost surely for all $\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$. Thus, using
the method of bounded difference (Wainwright, 2019, Corollary 2.21), we can
show that for all
$\mathcal{G}\in\widetilde{\mathscr{F}}_{N}(t/(4(\beta_{N}+\gamma_{N})))$,

$\displaystyle\mathbb{P}\bigg{\\{}\bigg{|}\frac{1}{N^{2}}\operatorname*{\sum\sum}_{1\leq
m\neq n\leq
N}\zeta_{n}\zeta_{m}h_{\mathcal{G}}(\mathcal{X}_{m},\mathcal{X}_{n})\bigg{|}>\frac{t}{2}\,\Big{|}\,\mathscr{X}_{N}\bigg{\\}}\leq
2\,\exp\bigg{\\{}-\frac{Nt^{2}}{32(\beta_{N}+\gamma_{N})^{4}}\bigg{\\}},$

for all $t>0$. Thus, we finally get that for all $t>0$,

$\displaystyle\mathbb{P}\Bigg{\\{}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\frac{1}{N^{2}}\operatorname*{\sum\sum}_{1\leq
n\neq m\leq
N}\zeta_{n}\zeta_{m}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})\bigg{|}>t\Bigg{\\}}$
$\displaystyle\kern 129.16626pt\leq
2\times\mathcal{N}\bigg{(}\frac{t}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\times\exp\bigg{\\{}-\frac{Nt^{2}}{32(\beta_{N}+\gamma_{N})^{4}}\bigg{\\}}.$
(E.7)

Now, for a non-negative random variable $Y$,

$\mathbb{E}(Y)=\int_{0}^{\infty}\mathbb{P}(Y>t)\,\mathrm{d}t\leq
u+\int_{u}^{\infty}\mathbb{P}(Y>t)\,\mathrm{d}t,$

holds for every $u>0$. Using this with (E.6), we get that

$\displaystyle\mathbb{E}\Bigg{[}\frac{1}{N^{2}}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\sum_{n=1}^{N}\zeta_{n}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{n})\bigg{|}>t\Bigg{]}$
$\displaystyle\kern 21.52771pt\leq
u+2\int_{u}^{\infty}\mathcal{N}\bigg{(}\frac{Nt}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\times\exp\bigg{\\{}-\frac{N^{3}t^{2}}{4(\beta_{N}+\gamma_{N})^{4}}\bigg{\\}}\,\mathrm{d}t$
$\displaystyle\kern 21.52771pt\leq
u+2\times\mathcal{N}\bigg{(}\frac{Nu}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\int_{u}^{\infty}\exp\bigg{\\{}-\frac{N^{3}ut}{4(\beta_{N}+\gamma_{N})^{4}}\bigg{\\}}\,\mathrm{d}t$
$\displaystyle\kern
21.52771pt=u+2\times\frac{4(\beta_{N}+\gamma_{N})^{2}}{N^{3}u}\times\mathcal{N}\bigg{(}\frac{Nu}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\times\exp\bigg{\\{}-\frac{N^{3}u^{2}}{4(\beta_{N}+\gamma_{N})^{4}}\bigg{\\}}.$

Similarly, from (E.1), we get

$\displaystyle\mathbb{E}\Bigg{[}\frac{1}{N^{2}}\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{|}\operatorname*{\sum\sum}_{1\leq
n\neq m\leq
N}\zeta_{n}\zeta_{m}h_{\mathcal{G}}(\mathcal{X}_{n},\mathcal{X}_{m})\bigg{|}>t\Bigg{]}$
$\displaystyle\kern 21.52771pt\leq
u+2\times\frac{32(\beta_{N}+\gamma_{N})^{4}}{Nu}\times\mathcal{N}\bigg{(}\frac{u}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{N},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\times\exp\bigg{\\{}-\frac{Nu^{2}}{32(\beta_{N}+\gamma_{N})^{4}}\bigg{\\}}.$

The proof is complete upon substituting these upper bounds in (E.1) in
addition to (E.5). ∎

The proof of Lemma 8 now follows upon noting that the stipulated assumptions
imply that the conditions of Corollaries 3 and 4 are satisfied. ∎

Next, we derive an upper bound on the Hilbert-Schmidt norm of an operator from
the shallow, deep and deepshared CovNet classes. In particular, we get the
following.

######  Proposition 2.

Let $\widetilde{\mathscr{F}}_{N}$ be any of the three CovNet classes of
operators (i.e., shallow/deepshared/deep). Then, for any
$\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$,
${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}\leq
R\lambda_{N}|\mathcal{Q}|$.

###### Proof.

We start with the class of shallow CovNet operators
$\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm sh}$. Let
$\mathcal{G}\in\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm sh}$ be an
operator with kernel of the form

$g(\text{\bf u},\text{\bf
v})=\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,\sigma(\mathbf{w}_{r}^{\top}\text{\bf
u}+b_{r})\,\sigma(\mathbf{w}_{s}^{\top}\text{\bf v}+b_{s}),\quad\text{\bf
u},\text{\bf v}\in\mathcal{Q},$

where $\Lambda=(\lambda_{r,s})$ satisfies
$\mathrm{0}\preceq\Lambda\preceq\lambda_{N}\mathrm{I}_{R}$. Since $g$ is a
non-negative definite kernel

$\|g\|_{\mathcal{L}_{\infty}(\mathcal{Q}\times\mathcal{Q})}:=\sup_{\text{\bf
u},\text{\bf v}\in\mathcal{Q}}|g(\text{\bf u},\text{\bf v})|=\sup_{\text{\bf
u}\in\mathcal{Q}}g(\text{\bf u},\text{\bf u}).$

It is easy to see that for any $\text{\bf u}\in\mathcal{Q}$,

$g(\text{\bf u},\text{\bf
u})=\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,\sigma(\mathbf{w}_{r}^{\top}\text{\bf
u}+b_{r})\,\sigma(\mathbf{w}_{s}^{\top}\text{\bf
u}+b_{s})=\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,a_{r}\,a_{s}={\bf
a}^{\top}\Lambda{\bf a},$

where $a_{r}=\sigma(\mathbf{w}_{r}^{\top}\text{\bf u}+b_{r}),r=1,\ldots,R$,
and ${\bf a}=(a_{1},\ldots,a_{R})^{\top}$. Since
$0\preceq\Lambda\preceq\lambda_{N}{\rm I}_{R}$, ${\bf a}^{\top}\Lambda{\bf
a}\leq\lambda_{N}{\bf a}^{\top}{\bf a}=\lambda_{N}\sum_{r=1}^{R}a_{r}^{2}$.
Also, since $\sigma$ is a sigmoidal activation function, $0\leq a_{r}\leq 1$
for $r=1,\ldots,R$. This gives us
$\|g\|_{\mathcal{L}_{\infty}(\mathcal{Q}\times\mathcal{Q})}\leq R\lambda_{N}$,
which in turn shows

$\|g\|^{2}_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}=\iint_{\mathcal{Q}\times\mathcal{Q}}g^{2}(\text{\bf
u},\text{\bf v})\,\mathrm{d}\text{\bf u}\,\mathrm{d}\text{\bf v}\leq
R^{2}\lambda_{N}^{2}|\mathcal{Q}|^{2}.$

Thus, for every $\mathcal{G}\in\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm
sh}$,
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}=\|g\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\leq
R\lambda_{N}|\mathcal{Q}|$, proving the result for the shallow CovNet class.
For the deep and the deepshared CovNet classes, consider a kernel of the form

$g(\text{\bf u},\text{\bf
v})=\sum_{r=1}^{R}\sum_{s=1}^{R}\lambda_{r,s}\,g_{r}(\text{\bf
u})\,g_{s}(\text{\bf v}),\quad\text{\bf u},\text{\bf v}\in\mathcal{Q},$

where $\|g_{r}\|_{\mathcal{L}_{\infty}(\mathcal{Q})}\leq M$ for all
$r=1,\ldots,R$, and
$\mathrm{0}\preceq\Lambda=(\lambda_{r,s})\preceq\lambda_{N}\,\mathrm{I}_{R}$.
Then, similarly to the previous derivations, it can be shown that
$\|g\|_{\mathcal{L}_{\infty}(\mathcal{Q}\times\mathcal{Q})}\leq
R\lambda_{N}M^{2}$ and
$\|g\|_{\mathcal{L}_{2}(\mathcal{Q}\times\mathcal{Q})}\leq
R\lambda_{N}M^{2}|\mathcal{Q}|$. Since our activation function is sigmoidal,
in particular since $|\sigma(t)|\leq 1$ for all $t$, it follows that $M\leq
1$. Thus, for the deep as well as the deepshared CovNet class, we get that
$\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}\leq
R\lambda_{N}|\mathcal{Q}|$. ∎

Now, we combine the pieces together. For the shallow CovNet estimator, using
(E.2), we get that

${|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}^{\rm
sh}_{R,N}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\leq
B_{N}+2V_{N},$

where $B_{N}=\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm
sh}}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}$
and $V_{N}=\sup_{\mathcal{G}\in\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm
sh}}\big{|}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-\mathbb{E}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\big{|}$.
By Theorem 1 and Remark 11, $B_{N}\to 0$ as $R,\lambda_{N}\to\infty$. From
Lemma 8, we know that $V_{N}\overset{P}{\to}0$ if, for all $u>0$,

$\frac{(\beta_{N}+\gamma_{N})^{4}}{N}\times\log\mathcal{N}\bigg{(}\frac{u}{4(\beta_{N}+\gamma_{N})},\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm
sh},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\bigg{)}\to
0\text{ as }N\to\infty,$

and $V_{N}\overset{a.s.}{\to}0$ if additionally
$(\beta_{N}+\gamma_{N})^{4}/N^{1-\delta}\to 0$ for some $\delta\in(0,1)$,
where
$\gamma_{N}=\operatornamewithlimits{arg\,max}_{\mathcal{G}\in\widetilde{\mathscr{F}}_{R,\lambda_{N}}^{\rm
sh}}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}$.
By Proposition 2, $\gamma_{N}\leq R\lambda_{N}|\mathcal{Q}|$. Also, Lemma 5
shows that

$\log\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}^{\rm
sh}_{R,\lambda_{N}},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}=\mathcal{O}\bigg{(}dR^{2}\log\Big{(}\frac{R^{2}\lambda_{N}+\epsilon}{\epsilon}\Big{)}\bigg{)},~{}~{}\text{
as }R,\lambda_{N}\to\infty.$

Thus, when $R,\lambda_{N}\to\infty$ as $N\to\infty$ in such a way that
$dR^{2}\Delta_{N}^{4}\log(\Delta_{N})/N\to 0$, where
$\Delta_{N}=\max\\{\beta_{N},\gamma_{N}\\}=\max\\{\beta_{N},|\mathcal{Q}|R\lambda_{N}\\}$,
it is easy to see that the condition for convergence of $V_{N}$ to $0$ in
probability is satisfied. This shows the convergence of
${|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{R,N}^{\rm
sh}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}$ to $0$ in
probability as $N\to\infty$. For almost sure convergence, we additionally
require $(\beta_{N}+\gamma_{N})^{4}/N^{1-\delta}\to 0$ for some
$\delta\in(0,1)$, or equivalently $\Delta_{N}^{4}/N^{1-\delta}\to 0$ as
$N\to\infty$. This proves part (A) of Theorem 3.

The proof of parts (B) and (C) follow similarly upon noting that by
Proposition 2,
${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}\leq
R\lambda_{N}|\mathcal{Q}|$ for all
$\mathcal{G}\in\widetilde{\mathscr{F}}_{R,L,\lambda_{N}}^{\rm d}$ or
$\widetilde{\mathscr{F}}_{R,L,\lambda_{N}}^{\rm ds}$, and the following about
the covering numbers:

$\displaystyle\log\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}^{\rm
d}_{R,L,\lambda_{N}},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}$
$\displaystyle=\mathcal{O}\bigg{(}L^{4}R^{8}\,\log^{2}\Big{(}\frac{L^{4}R^{8}\lambda_{N}+\epsilon}{\epsilon}\Big{)}\bigg{)}\quad\text{(Lemma~{}\ref{lemma:cover_covnet_deep}
and Remark~{}\ref{remark:cover_deep_order}), and }$
$\displaystyle\log\mathcal{N}\big{(}\epsilon,\widetilde{\mathscr{F}}^{\rm
ds}_{R,L,\lambda_{N}},{|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}_{2}\big{)}$
$\displaystyle=\mathcal{O}\bigg{(}L^{4}R^{6}\,\log^{2}\Big{(}\frac{LR}{\epsilon}\Big{)}\bigg{)}\quad\text{(Lemma~{}\ref{lemma:cover_covnet_deepshared}
and Remark~{}\ref{remark:cover_deepshared_order})}.$

###  E.2 Rates of convergence

To derive the rate of convergence, we use a different bias-variance type
decomposition. Recall that $\widetilde{\mathcal{C}}_{N}$ is a random element,
distributed identically to $\widehat{\mathcal{C}}_{N}$ independently of the
data $\mathscr{X}_{N}$. Using (E.1), we get

$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}$
$\displaystyle=\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\,\big{|}\,\mathscr{X}_{N}\Big{)}-\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}$
$\displaystyle=\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\,\big{|}\,\mathscr{X}_{N}\Big{)}-\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-2\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}$
$\displaystyle\kern
198.05493pt+2\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}$
$\displaystyle=:\widetilde{V}_{N}+\widetilde{B}_{N}.$ (E.8)

For the second component, we can write

$\displaystyle\widetilde{B}_{N}=2\bigg{(}\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\bigg{)}=2\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)},$

so that

$\displaystyle\mathbb{E}\widetilde{B}_{N}$
$\displaystyle=2\mathbb{E}\bigg{\\{}\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}\bigg{\\}}$
$\displaystyle\leq
2\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}\bigg{\\{}\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}\bigg{\\}}=2\inf_{\mathcal{G}\in\widetilde{\mathscr{F}}_{N}}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2},$
(E.9)

where in the last step we have used (E.1). This is the bias of the estimator
which, according to the universal approximation theorem, converges to $0$.

Next, we focus on the variance term $\widetilde{V}_{N}$. For $t>0$, we get

$\displaystyle\mathbb{P}\big{(}\widetilde{V}_{N}>t\big{)}=\mathbb{P}\bigg{\\{}\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\,\big{|}\,\mathscr{X}_{N}\Big{)}-\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-2\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\widehat{\mathcal{C}}_{\widetilde{\mathscr{F}}_{N}}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}>t\bigg{\\}}$
$\displaystyle\kern
21.52771pt\leq\mathbb{P}\bigg{\\{}\exists\,\mathcal{G}\in\widetilde{\mathscr{F}}_{N}:\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widetilde{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-2\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}>t\bigg{\\}}$
$\displaystyle\kern
21.52771pt=\mathbb{P}\bigg{\\{}\exists\,\mathcal{G}\in\widetilde{\mathscr{F}}_{N}:\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-2\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}>t\bigg{\\}}~{}~{}(\text{since
}\widetilde{\mathcal{C}}_{N}\operatorname{\overset{\cal
D}{=}}\widehat{\mathcal{C}}_{N})$ $\displaystyle\kern
21.52771pt=\mathbb{P}\bigg{\\{}\exists\,\mathcal{G}\in\widetilde{\mathscr{F}}_{N}:\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}$
$\displaystyle\kern
215.2771pt>\frac{1}{2}\bigg{(}\frac{t}{2}+\frac{t}{2}+\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}\bigg{)}\bigg{\\}}.$
(E.10)

To bound the last probability, we will use the following lemma, which is a
modified version of Theorem 11.4 in Györfi et al. (2002).

######  Lemma 11.

Let
$\mathcal{X}_{1},\ldots,\mathcal{X}_{N}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{X}\in\mathcal{L}_{2}(\mathcal{Q})$
be such that $\mathbb{P}(\|\mathcal{X}\|^{2}\leq\beta)=1$,
$\mathbb{E}(\mathcal{X})=0$ and
$\mathbb{E}(\mathcal{X}\otimes\mathcal{X})=\mathcal{C}$. Define
$\widehat{\mathcal{C}}_{N}=N^{-1}\sum_{n=1}^{N}\mathcal{X}_{n}\otimes\mathcal{X}_{n}$
to be the empirical covariance operator based on
$\mathcal{X}_{1},\ldots,\mathcal{X}_{N}$. Let $\widetilde{\mathscr{F}}$ be a
class of operators satisfying
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}\leq\gamma$
for all $\mathcal{G}\in\widetilde{\mathscr{F}}$. Then, for every $a,b>0$ and
$\delta\in\big{(}0,\frac{1}{2}\big{]}$,

$\displaystyle\mathbb{P}\Bigg{[}\exists\,\mathcal{G}\in\widetilde{\mathscr{F}}:\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}$
$\displaystyle\kern
215.2771pt>\delta\bigg{\\{}a+b+\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\big{)}\bigg{\\}}\Bigg{]}$
$\displaystyle\leq 14\times\mathcal{N}\bigg{(}\frac{\epsilon
b}{80(\beta+\gamma)^{3}},\widetilde{\mathscr{F}},{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\bigg{)}\times\exp\bigg{\\{}-\frac{\epsilon^{2}(1-\epsilon)aN}{214(\beta+\gamma)^{4}\,(1+\epsilon)}\bigg{\\}}.$

###### Proof.

Note that for any $\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$,

$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\widehat{\mathcal{C}}_{N}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}$
$\displaystyle={|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-\frac{2}{N}\sum_{n=1}^{N}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}-\mathcal{C},\mathcal{X}_{n}\otimes\mathcal{X}_{n}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}^{2}$
$\displaystyle=\frac{1}{N}\sum_{n=1}^{N}\big{(}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}-{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}-2{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}-\mathcal{C},\mathcal{X}_{n}\otimes\mathcal{X}_{n}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}\big{)}$
$\displaystyle=\frac{1}{N}\sum_{n=1}^{N}\big{\\{}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}-\mathcal{X}_{n}\otimes\mathcal{X}_{n}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}-{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}-\mathcal{X}_{n}\otimes\mathcal{X}_{n}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}\big{\\}}.$

Thus, the probability in question equals

$\displaystyle\mathbb{P}\Bigg{[}\exists\,\mathcal{G}\in\widetilde{\mathscr{F}}_{N}:\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\mathcal{X}\otimes\mathcal{X}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\mathcal{X}\otimes\mathcal{X}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}-\frac{1}{N}\sum_{n=1}^{N}\big{\\{}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}-\mathcal{X}_{n}\otimes\mathcal{X}_{n}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}-{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}-\mathcal{X}_{n}\otimes\mathcal{X}_{n}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}\big{\\}}$
$\displaystyle\kern
215.2771pt>\delta\bigg{\\{}a+b+\mathbb{E}\Big{(}{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}-\mathcal{X}\otimes\mathcal{X}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}-{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}-\mathcal{X}\otimes\mathcal{X}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\Big{)}\bigg{\\}}\Bigg{]},$

and we will derive an upper bound for this. For
$\mathcal{G}\in\widetilde{\mathscr{F}}_{N}$, define
$h_{\mathcal{G}}:\mathcal{L}_{2}(\mathcal{Q})\to\mathbb{R}$ by

$h_{\mathcal{G}}(x)={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}-x\otimes
x\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}-{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}-x\otimes
x\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2},~{}~{}x\in\mathcal{L}_{2}(\mathcal{Q}).$

With this, the probability in question can be written as

$\displaystyle\mathbb{P}\Big{\\{}\exists\,\mathcal{G}\in\widetilde{\mathscr{F}}_{N}:\mathbb{E}h_{\mathcal{G}}(\mathcal{X})-\frac{1}{N}\sum_{n=1}^{N}h_{\mathcal{G}}(\mathcal{X}_{i})\geq\epsilon\big{(}a+b+\mathbb{E}h_{\mathcal{G}}(\mathcal{X})\big{)}\Big{\\}}.$

We first note a few facts about the function $h_{\mathcal{G}}$. Note that

$-{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}-x\otimes
x\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}\leq
h_{\mathcal{G}}(x)\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}-x\otimes
x\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2},\text{ for all
}x\in\mathcal{L}_{2}(\mathcal{Q}).$

Thus, using
${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}_{1}+\mathcal{G}_{2}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}\leq
2({|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}_{1}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2}+{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}_{2}|\kern-1.07639pt|\kern-1.07639pt|}_{2}^{2})$,
with $\mathbb{P}\big{(}\|\mathcal{X}\|^{2}\leq\beta_{N}\big{)}=1$,
${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{C}|\kern-1.07639pt|\kern-1.07639pt|}_{2}\leq\beta_{N}$
and
${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{G}|\kern-1.07639pt|\kern-1.07639pt|}_{2}\leq\gamma_{N}$,
we get

$|h_{\mathcal{G}}(\mathcal{X})|\leq\max\\{4\beta_{N}^{2},2(\beta_{N}^{2}+\gamma_{N}^{2})\\}=:\eta_{N}\text{
almost surely for all }\mathcal{G}\in\widetilde{\mathscr{F}}_{N}.$ (E.11)

Again,

$\mathbb{E}h_{\mathcal{G}}(\mathcal{X})=\mathbb{E}\big{(}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}-\mathcal{X}\otimes\mathcal{X}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}-{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}-\mathcal{X}\otimes\mathcal{X}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}\big{)}={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}-\mathcal{C}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}\leq
2(\beta_{N}^{2}+\gamma_{N}^{2}).$ (E.12)

Using the alternative form
$h_{\mathcal{G}}(x)={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{G}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}-{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{C}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{2}^{2}-2{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}-\mathcal{C},x\otimes
x\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}$,
we get

$\displaystyle\textrm{Var}\big{(}h_{\mathcal{G}}(\mathcal{X})\big{)}=4\textrm{Var}\big{(}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}-\mathcal{C},\mathcal{X}\otimes\mathcal{X}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}\big{)}$
$\displaystyle\leq
4\mathbb{E}\big{(}{\left\langle\kern-2.15277pt\left\langle\kern-2.15277pt\left\langle\mathcal{G}-\mathcal{C},\mathcal{X}\otimes\mathcal{X}\right\rangle\kern-2.15277pt\right\rangle\kern-2.15277pt\right\rangle}_{2}^{2}\big{)}\leq