t_{1})\frac{8C_{\ref*{C_sum_Gamma_phi}}N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}{C_{\ref*{C_DMU}}^{2}\left(\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\right)}\right)\end{aligned}$
(124)

    2. (b)

When $\varepsilon=0$, (124) is still valid with not necessarily $N\geq
e^{-1}\left(\exp(2c_{\ref*{c_Men_1}}/\varepsilon)-4\right)$, but with
$C_{\ref*{C_noise_dependent_3}}$ replaced by
$32C_{\ref*{C_DMU}}c_{\ref*{c_Men_2}}$ and with $c_{\ref*{c_Men_3}}$ replaced
by $1$.

Proof. Recall that
${\boldsymbol{\epsilon}}={\boldsymbol{r}}+{\boldsymbol{\xi}}$. We have:

$\displaystyle{\boldsymbol{\epsilon}}^{\top}A{\boldsymbol{\epsilon}}={\boldsymbol{r}}^{\top}A{\boldsymbol{r}}+{\boldsymbol{\xi}}^{\top}A{\boldsymbol{\xi}}+{\boldsymbol{r}}^{\top}A{\boldsymbol{\xi}}+{\boldsymbol{\xi}}^{\top}A{\boldsymbol{r}}\leq
2\left\|A\right\|_{\text{op}}\left\|{\boldsymbol{r}}\right\|_{2}^{2}+2{\boldsymbol{\xi}}^{\top}A{\boldsymbol{\xi}}.$

By Hanson-Wright inequality, see, for example [Ver18, Theorem 6.2.1], there
exists some absolute constant $c>0$ such that for any $t_{1}\geq 0$,

$\displaystyle{\mathbb{P}}\left({\boldsymbol{\xi}}^{\top}A{\boldsymbol{\xi}}-\sigma_{\xi}^{2}\operatorname*{Tr}(A)\leq
t_{1}\sigma_{\xi}^{2}\operatorname*{Tr}(A)\right)\geq
1-\exp\left(-c(t_{1}^{2}\wedge
t_{1})\frac{\operatorname*{Tr}(A)}{\left\|A\right\|_{\text{op}}}\right).$

Let $\Omega_{\text{noise},1}$ as the random event on which

$\displaystyle\sqrt{\operatorname*{Tr}(A)}\leq\frac{4C_{\ref*{C_RIP_upper}}\sqrt{N}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}},\mbox{ and
}\left\|A\right\|_{\text{op}}^{1/2}\leq\frac{4C_{\ref*{C_RIP_upper}}\sqrt{N}\sigma\left(\square,\triangle\right)}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}.$

By (49) and (50), ${\mathbb{P}}(\Omega_{\text{noise},1})\geq
1-{\mathbb{P}}(\Omega_{0}^{c})$. In Lemma 3, let $Z=f^{*}(X)-f^{**}(X)$,
$q=2+\varepsilon$ for some $\varepsilon>0$, $r=2$, $p=1$. When $N\geq
e^{-1}\left(\exp(2c_{\ref*{c_Men_1}}/\varepsilon)-4\right)$, by Lemma 3, we
have $j_{0}=1$ and thus for $\beta=\varepsilon/4$, for any $t_{3}>2$, with
probability at least
$1-c_{\ref*{c_Men_3}}t_{3}^{-(2+\varepsilon)}N^{-\frac{\varepsilon}{4}}$,

$\displaystyle\left\|{\boldsymbol{r}}\right\|_{2}\leq
c_{\ref*{c_Men_2}}\left(\frac{2+\varepsilon}{2+\varepsilon-2(\varepsilon/4+1)}\right)^{1/2}t_{3}\left\|f^{*}-f^{**}\right\|_{L_{2+\varepsilon}}\sqrt{N}.$

Combining the above together, we obtain that for any $t_{1}\geq 0$ and
$t_{3}>2$,

$\displaystyle{\mathbb{P}}\bigg{(}{\boldsymbol{\epsilon}}^{\top}A{\boldsymbol{\epsilon}}\leq
2(1+t_{1})\sigma_{\xi}^{2}\frac{16C_{\ref*{C_RIP_upper}}^{2}N\left(\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}\right)}{\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)^{2}}+t_{3}^{2}C_{\ref*{C_noise_dependent_1}}^{2}\frac{\left(\sqrt{N}\sigma\left(\square,\triangle\right)\right)^{2}}{\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)^{2}}\left\|f^{*}-f^{**}\right\|_{L_{2+\varepsilon}}^{2}N\bigg{)}$
$\displaystyle\geq 1-{\mathbb{P}}(\Omega_{0}^{c})-\exp\left(-c(t_{1}^{2}\wedge
t_{1})\frac{\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}}{\sigma^{2}\left(\square,\triangle\right)}\right)-c_{\ref*{c_Men_3}}t_{3}^{-(2+\varepsilon)}N^{-\frac{\varepsilon}{4}},$

where
${C_{69}}=16C_{\ref*{C_RIP_upper}}^{2}c_{\ref*{c_Men_2}}\left(\frac{2+\varepsilon}{2+\varepsilon-2(\varepsilon/4+1)}\right)^{1/2}$.
In particular, when we use Markov’s inequality to replace Lemma 3, with the
probability deviation $t_{3}^{-2}$ instead of
$c_{\ref*{c_Men_3}}t_{3}^{-(2+\varepsilon)}N^{-\frac{\varepsilon}{4}}$, the
term $\sqrt{N}\left\|f^{*}-f^{**}\right\|_{L_{2+\varepsilon}}$ can be improved
to $\sqrt{N}\left\|f^{*}-f^{**}\right\|_{L_{2}}$.

Similarly, let $\Omega_{\text{noise},2}$ as the random event on which

$\displaystyle\operatorname*{Tr}(A)\leq\frac{16C_{\ref*{C_sum_Gamma_phi}}N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}{\left(4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})\right)^{2}}\mbox{
and
}\left\|A\right\|_{\text{op}}^{1/2}\leq\frac{4C_{\ref*{C_DMU}}}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}\left(\sqrt{\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}+\sqrt{N}\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\right).$

By (61) and (62), ${\mathbb{P}}(\Omega_{\text{noise},2})\geq
1-{\mathbb{P}}(\Omega_{0}^{c})$. Repeat the above arguments, we obtain that
for any $t_{1},t_{2}\geq 0$ and $t_{3}>2$,

$\displaystyle{\mathbb{P}}\bigg{(}{\boldsymbol{\epsilon}}^{\top}A{\boldsymbol{\epsilon}}\leq(1+t_{1})\sigma_{\xi}^{2}\frac{16C_{\ref*{C_sum_Gamma_phi}}^{2}N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}{(4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty}))^{2}}+t_{2}t_{3}\sigma_{\xi}\frac{C_{\ref*{C_noise_dependent_3}}\left(\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}^{2}\right)}{(4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty}))^{2}}\sqrt{N}\left\|f^{*}-f^{**}\right\|_{L_{2}}$
$\displaystyle+t_{3}^{2}\frac{C_{\ref*{C_noise_dependent_3}}\left(\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}^{2}\right)}{(4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty}))^{2}}N\left\|f^{*}-f^{**}\right\|_{L_{2+\varepsilon}}^{2}\bigg{)}$
$\displaystyle\geq
1-{\mathbb{P}}(\Omega_{0}^{c})-\exp(-ct_{2}^{2})-c_{\ref*{c_Men_3}}t_{3}^{-(2+\varepsilon)}N^{-\frac{\varepsilon}{4}}-\exp\left(-c(t_{1}^{2}\wedge
t_{1})\frac{8C_{\ref*{C_sum_Gamma_phi}}N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}{C_{\ref*{C_DMU}}^{2}\left(\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\right)}\right)$

where
${C_{70}}=32C_{\ref*{C_DMU}}c_{\ref*{c_Men_2}}\left(\frac{2+\varepsilon}{2+\varepsilon-2(\varepsilon/4+1)}\right)^{1/2}$.

For simplicity, we only consider the case where
$\sigma_{1}N>\kappa_{DM}(4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty}))$
and $k\lesssim N$. Replace the usage of Proposition 26 in Section 6.1 with
Proposition 27 and repeat the proof. We can conclude as follows:

######  Proposition 28.

Grant the assumptions of Theorem 4 and Proposition 27. Assume that
$\sigma_{1}N>\kappa_{DM}(4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty}))$.
Then with the same probability deviation as in Theorem 4 but with
$\bar{p}_{\xi}$ replaced by (123) and

$\displaystyle\left(\frac{C_{\ref*{C_noise}}\operatorname*{Tr}(\Gamma_{k+1:\infty})}{|J_{1}|\operatorname*{Tr}(\Gamma_{k+1:\infty})+N\left(\sum_{j\in
J_{2}}\sigma_{j}\right)}\right)^{\frac{r}{4}}$

replaced by (124), we have:

$\displaystyle\begin{aligned}
\left\|\hat{f}_{\lambda}-f^{*}\right\|_{L_{2}}&\lesssim\left\|f^{*}-f^{**}\right\|_{L_{2}}+\sigma_{\xi}\sqrt{\frac{\left|J_{1}\right|}{N}}+\sigma_{\xi}\sqrt{\frac{\sum_{j\in
J_{2}}\sigma_{j}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}}+\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{**}\right\|_{\cal
H}\\\
&+{\left\|\tilde{\Gamma}_{1,\mathrm{thre}}^{-1/2}f_{1:k}^{**}\right\|_{\cal
H}\frac{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}+4C_{\ref*{C_sum_Gamma_phi}}\sigma_{\xi}\frac{\sqrt{N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}\\\
&+\frac{C_{\ref*{C_noise_dependent_3}}^{1/2}\sqrt{\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}^{2}}}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}\sqrt{N}\left\|f^{*}-f^{**}\right\|_{L_{2+\varepsilon}}.\end{aligned}$
(125)

[Bac24, Section 7.5.2] uses
$\inf\\{\left\|f^{*}-f\right\|_{L_{2}}^{2}+\lambda\left\|f\right\|_{\cal
H}^{2}:f\in{\cal H}\\}$ to characterize the approximation error of ${\cal H}$,
that is, the trade-off between the approximation error and
$\left\|f\right\|_{\cal H}$. Our Proposition 28 shows that the approximation
error is actually traded off against
${\left\|\tilde{\Gamma}_{1,\mathrm{thre}}^{-1/2}f_{1:k}^{**}\right\|_{\cal
H}\frac{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}$ and
$\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{**}\right\|_{\cal H}$ instead
of $\left\|f^{**}\right\|_{\cal H}$.

We observe that when the following holds, we still have benign overfitting,
even though there is model-misspecification, when $\sigma_{\xi}\sim 1$: for
$k\lesssim N$ such that
$N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\lesssim\operatorname*{Tr}(\Gamma_{k+1:\infty})$,

$\displaystyle\begin{aligned} &\left|J_{1}\right|=o(N),\,\sum_{j\in
J_{2}}\sigma_{j}=o(\operatorname*{Tr}(\Gamma_{k+1:\infty})),\,\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{**}\right\|_{\cal
H}=o(1),\,{\left\|\tilde{\Gamma}_{1,\mathrm{thre}}^{-1/2}f_{1:k}^{**}\right\|_{\cal
H}\frac{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}=o(1),\\\
&\frac{\sqrt{N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}}{\operatorname*{Tr}(\Gamma_{k+1:\infty})}=o(1),\,\sqrt{N}\left\|f^{*}-f^{**}\right\|_{L_{2+\varepsilon}}=o\left(\frac{\operatorname*{Tr}(\Gamma_{k+1:\infty})}{\sqrt{\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}}\wedge\frac{\operatorname*{Tr}(\Gamma_{k+1:\infty})}{\sqrt{N}\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}}\wedge\sqrt{N}\right).\end{aligned}$
(126)

######  Remark 4.

We emphasize that this conclusion does not contradict the counterexamples
presented in [CLvdG22] and [Sha22] in the setting of adversarial noise and
model-misspecification. This is because in [CLvdG22],
$\|f^{*}-f^{**}\|_{L_{2}}=\Theta(\sigma_{\xi})$ (see [CLvdG22, Appendix D]);
in [Sha22], $f^{*}:{\boldsymbol{x}}\in\mathbb{R}^{d}\mapsto\exp(x_{1})$, where
$x_{1}$ is the first coordinate of ${\boldsymbol{x}}$, and
$f^{**}=\left<{\boldsymbol{x}},{\boldsymbol{\beta}}^{*}\right>$ for some
${\boldsymbol{\beta}}^{*}\in{\mathbb{R}}^{d}$. Under the probability measure
$\mu$ assumed in [Sha22, Example 1], $\left\|f^{*}-f^{**}\right\|_{L_{2}}$ is
$\inf_{\mathbf{w}\in{\mathbb{R}}^{d}}R_{d}(\mathbf{w})$ in the language of
[Sha22, Example 1], and it is grater than a constant depending only on $\mu$.
Therefore, when $\|f^{*}-f^{**}\|_{L_{2}}=\Theta(1)$, our (126) does not
necessarily yield benign overfitting, thus not conflicting with [CLvdG22,
Sha22].

####  6.5.10 Proof of Proposition 5

The proof of Proposition 5 is rather lengthy, and we complete it in Section
6.5.11, Section 6.5.12, Section 6.5.13, Section 6.5.14, and Section 6.5.19.
Section 6.5.19 relies on the proof of Theorem 9 in Section 6.5.15.

####  6.5.11 Spectrum of $\Gamma$.

The goal of this section is to use Theorem 4 and Theorem 5 to prove the
multiple descent phenomenon. For applying Theorem 4, we need to proceed with
the following steps:

  1. 1.

Verify Assumption 1, Assumption 2 and Assumption 5.

To achieve diagonal concentration, it suffices to verify (8), (15), and (16).
This is done in Section 6.5.13. To validate the norm-equivalence condition
stated in Assumption 1, Assumption 2, and Assumption 5, we will examine the
scenario where $\epsilon=6$ over the entire space ${\cal H}$. This shows the
norm-equivalence on ${\cal H}_{1:k}$ and ${\cal H}_{k+1:\infty}$, as these
subspaces are contained within ${\cal H}$. This is done in Section 6.5.12.

  2. 2.

Compute the appropriate $k$ such that $N\leq
c_{\ref*{c_kappa_DM}}\kappa_{DM}d_{0}^{*}\left(\Gamma_{k+1:\infty}^{1/2}B_{\cal
H}\right)$, and $k\leq c_{\ref*{c_RIP}}N$. In the context of multiple descent,
we will make use of Theorem 4, meaning that we will observe multiple descents
occurring when $k\lesssim N$. Given that
$\operatorname*{Tr}(\Gamma_{k+1:\infty})\sim 1$, our findings remain valid
even when $\lambda\lesssim 1$.

  3. 3.

Compute $\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)$,
$\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}$ and
$\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right)$.

The last two steps are done in the following two paragraphs.

In this subsection, the determination of the appropriate value for $k$ is
discussed. The selection of the value of $k$ can be divided into two distinct
scenarios: under a sub-Gaussian (the setup in [LRZ20]) or a uniform
distribution assumption (the setup in [GMMM21, MMM22, MM20, Mis22]) and for a
kernel $K$ such that (21) holds.

##### Sub-Gaussian design.

We have the following proposition, whose proof can be found in Section 6.5.14

######  Proposition 29.

Suppose that Assumption 6 holds. For a given $0\leq\iota\leq L-1$, there exist
absolute constants ${C_{71}}$ and ${c_{34}}$ (where
$c_{\ref*{c_multiple_upper}}$ depending on $L$) such that
$C_{\ref*{C_multiple_lower}}d^{\iota}\leq N\leq
c_{\ref*{c_multiple_upper}}d^{\iota+1}$. We consider $k\vcentcolon=\sum_{0\leq
l\leq\iota}d^{l}$ and decompose the kernel function into two terms:

$K(X,X)=h\left(\frac{\left\|X\right\|_{2}^{2}}{d}\right)=\sum_{0\leq
i\leq\iota}\alpha_{i}\left(\frac{\left\|X\right\|_{2}^{2}}{d}\right)^{i}+\sum_{i>\iota}\alpha_{i}\left(\frac{\left\|X\right\|_{2}^{2}}{d}\right)^{i}.$

Then,

$\displaystyle\frac{k}{N}\sim\frac{d^{\iota}}{N},\quad\frac{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}\sim\frac{1}{N},\quad\frac{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}}\gtrsim
d^{\iota+1}>c_{\ref*{c_kappa_DM}}\kappa_{DM}N,\quad\frac{\sqrt{N\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right)}}{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sim\sqrt{\frac{N}{d^{\iota+1}}}.$
(127)

It is worth noting that the selection of $k=\sum_{l\leq\iota}d^{l}$ means that
$\hat{f}_{0}$ learns $f_{\leq\iota}^{*}$ while considering $f_{>\iota}^{*}$ as
noise. By observing that $f_{\leq\iota}^{*}$ represents the projection onto
the subspace formed by the orthogonal polynomials of degree $\iota$ in the
Hilbert space $L_{2}(\mu)$, it becomes evident that $\hat{f}_{0}$ acquires
knowledge of a polynomial approximation of degree $\iota$ for $f^{*}$. By
increasing the number of samples inside the range of
$C_{\ref*{C_multiple_lower}}d^{\iota}\leq N\leq
c_{\ref*{c_multiple_upper}}d^{\iota+1}$ to
$C_{\ref*{C_multiple_lower}}d^{\iota+1}\leq N\leq
c_{\ref*{c_multiple_upper}}d^{\iota+2}$, a polynomial approximation may be
achieved with an additional degree. Proposition 29 is still valid when
$\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)$ is replaced by
$\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)$, where
$\lambda\lesssim 1$.

##### Uniform distribution design.

When $\Omega=\sqrt{d}S_{2}^{d-1}$ and $\mu$ (the distribution of $X$) is
uniform over $\sqrt{d}S_{2}^{d-1}$, $L_{2}(\sqrt{d}S_{2}^{d-1},\mu)$ admits an
orthonormal decomposition. The following statements are taken from [MMM22,
MM20, GMMM21, Mis22]. In fact, for $l\in{\mathbb{N}}$, let $\tilde{V}_{d,l}$
be the space of homogeneous harmonic polynomials of degree $l$ on
${\mathbb{R}}^{d}$, that is, the space of degree-$l$ polynomials
$q({\boldsymbol{x}})$ such that $\Delta q({\boldsymbol{x}})=0$, where $\Delta$
is the Laplacian. Let $V_{d,l}$ be the linear space of functions obtained by
restricting the polynomials in $\tilde{V}_{d,l}$ to $\sqrt{d}S_{2}^{d-1}$.
Then
$L_{2}(\sqrt{d}S_{2}^{d-1},\mu)=\oplus^{\perp}_{l\in{\mathbb{N}}}V_{d,l}$.
Furthermore, by [XHM+22, section 2], when $l<L$ and $L!=O(d)$, we have

$\displaystyle\dim\left(V_{d,l}\right)=\frac{d^{l}}{l!}+O(d^{l-1})\sim d^{l}.$
(128)

When Assumption 7 is true and for $0\leq\iota\leq L-1$ such that
$C_{\ref*{C_multiple_lower}}d^{\iota}\leq N\leq
c_{\ref*{c_multiple_upper}}d^{\iota+1}$, we define
$k=\sum_{l=0}^{\iota}\dim(V_{d,l})$. In the work of [XHM+22, section 2], it is
demonstrated that the eigenvalues with multiplicity (denoted by $\lambda_{l}$)
of the matrix $\Gamma$ exhibit a decay rate on the order of $d^{-l}$. Under
Assumption 7, $\sigma_{l}$ exhibits a multi-plateau trend as in the sub-
Gaussian case. Consequently, the spectrum of the variable $\Gamma$ exhibits
similarity to that of the sub-Gaussian design scenario, but with a constant
factor, and we decompose

$\displaystyle
K(X,X)=\sum_{i\leq\iota}\alpha_{i}\left(\frac{\left\|X\right\|_{2}^{2}}{d}\right)^{i}+\sum_{i>\iota}\alpha_{i}\left(\frac{\left\|X\right\|_{2}^{2}}{d}\right)^{i}=:K_{1:k}(X,X)+K_{k+1:\infty}(X,X)$
(129)

as well. Therefore,

$\displaystyle\frac{k}{N}\sim\frac{d^{\iota}}{N},\quad\frac{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}\sim\frac{1}{N},\quad\frac{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}}\gtrsim
d^{\iota+1}>c_{\ref*{c_kappa_DM}}\kappa_{DM}N,\quad\frac{\sqrt{N\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right)}}{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sim\sqrt{\frac{N}{d^{\iota+1}}}.$
(130)

In this way, we have completed the steps 2) and 3) outlined at the beginning
of this subsection. In the following two subsections, we will complete step
1).

####  6.5.12 Norm equivalence.

##### Under Assumption 6.

We strengthen [LRZ20, Lemma 10] from $L_{4}-L_{2}$ norm equivalence to
$L_{8}-L_{2}$ norm equivalence. The proof of the following Proposition can be
found in Section 6.5.20.

######  Proposition 30.

Under Assumption 6, there exists $\kappa\geq 1$ depending only on $L$ (with
exponential dependence), such that for all $f\in{\cal H}$,

$\displaystyle\left\|f\right\|_{L_{8}}\leq\kappa\left\|f\right\|_{L_{2}}.$

The proof of Proposition 30 may be found in Section 6.5.20.

##### Under Assumption 7.

For every $l\in{\mathbb{N}}$, $(V_{d,l},L_{2}(\mu))$ admits an ONB
$(Y_{l,m})_{m\leq\dim\left(V_{d,l}\right)}$ where
$(Y_{l,m})_{m\leq\dim\left(V_{d,l}\right)}$ are homogeneous polynomials of
degree $l$. For further details, please refer to section 4.2 of [FE12]. Given
that $\mu$ follows a uniform distribution over $\sqrt{d}S_{2}^{d-1}$ and
${\cal H}$ is a subset of $\oplus_{l>\iota}V_{d,l}$ that consists of
polynomials with degrees lower than $L$, (9) can be derived directly from the
work of [Bec92] by setting the values of the parameters $\epsilon=6$ and
$\kappa<3^{L}$, respectively.

####  6.5.13 Diagonal terms.

In this subsection, we check (8) under Assumption 7 and Assumption 6. The
concentration property of the diagonal terms appeared in Assumption 2 and
Assumption 5 followed by the same idea. The scenario described in Assumption 7
is comparatively simpler than the case outlined in Assumption 6. We therefore
prioritize addressing the former case initially.

##### Under Assumption 7.

Because $\mu$ is a uniform distribution over $\sqrt{d}S_{2}^{d-1}$, $K$ is a
translation-invariant kernel. Recall that we have chosen
$k=\sum_{l=0}^{\iota}\dim(V_{d,l})$. In fact,
$\left\|\phi_{k+1:\infty}(X)\right\|_{{\cal
H}}=\sqrt{K_{k+1:\infty}(X,X)}=\sqrt{\sum_{i>\iota}\alpha_{i}\left(\left\|X\right\|_{2}^{2}/d\right)^{i}}=\sqrt{\sum_{i=\iota+1}^{L}\alpha_{i}}=\sqrt{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}$
which is a constant. As a result, (8) follows by taking $\delta=\gamma=0$. The
validity of the diagonal terms appeared in Assumption 5 and Assumption 2
follows by noticing that $\sigma_{k}^{-1}\sim k$ and
$\sigma_{k+1}\sim\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})$ for our choice
of $k$. Hence $\left\|\Gamma_{1:k}^{-1/2}\phi_{1:k}(X)\right\|_{\cal
H}^{2}\leq\sigma_{k}^{-1}\left\|\phi_{1:k}(X)\right\|_{\cal H}^{2}\sim k$, and
$\left\|\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}\leq\sigma_{k+1}\left\|\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}\sim\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})$. As a result, we can
take ${\gamma_{\ref*{gamma_RIP_k>N}}}={\gamma_{\ref*{gamma_DMU_L2}}}=0$ and
$\delta_{\ref*{delta_DMU_L2}},\delta_{\ref*{delta_RIP_k>N}}\sim 1$.

##### Under Assumption 6.

Under Assumption 6, we need to develop a new concentration inequality similar
to the Hanson-Wright inequality for non-asymptotic verification of (8). For
the sake of generality, we will establish a concentration inequality for the
general kernel function $K$ in the following theorem, although we will only
utilize the special case of $K=K_{k+1:\infty}$.

######  Theorem 9.

Let $X\in{\mathbb{R}}^{d}$ be a random vector with i.i.d. mean zero
coordinates $(x_{i})_{i=1}^{d}$. Assume that $x_{1}$ is sub-Gaussian with the
sub-Gaussian norm denoted by $\left\|x_{1}\right\|_{\psi_{2}}$, that is to
say, for any $q\geq 2$, we have ${\mathbb{E}}x_{1}^{q}\leq
C_{\ref*{C_subgaussian}}q^{q/2}\left\|x_{1}\right\|_{\psi_{2}}^{q}$. Given
$L\in{\mathbb{N}}_{+}$, satisfying $L\geq 2$, and $2^{2L}L^{3L}<\sqrt{d}$.
Given $\gamma_{1},\cdots,\gamma_{L}\in{\mathbb{R}}$, we let
$h:t\in{\mathbb{R}}\mapsto\sum_{\iota=1}^{L}\gamma_{\iota}t^{\iota}$. We
suppose $h(1)\neq 0$ for the sake of simplicity. Define
$K:({\boldsymbol{x}},\mathbf{y})\in{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\mapsto
h(\left<{\boldsymbol{x}},\mathbf{y}\right>/d)\in{\mathbb{R}}$. There exists an
absolute constant ${C_{72}}$ depending on $L$ and
$\left\|x_{1}\right\|_{\psi_{2}}$, such that for any $t>0$, we have

$\displaystyle{\mathbb{P}}\left(\left|K(X,X)-{\mathbb{E}}K(X,X)\right|\geq
t\right)\leq\exp\left(-C_{\ref*{C_non_linear_HS}}\frac{t^{\frac{1}{L}}d^{\frac{1}{2L}}}{4L^{3}\left(\sum_{\iota=1}^{L}\gamma_{\iota}\right)^{\frac{1}{L}}}\right).$

The proof of Theorem 9 is postponed to Section 6.5.15.

Applying Theorem 9 to $K=K_{k+1:\infty}$,
$h:t\mapsto\sum_{i>\iota}^{L}\alpha_{i}t^{i}$ together with a union bound, we
can take $\delta=1/(200\sqrt{C_{\ref*{C_distortion_1}}})$ and
$\gamma=N\exp\left(-C_{\ref*{C_non_linear_HS_1}}\frac{d^{\frac{1}{2L}}}{4L^{3}\left(\sum_{i>\iota}^{L}\alpha_{i}\right)^{\frac{1}{L}}}\right)$
for an absolute constant ${C_{73}}$. We postpone the verification under
Assumption 6 of the diagonal concentration condition appeared in Assumption 5
and Assumption 2 to Section 6.5.19.

####  6.5.14 Proof of Proposition 29

We write the feature map explicitly

$\phi:{\boldsymbol{x}}\in{\mathbb{R}}^{d}\mapsto\sum_{\left|{\cal
I}\right|=0}^{L}{\sqrt{\frac{\alpha_{\left|{\cal I}\right|}}{d^{\left|{\cal
I}\right|}}}\sqrt{C_{{\cal I}}}}{P_{{\cal I}}({\boldsymbol{x}})}e_{\cal
I},\mbox{ s.t.
}K({\boldsymbol{x}},\mathbf{y})=\left\langle\phi({\boldsymbol{x}}),\phi(\mathbf{y})\right\rangle_{\ell_{2}}$
(131)

where $C_{{\cal I}}=\left|{\cal I}\right|!/\left|{\cal
I}_{1}\right|!\cdots\left|{\cal I}_{d}\right|!$, $P_{{\cal
I}}({\boldsymbol{x}})=x_{1}^{\left|{\cal I}_{1}\right|}\cdot\cdots\cdot
x_{d}^{\left|{\cal I}_{d}\right|}$ and $e_{\cal I}$ are ONB of
$\ell_{2}^{\binom{d+L}{L}}$. Notice that here we embed ${\cal H}$ into
$\ell_{2}$. The notation ${\cal I}$ is defined in Section 1.4.

Notice that $(P_{\cal I}(X))_{\left|{\cal I}\right|\leq L}$ is not an ONB of
$L_{2}(\mu)$, because they are not orthogonal in $L_{2}(\mu)$. To obtain an
ONB, we utilize the Gram-Schmidt procedure, employing the identical rationale
as in [LRZ20, Appendix A.2]:

######  Lemma 19.

Define $q_{0},q_{1},\cdots$ as the ONB of $L_{2}({\mathbb{R}},\mu_{1})$
produced by applying the Gram-Schmidt process on the basis
$\\{1,t,\cdots,t^{k},\cdots\\}$. Then we have the following properties:

  * •

$(Q_{\cal I})_{\left|{\cal I}\right|=1}^{\infty}$ is an ONB of
$L_{2}({\mathbb{R}}^{d},\mu)$ when $Q_{\cal
I}:{\boldsymbol{x}}\in{\mathbb{R}}^{d}\mapsto\prod_{j=1}^{d}q_{\left|{\cal
I}_{j}\right|}(x_{j})$ .

  * •

Let

$\psi:{\boldsymbol{x}}\in{\mathbb{R}}^{d}\mapsto\sum_{\left|{\cal
I}\right|=0}^{L}\sqrt{\frac{\alpha_{\left|{\cal I}\right|}}{d^{\left|{\cal
I}\right|}}}\sqrt{C_{\cal I}}Q_{\cal I}({\boldsymbol{x}})e_{\cal I}.$ (132)

There exists an upper triangular non-singular matrix
$\Lambda\in{\mathbb{R}}^{\binom{d+L}{L}\times\binom{d+L}{L}}$ with
$\max\\{\left\|\Lambda\right\|_{\text{op}},\,\left\|\Lambda^{-1}\right\|_{\text{op}}\\}\leq
C_{L}$, such that $\phi=\Lambda^{\top}\psi$.

The matrix $\Lambda^{\top}$ functions as the transformation matrix that
converts the orthonormal basis $(Q_{\cal I})_{\left|{\cal I}\right|\leq L}$
into a linearly independent basis $(P_{\cal I})_{\left|{\cal I}\right|\leq
L}$, which may be found in [MS23, section 4.8, section 5.5]. As a result,
$\Gamma={\mathbb{E}}\left[\phi(X)\otimes\phi(X)\right]={\mathbb{E}}\left[\left(\Lambda^{\top}\psi(X)\right)\otimes\left(\Lambda^{\top}\psi(X)\right)\right]=\Lambda^{\top}{\mathbb{E}}\left[\psi(X)\otimes\psi(X)\right]\Lambda$.
By Courant-Fisher’s max-min theorem, see for example, [Ver18, section 4.1],
together with Lemma 19, the eigenvalue of $\Gamma$ is equivalent to that of
${\mathbb{E}}\left[\psi(X)\otimes\psi(X)\right]$ up to absolute constants
depending on $L$, because
$\max\\{\left\|\Lambda\right\|_{\text{op}},\left\|\Lambda^{-1}\right\|_{\text{op}}\\}\leq
C_{L}$.

We now study the spectrum of ${\mathbb{E}}[\psi(X)\otimes\psi(X)]$, which is
up to constant, the spectrum of $\Gamma$. The spectrum of $\Gamma$ performs a
“multi-stage” pattern up to $\alpha$. More precisely, by (132), we have the
following.

  * •

When $\left|{\cal I}\right|=0$. By (132), there is a unique eigenvalue
$\alpha_{0}$, which is of constant order.

  * •

When $\left|{\cal I}\right|=1$. By (132), for every such ${\cal I}$, $C_{\cal
I}=1$, thus the first stage of $\mathrm{spec}(\Gamma)$ is a plateau of height
$1/d$ (up to $\alpha$), and of length $d$.

  * •

When $\left|{\cal I}\right|=2$. By (132), we know that $C_{\cal I}=1$ for
diagonal ${\cal I}$ and $C_{\cal I}=2$ for off-diagonal. Therefore the second
stage is of height $1/d^{2}$ (up to constants depending on $\alpha$) and of
length $d^{2}$.

  * •

Generally, if $\left|{\cal I}\right|=qd+r$ for $q\in{\mathbb{N}}$ and $0\leq
r<d$, the multi-nomial coefficient $C_{\cal I}$ has maximum $\left|{\cal
I}\right|!/\left((q!)^{d-r}\left((q+1)!\right)^{r}\right)$. When $L<d$, we
have $1\leq C_{\cal I}\leq\left|{\cal I}\right|!/2^{\left|{\cal
I}\right|}<\exp(\left|{\cal I}\right|)$. As in [LRZ20], we ignore $C_{\cal I}$
(this happens when $e^{L}<d$, which is guaranteed by Assumption 6). The
constraint mentioned above may be removed through careful computation;
however, we have chosen to avoid doing so in order to give priority to
simplicity. In fact, as $\left|{\cal I}\right|$ increases, each stage’s slope
rises rapidly (with an exponential rate), because of $C_{\cal I}$. For
instance, denoting $\left|{\cal I}\right|=l$, then the $l$-th stage of
$\mathrm{spec}(\Gamma)$ has length $d^{l}$ and drops from $l!/(2^{l}\cdot
d^{l})$ to $1/d^{l}$.

####  6.5.15 Proof of Theorem 9

In this section, we prove Theorem 9. We will introduce the notation for tensor
products and differential calculus used in the proof of Theorem 9 in Section
6.5.16 and Section 6.5.17, respectively. Subsequently, in Section 6.5.18, we
will employ these notations and lemmas to prove Theorem 9.

####  6.5.16 Tensors

In algebra, the tensor product of multiple vector spaces is used to deal with
multilinear mappings on these vector spaces. Given vectors222In this paper, we
only consider real vector spaces. spaces $U,V,W$, we write $U\otimes V$ as the
tensor product between $U$ and $V$, with the correspondence given by
$({\boldsymbol{u}},{\boldsymbol{v}})\mapsto{\boldsymbol{u}}\otimes{\boldsymbol{v}}$.
We also write $L(U;V)$ as the space of linear map from $U$ to $V$, which is
itself a vector space. The tensor product provides the following isomorphism:
$L(U;L(V;W))\cong L(U\otimes V;W)$, where “$\cong$” is algebraic isomorphism,
see [Lan02, Chapter 16, Section 2, pp.607]. Tensor product has associativity,
that is, $U\otimes V\otimes W\cong(U\otimes V)\otimes W\cong U\otimes(V\otimes
W)$, see [Yok92, Proposition 1.7, Proposition 1.8]. The following property of
tensor product is frequently utilized in the remaining part of this paper. Let
$V_{1},V_{2}$, $W_{1},W_{2}$ and $U_{1},U_{2}$ be real vector spaces, let
$F_{1},G_{1}\in L(V_{1};W_{1})$, $F_{2},G_{2}\in L(V_{2};W_{2})$, $H_{1}\in
L(W_{1};U_{1})$ and $H_{2}\in L(W_{2};U_{2})$. Then $(H_{1}\circ
F_{1})\otimes(H_{2}\circ F_{2})=(H_{1}\otimes H_{2})\circ(F_{1}\otimes
F_{2})$, see [Yok92, Proposition 1.9]. Given a tensor $T$, and some $k\geq 1$,
we write $T^{\otimes k}$ as $T\otimes\cdots\otimes T$ ($k$ times).

In statistics and computer science, it is common to select a basis and define
tensors by enumerating their elements. Given $k\in{\mathbb{N}}_{+}$ and
$d_{1},d_{2},\cdots,d_{k}\in{\mathbb{N}}_{+}$, a tensor of degree $k$,
dimension $d_{1},d_{2},\cdots,d_{k}$ is an array $T=(t_{i_{1},\cdots,i_{k}})$,
where $\\{t_{i_{1},\cdots,i_{k}}\\}^{\prime}s$ are in ${\mathbb{R}}$ (we only
consider real field in this note). If $d_{1}=d_{2}=\cdots=d_{k}$, we call $T$
as a tensor of degree $k$, dimension $d$. A degree $k$ dimension $d$ tensor
$T$ is called symmetric, if it is unchanged upon permuting the indices. The
space of symmetric degree $k$, dimension $d$ tensors, denoted as
$\mathrm{Sym}_{k}({\mathbb{R}}^{d})$. Given a tensor
$T\in\mathrm{Sym}_{k}({\mathbb{R}}^{d})$, we can always unfold $T$ into
${\mathbb{R}}^{d^{k}}$. Given two matrices $A\in{\mathbb{R}}^{m\times n}$,
$B\in{\mathbb{R}}^{p\times q}$ for some $m,n,p,q\in{\mathbb{N}}_{+}$,
$(A\otimes B)^{\top}=(A^{\top})\otimes(B^{\top})$, [Yok92, Proposition 1.9’].

Given two tensors $A=(a_{i_{1},\cdots,i_{k}})$ and
$B=(b_{i_{1},\cdots,i_{k}})$ of degree $k$ and dimension $d$, the inner
product between $A$ and $B$ is defined as:

$\displaystyle\left<A,B\right>=\sum_{i_{1},\cdots,i_{k}=1}^{d}a_{i_{1},\cdots,i_{k}}b_{i_{1},\cdots,i_{k}},$

which is equivalent to the inner product of the two vectors obtained by
unfolding $A$ and $B$ in ${\mathbb{R}}^{d^{k}}$. We let
$\left\|A\right\|_{HS}=\sqrt{\left<A,A\right>}$ as the Hilbert-Schmidt norm of
$A$.

Given a tensor $T\in\mathrm{Sym}_{k}({\mathbb{R}}^{d})$, whose entries are
random variables on ${\mathbb{R}}$, the expectation of $T$ is defined as a
tensor
${\mathbb{E}}T=({\mathbb{E}}t_{i_{1},\cdots,i_{k}})\in\mathrm{Sym}_{k}({\mathbb{R}}^{d})$.

Given $r,d\in{\mathbb{N}}_{+}$ and $A$ be a degree $r$, dimension $d$ tensor.
Let $P_{r}$ denote the set of partitions of $[r]$ into non-empty, pairwise
disjoint sets, and for each partition ${\cal J}\in P_{r}$, ${\cal
J}=\left\\{J_{1},\cdots,J_{k}\right\\}$, we define

$\left\|A\right\|_{\cal J}=\sup\left(\sum_{{\cal I}\in[d]^{r}}a_{\cal
I}\prod_{l=1}^{k}x_{{\cal I}_{J_{l}}}^{(l)}:\,\sqrt{\sum_{\left|{\cal
I}_{J_{l}}\right|\leq d}\left(x_{{\cal I}_{J_{l}}}^{(l)}\right)^{2}}\leq
1,\,1\leq l\leq k\right),$

see also [Leh11] for an alternative notation by using injective tensor
products. For example, when $r=2$,
$P_{2}=\\{\\{1,2\\},\\{\\{1\\},\\{2\\}\\}\\}$, $a_{\cal I}=a_{ij}$. For
$J_{1}=\\{1,2\\}$, we have $k=l=1$, ${\cal I}\in[d]^{2}$ and
$\sqrt{\sum_{i,j\leq d}x_{ij}^{2}}=\left\|x\right\|_{HS}$ for
$x\in{\mathbb{R}}^{d^{2}}$, thus
$\left\|A\right\|_{\left\\{1,2\right\\}}=\left\|A\right\|_{HS}$. For
$J_{1}=\\{1\\},J_{2}=\\{2\\}$, we have $k=2$ and for the sake of simplicity,
we write $x_{{\cal I}_{1}}^{(1)}$ and $x_{{\cal I}_{2}}^{(2)}$ as $x,y$ , thus
$\sqrt{\sum_{i\leq d}x_{i}^{2}},\sqrt{\sum_{j\leq d}y_{j}^{2}}\leq 1$ , and
$\left\|A\right\|_{\left\\{1\right\\},\left\\{2\right\\}}=\left\|A\right\|_{\text{op}}$.
For $r=3$, we can write $[3]=\\{1,2,3\\}$, corresponding to view
$A\in{\mathbb{R}}^{d^{3}}$ as a linear functional with norm
$\left\|A\right\|_{\\{1,2,3\\}}=\sqrt{\sum_{i,j,k}a_{i,j,k}^{2}}$; or
$\\{1,2\\},\\{3\\}$, corresponding to view $A\in{\mathbb{R}}^{d^{3}}$ as a bi-
linear functional on ${\mathbb{R}}^{d^{2}}\times{\mathbb{R}}$, with the norm
$\left\|A\right\|_{\\{1,2\\},\\{3\\}}=\sup\left(\left|\sum_{i,j,k}a_{i,j,k}x_{i,j}y_{k}\right|:\,\sum
x_{i,j}^{2}\leq 1,\,\sum y_{k}^{2}\leq 1\right)$ ($\\{1,3\\},\\{2\\}$ or
$\\{2,3\\},\\{1\\}$ are similar); or $\\{1\\},\\{2\\},\\{3\\}$, corresponding
to view $A$ as a tri-linear functional on $\left({\mathbb{R}}^{d}\right)^{3}$.
We have

$\left\|A\right\|_{\\{1\\},\\{2\\},\\{3\\}}\leq\left\|A\right\|_{\\{1,2\\},\\{3\\}},\,\left\|A\right\|_{\\{1,3\\},\\{2\\}},\,\left\|A\right\|_{\\{2,3\\},\\{1\\}}\leq\left\|A\right\|_{\\{1,2,3\\}}.$

If ${\cal K}$ is a finer partition than ${\cal J}$ (any element in ${\cal K}$
is contained in an element in ${\cal J}$), then $\left\|A\right\|_{\cal
K}\leq\left\|A\right\|_{\cal J}$, see [Leh11, Section 2.1].

####  6.5.17 Differential Calculus

Let ${\cal X},{\cal Y}$ be two normed vector spaces with norm
$\left\|\cdot\right\|_{\cal X}$ and $\left\|\cdot\right\|_{\cal Y}$,
$\Omega\subseteq{\cal X}$ be an open set, $f:\Omega\to{\cal Y}$ is Fréchet
differentiable at ${\boldsymbol{x}}\in\Omega$, if there exists a bounded
linear operator $A_{\boldsymbol{x}}\in L({\cal X},{\cal Y})$, such that

$\displaystyle\lim_{{\boldsymbol{h}}\to{\boldsymbol{0}}}\frac{\left\|f({\boldsymbol{x}}+{\boldsymbol{h}})-f({\boldsymbol{x}})-A_{\boldsymbol{x}}{\boldsymbol{h}}\right\|_{\cal
Y}}{\left\|{\boldsymbol{h}}\right\|_{\cal X}}=0,$ (133)

where the limit is in the sense of the topology generated by
$\left\|\cdot\right\|_{\cal X}$, see [AK16, Definition 14.2.1]. Denote
$\mathbf{D}f({\boldsymbol{x}})=A_{\boldsymbol{x}}$. In the case of ${\cal
X}=({\mathbb{R}}^{d},\left\|\cdot\right\|_{2})$ and ${\cal
Y}=({\mathbb{R}},\left\|\cdot\right\|_{1})$, the Fréchet derivative at
${\boldsymbol{x}}$ is simply the transpose of the gradient of $f$ at
${\boldsymbol{x}}$. If we omit ${\boldsymbol{x}}$, then
$\mathbf{D}f:{\boldsymbol{x}}\in{\cal X}\mapsto A_{\boldsymbol{x}}\in L({\cal
X},{\cal Y})$. Given $g:{\cal Z}\to\Omega\subseteq{\cal X}$, the chain rule
gives that $\mathbf{D}(f\circ
g)({\boldsymbol{z}})=\mathbf{D}f(g({\boldsymbol{z}}))\mathbf{D}g({\boldsymbol{z}})\in
L({\cal Z},{\cal Y})$. We omit the variables and write $\mathbf{D}(f\circ
g)=(\mathbf{D}f\circ g)(\mathbf{D}g)$ and
$\mathbf{D}(fg)=(\mathbf{D}f)g+f(\mathbf{D}g)$. These notations make sense
because $\mathbf{D}g:{\cal Z}\to L({\cal Z},{\cal X})$ and $\mathbf{D}f\circ
g:{\cal Z}\to L({\cal X},{\cal Y})$, hence $(\mathbf{D}f\circ
g)(\mathbf{D}g):{\cal Z}\to L({\cal Z},{\cal Y})$.

The second order Fréchet derivative is defined as the Fréchet derivative of
$\mathbf{D}f$, denoted as $\mathbf{D}^{2}f:{\cal X}\to L({\cal X},L({\cal
X},{\cal Y}))\cong L({\cal X}\otimes{\cal X},{\cal Y})$. That is to say, the
second-order Fréchet derivative is a degree 2 tensor. If ${\cal X}$ and ${\cal
Y}$ are both (finite-dimensional) Euclidean spaces, and we represent
$\mathbf{D}^{2}f$ in the standard orthogonal basis of Euclidean space, we will
obtain that $\mathbf{D}^{2}f$ is actually the Hessian, that is,
$(\mathbf{D}^{2}f)_{ij}=\frac{\partial^{2}}{\partial x_{i}\partial
x_{j}}f({\boldsymbol{x}})$. Generally, for $k\geq 1$, $\mathbf{D}^{k}f$ for
$f$ defined on ${\mathbb{R}}^{d}$ can be defined iteratively as
$\mathbf{D}^{k}f=\mathbf{D}(\mathbf{D}^{k-1}f)$, resulting in a tensor in
$\mathrm{Sym}_{k}({\mathbb{R}}^{d})$, and if we represent $\mathbf{D}^{k}f$ in
the standard ONB of ${\mathbb{R}}^{d}$, we have
$(\mathbf{D}^{k}f)_{i_{1},\cdots,i_{k}}=\frac{\partial^{k}}{\partial
x_{i_{1}}\cdots\partial x_{i_{k}}}f({\boldsymbol{x}})$.

Providing a high-order chain rule is not easy. To see this, recall that we
define $\mathbf{D}^{2}(f\circ g)=\mathbf{D}(\mathbf{D}(f\circ g))$. Applying
the product rule gives that $\mathbf{D}^{2}(f\circ
g)=\mathbf{D}(\mathbf{D}f\circ g)\mathbf{D}g+(\mathbf{D}f\circ
g)\mathbf{D}^{2}g$. However, if we use the chain rule for computing
$\mathbf{D}(\mathbf{D}f\circ g)=(\mathbf{D}^{2}f\circ g)\mathbf{D}g$, we face
the issue that $\mathbf{D}g:{\cal Z}\to L({\cal Z};{\cal X})$, however,
$\mathbf{D}^{2}f\circ g:{\cal Z}\to L({\cal X}\otimes{\cal X};{\cal Y})$. This
leads to its evaluation at ${\boldsymbol{z}}$, that is,
$((\mathbf{D}^{2}f\circ g)({\boldsymbol{z}}))(\mathbf{D}g({\boldsymbol{z}}))$
not being well-defined.

To address this issue, we adopt the tensor notations developed by [Man13],
that is,

$\displaystyle\begin{aligned} \mathbf{D}(\mathbf{D}f\circ
g)&=(\mathbf{D}^{2}f\circ g)(\mathbf{D}g\otimes I_{{\cal Z}\to L({\cal
X};{\cal X})}),\\\ \mathbf{D}((\mathbf{D}f\circ
g)(\mathbf{D}g))&=\mathbf{D}(\mathbf{D}f\circ g)(I_{{\cal Z}\to L({\cal
Z};{\cal Z})}\otimes\mathbf{D}g)+(\mathbf{D}f\circ g)(\mathbf{D}^{2}g),\\\
\mbox{ and }\mathbf{D}(f\otimes g)&=(\mathbf{D}f\otimes
g)+(f\otimes\mathbf{D}g).\end{aligned}$ (134)

Let’s verify that this notation makes sense. Recall that $\mathbf{D}^{2}f\circ
g:{\cal Z}\to L({\cal X};L({\cal X};{\cal Y}))\cong L({\cal X}\otimes{\cal
X};{\cal Y})$, and $\mathbf{D}g:{\cal Z}\to L({\cal Z};{\cal X})$. Hence,
$\mathbf{D}g\otimes I_{{\cal Z}\to L({\cal X};{\cal X})}:{\cal Z}\otimes{\cal
Z}\to L({\cal Z};{\cal X})\otimes L({\cal X};{\cal X})\cong L({\cal
Z}\otimes{\cal X};{\cal X}\otimes{\cal X})$. Therefore, the right-hand-side of
the modified chain rule satisfies, $(\mathbf{D}^{2}f\circ
g)(\mathbf{D}g\otimes I_{{\cal Z}\to L({\cal X};{\cal X})}):{\cal
Z}\otimes{\cal Z}\to L({\cal Z}\otimes{\cal X};{\cal Y})\cong L({\cal
Z};L({\cal X};{\cal Y}))$. The left-hand-side of the modified chain rule
$\mathbf{D}(\mathbf{D}f\circ g):{\cal Z}\to L({\cal Z};L({\cal X};{\cal Y}))$,
coincides with the right-hand-side formula. As a result, the modified chain
rule notation makes sense. The modified product rule follows from the same
idea.

The chain rule of higher-order Fréchet derivatives can be conveniently
represented using the tensor product language introduced in (134) as follows:

$\displaystyle\mathbf{D}^{2}(f\circ g)$
$\displaystyle=\mathbf{D}(\mathbf{D}(f\circ
g))=\mathbf{D}\left((\mathbf{D}f\circ
g)(\mathbf{D}g)\right)=\mathbf{D}(\mathbf{D}f\circ g)(I_{{\cal Z}\to L({\cal
Z};{\cal Z})}\otimes\mathbf{D}g)+(\mathbf{D}f\circ g)(\mathbf{D}^{2}g)$
$\displaystyle=(\mathbf{D}^{2}f\circ g)(\mathbf{D}g\otimes I_{{\cal Z}\to
L({\cal X};{\cal X})})(I_{{\cal Z}\to L({\cal Z};{\cal
Z})}\otimes\mathbf{D}g)+(\mathbf{D}f\circ g)(\mathbf{D}^{2}g)$
$\displaystyle=(\mathbf{D}^{2}f\circ
g)(\mathbf{D}g\otimes\mathbf{D}g)+(\mathbf{D}f\circ g)(\mathbf{D}^{2}g),.$
(135)

Since the domain and codomain of the identity map are unambiguously
understood, we henceforth omit the subscripts for the identity map.

Let $({\boldsymbol{v}}_{i})_{i=1}^{\infty}$ are an ONB of $\ell_{2}$, define
$\leq$ be a partial order on $\ell_{2}$ defined by
${\boldsymbol{x}}\leq\mathbf{y}\Leftrightarrow\left<{\boldsymbol{x}},{\boldsymbol{v}}_{i}\right>\leq\left<\mathbf{y},{\boldsymbol{v}}_{i}\right>$
for any $i\in{\mathbb{N}}_{+}$. We say ${\boldsymbol{x}}\lesssim\mathbf{y}$ if
there exists an absolute constant $C$ such that ${\boldsymbol{x}}\leq
C\mathbf{y}$. We say ${\boldsymbol{x}}\lesssim_{K}\mathbf{y}$ if the constant
$C$ depends on $K$. Let us prove the lemma below.

######  Lemma 20.

Let $d,p,q\geq 1$, $K\in{\mathbb{N}}_{+}$, $K\geq 3$. Suppose
$g:{\mathbb{R}}^{d}\to{\mathbb{R}}^{p}$ and
$f:{\mathbb{R}}^{p}\to{\mathbb{R}}^{q}$ be $C^{K}$ functions. Given any
$n,k\in[K]$ and $i_{1},\cdots,i_{k}\geq 0$, we view every tensor of the form
$(\mathbf{D}^{n}f\circ
g)(\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g)$ as orthonormal
vectors ${\boldsymbol{v}}_{(i_{1},\cdots,i_{k};n)}$ in $\ell_{2}$, that is,
given $k,l,m,n\in{\mathbb{N}}_{+}$,
$i_{1},\cdots,i_{k},i_{1}^{\prime},\cdots,i_{l}^{\prime}\geq 0$, then
$\left<{\boldsymbol{v}}_{(i_{1},\cdots,i_{k};n)},{\boldsymbol{v}}_{(i_{1}^{\prime},\cdots,i_{l}^{\prime};m)}\right>=\mathbbm{1}_{\\{(i_{1},\cdots,i_{k};n)=(i_{1}^{\prime},\cdots,i_{l}^{\prime};m)\\}}$.
In particular, if $l\neq k$ or $n\neq m$, then
$\left<{\boldsymbol{v}}_{(i_{1},\cdots,i_{k};n)},{\boldsymbol{v}}_{(i_{1}^{\prime},\cdots,i_{l}^{\prime};m)}\right>=0$.
There then exists an absolute constant ${C_{74}}$ depending only on $K$, such
that

$\displaystyle C_{\ref*{C_concentration}}^{-1}\mathbf{D}^{K}(f\circ
g)\leq(\mathbf{D}^{K}f\circ g)(\mathbf{D}g)^{\otimes
K}+\sum_{k=2}^{K-1}(\mathbf{D}^{k}f\circ
g)\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)+(\mathbf{D}f\circ
g)\mathbf{D}^{K}g.$ (136)

The overall strategy for proving Lemma 20 is based on the induction method. We
first prove the following lemma. To avoid certain pathological cases, in the
following text, we always assume that the functions appearing are sufficiently
many times Fréchet differentiable (for our purposes, this assumption always
holds).

######  Lemma 21.

Given any $k\geq 1$, for any normed vector spaces ${\cal Z},{\cal X}$ and
$g:{\cal Z}\to{\cal X}$ be $(k+1)$-times Fréchet differentiable on some open
set $\Omega\subseteq{\cal Z}$. We have

$\displaystyle\mathbf{D}\left((\mathbf{D}g)^{\otimes k}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=k+1\end{subarray}}\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes i_{k}}g.$ (137)

Moreover, given any $(i_{1},\cdots,i_{k})$ satisfying $i_{1},\cdots,i_{k}\geq
1$ and $i_{1}+\cdots+i_{k}=k+1$, we denote $(i_{1},\cdots,i_{k})+1$ as

$\displaystyle\begin{aligned}
(i_{1},\cdots,i_{k})+1:=\bigcup_{j\in[k]}(i_{1},\cdots,i_{j-1},i_{j}+1,i_{j+1},\cdots,i_{k}),\end{aligned}$
(138)

then

$\displaystyle\mathbf{D}\left(\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes
i_{k}}g\right)=\sum_{(l_{1},\cdots,l_{k})\in(i_{1},\cdots,i_{k})+1}\mathbf{D}^{\otimes
l_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes l_{k}}g.$ (139)

Proof. When $k=1$, $\mathbf{D}(\mathbf{D}g)=\mathbf{D}^{2}g$. Suppose (137)
holds for some $K\geq 1$, by (134) we have

$\displaystyle\mathbf{D}((\mathbf{D}g)^{\otimes(K+1)})$
$\displaystyle=\mathbf{D}\left((\mathbf{D}g)^{\otimes
K}\otimes\mathbf{D}g\right)=\mathbf{D}(\mathbf{D}g)^{\otimes
K}\otimes\mathbf{D}g+(\mathbf{D}g)^{\otimes K}\otimes\mathbf{D}^{2}g$
$\displaystyle=\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{K}\geq 1\\\
i_{1}+\cdots+i_{K}=K+1\end{subarray}}\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes
i_{K}}g\otimes\mathbf{D}g\right)+(\mathbf{D}g)^{\otimes
K}\otimes\mathbf{D}^{2}g$ (140)
$\displaystyle=\sum_{\begin{subarray}{c}i_{1},\cdots,i_{K+1}\geq 1\\\
i_{1}+\cdots+i_{K+1}=K+2\end{subarray}}\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes i_{K+1}}g,$

where the last equality is via the following observation: given
$l\in{\mathbb{N}}_{+}$ and $i_{1}+\cdots+i_{l}=l+1$ and
$i_{1},\cdots,i_{l}\geq 1$, by the Pigeonhole principle, there must be a
unique $n(l)\in[l]$ such that $n(l)=2$. Now let $l=K+1$, we have:

  1. 1.

the first term in (140) corresponds to the case where $n(K+1)$ belongs to
$[K]$, that is, we have: $i_{1}+\cdots+i_{K}+i_{K+1}=K+2$,
$i_{1},\cdots,i_{K},i_{K+1}\geq 1$, and $i_{K+1}=1$. Therefore, $n(K+1)$ must
necessarily appear among $[K]$, and

  2. 2.

the second term in (140) corresponds to the case where $n(K+1)=K+1$. That is,
$i_{1},\cdots,i_{K},i_{K+1}\geq 1$, $i_{1}+\cdots+i_{K}+i_{K+1}=K+2$, and
$i_{1}=\cdots=i_{K}=1$.

(137) is therefore derived.

Now we prove (139). When $k=1$, $i_{1}=2$ and $(i_{1})+1=(i_{1}+1)=(3)$.
$\mathbf{D}(\mathbf{D}^{2}g)=\mathbf{D}^{3}g$. Hence (139) is valid when
$k=1$. Suppose (139) is valid for some $K\geq 1$, then for any
$(i_{1},\cdots,i_{K},i_{K+1})$ such that $i_{1},\cdots,i_{K+1}\geq 1$ and
$i_{1}+\cdots+i_{K+1}=K+1$, by (134), we have

$\displaystyle\mathbf{D}\left(\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes
i_{K}}g\otimes\mathbf{D}^{i_{K+1}}g\right)=\mathbf{D}\left(\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes
i_{K}}g\right)\otimes\mathbf{D}^{i_{K+1}}g+\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes
i_{K}}g\otimes\mathbf{D}^{i_{K+1}+1}g$
$\displaystyle=\left(\sum_{\begin{subarray}{c}(l_{1},\cdots,l_{k})\in(i_{1},\cdots,i_{K})+1\end{subarray}}\mathbf{D}^{\otimes
l_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes
l_{K}}g\otimes\mathbf{D}^{i_{K+1}}g\right)+\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes
i_{K}}g\otimes\mathbf{D}^{i_{K+1}+1}g$
$\displaystyle=\sum_{(l_{1},\cdots,l_{K+1})\in(i_{1},\cdots,i_{K+1})+1}\mathbf{D}^{\otimes
l_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes l_{K+1}}g.$

Having proved Lemma 21, we proceed to prove Lemma 20.

##### Proof of Lemma 20.

We begin with $\mathbf{D}^{3}(f\circ g)$.

$\displaystyle\begin{aligned} \mathbf{D}^{3}(f\circ
g)&=\mathbf{D}\left((\mathbf{D}^{2}f\circ
g)(\mathbf{D}g\otimes\mathbf{D}g)\right)+\mathbf{D}\left((\mathbf{D}f\circ
g)(\mathbf{D}^{2}g)\right)\\\ &=(\mathbf{D}(\mathbf{D}^{2}f\circ
g))(I\otimes(\mathbf{D}g)^{\otimes 2})+(\mathbf{D}^{2}f\circ
g)\mathbf{D}((\mathbf{D}g)^{\otimes 2})+(\mathbf{D}(\mathbf{D}f\circ
g))(I\otimes\mathbf{D}^{2}g)+(\mathbf{D}f\circ g)(\mathbf{D}^{3}g)\\\
&=(\mathbf{D}^{3}f\circ g)(\mathbf{D}g\otimes
I)(I\otimes(\mathbf{D}g)^{\otimes 2})+(\mathbf{D}^{2}f\circ
g)(\mathbf{D}^{2}g\otimes\mathbf{D}g+\mathbf{D}g\otimes\mathbf{D}^{2}g)\\\
&+(\mathbf{D}^{2}f\circ g)(\mathbf{D}g\otimes
I)(I\otimes\mathbf{D}^{2}g)+(\mathbf{D}f\circ g)(\mathbf{D}^{3}g)\\\
&=(\mathbf{D}^{3}f\circ g)(\mathbf{D}g)^{\otimes 3}+(\mathbf{D}^{2}f\circ
g)(\mathbf{D}^{2}g\otimes\mathbf{D}g+\mathbf{D}g\otimes\mathbf{D}^{2}g+\mathbf{D}g\otimes\mathbf{D}^{2}g)+(\mathbf{D}f\circ
g)\mathbf{D}^{3}g.\end{aligned}$ (141)

All terms in (141) of the form $(\mathbf{D}^{n}f\circ
g)(\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g)$ can be
regarded as orthonormal vectors in $\ell_{2}$: $(\mathbf{D}^{3}f\circ
g)(\mathbf{D}g)^{\otimes 3}$ is viewed as ${\boldsymbol{v}}_{(1,1,1;3)}$,
$(\mathbf{D}^{2}f\circ g)(\mathbf{D}^{2}g\otimes\mathbf{D}g)$ is viewed as
${\boldsymbol{v}}_{(2,1;2)}$, $(\mathbf{D}^{2}f\circ
g)(\mathbf{D}g\otimes\mathbf{D}^{2}g)$ is viewed as
${\boldsymbol{v}}_{(1,2;2)}$, $(\mathbf{D}f\circ g)\mathbf{D}^{3}g$ is viewed
as ${\boldsymbol{v}}_{(3;1)}$. If we consider $\mathbf{D}^{3}(f\circ g)$ as a
vector in $\ell_{2}$ and expand it in this ONB, the coordinates of
$\mathbf{D}^{3}(f\circ g)$ are (we ignore terms with coordinates equal to
$0$): $(1,1,2,1)$. The coordinates of the right-hand side of (136) in this ONB
when $K=3$ are $(1,1,1,1)$. Therefore, when $K=3$ and
$C_{\ref*{C_concentration}}=2$, (136) holds.

Suppose (136) is satisfied with some $K\geq 3$. By (134) and (137) we have:

$\displaystyle\mathbf{D}\left((\mathbf{D}^{K}f\circ g)(\mathbf{D}g)^{\otimes
K}\right)$ $\displaystyle=\mathbf{D}(\mathbf{D}^{K}f\circ
g)(I\otimes(\mathbf{D}g)^{\otimes K})+(\mathbf{D}^{K}f\circ
g)\mathbf{D}(\mathbf{D}g)^{\otimes K}$ $\displaystyle=(\mathbf{D}^{K+1}f\circ
g)(\mathbf{D}g\otimes I)(I\otimes(\mathbf{D}g)^{\otimes
K})+(\mathbf{D}^{K}f\circ g)\sum_{\begin{subarray}{c}i_{1},\cdots,i_{K}\geq
1\\\ i_{1}+\cdots+i_{K}=K+1\end{subarray}}\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes i_{K}}g$
$\displaystyle=(\mathbf{D}^{K+1}f\circ
g)(\mathbf{D}g)^{\otimes(K+1)}+(\mathbf{D}^{K}f\circ
g)\sum_{\begin{subarray}{c}i_{1},\cdots,i_{K}\geq 1\\\
i_{1}+\cdots+i_{K}=K+1\end{subarray}}\mathbf{D}^{\otimes
i_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes i_{K}}g,$ (142)

and

$\displaystyle\mathbf{D}\left((\mathbf{D}f\circ g)(\mathbf{D}^{K}g)\right)$
$\displaystyle=\mathbf{D}(\mathbf{D}f\circ
g)(I\otimes\mathbf{D}^{K}g)+(\mathbf{D}f\circ g)\mathbf{D}^{K+1}g$
$\displaystyle=(\mathbf{D}^{2}f\circ g)(\mathbf{D}g\otimes
I)(I\otimes\mathbf{D}^{K}g)+(\mathbf{D}f\circ g)\mathbf{D}^{K+1}g$
$\displaystyle=(\mathbf{D}^{2}f\circ
g)(\mathbf{D}g\otimes\mathbf{D}^{K}g)+(\mathbf{D}f\circ g)\mathbf{D}^{K+1}g.$
(143)

We are left with the middle term in (136). For any $2\leq k\leq K-1$, by
(134), we have:

$\displaystyle\mathbf{D}\left((\mathbf{D}^{k}f\circ
g)\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)\right)$
$\displaystyle=\mathbf{D}(\mathbf{D}^{k}f\circ
g)\left(I\otimes\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)\right)$
(144) $\displaystyle+(\mathbf{D}^{k}f\circ
g)\mathbf{D}\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right).$
(145)

We now separately compute (144) and (145). By (134) we have:

$\displaystyle\eqref{eq:proof_chain_rule_higer_3}$
$\displaystyle=(\mathbf{D}^{k+1}f\circ g)(\mathbf{D}g\otimes
I)\left(I\otimes\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)\right)$
$\displaystyle=(\mathbf{D}^{k+1}f\circ
g)\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}g\otimes\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)$
$\displaystyle=(\mathbf{D}^{k+1}f\circ
g)\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k+1}\geq 1\\\
i_{1}+\cdots+i_{k+1}=K+1\\\
i_{1}=1\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k+1}}g\right).$
(146)

By (139) we have:

$\displaystyle\eqref{eq:proof_chain_rule_higer_4}$
$\displaystyle=(\mathbf{D}^{k}f\circ
g)\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}\left(\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)$
$\displaystyle=(\mathbf{D}^{k}f\circ
g)\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\sum_{(l_{1},\cdots,l_{k})\in(i_{1},\cdots,i_{k})+1}\mathbf{D}^{\otimes
l_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes l_{k}}g.$ (147)

By the definition of $(i_{1},\cdots,i_{k})+1$, see (138),
$l_{1}+\cdots+l_{k}=i_{1}+\cdots+i_{k}+1=K+1$. This implies that every term
$\mathbf{D}^{\otimes l_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes l_{k}}g$
appeared in (147) is contained in one term of the following sum

$\displaystyle\sum_{\begin{subarray}{c}i_{1}^{\prime}\cdots,i_{k}^{\prime}\geq
1\\\
i_{1}^{\prime}+\cdots+i_{k}^{\prime}=K+1\end{subarray}}\mathbf{D}^{i_{1}^{\prime}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}^{\prime}}g.$
(148)

We therefore only need to compute the repetition counts. Given any
$i_{1}^{\prime},\cdots,i_{k}^{\prime}\geq 1$ such that
$i_{1}^{\prime}+\cdots+i_{k}^{\prime}=K+1$, then there are
$\left|\left\\{j\in[k]:i_{j}^{\prime}\geq 2\right\\}\right|$ choices of
$(i_{1},\cdots,i_{k})$ in (147) that satisfy
$l_{1}=i_{1}^{\prime},\cdots,l_{k}=i_{k}^{\prime}$. For example, with $K=7$
and $k=4$, consider a term
$(i_{1}^{\prime},i_{2}^{\prime},i_{3}^{\prime},i_{4}^{\prime})=(3,1,3,1)$ from
(148) (this term is in (148) because $3+1+3+1=K+1$). Then, only
$(i_{1},i_{2},i_{3},i_{4})=(2,1,3,1)$ and
$(i_{1},i_{2},i_{3},i_{4})=(3,1,2,1)$ from
$\eqref{eq:proof_chain_rule_higer_5}$ may be transformed into $(3,1,3,1)$. In
other words, given any $i_{1}^{\prime},\cdots,i_{k}^{\prime}\geq 1$ such that
$i_{1}^{\prime}+\cdots+i_{k}^{\prime}=K+1$, if we compute the multiplicity,
then
$(\mathbf{D}^{i_{1}^{\prime}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}^{\prime}}g)$
appears $\left|\\{j\in[k]:i_{j}^{\prime}\geq 2\\}\right|$ times in the
summation of (147). We have $\left|\\{j\in[k]:i_{j}^{\prime}\geq
2\\}\right|\leq k<K$ uniformly over all
$i_{1}^{\prime},\cdots,i_{k}^{\prime}\geq 1$,
$i_{1}^{\prime}+\cdots+i_{k}^{\prime}=K+1$ and $k<K$.

Therefore, if we view each $(\mathbf{D}^{k}f\circ g)(\mathbf{D}^{\otimes
l_{1}}g\otimes\cdots\otimes\mathbf{D}^{\otimes l_{k}}g)$ in (147) as a vector
${\boldsymbol{v}}_{(l_{1},\cdots,l_{k};k)}$ in $\ell^{2}$, and define a
partial order on $\ell^{2}$ as ${\boldsymbol{x}}\leq\mathbf{y}$ if $x_{i}\leq
y_{i}$ for any $i\in\mathbb{N}_{+}$, then

$\displaystyle\eqref{eq:proof_chain_rule_higer_5}\leq K(\mathbf{D}^{k}f\circ
g)\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K+1\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g.$
(149)

Combining (142), (6.5.17), (144), (145), (146) and (149) indicates

$\displaystyle\mathbf{D}^{K+1}(f\circ g)\lesssim_{K}(\mathbf{D}^{K+1}f\circ
g)(\mathbf{D}g)^{\otimes{K+1}}+\sum_{k=2}^{K}(\mathbf{D}^{k}f\circ
g)\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq 1\\\
i_{1}+\cdots+i_{k}=K+1\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)+(\mathbf{D}f\circ
g)\mathbf{D}^{K+1}g.$

Lemma 20 follows by induction.

####  6.5.18 Continue: Proof of Theorem 9

The proof of Theorem 9 relies on the following theorem, taken from [AW15].

######  Theorem 10.

Let $X=(x_{j})_{j=1}^{d}$ be a random vector with independent coordinates,
such that for all $j\in[d]$ we have $\left\|x_{j}\right\|_{\psi_{2}}\leq L$
for some $L>0$. Then for every polynomial $g:{\mathbb{R}}^{d}\to{\mathbb{R}}$
of degree $D$ and every $q\geq 2$,

$\left\|g(X)-{\mathbb{E}}g(X)\right\|_{L_{q}}\leq
C_{D}\sum_{r=1}^{D}\left\|x_{1}\right\|_{\psi_{2}}^{r}\sum_{{\cal J}\in
P_{r}}q^{\left|J\right|/2}\left\|{\mathbb{E}}\mathbf{D}^{r}g(X)\right\|_{\cal
J}.$

As a consequence, for any $t>0$,

${\mathbb{P}}\left(\left|g(X)-{\mathbb{E}}g(X)\right|\geq t\right)\leq
2\exp\left(-\frac{1}{C_{D}}\eta_{g}(t)\right),$

where $C_{D}$ is an absolute constant depending on $D$ and

$\eta_{g}(t)=\min\left(\min\left(\left(\frac{t}{\left\|x_{1}\right\|_{\psi_{2}}^{r}\left\|{\mathbb{E}}\mathbf{D}^{r}g(X)\right\|_{\cal
J}}\right)^{2/\left|{\cal J}\right|}:\,{\cal J}\in P_{r}\right):\,1\leq r\leq
D\right).$

Due to Theorem 10, we only need to apply Theorem 10 to
$g(\cdot)=K(\cdot,\cdot)$, which is a $2L$-degree polynomial. Consequently, we
only need to estimate $\eta_{g}(t)$ from below. Given that ${\cal J}$ is a
subset of the set $[r]$, we will employ the straightforward upper bound
$\left\|{\mathbb{E}}\mathbf{D}^{r}g(X)\right\|_{\cal
J}\leq\left\|{\mathbb{E}}\mathbf{D}^{r}g(X)\right\|_{HS}$ uniformly for all
${\cal J}$ belonging to the set $P_{r}$ and for all values of $r\in[2L]$. For
any $r\in[2L]$, we have:

$\displaystyle\max\left(\left\|{\mathbb{E}}\mathbf{D}^{r}K(X,X)\right\|_{{\cal
J}}:\,{\cal J}\in
P_{r}\right)\leq\left\|{\mathbb{E}}\mathbf{D}^{r}K(X,X)\right\|_{HS}\leq\sum_{\iota=1}^{L}\left\|{\mathbb{E}}\mathbf{D}^{r}\frac{\gamma_{\iota}}{d^{\iota}}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}.$
(150)

Given any $r\in[2L]$, it suffices to bound
$\left\|{\mathbb{E}}\mathbf{D}^{r}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}$
from above for any $\iota\in[L]$.

##### Warm up: the cases for $r=1$ and $r=2$.

We first deal with the cases where $r=1$ and $r=2$, that is, we bound
$\left\|{\mathbb{E}}\mathbf{D}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}$
and
$\left\|{\mathbb{E}}\mathbf{D}^{2}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}$
from above.

  1. 1.

$\left\|{\mathbb{E}}\mathbf{D}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}$.
For any $j\in[d]$, we have

$\displaystyle({\mathbb{E}}\mathbf{D}(\left\|X\right\|_{2}^{2})^{\iota})_{j}$
$\displaystyle=2\iota{\mathbb{E}}(\left\|X\right\|_{2}^{2})^{\iota-1}x_{j}=2\iota{\mathbb{E}}\left[\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-1\\\
\forall i\in[d],n_{i}\geq
0\end{subarray}}\frac{(\iota-1)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}x_{1}^{2n_{1}}\cdot\cdots\cdot
x_{j-1}^{2n_{j-1}}x_{j}^{2n_{j}+1}x_{j+1}^{2n_{j+1}}\cdot\cdots\cdot
x_{d}^{2n_{d}}\right].$

As we have assumed that $d>\iota$, given any $n_{1}+\cdots+n_{d}=\iota-1$ and
$n_{1},\cdots,n_{d}\geq 0$, there exists $i^{*}\in[d]$ such that
$n_{i^{*}}=0$. If $j=i^{*}$, by the independence of the coordinates and the
mean zero assumption,
$({\mathbb{E}}\mathbf{D}(\left\|X\right\|_{2}^{2})^{\iota})_{j}=0$. Given the
$j$-th component of this first-order Fréchet derivative, in the summation
above, only the terms corresponding to $n_{j}\geq 1$ contributes. By [Juk11,
Proposition 1.5] we have

$\displaystyle\frac{1}{2\iota}\left({\mathbb{E}}\mathbf{D}(\left\|X\right\|_{2}^{2})^{\iota}\right)_{j}={\mathbb{E}}\left[\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-1\\\
0\leq n_{1},\cdots,n_{j-1},n_{j+1},\cdots,n_{d}\leq\iota-1\\\ n_{j}\geq
1\end{subarray}}^{d}\frac{(\iota-1)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}x_{1}^{2n_{1}}\cdot\cdots\cdot x_{d}^{2n_{d}}x_{j}\right]$
$\displaystyle=\sum_{b=1}^{\iota-1}\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{j-1}+n_{j+1}+\cdots+n_{d}=\iota-b-1\\\
0\leq
n_{1},\cdots,n_{j-1},n_{j+1},\cdots,n_{d}\leq\iota-1\end{subarray}}\frac{(\iota-1)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}{\mathbb{E}}[x_{1}^{2n_{1}}]\cdot\cdots\cdot{\mathbb{E}}[x_{{j-1}}^{2n_{j-1}}]\cdot{\mathbb{E}}[x_{j}^{2b+1}]\cdot{\mathbb{E}}[x_{{j+1}}^{2n_{j+1}}]\cdot\cdots\cdot{\mathbb{E}}[x_{d}^{2n_{d}}]$
$\displaystyle\leq(\iota-1)!(2(\iota-2))^{\iota-\frac{3}{2}}\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-1}\sum_{b=1}^{\iota-1}\binom{d-1+\iota-b-2}{\iota-b-1}<(\iota-1)!\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-1}(2(\iota-2))^{\iota-\frac{3}{2}}\sum_{b=1}^{\iota-1}\binom{2d}{\iota-b-1}$
$\displaystyle<(\iota-1)!(2(\iota-2))^{\iota-\frac{3}{2}}\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-1}\left(\frac{2ed}{\iota-1}\right)^{\iota-1}.$

We conclude that

$\displaystyle\frac{\left\|\gamma_{\iota}{\mathbb{E}}\mathbf{D}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}^{2}}{d^{2\iota}}$
$\displaystyle<4\iota^{2}\gamma_{\iota}^{2}((\iota-1)!)^{2}(2(\iota-2))^{2\iota-3}\left\|x_{1}\right\|_{\psi_{2}}^{4\iota-2}d^{2(1-\iota)}\left(\frac{2ed}{\iota-1}\right)^{2(\iota-1)}$
$\displaystyle=\frac{4\iota^{2}\gamma_{\iota}^{2}((\iota-1)!)^{2}(2(\iota-2))^{2\iota-3}\left\|x_{1}\right\|_{\psi_{2}}^{4\iota-2}(2e)^{2(\iota-1)}}{(\iota-1)^{2(\iota-1)}d}$
$\displaystyle\sim\frac{4\iota^{2}\gamma_{\iota}^{2}(2(\iota-2))^{2\iota-3}\left\|x_{1}\right\|_{\psi_{2}}^{4\iota-2}}{d}.$
(151)

  2. 2.

$\left\|{\mathbb{E}}\mathbf{D}^{2}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}$.
By (135), we know that
${\mathbb{E}}\mathbf{D}^{2}(\left\|X\right\|_{2}^{2})^{\iota}=\iota(\iota-1)(\left\|X\right\|_{2}^{2})^{\iota-2}((X^{\top})\otimes(X^{\top}))+2\iota(\left\|X\right\|_{2}^{2})^{\iota-1}I_{d}$.
Take the $\left\|\cdot\right\|_{HS}$ and by triangular inequality we obtain
that

$\displaystyle\left\|{\mathbb{E}}\mathbf{D}^{2}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}$
$\displaystyle\leq\iota(\iota-1)\left\|{\mathbb{E}}\left[(\left\|X\right\|_{2}^{2})^{\iota-2}((X^{\top})\otimes(X^{\top}))\right]\right\|_{HS}+2\iota\sqrt{d}{\mathbb{E}}(\left\|X\right\|_{2}^{2})^{\iota-1}$
$\displaystyle=\iota(\iota-1)\left\|{\mathbb{E}}\left[(\left\|X\right\|_{2}^{2})^{\iota-2}(X\otimes
X)\right]\right\|_{HS}+2\iota\sqrt{d}{\mathbb{E}}(\left\|X\right\|_{2}^{2})^{\iota-1}.$

We have:
$\sqrt{d}{\mathbb{E}}(\left\|X\right\|_{2}^{2})^{\iota-1}\lesssim(2(\iota-1))^{\iota-1}\left\|x_{1}\right\|_{\psi_{2}}^{2(\iota-1)}d^{\iota-1/2}$.
For any $j_{1},j_{2}\in[d]$, we discuss the following two cases separately:

    1. (a)

$j_{1}\neq j_{2}$. We have:

$\displaystyle\left({\mathbb{E}}\left[(\left\|X\right\|_{2}^{2})^{\iota-2}(X\otimes
X)\right]\right)_{j_{1},j_{2}}={\mathbb{E}}\left[x_{j_{1}}x_{j_{2}}\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-2\\\
\forall i\in[d],n_{i}\geq
0\end{subarray}}\frac{(\iota-2)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}x_{1}^{2n_{1}}\cdot\cdots\cdot x_{d}^{2n_{d}}\right].$ (152)

Repeat the argument in case [1], we obtain that

$\displaystyle\eqref{eq:proof_K=2_1}$
$\displaystyle=\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-2\\\ \forall
i\in[d],n_{i}\geq 0\\\ n_{j_{1}}n_{j_{2}}\geq
1\end{subarray}}\frac{(\iota-2)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}\prod_{\begin{subarray}{c}\alpha\in[d]\\\ \alpha\neq
j_{1},j_{2}\end{subarray}}{\mathbb{E}}[x_{\alpha}^{2n_{\alpha}}]{\mathbb{E}}[x_{j_{1}}^{2n_{j_{1}}+1}]{\mathbb{E}}[x_{j_{2}}^{2n_{j_{2}}+1}]$
$\displaystyle\lesssim(\iota-2)!(2\iota-1)^{\iota-1}\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-2}\left(\frac{2ed}{\iota-2}\right)^{\iota-2}.$

Therefore,

$\displaystyle\sum_{\begin{subarray}{c}j_{1},j_{2}\in[d]\\\ j_{1}\neq
j_{2}\end{subarray}}\left({\mathbb{E}}\left[(\left\|X\right\|_{2}^{2})^{\iota-2}(X\otimes
X)\right]\right)_{j_{1},j_{2}}^{2}\lesssim(2\iota-1)^{2(\iota-1)}\left\|x_{1}\right\|_{\psi_{2}}^{4\iota-4}d^{2\iota-2}.$

    2. (b)

$j_{1}=j_{2}$. In this scenario, we cannot employ the method of $j_{1}\neq
j_{2}$ to obtain sparsity in this second-order gradient tensor. Fortunately,
in this case, the Hilbert-Schmidt norm of this second-order tensor only
possesses one “degree of freedom”:

$\displaystyle\sum_{j_{1}=1}^{d}\left({\mathbb{E}}\left[(\left\|X\right\|_{2}^{2})^{\iota-2}(X\otimes
X)\right]\right)_{j_{1},j_{1}}^{2}\lesssim\sum_{j_{1}=1}^{d}\left((2\iota-1)^{\iota-1}\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-2}d^{\iota-2}\right)^{2}=(2\iota-1)^{2(\iota-1)}\left\|x_{1}\right\|_{\psi_{2}}^{4\iota-4}d^{2\iota-3}.$

In summary,

$\displaystyle\frac{\gamma_{\iota}^{2}\left\|{\mathbb{E}}\mathbf{D}^{2}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}^{2}}{d^{2\iota}}$
$\displaystyle\lesssim\gamma_{\iota}^{2}(2\iota-1)^{2(\iota-1)}\left\|x_{1}\right\|_{\psi_{2}}^{4\iota-4}d^{-2}+\gamma_{\iota}^{2}(2\iota-1)^{2(\iota-1)}\left\|x_{1}\right\|_{\psi_{2}}^{4\iota-4}d^{-3}$
$\displaystyle+\gamma_{\iota}^{2}(2(\iota-1))^{2(\iota-1)}\left\|x_{1}\right\|_{\psi_{2}}^{4(\iota-1)}d^{-1}\sim\frac{\gamma_{\iota}^{2}}{d}(2\iota-1)^{2(\iota-1)}\left\|x_{1}\right\|_{\psi_{2}}^{4\iota-4}.$
(153)

Before addressing the case of $r\geq 3$, let us first review the proof for
$r=2$, as the main proof strategy for the case of $r\geq 3$ will be utilized
from the case of $r=2$. The computation of
$\mathbb{E}\mathbf{D}^{2}(\|X\|_{2}^{2})^{\iota}$ can be broadly divided into
two parts: corresponding to the first and last terms in equation (136). For
the computation of the first term, we divide it into two cases: in the off-
diagonal case, we exploit the independence of coordinates of $X$ and its mean-
zero property to induce sparsity; in the diagonal case, since there are fewer
entries (referred to as ”degrees of freedom”) in the diagonal of the gradient
tensor, we compute it directly. Next, in the case of $r\geq 3$, we will
continue using this approach. The difference lies in the fact that for $r\geq
3$, we also need to consider the intermediate term in equation (136).

##### The case for $3\leq r\leq 2\iota$.

We temporarily substitute $r$ with $K$ for ease of use with Lemma 20.

For any $\iota\geq 1$, let
$g:{\boldsymbol{z}}\in{\mathbb{R}}^{d}\mapsto\left\|{\boldsymbol{z}}\right\|_{2}^{2}\in{\mathbb{R}}$
and $f:t\in{\mathbb{R}}\mapsto t^{\iota}\in{\mathbb{R}}$. Then $f\circ
g:{\boldsymbol{z}}\in{\mathbb{R}}^{d}\mapsto\left\|{\boldsymbol{z}}\right\|_{2}^{2\iota}$.
Moreover, $\mathbf{D}g({\boldsymbol{z}})=2{\boldsymbol{z}}^{\top}$,
$\mathbf{D}^{2}g({\boldsymbol{z}})=2I_{d}$ and
$\mathbf{D}^{3}g({\boldsymbol{z}})={\boldsymbol{0}}$, the zero tensor of
degree $3$, dimension $d$. We also have that for any $k\in[\iota]$,
$(\mathbf{D}^{k}f\circ
g)({\boldsymbol{z}})=((\iota!)/(\iota-k)!)\left\|{\boldsymbol{z}}\right\|_{2}^{2\iota-2k}$
and for $k>\iota$, $(\mathbf{D}^{k}f\circ
g)({\boldsymbol{z}})={\boldsymbol{0}}$. Let ${\boldsymbol{z}}=X$ introduced in
Theorem 9.

By Lemma 20, take expectation and Hilbert-Schmidt norm, and by triangular
inequality, we obtain that there exists an absolute constant ${C_{75}}$
depending only on $K$ such that

$\displaystyle\begin{aligned}
\left\|{\mathbb{E}}\mathbf{D}^{K}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}&\leq
C_{\ref*{C_Concentration_2}}\mathbbm{1}_{\\{K\leq\iota\\}}\left\|{\mathbb{E}}\left[(\left\|X\right\|_{2}^{2})^{\iota-K}(X^{\top})^{\otimes
K}\right]\right\|_{HS}+C_{\ref*{C_Concentration_2}}\left\|{\mathbb{E}}\left[(\left\|X\right\|_{2}^{2})^{\iota-1}\mathbf{D}^{K}\left\|X\right\|_{2}^{2}\right]\right\|_{HS}\\\
&+C_{\ref*{C_Concentration_2}}\left\|\sum_{k=2}^{K-1\wedge\iota}{\mathbb{E}}\left[(\left\|X\right\|_{2}^{2})^{\iota-k}\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\geq
1\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)(X)\right]\right\|_{HS}.\end{aligned}$

By triangular inequality again, we have

$\displaystyle\left\|{\mathbb{E}}\mathbf{D}^{K}\left\|X\right\|_{2}^{2\iota}\right\|_{HS}\lesssim_{K}\mathbbm{1}_{\\{K\leq\iota\\}}\left\|{\mathbb{E}}\left\|X\right\|_{2}^{2\iota-2K}(X^{\top})^{\otimes
K}\right\|_{HS}+\sum_{k=2}^{K-1\wedge\iota}\left\|{\mathbb{E}}\left\|X\right\|_{2}^{2\iota-2k}\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\in\\{1,2\\}\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)\right\|_{HS}.$
(154)

We first deal with the last term in (154).

##### For any $2\leq k\leq K-1\wedge\iota$, compute
$\left\|{\mathbb{E}}\left\|X\right\|_{2}^{2\iota-2k}\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\in\\{1,2\\}\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)\right\|_{HS}$.

Given $i_{1},\cdots,i_{k}\in\\{1,2\\}$ such that $i_{1}+\cdots+i_{k}=K$, we
can separate $[K]$ into $k$ groups, that is, $[K]=\sqcup_{a=1}^{k}J_{a}$,
where $J_{a}$ is of the form $J_{a}=\\{j,j+1\\}$ or $J_{a}=\\{j\\}$ for
$j\in[K]$ according to $i_{a}$ for $a\in[k]$, that is, we have
$i_{a}=\left|J_{a}\right|$ equals either $1$ or $2$. Denote ${\cal
J}=\cup_{a=1}^{k}\\{J_{a}:\,\left|J_{a}\right|=2\\}$, and ${\cal
J}^{c}=\cup_{a=1}^{k}\\{J_{a}:\,\left|J_{a}\right|=1\\}$. As ${\cal
J}\sqcup{\cal J}^{c}=[K]$, there exists a surjective
$\pi:l\in[K]\mapsto\pi(l)\in[k]$ such that $l\in J_{\pi(l)}$. Given any
$\alpha_{1},\cdots,\alpha_{K}$, denote ${\cal
I}=\cup_{j=1}^{K-1}\\{\alpha_{j},\alpha_{j+1}:\,\pi(j)=\pi(j+1)\\}$, and
${\cal I}^{*}=\cup_{j=1}^{K}\\{\alpha_{j}:\,\left|J_{\pi(j)}\right|=1\\}$. We
have ${\cal I}\sqcup{\cal I}^{*}=\\{\alpha_{1},\cdots,\alpha_{K}\\}$. We have
$\left|{\cal
I}^{*}\right|=\sum_{a=1}^{k}\mathbbm{1}_{\\{\left|J_{a}\right|=1\\}}=\left|{\cal
J}^{c}\right|$.

Let $\alpha_{1},\cdots,\alpha_{K}\in[d]$. For $a^{*}\in[k]$ such that
$i_{a^{*}}=2$, we have $\mathbf{D}^{i_{a^{*}}}g(X)=\mathbf{D}^{2}g(X)=2I_{d}$,
and for $a^{*}\in[k]$ such that $i_{a^{*}}=1$, we have
$\mathbf{D}^{i_{a^{*}}}g(X)=2X^{\top}$. We therefore have: for any $j\in[K]$,
if $\left|J_{\pi(j)}\right|=2$, then there exists an $j^{\prime}=j\pm 1$ such
that $\pi(j^{\prime})=\pi(j)$ and
$(\mathbf{D}^{\left|J_{\pi(j)}\right|}g(X))_{\alpha_{j},\alpha_{j^{\prime}}}=\mathbbm{1}_{\\{\alpha_{j}=\alpha_{j^{\prime}}\\}}$;
if $\left|J_{\pi(j)}\right|=1$, then
$((\mathbf{D}^{\left|J_{\pi(j)}\right|})g(X)^{\top})_{\alpha_{j}}=x_{\alpha_{j}}$.
Therefore,

$\displaystyle\left(\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)_{\alpha_{1},\cdots,\alpha_{K}}^{\top}=\prod_{\begin{subarray}{c}j\in[K]\\\
\left|J_{\pi(j)}\right|=1\end{subarray}}x_{\alpha_{j}}\prod_{\begin{subarray}{c}j\in[K]\\\
\left|J_{\pi(j)}\right|=2\end{subarray}}\mathbbm{1}_{\\{\alpha_{j}=\alpha_{j^{\prime}}\\}}.$

Depending on the relation between $2k$ and $K$, there are three regimes in
general:

  1. 1.

When $2k<K$, it is impossible to have $i_{1}+\cdots+i_{k}=K$ while
$i_{1},\cdots,i_{k}\in\\{1,2\\}$.

  2. 2.

When $2k=K$, $\left|{\cal J}^{c}\right|=0$, and $\left|{\cal J}\right|=K/2$.

In this case,

$\displaystyle{\mathbb{E}}\left[\left\|X\right\|_{2}^{2\iota-2k}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right]=2^{k}{\mathbb{E}}[\left\|X\right\|_{2}^{2\iota-2k}](I_{d})^{\otimes
k}.$

Therefore,

$\displaystyle\left\|{\mathbb{E}}\left[\left\|X\right\|_{2}^{2\iota-2k}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right]\right\|_{HS}^{2}=2^{2k}\left({\mathbb{E}}\left\|X\right\|_{2}^{2\iota-2k}\right)^{2}d^{k}\lesssim
2^{2k}\left\|x_{1}\right\|_{\psi_{2}}^{4(\iota-k)}(2(\iota-k))^{\iota-k}d^{2\iota-k}.$
(155)

  3. 3.

When $2k>K$, $\left|{\cal J}^{c}\right|=2k-K\geq 1$, and $\left|{\cal
J}\right|=K-k$. Recall that

$\displaystyle(\left\|X\right\|_{2}^{2})^{\iota-k}=\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-k\\\
\forall i\in[d],n_{i}\geq
0\end{subarray}}\frac{(\iota-k)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}x_{1}^{2n_{1}}\cdot\cdots\cdot x_{d}^{2n_{d}}.$

As we have assumed that $d>\iota$, there exists $i^{*}\in[d]$ such that
$n_{i^{*}}=0$. Given $(\alpha_{j})_{j=1}^{K}\in[d]^{K}$, if there exists
$j^{*}\in[K]$ such that $\alpha_{j^{*}}=i^{*}$, and
$\left|J_{\pi(j^{*})}\right|=1$, then
$({\mathbb{E}}[(\left\|X\right\|_{2}^{2})^{\iota-k}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g])_{\alpha_{1},\cdots,\alpha_{K}}=0$.
Therefore,

$\displaystyle\left({\mathbb{E}}[(\left\|X\right\|_{2}^{2})^{\iota-k}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g]\right)_{\alpha_{1},\cdots,\alpha_{K}}$
$\displaystyle={\mathbb{E}}\left[\prod_{\begin{subarray}{c}j\in[K]\\\
\left|I_{\pi(j)}\right|=1\end{subarray}}x_{\alpha_{j}}\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-k\\\
\forall i\in[d],n_{i}\geq
0\end{subarray}}\frac{(\iota-k)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}x_{1}^{2n_{1}}\cdot\cdots\cdot
x_{d}^{2n_{d}}\prod_{\begin{subarray}{c}j\in[K]\\\
\left|I_{\pi(j)}\right|=2\end{subarray}}\mathbbm{1}_{\\{\alpha_{j}=\alpha_{j^{\prime}}\\}}\right]$
$\displaystyle=\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-k\\\ \forall
i\in[d],n_{i}\geq 0\end{subarray}}\frac{(\iota-k)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}\prod_{i^{*}\in{\cal
I}^{*}}{\mathbb{E}}\left[x_{i^{*}}^{2n_{i^{*}}+1}\right]\prod_{i\notin{\cal
I}^{*}}{\mathbb{E}}\left[x_{i}^{2n_{i}}\right]\prod_{(i_{1},i_{1}+1)\in{\cal
I}}\mathbbm{1}_{\\{i_{1}=i_{1}+1\\}}.$ (156)

To have (156) not equals to $0$, we necessarily need for any $i^{*}\in{\cal
I}^{*}$, $n_{i^{*}}\geq 1$. Therefore,

$\displaystyle\eqref{eq:proof_middle_1}$
$\displaystyle\leq\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-k\\\
\forall i\in[d],n_{i}\geq 0\\\ \forall i^{*}\in{\cal I}^{*},n_{i^{*}}\geq
1\end{subarray}}\frac{(\iota-k)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}\prod_{i^{*}\in{\cal
I}^{*}}{\mathbb{E}}\left[x_{i^{*}}^{2n_{i^{*}}+1}\right]\prod_{i\notin{\cal
I}^{*}}{\mathbb{E}}\left[x_{i}^{2n_{i}}\right]$
$\displaystyle\lesssim(2(\iota-k)+1)^{\iota+\frac{k}{2}}\left\|x_{1}\right\|_{\psi_{2}}^{2(\iota-k)+\left|{\cal
I}^{*}\right|}\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-k\\\ \forall
i\in[d],n_{i}\geq 0\\\ \forall i^{*}\in{\cal I}^{*},n_{i^{*}}\geq
1\end{subarray}}\frac{(\iota-k)!}{n_{1}!\cdot\cdots\cdot n_{d}!}$
$\displaystyle\leq(2(\iota-k)+1)^{\iota+\frac{k}{2}}\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-k}(\iota-k)!\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-k\\\
\forall i\in[d],n_{i}\geq 0\\\ \forall i^{*}\in{\cal I}^{*},n_{i^{*}}\geq
1\end{subarray}}1=\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-k}(\iota-k)!\binom{d+(\iota-k)-1-\left|{\cal
I}^{*}\right|}{\iota-k-\left|{\cal I}^{*}\right|}$
$\displaystyle\leq(2(\iota-k)+1)^{\iota+\frac{k}{2}}\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-k}(\iota-k)!\left(\frac{2ed}{\iota-k-1}\right)^{\iota-k-1}.$

Therefore,

$\displaystyle\gamma_{\iota}^{2}d^{-2\iota}\left\|{\mathbb{E}}(\left\|X\right\|_{2}^{2})^{\iota-k}\left(\sum_{\begin{subarray}{c}i_{1},\cdots,i_{k}\in\\{1,2\\}\\\
i_{1}+\cdots+i_{k}=K\end{subarray}}\mathbf{D}^{i_{1}}g\otimes\cdots\otimes\mathbf{D}^{i_{k}}g\right)\right\|_{HS}^{2}$
$\displaystyle<\gamma_{\iota}^{2}(2(\iota-k)+1)^{2\iota+k}d^{-2\iota}d^{k}\left\|x_{1}\right\|_{\psi_{2}}^{2(2\iota-k)}((\iota-k)!)^{2}\left(\frac{2e}{\iota-k-1}\right)^{2(\iota-k-1)}d^{2(\iota-k-1)}$
$\displaystyle=\gamma_{\iota}^{2}(2(\iota-k)+1)^{2\iota+k}\left\|x_{1}\right\|_{\psi_{2}}^{2(2\iota-k)}((\iota-k)!)^{2}\left(\frac{2e}{\iota-k-1}\right)^{2(\iota-k-1)}d^{-k-2}$
$\displaystyle\sim\gamma_{\iota}^{2}\left(2(\iota-k)+1\right)^{2\iota+k}\left\|x_{1}\right\|_{\psi_{2}}^{2(2\iota-k)}d^{-k-2}.$
(157)

We then deal with the first term in (154).

##### The case for $\iota=K$: $\left\|{\mathbb{E}}(X^{\top})^{\otimes
K}\right\|_{HS}.$

Given any ${\boldsymbol{\alpha}}:=(\alpha_{1},\cdots,\alpha_{K})\in[d]^{K}$,
we construct a graph $G({\boldsymbol{\alpha}})$ with vertex set $[K]$. Let
$\\{i\\}$ is connected with $\\{j\\}$, if $\alpha_{i}=\alpha_{j}$. To have
$({\mathbb{E}}(X^{\top})^{\otimes K})_{{\boldsymbol{\alpha}}}\neq 0$, we
necessarily need $G({\boldsymbol{\alpha}})$ has no isolated vertex. Let
$E({\boldsymbol{\alpha}})$ as the set of edges of $G({\boldsymbol{\alpha}})$,
then $\left|E({\boldsymbol{\alpha}})\right|\leq\lceil K/2\rceil$. For each
${\boldsymbol{\alpha}}$ such that
$\left|E({\boldsymbol{\alpha}})\right|\leq\lceil K/2\rceil$, we can bound
$({\mathbb{E}}(X^{\top})^{\otimes K})_{{\boldsymbol{\alpha}}}$ from above as
$C_{\ref*{C_subgaussian}}K^{K/2}\left\|x_{1}\right\|_{\psi_{2}}^{K}$.
Therefore,

$\displaystyle\left\|{\mathbb{E}}(X^{\top})^{\otimes K}\right\|_{HS}^{2}$
$\displaystyle=\left\|{\mathbb{E}}X^{\otimes K}\right\|_{HS}^{2}\lesssim
K^{K}\left\|x_{1}\right\|_{\psi_{2}}^{2K}\sum_{i=0}^{\lceil
K/2\rceil}\sum_{\begin{subarray}{c}{\boldsymbol{\alpha}}\in[d]^{K}\\\
\left|E({\boldsymbol{\alpha}})\right|=i\end{subarray}}d^{i}\lesssim
K^{K}\left\|x_{1}\right\|_{\psi_{2}}^{2K}\sum_{i=0}^{\lceil
K/2\rceil}d^{i}\binom{K}{2}^{i}$ $\displaystyle\lesssim
K^{K}\left\|x_{1}\right\|_{\psi_{2}}^{2K}\sum_{i=0}^{\lceil
K/2\rceil}d^{i}K^{2i}\lesssim\left\|x_{1}\right\|_{\psi_{2}}^{2K}d^{\lceil
K/2\rceil}K^{2K}.$

Therefore,

$\displaystyle\frac{\gamma_{K}^{2}\left\|{\mathbb{E}}(X^{\top})^{\otimes
K}\right\|_{HS}^{2}}{d^{K}}\lesssim\gamma_{\iota}^{2}\left\|x_{1}\right\|_{\psi_{2}}^{2K}\iota^{2\iota}d^{-\iota/2}.$
(158)

##### The case for $K<\iota$:
$\mathbbm{1}_{\\{K<\iota\\}}\left\|{\mathbb{E}}\left\|X\right\|_{2}^{2\iota-2K}(X^{\top})^{\otimes
K}\right\|_{HS}$.

Given ${\boldsymbol{\alpha}}:=(\alpha_{1},\cdots,\alpha_{K})\in[d]^{K}$, we
construct a undirected graph $G({\boldsymbol{\alpha}})$ with vertex $[K]$, and
$\\{i\\}$ is connected with $\\{j\\}$ for $i,j\in[K]$, if
$\alpha_{i}=\alpha_{j}$. We define a equivalence relation on $[K]$, denoted by
$i\sim j$, where $i,j\in[K]$, if there is a path connecting $\\{i\\}$ and
$\\{j\\}$. We partition $[K]$ into equivalence classes ${\cal
C}({\boldsymbol{\alpha}})=\cup_{l}{\cal C}_{l}({\boldsymbol{\alpha}})$, that
is, for every $i,j\in{\cal C}_{l}({\boldsymbol{\alpha}})$ (possibly $i=j$), we
have $i\sim j$, and ${\cal C}_{l}({\boldsymbol{\alpha}})$ is largest, in the
sense that if $i\sim j$, $i\in{\cal C}_{l}$, then $j\in{\cal C}_{l}$; for
every $i\in{\cal C}_{l}({\boldsymbol{\alpha}})$, $j\in{\cal
C}_{m}({\boldsymbol{\alpha}})$, $l\neq m$, we have $i\not\sim j$. Define the
map $q:j\in[K]\mapsto q(j)\in[\left|{\cal C}({\boldsymbol{\alpha}})\right|]$
such that $j\in{\cal C}_{q(j)}({\boldsymbol{\alpha}})$, that is, the map $q$
maps each vertex into its unique equivalent class. Let ${\cal
O}^{*}({\boldsymbol{\alpha}})=\\{\alpha_{j}:\,j\in[K],\left|{\cal
C}_{q(j)}({\boldsymbol{\alpha}})\right|=1\\}$, and ${\cal
O}^{**}({\boldsymbol{\alpha}})=\\{\alpha_{j}:\,j\in[K],\left|{\cal
C}_{q(j)}({\boldsymbol{\alpha}})\right|>1\\}$. We have the following relation:
$\left|{\cal C}({\boldsymbol{\alpha}})\right|\leq\lfloor\frac{K-\left|{\cal
O}^{*}({\boldsymbol{\alpha}})\right|}{2}\rfloor$. This is because ${\cal
O}^{*}({\boldsymbol{\alpha}})$ and $\\{{\cal
C}_{l}({\boldsymbol{\alpha}}):l\in[\left|{\cal
C}({\boldsymbol{\alpha}})\right|],\left|{\cal
C}_{l}({\boldsymbol{\alpha}})\right|=1\\}$ are one-to-one corresponded; and
for ${\cal C}_{l}({\boldsymbol{\alpha}})$ with $\left|{\cal
C}_{l}({\boldsymbol{\alpha}})\right|>1$, the smallest size of ${\cal
C}_{l}({\boldsymbol{\alpha}})$ is $2$.

Notice that ${\cal O}^{*}({\boldsymbol{\alpha}})\cup{\cal
O}^{**}({\boldsymbol{\alpha}})$ might not be $[d]$. This is illustrated in the
following example: let $K=8$, $d=100$,
$\\{\alpha_{1},\cdots,\alpha_{8}\\}=\\{1,1,2,2,3,3,3,4\\}$, then
$\\{1\\},\\{2\\}$ are connected, so as $\\{3\\},\\{4\\}$ and
$\\{5\\},\\{6\\},\\{7\\}$. Moreover, $1\sim 2$, $3\sim 4$, $5\sim 6\sim 7$,
thus ${\cal C}({\boldsymbol{\alpha}})={\cal
C}_{1}({\boldsymbol{\alpha}})\cup{\cal C}_{2}({\boldsymbol{\alpha}})\cup{\cal
C}_{3}({\boldsymbol{\alpha}})\cup{\cal C}_{4}({\boldsymbol{\alpha}})$ where
${\cal C}_{1}({\boldsymbol{\alpha}})=\\{1,2\\}$, ${\cal
C}_{2}({\boldsymbol{\alpha}})=\\{3,4\\}$, ${\cal
C}_{3}({\boldsymbol{\alpha}})=\\{5,6,7\\}$ and ${\cal
C}_{4}({\boldsymbol{\alpha}})=\\{8\\}$. For any $j\in[8]$, only for $j=8$ we
have $\left|{\cal C}_{q(8)}({\boldsymbol{\alpha}})\right|=\left|{\cal
C}_{4}({\boldsymbol{\alpha}})\right|=1$, hence ${\cal
O}^{*}({\boldsymbol{\alpha}})=\\{\alpha_{8}\\}=\\{4\\}$. Similarly, ${\cal
O}^{**}({\boldsymbol{\alpha}})=\\{1,2,3\\}$. Thus ${\cal
O}^{*}({\boldsymbol{\alpha}})\cup{\cal O}^{**}({\boldsymbol{\alpha}})=[4]$,
however $[d]=[100]$.

$\displaystyle\left({\mathbb{E}}\left\|X\right\|_{2}^{2\iota-2K}X^{\otimes
K}\right)_{{\boldsymbol{\alpha}}}$
$\displaystyle={\mathbb{E}}\left[\left(\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-K\\\
\forall i\in[d],n_{i}\geq
0\end{subarray}}\frac{(\iota-K)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}x_{1}^{2n_{1}}\cdot\cdots\cdot
x_{d}^{2n_{d}}\right)\left(\prod_{\begin{subarray}{c}\alpha_{j}\in{\cal
O}^{*}({\boldsymbol{\alpha}})\end{subarray}}x_{\alpha_{j}}\right)\left(\prod_{\begin{subarray}{c}\alpha_{j}\in{\cal
O}^{**}({\boldsymbol{\alpha}})\end{subarray}}x_{\alpha_{j}}\right)\right].$
(159)

We now seek $n_{1},\cdots,n_{d}$ such that (159) is non-zero. A necessary
condition is as follows: for every $i\in{\cal O}^{*}({\boldsymbol{\alpha}})$,
we must have $n_{i}\geq 1$. Therefore,

$\displaystyle\eqref{eq:proof_head_1}$
$\displaystyle<(2\iota-K)^{\iota}\sum_{\begin{subarray}{c}n_{1}+\cdots+n_{d}=\iota-K\\\
\forall i\in[d],n_{i}\geq 0\\\ \forall i\in{\cal
O}^{*}({\boldsymbol{\alpha}}),n_{i}\geq
1\end{subarray}}\frac{(\iota-K)!}{n_{1}!\cdot\cdots\cdot
n_{d}!}\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-K}<(2\iota-K)^{\iota}\left\|x_{1}\right\|_{\psi_{2}}^{2\iota-K}(\iota-K)!\binom{d+(\iota-K)-1-\left|{\cal
O}^{*}({\boldsymbol{\alpha}})\right|}{\iota-K-\left|{\cal
O}^{*}({\boldsymbol{\alpha}})\right|},$

where we emphasize that when $\iota-K-\left|{\cal
O}^{*}({\boldsymbol{\alpha}})\right|=0$, the binomial coefficient defined as
$1$, and when $\iota-K-\left|{\cal O}^{*}({\boldsymbol{\alpha}})\right|<0$,
the binomial coefficient is $0$. Before we taking square and taking sum over
all ${\boldsymbol{\alpha}}\in[d]^{k}$, we need to count the “degree of
freedom”. Recall the example $K=8$, $d=100$ and
$\\{\alpha_{1},\cdots,\alpha_{8}\\}=\\{1,1,2,2,3,3,3,4\\}$. In this example,
if we take sum over all ${\boldsymbol{\alpha}}$ with the edge of associated
$G({\boldsymbol{\alpha}})$ are the same, it is equivalent to taking sum over
$x_{1}=x_{2}$, $x_{3}=x_{4}$, $x_{5}=x_{6}=x_{7}$, and none of
$x_{1},x_{3},x_{5},x_{8}$ are equal. Therefore, the sum is over
$x_{1},x_{3},x_{5},x_{8}\in[d]$, thus have $d^{4}=d^{\left|{\cal C}\right|}$
terms. Moreover, given $\left|{\cal O}^{*}({\boldsymbol{\alpha}})\right|=\chi$
where $\chi$ is fixed, there are at most $(K-\chi)^{K-\chi}$ choices of
$G({\boldsymbol{\alpha}})$.

Now, we take square and sum over all
${\boldsymbol{\alpha}}=(\alpha_{1},\cdots,\alpha_{K})\in[d]^{k}$,

$\displaystyle\left\|{\mathbb{E}}(\left\|X\right\|_{2}^{2})^{\iota-K}(X^{\top})^{\otimes
K}\right\|_{HS}^{2}=\left\|{\mathbb{E}}(\left\|X\right\|_{2}^{2})^{\iota-K}X^{\otimes
K}\right\|_{HS}^{2}$
$\displaystyle=\sum_{\chi=1}^{K}\sum_{\begin{subarray}{c}{\boldsymbol{\alpha}}\in[d]^{\otimes
K}\\\ \left|{\cal
O}^{*}({\boldsymbol{\alpha}})\right|=\chi\end{subarray}}\left({\mathbb{E}}\left\|X\right\|_{2}^{2\iota-2K}X^{\otimes
K}\right)_{{\boldsymbol{\alpha}}}^{2}$
$\displaystyle\lesssim\sum_{\chi=1}^{\iota-K}(K-\chi)^{K-\chi}d^{\lfloor\frac{K-\chi}{2}\rfloor}\left\|x_{1}\right\|_{\psi_{2}}^{2(2\iota-K)}(2\iota-K)^{2\iota}((\iota-K)!)^{2}\left(\frac{2ed}{\iota-K-\chi}\right)^{2(\iota-K-\chi)}$
$\displaystyle\lesssim(K-1)^{K-1}\left\|x_{1}\right\|_{\psi_{2}}^{2(2\iota-K)}(2\iota-K)^{2\iota}((\iota-K)!)^{2}\left(\frac{2e}{\iota-K}\right)^{2(\iota-K)}\sum_{\chi=1}^{\iota-K}d^{2\iota-\frac{3}{2}K-\frac{5}{2}\chi}$
$\displaystyle\lesssim(K-1)^{K-1}\left\|x_{1}\right\|_{\psi_{2}}^{2(2\iota-K)}(2\iota-K)^{2\iota}((\iota-K)!)^{2}\left(\frac{2e}{\iota-K}\right)^{2(\iota-K)}d^{2\iota-\frac{3}{2}K-\frac{5}{2}}.$

As a result,

$\displaystyle\frac{\gamma_{\iota}^{2}\left\|{\mathbb{E}}(\left\|X\right\|_{2}^{2})^{\iota-K}(X^{\top})^{\otimes
K}\right\|_{HS}^{2}}{d^{2\iota}}\lesssim\gamma_{\iota}^{2}(K-1)^{K-1}\left\|x_{1}\right\|_{\psi_{2}}^{2(2\iota-K)}(2\iota-K)^{2\iota}d^{2\iota-\frac{3}{2}K-\frac{5}{2}}.$
(160)

Combining (1), (2), (157), (158) and (160), we know that: for any $r\in[2L]$,
we have,

$\displaystyle\left\|{\mathbb{E}}\mathbf{D}^{r}K(X,X)\right\|_{HS}$
$\displaystyle\leq\sum_{\iota=1}^{L}\left\|{\mathbb{E}}\mathbf{D}^{r}\frac{\gamma_{\iota}}{d^{\iota}}(\left\|X\right\|_{2}^{2})^{\iota}\right\|_{HS}\lesssim\frac{2^{2L}L^{3L}}{\sqrt{d}}(\left\|x_{1}\right\|_{\psi_{2}}^{2L-1}\vee
1)\sum_{\iota=1}^{L}\gamma_{\iota}.$ (161)

Plug it into (150), we obtain that for any $r\in[2L]$,

$\displaystyle\left(\left\|x_{1}\right\|_{\psi_{2}}^{r}\max\left(\left\|{\mathbb{E}}\mathbf{D}^{r}K(X,X)\right\|_{\cal
J}:{\cal J}\in
P_{r}\right)\right)^{2/r}\lesssim\left(\frac{2^{2L}L^{3L}}{\sqrt{d}}(\left\|x_{1}\right\|_{\psi_{2}}^{2L+r-1}\vee\left\|x_{1}\right\|_{\psi_{2}}^{r})\sum_{\iota=1}^{L}\gamma_{\iota}\right)^{2/r}.$

By Theorem 10, we have, for any $t>0$:

$\displaystyle{\mathbb{P}}\left(\left|K(X,X)-{\mathbb{E}}K(X,X)\right|\geq
t\right)\leq\exp\left(-C_{\ref*{C_non_linear_HS}}\frac{t^{\frac{1}{L}}d^{\frac{1}{2L}}}{4L^{3}\left(\sum_{\iota=1}^{L}\gamma_{\iota}\right)^{\frac{1}{L}}}\right).$

####  6.5.19 Verifying (8) from Assumption 5 and Assumption 2 under sub-
Gaussian assumption.

We apply Theorem 10 to
$g(X)=\left\|\Gamma_{1:k}^{-1/2}\phi_{1:k}(X)\right\|_{\cal H}^{2}$, and
$g(X)=\left\|\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}$.

##### Checking diagonal concentration in Assumption 2,
$g(X)=\left\|\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}$.

By the definition of $\Gamma_{k+1:\infty}$ and $\phi_{k+1:\infty}(X)$, we know
that
$\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}(X)=\sum_{j>k}\sqrt{\sigma_{j}}\varphi_{j}(X)\varphi_{j}$.
For each $j\in{\mathbb{N}}_{+}$, let
$f_{j}=\frac{1}{\sqrt{\sigma_{j}}}\varphi_{j}$ be the corresponding ONB in
$L_{2}(\mu)$, then
$\left\|\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}=\sum_{j>k}\sigma_{j}^{2}f_{j}^{2}(X)$. Compared to
$\left\|\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}=\sum_{j>k}\sigma_{j}f_{j}^{2}(X)$, we observe that the eigenvalues are
replaced by their square.

For any $r\geq 0$, $i_{1},\cdots,i_{r}\in[d]$ and $X\in{\mathbb{R}}^{d}$, we
have

$\displaystyle\left(\mathbf{D}^{r}\left\|\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}\right)_{i_{1},\cdots,i_{r}}$
$\displaystyle=\left(\frac{\partial^{r}}{\partial x_{1}\cdots\partial
x_{r}}\right)\sum_{j>k}\sigma_{j}^{2}f_{j}^{2}(X)\leq\sigma_{k+1}\left(\frac{\partial^{r}}{\partial
x_{1}\cdots\partial x_{r}}\right)\sum_{j>k}\sigma_{j}f_{j}^{2}(X)$
$\displaystyle=\sigma_{k+1}\left(\mathbf{D}^{r}\left\|\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}\right)_{i_{1},\cdots,i_{r}}.$

By the positive homogeneity of expectation and Hilbert-Schmidt norm, we know
that for any $r$, we have

$\displaystyle\left\|{\mathbb{E}}\mathbf{D}^{r}\left\|\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}\right\|_{HS}\leq\sigma_{k+1}\left\|{\mathbb{E}}\mathbf{D}^{r}\left\|\phi_{k+1:\infty}(X)\right\|_{\cal
H}^{2}\right\|_{HS},$

where upper bounds for the right-hand-side may be found in (161). We apply
Theorem 10 with $t=1000\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})$ for
$k=\sum_{i=0}^{\iota}d^{\iota}$. Notice that at this time,
$\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})\sim d^{-(\iota+1)}$ (see the
discussion after Lemma 19), and $\sigma_{k+1}\sim d^{-(\iota+1)}$. By Theorem
10 together with (161), we can take $\delta_{\ref*{delta_DMU_L2}}=999$ and
${\gamma_{\ref*{gamma_DMU_L2}}}\sim\gamma$.

##### Checking diagonal term concentration in Assumption 5,
$g(X)=\left\|\Gamma_{1:k}^{-1/2}\phi_{1:k}(X)\right\|_{\cal H}^{2}$.

The idea is again to use Theorem 10, by noticing that for any $r\geq 0$,
$i_{1},\cdots,i_{r}\in[d]$ and $X\in{\mathbb{R}}^{d}$, we have

$\displaystyle\left(\mathbf{D}^{r}\left\|\Gamma_{1:k}^{-1/2}\phi_{1:k}(X)\right\|_{\cal
H}^{2}\right)_{i_{1},\cdots,i_{r}}$
$\displaystyle=\left(\frac{\partial^{r}}{\partial x_{1}\cdots\partial
x_{r}}\right)\sum_{j\leq
k}f_{j}^{2}(X)\leq\sigma_{k}^{-1}\left(\frac{\partial^{r}}{\partial
x_{1}\cdots\partial x_{r}}\right)\sum_{j\leq k}\sigma_{j}f_{j}^{2}(X)$
$\displaystyle=\sigma_{k}^{-1}\left(\mathbf{D}^{r}\left\|\phi_{1:k}(X)\right\|_{\cal
H}^{2}\right)_{i_{1},\cdots,i_{r}}.$

As a result, for any $r$, we have

$\displaystyle\left\|{\mathbb{E}}\mathbf{D}^{r}\left\|\Gamma_{1:k}^{-1/2}\phi_{1:k}(X)\right\|_{\cal
H}^{2}\right\|_{HS}\leq\sigma_{k}^{-1}\left\|{\mathbb{E}}\mathbf{D}^{r}\left\|\phi_{1:k}(X)\right\|_{\cal
H}^{2}\right\|_{HS},$

where the upper bound for the right-hand-side may be found in (161). We apply
Theorem 10 with $t=1000k$, $k=\sum_{i=0}^{\iota}d^{i}$. Notice that
$\sigma_{k}^{-1}\sim d^{\iota}\sim k$, we can take
$\delta_{\ref*{delta_RIP}}=999$ and ${\gamma_{\ref*{gamma_RIP}}}\sim\gamma$.

####  6.5.20 Proof of Proposition 30

In this subsection, we verify that (9), (15) and (16) hold under Assumption 6
with $\epsilon=6$. The following Lemma is taken from [LRZ20, Lemma 10]:

######  Lemma 22.

Suppose [1] of Assumption 6 holds. There exists $\kappa_{L}\geq 1$ such that
for any $\beta\in\ell_{2}^{\binom{d+L}{L}}$ and
$f_{\beta}(\cdot):=\sum_{\left|{\cal I}\right|\leq L}\beta_{\cal I}Q_{\cal
I}(\cdot)$, we have

$\displaystyle\left\|f_{\beta}\right\|_{L_{4}}\leq\kappa_{L}\left\|f_{\beta}\right\|_{L_{2}}=\kappa_{L}\sqrt{\sum_{\left|{\cal
I}\right|\leq L}\beta_{\cal I}^{2}}.$

The original assumption of [LRZ20] in Lemma 22 is: there exist absolute
constants $\nu>1,{C_{76}}>0$ such that
${\mathbb{P}}\left(\left|x_{1}\right|\geq t\right)\leq
C_{\ref*{C_LRZ}}(1+t)^{-\nu}$ for all $t\geq 0$. This assumption is implied by
Assumption 6. By Assumption 6, $x_{1}$ has a finite $\psi_{2}$ norm
$\left\|x_{1}\right\|_{\psi_{2}}$ such that
${\mathbb{P}}\left(\left|x_{1}\right|\geq
t\right)\leq\exp\left(-{C_{77}}t^{2}/\left\|x_{1}\right\|_{\psi_{2}}^{2}\right)$
for some absolute constant $C_{\ref*{C_subgaussian}}>0$. In fact, one can
choose
$\nu=\sqrt{2C_{\ref*{C_subgaussian}}\log{C_{\ref*{C_LRZ}}}/\left\|x_{1}\right\|_{\psi_{2}}^{2}}>1$
and
$C_{\ref*{C_LRZ}}>\exp\left(\left\|x_{1}\right\|_{\psi_{2}}^{2}/(2C_{\ref*{C_subgaussian}})\right)>1$.
This is because
$\exp\left(-C_{\ref*{C_subgaussian}}t^{2}/\left\|x_{1}\right\|_{\psi_{2}}^{2}\right)\leq
C_{\ref*{C_LRZ}}(1+t)^{-\nu}$ for all $t\geq 0$ is equivalent to
$(-C_{\ref*{C_subgaussian}}/\left\|x_{1}\right\|_{\psi_{2}}^{2})t^{2}+\nu\log(1+t)-\log{C_{\ref*{C_LRZ}}}\leq
0$ for all $t\geq 0$, and the above choice of $C_{\ref*{C_LRZ}}$ and $\nu$ is
a sufficient condition for it.

Proof. [Proposition 30] To prove Proposition 30, we simply note that $(Q_{\cal
I})_{\cal I}$ is an ONB of $L_{2}(\mu)$ by Lemma 19. Notice that for any
$\gamma\in\ell_{2}^{\binom{d+L}{L}}$, $(f_{\gamma})^{2}\in L_{2}(\mu)$ due to
$\mu$ being sub-Gaussian and $(Q_{\cal I})$ being finite-degree polynomial.
There therefore exists $\zeta\in\ell_{2}^{\binom{d+2L}{2L}}$ such that

$\displaystyle\left(f_{\gamma}(\cdot)\right)^{2}=f_{\zeta}(\cdot)=\sum_{\left|{\cal
I}\right|\leq 2L}\zeta_{\cal I}Q_{\cal I}(\cdot).$

Applying Lemma 22 with $L$ replaced by $2L$ and $\beta$ replaced by $\zeta$,
we have

$\displaystyle\left\|f_{\gamma}\right\|_{L_{8}}^{2}=\left\|f_{\zeta}\right\|_{L_{4}}\leq\kappa_{2L}\sqrt{\sum_{\left|{\cal
I}\right|\leq 2L}\zeta_{\cal I}^{2}}.$

On the other hand, we know that $\sum_{\left|{\cal I}\right|\leq
2L}\zeta_{\cal I}^{2}=\left\|f_{\gamma}\right\|_{L_{4}}^{2}$. This is because

$\displaystyle
f_{\gamma}^{4}(X)=\left(f_{\gamma}^{2}(X)\right)^{2}=\left(f_{\zeta}(X)\right)^{2}=\sum_{\left|{\cal
I}\right|,\left|{\cal J}\right|\leq 2L}\zeta_{\cal I}\zeta_{\cal J}Q_{\cal
I}(X)Q_{\cal J}(X),$

which implies that $\left\|f_{\gamma}\right\|_{L_{4}}^{4}=\sum_{\left|{\cal
I}\right|\leq 2L}\zeta_{\cal I}^{2}$. Applying Lemma 22 again with
$\beta=\gamma$, we have $\sum_{\left|{\cal I}\right|\leq 2L}\zeta_{\cal
I}^{2}=\left\|f_{\gamma}\right\|_{L_{4}}^{4}\leq\kappa_{L}^{4}\left\|f_{\gamma}\right\|_{L_{2}}^{4}$.
As a result,

$\displaystyle\left\|f_{\gamma}\right\|_{L_{8}}\leq\sqrt{\kappa_{2L}}\kappa_{L}\left\|f_{\gamma}\right\|_{L_{2}}.$

Thus, Proposition 29 as a corollary of Theorem 4 has been proven.

## References

  * [AAGM15] Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D. Milman.  Asymptotic Geometric Analysis, Part I.  American Mathematical Society, Providence, RI, June 2015.
  * [Ada15] Radoslaw Adamczak.  A note on the Hanson-Wright inequality for random vectors with dependencies.  Electronic Communications in Probability, 20(none):1–13, January 2015.  Publisher: Institute of Mathematical Statistics and Bernoulli Society.
  * [AK16] Fernando Albiac and Nigel J. Kalton.  Topics in Banach Space Theory, volume 233 of Graduate Texts in Mathematics.  Springer International Publishing, Cham, 2016.
  * [AK23] Radosław Adamczak and Dominik Kutek.  On Orlicz spaces satisfying the Hoffmann-J{\o}rgensen inequality, October 2023.  arXiv:2310.04163 [math].
  * [AKLZ20] Benjamin Aubin, Florent Krzakala, Yue Lu, and Lenka Zdeborová.  Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization.  In Advances in Neural Information Processing Systems, volume 33, pages 12199–12210. Curran Associates, Inc., 2020.
  * [AW15] Radosław Adamczak and Paweł Wolff.  Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order.  Probability Theory and Related Fields, 162(3):531–586, August 2015.
  * [Bac17] Francis Bach.  Breaking the Curse of Dimensionality with Convex Neural Networks.  Journal of Machine Learning Research, 18(19):1–53, 2017.
  * [Bac24] Francis Bach.  Learning Theory from First Principles.  MIT Press, 2024.
  * [BAGJ21] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath.  Online stochastic gradient descent on non-convex losses from high-dimensional inference.  Journal of Machine Learning Research, 22(106):1–51, 2021.
  * [BB21] Alberto Bietti and Francis R. Bach.  Deep Equals Shallow for ReLU Networks in Kernel Regimes.  In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
  * [BBPV23] Alberto Bietti, Joan Bruna, and Loucas Pillaud-Vivien.  On Learning Gaussian Multi-index Models with Gradient Flow, November 2023.  arXiv:2310.19793 [cs, math, stat].
  * [BBSS22] Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song.  Learning Single-Index Models with Shallow Neural Networks, October 2022.  arXiv:2210.15651 [cs, math, stat].
  * [Bec92] W Beckner.  Sobolev inequalities, the Poisson semigroup, and analysis on the sphere Sn.  Proceedings of the National Academy of Sciences, 89(11):4816–4819, June 1992.  Publisher: Proceedings of the National Academy of Sciences.
  * [Bel17] Pierre C. Bellec.  Optimistic lower bounds for convex regularized least-squares, October 2017.  arXiv:1703.01332 [math, stat].
  * [Bel21] Mikhail Belkin.  Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation, May 2021.  arXiv:2105.14368 [cs, math, stat].
  * [BES+22] Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang.  High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation, May 2022.  arXiv:2205.01445 [cs, math, stat].
  * [BES+23] Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki, Zhichao Wang, and Denny Wu.  Learning in the Presence of Low-dimensional Structure: A Spiked Random Matrix Perspective.  November 2023.
  * [BLLT20] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler.  Benign overfitting in linear regression.  Proceedings of the National Academy of Sciences, 117(48):30063–30070, December 2020.  Publisher: Proceedings of the National Academy of Sciences.
  * [BLM13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  Concentration Inequalities: A Nonasymptotic Theory of Independence.  Oxford University Press, February 2013.
  * [BM16] Gilles Blanchard and Nicole Mücke.  Kernel regression, minimax rates and effective dimensionality: beyond the regular case, November 2016.  arXiv:1611.03979 [stat].
  * [BM19] Alberto Bietti and Julien Mairal.  On the Inductive Bias of Neural Tangent Kernels.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [BM22] Daniel Bartl and Shahar Mendelson.  Random embeddings with an almost Gaussian distortion.  Advances in Mathematics, 400:108261, May 2022.
  * [BMM18] Mikhail Belkin, Siyuan Ma, and Soumik Mandal.  To Understand Deep Learning We Need to Understand Kernel Learning.  In Proceedings of the 35th International Conference on Machine Learning, pages 541–549. PMLR, July 2018.  ISSN: 2640-3498.
  * [BMM19] Gilles Blanchard, Peter Mathé, and Nicole Mücke.  Lepskii Principle in Supervised Learning, May 2019.  arXiv:1905.10764 [math, stat].
  * [BMR21] Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin.  Deep learning: a statistical viewpoint.  Acta Numerica, 30:87–201, May 2021.  Publisher: Cambridge University Press.
  * [Bou23] Nicolas Boumal.  An Introduction to Optimization on Smooth Manifolds.  Cambridge University Press, Cambridge, 2023.
  * [Boy22] Claire Boyer.  Living la vida loca: learning in interpolation regimes.  2022\.
  * [BPR07] Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco.  On regularization algorithms in learning theory.  Journal of Complexity, 23(1):52–72, February 2007.
  * [BS24] Daniel Barzilai and Ohad Shamir.  Generalization in Kernel Regression Under Realistic Assumptions, February 2024.  arXiv:2312.15995 [cs, stat].
  * [Buc22] Simon Buchholz.  Kernel interpolation in Sobolev spaces is not consistent in low dimensions.  In Proceedings of Thirty Fifth Conference on Learning Theory, pages 3410–3440. PMLR, June 2022.  ISSN: 2640-3498.
  * [CCFRF22] Lénaïc Chizat, Maria Colombo, Xavier Fernández-Real, and Alessio Figalli.  Infinite-width limit of deep linear neural networks, November 2022.  arXiv:2211.16980 [cs, math, stat].
  * [CDV07] A. Caponnetto and E. De Vito.  Optimal Rates for the Regularized Least-Squares Algorithm.  Foundations of Computational Mathematics, 7(3):331–368, July 2007.
  * [CLvdG22] Geoffrey Chinot, Matthias Loffler, and Sara van de Geer.  On the robustness of minimum norm interpolators and regularized empirical risk minimizers.  The Annals of Statistics, 2022.
  * [COB19] Lénaïc Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  In Proceedings of the 33rd International Conference on Neural Information Processing Systems, number 264, pages 2937–2947. Curran Associates Inc., Red Hook, NY, USA, 2019.
  * [CS13] Xiuyuan Cheng and Amit Singer.  The spectrum of random inner-product kernel matrices.  Random Matrices: Theory and Applications, 02(04):1350010, October 2013.  Publisher: World Scientific Publishing Co.
  * [DHP21] Ronald DeVore, Boris Hanin, and Guergana Petrova.  Neural network approximation.  Acta Numerica, 30:327–444, May 2021.
  * [DKL+23] Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan.  How Two-Layer Neural Networks Learn, One (Giant) Step at a Time, October 2023.  arXiv:2305.18270 [cs, stat].
  * [DL20] Oussama Dhifallah and Yue M. Lu.  A Precise Performance Analysis of Learning with Random Features, August 2020.  arXiv:2008.11904 [cs, math].
  * [dlPG99] Víctor H. de la Peña and Evarist Giné.  Decoupling.  Probability and its Applications. Springer, New York, NY, 1999.
  * [DLS22] Alex Damian, Jason D. Lee, and Mahdi Soltanolkotabi.  Neural Networks can Learn Representations with Gradient Descent, June 2022.  arXiv:2206.15144 [cs, math, stat].
  * [DRSY22] Konstantin Donhauser, Nicolò Ruggeri, Stefan Stojanovic, and Fanny Yang.  Fast rates for noisy interpolation require rethinking the effect of inductive bias.  In Proceedings of the 39th International Conference on Machine Learning, pages 5397–5428. PMLR, June 2022.  ISSN: 2640-3498.
  * [DV13] Yen Do and Van Vu.  The spectrum of random kernel matrices: universality results for rough and varying kernels.  Random Matrices: Theory and Applications, 02(03):1350005, July 2013.  Publisher: World Scientific Publishing Co.
  * [DWY21] Konstantin Donhauser, Mingqi Wu, and Fanny Yang.  How rotational invariance of common kernels prevents generalization in high dimensions.  In Proceedings of the 38th International Conference on Machine Learning, pages 2804–2814. PMLR, July 2021.  ISSN: 2640-3498.
  * [EK10] Noureddine El Karoui.  The spectrum of kernel random matrices.  The Annals of Statistics, 38(1):1–50, February 2010.  Publisher: Institute of Mathematical Statistics.
  * [FE12] Christopher Frye and Costas J. Efthimiou.  Spherical Harmonics in p Dimensions, May 2012.  arXiv:1205.3548 [hep-th, physics:math-ph].
  * [FM19] Zhou Fan and Andrea Montanari.  The spectral norm of random inner-product kernel matrices.  Probability Theory and Related Fields, 173(1):27–85, February 2019.
  * [FR13] Simon Foucart and Holger Rauhut.  A Mathematical Introduction to Compressive Sensing.  Applied and Numerical Harmonic Analysis. Springer, New York, NY, 2013.
  * [FS20] Simon Fischer and Ingo Steinwart.  Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm, October 2020.  arXiv:1702.07254 [stat].
  * [FW20] Zhou Fan and Zhichao Wang.  Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks, October 2020.  arXiv:2005.11879 [cs, math, stat].
  * [GLPTJ17] Olivier Guédon, Alexander E. Litvak, Alain Pajor, and Nicole Tomczak-Jaegermann.  On the interval of fluctuation of the singular values of random matrices.  Journal of the European Mathematical Society, 19(5):1469–1505, April 2017.
  * [GMKZ20] Sebastian Goldt, Marc Mézard, Florent Krzakala, and Lenka Zdeborová.  Modelling the influence of data structure on learning in neural networks: the hidden manifold model.  Physical Review X, 10(4):041044, December 2020.  arXiv:1909.11500 [cond-mat, stat].
  * [GMMM21] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Linearized two-layers neural networks in high dimension.  The Annals of Statistics, 49(2):1029–1054, April 2021.  Publisher: Institute of Mathematical Statistics.
  * [GMPTJ07] Olivier Guédon, Shahar Mendelson, Alain Pajor, and Nicole Tomczak-Jaegermann.  Subspaces and Orthogonal Decompositions Generated by Bounded Orthogonal Systems.  Positivity, 11(2):269–283, May 2007.
  * [HHvLS23] Moritz Haas, David Holzmüller, Ulrike von Luxburg, and Ingo Steinwart.  Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension, May 2023.  arXiv:2305.14077 [cs, math, stat].
  * [HL22] Hong Hu and Yue M. Lu.  Universality Laws for High-Dimensional Learning with Random Features, October 2022.  arXiv:2009.07669 [cs, math].
  * [HMRT22] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani.  Surprises in high-dimensional ridgeless least squares interpolation.  The Annals of Statistics, 50(2):949–986, April 2022.  Publisher: Institute of Mathematical Statistics.
  * [HT23] Han Huang and Konstantin Tikhomirov.  On dimension-dependent concentration for convex Lipschitz functions in product spaces.  Electronic Journal of Probability, 28(none):1–23, January 2023.  Publisher: Institute of Mathematical Statistics and Bernoulli Society.
  * [HTF09] Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  The Elements of Statistical Learning.  Springer Series in Statistics. Springer, New York, NY, 2009.
  * [JGH18] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: convergence and generalization in neural networks.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, pages 8580–8589, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * [Juk11] Stasys Jukna.  Extremal combinatorics: with applications in computer science, volume 571.  Springer, 2011.
  * [KB17] Diederik P. Kingma and Jimmy Ba.  Adam: A Method for Stochastic Optimization, January 2017.  arXiv:1412.6980 [cs].
  * [KC22] Arun Kumar Kuchibhotla and Abhishek Chakrabortty.  Moving beyond sub-Gaussianity in high-dimensional statistics: applications in covariance estimation and linear regression.  Information and Inference: A Journal of the IMA, 11(4):1389–1456, December 2022.
  * [KR21] Gil Kur and Alexander Rakhlin.  On the Minimal Error of Empirical Risk Minimization.  In Proceedings of Thirty Fourth Conference on Learning Theory, pages 2849–2852. PMLR, July 2021.  ISSN: 2640-3498.
  * [KZ20] Yegor Klochkov and Nikita Zhivotovskiy.  Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method.  Electronic Journal of Probability, 22:1–30, 2020.  Publisher: Institute of Mathematical Statistics.
  * [KZSS21] Frederic Koehler, Lijia Zhou, Danica J. Sutherland, and Nathan Srebro.  Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting.  October 2021.
  * [Lan02] Serge Lang.  Algebra, volume 211 of Graduate Texts in Mathematics.  Springer, New York, NY, 2002.
  * [Lax02] Peter D. Lax.  Functional Analysis.  Wiley–Blackwell, New York, April 2002.
  * [Leh11] Joseph Lehec.  Moments of the Gaussian Chaos.  In Catherine Donati-Martin, Antoine Lejay, and Alain Rouault, editors, Séminaire de Probabilités XLIII, Lecture Notes in Mathematics, pages 327–340. Springer, Berlin, Heidelberg, 2011.
  * [Li] Zhifan Li.  Personal Communication.
  * [LM18] Guillaume Lecué and Shahar Mendelson.  REGULARIZATION AND THE SMALL-BALL METHOD I: SPARSE RECOVERY.  The Annals of Statistics, 46(2):611–641, 2018.  Publisher: Institute of Mathematical Statistics.
  * [Lon21] Philip M. Long.  Properties of the After Kernel, December 2021.  arXiv:2105.10585 [cs].
  * [LR20] Tengyuan Liang and Alexander Rakhlin.  Just Interpolate: Kernel ”Ridgeless” Regression Can Generalize.  The Annals of Statistics, 48(3), June 2020.  arXiv:1808.00387 [cs, math, stat].
  * [LRZ20] Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai.  On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels.  In Proceedings of Thirty Third Conference on Learning Theory, pages 2683–2711. PMLR, July 2020.  ISSN: 2640-3498.
  * [LS22] Guillaume Lecué and Zong Shang.  A geometrical viewpoint on the benign overfitting property of the minimum ell_2-norm interpolant estimator, March 2022.
  * [LZL23] Yicheng Li, Haobo Zhang, and Qian Lin.  On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decay, September 2023.  arXiv:2309.13337 [cs, math, stat].
  * [Man13] Jonathan H. Manton.  Differential Calculus, Tensor Products and the Importance of Notation, October 2013.  arXiv:1208.0197 [math].
  * [MBM18] Song Mei, Yu Bai, and Andrea Montanari.  The Landscape of Empirical Risk for Nonconvex Losses.  The Annals of Statistics, 46(6A):2747–2774, 2018.  Publisher: Institute of Mathematical Statistics.
  * [Men16] Shahar Mendelson.  Upper bounds on product and multiplier empirical processes.  Stochastic Processes and their Applications, 126(12):3652–3680, December 2016.
  * [MHPG+23] Alireza Mousavi-Hosseini, Sejun Park, Manuela Girotti, Ioannis Mitliagkas, and Murat A. Erdogdu.  Neural Networks Efficiently Learn Low-Dimensional Representations with SGD, March 2023.  arXiv:2209.14863 [cs, stat].
  * [Mis22] Theodor Misiakiewicz.  Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression, April 2022.  arXiv:2204.10425 [math, stat].
  * [MKDM22] Andrew D. Mcrae, Santhosh Karnik, Mark Davenport, and Vidya K. Muthukumar.  Harmless interpolation in regression and classification with structured features.  In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 5853–5875. PMLR, May 2022.  ISSN: 2640-3498.
  * [MLHD23] Behrad Moniri, Donghwan Lee, Hamed Hassani, and Edgar Dobriban.  A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networks, October 2023.  arXiv:2310.07891 [cs, stat].
  * [MM20] Song Mei and Andrea Montanari.  The generalization error of random features regression: Precise asymptotics and double descent curve, December 2020.  arXiv:1908.05355 [math, stat].
  * [MMM22] Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration.  Applied and Computational Harmonic Analysis, 59:3–84, July 2022.
  * [MN10] Shahar Mendelson and Joseph Neeman.  Regularization in kernel learning.  The Annals of Statistics, 38(1):526–565, February 2010.  Publisher: Institute of Mathematical Statistics.
  * [MR22] Jaouad Mourtada and Lorenzo Rosasco.  An elementary analysis of ridge regression with random design.  Comptes Rendus. Mathématique, 360(G9):1055–1063, September 2022.  arXiv:2203.08564 [cs, math, stat].
  * [MS22] Andrea Montanari and Basil N. Saeed.  Universality of empirical risk minimization.  In Proceedings of Thirty Fifth Conference on Learning Theory, pages 4310–4312. PMLR, June 2022.  ISSN: 2640-3498.
  * [MS23] Carl D. Meyer and Ian Stewart.  Matrix Analysis and Applied Linear Algebra, Second Edition.  Other Titles in Applied Mathematics. Society for Industrial and Applied Mathematics, January 2023.
  * [MVZ22] Jaouad Mourtada, Tomas Vaškevičius, and Nikita Zhivotovskiy.  Distribution-free robust linear regression.  Mathematical Statistics and Learning, 4(3):253–292, January 2022.
  * [OS19] Samet Oymak and Mahdi Soltanolkotabi.  Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?  In Proceedings of the 36th International Conference on Machine Learning, pages 4951–4960. PMLR, May 2019.  ISSN: 2640-3498.
  * [Pis89] Gilles Pisier.  The Volume of Convex Bodies and Banach Space Geometry.  Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1989.
  * [PVB23] Loucas Pillaud-Vivien and Francis Bach.  Kernelized Diffusion Maps.  In Proceedings of Thirty Sixth Conference on Learning Theory, pages 5236–5259. PMLR, July 2023.  ISSN: 2640-3498.
  * [RBPB22] Adityanarayanan Radhakrishnan, Daniel Beaglehole, Parthe Pandit, and Mikhail Belkin.  Feature learning in neural networks and kernel machines that recursively learn features, December 2022.  arXiv:2212.13881 [cs].
  * [RW05] Carl Edward Rasmussen and Christopher K. I. Williams.  Gaussian Processes for Machine Learning.  November 2005.
  * [RZ19] Alexander Rakhlin and Xiyu Zhai.  Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon.  In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 2595–2623. PMLR, 2019.
  * [Sam23] Holger Sambale.  Some Notes on Concentration for $\alpha$-Subexponential Random Variables.  In Radosław Adamczak, Nathael Gozlan, Karim Lounici, and Mokshay Madiman, editors, High Dimensional Probability IX, pages 167–192, Cham, 2023. Springer International Publishing.
  * [SC08] Ingo Steinwart and Andreas Christmann.  Support Vector Machines.  Information Science and Statistics. Springer, New York, NY, 2008.  ISSN: 1613-9011.
  * [SH20] Johannes Schmidt-Hieber.  Nonparametric regression using deep neural networks with ReLU activation function.  The Annals of Statistics, 48(4):1875–1897, August 2020.  Publisher: Institute of Mathematical Statistics.
  * [Sha22] Ohad Shamir.  The Implicit Bias of Benign Overfitting.  In Proceedings of Thirty Fifth Conference on Learning Theory, pages 448–478. PMLR, June 2022.  ISSN: 2640-3498.
  * [SHS09] Ingo Steinwart, Don R. Hush, and Clint Scovel.  Optimal Rates for Regularized Least Squares Regression.  In COLT, pages 79–93, 2009.
  * [SLTC20] Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet.  Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixtures, January 2020.  arXiv:2001.08370 [cs, stat].
  * [SMG14] Andrew M. Saxe, James L. McClelland, and Surya Ganguli.  Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, February 2014.  arXiv:1312.6120 [cond-mat, q-bio, stat].
  * [SS16] Saburou Saitoh and Yoshihiro Sawano.  Theory of Reproducing Kernels and Applications, volume 44 of Developments in Mathematics.  Springer, Singapore, 2016.
  * [STC04] John Shawe-Taylor and Nello Cristianini.  Kernel Methods for Pattern Analysis.  Cambridge University Press, Cambridge, 2004.
  * [Suz18] Taiji Suzuki.  Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality.  September 2018.
  * [Tal96] Michel Talagrand.  A New Look at Independence.  The Annals of Probability, 24(1):1–34, 1996.  Publisher: Institute of Mathematical Statistics.
  * [Tal21] Michel Talagrand.  Upper and Lower Bounds for Stochastic Processes: Decomposition Theorems, volume 60 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics.  Springer International Publishing, Cham, 2021.
  * [TB23] Alexander Tsigler and Peter L. Bartlett.  Benign overfitting in ridge regression.  Journal of Machine Learning Research, 24(123):1–76, 2023.
  * [Tik18] Konstantin Tikhomirov.  Sample Covariance Matrices of Heavy-Tailed Distributions.  International Mathematics Research Notices, 2018(20):6254–6289, October 2018.
  * [TV23] Yan Shuo Tan and Roman Vershynin.  Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval.  Journal of Machine Learning Research, 24(58):1–47, 2023.
  * [Ver11] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices, November 2011.  arXiv:1011.3027 [cs, math].
  * [Ver18] Roman Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018.
  * [VS21] Gal Vardi and Ohad Shamir.  Implicit Regularization in ReLU Networks with the Square Loss.  In Proceedings of Thirty Fourth Conference on Learning Theory, pages 4224–4258. PMLR, July 2021.  ISSN: 2640-3498.
  * [Wai19] Martin J. Wainwright.  High-Dimensional Statistics: A Non-Asymptotic Viewpoint.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2019.
  * [WDY22] Guillaume Wang, Konstantin Donhauser, and Fanny Yang.  Tight bounds for minimum $\ell_1$-norm interpolation of noisy data.  In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 10572–10602. PMLR, May 2022.  ISSN: 2640-3498.
  * [WGL+20] Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro.  Kernel and Rich Regimes in Overparametrized Models.  In Proceedings of Thirty Third Conference on Learning Theory, pages 3635–3673. PMLR, July 2020.  ISSN: 2640-3498.
  * [WZ23] Zhichao Wang and Yizhe Zhu.  Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks.  Annals of Applied Probability, 2023.  arXiv:2109.09304 [cs, math, stat].
  * [XHM+22] Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington.  Precise Learning Curves and Higher-Order Scalings for Dot-product Kernel Regression.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 4558–4570. Curran Associates, Inc., 2022.
  * [Yan20] Greg Yang.  Tensor Programs II: Neural Tangent Kernel for Any Architecture.  CoRR, abs/2006.14548, 2020.  arXiv: 2006.14548.
  * [Yar17] Dmitry Yarotsky.  Error bounds for approximations with deep ReLU networks.  Neural Networks, 94:103–114, October 2017.
  * [YH21] Greg Yang and Edward J. Hu.  Tensor Programs IV: Feature Learning in Infinite-Width Neural Networks.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 11727–11737. PMLR, 2021.
  * [Yok92] Takeo Yokonuma.  Tensor Spaces and Exterior Algebra.  American Mathematical Soc., 1992.
  * [ZBH+17] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [Zhi21] Nikita Zhivotovskiy.  Dimension-free Bounds for Sums of Independent Matrices and Simple Tensors via the Variational Principle.  arXiv, 2021.
  * [ZLL23] Haobo Zhang, Yicheng Li, and Qian Lin.  On the Optimality of Misspecified Spectral Algorithms, August 2023.  arXiv:2303.14942 [math, stat].