particles have $\ell_{2}$ norm at most $1$. Additionally, for the case
$i_{2}\geq 2$, after taking the average of $\|\delta^{\prime}_{\eta
t}\|_{2}^{i_{2}}\lesssim\|\delta^{\prime}_{\eta t}\|_{2}^{2}$ across all
$\chi$, the bound is at most

$\displaystyle(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})$
$\displaystyle(\log d)^{O(1)}\overline{\Delta}_{\eta
t}^{2}\|{\tilde{\delta}}_{t}\|_{2}^{2}\Big{(}\sqrt{\frac{d}{n}}+\frac{d^{(i_{2}+i_{4}+i_{5})/2+1}}{n}+\frac{1}{d^{\Omega(\log
d)}}\Big{)}$ (D.46)
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\overline{\Delta}_{\eta
t}^{2}\|{\tilde{\delta}}_{t}\|_{2}^{2}\Big{(}d^{i_{2}/2-1}+O\Big{(}\frac{1}{d}\Big{)}\Big{)}$
(B.c. $n\gtrsim d^{3}(\log d)^{O(1)}$ and $i_{4}+i_{5}\leq 2$)
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\|{\tilde{\delta}}_{t}\|_{2}^{2}$
(B.c. $\overline{\Delta}_{\eta t}\leq\frac{1}{\sqrt{d}}$ and $i_{2}\leq 4$)

where we have $\overline{\Delta}_{\eta t}\leq\frac{1}{\sqrt{d}}$ because by
Lemma C.3, we have that 5.3 holds as long as $\eta t\leq T_{*,\epsilon}$. In
summary, we have shown that terms of the form Eq. D.38 contribute at most
$(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\|{\tilde{\delta}}_{t}\|_{2}^{2}$,
up to constant factors, to the concentration error between $S_{1}$ and
$M_{2}$.

##### Contribution of Eq. D.37 to Concentration Error

We expand Eq. D.37 by using $\tilde{u}_{t}={\tilde{\delta}}_{t}+\delta_{\eta
t}+\bar{u}_{\eta t}$, $\hat{u}_{\eta t}=\delta_{\eta t}+\bar{u}_{\eta t}$ and
$\tilde{u}_{t}^{\prime}={\tilde{\delta}}_{t}^{\prime}+\delta_{\eta
t}^{\prime}+\bar{u}_{\eta t}^{\prime}$. Thus, we can write Eq. D.37 as a
linear combination of terms of the form

$\displaystyle({\tilde{\delta}}_{t}\cdot
x)^{1+i_{1}}({\tilde{\delta}}_{t}^{\prime}\cdot x)^{1+i_{2}}(\delta_{\eta
t}\cdot x)^{i_{3}}(\delta_{\eta t}^{\prime}\cdot x)^{i_{4}}(\bar{u}_{\eta
t}\cdot x)^{i_{5}}(\bar{u}_{\eta t}^{\prime}\cdot x)^{i_{6}}$ (D.47)

where $i_{1}+i_{2}+i_{3}+i_{4}+i_{5}+i_{6}=6$ (since the degrees of each of
the monomials must be $8$) and $i_{3}\leq 3$ (since each of these terms
originates from $(\tilde{u}_{t}^{\prime}\cdot x)^{i_{3}}(\hat{u}_{\eta
t}^{\prime}\cdot x)^{i_{4}}(\tilde{u}_{t}\cdot
x)^{i_{2}}({\tilde{\delta}}_{t}\cdot x)({\tilde{\delta}}_{t}^{\prime}\cdot x)$
where $i_{2}\leq 3$). Using Lemma G.7, we obtain a concentration bound for Eq.
D.47:

$\displaystyle\Big{|}\frac{1}{n}\sum_{i=1}^{n}$
$\displaystyle({\tilde{\delta}}_{t}\cdot
x_{i})^{1+i_{1}}({\tilde{\delta}}_{t}^{\prime}\cdot
x_{i})^{1+i_{2}}(\delta_{\eta t}\cdot x_{i})^{i_{3}}(\delta_{\eta
t}^{\prime}\cdot x_{i})^{i_{4}}(\bar{u}_{\eta t}\cdot
x_{i})^{i_{5}}(\bar{u}_{\eta t}^{\prime}\cdot x_{i})^{i_{6}}$ (D.48)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}\Big{[}({\tilde{\delta}}_{t}\cdot
x)^{1+i_{1}}({\tilde{\delta}}_{t}^{\prime}\cdot x)^{1+i_{2}}(\delta_{\eta
t}\cdot x)^{i_{3}}(\delta_{\eta t}^{\prime}\cdot x)^{i_{4}}(\bar{u}_{\eta
t}\cdot x)^{i_{5}}(\bar{u}_{\eta t}^{\prime}\cdot x)^{i_{6}}\Big{]}\Big{|}$
(D.49) $\displaystyle\lesssim(\log
d)^{O(1)}\frac{\|{\tilde{\delta}}_{t}\|_{2}^{1+i_{1}}\|{\tilde{\delta}}_{t}^{\prime}\|_{2}^{1+i_{2}}\|\delta_{\eta
t}\|_{2}^{i_{3}}\|\delta_{\eta
t}^{\prime}\|_{2}^{i_{4}}}{d^{1+(i_{1}+i_{2}+i_{3}+i_{4}+i_{5}+i_{6})/2}}\Big{(}\sqrt{\frac{d}{n}}+\frac{d^{1+(i_{1}+i_{2}+i_{3}+i_{4})/2}}{n}+\frac{1}{d^{\Omega(\log
d)}}\Big{)}\,.$ (D.50)

As discussed in the previous case, after we consider the coefficients of
$\sigma(t)$ and $\sigma^{\prime}(t)$, we find that the term in Eq. D.47
contributes

$\displaystyle(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})(\log
d)^{O(1)}\|{\tilde{\delta}}_{t}\|_{2}^{1+i_{1}}\|{\tilde{\delta}}_{t}^{\prime}\|_{2}^{1+i_{2}}\|\delta_{\eta
t}\|_{2}^{i_{3}}\|\delta_{\eta
t}^{\prime}\|_{2}^{i_{4}}\Big{(}\sqrt{\frac{d}{n}}+\frac{d^{1+(i_{1}+i_{2}+i_{3}+i_{4})/2}}{n}+\frac{1}{d^{\Omega(\log
d)}}\Big{)}\,.$ (D.51)

Now, suppose $i_{5}+i_{6}\geq 2$. Then, $i_{1}+i_{2}+i_{3}+i_{4}\leq 4$,
meaning the contribution to the concentration error is at most

$\displaystyle(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\|{\tilde{\delta}}_{t}\|_{2}\|{\tilde{\delta}}_{t}^{\prime}\|_{2}$
$\displaystyle\leq(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}$
(D.52)

using the fact that $n\gtrsim d^{3}(\log d)^{C}$ for a sufficiently large
constant $C$, and $\|{\tilde{\delta}}_{t}\|_{2}\lesssim 1$ and $\|\delta_{\eta
t}\|_{2}\lesssim 1$. On the other hand, if $i_{5}+i_{6}\leq 1$, then
$i_{1}+i_{2}+i_{3}+i_{4}\geq 5$, and since $i_{3}\leq 3$, this implies that
$i_{1}+i_{2}+i_{4}\geq 2$. In this case, the bound is at most

$\displaystyle(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})$
$\displaystyle(\log
d)^{O(1)}\|{\tilde{\delta}}_{t}\|_{2}^{1+i_{1}}\|{\tilde{\delta}}_{t}^{\prime}\|_{2}^{1+i_{2}}\|\delta_{\eta
t}\|_{2}^{i_{3}}\|\delta_{\eta
t}^{\prime}\|_{2}^{i_{4}}\Big{(}\sqrt{\frac{d}{n}}+\frac{d^{1+(i_{1}+i_{2}+i_{3}+i_{4})/2}}{n}+\frac{1}{d^{\Omega(\log
d)}}\Big{)}$ (D.53)
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\|{\tilde{\delta}}_{t}\|_{2}^{1+i_{1}}\|{\tilde{\delta}}_{t}^{\prime}\|_{2}^{1+i_{2}}\|\delta_{\eta
t}\|_{2}^{i_{3}}\|\delta_{\eta t}^{\prime}\|_{2}^{i_{4}}d$ (B.c.
$i_{1}+i_{2}+i_{3}+i_{4}\leq 6$ and $n\gtrsim d^{3}(\log d)^{C}$)
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\cdot\frac{1}{d^{(i_{1}+i_{2})/2}}\|\delta_{\eta
t}^{\prime}\|_{2}^{i_{4}}d\,.$ (B.c.
$\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}\leq\frac{1}{\sqrt{d}}$ and
$\|\delta_{\eta t}\|_{2}\lesssim 1$)

Thus, if $i_{1}+i_{2}\geq 2$, then the contribution of this term to the
overall concentration error is at most
$(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}$.
On the other hand, if $i_{4}=1$, then we can take the average of
$\|\delta_{\eta t}^{\prime}\|_{2}$ across $\chi$, and by Lemma C.3, we have
that 5.3 holds for $\eta t\leq T_{*,\epsilon}$, meaning that
$\operatorname*{\mathbb{E}}_{\chi}\|\delta_{\eta
t}^{\prime}\|_{2}\leq\overline{\Delta}_{\eta t}\leq\frac{1}{\sqrt{d}}$. In
this case, the contribution of this term to the overall concentration error is
at most
$(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\cdot\frac{1}{d^{(i_{1}+i_{2}+i_{4})/2}}d=(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}$.
Finally, when $i_{4}\geq 2$, we can take the average of $\|\delta_{\eta
t}^{\prime}\|_{2}^{2}$ over $\chi$ — we have
$\operatorname*{\mathbb{E}}_{\chi}\|\delta_{\eta
t}^{\prime}\|_{2}^{2}\leq\frac{1}{d}$, and therefore the contribution of this
term to the overall concentration error is at most

$\displaystyle(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\cdot\frac{1}{d^{1+(i_{1}+i_{2})/2}}d\leq(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\,.$
(D.54)

In all cases, the contribution of Eq. D.37 to the overall concentration error
between $S_{1}$ and $M_{1}$ is at most

$\displaystyle(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\,.$
(D.55)

##### Overall Concentration Error

In summary, the overall concentration error between $S_{1}$ and $M_{1}$ is
that of $G(x)$. We have expanded $G(x)$ into various monomials of dot products
involving $x$, and shown that each monomial contributes at most
$(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}$
to the concentration error. Thus, with high probability,

$\displaystyle|M_{1}-S_{1}|$
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\,.$
(D.56)

In order to bound $|M_{2}-S_{2}|$, an almost identical, but simpler, argument
can be used, with $y(x)$ in the place of $f_{{\tilde{\rho}}_{t}}(x)$ or
$f_{{\hat{\rho}}_{\eta t}}(x)$. In the modified argument,
$\tilde{u}_{t}^{\prime}$, $\hat{u}_{\eta t}^{\prime}$ and $\bar{u}_{\eta
t}^{\prime}$ will all be replaced with $e_{1}$. Thus, in the analysis of Eq.
D.40, we can replace $\bar{u}_{\eta t}^{\prime}$ with $e_{1}$ and assume that
$i_{2}=0$ (since otherwise this term becomes $0$ due to the $\delta_{\eta
t}^{\prime}\cdot x$ factor) — we can then proceed similarly to the subcase
where $i_{2}\leq 1$ in the analysis of Eq. D.40. Additionally, the term
analogous to Eq. D.47 does not arise in the case where
$f_{{\tilde{\rho}}_{t}}(x)$ and $f_{{\hat{\rho}}_{\eta t}}(x)$ are replaced by
$y(x)$, since $\tilde{u}_{t}^{\prime}$ and $\hat{u}_{\eta t}^{\prime}$ are
both replaced by $e_{1}$, so the corresponding term is $0$. We also note that
the Legendre coefficients of $y(x)$ have absolute values which are less than
those of $\sigma$. Thus, we have

$\displaystyle|M_{1}-S_{1}|+|M_{2}-S_{2}|\leq(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\,.$
(D.57)

##### Bounding the Expectation

To complete the proof, it suffices to bound $|M_{1}-M_{2}|$. We have that

$\displaystyle M_{1}-M_{2}$
$\displaystyle=\nabla_{\tilde{u}_{t}}L({\tilde{\rho}}_{t})\cdot{\tilde{\delta}}_{t}-\nabla_{\hat{u}_{\eta
t}}L({\hat{\rho}}_{\eta t})\cdot{\tilde{\delta}}_{t}$ (D.58)

and by Lemma D.1, we have

$\displaystyle|M_{1}-M_{2}|$
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\Big{(}\operatorname*{\mathbb{E}}_{(\tilde{u}_{t}^{\prime},\hat{u}_{\eta
t}^{\prime})\sim({\tilde{\rho}}_{t},{\hat{\rho}}_{\eta
t})}\Big{[}\|\tilde{u}_{t}^{\prime}-\hat{u}_{\eta
t}^{\prime}\|_{2}^{2}\Big{]}^{1/2}+\|\tilde{u}_{t}-\hat{u}_{\eta
t}\|_{2}\Big{)}\|{\tilde{\delta}}_{t}\|_{2}$ (D.59)
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}$
(D.60)

Combining this with our bound on $|M_{1}-S_{1}|+|M_{2}-S_{2}|$, we find that

$\displaystyle|({\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t})-{\textup{grad}}_{\hat{u}_{\eta
t}}\widehat{L}({\hat{\rho}}_{\eta t}))\cdot{\tilde{\delta}}_{t}|$
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}$
(D.61)

as desired. ∎

######  Lemma D.3.

Suppose we are in the setting of Theorem 3.5. Suppose $s,t\geq 0$. Then,

$\displaystyle\|{\textup{grad}}_{\hat{u}_{t}}\widehat{L}({\hat{\rho}}_{t})-{\textup{grad}}_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s})\|_{2}\leq(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{4}\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}$
(D.62)

###### Proof.

We have

$\displaystyle\|{\textup{grad}}_{\hat{u}_{t}}\widehat{L}({\hat{\rho}}_{t})$
$\displaystyle-{\textup{grad}}_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s})\|_{2}$
(D.63)
$\displaystyle=\|(I-\hat{u}_{t}\hat{u}_{t}^{\top})\nabla_{\hat{u}_{t}}\widehat{L}({\hat{\rho}}_{t})-(I-\hat{u}_{s}\hat{u}_{s}^{\top})\nabla_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s})\|_{2}$
(D.64)
$\displaystyle=\Big{\|}(I-\hat{u}_{t}\hat{u}_{t}^{\top})\cdot\frac{1}{n}\sum_{i=1}^{n}(f_{{\hat{\rho}}_{t}}(x_{i})-y(x_{i}))\sigma^{\prime}(\hat{u}_{t}^{\top}x_{i})x_{i}$
(D.65)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-(I-\hat{u}_{s}\hat{u}_{s}^{\top})\cdot\frac{1}{n}\sum_{i=1}^{n}(f_{{\hat{\rho}}_{s}}(x_{i})-y(x_{i}))\sigma^{\prime}(\hat{u}_{s}^{\top}x_{i})x_{i}\Big{\|}_{2}$
(D.66)
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\|(f_{{\hat{\rho}}_{t}}(x_{i})-y(x_{i}))\sigma^{\prime}(\hat{u}_{t}^{\top}x_{i})(I-\hat{u}_{t}\hat{u}_{t}^{\top})x_{i}-(f_{{\hat{\rho}}_{s}}(x_{i})-y(x_{i}))\sigma^{\prime}(\hat{u}_{s}^{\top}x_{i})(I-\hat{u}_{s}\hat{u}_{s}^{\top})x_{i}\|_{2}\,.$
(D.67)

We bound the right-hand side by several applications of the triangle
inequality. First, observe that for any $x\in\mathbb{S}^{d-1}$, we have

$\displaystyle|f_{{\hat{\rho}}_{t}}(x)-f_{{\hat{\rho}}_{s}}(x)|$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}|\sigma(\hat{u}_{t}(\chi_{i})\cdot
x)-\sigma(\hat{u}_{s}(\chi_{i})\cdot x)|$ (D.68)
$\displaystyle\lesssim\frac{1}{m}\sum_{j=1}^{m}(|\hat{\sigma}_{2,d}|\sqrt{N_{2,d}}+|\hat{\sigma}_{4,d}|\sqrt{N_{4,d}})|\hat{u}_{t}(\chi_{i})\cdot
x-\hat{u}_{s}(\chi_{i})\cdot x|$ (By Lemma C.12)
$\displaystyle\lesssim\frac{(|\hat{\sigma}_{2,d}|\sqrt{N_{2,d}}+|\hat{\sigma}_{4,d}|\sqrt{N_{4,d}})}{m}\sum_{j=1}^{m}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}$
(D.69)
$\displaystyle\lesssim(|\hat{\sigma}_{2,d}|\sqrt{N_{2,d}}+|\hat{\sigma}_{4,d}|\sqrt{N_{4,d}})\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}\,.$
(D.70)

Additionally, for $\hat{u}_{t}$ and $\hat{u}_{s}$ with the same initialization
$\chi$, we have

$\displaystyle|\sigma^{\prime}(\hat{u}_{t}^{\top}x)-\sigma^{\prime}(\hat{u}_{s}^{\top}x)|$
$\displaystyle\lesssim(|\hat{\sigma}_{2,d}|\sqrt{N_{2,d}}+|\hat{\sigma}_{4,d}|\sqrt{N_{4,d}})\cdot|\hat{u}_{t}^{\top}x-\hat{u}_{s}^{\top}x|$
(By Lemma C.12)
$\displaystyle\lesssim(|\hat{\sigma}_{2,d}|\sqrt{N_{2,d}}+|\hat{\sigma}_{4,d}|\sqrt{N_{4,d}})\|\hat{u}_{t}-\hat{u}_{s}\|_{2}\,.$
(D.71)
$\displaystyle\lesssim(|\hat{\sigma}_{2,d}|\sqrt{N_{2,d}}+|\hat{\sigma}_{4,d}|\sqrt{N_{4,d}})\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}\,.$
(D.72)

Also, for $\hat{u}_{t}$ and $\hat{u}_{s}$ with the same initialization $\chi$,
we have

$\displaystyle\|(I-\hat{u}_{t}\hat{u}_{t}^{\top})x_{i}-(I-\hat{u}_{s}\hat{u}_{s}^{\top})x_{i}\|_{2}$
$\displaystyle=\|(\hat{u}_{t}\cdot x_{i})\hat{u}_{t}-(\hat{u}_{s}\cdot
x_{i})\hat{u}_{s}\|_{2}$ (D.73) $\displaystyle\leq\|(\hat{u}_{t}\cdot
x_{i}-\hat{u}_{s}\cdot x_{i})\hat{u}_{t}\|_{2}+|\hat{u}_{s}\cdot
x_{i}|\|\hat{u}_{t}-\hat{u}_{s}\|_{2}$ (D.74)
$\displaystyle\lesssim\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}\,.$
(D.75)

Finally, for $x\in\mathbb{S}^{d-1}$ and any distribution $\rho$ on
$\mathbb{S}^{d-1}$, we have

$\displaystyle|f_{\rho}(x)-y(x)|$
$\displaystyle\lesssim|\hat{\sigma}_{2,d}|\sqrt{N_{2,d}}+|\hat{\sigma}_{4,d}|\sqrt{N_{4,d}}$
(D.76)

since we can bound $|f_{\rho}(x)|$ using Lemma C.12, and because (ignoring
$\hat{h}_{0,d}$ since it is equal to $\hat{\sigma}_{0,d}$)
$y(x)=\gamma_{2}\hat{\sigma}_{2,d}{P_{2,d}}+\gamma_{4}\hat{\sigma}_{4,d}{P_{4,d}}$,
and using 3.2.

Thus, we can simplify the right-hand side of Eq. D.67 using the triangle
inequality, and combining Eq. D.70, Eq. D.72, Eq. D.75 and Eq. D.76:

$\displaystyle\|(f_{{\hat{\rho}}_{t}}(x_{i})-y(x_{i}))$
$\displaystyle\sigma^{\prime}(\hat{u}_{t}^{\top}x_{i})(I-\hat{u}_{t}\hat{u}_{t}^{\top})x_{i}-(f_{{\hat{\rho}}_{s}}(x_{i})-y(x_{i}))\sigma^{\prime}(\hat{u}_{s}^{\top}x_{i})(I-\hat{u}_{s}\hat{u}_{s}^{\top})x_{i}\|_{2}$
(D.77)
$\displaystyle\leq|f_{{\hat{\rho}}_{t}}(x_{i})-f_{{\hat{\rho}}_{s}}(x_{i})|\|\sigma^{\prime}(\hat{u}_{t}^{\top}x_{i})(I-\hat{u}_{t}\hat{u}_{t}^{\top})x_{i}\|_{2}$
(D.78)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+|f_{{\hat{\rho}}_{s}}(x_{i})-y(x_{i})||\sigma^{\prime}(\hat{u}_{t}^{\top}x_{i})-\sigma^{\prime}(\hat{u}_{s}^{\top}x_{i})|\|(I-\hat{u}_{t}\hat{u}_{t}^{\top})x_{i}\|_{2}$
(D.79)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+|f_{{\hat{\rho}}_{s}}(x_{i})-y(x_{i})||\sigma^{\prime}(\hat{u}_{s}^{\top}x_{i})|\|(I-\hat{u}_{t}\hat{u}_{t}^{\top})x_{i}-(I-\hat{u}_{s}\hat{u}_{s}^{\top})x_{i}\|_{2}$
(D.80)
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}N_{2,d}+\hat{\sigma}_{4,d}^{2}N_{4,d})\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}$
(D.81)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+|f_{{\hat{\rho}}_{s}}(x_{i})-y(x_{i})||\sigma^{\prime}(\hat{u}_{t}^{\top}x_{i})-\sigma^{\prime}(\hat{u}_{s}^{\top}x_{i})|\|(I-\hat{u}_{t}\hat{u}_{t}^{\top})x_{i}\|_{2}$
(D.82)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+|f_{{\hat{\rho}}_{s}}(x_{i})-y(x_{i})||\sigma^{\prime}(\hat{u}_{s}^{\top}x_{i})|\|(I-\hat{u}_{t}\hat{u}_{t}^{\top})x_{i}-(I-\hat{u}_{s}\hat{u}_{s}^{\top})x_{i}\|_{2}$
(By Eq. D.70, bounding $|\sigma^{\prime}(\hat{u}_{t}^{\top}x_{i})|$ by Lemma
C.12)
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}N_{2,d}+\hat{\sigma}_{4,d}^{2}N_{4,d})\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}$
(D.83)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+(\hat{\sigma}_{2,d}^{2}N_{2,d}+\hat{\sigma}_{4,d}^{2}N_{4,d})\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}$
(D.84)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+|f_{{\hat{\rho}}_{s}}(x_{i})-y(x_{i})||\sigma^{\prime}(\hat{u}_{s}^{\top}x_{i})|\|(I-\hat{u}_{t}\hat{u}_{t}^{\top})x_{i}-(I-\hat{u}_{s}\hat{u}_{s}^{\top})x_{i}\|_{2}$
(By Eq. D.76 and Eq. D.72)
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}N_{2,d}+\hat{\sigma}_{4,d}^{2}N_{4,d})\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}$
(D.85)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+(\hat{\sigma}_{2,d}^{2}N_{2,d}+\hat{\sigma}_{4,d}^{2}N_{4,d})\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}$
(D.86)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+(\hat{\sigma}_{2,d}^{2}N_{2,d}+\hat{\sigma}_{4,d}^{2}N_{4,d})\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}$
(By Eq. D.75, Eq. D.76 and Lemma C.12)
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}N_{2,d}+\hat{\sigma}_{4,d}^{2}N_{4,d})\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}\,.$
(D.87)

Therefore, Eq. D.67 gives

$\displaystyle\|{\textup{grad}}_{\hat{u}_{t}}\widehat{L}({\hat{\rho}}_{t})-{\textup{grad}}_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s})\|_{2}$
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}N_{2,d}+\hat{\sigma}_{4,d}^{2}N_{4,d})\cdot\max_{i\in[m]}\|\hat{u}_{t}(\chi_{i})-\hat{u}_{s}(\chi_{i})\|_{2}$
(D.88)

as desired. ∎

###### Proof of Theorem 3.5.

To show that projected gradient descent achieves low population loss, we show
that it does not diverge far from projected gradient descent. Suppose
${\hat{\rho}}_{0}$ and ${\tilde{\rho}}_{0}$ are both equal to
$\textup{unif}(\chi_{1},\ldots,\chi_{m}\\})$. Then, by induction over $t$, we
bound the difference between $\tilde{u}_{t}(\chi)$ and $\hat{u}_{\eta
t}(\chi)$ for all $\chi\in\\{\chi_{1},\ldots,\chi_{m}\\}$. At $t=0$, we have
$\tilde{u}_{0}(\chi)=\hat{u}_{0}(\chi)$. Let $t$ be a nonnegative integer, and
assume that for all $s\leq t$ we have
$\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}\leq\frac{1}{\sqrt{d}}$.

By the definition of projected gradient descent, we have

$\displaystyle\tilde{u}_{t+1}(\chi)$
$\displaystyle=\frac{\tilde{u}_{t}(\chi)-\eta\cdot{\textup{grad}}_{\tilde{u}_{t}(\chi)}\widehat{L}({\tilde{\rho}}_{t})}{\|\tilde{u}_{t}(\chi)-\eta\cdot{\textup{grad}}_{\tilde{u}_{t}(\chi)}\widehat{L}({\tilde{\rho}}_{t})\|_{2}}\,.$
(D.89)

Note that
$\|\tilde{u}_{t}-\eta\cdot{\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t})\|_{2}\geq\|\tilde{u}_{t}\|_{2}$,
since ${\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t})$ is
orthogonal to $\tilde{u}_{t}$. Thus, letting $\Pi$ denote the projection onto
the $\ell_{2}$ unit ball, we have

$\displaystyle\|\tilde{u}_{t+1}-\hat{u}_{\eta(t+1)}\|_{2}=\|\Pi(\tilde{u}_{t}-\eta\cdot{\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t}))-\Pi(\hat{u}_{\eta(t+1)})\|_{2}\leq\|\tilde{u}_{t}-\eta\cdot{\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t})-\hat{u}_{\eta(t+1)}\|_{2}\,.$
(D.90)

Also, we have

$\displaystyle\hat{u}_{\eta(t+1)}(\chi)$ $\displaystyle=\hat{u}_{\eta
t}(\chi)-\int_{\eta
t}^{\eta(t+1)}{\textup{grad}}_{\hat{u}_{s}(\chi)}\widehat{L}({\hat{\rho}}_{s})ds\,.$
(D.91)

Thus,

$\displaystyle\|\tilde{u}_{t}-\eta\cdot{\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t})-\hat{u}_{\eta(t+1)}\|_{2}^{2}$
$\displaystyle=\Big{\|}\tilde{u}_{t}-\eta\cdot{\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t})-\hat{u}_{\eta
t}+\int_{\eta
t}^{\eta(t+1)}{\textup{grad}}_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s})ds\Big{\|}_{2}^{2}$
(D.92) $\displaystyle=\|\tilde{u}_{t}-\hat{u}_{\eta
t}\|_{2}^{2}+\Big{\|}\eta\cdot{\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t})-\int_{\eta
t}^{\eta(t+1)}{\textup{grad}}_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s})ds\Big{\|}_{2}^{2}$
(D.93)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+2(\tilde{u}_{t}-\hat{u}_{\eta
t})\cdot\int_{\eta
t}^{\eta(t+1)}({\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t})-{\textup{grad}}_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s}))ds$
(D.94)
$\displaystyle=\|{\tilde{\delta}}_{t}\|_{2}^{2}+O\Big{(}\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}\Big{)}$
(D.95)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+2\eta{\tilde{\delta}}_{t}\cdot({\textup{grad}}_{\tilde{u}_{t}}\widehat{L}({\tilde{\rho}}_{t})-{\textup{grad}}_{\hat{u}_{\eta
t}}\widehat{L}({\hat{\rho}}_{\eta t}))$ (D.96)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+2{\tilde{\delta}}_{t}\cdot\int_{\eta
t}^{\eta(t+1)}({\textup{grad}}_{\hat{u}_{\eta
t}}\widehat{L}({\hat{\rho}}_{\eta
t})-{\textup{grad}}_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s})ds$ (By Lemma
C.14)
$\displaystyle\leq\|{\tilde{\delta}}_{t}\|_{2}^{2}+O\Big{(}\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}\Big{)}+O\Big{(}\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\Big{)}$
(D.97)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+2{\tilde{\delta}}_{t}\cdot\int_{\eta
t}^{\eta(t+1)}({\textup{grad}}_{\hat{u}_{\eta
t}}\widehat{L}({\hat{\rho}}_{\eta
t})-{\textup{grad}}_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s})ds$ (By Lemma
D.2)
$\displaystyle\leq\|{\tilde{\delta}}_{t}\|_{2}^{2}+O\Big{(}\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}\Big{)}+O\Big{(}\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\Big{)}$
(D.98)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+2\eta\|{\tilde{\delta}}_{t}\|_{2}\max_{s\in[\eta
t,\eta(t+1)]}\|{\textup{grad}}_{\hat{u}_{\eta
t}}\widehat{L}({\hat{\rho}}_{\eta
t})-{\textup{grad}}_{\hat{u}_{s}}\widehat{L}({\hat{\rho}}_{s})\|_{2}$ (D.99)
$\displaystyle\leq\|{\tilde{\delta}}_{t}\|_{2}^{2}+O\Big{(}\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}\Big{)}+O\Big{(}\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\Big{)}$
(D.100)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+2\eta\|{\tilde{\delta}}_{t}\|_{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{4}\max_{s\in[\eta
t,\eta(t+1)]}\max_{i\in[m]}\|\hat{u}_{s}(\chi_{i})-\hat{u}_{\eta
t}(\chi_{i})\|_{2}$ (By Lemma D.3)
$\displaystyle\leq\|{\tilde{\delta}}_{t}\|_{2}^{2}+O\Big{(}\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}\Big{)}+O\Big{(}\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\Big{)}$
(D.101)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+2\eta\|{\tilde{\delta}}_{t}\|_{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{4}\cdot\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{4}$
(By Lemma C.14)
$\displaystyle\leq\|{\tilde{\delta}}_{t}\|_{2}^{2}+O\Big{(}\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}\Big{)}+O\Big{(}\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\Big{)}\,.$
(D.102)

Thus, we have

$\displaystyle\max_{\chi}\|{\tilde{\delta}}_{t+1}(\chi)\|_{2}^{2}$
$\displaystyle\leq\Big{(}1+O\Big{(}\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\Big{)}\Big{)}\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}+O\Big{(}\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}\Big{)}$
(D.103)

which means that for some universal constant $C$,

$\displaystyle\max_{\chi}\|{\tilde{\delta}}_{t+1}(\chi)\|_{2}^{2}$
$\displaystyle\lesssim\sum_{i=0}^{t}\Big{(}1+C\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\Big{)}^{i}\cdot\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}$
(D.104)
$\displaystyle\lesssim\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}\cdot\frac{\Big{(}1+C\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\Big{)}^{t+1}-1}{\Big{(}1+C\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\Big{)}-1}$
(D.105)
$\displaystyle\lesssim\eta^{2}(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})^{2}d^{8}\cdot\frac{\Big{(}1+C\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\Big{)}^{t+1}-1}{C\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})}$
(D.106)
$\displaystyle\lesssim\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{8}\cdot\Big{(}1+C\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\Big{)}^{t+1}$
(D.107)
$\displaystyle\lesssim\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{8}\cdot
e^{C\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})(t+1)}\,.$ (D.108)

Thus, as long as
$\eta=\frac{1}{(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{B}}$ for a
sufficiently large universal constant $B$, and choosing $\eta$ so that
$T_{*,\epsilon}$ is an integer multiple of $\eta$, we have
$\max_{\chi}\|{\tilde{\delta}}_{t+1}(\chi)\|_{2}\leq\frac{1}{\sqrt{d}}$,
because if $t\leq\frac{T_{*,\epsilon}}{\eta}$, then

$\displaystyle\max_{\chi}\|{\tilde{\delta}}_{t+1}(\chi)\|_{2}^{2}$
$\displaystyle\leq\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{8}\cdot
e^{C(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})T_{*,\epsilon}}$ (D.109)
$\displaystyle\leq\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{8}\cdot
e^{O(\log d)}$ (D.110)
$\displaystyle\leq\eta(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})d^{O(1)}\,.$
(D.111)

This completes the induction, and therefore for all
$t\leq\frac{T_{*,\epsilon}}{\eta}$, we have
$\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}\leq\frac{1}{\sqrt{d}}$.
Additionally, by Lemma C.16, and using the coupling between
${\tilde{\rho}}_{t}$ and ${\hat{\rho}}_{\eta t}$ which is the joint
distribution of $(\tilde{u}_{t}(\chi),\hat{u}_{\eta t}(\chi))$, we have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}[(f_{{\tilde{\rho}}_{t}}(x)-f_{{\hat{\rho}}_{\eta
t}}(x))^{2}]$
$\displaystyle\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\max_{\chi}\|{\tilde{\delta}}_{t}(\chi)\|_{2}^{2}\lesssim\frac{\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2}}{d}\lesssim(\hat{\sigma}_{2,d}^{2}+\hat{\sigma}_{4,d}^{2})\epsilon$
(D.112)

which completes the proof. ∎

##  Appendix E Missing Proofs in Section 3

###  E.1 Proof of Lemma 3.1

In this section, we prove sufficient and necessary conditions for $\gamma_{2}$
and $\gamma_{4}$ when the population loss is 0.

######  Proposition E.1 (Necessary condition).

Let $f_{\rho}(x)=\operatorname*{\mathbb{E}}_{u\sim\rho}[\sigma(u^{\top}x)]$ be
a (not necessarily symmetric nor rotational invariant) two-layer neural
network and $y(x)=h(e_{1}^{\top}x)$ the target function. Define
$\gamma_{k}=\frac{\hat{h}_{k,d}}{\hat{\sigma}_{k,d}},\forall k\geq 0$. Suppose
$\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}(f_{\rho}(x)-y(x))^{2}=0$
and $\hat{\sigma}_{2,d}\neq 0,\hat{\sigma}_{4,d}\neq 0$, we have

$\displaystyle\gamma_{2}^{2}\leq\gamma_{4}+O\left(\frac{1}{\sqrt{d}}\right),$
(E.1)
$\displaystyle\gamma_{4}\leq\gamma_{2}+O\left(\frac{1}{\sqrt{d}}\right),$
(E.2) $\displaystyle\gamma_{2}\leq 1.$ (E.3)

###### Proof.

Similar to the proof of Lemma 4.2, we have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}[(f_{\rho}(x)-h(x^{\top}e_{1}))^{2}]=\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}\Big{(}\operatorname*{\mathbb{E}}_{u\sim\rho}[\sigma(u^{\top}x)]-h(x^{\top}e_{1})\Big{)}^{2}$
(E.4) $\displaystyle=\;$
$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}\Big{(}\operatorname*{\mathbb{E}}_{u\sim\rho}\Big{[}\sum_{k=0}^{\infty}\hat{\sigma}_{k,d}\overline{P_{k,d}}(u^{\top}x)\Big{]}-\sum_{k=0}^{\infty}\hat{h}_{k,d}\overline{P}_{k,d}(x^{\top}e_{1})\Big{)}^{2}$
(E.5) $\displaystyle=\;$
$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}\Big{(}\sum_{k=0}^{\infty}\Big{(}\hat{\sigma}_{k,d}\operatorname*{\mathbb{E}}_{u\sim\rho}[\overline{P}_{k,d}(u^{\top}x)]-\hat{h}_{k,d}\overline{P}_{k,d}(x^{\top}e_{1})\Big{)}\Big{)}^{2}.$
(E.6)

Continuing the equation by invoking Lemma A.5, we get

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}\Big{(}\sum_{k=0}^{\infty}\Big{(}\hat{\sigma}_{k,d}\operatorname*{\mathbb{E}}_{u\sim\rho}[\overline{P}_{k,d}(u^{\top}x)]-\hat{h}_{k,d}\overline{P}_{k,d}(x^{\top}e_{1})\Big{)}\Big{)}^{2}$
(E.7) $\displaystyle=\;$
$\displaystyle\sum_{k=0}^{\infty}\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}\Big{(}\hat{\sigma}_{k,d}\operatorname*{\mathbb{E}}_{u\sim\rho}[\overline{P}_{k,d}(u^{\top}x)]-\hat{h}_{k,d}\overline{P}_{k,d}(x^{\top}e_{1})\Big{)}^{2}$
(E.8) $\displaystyle=\;$
$\displaystyle\sum_{k=0}^{\infty}\hat{\sigma}_{k,d}^{2}\Big{(}\operatorname*{\mathbb{E}}_{u,u^{\prime}\sim\rho}[P_{k,d}(u^{\top}u^{\prime})-2\gamma_{k}P_{k,d}(u^{\top}e_{1})+\gamma_{k}^{2}P_{k,d}(e_{1}^{\top}e_{1}])\Big{)}^{2}.$
(E.9)

Therefore,
$\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}[(f_{\rho}(x)-h(x^{\top}e_{1}))^{2}]=0$
implies that

$\displaystyle\operatorname*{\mathbb{E}}_{u,u^{\prime}\sim\rho}[P_{2,d}(u^{\top}u^{\prime})-2\gamma_{2}P_{2,d}(u^{\top}e_{1})+\gamma_{2}^{2}P_{2,d}(e_{1}^{\top}e_{1})]=0,$
(E.10)
$\displaystyle\operatorname*{\mathbb{E}}_{u,u^{\prime}\sim\rho}[P_{4,d}(u^{\top}u^{\prime})-2\gamma_{4}P_{4,d}(u^{\top}e_{1})+\gamma_{4}^{2}P_{4,d}(e_{1}^{\top}e_{1})]=0.$
(E.11)

First we prove Eq. (E.3). By Lemma A.6, there is a feature mapping
$\phi:\mathbb{S}^{d-1}\to\mathbb{R}^{N_{2,d}}$ such that for every
$u,v\in\mathbb{S}^{d-1}$,

$\displaystyle\left<\phi(u),\phi(v)\right>=N_{2,d}P_{2,d}(u^{\top}v),$ (E.12)
$\displaystyle\|\phi_{u}\|_{2}^{2}=N_{2,d}.$ (E.13)

Rewrite Eq. (E.10) using $\phi_{2}$ we get

$\displaystyle\|\operatorname*{\mathbb{E}}_{u\sim\rho}[\phi_{2}(u)]-\gamma_{2}\phi_{2}(e_{1})\|_{2}^{2}=0.$
(E.14)

Or equivalently,

$\displaystyle\gamma_{2}\phi_{2}(e_{1})=\operatorname*{\mathbb{E}}_{u\sim\rho}[\phi_{2}(u)]$
(E.15)

As a result,

$\displaystyle\gamma_{2}=\left\lVert\frac{\phi_{2}(e_{1})}{\sqrt{N_{k,d}}}\right\rVert_{2}=\left\lVert\frac{\operatorname*{\mathbb{E}}_{u\sim\rho}[\phi_{2}(u)]}{\sqrt{N_{k,d}}}\right\rVert_{2}\leq\frac{\operatorname*{\mathbb{E}}_{u\sim\rho}[\left\lVert\phi_{2}(u)]\right\rVert_{2}}{\sqrt{N_{2,d}}}=1.$
(E.16)

Similarly, we also have $\gamma_{4}\leq 1.$

Now we prove Eq. (E.1). Recall that

$\displaystyle P_{2,d}(t)$ $\displaystyle=\frac{d}{d-1}t^{2}-\frac{1}{d-1},$
(E.17) $\displaystyle P_{4,d}(t)$
$\displaystyle=\frac{(d+2)(d+4)}{d^{2}-1}t^{4}-\frac{6d+12}{d^{2}-1}t^{2}+\frac{3}{d^{2}-1}.$
(E.18)

Combining Eq. (E.10) and Eq. (E.17) we have

$\displaystyle
0=\frac{d-1}{d}\operatorname*{\mathbb{E}}_{u,u^{\prime}\sim\rho}[P_{2,d}(u^{\top}u^{\prime})-2\gamma_{2}P_{2,d}(u^{\top}e_{1})+\gamma_{2}^{2}P_{2,d}(e_{1}^{\top}e_{1})]$
(E.19) $\displaystyle=$
$\displaystyle\;\operatorname*{\mathbb{E}}_{u,u^{\prime}\sim\rho}[(u^{\top}u^{\prime})^{2}-2\gamma_{2}(u^{\top}e_{1})^{2}+\gamma_{2}^{2}(e_{1}^{\top}e_{1})^{2}]-\frac{1}{d}(1-2\gamma_{2}+\gamma_{2}^{2})$
(E.20) $\displaystyle=$
$\displaystyle\;\|\operatorname*{\mathbb{E}}_{u\sim\rho}[u^{\otimes
2}-\gamma_{2}e_{1}^{\otimes 2}]\|_{F}^{2}-\frac{1}{d}(1-\gamma_{2})^{2}.$
(E.21)

Consequently,

$\displaystyle\|\operatorname*{\mathbb{E}}_{u\sim\rho}[u^{\otimes
2}-\gamma_{2}e_{1}^{\otimes 2}]\|_{F}^{2}=\frac{1}{d}(1-\gamma_{2})^{2}.$
(E.22)

Similarly, combining Eq. (E.11) and Eq. (E.18) we get

$\displaystyle
0=\frac{d^{2}-1}{(d+2)(d+4)}\operatorname*{\mathbb{E}}_{u,u^{\prime}\sim\rho}[P_{4,d}(u^{\top}u^{\prime})-4\gamma_{4}P_{4,d}(u^{\top}e_{1})+\gamma_{4}^{2}P_{4,d}(e_{1}^{\top}e_{1})]$
(E.23) $\displaystyle=$
$\displaystyle\;\operatorname*{\mathbb{E}}_{u,u^{\prime}\sim\rho}[(u^{\top}u^{\prime})^{4}-2\gamma_{4}(u^{\top}e_{1})^{4}+\gamma_{4}^{2}(e_{1}^{\top}e_{1})^{4}]+\frac{3}{(d+2)(d+4)}(1-2\gamma_{4}+\gamma_{4}^{2})$
(E.24)
$\displaystyle-\frac{6d+12}{(d+2)(d+4)}\operatorname*{\mathbb{E}}_{u,u^{\prime}\sim\rho}[(u^{\top}u^{\prime})^{2}-2\gamma_{4}(u^{\top}e_{1})^{2}+\gamma_{4}^{2}(e_{1}^{\top}e_{1})^{2}].$
(E.25)

Consequently,

$\displaystyle\|\operatorname*{\mathbb{E}}_{u\sim\rho}[u^{\otimes
4}-\gamma_{4}e_{1}^{\otimes
4}]\|_{F}^{2}\leq\frac{3}{(d+2)(d+4)}(1-\gamma_{4})^{2}+\frac{6d+12}{(d+2)(d+4)}(\gamma_{4}+1)^{2}.$
(E.26)

Now for any fixed $\xi\in\mathbb{S}^{d-1}$, our key observation is that by
Jensen’s inequality,

$\displaystyle\operatorname*{\mathbb{E}}_{u\sim\rho}[(u^{\top}\xi)^{2}]^{2}\leq\operatorname*{\mathbb{E}}_{u\sim\rho}[(u^{\top}\xi)^{4}].$
(E.27)

On the one hand, by Eq. (E.22) we have

$\displaystyle\left|\operatorname*{\mathbb{E}}_{u\sim\rho}[(u^{\top}\xi)^{2}]-\gamma_{2}(e_{1}^{\top}\xi)^{2}\right|=\left|\operatorname*{\mathbb{E}}_{u\sim\rho}[\left<u^{\otimes
2}-\gamma_{2}e_{1}^{\otimes 2},\xi^{\otimes 2}\right>]\right|$ (E.28)
$\displaystyle\leq\;$
$\displaystyle\|\operatorname*{\mathbb{E}}_{u\sim\rho}[u^{\otimes
2}-\gamma_{2}e_{1}^{\otimes 2}]\|_{F}\|\xi^{\otimes
2}\|_{F}=\sqrt{\frac{(1-\gamma_{2})^{2}}{d}}.$ (E.29)

On the other hand, by Eq. (E.26) we have

$\displaystyle\left|\operatorname*{\mathbb{E}}_{u\sim\rho}[(u^{\top}\xi)^{4}]-\gamma_{4}(e_{1}^{\top}\xi)^{4}\right|=\left|\operatorname*{\mathbb{E}}_{u\sim\rho}[\left<u^{\otimes
4}-\gamma_{4}e_{1}^{\otimes 4},\xi^{\otimes 4}\right>]\right|$ (E.30)
$\displaystyle\leq\;$
$\displaystyle\|\operatorname*{\mathbb{E}}_{u\sim\rho}[u^{\otimes
4}-\gamma_{4}e_{1}^{\otimes 4}]\|_{F}\|\xi^{\otimes 4}\|_{F}\leq
2\sqrt{\frac{6d+12}{(d+2)(d+4)}}(|\gamma_{4}+1|+|\gamma_{4}-1|).$ (E.31)

Finally, combining Eqs (E.27)-(E.31) and set $\xi=e_{1}$ we get

$\displaystyle\left(\gamma_{2}-\sqrt{\frac{(1-\gamma_{2})^{2}}{d}}\right)^{2}\leq\gamma_{4}+2\sqrt{\frac{6d+12}{(d+2)(d+4)}}(|\gamma_{4}+1|+|\gamma_{4}-1|).$
(E.32)

It follows directly that

$\displaystyle\gamma_{2}^{2}\leq\gamma_{4}+O\left(\frac{1}{\sqrt{d}}\right).$
(E.33)

Finally we prove Eq. (E.2). For any $\xi,u\in\mathbb{S}^{d-1}$ we have
$|u^{\top}\xi|\leq 1$. As a result,

$\displaystyle\operatorname*{\mathbb{E}}_{u\sim\rho}[(u^{\top}\xi)^{4}]\leq\operatorname*{\mathbb{E}}_{u\sim\rho}[(u^{\top}\xi)^{2}].$
(E.34)

Combining with Eq. (E.29) and Eq. (E.31) and setting $\xi=e_{1}$ we get

$\displaystyle\gamma_{4}\leq
O(1/\sqrt{d})+\operatorname*{\mathbb{E}}_{u\sim\rho}[(u^{\top}\xi)^{4}]\leq
O(1/\sqrt{d})+\operatorname*{\mathbb{E}}_{u\sim\rho}[(u^{\top}\xi)^{2}]\leq
O(1/\sqrt{d})+\gamma_{2}.$ (E.35)

∎

######  Proposition E.2 (Sufficient condition).

Let $f_{\rho}(x)=\operatorname*{\mathbb{E}}_{u\sim\rho}[\sigma(u^{\top}x)]$ be
a two-layer neural network and $y(x)=h(e_{1}^{\top}x)$ the target function.
Let $\gamma_{k}=\frac{\hat{h}_{k,d}}{\hat{\sigma}_{k,d}},\forall k\geq 0$.
Suppose $\hat{h}_{k,d}=0,\forall k\not\in\\{0,2,4\\}$,
$\hat{h}_{0,d}=\hat{\sigma}_{0,d}$, $\sigma$ is a degree-4 polynomial, and

$\displaystyle\gamma_{2}^{2}\leq\gamma_{4}-O\left(1/d\right),$ (E.36)
$\displaystyle\gamma_{4}\leq\gamma_{2}-O\left(1/d\right),$ (E.37)
$\displaystyle\gamma_{2}\leq 1-O\left(1/d\right).$ (E.38)

Then there exists a symmetric and rotational invariant neural network $\rho$
such that
$\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}(f_{\rho}(x)-y(x))^{2}=0$.

###### Proof.

Recall that by Lemma 4.2, for every symmetric and rotational invariant neural
network $\rho$ we have

$\displaystyle L(\rho)$
$\displaystyle=\frac{\hat{\sigma}_{2,d}^{2}}{2}\Big{(}\operatorname*{\mathbb{E}}_{u\sim\rho}[P_{2,d}(w)]-\gamma_{2}\Big{)}^{2}+\frac{\hat{\sigma}_{4,d}^{2}}{2}\Big{(}\operatorname*{\mathbb{E}}_{u\sim\rho}[P_{4,d}(w)]-\gamma_{4}\Big{)}^{2}$
(E.39)

where $u=(w,z)$, $w\in[-1,1]$, and $z\in\sqrt{1-w^{2}}\mathbb{S}^{d-2}.$
Therefore, we only need to show that there exists a one-dimensional
distribution $\mu$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu}[P_{2,d}(w)]=\gamma_{2},$
(E.40)
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu}[P_{4,d}(w)]=\gamma_{4}.$
(E.41)

Recall that

$\displaystyle P_{2,d}(t)$ $\displaystyle=\frac{d}{d-1}t^{2}-\frac{1}{d-1},$
(E.42) $\displaystyle P_{4,d}(t)$
$\displaystyle=\frac{(d+2)(d+4)}{d^{2}-1}t^{4}-\frac{6d+12}{d^{2}-1}t^{2}+\frac{3}{d^{2}-1}.$
(E.43)

Consequently, Eq. (E.40) and Eq. (E.41) is equivalent to

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu}[w^{2}]=\frac{d-1}{d}\gamma_{2}+\frac{1}{d},$
(E.44)
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu}[w^{4}]=\frac{d^{2}-1}{(d+2)(d+4)}\gamma_{4}+\frac{6d+12}{(d+2)(d+4)}\left(\frac{d-1}{d}\gamma_{2}+\frac{1}{d}\right)-\frac{3}{(d+2)(d+4)}.$
(E.45)

Let $\beta_{2}=\frac{d-1}{d}\gamma_{2}+\frac{1}{d}$ and
$\beta_{4}=\frac{d^{2}-1}{(d+2)(d+4)}\gamma_{4}+\frac{6d+12}{(d+2)(d+4)}\left(\frac{d-1}{d}\gamma_{2}+\frac{1}{d}\right)-\frac{3}{(d+2)(d+4)}$.
Then we have $|\beta_{2}-\gamma_{2}|\leq O(1/d)$ and
$|\beta_{4}-\gamma_{4}|\leq O(1/d).$ Rewriting Eqs. (E.36)-(E.38) using
$\beta_{2}$ and $\beta_{4}$, we have

$\displaystyle\beta_{2}^{2}\leq\beta_{4},$ (E.46)
$\displaystyle\beta_{4}\leq\beta_{2},$ (E.47) $\displaystyle\beta_{2}\leq 1.$
(E.48)

By Proposition G.14, there exists a distribution $\mu^{\star}$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu^{\star}}[w^{2}]=\beta_{2},$
(E.49)
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu^{\star}}[w^{4}]=\beta_{4}.$
(E.50)

Hence, by setting the marginal distribution of $w$ equal to $\mu^{\star}$, we
have

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu^{\star}}[P_{2,d}(w)]=\gamma_{2},\quad\operatorname*{\mathbb{E}}_{w\sim\mu^{\star}}[P_{4,d}(w)]=\gamma_{4},$
(E.51)

which proves the desired result. ∎

##  Appendix F Proofs for Sample Complexity Lower Bounds for Kernel Method

In this section, we present a sample complexity lower bound for kernel methods
with any inner product kernel. That is, the kernel
$K:\mathbb{S}^{d-1}\times\mathbb{S}^{d-1}\to\mathbb{R}$ can be written as
$K(x,z)=\kappa(x^{\top}z)$ for some one-dimensional function
$\kappa:[-1,1]\to\mathbb{R}$. Inner product kernels are rotational invariant
and do not specialize to any coordinate. In particular, NTK of two-layer
neural networks is an inner product kernel (e.g., Du et al. [2018], Wei et al.
[2019b]).

To prove Theorem 3.6, we only need to work on the degree-$k$ spherical
harmonics component of the target function and its estimation because, by the
orthogonality of spherical harmonics, any lower bound for the degree-$k$
components directly translates to the original setting. The following lemma
states the lower bound for general $k\geq 0$, while Theorem 3.6 only requires
the case $k=4.$

######  Lemma F.1.

Fixed any $k\geq 1$, let $g^{\star}(x)=\overline{P}_{k,d}(u^{\top}x)$ for some
fixed $u\in\mathbb{S}^{d-1}$. When $d$ is larger than a sufficiently large
universal constant and $n<d^{k}(8k)^{-(3k+1)}(\ln d)^{-(k+2)}$, with
probability at least $1/2$ over the randomness of $n$ i.i.d. data
$\\{x_{1},\cdots,x_{n}\\}$ drawn uniformly from $\mathbb{S}^{d-1}$, any
estimation $g$ of the form
$g(x)=\sum_{i=1}^{n}\beta_{i}\overline{P}_{k,d}(x^{\top}x_{i})$ must have a
constant error:

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}(g(x)-g(x)^{\star})^{2}\geq
3/4.$ (F.1)

Proof of Lemma F.1 is deferred to Appendix F.2, where our key observation is
that $\overline{P}_{k,d}(\left<x_{i},\cdot\right>)$ cannot correlate too much
with $g^{\star}$ when $x_{i}$ is uniformly randomly drawn from the unit
sphere. Indeed,
$\left<\overline{P}_{k,d}(\left<x_{i},\cdot\right>),g^{\star}\right>=P_{k,d}(x_{i}^{\top}u)$
concentrates within $\pm 1/N_{k,d}$ (Lemma A.7). Hence, we can upperbound
$\left<g,g^{\star}\right>=\sum_{i=1}^{n}\beta_{i}P_{k,d}(x_{i}^{\top}u)\lesssim\|\beta\|_{2}\sqrt{n/N_{k,d}}$.
However, we also have
$\|g\|_{2}^{2}=\sum_{i,j\in[n]}\beta_{i}\beta_{j}P_{k,d}(x_{i}^{\top}x_{j})\gtrsim\|\beta\|_{2}^{2}$
because the matrix $(P_{k,d}(x_{i}^{\top}x_{j}))_{i,j\in[n]}$ concentrates
around $I$ (Lemma F.3). Since $\|g-g^{\star}\|_{2}^{2}<3/4$ requires
$\left<g,g^{\star}\right>>\|g\|_{2}/2$, we must have $n\gtrsim N_{k,d}\approx
d^{-k}$.

###  F.1 Proof of Theorem 3.6

The following theorem states that for every $k\geq 0$, to achieve a constant
population error, we need at least $C_{k}d^{-k}(\ln d)^{-(k+2)}$ samples where
$C_{k}=(8k)^{-(3k+1)}$ is a constant that only depends on $k$. Hence, Theorem
3.6 is a direct corollary of Theorem F.2 by taking $k=4.$

######  Theorem F.2.

Let $y:\mathbb{S}^{d-1}\to\mathbb{R}$ be a function of the form
$y(x)=h(q_{\star}^{\top}x)$ where $q_{\star}\in\mathbb{S}^{d-1}$ is a fixed
vector and $h:[-1,1]\to\mathbb{R}$ is a one-dimensional function. Let
$K:\mathbb{S}^{d-1}\times\mathbb{S}^{d-1}\to\mathbb{R}$ be any inner product
kernel. When $d$ is larger than a universal constant and
$n<d^{k}(8k)^{-(3k+1)}(\ln d)^{-(k+2)}$, with probability at least $1/2$ over
the randomness of $n$ i.i.d. data points $\\{x_{i}\\}_{i=1}^{n}$, any
estimation $f$ of the form $f(x)=\sum_{i=1}^{n}\beta_{i}K(x_{i},x)$ must have
a significant error:

$\|y-f\|_{2}^{2}\geq\frac{3}{4}(\hat{h}_{k,d})^{2}.$

###### Proof of Theorem F.2.

In the following we first fix a degree $k\geq 1$. For every $l>0$, let
$\mathbb{Y}_{l,d}$ be the space of degree-$l$ spherical harmonics and
$\Pi_{l}$ the projection to $\mathbb{Y}_{l,d}$. By the orthogonality of
$\mathbb{Y}_{l,d}$, we have

$\displaystyle\|y-f\|_{2}^{2}=\sum_{l=0}^{\infty}\|\Pi_{l}(y-f)\|_{2}^{2}\geq\|\Pi_{k}(y-f)\|_{2}^{2}.$
(F.2)

By Atkinson and Han [2012, Section 2.3], the projection operator $\Pi_{k}$ is
given by

$\displaystyle(\Pi_{k}f)(x)=\sqrt{N_{k,d}}\operatorname*{\mathbb{E}}_{\xi\sim\mathbb{S}^{d-1}}[\overline{P}_{k,d}(x^{\top}\xi)f(\xi)].$
(F.3)

Consequently, we have
$(\Pi_{k}y)(x)=\sqrt{N_{k,d}}\operatorname*{\mathbb{E}}_{\xi\sim\mathbb{S}^{d-1}}[\overline{P}_{k,d}(x^{\top}\xi)h(q_{\star}^{\top}\xi)].$
Recall that

$\displaystyle\mu_{d}(t)\triangleq(1-t^{2})^{\frac{d-3}{2}}\frac{\Gamma(d/2)}{\Gamma((d-1)/2)}\frac{1}{\sqrt{\pi}}$
(F.4)

is the density of $u_{1}$ when $u=(u_{1},\cdots,u_{d})$ is drawn uniformly
from $\mathbb{S}^{d-1}$, and
$\hat{h}_{k,d}=\operatorname*{\mathbb{E}}_{t\sim\mu_{d}}[\overline{P}_{k,d}(t)h(t)].$
By Funk-Hecke formula (Theorem A.1) we get

$\displaystyle(\Pi_{k}y)(x)=\hat{h}_{k,d}\overline{P}_{k,d}(x^{\top}q_{\star}),\quad\forall
x\in\mathbb{S}^{d-1}.$ (F.5)

Similarly, we can write the inner product kernel $K$ as
$K(x,z)=\kappa(x^{\top}z)$. Define
$\hat{\kappa}_{k,d}=\operatorname*{\mathbb{E}}_{t\sim\mu_{d}}[\overline{P}_{k,d}(t)\kappa(t)].$
Then we have

$\displaystyle(\Pi_{k}f)(x)=\hat{\kappa}_{k,d}\sum_{i=1}^{n}\beta_{i}\overline{P}_{k,d}(x^{\top}x_{i}),\quad\forall
x\in\mathbb{S}^{d-1}.$ (F.6)

Now we apply Lemma F.1 to the function
$(\hat{h}_{k,d})^{-1}(\Pi_{k}y)=\overline{P}_{k,d}(\left<q_{\star},\cdot\right>)$.
As a result, with probability at least $1/2$ over the randomness of
$\\{x_{i}\\}_{i=1}^{n}$, for any function $f$ of the form
$f(\cdot)=\sum_{i=1}^{n}\beta_{i}K(x_{i},\cdot)$, we have
$\|(\hat{h}_{k,d})^{-1}\Pi_{4}(y-f)\|_{2}^{2}\geq 3/4,$ which implies
$\|y-f\|_{2}^{2}\geq\frac{3}{4}(\hat{h}_{k,d})^{2}.$ ∎

###  F.2 Proof of Lemma F.1

###### Proof of Lemma F.1.

First we prove that when $\|g^{\star}\|_{2}=1$, $\|g-g^{\star}\|_{2}^{2}<3/4$
implies $\left<g,g^{\star}\right>\geq\|g\|_{2}/2.$ To this end, by basic
algebra we get

$\displaystyle
3/4>\|g-g^{\star}\|_{2}^{2}=\|g\|_{2}^{2}+\|g^{\star}\|_{2}^{2}-2\left<g,g^{\star}\right>.$
(F.7)

Consequently,

$\displaystyle\left<g,g^{\star}\right>\geq\frac{1}{2}\left(\|g\|_{2}^{2}+\frac{1}{4}\right)\geq\frac{1}{2}\|g\|_{2},$
(F.8)

where the last inequality follows from AM-GM. In the following, we prove that
with probability at least $1/2$, Eq. (F.8) is impossible when
$n<d^{k}(8k)^{-(3k+1)}(\ln d)^{-(k+2)}$.

Recall that Lemma A.5 states that for every $x,z\in\mathbb{S}^{d-1}$ and
$k\geq 0$,

$\displaystyle\left<\overline{P}_{k,d}(\left<x,\cdot\right>),\overline{P}_{k,d}(\left<z,\cdot\right>)\right>=P_{k,d}(\left<x,z\right>).$
(F.9)

As a result,

$\displaystyle\|g\|_{2}^{2}=\sum_{i,j=1}^{n}\beta_{i}\beta_{j}\left<\overline{P}_{k,d}(\left<x_{i},\cdot\right>),\overline{P}_{k,d}(\left<x_{j},\cdot\right>)\right>=\sum_{i,j=1}^{n}\beta_{i}\beta_{j}P_{k,d}(\left<x_{i},x_{j}\right>).$
(F.10)

Invoking Lemma F.3, with probability at least $3/4$ over the randomness of
$\\{x_{i}\\}_{i\in[n]}$, we have

$\displaystyle\|g\|_{2}^{2}=\sum_{i,j=1}^{n}\beta_{i}\beta_{j}P_{k,d}(\left<x_{i},x_{j}\right>)\geq\frac{1}{2}\|\beta\|_{2}^{2}.$
(F.11)

For the LHS of Eq. (F.8),

$\displaystyle\left<g,g^{\star}\right>$
$\displaystyle=\sum_{i=1}^{n}\beta_{i}\left<\overline{P}_{k,d}(\left<x_{i},\cdot\right>),\overline{P}_{k,d}(\left<u,\cdot\right>)\right>=\sum_{i=1}^{n}\beta_{i}P_{k,d}(\left<x_{i},u\right>)$
(F.12)
$\displaystyle\leq\left(\sum_{i=1}^{n}\beta_{i}^{2}\right)^{1/2}\left(\sum_{i=1}^{n}P_{k,d}(\left<x_{i},u\right>)^{2}\right)^{1/2}=\|\beta\|_{2}\left(\sum_{i=1}^{n}P_{k,d}(\left<x_{i},u\right>)^{2}\right)^{1/2}.$
(F.13)

By Lemma A.7, when $n<d^{k}(8k)^{-(3k+1)}(\ln d)^{-(k+2)}$, with probability
at least $3/4$ we have

$\displaystyle\left<g,g^{\star}\right>\leq\|\beta\|_{2}\left(\sum_{i=1}^{n}P_{k,d}(\left<x_{i},u\right>)^{2}\right)^{1/2}\leq\|\beta\|_{2}\left(n\max_{i\in[n]}P_{k,d}(\left<x_{i},u\right>)^{2}\right)^{1/2}$
(F.14) $\displaystyle\leq\;$
$\displaystyle\|\beta\|_{2}\sqrt{\frac{n(32k\ln(dn))^{k}}{d^{k}}}\leq\|\beta\|_{2}\sqrt{\frac{1}{\ln
d}}.$ (F.15)

Combining Eq. (F.11) and Eq. (F.15), there exists a universal constant
$d_{0}>0$ such that when $d>d_{0}$, with probability at least $1/2$ over the
randomness of $\\{x_{1},\cdots,x_{n}\\}$,

$\displaystyle\left<g,g^{\star}\right><\|\beta\|_{2}/4\leq\|g\|_{2}/2.$ (F.16)

Recall that $\|g-g^{\star}\|_{2}^{2}<3/4$ implies
$\left<g,g^{\star}\right>\geq\|g\|_{2}/2$. Consequently, with probability at
least $1/2$, when $n<d^{k}(8k)^{-(3k+1)}(\ln d)^{-(k+2)}$ and $d>d_{0}$ we
have $\|g-g^{\star}\|_{2}^{2}\geq 3/4.$ ∎

######  Lemma F.3.

Let $x_{1},\cdots,x_{n}$ be i.i.d. random variables drawn uniformly from
$\mathbb{S}^{d-1}$, and $P_{k,d}$ the degree-$k$ Legendre polynomial. For any
fixed $k\geq 1$, define the matrix $M_{k}\in\mathbb{R}^{n\times n}$ where
$[M_{k}]_{i,j}=P_{k,d}(\left<x_{i},x_{j}\right>).$ There exists universal
constants $d_{0}$ such that, when $n<d^{k}(8k)^{-(3k+1)}(\ln d)^{-(k+2)}$ and
$d>d_{0}$, with probability at least $3/4$,

$\displaystyle\lambda_{\min}(M_{k})\geq 1/2.$ (F.17)

###### Proof.

In the following, we fix $k\geq 1$. First, we prove that

$\displaystyle\operatorname*{\mathbb{E}}[\lambda_{\min}(M_{k})]\geq 7/8.$
(F.18)

To this end, we invoke Theorem G.4 by constructing a matrix $A$ such that
$\frac{1}{N_{k,d}}A^{\top}A=M_{k}$.

By Lemma A.6, there exists a feature mapping
$\phi:\mathbb{S}^{d-1}\to\mathbb{R}^{N_{k,d}}$ such that for every
$u,v\in\mathbb{S}^{d-1}$

$\displaystyle\left<\phi(u),\phi(v)\right>=N_{k,d}P_{k,d}(u^{\top}v),$ (F.19)
$\displaystyle\|\phi(u)\|_{2}^{2}=N_{k,d},$ (F.20)
$\displaystyle\operatorname*{\mathbb{E}}_{u\sim\mathbb{S}^{d-1}}[\phi(u)\phi(u)^{\top}]=I.$
(F.21)

We set $A_{i}=\phi(x_{i}),\forall 1\leq i\leq n$. Consequently,

$\displaystyle\frac{1}{N_{k,d}}A^{\top}A=M_{k},$ (F.22)
$\displaystyle\|A_{i}\|_{2}^{2}=N_{k,d},$ (F.23)
$\displaystyle\operatorname*{\mathbb{E}}[A_{i}A_{i}^{\top}]=I.$ (F.24)

In the following, we upper bound the incoherence parameter $p$ defined in
Theorem G.4:

$\displaystyle p=\frac{1}{N_{k,d}}\operatorname*{\mathbb{E}}\left[\max_{i\leq
n}\sum_{j\in[n],j\neq i}\left<A_{i},A_{j}\right>^{2}\right].$ (F.25)

By Eq. (F.19) we get

$\displaystyle\frac{1}{N_{k,d}}\operatorname*{\mathbb{E}}\left[\max_{i\leq
n}\sum_{j\in[n],j\neq
i}\left<A_{i},A_{j}\right>^{2}\right]=N_{k,d}\operatorname*{\mathbb{E}}\left[\max_{i\leq
n}\sum_{j\in[n],j\neq i}P_{k,d}(\left<x_{i},x_{j}\right>)^{2}\right]$ (F.26)
$\displaystyle\leq\;$ $\displaystyle
nN_{k,d}\operatorname*{\mathbb{E}}\left[\max_{i\leq n}\max_{j\neq
i}P_{k,d}(\left<x_{i},x_{j}\right>)^{2}\right].$ (F.27)

Invoking Lemma A.7 we get

$\displaystyle N_{k,d}\operatorname*{\mathbb{E}}\left[\max_{i\leq
n}\max_{j\neq
i}P_{k,d}(\left<x_{i},x_{j}\right>)^{2}\right]\lesssim(32k\ln(dn))^{k}.$
(F.28)

It follows that $p\lesssim n(32k\ln(dn))^{k}$.

Now that we have established the conditions, by Theorem G.4 we have

$\displaystyle\operatorname*{\mathbb{E}}[\|M-I\|]\lesssim\sqrt{\frac{n(\ln
n)(32k\ln(dn))^{k}}{N_{k,d}}}.$ (F.29)

Note that $N_{k,d}\geq\binom{k+d-2}{k}\geq(d/k)^{k}$ when $k\geq 2$, and
clearly $N_{1,d}\geq d$. Hence, there exists a universal constant $d_{0}$ such
that, when $n<d^{k}(8k)^{-(3k+1)}(\ln d)^{-(k+2)}$.

$\displaystyle\frac{n(\ln
n)(32k\ln(dn))^{k}}{N_{k,d}}\leq\frac{n(8k)^{2k}\ln(dn)^{k+1}}{d^{k}}\leq\frac{n(8k)^{2k}\ln(d^{k+1})^{k+1}}{d^{k}}\leq\frac{1}{\ln
d}.$ (F.30)

Hence, there exists a universal constant $d_{0}$ such that when $d\geq d_{0}$,

$\displaystyle\operatorname*{\mathbb{E}}[\lambda_{\min}(M)]\geq
1-O(1)\sqrt{\frac{n(\ln n)(32k\ln(dn))^{k}}{N_{k,d}}}\geq
1-O(1)\sqrt{\frac{1}{\ln d}}\geq 7/8.$ (F.31)

Now we prove Eq. (F.17). Let $t=1-\lambda_{\min}(M)$ be a random variable.
Note that by Eq. (F.18) we have $\operatorname*{\mathbb{E}}[t]\leq 1/8.$ By
basic algebra, we also have

$\displaystyle\lambda_{\min}(M)\leq
M_{1,1}=P_{k,d}(\left<x_{1},x_{1}\right>)=P_{k,d}(1)=1,$ (F.32)

which implies $t\geq 0.$ Therefore, by Markov inequality we get

$\displaystyle\Pr(\lambda_{\min}(M)\leq 1/2)=\Pr(t\geq 1/2)\leq
2\operatorname*{\mathbb{E}}[t]\leq 1/4.$ (F.33)

∎

##  Appendix G Toolbox

###  G.1 Rademacher Complexity and Generalization Bounds

######  Lemma G.1 (Special Case of Contraction Principle (Lemma 4.6 of
Adamczak et al. [2009])).

Let $\mathcal{F}$ be a family of functions from $D$ to $\mathbb{R}$, and let
$\varphi$ be an $L$-Lipschitz function with $\varphi(0)=0$. Then, for any
$S=\\{x_{1},\ldots,x_{N}\\}\subset D$,

$\displaystyle\operatorname*{\mathbb{E}}_{\epsilon_{i}}\sup_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}\varphi(f(x_{i}))\leq
L\cdot\operatorname*{\mathbb{E}}_{\epsilon_{i}}\sup_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}f(x_{i})$
(G.1)

where the expectations are taken over i.i.d. Rademacher random variables
$\epsilon_{1},\ldots,\epsilon_{N}$.

In the following, for a function family $\mathcal{H}$, we let
${R_{N}}(\mathcal{H})$ denote its Rademacher complexity and
${R_{S}}(\mathcal{H})$ denote its empirical Rademacher complexity (given a
fixed dataset $S$) — see Section 4.4.2 of Ma [2022] for a definition of these
concepts.

######  Lemma G.2 (Empirical Rademacher Complexity of Products).

Suppose $\mathcal{F}$ and $\mathcal{G}$ are two families of functions from $D$
to $\mathbb{R}$, with $D\subset\mathbb{R}^{d}$, which are uniformly bounded by
$B>0$. Then, for any set $S=\\{x_{1},\ldots,x_{N}\\}\subset D$,

$\displaystyle{R_{S}}(\mathcal{F}\cdot\mathcal{G})$ $\displaystyle\leq
B\cdot({R_{S}}(\mathcal{F})+{R_{S}}(\mathcal{G}))\,,$ (G.2)

where $\mathcal{F}\cdot\mathcal{G}=\\{fg\mid
f\in\mathcal{F},g\in\mathcal{G}\\}$. As a corollary,

$\displaystyle{R_{N}}(\mathcal{F}\cdot\mathcal{G})$ $\displaystyle\leq
B\cdot({R_{N}}(\mathcal{F})+{R_{N}}(\mathcal{G}))\,.$ (G.3)

###### Proof of Lemma G.2.

We can write

$\displaystyle{R_{S}}(\mathcal{F}\cdot\mathcal{G})$
$\displaystyle=\operatorname*{\mathbb{E}}_{\epsilon_{i}}\sup_{f\in\mathcal{F},g\in\mathcal{G}}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}f(x_{i})g(x_{i})$
(G.4)
$\displaystyle=\operatorname*{\mathbb{E}}_{\epsilon_{i}}\sup_{f\in\mathcal{F},g\in\mathcal{G}}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}\cdot\frac{(f(x_{i})+g(x_{i}))^{2}-(f(x_{i})-g(x_{i}))^{2}}{4}$
(G.5)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{\epsilon_{i}}\sup_{f\in\mathcal{F},g\in\mathcal{G}}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}\cdot\frac{(f(x_{i})+g(x_{i}))^{2}}{4}+\operatorname*{\mathbb{E}}_{\epsilon_{i}}\sup_{f\in\mathcal{F},g\in\mathcal{G}}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}\frac{(f(x_{i})-g(x_{i}))^{2}}{4}\,.$
(G.6)

Using Lemma G.1 and the fact that the function $x\mapsto x^{2}$ is $2B$
Lipschitz on the interval $[-B,B]$, we have

$\displaystyle{R_{S}}(\mathcal{F}\cdot\mathcal{G})$ $\displaystyle\leq
2B\cdot\operatorname*{\mathbb{E}}_{\epsilon_{i}}\sup_{f\in\mathcal{F},g\in\mathcal{G}}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}\cdot\frac{f(x)+g(x)}{4}+2B\cdot\operatorname*{\mathbb{E}}_{\epsilon_{i}}\sup_{f\in\mathcal{F},g\in\mathcal{G}}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}\frac{f(x_{i})-g(x_{i})}{4}$
(G.7)
$\displaystyle\leq\frac{B}{2}\cdot({R_{S}}(\mathcal{F})+{R_{S}}(\mathcal{G}))+\frac{B}{2}\cdot({R_{S}}(\mathcal{F})+{R_{S}}(\mathcal{G}))$
(G.8) $\displaystyle=B\cdot({R_{S}}(\mathcal{F})+{R_{S}}(\mathcal{G}))\,,$
(G.9)

as desired. ∎

######  Lemma G.3 (Symmetrization — Analogous to Corollary 4.7 of Adamczak et
al. [2009]).

Let $X_{1},\ldots,X_{N}$ be independent random variables. Let $\mathcal{F}$ be
a family of functions from $D\subset\mathbb{R}^{d}$ to $\mathbb{R}$ that is
uniformly bounded by $B_{1}\geq 1$, and let $\mathcal{G}$ be a family of
functions from $D\subset\mathbb{R}^{d}$ to $\mathbb{R}$. Then, for nonnegative
integers $p_{1},p_{2},p_{3},p_{4}$ and a fixed $g\in\mathcal{G}$ that is
bounded by $B_{2}\geq 1$, we have

$\displaystyle\operatorname*{\mathbb{E}}_{X_{i}}\sup_{f_{1},f_{2},f_{3},f_{4}\in\mathcal{F},g\in\mathcal{G}}$
$\displaystyle\Big{|}\frac{1}{N}\sum_{i=1}^{N}\Big{(}|f_{1}(X_{i})|^{p_{1}}|f_{2}(X_{i})|^{p_{2}}|f_{3}(X_{i})|^{p_{3}}|f_{4}(X_{i})|^{p_{4}}|g(X_{i})|$
(G.10)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X_{i}}\Big{[}|f_{1}(X_{i})|^{p_{1}}|f_{2}(X_{i})|^{p_{2}}|f_{3}(X_{i})|^{p_{3}}|f_{4}(X_{i})|^{p_{4}}|g(X_{i})|\Big{]}\Big{)}\Big{|}$
(G.11)
$\displaystyle\leq\textup{poly}(p_{1},p_{2},p_{3},p_{4},B_{1}^{p_{1}+p_{2}+p_{3}+p_{4}},B_{2})\cdot{R_{N}}(\mathcal{F})$
(G.12)

###### Proof of Lemma G.3.

By Theorem 4.13 of Ma [2022],

$\displaystyle\operatorname*{\mathbb{E}}_{X_{i}}\sup_{f_{1},f_{2},f_{3},f_{4}\in\mathcal{F},g\in\mathcal{G}}$
$\displaystyle\Big{|}\frac{1}{N}\sum_{i=1}^{N}\Big{(}|f_{1}(X_{i})|^{p_{1}}|f_{2}(X_{i})|^{p_{2}}|f_{3}(X_{i})|^{p_{3}}|f_{4}(X_{i})|^{p_{4}}|g(X_{i})|$
(G.13)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X_{i}}\Big{[}|f_{1}(X_{i})|^{p_{1}}|f_{2}(X_{i})|^{p_{2}}|f_{3}(X_{i})|^{p_{3}}|f_{4}(X_{i})|^{p_{4}}|g(X_{i})|\Big{]}\Big{)}\Big{|}$
(G.14)
$\displaystyle\lesssim{R_{N}}(\mathcal{F}^{p_{1}}\cdot\mathcal{F}^{p_{2}}\cdot\mathcal{F}^{p_{3}}\cdot\mathcal{F}^{p_{4}}\cdot
g)$ (By Theorem 4.13 of Ma [2022])
$\displaystyle\lesssim\max(B_{1}^{p_{1}+p_{2}+p_{3}+p_{4}},B_{2})\cdot\Big{(}{R_{N}}(\mathcal{F}^{p_{1}}\cdot\mathcal{F}^{p_{2}}\cdot\mathcal{F}^{p_{3}}\cdot\mathcal{F}^{p_{4}})+{R_{N}}(\\{g\\})\Big{)}$
(By Lemma G.2)
$\displaystyle\lesssim\max(B_{1}^{p_{1}+p_{2}+p_{3}+p_{4}},B_{2})\cdot{R_{N}}(\mathcal{F}^{p_{1}}\cdot\mathcal{F}^{p_{2}}\cdot\mathcal{F}^{p_{3}}\cdot\mathcal{F}^{p_{4}})$
(G.15)
$\displaystyle\lesssim\max(B_{1}^{p_{1}+p_{2}+p_{3}+p_{4}},B_{2})\cdot\max(B_{1}^{p_{1}},B_{1}^{p_{2}+p_{3}+p_{4}})\cdot\max(B_{1}^{p_{2}},B_{1}^{p_{3}+p_{4}})$
(G.16)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\cdot\max(B_{1}^{p_{3}},B_{1}^{p_{4}})\cdot({R_{N}}(\mathcal{F}^{p_{1}})+{R_{N}}(\mathcal{F}^{p_{2}})+{R_{N}}(\mathcal{F}^{p_{3}})+{R_{N}}(\mathcal{F}^{p_{4}}))$
(By repeated applications of Lemma G.2)
$\displaystyle\lesssim\max(B_{1}^{O(p_{1}+p_{2}+p_{3}+p_{4})},B_{2})\cdot({R_{N}}(\mathcal{F}^{p_{1}})+{R_{N}}(\mathcal{F}^{p_{2}})+{R_{N}}(\mathcal{F}^{p_{3}})+{R_{N}}(\mathcal{F}^{p_{4}}))$
(G.17)

Finally, we simplify ${R_{N}}(\mathcal{F}^{p_{i}})$ for each $i$. For
nonnegative integers $p$, since $\mathcal{F}$ is uniformly bounded by $B_{1}$,
the function $x\mapsto x^{p}$ is $pB_{1}^{p-1}$-Lipschitz on $[-B_{1},B_{1}]$
for $p\geq 1$ and is $1$-Lipschitz for $p=0$. Thus, by Lemma G.1, we have
${R_{N}}(\mathcal{F}^{p})\leq\min(1,pB_{1}^{p-1}){R_{N}}(\mathcal{F})$, and

$\displaystyle\operatorname*{\mathbb{E}}_{X_{i}}\sup_{f_{1},f_{2},f_{3},f_{4}\in\mathcal{F},g\in\mathcal{G}}$
$\displaystyle\Big{|}\frac{1}{N}\sum_{i=1}^{N}\Big{(}|f_{1}(X_{i})|^{p_{1}}|f_{2}(X_{i})|^{p_{2}}|f_{3}(X_{i})|^{p_{3}}|f_{4}(X_{i})|^{p_{4}}|g(X_{i})|$
(G.18)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X_{i}}\Big{[}|f_{1}(X_{i})|^{p_{1}}|f_{2}(X_{i})|^{p_{2}}|f_{3}(X_{i})|^{p_{3}}|f_{4}(X_{i})|^{p_{4}}|g(X_{i})|\Big{]}\Big{)}\Big{|}$
(G.19)
$\displaystyle\lesssim\max(B_{1}^{O(p_{1}+p_{2}+p_{3}+p_{4})},B_{2})\cdot\max(p_{1}B_{1}^{p_{1}},p_{2}B_{1}^{p_{2}},p_{3}B_{1}^{p_{3}},p_{4}B_{1}^{p_{4}})\cdot{R_{N}}(\mathcal{F})$
(G.20)
$\displaystyle\lesssim\textup{poly}(p_{1},p_{2},p_{3},p_{4},B_{1}^{p_{1}+p_{2}+p_{3}+p_{4}},B_{2})\cdot{R_{N}}(\mathcal{F})$
(G.21)

as desired. ∎

###  G.2 Concentration Lemmas

######  Theorem G.4 (Theorem 5.62 of Vershynin [2010]).

Let $A$ be an $m\times n$ matrix with independent columns
$\\{A_{j}\\}_{j=1}^{n}$ and $m\geq n$. Suppose $A_{j}$ is isotropic, i.e.,
$\operatorname*{\mathbb{E}}[A_{j}A_{j}^{\top}]=I$ and $\|A_{j}\|_{2}=\sqrt{m}$
for every $j\in[n]$. Let $p$ be the incoherence parameter defined by

$\displaystyle
p\triangleq\frac{1}{m}\operatorname*{\mathbb{E}}\left[\max_{i\leq
n}\sum_{j\in[n],j\neq i}\left<A_{i},A_{j}\right>^{2}\right].$ (G.22)

Then there is a universal constant $C_{0}$ such that

$\displaystyle\operatorname*{\mathbb{E}}\left[\left\lVert\frac{1}{m}A^{\top}A-I\right\rVert\right]\leq
C_{0}\sqrt{\frac{p\ln n}{m}}.$ (G.23)

The following proposition gives the tail bound for inner products of random
vectors in $\mathbb{S}^{d-1}$ (c.f. Theorem 3.4.6 of Vershynin [2018]).

######  Proposition G.5.

Let $u$ be a vector drawn uniformly at random from the unit sphere
$\mathbb{S}^{d-1}$. For any fixed vector $v\in\mathbb{S}^{d-1}$, we have

$\displaystyle\forall t>0,\quad\Pr(|u^{\top}v|\geq t)\leq
2\exp\left(-\frac{t^{2}d}{2}\right).$ (G.24)

###### Proof of Proposition G.5.

By the symmetricity of $u$ and $v$, we can assume that $v=(1,0,\cdots,0)$
without loss of generality. Let $x=\frac{1}{2}(u^{\top}v+1)$. Then we have
$x\sim\text{Beta}(\frac{d-1}{2},\frac{d-1}{2}).$ Hence, the desired result
follows directly from Skorski [2023, Theorem 1]. ∎

######  Lemma G.6 (Modification of Proposition 4.4 of Adamczak et al. [2009]).

Let $X_{1},\ldots,X_{N}$ be i.i.d. random vectors drawn uniformly from
$\sqrt{d}\mathbb{S}^{d-1}$, and let $p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}$ be
nonnegative integers. Suppose $p_{1}+p_{2}+p_{3}+p_{4}\geq 2$. Then, for fixed
$w_{1},w_{2}\in\mathbb{S}^{d-1}$, as long as $N\leq d^{C}$ for any universal
constant $C>0$, we have

$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}$
$\displaystyle\Big{|}\frac{1}{N}\sum_{i=1}^{N}|\langle
X_{i},u_{1}\rangle|^{p_{1}}|\langle X_{i},u_{2}\rangle|^{p_{2}}|\langle
X_{i},u_{3}\rangle|^{p_{3}}|\langle X_{i},u_{4}\rangle|^{p_{4}}|\langle
X_{i},w_{1}\rangle|^{q_{1}}|\langle X_{i},w_{2}\rangle|^{q_{2}}$ (G.25)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}\Big{[}|\langle
X,u_{1}\rangle|^{p_{1}}|\langle X,u_{2}\rangle|^{p_{2}}|\langle
X,u_{3}\rangle|^{p_{3}}|\langle X,u_{4}\rangle|^{p_{4}}|\langle
X,w_{1}\rangle|^{q_{1}}|\langle X,w_{2}\rangle|^{q_{2}}\Big{]}$ (G.26)
$\displaystyle\leq C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}(\log
d)^{O(p_{1}+p_{2}+p_{3}+p_{4}+q_{1}+q_{2})}\cdot\sqrt{\frac{d}{N}}$ (G.27)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+C_{p_{1},p_{2},p_{3},p_{4}}(\log
d)^{O(q_{1}+q_{2})}\cdot\frac{d^{\frac{p_{1}+p_{2}+p_{3}+p_{4}}{2}}}{N}+\frac{C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}}{d^{\Omega(\log
d)}}$ (G.28)

with probability at least $1-\frac{1}{d^{\Omega(\log d)}}$. Here,
$C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}$ is a sufficiently large constant
which depends on $p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}$ and
$C_{p_{1},p_{2},p_{3},p_{4}}$ is a constant which depends on
$p_{1},p_{2},p_{3},p_{4}$.

###### Proof of Lemma G.6.

We largely follow the proof of Proposition 4.4 of Adamczak et al. [2009], with
some minor modifications. First, let $E_{1}$ be the event that $|\langle
X_{i},w_{1}\rangle|\leq(\log d)^{2}$ for all $i=1,\ldots,N$, and define
$E_{2}$ analogously for $w_{2}$. By Lemma G.10, the sub-exponential norm of
$\langle X_{i},w_{1}\rangle$ is at most an absolute constant $K>0$. Thus, by
Proposition 2.7.1 of Vershynin [2018], we have

$\displaystyle\mathbb{P}\Big{(}|\langle X_{i},w_{1}\rangle|\geq(\log
d)^{2}\Big{)}$ $\displaystyle\leq 2\exp\Big{(}-\Omega\Big{(}\frac{(\log
d)^{2}}{\|\langle X_{i},w_{1}\rangle\|_{\psi_{1}}}\Big{)}\Big{)}$ (G.29)
$\displaystyle\lesssim\exp\Big{(}-\Omega(\log d)^{2}\Big{)}$ (G.30)
$\displaystyle\lesssim\frac{1}{d^{\Omega(\log d)}}\,.$ (G.31)

Thus, by a union bound, with probability at least $1-\frac{N}{d^{\Omega(\log
d)}}$, for all $i=1,\ldots,N$, we have $|\langle X_{i},w_{1}\rangle|\leq(\log
d)^{2}$, and $|\langle X_{i},w_{2}\rangle|\leq(\log d)^{2}$ (by performing a
similar union bound using the sub-exponential norm of $\langle
X_{i},w_{2}\rangle$). In summary, $E_{1}$ and $E_{2}$ simultaneously hold with
probability at least $1-\frac{1}{d^{\Omega(\log d)}}$ since $N\leq d^{C}$ for
some universal constant $C>0$.

Now, as in Adamczak et al. [2009], define $B>1$, which we will specify later —
this is the amount by which we will truncate $\langle X_{i},u_{1}\rangle$,
$\langle X_{i},u_{2}\rangle$, $\langle X_{i},u_{3}\rangle$ and $\langle
X_{i},u_{4}\rangle$. For convenience, define the function
${\varphi_{B}}:\mathbb{R}\to\mathbb{R}$ given by

$\displaystyle{\varphi_{B}}(t)=\begin{cases}t&t\in[-B,B]\\\ B&t>B\\\
-B&t<B\end{cases}$ (G.32)

Define $B^{\prime}=(\log d)^{2}$, and define ${\varphi_{B^{\prime}}}$
similarly to ${\varphi_{B}}$, but with $B$ replaced by $B^{\prime}$. If
$E_{1}$ and $E_{2}$ hold, then for all
$u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}$, we have

$\displaystyle\Big{|}\frac{1}{N}\sum_{i=1}^{N}|\langle
X_{i},u_{1}\rangle|^{p_{1}}|\langle X_{i},u_{2}\rangle|^{p_{2}}|\langle
X_{i},u_{3}\rangle|^{p_{3}}|\langle
X_{i},u_{4}\rangle|^{p_{4}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{2}\rangle)|^{q_{2}}$ (G.33)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}\Big{[}|\langle
X,u_{1}\rangle|^{p_{1}}|\langle X,u_{2}\rangle|^{p_{2}}|\langle
X,u_{3}\rangle|^{p_{3}}|\langle
X,u_{4}\rangle|^{p_{4}}|{\varphi_{B^{\prime}}}(\langle
X,w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X,w_{2}\rangle)|^{q_{2}}\Big{]}\Big{|}$ (G.34)
$\displaystyle=\Big{|}\frac{1}{N}\sum_{i=1}^{N}|\langle
X_{i},u_{1}\rangle|^{p_{1}}|\langle X_{i},u_{2}\rangle|^{p_{2}}|\langle
X_{i},u_{3}\rangle|^{p_{3}}|\langle X_{i},u_{4}\rangle|^{p_{4}}|\langle
X_{i},w_{1}\rangle|^{q_{1}}|\langle X_{i},w_{2}\rangle|^{q_{2}}$ (G.35)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}\Big{[}|\langle
X,u_{1}\rangle|^{p_{1}}|\langle X,u_{2}\rangle|^{p_{2}}|\langle
X,u_{3}\rangle|^{p_{3}}|\langle
X,u_{4}\rangle|^{p_{4}}|{\varphi_{B^{\prime}}}(\langle
X,w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X,w_{2}\rangle)|^{q_{2}}\Big{]}\Big{|}$ (B.c. $E_{1}$ and $E_{2}$ hold)
$\displaystyle=\Big{|}\frac{1}{N}\sum_{i=1}^{N}|\langle
X_{i},u_{1}\rangle|^{p_{1}}|\langle X_{i},u_{2}\rangle|^{p_{2}}|\langle
X_{i},u_{3}\rangle|^{p_{3}}|\langle X_{i},u_{4}\rangle|^{p_{4}}|\langle
X_{i},w_{1}\rangle|^{q_{1}}|\langle X_{i},w_{2}\rangle|^{q_{2}}$ (G.36)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}\Big{[}|\langle
X,u_{1}\rangle|^{p_{1}}|\langle X,u_{2}\rangle|^{p_{2}}|\langle
X,u_{3}\rangle|^{p_{3}}|\langle X,u_{4}\rangle|^{p_{4}}|\langle
X,w_{1}\rangle|^{q_{1}}|\langle X,w_{2}\rangle|^{q_{2}}\Big{]}\Big{|}$ (G.37)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\pm
C_{p_{1},\ldots,p_{4},q_{1},q_{2}}e^{-\Omega(B^{\prime})}\,.$ (By Lemma G.8)

Thus, the rest of the proof will focus on obtaining an upper bound on

$\displaystyle U:=$
$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}}\Big{|}\frac{1}{N}\sum_{i=1}^{N}|\langle
X_{i},u_{1}\rangle|^{p_{1}}|\langle X_{i},u_{2}\rangle|^{p_{2}}|\langle
X_{i},u_{3}\rangle|^{p_{3}}|\langle
X_{i},u_{4}\rangle|^{p_{4}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{2}\rangle)|^{q_{2}}$ (G.38)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}\Big{[}|\langle
X,u_{1}\rangle|^{p_{1}}|\langle X,u_{2}\rangle|^{p_{2}}|\langle
X,u_{3}\rangle|^{p_{3}}|\langle
X,u_{4}\rangle|^{p_{4}}|{\varphi_{B^{\prime}}}(\langle
X,w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X,w_{2}\rangle)|^{q_{2}}\Big{]}\Big{|}$ (G.39)

First define

$\displaystyle{U^{\prime}}:=$
$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}}\Big{|}\frac{1}{N}\sum_{i=1}^{N}|{\varphi_{B}}(\langle
X_{i},u_{1}\rangle)|^{p_{1}}|{\varphi_{B}}(\langle
X_{i},u_{2}\rangle)|^{p_{2}}|{\varphi_{B}}(\langle
X_{i},u_{3}\rangle)|^{p_{3}}|{\varphi_{B}}(\langle
X_{i},u_{4}\rangle)|^{p_{4}}$ (G.40)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{2}\rangle)|^{q_{2}}$ (G.41)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}\Big{[}|{\varphi_{B}}(\langle
X,u_{1}\rangle)|^{p_{1}}|{\varphi_{B}}(\langle
X,u_{2}\rangle)|^{p_{2}}|{\varphi_{B}}(\langle
X,u_{3}\rangle)|^{p_{3}}|{\varphi_{B}}(\langle X,u_{4}\rangle)|^{p_{4}}$
(G.42)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|{\varphi_{B^{\prime}}}(\langle
X,w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X,w_{2}\rangle)|^{q_{2}}\Big{]}\Big{|}$ (G.43)

We will first obtain an upper bound on ${U^{\prime}}$, then show that
${U^{\prime}}$ and $U$ are close. We apply Lemma G.3 with
$\mathcal{F}=\\{x\mapsto{\varphi_{B}}(\langle x,u\rangle)\mid
u\in\mathbb{S}^{d-1}\\}$, and with $f_{i}$ corresponding to
${\varphi_{B}}(\langle x,u_{i}\rangle)$, and finally with
$g(x)=|{\varphi_{B^{\prime}}}(\langle
x,w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
x,w_{2}\rangle)|^{q_{2}}$, to find that

$\displaystyle\operatorname*{\mathbb{E}}_{X_{i}}{U^{\prime}}$
$\displaystyle\leq\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot{R_{N}}(\mathcal{F})$
(By Lemma G.3)
$\displaystyle\leq\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot\operatorname*{\mathbb{E}}_{X_{i},\epsilon_{i}}\sup_{u\in\mathbb{S}^{d-1}}\Big{|}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}{\varphi_{B}}(\langle
X_{i},u\rangle)\Big{|}$ (G.44)
$\displaystyle\leq\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot\operatorname*{\mathbb{E}}_{X_{i},\epsilon_{i}}\sup_{u\in\mathbb{S}^{d-1}}\Big{|}\frac{1}{N}\sum_{i=1}^{N}\epsilon\langle
X_{i},u\rangle\Big{|}$ (By Lemma G.1 since ${\varphi_{B}}$ is $1$-Lipschitz)
$\displaystyle\leq\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot\operatorname*{\mathbb{E}}_{X_{i},\epsilon_{i}}\Big{\|}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}X_{i}\Big{\|}_{2}$
(G.45)
$\displaystyle\leq\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot\sqrt{\frac{d}{N}}\,.$
(By Lemma G.9)

Now, to show a high-probability upper bound on ${U^{\prime}}$, we apply Lemma
4.8 of Adamczak et al. [2009] (Talagrand’s concentration inequality), and we
ensure that all of the conditions are satisfied:

  * •

We set $X_{1},\ldots,X_{N}$ in Lemma 4.8 of Adamczak et al. [2009] to be as
defined in the statement of Lemma G.6.

  * •

For convenience, define

$\displaystyle g_{B,B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(x)$
$\displaystyle=|{\varphi_{B}}(\langle
x,u_{1}\rangle)|^{p_{1}}|{\varphi_{B}}(\langle
x,u_{2}\rangle)|^{p_{2}}|{\varphi_{B}}(\langle
x,u_{3}\rangle)|^{p_{3}}|{\varphi_{B}}(\langle x,u_{4}\rangle)|^{p_{4}}$
(G.46)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|{\varphi_{B^{\prime}}}(\langle
x,w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
x,w_{2}\rangle)|^{q_{2}}\,.$ (G.47)

Then, we let

$\displaystyle\mathcal{F}=\\{x\mapsto
g_{B,B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(x)-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[g_{B,B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X)]\mid
u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}\\}$ (G.48)

where $w_{1}$ and $w_{2}$ are fixed (i.e. as defined in the statement of Lemma
G.6).

  * •

We let $a=2B^{p_{1}+p_{2}+p_{3}+p_{4}}(B^{\prime})^{q_{1}+q_{2}}$, which is a
uniform bound on all the functions in $\mathcal{F}$.

  * •

Observe that for all $f\in\mathcal{F}$,
$\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}f(X)=0$.

  * •

We let $Z=\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}f(X_{i})$ and
$\sigma^{2}=\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}\operatorname*{\mathbb{E}}f(X_{i})^{2}$.
Observe that $\sigma^{2}\leq a^{2}N$.

Thus, we apply Lemma 4.8 of Adamczak et al. [2009] with

$\displaystyle
t=a\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot\sqrt{\frac{d}{N}}\cdot(\log
d)^{2}\geq a(\log d)^{2}\operatorname*{\mathbb{E}}_{X_{i}}{U^{\prime}}$ (G.49)

to find that

$\displaystyle{U^{\prime}}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{X_{i}}{U^{\prime}}+a\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot\sqrt{\frac{d}{N}}$
(G.50)

with failure probability at most

$\displaystyle\exp\Big{(}-\frac{t^{2}N^{2}}{2(\sigma^{2}+2aN\operatorname*{\mathbb{E}}{U^{\prime}})+3atN}\Big{)}$
$\displaystyle\leq\exp\Big{(}-\frac{t^{2}N^{2}}{12\max(\sigma^{2}+2a\cdot
N\operatorname*{\mathbb{E}}{U^{\prime}},atN)}\Big{)}$ (G.51)
$\displaystyle=\exp\Big{(}-\frac{1}{12}\min\Big{(}\frac{t^{2}N^{2}}{\sigma^{2}+2aN\operatorname*{\mathbb{E}}{U^{\prime}}},\frac{tN}{a}\Big{)}\Big{)}$
(G.52)
$\displaystyle\leq\exp\Big{(}-\frac{1}{12}\min\Big{(}\frac{t^{2}N^{2}}{a^{2}N+2aN\operatorname*{\mathbb{E}}U^{\prime}},\frac{tN}{a}\Big{)}\Big{)}$
(G.53)
$\displaystyle\leq\exp\Big{(}-\frac{1}{12}\min\Big{(}\frac{t^{2}N^{2}}{a^{2}N+2aN\operatorname*{\mathbb{E}}U^{\prime}},\sqrt{dN}\Big{)}\Big{)}$
(G.54)
$\displaystyle\leq\exp\Big{(}-\frac{1}{12}\min\Big{(}\frac{t^{2}N}{a^{2}+2a\operatorname*{\mathbb{E}}U^{\prime}},\sqrt{dN}\Big{)}\Big{)}$
(G.55)
$\displaystyle\leq\exp\Big{(}-\frac{1}{24}\min\Big{(}\frac{t^{2}N}{a^{2}},\frac{t^{2}N}{2a\operatorname*{\mathbb{E}}U^{\prime}},\sqrt{dN}\Big{)}\Big{)}$
(G.56)
$\displaystyle\leq\exp\Big{(}-\frac{1}{24}\min\Big{(}d,\frac{t^{2}N}{2a\operatorname*{\mathbb{E}}U^{\prime}},\sqrt{dN}\Big{)}\Big{)}$
(G.57)
$\displaystyle\leq\exp\Big{(}-\frac{1}{24}\min\Big{(}d,tN,\sqrt{dN}\Big{)}\Big{)}$
(G.58)
$\displaystyle\leq\exp\Big{(}-\frac{1}{24}\min\Big{(}d,\sqrt{dN}\Big{)}\Big{)}$
(G.59) $\displaystyle\leq\exp(-\Omega(\sqrt{d}))\,.$ (G.60)

Observe that Talagrand’s concentration inequality only gives us a bound on
$\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}f(X_{i})$, while we wish to obtain a
high-probability bound on $\sup_{f\in\mathcal{F}}|\sum_{i=1}^{N}f(X_{i})|$.
However, using the same argument, we can obtain a similar high-probability
bound on
$\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}-f(X_{i})=-\inf_{f\in\mathcal{F}}\sum_{i=1}^{N}f(X_{i})$.
Thus, we obtain a lower bound on
$\inf_{f\in\mathcal{F}}\sum_{i=1}^{N}f(X_{i})$ which is the negative of the
upper bound that we obtained for
$\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}f(X_{i})$, meaning that the upper bound
we obtained for $\sup_{f\in\mathcal{F}}\sum_{i=1}^{N}f(X_{i})$ also holds for
$\sup_{f\in\mathcal{F}}|\sum_{i=1}^{N}f(X_{i})|$. In summary,

$\displaystyle{U^{\prime}}$
$\displaystyle\leq\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot(\log
d)^{2}\cdot\sqrt{\frac{d}{N}}$ (G.61)

with probability at least $1-\exp(-\Omega(\sqrt{d}))$.

Now that we have obtained a high-probability bound on ${U^{\prime}}$, let us
analyze the difference between ${U^{\prime}}$ and $U$. Recall the definition
of $g_{B,B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}$ from above.
Additionally, for convenience, let
$g_{B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(x)=|\langle
x,u_{1}\rangle|^{p_{1}}|\langle x,u_{2}\rangle|^{p_{2}}|\langle
x,u_{3}\rangle|^{p_{3}}|\langle
x,u_{4}\rangle|^{p_{4}}|{\varphi_{B^{\prime}}}(\langle
x,w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
x,w_{2}\rangle)|^{q_{2}}$, i.e. we are simply removing the truncation by $B$.
Then, following the proof of Proposition 4.4 in Adamczak et al. [2009], we
have

$\displaystyle U$ $\displaystyle\leq{U^{\prime}}$ (G.62)
$\displaystyle+\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}\frac{1}{N}\sum_{i=1}^{N}|g_{B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})-g_{B,B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})|1\Big{(}\bigcup_{j=1}^{4}\\{|\langle
X_{i},u_{j}\rangle|\geq B\\}\Big{)}$ (G.63)
$\displaystyle+\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}\frac{1}{N}\sum_{i=1}^{N}\operatorname*{\mathbb{E}}_{X_{i}}|g_{B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})-g_{B,B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})|1\Big{(}\bigcup_{j=1}^{4}\\{|\langle
X_{i},u_{j}\rangle|\geq B\\}\Big{)}\,,$ (G.64)

where $\\{C\\}$ denotes the event that the condition $C$ holds. Here the
inequality holds because the difference
$g_{B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})-g_{B,B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})$
is nonzero if and only if $1\Big{(}\bigcup_{j=1}^{4}\\{|\langle
X_{i},u_{j}\rangle|\geq B\\}\Big{)}$ is nonzero. We have obtained a high
probability bound on ${U^{\prime}}$. Let us now obtain a bound on the third
term on the right-hand side of Eq. G.62 (here,
$C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}$ is a constant that depends on
$p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}$):

$\displaystyle\operatorname*{\mathbb{E}}_{X_{i}}|g_{B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})-g_{B,B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})|1\Big{(}\bigcup_{j=1}^{4}\\{|\langle
X_{i},u_{j}\rangle|\geq B\\}\Big{)}$ (G.65)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{X_{i}}|\langle
X_{i},u_{1}\rangle|^{p_{1}}|\langle X_{i},u_{2}\rangle|^{p_{2}}|\langle
X_{i},u_{3}\rangle|^{p_{3}}|\langle X_{i},u_{4}\rangle|^{p_{4}}|\langle
X_{i},w_{1}\rangle|^{q_{1}}|\langle
X_{i},w_{2}\rangle|^{q_{2}}1\Big{(}\bigcup_{j=1}^{4}\\{|\langle
X_{i},u_{j}\rangle|\geq B\\}\Big{)}$ (G.66)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{X_{i}}[|\langle
X_{i},u_{1}\rangle|^{2p_{1}}|\langle X_{i},u_{2}\rangle|^{2p_{2}}|\langle
X_{i},u_{3}\rangle|^{2p_{3}}|\langle X_{i},u_{4}\rangle|^{2p_{4}}|\langle
X_{i},w_{1}\rangle|^{2q_{1}}|\langle X_{i},w_{2}\rangle|^{2q_{2}}]^{1/2}$
(G.67)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathbb{P}\Big{(}\bigcup_{j=1}^{4}\\{|\langle
X_{i},u_{j}\rangle|\geq B\\}\Big{)}^{1/2}$ (By Cauchy-Schwarz inequality)
$\displaystyle\leq
C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}\mathbb{P}\Big{(}\bigcup_{j=1}^{4}\\{|\langle
X_{i},u_{j}\rangle|\geq B\\}\Big{)}^{1/2}\,.$ (G.68)

To obtain the last inequality, we apply the Cauchy-Schwarz inequality multiple
times to write

$\displaystyle\operatorname*{\mathbb{E}}_{X_{i}}[|\langle
X_{i},u_{1}\rangle|^{2p_{1}}|\langle X_{i},u_{2}\rangle|^{2p_{2}}|\langle
X_{i},u_{3}\rangle|^{2p_{3}}|\langle X_{i},u_{4}\rangle|^{2p_{4}}|\langle
X_{i},w_{1}\rangle|^{2q_{1}}|\langle X_{i},w_{2}\rangle|^{2q_{2}}]^{1/2}$
(G.69)

as a product of moments of $|\langle X_{i},u_{j}\rangle|$ and $|\langle
X_{i},w_{j}\rangle|$, and by Lemma G.10, each of these moments can be bounded
above by a constant that depends on $p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}$.
Additionally, by Lemma G.10 and Proposition 2.7.1, part (a) of Vershynin
[2018], we have $\mathbb{P}(|\langle X_{i},u_{j}\rangle|\geq B)\lesssim
e^{-\Omega(B)}$, since $|\langle X_{i},u_{j}\rangle|$ has constant sub-
exponential norm. In summary,

$\displaystyle\operatorname*{\mathbb{E}}_{X_{i}}|g_{B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})-g_{B,B^{\prime},u_{1},u_{2},u_{3},u_{4},w_{1},w_{2}}(X_{i})|1\Big{(}\bigcup_{j=1}^{4}\\{|\langle
X_{i},u_{j}\rangle|\geq B\\}\Big{)}$ (G.70)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\leq
C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}e^{-\Omega(B)}\,.$ (G.71)

To complete the proof, we bound the second term on the right-hand side of Eq.
G.62. Following the proof of Proposition 4.4 of Adamczak et al. [2009], we
apply Lemma G.11 (a variant of Theorem 3.6 of Adamczak et al. [2009]) to find
that, with failure probability at most $e^{-\Omega(\sqrt{d})}$, for all
$m$-sparse vectors $z\in\mathbb{S}^{N-1}$, we have

$\displaystyle\Big{\|}\sum_{i=1}^{N}z_{i}X_{i}\Big{\|}_{2}\lesssim\sqrt{d}+\sqrt{m}\log\Big{(}\frac{2N}{m}\Big{)}\,.$
(G.72)

Let ${E_{\textup{sparse}}}$ be the event that Eq. G.72 holds. For convenience,
let $A\in\mathbb{R}^{d\times N}$ be the matrix whose $i^{th}$ column is
$X_{i}$. Additionally, for any subset $S\subset[N]$, let $A_{S}$ be the matrix
whose columns have indices in $S$. If $S\subset[N]$ with $|S|=m$, then
assuming ${E_{\textup{sparse}}}$ holds, the operator norm of $A_{S}$ is at
most $\sqrt{d}+\sqrt{m}\log\Big{(}\frac{2N}{m}\Big{)}$ up to a constant
factor. Thus, for any set $S\subset[N]$, if ${E_{\textup{sparse}}}$ holds,

$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}$
$\displaystyle\Big{(}\sum_{i\in S}|\langle X_{i},u_{1}\rangle|^{p_{1}}|\langle
X_{i},u_{2}\rangle|^{p_{2}}|\langle X_{i},u_{3}\rangle|^{p_{3}}|\langle
X_{i},u_{4}\rangle|^{p_{4}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{2}\rangle)|^{q_{2}}\Big{)}^{\frac{1}{p_{1}+p_{2}+p_{3}+p_{4}}}$
(G.73)
$\displaystyle\leq(B^{\prime})^{\frac{q_{1}+q_{2}}{p_{1}+p_{2}+p_{3}+p_{4}}}\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}\Big{(}\sum_{i\in
S}|\langle X_{i},u_{1}\rangle|^{p_{1}}|\langle
X_{i},u_{2}\rangle|^{p_{2}}|\langle X_{i},u_{3}\rangle|^{p_{3}}|\langle
X_{i},u_{4}\rangle|^{p_{4}}\Big{)}^{\frac{1}{p_{1}+p_{2}+p_{3}+p_{4}}}$ (G.74)
$\displaystyle\leq(B^{\prime})^{\frac{q_{1}+q_{2}}{p_{1}+p_{2}+p_{3}+p_{4}}}\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}\Big{(}\sum_{i\in
S}|\langle
X_{i},u_{1}\rangle|^{\frac{2p_{1}}{p_{1}+p_{2}+p_{3}+p_{4}}}|\langle
X_{i},u_{2}\rangle|^{\frac{2p_{2}}{p_{1}+p_{2}+p_{3}+p_{4}}}$ (G.75)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\langle
X_{i},u_{3}\rangle|^{\frac{2p_{3}}{p_{1}+p_{2}+p_{3}+p_{4}}}|\langle
X_{i},u_{4}\rangle|^{\frac{2p_{4}}{p_{1}+p_{2}+p_{3}+p_{4}}}\Big{)}^{\frac{1}{2}}$
(B.c. $\|x\|_{2}\geq\|x\|_{p}$ for $p\geq 2$ and $x\in\mathbb{R}^{d}$, and
$p_{1}+p_{2}+p_{3}+p_{4}\geq 2$) $\displaystyle\leq
C_{p_{1},p_{2},p_{3},p_{4}}(B^{\prime})^{\frac{q_{1}+q_{2}}{p_{1}+p_{2}+p_{3}+p_{4}}}\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}\Big{(}\sum_{i\in
S}|\langle X_{i},u_{1}\rangle|^{2}+|\langle X_{i},u_{2}\rangle|^{2}$ (G.76)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+|\langle
X_{i},u_{3}\rangle|^{2}+|\langle X_{i},u_{4}\rangle|^{2}\Big{)}^{\frac{1}{2}}$
(By Weighted AM-GM Inequality, with $C_{p_{1},p_{2},p_{3},p_{4}}$ a constant
depending on $p_{1},p_{2},p_{3},p_{4}$) $\displaystyle\lesssim
C_{p_{1},p_{2},p_{3},p_{4}}(B^{\prime})^{\frac{q_{1}+q_{2}}{p_{1}+p_{2}+p_{3}+p_{4}}}\cdot\Big{(}\sqrt{d}+\sqrt{|S|}\log\Big{(}\frac{2N}{|S|}\Big{)}\Big{)}\,.$
(G.77)

where the last inequality is because ${E_{\textup{sparse}}}$ holds.

Following the proof of Proposition 4.4 of Adamczak et al. [2009], we now
define $S_{B}=\\{i\in[N]\mid|\langle X_{i},u_{j}\rangle|\geq B\text{ for some
}j\in[4]\\}$. Note that $S_{B}$ depends on $u_{1},u_{2},u_{3},u_{4}$, and we
will now show that if we select $B$ to be a certain value which is not too
large, this will still ensure that $S_{B}$ is small. Observe that

$\displaystyle\Big{(}\sum_{i\in S_{B}}|\langle
X_{i},u_{1}\rangle|^{2}+|\langle X_{i},u_{2}\rangle|^{2}+|\langle
X_{i},u_{3}\rangle|^{2}+|\langle
X_{i},u_{4}\rangle|^{2}\Big{)}^{1/2}\geq\Big{(}\sum_{i\in
S_{B}}B^{2}\Big{)}^{1/2}\geq B\sqrt{|S_{B}|}$ (G.78)

and

$\displaystyle\Big{(}\sum_{i\in S_{B}}|\langle
X_{i},u_{1}\rangle|^{2}+|\langle X_{i},u_{2}\rangle|^{2}+|\langle
X_{i},u_{3}\rangle|^{2}+|\langle X_{i},u_{4}\rangle|^{2}\Big{)}^{1/2}$
$\displaystyle\lesssim\sqrt{d}+\sqrt{|S_{B}|}\log\Big{(}\frac{N}{|S_{B}|}\Big{)}\,.$
(B.c. ${E_{\textup{sparse}}}$ holds)

Combining these we obtain

$\displaystyle B\sqrt{|S_{B}|}$
$\displaystyle\lesssim\sqrt{d}+\sqrt{|S_{B}|}\log\Big{(}\frac{N}{|S_{B}|}\Big{)}\,.$
(G.79)

Therefore, if we select $B\gtrsim\log\Big{(}\frac{N}{|S_{B}|}\Big{)}$, we can
eliminate the second term on the right-hand side of Eq. G.79, finding that
$|S_{B}|\lesssim\frac{d}{B^{2}}$. Combining this with Eq. G.73, if
$B\gtrsim\log N$ and ${E_{\textup{sparse}}}$ holds we obtain

$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}$
$\displaystyle\Big{(}\sum_{i\in S_{B}}|\langle
X_{i},u_{1}\rangle|^{p_{1}}|\langle X_{i},u_{2}\rangle|^{p_{2}}|\langle
X_{i},u_{3}\rangle|^{p_{3}}|\langle
X_{i},u_{4}\rangle|^{p_{4}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{2}\rangle)|^{q_{2}}\Big{)}^{\frac{1}{p_{1}+p_{2}+p_{3}+p_{4}}}$
(G.80) $\displaystyle\lesssim
C_{p_{1},p_{2},p_{3},p_{4}}(B^{\prime})^{\frac{q_{1}+q_{2}}{p_{1}+p_{2}+p_{3}+p_{4}}}\cdot\Big{(}\sqrt{d}+\sqrt{|S_{B}|}\log
N\Big{)}$ (G.81) $\displaystyle\lesssim
C_{p_{1},p_{2},p_{3},p_{4}}(B^{\prime})^{\frac{q_{1}+q_{2}}{p_{1}+p_{2}+p_{3}+p_{4}}}\cdot\Big{(}\sqrt{d}+\frac{\sqrt{d}}{B}\log
N\Big{)}$ (B.c. $|S_{B}|\lesssim\frac{d}{B^{2}}$) $\displaystyle\lesssim
C_{p_{1},p_{2},p_{3},p_{4}}(B^{\prime})^{\frac{q_{1}+q_{2}}{p_{1}+p_{2}+p_{3}+p_{4}}}\sqrt{d}\,.$
(B.c. $B\gtrsim\log N$)

Raising both sides to the $(p_{1}+p_{2}+p_{3}+p_{4})^{\textup{th}}$ power, we
finally obtain

$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}$
$\displaystyle\sum_{i\in S_{B}}|\langle X_{i},u_{1}\rangle|^{p_{1}}|\langle
X_{i},u_{2}\rangle|^{p_{2}}|\langle X_{i},u_{3}\rangle|^{p_{3}}|\langle
X_{i},u_{4}\rangle|^{p_{4}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{1}\rangle)|^{q_{1}}|{\varphi_{B^{\prime}}}(\langle
X_{i},w_{2}\rangle)|^{q_{2}}$ (G.82) $\displaystyle\lesssim
C_{p_{1},p_{2},p_{3},p_{4}}^{\prime}(B^{\prime})^{q_{1}+q_{2}}\cdot
d^{\frac{p_{1}+p_{2}+p_{3}+p_{4}}{2}}$ (G.83)

with probability $1-e^{-\Omega(\sqrt{d})}$, where
$C_{p_{1},p_{2},p_{3},p_{4}}^{\prime}$ is a constant which depends on
$p_{1},p_{2},p_{3},p_{4}$.

In summary, assuming ${E_{\textup{sparse}}}$ holds and the high-probability
bound on ${U^{\prime}}$ holds (and these both hold simultaneously with
probability at least $1-\exp(-\Omega(\sqrt{d}))$), we obtain

$\displaystyle U$
$\displaystyle\lesssim\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot(\log
d)^{2}\cdot\sqrt{\frac{d}{N}}+C_{p_{1},p_{2},p_{3},p_{4}}^{\prime}(B^{\prime})^{q_{1}+q_{2}}\cdot\frac{d^{\frac{p_{1}+p_{2}+p_{3}+p_{4}}{2}}}{N}$
(G.84)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}e^{-\Omega(B)}$
(G.85)

by Eq. G.62. Finally, by Eq. G.33, we have

$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}\Big{|}\frac{1}{N}\sum_{i=1}^{N}$
$\displaystyle|\langle X_{i},u_{1}\rangle|^{p_{1}}|\langle
X_{i},u_{2}\rangle|^{p_{2}}|\langle X_{i},u_{3}\rangle|^{p_{3}}|\langle
X_{i},u_{4}\rangle|^{p_{4}}|\langle X_{i},w_{1}\rangle|^{q_{1}}|\langle
X_{i},w_{2}\rangle|^{q_{2}}$ (G.86)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}\Big{[}|\langle
X,u_{1}\rangle|^{p_{1}}|\langle X,u_{2}\rangle|^{p_{2}}|\langle
X,u_{3}\rangle|^{p_{3}}|\langle X,u_{4}\rangle|^{p_{4}}|\langle
X,w_{1}\rangle|^{q_{1}}|\langle X,w_{2}\rangle|^{q_{2}}\Big{]}\Big{|}$ (G.87)
$\displaystyle=U\pm
C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}e^{-\Omega(B^{\prime})}$ (G.88)

as long as the events $E_{1}$ and $E_{2}$ hold, and these events
simultaneously hold with probability at least $1-\frac{1}{d^{\Omega(\log
d)}}$. Thus, by our above bound on $U$ we have

$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}\Big{|}\frac{1}{N}\sum_{i=1}^{N}$
$\displaystyle|\langle X_{i},u_{1}\rangle|^{p_{1}}|\langle
X_{i},u_{2}\rangle|^{p_{2}}|\langle X_{i},u_{3}\rangle|^{p_{3}}|\langle
X_{i},u_{4}\rangle|^{p_{4}}|\langle X_{i},w_{1}\rangle|^{q_{1}}|\langle
X_{i},w_{2}\rangle|^{q_{2}}$ (G.89)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}\Big{[}|\langle
X,u_{1}\rangle|^{p_{1}}|\langle X,u_{2}\rangle|^{p_{2}}|\langle
X,u_{3}\rangle|^{p_{3}}|\langle X,u_{4}\rangle|^{p_{4}}|\langle
X,w_{1}\rangle|^{q_{1}}|\langle X,w_{2}\rangle|^{q_{2}}\Big{]}\Big{|}$ (G.90)
$\displaystyle\lesssim\textup{poly}(p_{1},p_{2},p_{3},p_{4},B^{p_{1}+p_{2}+p_{3}+p_{4}},(B^{\prime})^{q_{1}+q_{2}})\cdot(\log
d)^{2}\cdot\sqrt{\frac{d}{N}}$ (G.91)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+C_{p_{1},p_{2},p_{3},p_{4}}^{\prime}(B^{\prime})^{q_{1}+q_{2}}\cdot\frac{d^{\frac{p_{1}+p_{2}+p_{3}+p_{4}}{2}}}{N}+C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}e^{-\Omega(B)}$
(G.92)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}e^{-\Omega(B^{\prime})}\,.$
(G.93)

Setting $B^{\prime}=(\log d)^{2}$ and $B\gtrsim\max(\log N,(\log
d)^{2})\asymp(\log d)^{2}$ (recall that $N\leq d^{C}$ for a universal constant
$C$), we have

$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}\Big{|}\frac{1}{N}\sum_{i=1}^{N}$
$\displaystyle|\langle X_{i},u_{1}\rangle|^{p_{1}}|\langle
X_{i},u_{2}\rangle|^{p_{2}}|\langle X_{i},u_{3}\rangle|^{p_{3}}|\langle
X_{i},u_{4}\rangle|^{p_{4}}|\langle X_{i},w_{1}\rangle|^{q_{1}}|\langle
X_{i},w_{2}\rangle|^{q_{2}}$ (G.94)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}\Big{[}|\langle
X,u_{1}\rangle|^{p_{1}}|\langle X,u_{2}\rangle|^{p_{2}}|\langle
X,u_{3}\rangle|^{p_{3}}|\langle X,u_{4}\rangle|^{p_{4}}|\langle
X,w_{1}\rangle|^{q_{1}}|\langle X,w_{2}\rangle|^{q_{2}}\Big{]}\Big{|}$ (G.95)
$\displaystyle\leq C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}(\log
d)^{O(p_{1}+p_{2}+p_{3}+p_{4}+q_{1}+q_{2})}\cdot\sqrt{\frac{d}{N}}$ (G.96)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+C_{p_{1},p_{2},p_{3},p_{4}}(\log
d)^{O(q_{1}+q_{2})}\cdot\frac{d^{\frac{p_{1}+p_{2}+p_{3}+p_{4}}{2}}}{N}+\frac{C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}}{d^{\Omega(\log
d)}}$ (G.97)

with probability at least $1-\frac{1}{d^{\Omega(\log d)}}$, as desired. ∎

######  Lemma G.7 (Corollary for Uniform Samples from $\mathbb{S}^{d-1}$).

Let $x_{1},\ldots,x_{N}$ be i.i.d. random vectors sampled uniformly from
$\mathbb{S}^{d-1}$, and let $p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}$ be
nonnegative integers. Suppose $p_{1}+p_{2}+p_{3}+p_{4}\geq 2$. Then, for fixed
$w_{1},w_{2}\in\mathbb{S}^{d-1}$, as long as $N\leq d^{C}$ for any universal
constant $C>0$, we have

$\displaystyle\sup_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{S}^{d-1}}$
$\displaystyle\Big{|}\frac{1}{N}\sum_{i=1}^{N}|\langle
x_{i},u_{1}\rangle|^{p_{1}}|\langle x_{i},u_{2}\rangle|^{p_{2}}|\langle
x_{i},u_{3}\rangle|^{p_{3}}|\langle x_{i},u_{4}\rangle|^{p_{4}}|\langle
x_{i},w_{1}\rangle|^{q_{1}}|\langle x_{i},w_{2}\rangle|^{q_{2}}$ (G.98)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,-\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}\Big{[}|\langle
x,u_{1}\rangle|^{p_{1}}|\langle x,u_{2}\rangle|^{p_{2}}|\langle
x,u_{3}\rangle|^{p_{3}}|\langle x,u_{4}\rangle|^{p_{4}}|\langle
x,w_{1}\rangle|^{q_{1}}|\langle x,w_{2}\rangle|^{q_{2}}\Big{]}$ (G.99)
$\displaystyle\leq\frac{1}{d^{\frac{p_{1}+p_{2}+p_{3}+p_{4}+q_{1}+q_{2}}{2}}}\Big{(}C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}(\log
d)^{O(p_{1}+p_{2}+p_{3}+p_{4}+q_{1}+q_{2})}\cdot\sqrt{\frac{d}{N}}$ (G.100)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+C_{p_{1},p_{2},p_{3},p_{4}}(\log
d)^{O(q_{1}+q_{2})}\cdot\frac{d^{\frac{p_{1}+p_{2}+p_{3}+p_{4}}{2}}}{N}+\frac{C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}}{d^{\Omega(\log
d)}}\Big{)}$ (G.101)

with probability at least $1-\frac{1}{d^{\Omega(\log d)}}$. Here,
$C_{p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}}$ is a constant which depends on
$p_{1},p_{2},p_{3},p_{4},q_{1},q_{2}$, and $C_{p_{1},p_{2},p_{3},p_{4}}$ is a
constant which depends on $p_{1},p_{2},p_{3},p_{4}$.

###### Proof of Lemma G.7.

This is a direct corollary of Lemma G.6, obtained by dividing both sides of
Lemma G.6 by $\frac{1}{d^{(p_{1}+p_{2}+p_{3}+p_{4}+q_{1}+q_{2})/2}}$. ∎

######  Lemma G.8 (Moments for Truncated Dot Products with Random Spherical
Vectors).

Let $P$ be a positive integer, and for $i=1,\ldots,P$, let
$u_{i}\in\mathbb{S}^{d-1}$ and $p_{i}$ be a nonnegative integer. Additionally,
let $B\geq 1$. Finally, let $X$ be a random vector drawn uniformly from
$\sqrt{d}\mathbb{S}^{d-1}$. Then, for some absolute constant $c>0$ we have

$\displaystyle\Big{|}\operatorname*{\mathbb{E}}_{X}\Big{[}\prod_{i=1}^{P}|\langle
X,u_{i}\rangle|^{p_{i}}\Big{]}-\operatorname*{\mathbb{E}}_{X}\Big{[}\prod_{i=1}^{P}|{\varphi_{B}}(\langle
X,u_{i}\rangle)|^{p_{i}}\Big{]}\Big{|}$ $\displaystyle\leq
C_{p_{1},\ldots,p_{P}}e^{-cB}$ (G.102)

where ${\varphi_{B}}$ is defined as

$\displaystyle{\varphi_{B}}(t)=\begin{cases}t&t\in[-B,B]\\\ B&t>B\\\
-B&t<B\end{cases}$ (G.103)

and $C_{p_{1},\ldots,p_{P}}$ is a constant which depends only on
$p_{1},\ldots,p_{P}$.

###### Proof of Lemma G.8.

We use an argument similar to one used in part of the proof of Proposition 4.4
in Adamczak et al. [2009]. First, for $i\in[P]$, we can write

$\displaystyle|\langle X,u_{i}\rangle|^{p_{i}}=|{\varphi_{B}}(\langle
X,u_{i}\rangle)|^{p_{i}}+(|\langle
X,u_{i}\rangle|^{p_{i}}-B^{p_{i}})1_{|\langle X,u_{i}\rangle\geq B}\,.$
(G.104)

Thus, in the expression

$\displaystyle\prod_{i=1}^{P}|\langle
X,u_{i}\rangle|^{p_{i}}-\prod_{i=1}^{P}|{\varphi_{B}}(\langle
X,u_{i}\rangle)|^{p_{i}}\,,$ (G.105)

if we expand the first product using Eq. G.104, then we obtain terms of the
form $\prod_{i=1}^{P}F_{i}$, where $F_{i}$ is either $|{\varphi_{B}}(\langle
X,u_{i}\rangle)|^{p_{i}}$ or $(|\langle
X,u_{i}\rangle|^{p_{i}}-B^{p_{i}})1(|\langle X,u_{i}\rangle|\geq B)$. Observe
that the term where $F_{i}=|{\varphi_{B}}(\langle X,u_{i}\rangle)|^{p_{i}}$
for all $i\in[P]$ cancels with the second term in Eq. G.105. Thus, in order to
obtain an upper bound on

$\displaystyle\operatorname*{\mathbb{E}}_{X}\Big{[}\prod_{i=1}^{P}|\langle
X,u_{i}\rangle|^{p_{i}}-\prod_{i=1}^{P}|{\varphi_{B}}(\langle
X,u_{i}\rangle)|^{p_{i}}\Big{]}\,,$ (G.106)

it suffices to upper bound the terms $\prod_{i=1}^{P}F_{i}$ where at least one
of the $F_{i}$ is $(|\langle X,u_{i}\rangle|^{p_{i}}-B^{p_{i}})1(|\langle
X,u_{i}\rangle|\geq B)$. Observe however that

$\displaystyle(|\langle X,u_{i}\rangle|^{p_{i}}-B^{p_{i}})1(|\langle
X,u_{i}\rangle|\geq B)$ $\displaystyle\leq|\langle
X,u_{i}\rangle|^{p_{i}}1(|\langle X,u_{i}\rangle|\geq B)\,.$ (G.107)

Thus, because $|{\varphi_{B}}(\langle X,u_{i}\rangle)|\leq|\langle
X,u_{i}\rangle|$, in order to upper bound the terms $\prod_{i=1}^{P}F_{i}$
where at least one of the $F_{i}$ is $(|\langle
X,u_{i}\rangle|^{p_{i}}-B^{p_{i}})1(|\langle X,u_{i}\rangle\geq B)$, it
suffices to obtain an upper bound on the expected value of

$\displaystyle 1(|\langle X,u_{i}\rangle|\geq B\text{ for some
}i\in[P])\prod_{i=1}^{P}|\langle X,u_{i}\rangle|^{p_{i}}$
$\displaystyle\leq\sum_{i=1}^{P}1(|\langle X,u_{i}\rangle|\geq
B)\prod_{j=1}^{P}|\langle X,u_{j}\rangle|^{p_{i}}\,.$ (G.108)

Without loss of generality, let us bound the expected value of the first term
in the sum above:

$\displaystyle\operatorname*{\mathbb{E}}_{X}\Big{[}1(|\langle
X,u_{1}\rangle|\geq B)\prod_{i=1}^{P}|\langle X,u_{j}\rangle|^{p_{i}}\Big{]}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{X}[1(|\langle
X,u_{1}\rangle|\geq
B)]^{1/2}\operatorname*{\mathbb{E}}_{X}\Big{[}\prod_{i=1}^{P}|\langle
X,u_{j}\rangle|^{2p_{i}}\Big{]}^{1/2}$ (By the Cauchy-Schwarz Inequality)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{X}[1(|\langle
X,u_{1}\rangle|\geq
B)]^{1/2}\cdot\prod_{i=1}^{P}\operatorname*{\mathbb{E}}_{X}[|\langle
X,u_{j}\rangle|^{2^{i+1}p_{i}}]^{\frac{1}{2^{i+1}}}$ (By applying the Cauchy-
Schwarz inequality $P-1$ times) $\displaystyle\leq
C_{p_{1},\ldots,p_{P}}\operatorname*{\mathbb{E}}_{X}[1(|\langle
X,u_{1}\rangle|\geq B]^{1/2}\,,$ (G.109)

where the last inequality is by Lemma G.10 and Proposition 2.7.1 of Vershynin
[2018]. Finally, since the sub-exponential norm of $\langle X,u_{1}\rangle$ is
at most an absolute constant by Lemma G.10, we have that

$\displaystyle\operatorname*{\mathbb{E}}_{X}[1(|\langle X,u_{1}\rangle|\geq
B]=\mathbb{P}(|\langle X,u_{1}\rangle|\geq B)\lesssim e^{-cB}$ (G.110)

for some absolute constant $c>0$. Thus, by Eq. G.109, we obtain

$\displaystyle\operatorname*{\mathbb{E}}_{X}\Big{[}1(|\langle
X,u_{1}\rangle|\geq B)\prod_{i=1}^{P}|\langle X,u_{j}\rangle|^{p_{j}}\Big{]}$
$\displaystyle\lesssim C_{p_{1},\ldots,p_{P}}e^{-cB}$ (G.111)

for some absolute constant $c>0$. This completes the proof. ∎

######  Lemma G.9.

Let $N,d\in\mathbb{N}$. Let $X_{1},\ldots,X_{N}$ i.i.d. random vectors drawn
uniformly from $\sqrt{d}\mathbb{S}^{d-1}$. Additionally, let
$\epsilon_{1},\ldots,\epsilon_{N}$ be i.i.d. Rademacher random variables.
Then,

$\displaystyle\operatorname*{\mathbb{E}}_{X,\epsilon_{i}}\Big{\|}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}X_{i}\Big{\|}_{2}$
$\displaystyle\leq\sqrt{\frac{d}{N}}\,.$ (G.112)

###### Proof of Lemma G.9.

We first bound the second moment of the norm:

$\displaystyle\operatorname*{\mathbb{E}}_{X,\epsilon_{i}}\Big{\|}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}X_{i}\Big{\|}_{2}^{2}$
$\displaystyle=\frac{1}{N^{2}}\sum_{i=1}^{N}\sum_{j=1}^{N}\operatorname*{\mathbb{E}}_{\epsilon_{i},X_{i}}\epsilon_{i}\epsilon_{j}\langle
X_{i},X_{j}\rangle$ (G.113)
$\displaystyle=\frac{1}{N^{2}}\sum_{i=1}^{N}\operatorname*{\mathbb{E}}_{X_{i}}\|X_{i}\|_{2}^{2}$
(B.c. $\operatorname*{\mathbb{E}}[\epsilon_{i}\epsilon_{j}]=0$ for $i\neq j$)
$\displaystyle=\frac{1}{N^{2}}\sum_{i=1}^{N}d$ (B.c. $\|X_{i}\|_{2}=\sqrt{d}$
with probability $1$) $\displaystyle=\frac{Nd}{N^{2}}$ (G.114)
$\displaystyle=\frac{d}{N}\,.$ (G.115)

Thus,
$\operatorname*{\mathbb{E}}_{X,\epsilon_{i}}\Big{\|}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}X_{i}\Big{\|}_{2}\leq\Big{(}\operatorname*{\mathbb{E}}_{X,\epsilon_{i}}\Big{\|}\frac{1}{N}\sum_{i=1}^{N}\epsilon_{i}X_{i}\Big{\|}_{2}^{2}\Big{)}^{1/2}\leq\sqrt{\frac{d}{N}}$,
as desired. ∎

######  Lemma G.10 (Sub-Exponential Norm of Uniform Distribution on
$\sqrt{d}\mathbb{S}^{d-1}$).

Assume $d\geq C$ for some sufficiently large universal constant $C$. Then
there exists an absolute constant $K>0$ such that, if $X$ is a random vector
drawn uniformly from $\sqrt{d}\mathbb{S}^{d-1}$ and $v\in\mathbb{S}^{d-1}$ is
a fixed vector, then $\|\langle X,v\rangle\|_{\psi_{1}}\leq K$, where
$\|\cdot\|_{\psi_{1}}$ denotes the sub-exponential norm of a random variable.
(See Definition 2.7.5 of Vershynin [2018].) As a corollary, for any $p\geq 1$,
there exists a constant $C_{p}>0$ depending on $p$ such that for any
$v\in\mathbb{S}^{d-1}$,
$\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
X,v\rangle|^{p}]\leq C_{p}$.

###### Proof of Lemma G.10.

Let $X$ be drawn uniformly at random from the uniform distribution on
$\sqrt{d}\mathbb{S}^{d-1}$, and let $v\in\mathbb{S}^{d-1}$. Observe that the
distribution of $\frac{1}{\sqrt{d}}\langle X,v\rangle$ is $\mu_{d}$. Thus, the
density of $\frac{1}{\sqrt{d}}\langle X,v\rangle$ is
$p(t)=\frac{\Gamma(d/2)}{\sqrt{\pi}\Gamma((d-1)/2)}(1-t^{2})^{\frac{d-3}{2}}$
by Eqs. (1.16) and (1.18) of Atkinson and Han [2012]. By a change of
variables, the density of $\langle X,v\rangle$ is

$\displaystyle p(t)$
$\displaystyle=\frac{\Gamma(d/2)}{\sqrt{\pi}\Gamma((d-1)/2)}\Big{(}1-\frac{t^{2}}{d}\Big{)}^{\frac{d-3}{2}}\cdot\frac{1}{\sqrt{d}}.$
(G.116)

Thus, for any $t\geq 0$,

$\displaystyle\mathbb{P}(|\langle X,v\rangle|\geq t)$ $\displaystyle\lesssim
2\int_{t}^{\infty}p(s)ds$ (G.117) $\displaystyle\lesssim
2\int_{t}^{\infty}\frac{\Gamma(d/2)}{\sqrt{\pi}\Gamma((d-1)/2)}\Big{(}1-\frac{s^{2}}{d}\Big{)}^{\frac{d-3}{2}}\cdot\frac{1}{\sqrt{d}}ds$
(G.118)
$\displaystyle\lesssim\int_{t}^{\infty}\Big{(}1-\frac{s^{2}}{d}\Big{)}^{\frac{d-3}{2}}ds$
(By Stirling’s formula)
$\displaystyle\lesssim\int_{t}^{\infty}e^{-\frac{d-3}{2}\cdot\frac{s^{2}}{d}}ds$
(B.c. $1+x\leq e^{x}$)
$\displaystyle\lesssim\int_{t}^{\infty}e^{-\frac{s^{2}}{3}}ds$ (B.c.
$\frac{d-3}{2d}\geq\frac{1}{3}$ for $d$ sufficiently large)

Thus, for some absolute constant $C>0$ and all $t\geq 0$,

$\displaystyle\mathbb{P}(|\langle X,v\rangle|\geq t)\leq
C\int_{t}^{\infty}e^{-\frac{s^{2}}{3}}ds\leq
C\int_{t}^{\infty}e^{-\frac{st}{3}}ds=C\Big{(}-\frac{3}{t}e^{-\frac{st}{3}}\Big{)}\Big{|}_{t}^{\infty}=\frac{3C}{t}e^{-\frac{t^{2}}{3}}\leq
e^{-\frac{t^{2}}{3}+\log\frac{3C}{t}}$ (G.119)

Suppose $t\geq(18C)^{1/3}$. Then, $\frac{t^{2}}{6}\geq\log\frac{3C}{t}$,
meaning that $-\frac{t^{2}}{3}+\log\frac{3C}{t}\leq-\frac{t^{2}}{6}$, and
therefore

$\displaystyle\mathbb{P}(|\langle X,v\rangle|\geq t)$ $\displaystyle\leq
e^{-\frac{t^{2}}{6}}$ (G.120)

Thus, by the definition of sub-Gaussian norm (Definition 2.5.6 and Proposition
2.5.2 of Vershynin [2018]), the sub-Gaussian norm of $\langle X,v\rangle$ is
bounded by a constant, i.e. for any $v\in\mathbb{S}^{d-1}$, we have $\|\langle
X,v\rangle\|_{\psi_{2}}\leq K$ for some absolute constant $K>0$ (here
$\|\cdot\|_{\psi_{2}}$ denotes the sub-Gaussian norm of a random variable). By
Propositions 2.5.2 and 2.7.1, and Definition 2.7.5, of Vershynin [2018], this
implies that $\|\langle X,v\rangle\|_{\psi_{1}}\lesssim 1$, since sub-Gaussian
random variables are always sub-exponential (specifically, using item (ii) of
Proposition 2.5.2 and item (b) of Proposition 2.7.1 of Vershynin [2018]). The
last statement of the lemma follows directly from Proposition 2.7.1, item (b)
of Vershynin [2018]. ∎

######  Lemma G.11 (Modification of Theorem 3.6 of Adamczak et al. [2009]).

Let $d\geq C$ for some absolute constant $C$, and $1\leq N\leq e^{\sqrt{d}}$.
Let $X_{1},\ldots,X_{N}$ be i.i.d. random vectors sampled from the uniform
distribution on $\sqrt{d}\mathbb{S}^{d-1}$. Finally, let $t\geq 1$. Then, for
some absolute constant $c>0$, with probability at least $1-e^{-ct\sqrt{d}}$,
for all $m\in[N]$,

$\displaystyle\sup_{\begin{subarray}{c}z\in\mathbb{S}^{d-1}\\\
|\textup{supp}\,z|\leq
m\end{subarray}}\Big{\|}\sum_{i=1}^{N}z_{i}X_{i}\Big{\|}_{2}\lesssim
t\Big{(}\sqrt{d}+\sqrt{m}\log\Big{(}\frac{2N}{m}\Big{)}\Big{)}$ (G.121)

Here, we use $\textup{supp}\,z$ to denote the set of nonzero coordinates of
$z$.

###### Proof of Lemma G.11.

The proof is the same as that of Theorem 3.6 of Adamczak et al. [2009] — while
Theorem 3.6 of Adamczak et al. [2009] is shown for the case where
$X_{1},\ldots,X_{N}$ are sampled from an isotropic, log-concave probability
distribution, the proof can be generalized to the case where the $X_{i}$ are
sampled from $\sqrt{d}\mathbb{S}^{d-1}$. To see why, observe that the proof
only uses the fact that the distribution of the $X_{i}$ is log-concave in the
following places: (i) when applying Lemma 3.1 (also of Adamczak et al.
[2009]), of which the conclusion is that $\max_{i\leq N}\|X_{i}\|_{2}\leq
C_{0}K\sqrt{d}$ with probability at least $1-e^{-K\sqrt{d}}$, for some
absolute constant $C_{0}$, (ii) when applying Lemmas 3.3 and 3.4 (also of
Adamczak et al. [2009]) the proof requires that $\|\langle
X_{i},y\rangle\|_{\psi_{1}}\leq\psi$ for some absolute constant $\psi>0$ and
any $y\in\mathbb{S}^{d-1}$. However, property (i) trivially holds when the
$X_{i}$ are on $\sqrt{d}\mathbb{S}^{d-1}$ since $\|X_{i}\|_{2}=\sqrt{d}$, and
property (ii) holds by Lemma G.10. ∎

###  G.3 Helper Lemmas

######  Lemma G.12.

Let $f:[0,\infty)\to\mathbb{R}_{\geq 0}$ such that

$\displaystyle\frac{d}{dt}f(t)^{2}\leq p_{t}f(t)+q_{t}f(t)^{2}$ (G.122)

where $p_{t},q_{t}>0$ for $t\in[0,\infty)$. Then, for $T>0$ we have

$\displaystyle
f(T)^{2}\leq\Big{(}f(0)+\frac{\max_{t}p_{t}}{\min_{t}q_{t}}\Big{)}^{2}\exp\Big{(}\int_{0}^{T}q_{t}dt\Big{)}.$
(G.123)

###### Proof.

$\displaystyle\frac{df(t)}{dt}=\frac{1}{2f(t)}\frac{df(t)^{2}}{dt}\leq\frac{p_{t}}{2}+\frac{q_{t}}{2}f(t)\leq\frac{\max_{t}p_{t}}{2}+\frac{q_{t}}{2}f(t).$
(G.124)

Thus, we have

$\displaystyle\frac{d}{dt}\Big{(}f(t)+\frac{\max_{t}p_{t}}{\min_{t}q_{t}}\Big{)}\leq\frac{q_{t}}{2}\Big{(}f(t)+\frac{\max_{t}p_{t}}{\min_{t}q_{t}}\Big{)}.$
(G.125)

As a result, by G.13,

$\displaystyle
f(T)\leq\Big{(}f(0)+\frac{\max_{t}p_{t}}{\min_{t}q_{t}}\Big{)}\exp\Big{(}\int_{0}^{T}\frac{q_{t}}{2}dt\Big{)}.$
(G.126)

Taking the square of both sides finishes the proof. ∎

######  Fact G.13 (Gronwall’s Inequality [Bainov and Simeonov, 1992]).

Let $a<b$, and let $f:[a,b]\to\mathbb{R}_{\geq 0}$ and $g:[a,b]\to\mathbb{R}$
be differentiable functions, such that

$\displaystyle f^{\prime}(t)\leq g(t)f(t)$ (G.127)

for all $t\in[a,b]$. Then, for all $t\in[a,b]$, $f(t)\leq
f(a)\exp(\int_{a}^{s}g(s)ds)$. Additionally, suppose $f,g$ satisfy

$\displaystyle f^{\prime}(t)\geq g(t)f(t)$ (G.128)

for all $t\in[a,b]$. Then, for all $t\in[a,b]$, $f(t)\geq
f(a)\exp(\int_{a}^{s}g(s)ds)$.

######  Proposition G.14.

For any $\beta_{2},\beta_{4}$ such that
$0\leq\beta_{2}^{2}\leq\beta_{4}\leq\beta_{2}\leq 1$, there exists a one-
dimensional distribution $\mu$ that satisfies

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu}[w^{2}]=\beta_{2},$ (G.129)
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu}[w^{4}]=\beta_{4},$ (G.130)
$\displaystyle{\rm supp}(\mu)\subseteq[-1,1].$ (G.131)

###### Proof.

Let $p=\beta_{2}^{2}/\beta_{4}.$ By the assumptions we have $0\leq p\leq 1$.
Consider the distribution

$\displaystyle\mu(x)=\frac{\beta_{2}^{2}}{\beta_{4}}\delta_{x=\beta_{4}^{1/2}\beta_{2}^{-1/2}}+\left(1-\frac{\beta_{2}^{2}}{\beta_{4}}\right)\delta_{x=0},$
(G.132)

where $\delta_{x=t}$ denotes the Dirac measure at $x=t$. First of all, since
$\beta_{2}^{2}\leq\beta_{4}$, the distribution $\mu(x)$ is well-defined. And
we can verify that

$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu}[w^{2}]=\frac{\beta_{2}^{2}}{\beta_{4}}(\beta_{4}^{1/2}\beta_{2}^{-1/2})^{2}=\beta_{2},$
(G.133)
$\displaystyle\operatorname*{\mathbb{E}}_{w\sim\mu}[w^{4}]=\frac{\beta_{2}^{2}}{\beta_{4}}(\beta_{4}^{1/2}\beta_{2}^{-1/2})^{4}=\beta_{4}.$
(G.134)

Note that $0\leq\beta_{4}\leq\beta_{2}$ implies
$\beta_{4}^{1/2}\beta_{2}^{-1/2}\in[0,1]$. Consequently,

$\displaystyle{\rm supp}(\mu)\subseteq[-1,1].$ (G.135)

∎

######  Lemma G.15.

Let $\rho$ be a distribution which is rotationally invariant as in Definition
4.1. Let $\nabla_{u}L(\rho)$ be defined as in Eq. 3.4, and let
$\nabla_{z}L(\rho)$ denote the last $(d-1)$ coordinates of
$\nabla_{u}L(\rho)$. Then, for any particle $u=(w,z)$, we have that
$\nabla_{z}L(\rho)$ is a scalar multiple of $z$. In particular, if
${\textup{grad}}_{u}L(\rho)$ is defined as in Eq. 3.4 and
${\textup{grad}}_{z}L(\rho)$ denotes the last $(d-1)$ coordinates of
${\textup{grad}}_{u}L(\rho)$, then ${\textup{grad}}_{z}L(\rho)$ is a scalar
multiple of $z$.

###### Proof.

From Eq. 3.4, we have

$\displaystyle\nabla_{u}L(\rho)$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}[(f_{\rho}(x)-y(x))\sigma^{\prime}(u^{\top}x)x]\,.$
(G.136)

Since $\rho$ is rotationally invariant, if $x,x^{\prime}\in\mathbb{S}^{d-1}$
such that $\langle e_{1},x\rangle=\langle e_{1},x^{\prime}\rangle$, then
$f_{\rho}(x)-y(x)=f_{\rho}(x^{\prime})-y(x^{\prime})$. Thus,
$(f_{\rho}(x)-y(x))\sigma^{\prime}(u^{\top}x)$ only depends on $\langle
e_{1},x\rangle$ and $\langle u,x\rangle$.

Let $P_{e_{1},u}\in\mathbb{R}^{d\times d}$ denote the projection matrix into
the subspace spanned by $e_{1}$ and $u$. Then,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}[(f_{\rho}(x)-y(x))\sigma^{\prime}(u^{\top}x)(x-P_{e_{1},u}x)]=0$
(G.137)

because if $v\in\mathbb{S}^{d-1}$ is orthogonal to $e_{1}$ and $u$, then the
distribution of $\langle v,x\rangle$ conditioned on $\langle e_{1},x\rangle$
and $\langle u,x\rangle$ is symmetric around $0$. Thus,

$\displaystyle\nabla_{u}L(\rho)=\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}[(f_{\rho}(x)-y(x))\sigma^{\prime}(u^{\top}x)P_{e_{1},u}x]=P_{e_{1},u}(\nabla_{u}L(\rho))$
(G.138)

and we have that $\nabla_{u}L(\rho)$ is in the subspace spanned by $e_{1}$ and
$u$. In other words, there are scalars $c_{1},c_{2}\in\mathbb{R}$ such that

$\displaystyle\nabla_{u}L(\rho)$ $\displaystyle=c_{1}e_{1}+c_{2}u$ (G.139)

and taking the last $(d-1)$ coordinates of both sides of this equation gives
$\nabla_{u}L(\rho)=c_{2}z$, as desired. The last statement of the lemma holds
because ${\textup{grad}}_{u}L(\rho)=(I-uu^{\top})\nabla_{u}L(\rho)$, which is
also a linear combination of $e_{1}$ and $u$. ∎

######  Lemma G.16.

Let $P$ be a polynomial of degree at most $k>0$, where $k$ is bounded by a
universal constant, and let $w_{1},w_{2}\in[-1,1]$. Suppose the coefficients
of $P$ are bounded by $B$. Then, $|P(w_{1})-P(w_{2})|\lesssim B|w_{1}-w_{2}|$.

###### Proof.

Let $c_{i}$ be the coefficient of the $i^{th}$ degree term in $P$. Then, the
lemma follows from expanding $P(w_{1})-P(w_{2})$ as

$\displaystyle|P(w_{1})-P(w_{2})|$
$\displaystyle\leq\sum_{i=0}^{k}|c_{i}||w_{1}^{i}-w_{2}^{i}|$ (G.140)
$\displaystyle\leq\sum_{i=0}^{k}|c_{i}||w_{1}-w_{2}|\cdot\sum_{j=0}^{i}|w_{1}|^{j}|w_{2}|^{i-j}$
(G.141) $\displaystyle\leq\sum_{i=0}^{k}(i+1)\cdot|c_{i}||w_{1}-w_{2}|$ (B.c.
$|w_{1}|,|w_{2}|\leq 1$) $\displaystyle\leq B(k+1)\sum_{i=0}^{k}|w_{1}-w_{2}|$
(G.142) $\displaystyle=B(k+1)^{2}|w_{1}-w_{2}|$ (G.143) $\displaystyle\lesssim
B|w_{1}-w_{2}|$ (B.c. $k$ is at most an absolute constant)

as desired. ∎

######  Lemma G.17 (Powers of Dot Products on $\mathbb{S}^{d-1}$).

Let $u_{1},u_{2},u_{3},u_{4},u_{5}\in\mathbb{S}^{d-1}$, and $p,q,r,s,t\geq 1$.
Then,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}[|\langle
u_{1},x\rangle|^{p}|\langle u_{2},x\rangle|^{q}|\langle
u_{3},x\rangle|^{r}|\langle u_{4},x\rangle|^{s}|\langle
u_{5},x\rangle|^{t}]\leq C_{p,q,r,s,t}\frac{1}{d^{(p+q+r+s+t)/2}}\,.$ (G.144)

Here, $C_{p,q,r,s,t}$ is a constant depending on $p,q,r,s,t$.

###### Proof of Lemma G.17.

By repeated applications of the Cauchy-Schwarz inequality, we have

$\displaystyle\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}$
$\displaystyle[|\langle u_{1},X\rangle|^{p}|\langle
u_{2},X\rangle|^{q}|\langle u_{3},X\rangle|^{r}|\langle
u_{4},X\rangle|^{s}|\langle u_{5},X\rangle|^{t}]$ (G.145)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[\langle
u_{1},X\rangle|^{2p}]^{1/2}\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{2},X\rangle|^{2q}|\langle u_{3},X\rangle|^{2r}|\langle
u_{4},X\rangle|^{2s}|\langle u_{5},X\rangle|^{2t}]^{1/2}$ (G.146)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[\langle
u_{1},X\rangle|^{2p}]^{1/2}\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{2},X\rangle|^{4q}]^{1/4}\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{3},X\rangle|^{4r}|\langle u_{4},X\rangle|^{4s}|\langle
u_{5},X\rangle|^{4t}]^{1/4}$ (G.147)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[\langle
u_{1},X\rangle|^{2p}]^{1/2}\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{2},X\rangle|^{4q}]^{1/4}\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{3},X\rangle|^{8r}]^{1/8}$ (G.148)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{4},X\rangle|^{8s}|\langle u_{5},X\rangle|^{8t}]^{1/8}$ (G.149)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[\langle
u_{1},X\rangle|^{2p}]^{1/2}\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{2},X\rangle|^{4q}]^{1/4}\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{3},X\rangle|^{8r}]^{1/8}$ (G.150)
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{4},X\rangle|^{16s}]^{1/16}\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{5},X\rangle|^{16t}]^{1/16}$ (G.151)

where each line results from a single application of the Cauchy-Schwarz
inequality. Thus, by Lemma G.10, we have

$\displaystyle\operatorname*{\mathbb{E}}_{X\sim\sqrt{d}\mathbb{S}^{d-1}}[|\langle
u_{1},X\rangle|^{p}|\langle u_{2},X\rangle|^{q}|\langle
u_{3},X\rangle|^{r}|\langle u_{4},X\rangle|^{s}|\langle u_{5},X\rangle|^{t}]$
$\displaystyle\leq C_{p,q,r,s,t}\,.$ (G.152)

Dividing both sides by $d^{(p+q+r+s+t)/2}$, we obtain

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathbb{S}^{d-1}}[|\langle
u_{1},x\rangle|^{p}|\langle u_{2},x\rangle|^{q}|\langle
u_{3},x\rangle|^{r}|\langle u_{4},x\rangle|^{s}|\langle
u_{5},x\rangle|^{t}]\leq C_{p,q,r,s,t}\frac{1}{d^{(p+q+r+s+t)/2}}$ (G.153)

as desired. ∎