W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}-\eta/10}\right)-\eta/10}\right)-\eta/10$
$\displaystyle\quad\geqslant(1-\eta)\mathbb{E}\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}-\eta.$

∎

######  Lemma 6.5.

Let $\eta<0.001$. For

$n\geqslant
kd\log^{2}(d/\varepsilon)\cdot\mathopen{}\mathclose{{}\left(\frac{t\cdot\|\operatorname{cov}(\bm{y}^{0})\|\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|}{\eta}}\right)^{O(1)},$

with probability $1-\varepsilon$,

$\mathopen{}\mathclose{{}\left\\{\|v\|^{2}=1}\right\\}\sststile{2t}{}\mathopen{}\mathclose{{}\left\\{\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t}\leqslant(1+\eta)\cdot\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}+\eta}\right\\},$
$\mathopen{}\mathclose{{}\left\\{\|v\|^{2}=1}\right\\}\sststile{2t}{}\mathopen{}\mathclose{{}\left\\{\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t}\geqslant(1-\eta)\cdot\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}-\eta}\right\\}.$

###### Proof.

See Section A.8. ∎

######  Lemma 6.6.

Let $\eta<0.001$. For

$n\geqslant
kd\log^{2}(d)\varepsilon^{-1}\cdot\mathopen{}\mathclose{{}\left(\frac{tp_{\mathrm{min}}^{-1}d\cdot\|\operatorname{cov}(\bm{y}^{0})\|\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|}{\eta}}\right)^{O(1)},$

with probability $1-\varepsilon$,

$\mathopen{}\mathclose{{}\left\\{\|v\|^{2}=1}\right\\}\sststile{2t}{}\mathopen{}\mathclose{{}\left\\{\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}\leqslant(1+\eta)\cdot\hat{\mathbb{E}}\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}+\eta}\right\\},$
$\mathopen{}\mathclose{{}\left\\{\|v\|^{2}=1}\right\\}\sststile{2t}{}\mathopen{}\mathclose{{}\left\\{\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}\geqslant(1-\eta)\cdot\hat{\mathbb{E}}\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}-\eta}\right\\}.$

###### Proof.

See Section A.8. ∎

######  Lemma 6.7.

Let $\eta<0.001$. Let $v\in\mathbb{R}^{d}$ be a unit vector. For

$n\geqslant
kd\log^{2}(d/\varepsilon)\cdot\mathopen{}\mathclose{{}\left(\frac{\|\operatorname{cov}(\bm{y}^{0})\|\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|}{\eta}}\right)^{O(1)},$

with probability $1-\varepsilon$, for all $i,j\in[k]$,

$|\langle
W(\mu_{i}^{0}-\mu_{j}^{0}),v\rangle-\langle\hat{W}(\mu_{i}^{0}-\mu_{j}^{0}),v\rangle|\leqslant\eta.$

###### Proof.

See Section A.8. ∎

######  Lemma 6.8.

Let $\eta<0.001$. Let $v\in\mathbb{R}^{d}$ be a unit vector. For

$n\geqslant
kd\log^{2}(d/\varepsilon)\cdot\mathopen{}\mathclose{{}\left(\frac{p_{\mathrm{min}}^{-1}\cdot\|\operatorname{cov}(\bm{y}^{0})\|\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|}{\eta}}\right)^{O(1)},$

with probability $1-\varepsilon$,

$\|v^{\top}W(\Sigma^{0})^{1/2}-v^{\top}\hat{W}(\Sigma^{0})^{1/2}\|\leqslant\eta.$

###### Proof.

See Section A.8. ∎

###  6.4 Proof of Theorem 6.1

###### Proof of Theorem 6.1.

The first step of the algorithm is to apply the approximate istropic position
transformation described in Section 6.2 to input samples
$y_{1}^{0},...,y_{n}^{0}$. Then, the new samples are
$\hat{W}(y_{1}^{0}-\hat{\mathbb{E}}y^{0}),...,\hat{W}(y_{n}^{0}-\hat{\mathbb{E}}y^{0})$.
After that, the algorithm is the same as that of Theorem 5.1.

We now argue that, for $n\geqslant n_{0}$, the same guarantees as in Theorem
5.1 hold. Recall that Theorem 5.1 is composed of two parts: the algorithm of
Theorem 5.16 which computes a unit vector $\hat{u}$ with correlation
$1-320\min(\sigma^{2},\frac{1}{k})$ with $u$, and the clustering algorithm of
Theorem 5.17, which uses a unit vector $\hat{u}$ with such correlation in
order to cluster the samples.

For the algorithm of Theorem 5.16, we note that by Lemma 6.4, for $n\geqslant
n_{0}$, we have sum-of-squares proofs that, for $t=O(\log
p_{\mathrm{min}}^{-1})$,

$\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t}\leqslant\mathopen{}\mathclose{{}\left(1+\frac{\sigma^{2}}{10000M}}\right)\mathbb{E}\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}+\frac{\sigma^{2}}{10000M}$

and

$\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t}\geqslant\mathopen{}\mathclose{{}\left(1-\frac{\sigma^{2}}{10000M}}\right)\mathbb{E}\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}-\frac{\sigma^{2}}{10000M},$

where $\hat{W}(\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0})$ corresponds to the
mixture in approximate isotropic position and
$W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0})$ corresponds to the mixture in exact
isotropic position. It is easy to verify, similarly to the analysis of the
errors in the proof of Theorem 5.16, that these errors are tolerated by the
algorithm and that it behaves as if the distribution was in exact isotropic
position.

For the clustering algorithm of Theorem 5.17, the main issue is that the
samples are colinear in direction $\frac{\hat{W}u^{0}}{\|\hat{W}u^{0}\|}$, but
$\hat{u}$ is guaranteed to have large correlation with
$\frac{Wu^{0}}{\|Wu^{0}\|}$. We prove, nevertheless, that the algorithm has
the same guarantees. First, we show that the variance of the one-dimensional
components
$\hat{u}^{\top}\hat{W}^{\top}\Sigma^{0}\hat{W}\hat{u}/(2(C+1)\sigma^{2})$ is
upper bounded by $1$, as required by the algorithm of [HL18]. We have by Lemma
6.8 that, for $n\geqslant n_{0}$, with high probability

$|\|\hat{u}^{\top}W(\Sigma^{0})^{1/2}\|-\|\hat{u}^{\top}\hat{W}(\Sigma^{0})^{1/2}\||\leqslant\|\hat{u}^{\top}W(\Sigma^{0})^{1/2}-\hat{u}^{\top}\hat{W}(\Sigma^{0})^{1/2}\|\leqslant\sigma/100,$

so using that $\hat{u}^{\top}W\Sigma^{0}W^{T}\hat{u}\geqslant\sigma^{2}$,

$\hat{u}^{\top}W\Sigma^{0}W^{T}\hat{u}\geqslant\frac{1}{2}\hat{u}^{\top}\hat{W}\Sigma^{0}\hat{W}^{T}\hat{u}.$

Therefore, using from the proof of Theorem 5.17 that
$(\hat{u}^{\top}W^{\top}\Sigma^{0}W\hat{u})/(2(C+1)\sigma^{2})\leqslant 0.5$,

$\frac{\hat{u}^{\top}\hat{W}^{\top}\Sigma^{0}\hat{W}\hat{u}}{2(C+1)\sigma^{2}}\leqslant
2\frac{\hat{u}^{\top}W^{\top}\Sigma^{0}W\hat{u}}{2(C+1)\sigma^{2}}\leqslant
1.$

Second, we show that the one-dimensional means
$\langle\hat{W}(\mu_{i}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),\hat{u}\rangle$ have
large separation. We have by the proof of Theorem 5.17 that, for $n\geqslant
n_{0}$, with high probability

$\langle
W(\mu_{i}^{0}-\mu_{j}^{0}),\hat{u}\rangle^{2}\geqslant\frac{C_{sep}}{2}\sigma^{2}\log
p_{\mathrm{min}}^{-1}.$

We are interested in a similar bound with $W$ changed into $\hat{W}$. By Lemma
6.7, for $n\geqslant n_{0}$, we have with high probability

$|\langle
W(\mu_{i}^{0}-\mu_{j}^{0}),\hat{u}\rangle-\langle\hat{W}(\mu_{i}^{0}-\mu_{j}^{0}),\hat{u}\rangle|\leqslant\sigma/100,$

so using that $\langle
W(\mu_{i}^{0}-\mu_{j}^{0}),\hat{u}\rangle^{2}\geqslant\sigma^{2}$,

$\langle\hat{W}(\mu_{i}^{0}-\mu_{j}^{0}),\hat{u}\rangle^{2}\geqslant\frac{1}{2}\langle
W(\mu_{i}^{0}-\mu_{j}^{0}),\hat{u}\rangle^{2}.$

Therefore,

$\langle\hat{W}(\mu_{i}^{0}-\mu_{j}^{0}),\hat{u}\rangle^{2}\geqslant\frac{C_{sep}}{4}\sigma^{2}\log
p_{\mathrm{min}}^{-1},$

so

$\mathopen{}\mathclose{{}\left(\frac{\langle\hat{W}(\mu_{i}^{0}-\mu_{j}^{0}),\hat{u}\rangle}{\sqrt{2(C+1)\sigma^{2}}}}\right)^{2}\geqslant\frac{C_{sep}}{8(C+1)}\log
p_{\mathrm{min}}^{-1}.$

For $C_{sep}/C$ larger than some universal constant, the separation
coefficient $C_{sep}/(8(C+1))$ is large enough for the guarantees of Theorem
5.1 of [HL18] to hold as before with $t=O(\log p_{\mathrm{min}}^{-1})$.

Then, overall, the same guarantees as in Theorem 5.1 hold. ∎

## Acknowledgement

We thank Samuel B. Hopkins for the discussions related to this project.

## References

  * [BDH+20] Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K. Kothari, _Outlier-robust clustering of Gaussians and other non-spherical mixtures_ , 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, CA, [2020] ©2020, pp. 149–159. MR 4232031
  * [BS14] Boaz Barak and David Steurer, _Sum-of-squares proofs and the quest toward optimal algorithms_ , Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. IV, Kyung Moon Sa, Seoul, 2014, pp. 509–533. MR 3727623
  * [BV08] S. Charles Brubaker and Santosh Vempala, _Isotropic PCA and affine-invariant clustering_ , FOCS, IEEE Computer Society, 2008, pp. 551–560.
  * [Das99] Sanjoy Dasgupta, _Learning mixtures of gaussians_ , FOCS, IEEE Computer Society, 1999, pp. 634–644.
  * [DK20] Ilias Diakonikolas and Daniel M. Kane, _Small covers for near-zero sets of polynomials and learning latent variable models_ , 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, CA, [2020] ©2020, pp. 184–195. MR 4232034
  * [DKK+19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart, _Robust estimators in high-dimensions without the computational intractability_ , SIAM J. Comput. 48 (2019), no. 2, 742–864. MR 3945261
  * [DKS17] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart, _Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures (extended abstract)_ , 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp. 73–84. MR 3734219
  * [DKS18] , _List-decodable robust mean estimation and learning mixtures of spherical Gaussians_ , STOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2018, pp. 1047–1060. MR 3826316
  * [GHK15] Rong Ge, Qingqing Huang, and Sham M. Kakade, _Learning mixtures of gaussians in high dimensions_ , STOC, ACM, 2015, pp. 761–770.
  * [HK13] Daniel Hsu and Sham M. Kakade, _Learning mixtures of spherical Gaussians: moment methods and spectral decompositions_ , ITCS’13—Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, ACM, New York, 2013, pp. 11–19. MR 3385380
  * [HL18] Samuel B. Hopkins and Jerry Li, _Mixture models, robustness, and sum of squares proofs_ , STOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2018, pp. 1021–1034. MR 3826314
  * [KMV10] Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant, _Efficiently learning mixtures of two gaussians_ , STOC, ACM, 2010, pp. 553–562.
  * [KS17] Pravesh K. Kothari and David Steurer, _Outlier-robust moment-estimation via sum-of-squares_ , CoRR abs/1711.11581 (2017).
  * [KSS18] Pravesh K. Kothari, Jacob Steinhardt, and David Steurer, _Robust moment estimation and improved clustering via sum of squares_ , STOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2018, pp. 1035–1046. MR 3826315
  * [LM21] Allen Liu and Ankur Moitra, _Settling the robust learnability of mixtures of gaussians_ , STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, ACM, 2021, pp. 518–531.
  * [MV10] Ankur Moitra and Gregory Valiant, _Settling the polynomial learnability of mixtures of gaussians_ , FOCS, IEEE Computer Society, 2010, pp. 93–102.
  * [Pea94] Karl Pearson, _Contributions to the mathematical theory of evolution_ , Philosophical Transactions of the Royal Society of London. A 185 (1894), 71–110.
  * [Pol02] David Pollard, _A user’s guide to measure theoretic probability_ , no. 8, Cambridge University Press, 2002.
  * [RSS18] Prasad Raghavendra, Tselil Schramm, and David Steurer, _High dimensional estimation via sum-of-squares proofs_ , Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 3389–3423. MR 3966537
  * [VW02] Santosh Vempala and Grant Wang, _A spectral algorithm for learning mixtures of distributions_ , FOCS, IEEE Computer Society, 2002, p. 113.

##  Appendix A Appendix

###  A.1 Bipartition from distance function

The following lemma applies in the setting of Section 4.

######  Lemma A.1 (Bipartition from distance function).

Assume access to a distance function
$d:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ such that:

  * •

There exist distinct $a,b\in[k]$ such that the independent random vectors
$\bm{y}\sim N(\mu_{a},\Sigma)$ and $\bm{y}^{\prime}\sim N(\mu_{b},\Sigma)$
satisfy

$\operatorname*{\mathbb{P}}\mathopen{}\mathclose{{}\left\\{d(\bm{y},\bm{y}^{\prime})\geqslant\frac{1}{\sqrt{8}}}\right\\}\geqslant
0.99999.\,$

  * •

For all $a\in[k]$, the independent random vectors $\bm{y},\bm{y}^{\prime}\sim
N(\mu_{a},\Sigma)$ satisfy

$\operatorname*{\mathbb{P}}\mathopen{}\mathclose{{}\left\\{d(\bm{y},\bm{y}^{\prime})\leqslant\frac{1}{\sqrt{80}}}\right\\}\geqslant
0.99999.\,$

Given a sample of size $n=\Omega(p_{\mathrm{min}}^{-1})$ from the mixture,
there exists a polynomial-time algorithm that returns with probability $0.99$
a partition of $[n]$ into two sets $C_{1}$ and $C_{2}$ such that, if true
clustering of the samples is $S_{1},...,S_{k}$, then

$\max_{i}\frac{|C_{1}\cap S_{i}|}{|S_{i}|}\geqslant
0.99\quad\text{and}\quad\max_{i}\frac{|C_{2}\cap S_{i}|}{|S_{i}|}\geqslant
0.99.$

###### Proof.

The algorithm is:

  1. 1.

Choose $i\in[n]$ uniformly at random.

  2. 2.

Let $S=\\{j\in[n]:d(y_{i},y_{j})\leqslant\frac{1}{\sqrt{80}}\\}$.

  3. 3.

Return $S$ and $[n]\setminus S$.

We now analyze the algorithm.

First, we prove that, with probability at least $0.995$, a $0.99$-fraction of
the samples from the same component as $i$ are included in $S$. With high
probability, a $0.99998$-fraction of the pairs of samples $(y,y^{\prime})$
with $y$ and $y^{\prime}$ from the same component as $i$ satisfy
$d(y,y^{\prime})\leqslant\frac{1}{\sqrt{80}}$. Then, the fraction of samples
from this component that are farther than $\frac{1}{\sqrt{80}}$ from more than
a $0.01$-fraction of the other samples in the component is at most
$\frac{1-0.99998}{0.01}=0.002$. Then, overall, with probability at least
$0.995$, $i$ is closer than $\frac{1}{\sqrt{80}}$ to at least a
$0.99$-fraction of the other samples in the component. In this case, $S$
includes a $0.99$-fraction of the samples from the same component as $i$.

Second, we prove that, with probability at least $0.995$, at least a
$0.99$-fraction of the samples from one of the components are not included in
$S$. Let $a,b\in[k]$ be the two components for which the large-distance
guarantee holds. With high probability, a $0.99998$-fraction of the pairs of
samples $(y,y^{\prime})$ with $y$ from $a$ and $y^{\prime}$ from $b$ satisfy
$d(y,y^{\prime})\geqslant\frac{1}{\sqrt{8}}$. We have
$d(y,y^{\prime})\leqslant d(y,y_{i})+d(y^{\prime},y_{i})$, so if
$d(y,y^{\prime})\geqslant\frac{1}{\sqrt{8}}$, then at least one of
$d(y,y_{i})$ or $d(y^{\prime},y_{i})$ is at least
$\frac{1}{2\sqrt{8}}>\frac{1}{\sqrt{80}}$. Then, for such pairs, it is
impossible for both $y$ and $y^{\prime}$ to be in $S$. Suppose that a
$q_{a}$-fraction of the samples from $a$ are in $S$ and that a
$q_{b}$-fraction of the samples from $b$ are in $S$. We need then that
$1-q_{a}q_{b}\geqslant 0.99998$, so
$\min(q_{a},q_{b})\leqslant\sqrt{1-0.9998}\leqslant 0.01$. Therefore,
$[n]\setminus S$ contains at least a $0.99$-fraction of the samples from one
of $a$ or $b$.

Therefore, with probability at least $0.99$, the conclusion of the lemma
holds. ∎

###  A.2 Sum-of-squares lemmas

We first prove a number of useful SOS facts.

######  Lemma A.2 (Restatement of Lemma A.1 in [KS17]).

For variables $X_{1},...,X_{t}\in\mathbb{R}$,

$\sststile{t}{X}X_{1}\cdot...\cdot
X_{t}\leqslant\frac{1}{t}(X_{1}^{t}+...+X_{t}^{t}).$

######  Lemma A.3 (Restatement of Lemma A.2 in [KS17]).

For variables $A,B\in\mathbb{R}$ and $t\geqslant 2$ even,

$\sststile{t}{A,B}(A+B)^{t}\leqslant 2^{t-1}A^{2t}+2^{t-1}B^{t}.$

######  Lemma A.4.

For variables $A,B\in\mathbb{R}$ and $\delta>0$ and $t\geqslant 2$ even,

$\sststile{2t}{A,B}(A+B)^{2t}\leqslant(1+\delta)^{2t-1}A^{2t}+\mathopen{}\mathclose{{}\left(1+\frac{1}{\delta}}\right)B^{2t}.$

###### Proof.

$\displaystyle\sststile{t}{A,B}(A+B)^{t}$
$\displaystyle=\sum_{s=0}^{t}\binom{t}{s}A^{s}B^{t-s}$
$\displaystyle=\sum_{s=0}^{t}\binom{t}{s}\mathopen{}\mathclose{{}\left(\delta^{1-s/t}A}\right)^{s}\mathopen{}\mathclose{{}\left(\frac{1}{\delta^{s/t}}B}\right)^{t-s}$
$\displaystyle\stackrel{{\scriptstyle(1)}}{{\leqslant}}\sum_{s=0}^{t}\binom{t}{s}\mathopen{}\mathclose{{}\left(\frac{s}{t}\mathopen{}\mathclose{{}\left(\delta^{1-s/t}A}\right)^{t}+\frac{t-s}{s}\mathopen{}\mathclose{{}\left(\frac{1}{\delta^{s/t}}B}\right)^{t}}\right)$
$\displaystyle=\mathopen{}\mathclose{{}\left(\sum_{s=0}^{t}\binom{t}{s}\frac{s}{t}\delta^{t-s}}\right)A^{t}+\mathopen{}\mathclose{{}\left(\sum_{s=0}^{t}\binom{t}{s}\frac{t-s}{t}\frac{1}{\delta^{s}}}\right)B^{t}$
$\displaystyle\stackrel{{\scriptstyle(2)}}{{=}}(1+\delta)^{t-1}A^{t}+\mathopen{}\mathclose{{}\left(1+\frac{1}{\delta}}\right)^{t-1}B^{t}$

where in (1) we used Lemma A.2 and in (2) we used the identities

$\sum_{s=0}^{t}\binom{t}{s}\frac{s}{t}x^{t-s}=\sum_{s=0}^{t-1}\binom{t-1}{s}x^{t-1-s}=(1+x)^{t-1}$

and

$\sum_{s=0}^{t}\binom{t}{s}\frac{t-s}{t}x^{s}=\sum_{s=0}^{t-1}\binom{t-1}{s}x^{s}=(1+x)^{t-1}.$

∎

######  Lemma A.5.

For variable $X\in\mathbb{R}$ and $t\geqslant 0$ integer,

$\\{X\geqslant 0\\}\sststile{t}{X}\\{X^{t}\geqslant 0\\}.$

###### Proof.

For $t$ even, $\sststile{t}{X}X^{t}\geqslant 0$ is trivial. For $t$ odd, we
have that $\sststile{t}{X}X^{t}=X^{t-1}X\geqslant 0$, where we used that
$\sststile{t-1}{X}X^{t-1}\geqslant 0$ because $t-1$ is even. ∎

######  Lemma A.6.

For variable $X\in\mathbb{R}$ and $t\geqslant 1$ integer,

$\\{0\leqslant X\leqslant 1\\}\sststile{t}{X}\\{X^{t}\leqslant 1\\}.$

###### Proof.

We have $\sststile{X}{t}1-X^{t}=(1-X)(1+X+...+X^{t-1})\geqslant 0$, where we
used that, by Lemma A.5, $\sststile{i}{X}X^{i}\geqslant 0$ for
$i\in\\{0,...,t-1\\}$. ∎

######  Lemma A.7 (Restatement of Lemma A.3 in [KS17]).

For variable $X\in\mathbb{R}$ and $t\geqslant 2$ even,

$\\{X^{t}\leqslant 1\\}\sststile{t}{X}\\{X\leqslant 1\\}.$

######  Lemma A.8.

For variables $u,v\in\mathbb{R}^{d}$,

$\sststile{2}{u,v}\langle u,v\rangle^{2}\leqslant\|u\|^{2}\cdot\|v\|^{2}.$

###### Proof.

By Lagrange’s identity,

$\langle
u,v\rangle^{2}=\|u\|^{2}\cdot\|v\|^{2}+\sum_{i=1}^{d-1}\sum_{j=i+1}^{d}(u_{i}v_{j}-u_{j}v_{j})^{2},$

so

$\sststile{2}{u,v}\langle u,v\rangle^{2}\leqslant\|u\|^{2}\cdot\|v\|^{2}.$

∎

######  Lemma A.9.

For variable $X\in\mathbb{R}$ and $\delta\in\mathbb{R}$ and $t\geqslant 1$
integer,

$\\{0\leqslant X\leqslant
1,X^{t}\geqslant\delta\\}\sststile{t}{X}\\{X\geqslant\delta\\}.$

###### Proof.

We have
$\sststile{t}{X}X=(X^{t}-\delta)+(1-X)(1+X+...+X^{t-1})+\delta\geqslant\delta$,
where we used that, by Lemma A.5, $\sststile{i}{}X^{i}\geqslant 0$ for
$i\in\\{0,...,t-1\\}$. ∎

######  Lemma A.10.

For variable $X\in\mathbb{R}$ and $C\geqslant 2$ and $t\geqslant 1$ integer,

$\mathopen{}\mathclose{{}\left\\{0\leqslant
X\leqslant\frac{1}{Ct}}\right\\}\sststile{t}{}\mathopen{}\mathclose{{}\left\\{(1-X)^{t}\leqslant
1-\frac{C-2}{C-1}tX}\right\\}.$

###### Proof.

We have that

$\displaystyle\sststile{t}{X}(1-X)^{t}$
$\displaystyle=1-tX+\sum_{i=2}^{t}\binom{t}{i}(-1)^{i}X^{i}\stackrel{{\scriptstyle(1)}}{{\leqslant}}1-tX+\sum_{i=2}^{t}\binom{t}{i}X^{i}$
$\displaystyle\stackrel{{\scriptstyle(2)}}{{\leqslant}}1-tX+\sum_{i=2}^{t}t^{i}X^{i}=1-tX+tX\sum_{i=1}^{t-1}t^{i}X^{i}$
$\displaystyle\stackrel{{\scriptstyle(3)}}{{\leqslant}}1-tX+tX\sum_{i=1}^{t-1}\frac{1}{C^{i}}\stackrel{{\scriptstyle(4)}}{{\leqslant}}1-tX+\frac{1}{C-1}tX$
$\displaystyle=1-\frac{C-2}{C-1}tX.$

We use throughout that, by Lemma A.5, $\sststile{i}{X}X^{i}\geqslant 0$ for
$i\in\\{0,...,t\\}$. In (1) we used that $\sststile{i}{X}-X^{i}\leqslant
X^{i}$. In (2) we used that $\binom{t}{i}\leqslant t^{i}$. In (3) we used that
$\sststile{1}{}0\leqslant X\leqslant\frac{1}{Ct}$ implies that
$\sststile{i+1}{}0\leqslant X^{i+1}\leqslant\frac{1}{(Ct)^{i}}X$. The upper
bound is true because

$\sststile{i+1}{}\frac{1}{(Ct)^{i}}X-X^{i+1}=\mathopen{}\mathclose{{}\left(\frac{1}{Ct}-X}\right)\mathopen{}\mathclose{{}\left(\sum_{j=0}^{i-1}\frac{1}{(Ct)^{j}}X^{i-1-j}}\right)X\geqslant
0.$

In (4) we used that
$\sum_{i=1}^{t-1}\frac{1}{C^{i}}\leqslant\sum_{i=1}^{\infty}\frac{1}{C^{i}}=\frac{1}{1-\frac{1}{C}}-1=\frac{1}{C-1}$.
∎

######  Lemma A.11 (Restatement of Claim 1.5 in [RSS18]).

If $\tilde{\mathbb{E}}$ is a degree-$d$ pseudo-expectation and if $p,q$ are
polynomials of degree at most $\frac{d}{2}$, then
$\tilde{\mathbb{E}}[q(x)\cdot
p(x)]\leqslant\frac{1}{2}\tilde{\mathbb{E}}[q(x)^{2}]+\frac{1}{2}\tilde{\mathbb{E}}[p(x)^{2}]$.

######  Lemma A.12.

If $\tilde{\mathbb{E}}$ is a degree-$d$ pseudo-expectation and if $p$ is a
polynomial of degree at most $\frac{d}{2}$, then
$(\tilde{\mathbb{E}}[p(x)])^{2}\leqslant\tilde{\mathbb{E}}[p(x)^{2}]$.

###### Proof.

Let $\tilde{\mathbb{E}}_{x}$ be the given pseudo-expectation over $x$, and let
$\tilde{\mathbb{E}}_{x^{\prime}}$ be a copy of the given pseudo-expectaiton
but over $x^{\prime}$ instead of $x$. Then we have

$(\tilde{\mathbb{E}}_{x}[p(x)])^{2}=(\tilde{\mathbb{E}}_{x}[p(x)])(\tilde{\mathbb{E}}_{x^{\prime}}[p(x^{\prime})])=\tilde{\mathbb{E}}_{x,x^{\prime}}[p(x)p(x^{\prime})].$

Then, by Lemma A.11,

$(\tilde{\mathbb{E}}_{x}[p(x)])^{2}\leqslant\frac{1}{2}\tilde{\mathbb{E}}_{x,x^{\prime}}[p(x)^{2}]+\frac{1}{2}\tilde{\mathbb{E}}_{x,x^{\prime}}[p(x^{\prime})^{2}]=\tilde{\mathbb{E}}_{x}[p(x)^{2}].$

∎

We give now some sum-of-squares proofs that are more specific to our setting.
The purpose of Lemma A.13 and Lemma A.14 is to aid in transforming some sum-
of-squares proofs about polynomials $p(x)$ and $q(x)$ into sum-of-squares
proofs about polynomials $p(x)^{t}$ and $q(x)^{t}$. Lemma A.13 shows that,
under some conditions, if $\\{p(x)\geqslant 1\\}\sststile{}{}\\{q(x)\geqslant
1\\}$, then also $\\{p(x)^{t}\geqslant 1\\}\sststile{}{}\\{q(x)^{t}\geqslant
1\\}$, while Lemma A.14 shows that, again under some conditions, if
$\\{p(x)\leqslant 1\\}\sststile{}{}\\{q(x)\geqslant 1\\}$, then also
$\\{p(x)^{t}\leqslant 1\\}\sststile{}{}\\{q(x)^{t}\geqslant 1\\}$. These are
used in Lemma A.15 and Lemma A.16, which implement sum-of-squares proofs with
some polynomials raised to the $t$-th power.

######  Lemma A.13.

Let $p,q:\mathbb{R}\to\mathbb{R}$ with $p(x)\geqslant 0$ for all
$x\in\mathbb{R}$. Let $\gamma>1$ be a real number and $t\geqslant 2$ be an
even integer. Suppose that, for all $x\in\mathbb{R}$,
$q(x)-1-\gamma(p(x)-1)\geqslant 0$. Then, for all $x\in\mathbb{R}$,

$q(x)^{t}-1-\gamma(p(x)^{t}-1)\geqslant 0.$

###### Proof.

We consider two cases. First, suppose that $1+\gamma(p(x)-1)<0$. This implies
that $p(x)<1-\frac{1}{\gamma}$, which implies that
$1+\gamma(p(x)^{t}-1)<1+\gamma(p(x)-1)<0$. Therefore $q(x)^{t}\geqslant
1+\gamma(p(x)^{t}-1)$ is satisfied trivially for $t$ even.

Second, suppose that $1+\gamma(p(x)-1)\geqslant 0$. Then the given assumption
implies that
${q(x)^{t}\geqslant\mathopen{}\mathclose{{}\left(1+\gamma(p(x)-1)}\right)^{t}}$.
Then

$q(x)^{t}-1-\gamma(p(x)^{t}-1)\geqslant\mathopen{}\mathclose{{}\left(1+\gamma(p(x)-1)}\right)^{t}-1-\gamma(p(x)^{t}-1).$

To show that the expression on the right-hand side is non-negative, it
suffices to show that

$f(x)=\mathopen{}\mathclose{{}\left(1+\gamma(x-1)}\right)^{t}-1-\gamma(x^{t}-1)$

is non-negative everywhere. For $\gamma>1$, we have that
$\lim_{x\to-\infty}f(x)=\infty$ and $\lim_{x\to\infty}f(x)=\infty$. Then, it
suffices to show that $f(x)$ is non-negative at all its critical points. We
have

$\frac{d}{dx}f(x)=\gamma t(\gamma(x-1)+1)^{t-1}-\gamma tx^{t-1},$

so

$\frac{d}{dx}f(x)=0\Longleftrightarrow\gamma(x-1)+1=x\Longleftrightarrow x=1.$

We have $f(1)=0\geqslant 0$. Therefore, $f(x)\geqslant 0$ for all
$x\in\mathbb{R}$.

∎

######  Lemma A.14.

Let $p,q:\mathbb{R}\to\mathbb{R}$ for all $x\in\mathbb{R}$. Let $\gamma>0$ be
a real number and $t\geqslant 2$ be an even integer. Suppose that, for all
$x\in\mathbb{R}$, $q(x)-1-\gamma(1-p(x))\geqslant 0$. Then, for all
$x\in\mathbb{R}$,

$q(x)^{t}-1-\gamma(1-p(x)^{t})\geqslant 0.$

###### Proof.

We consider two cases. First, suppose that $1+\gamma(1-p(x))<0$. This implies
that $p(x)>1+\frac{1}{\gamma}$, which implies that
$1+\gamma(1-p(x)^{t})<1+\gamma(1-p(x))<0$. Therefore $q(x)^{t}\geqslant
1+\gamma(1-p(x)^{t})$ is satisfied trivially for $t$ even.

Second, suppose that $1+\gamma(1-p(x))\geqslant 0$. Then the given assumption
implies that
${q(x)^{t}\geqslant\mathopen{}\mathclose{{}\left(1+\gamma(1-p(x))}\right)^{t}}$.
Then

$q(x)^{t}-1-\gamma(1-p(x)^{t})\geqslant\mathopen{}\mathclose{{}\left(1+\gamma(1-p(x))}\right)^{t}-1-\gamma(1-p(x)^{t}).$

To show that the expression on the right-hand side, it suffices to show that

$f(x)=\mathopen{}\mathclose{{}\left(1+\gamma(1-x)}\right)^{t}-1-\gamma(1-x^{t})$

is non-negative everywhere. For $\gamma>0$, we have that
$\lim_{x\to-\infty}f(x)=\infty$ and $\lim_{x\to\infty}f(x)=\infty$. Then, it
suffices to show that $f(x)$ is non-negative at all its critical points. We
have

$\frac{d}{dx}f(x)=\gamma tx^{t-1}-\gamma t(\gamma(1-x)+1)^{t-1},$

so

$\frac{d}{dx}f(x)=0\Longleftrightarrow x=\gamma(1-x)+1\Longleftrightarrow
x=1.$

We have $f(1)=0\geqslant 0$. Therefore, $f(x)\geqslant 0$ for all
$x\in\mathbb{R}$.

∎

Lemma A.15, which is used in Lemma 5.11, provides a sum-of-squares proof that
if
$\mathopen{}\mathclose{{}\left(x^{2}+\frac{1}{M}(1-(1-\sigma^{2})x^{2})}\right)^{t}\geqslant\frac{1}{\gamma^{t}}$,
then
$x^{2t}\geqslant\mathopen{}\mathclose{{}\left(\frac{M-\gamma}{\gamma}\frac{1}{M-1+\sigma^{2}}}\right)^{t}$.

######  Lemma A.15.

For a variable $x\in\mathbb{R}$ and for $0\leqslant\sigma^{2}<1$ and
$0<\gamma<M$ and $M\geqslant 2$, we have that

$\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(x^{2}+\frac{1}{M}(1-(1-\sigma^{2})x^{2})}\right)}\right)^{t}\geqslant
1}\right\\}\sststile{2t}{}\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(\frac{\gamma}{M-\gamma}(M-1+\sigma^{2})x^{2}}\right)^{t}\geqslant
1}\right\\}.$

###### Proof.

Let

$p(x)=\gamma\mathopen{}\mathclose{{}\left(x^{2}+\frac{1}{M}(1-(1-\sigma^{2})x^{2})}\right)=\gamma\mathopen{}\mathclose{{}\left(\frac{M-1+\sigma^{2}}{M}x^{2}+\frac{1}{M}}\right)$

and

$q(x)=\delta(M-1+\sigma^{2})x^{2},$

for some $\delta>0$ to be determined later. Note that $p(x)\geqslant 0$ for
all $x\in\mathbb{R}$.

We check now that, for all $x\in\mathbb{R}$,

$q(x)-1-\frac{M\delta}{\gamma}(p(x)-1)\geqslant 0,$

which corresponds to a sum-of-squares proof that $\\{p(x)\geqslant
1\\}\sststile{}{}\\{q(x)\geqslant 1\\}$. We note that the coefficient
$\frac{M\delta}{\gamma}$ was chosen such that $x^{2}$ cancels. We have then

$\displaystyle
q(x)-1-\frac{M\delta}{\gamma}(p(x)-1)=-1-\frac{M\delta}{\gamma}\mathopen{}\mathclose{{}\left(\frac{\gamma}{M}-1}\right)=\frac{M\delta}{\gamma}-1-\delta.$

Set $\delta=\frac{\gamma}{M-\gamma}$, which makes the term equal to $0$.
Therefore, for all $x\in\mathbb{R}$,

$q(x)-1-\frac{2\frac{\gamma}{M-\gamma}}{\gamma}(p(x)-1)\geqslant 0.$

Therefore, by Lemma A.13, for all $x\in\mathbb{R}$,

$f(x)=q(x)^{t}-1-\frac{2\frac{\gamma}{M-\gamma}}{\gamma}(p(x)^{t}-1)\geqslant
0.$

Because $f(x)$ is a univariate polynomial of degree $2t$, there also exists a
sum-of-squares proof of degree at most $2t$ that $f(x)\geqslant 0$. Note that
this constitutes a degree-$2t$ sum-of-squares proof that $\\{p(x)^{t}\geqslant
1\\}\sststile{}{}\\{q(x)^{t}\geqslant 1\\}$. This concludes the proof.

∎

Lemma A.16, which is used in Lemma 5.12, provides a sum-of-squares proof that
if
$\mathopen{}\mathclose{{}\left(\frac{x^{2}+\Delta(1-(1-\sigma^{2})x^{2})}{1+8\Delta\sigma^{2}}}\right)^{t}\leqslant\frac{1}{\gamma^{t}}$,
then
$x^{2t}\geqslant\mathopen{}\mathclose{{}\left(\frac{\gamma\Delta-1}{\gamma(\Delta-1)}(1-10\sigma^{2})}\right)^{t}$.

######  Lemma A.16.

For a variable $x\in\mathbb{R}$ and for $0\leqslant\sigma^{2}<0.1$ and
$\Delta\geqslant 10$ and $t$ even and $\gamma\geqslant 0.9$, we have that

$\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(\gamma\frac{x^{2}+\Delta(1-(1-\sigma^{2})x^{2})}{1+8\Delta\sigma^{2}}}\right)^{t}\leqslant
1}\right\\}\sststile{2t}{}\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(\frac{\gamma(\Delta-1)}{\gamma\Delta-1}\frac{x^{2}}{1-10\sigma^{2}}}\right)^{t}\geqslant
1}\right\\}.$

###### Proof.

Note that we need $\sigma^{2}<0.1$ in order to have $1-10\sigma^{2}>0$.

Let

$p(x)=\gamma\frac{x^{2}+\Delta(1-(1-\sigma^{2})x^{2})}{1+8\Delta\sigma^{2}}=\gamma\frac{\mathopen{}\mathclose{{}\left(1-\Delta(1-\sigma^{2})}\right)x^{2}+\Delta}{1+8\Delta\sigma^{2}}$

and

$q(x)=\delta\frac{x^{2}}{1-10\sigma^{2}},$

for some $\delta>0$ to be determined later.

We check now that, for all $x\in\mathbb{R}$,

$q(x)-1-\frac{\delta(1+8\Delta\sigma^{2})}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}(1-p(x))\geqslant
0,$

which corresponds to a sum-of-squares proof that $\\{p(x)\leqslant
1\\}\sststile{}{}\\{q(x)\geqslant 1\\}$. We note that the coefficient
$\frac{\delta(1+8\Delta\sigma^{2})}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}$
was chosen such that $x^{2}$ cancels. We have then

$\displaystyle
q(x)-1-\frac{\delta(1+8\Delta\sigma^{2})}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}(1-p(x))$
$\displaystyle\quad=-1-\frac{\delta(1+8\Delta\sigma^{2})}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}\mathopen{}\mathclose{{}\left(1-\frac{\gamma\Delta}{1+8\Delta\sigma^{2}}}\right)$
$\displaystyle\quad=-1-\frac{\delta(1+8\Delta\sigma^{2})}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}\frac{1+8\Delta\sigma^{2}-\gamma\Delta}{1+8\Delta\sigma^{2}}$
$\displaystyle\quad=-1-\frac{\delta(1+8\Delta\sigma^{2}-\gamma\Delta)}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}$
$\displaystyle\quad=\frac{-\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})-\delta(1+8\Delta\sigma^{2}-\gamma\Delta)}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}$
$\displaystyle\quad=\frac{(-10\gamma\Delta)\sigma^{4}+(11\gamma\Delta-10\gamma-8\delta\Delta)\sigma^{2}+(\gamma\delta\Delta-\gamma\Delta+\gamma-\delta)}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}.$

Note that the denominator is positive. Set
$\delta=\frac{\gamma(\Delta-1)}{\gamma\Delta-1}$. Then the numerator, viewed
as a quadratic in $\sigma^{2}$, has roots at $0$ and at
$\frac{11\gamma\Delta^{2}-10\gamma\Delta-8\Delta^{2}-3\Delta+10}{10\Delta(\gamma\Delta-1)}$.
Furthermore, when the second root is positive, the quadratic is also positive
for all $\sigma^{2}$ between the two roots. Hence, in order to prove that the
expression is positive for all $0\leqslant\sigma^{2}<0.1$, it suffices to show
that the second root is at least $0.1$ in our setting. Indeed, for all
$\gamma\geqslant 0.9$ and all $\Delta\geqslant 10$, we have that
$\frac{11\gamma\Delta^{2}-10\gamma\Delta-8\Delta^{2}-3\Delta+10}{10\Delta(\gamma\Delta-1)}\geqslant
0.1$.

Therefore, for all $x\in\mathbb{R}$,

$f(x)=q(x)-1-\frac{\frac{\gamma(\Delta-1)}{\gamma\Delta-1}(1+8\Delta\sigma^{2})}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}(1-p(x))\geqslant
0.$

Therefore, by Lemma A.14, for all $x\in\mathbb{R}$,

$f(x)=q(x)^{t}-1-\frac{\frac{\gamma(\Delta-1)}{\gamma\Delta-1}(1+8\Delta\sigma^{2})}{\gamma(\Delta(1-\sigma^{2})-1)(1-10\sigma^{2})}(1-p(x)^{t})\geqslant
0.$

Because $f(x)$ is a univariate polynomial of degree $2t$, there also exists a
sum-of-squares proof of degree at most $2t$ that $f(x)\geqslant 0$. Note that
this constitutes a degree-$2t$ sum-of-squares proof that $\\{p(x)^{t}\leqslant
1\\}\sststile{}{}\\{q(x)^{t}\geqslant 1\\}$. This concludes the proof.

∎

###  A.3 Finite sample lemmas

######  Lemma A.17 (Restatement of Theorem 4 in [BV08]).

For $n\geqslant C\frac{kd\log^{2}(d/\delta)}{\varepsilon^{2}}$, with
probability $1-\delta$,

$\|\operatorname{cov}(\bm{y}^{0})^{-1/2}(\hat{\mathbb{E}}\bm{y}^{0}-\mathbb{E}\bm{y}^{0})\|\leqslant\varepsilon$

and

$\|I_{d}-\operatorname{cov}(\bm{y}^{0})^{-1/2}\widehat{\operatorname{cov}}(\bm{y}^{0})\operatorname{cov}(\bm{y}^{0})^{-1/2}\|\leqslant\varepsilon.$

######  Lemma A.18.

For $n\geqslant C\frac{kd\log^{2}(d/\delta)}{\varepsilon^{2}}$, with
probability $1-\delta$,

$\|I_{d}-\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1/2}\operatorname{cov}(\bm{y}^{0})\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1/2}\|\leqslant\varepsilon.$

###### Proof.

By Lemma A.17,

$\|I_{d}-\operatorname{cov}(\bm{y}^{0})^{-1/2}\widehat{\operatorname{cov}}(\bm{y}^{0})\operatorname{cov}(\bm{y}^{0})^{-1/2}\|\leqslant
2\varepsilon.$

Then

$(1-\varepsilon)I_{d}\preceq\operatorname{cov}(\bm{y}^{0})^{-1/2}\widehat{\operatorname{cov}}(\bm{y}^{0})\operatorname{cov}(\bm{y}^{0})^{-1/2}\preceq(1+\varepsilon)I_{d},$
$(1-\varepsilon)\operatorname{cov}(\bm{y}^{0})\preceq\widehat{\operatorname{cov}}(\bm{y}^{0})\preceq(1+\varepsilon)\operatorname{cov}(\bm{y}^{0}),$
$\frac{1}{1+\varepsilon}\widehat{\operatorname{cov}}(\bm{y}^{0})\preceq\operatorname{cov}(\bm{y}^{0})\preceq\frac{1}{1-\varepsilon}\widehat{\operatorname{cov}}(\bm{y}^{0}).$

Using that $\frac{1}{1+\varepsilon}\geqslant 1-2\varepsilon$ and
$\frac{1}{1-\varepsilon}\leqslant 1+2\varepsilon$ for $\varepsilon\leqslant
1/2$,

$(1-2\varepsilon)\widehat{\operatorname{cov}}(\bm{y}^{0})\preceq\operatorname{cov}(\bm{y}^{0})\preceq(1+2\varepsilon)\widehat{\operatorname{cov}}(\bm{y}^{0}),$
$(1-2\varepsilon)I_{d}\preceq\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1/2}\operatorname{cov}(\bm{y}^{0})\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1/2}\preceq(1+2\varepsilon)I_{d},$
$\|I_{d}-\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1/2}\operatorname{cov}(\bm{y}^{0})\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1/2}\|\leqslant
2\varepsilon.$

∎

######  Lemma A.19 (Restatement of Lemma 22 in [MV10]).

Let the random variable $\overline{\bm{y}}\in\mathbb{R}$ be distributed
according to an istotropic mixture of $k$ one-dimensional Gaussian
distributions with minimum mixing weight $p_{\mathrm{min}}$. Let
$\overline{y}_{1},...,\overline{y}_{n}\in\mathbb{R}$ be generated i.i.d.
according to the distribution of $\overline{\bm{y}}$. Then, with probability
$1-\delta$,

$\mathopen{}\mathclose{{}\left(\frac{1}{n}\sum_{i=1}^{n}\overline{y}_{i}^{t}-\mathbb{E}\overline{\bm{y}}^{t}}\right)^{2}\leqslant\frac{1}{n\delta}p_{\mathrm{min}}^{-O(t)}.$

######  Lemma A.20.

Let the random variable $\bm{y}\in\mathbb{R}^{d}$ be distributed according to
an istotropic mixture of $k$ $d$-dimensional Gaussian distributions with
minimum mixing weight $p_{\mathrm{min}}$. Let
$y_{1},...,y_{n}\in\mathbb{R}^{d}$ be generated i.i.d. according to the
distribution of $\bm{y}$. Then, with probability $1-d^{t}\delta$,

$\mathopen{}\mathclose{{}\left\|\frac{1}{n}\sum_{i=1}^{n}y_{i}^{\otimes
t}-\mathbb{E}\bm{y}^{\otimes
t}}\right\|^{2}\leqslant\frac{1}{n\delta}(p_{\mathrm{min}}^{-1}d)^{O(t)}.$

###### Proof.

The proof is similar to the proof of Lemma 22 in [MV10].

We denote by $\bm{y}^{(j)}$ the $j$-th coordinate of $\bm{y}$. Let
$\alpha\in\mathbb{N}^{d}$ satisfy $\sum_{j=1}^{d}\alpha_{j}=t$. Let
$\bm{z}^{\alpha}=\prod_{j=1}^{d}(\bm{y}^{(j)})^{\alpha_{j}}$. By Chebyshev’s
inequality, with probability at least $1-\delta$,

$\mathopen{}\mathclose{{}\left(\frac{1}{n}\sum_{i=1}^{n}z_{i}^{\alpha}-\mathbb{E}\bm{z}^{\alpha}}\right)^{2}\leqslant\frac{1}{\delta}\mathbb{E}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\frac{1}{n}\sum_{i=1}^{n}z_{i}^{\alpha}-\mathbb{E}\bm{z}^{\alpha}}\right)^{2}}\right].$

We now bound the right-hand side. Note that
$\mathbb{E}[\frac{1}{n}\sum_{i=1}^{n}z_{i}^{\alpha}-\mathbb{E}\bm{z}^{\alpha}]=0$.
Using that for independent random variables the variance of the sum is equal
to the sum of the variances,

$\displaystyle\mathbb{E}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\frac{1}{n}\sum_{i=1}^{n}z_{i}^{\alpha}-\mathbb{E}\bm{z}^{\alpha}}\right)^{2}}\right]=\frac{1}{n}\mathbb{E}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\bm{z}^{\alpha}-\mathbb{E}\bm{z}^{\alpha}}\right)^{2}}\right]\leqslant\frac{1}{n}\mathbb{E}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\bm{z}^{\alpha}}\right)^{2}}\right]\leqslant\frac{1}{n}p_{\mathrm{min}}^{-O(t)}.$

The last inequality follows by using that
$\mathbb{E}(\bm{y}^{(j)})^{t}\leqslant p_{\mathrm{min}}^{-O(t)}$ for all $j$
and that, for random varaibles $\bm{x}_{1},...,\bm{x}_{t}\in\mathbb{R}$,
$|\mathbb{E}[\bm{x}_{1}\cdot...\cdot\bm{x}_{t}]|\leqslant(\mathbb{E}\bm{x}_{1}^{t}\cdot...\cdot\mathbb{E}\bm{x}_{t}^{t})^{1/t}$.
Then, by a union bound, with probability at least $1-d^{t}\delta$,

$\mathopen{}\mathclose{{}\left\|\frac{1}{n}\sum_{i=1}^{n}y_{i}^{\otimes
t}-\mathbb{E}\bm{y}^{\otimes
t}}\right\|^{2}\leqslant\frac{1}{n\delta}d^{t}p_{\mathrm{min}}^{-O(t)}.$

∎

######  Lemma A.21.

Let the random variable $\bm{y}\in\mathbb{R}^{d}$ be distributed according to
an istotropic mixture of $k$ $d$-dimensional Gaussian distributions with
minimum mixing weight $p_{\mathrm{min}}$. Let
$y_{1},...,y_{n}\in\mathbb{R}^{d}$ be generated i.i.d. according to the
distribution of $\bm{y}$. Then, for $n\geqslant\frac{1}{\delta}$, with
probability $1-d\delta$,

$\frac{1}{n}\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\|y_{i}}\right\|^{2t}\leqslant(p_{\mathrm{min}}^{-1}d)^{O(t)}.$

###### Proof.

Denote by $\bm{y}^{(j)}$ the $j$-th coordinate of $\bm{y}$. We have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\|y_{i}\|^{2t}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left(\sum_{j=1}^{d}(y_{i}^{(j)})^{2}}\right)^{t}\leqslant\frac{1}{n}\sum_{i=1}^{n}d^{t-1}\sum_{j=1}^{d}(y_{i}^{(j)})^{2t}=d^{t-1}\sum_{j=1}^{d}\frac{1}{n}\sum_{i=1}^{n}(y_{i}^{(j)})^{2t}.$

Note that, for each $j$, $\bm{y}^{(j)}$ is distributed according to an
isotropic mixture of $k$ one-dimensional Gaussian distributions. By a union
bound, with probability $1-d\delta$ the result in Lemma A.19 holds for each
coordinate $\bm{y}^{(j)}$. Then

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\|y_{i}\|^{2t}$ $\displaystyle\leqslant
d^{t-1}\sum_{j=1}^{d}\mathopen{}\mathclose{{}\left(\mathbb{E}(\bm{y}^{(j)})^{2t}+\frac{1}{\sqrt{n\delta}}p_{\mathrm{min}}^{-O(t)}}\right).$

We have that $\mathbb{E}(\bm{y}^{(j)})^{2t}\leqslant
p_{\mathrm{min}}^{-O(t)}$. Using that $n\delta\geqslant 1$, we get then

$\frac{1}{n}\sum_{i=1}^{n}\|y_{i}\|^{2t}\leqslant d^{t}\cdot
p_{\mathrm{min}}^{-O(t)}\leqslant(p_{\mathrm{min}}^{-1}d)^{O(t)}.$

∎

###  A.4 Isotropic position transformation lemmas

The setting for the following two lemmas is that of Section 6.3.

######  Lemma A.22 (See Lemma 10 in [HK13]).

We have

  * •

$\hat{W}\widehat{\operatorname{cov}(\bm{y}^{0})}\hat{W}^{\top}=I_{d}$,

  * •

$\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top}\succ 0$,

  * •

$W\operatorname{cov}(\bm{y}^{0})W^{\top}=I_{d}$.

###### Proof.

The results are immediate by substitution. ∎

######  Lemma A.23 (See Lemma 10 in [HK13]).

Suppose that

$\|I_{d}-\operatorname{cov}(\bm{y}^{0})^{-1/2}\widehat{\operatorname{cov}}(\bm{y}^{0})\operatorname{cov}(\bm{y}^{0})^{-1/2}\|\leqslant\varepsilon.$

Then

$\|I_{d}-(\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top})^{1/2}\|\leqslant
O(\varepsilon)\cdot\|\operatorname{cov}(\bm{y}^{0})\|\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|.$

###### Proof.

The given assumption implies that all eigenvalues of
$\operatorname{cov}(\bm{y}^{0})^{-1/2}\widehat{\operatorname{cov}}(\bm{y}^{0})\operatorname{cov}(\bm{y}^{0})^{-1/2}$
lie between $1-\varepsilon$ and $1+\varepsilon$. Hence all eigenvalues of the
inverse of this matrix lie between $\frac{1}{1+\varepsilon}=1+O(\varepsilon)$
and $\frac{1}{1-\varepsilon}=1-O(\varepsilon)$. Then

$\|I_{d}-\operatorname{cov}(\bm{y}^{0})^{1/2}\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1}\operatorname{cov}(\bm{y}^{0})^{1/2}\|\leqslant
O(\varepsilon),$
$(1-O(\varepsilon))\cdot\operatorname{cov}(\bm{y}^{0})^{-1}\preceq\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1}\preceq(1+O(\varepsilon))\cdot\operatorname{cov}(\bm{y}^{0})^{-1}.$

Then

$\displaystyle\|\hat{W}\|$
$\displaystyle=\|(\hat{U}^{\top}\widehat{\operatorname{cov}}(\bm{y}^{0})\hat{U})^{-1/2}\hat{U}^{\top}\|\leqslant\|(\hat{U}^{\top}\widehat{\operatorname{cov}}(\bm{y}^{0})\hat{U})^{-1/2}\|=\|\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1/2}\|$
$\displaystyle=\|\widehat{\operatorname{cov}}(\bm{y}^{0})^{-1}\|^{1/2}\leqslant((1+O(\varepsilon))\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|)^{1/2}.$

The given assumption also implies that

$-\varepsilon\cdot\operatorname{cov}(\bm{y}^{0})\preceq\widehat{\operatorname{cov}}(\bm{y}^{0})-\operatorname{cov}(\bm{y}^{0})\preceq\varepsilon\cdot\operatorname{cov}(\bm{y}^{0}).$

Hence

$\displaystyle\|\widehat{\operatorname{cov}}(\bm{y}^{0})-\operatorname{cov}(\bm{y}^{0})\|\leqslant\varepsilon\cdot\|\operatorname{cov}(\bm{y}^{0})\|.$

Using these bounds on $\|\hat{W}\|$ and
$\|\widehat{\operatorname{cov}}(\bm{y}^{0})-\operatorname{cov}(\bm{y}^{0})\|$,
together with the fact that
$\hat{W}\widehat{\operatorname{cov}}(\bm{y}^{0})\hat{W}^{\top}=I_{d}$, we get
that

$\displaystyle\|I_{d}-\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top}\|$
$\displaystyle=\|\hat{W}(\widehat{\operatorname{cov}}(\bm{y}^{0})-\operatorname{cov}(\bm{y}^{0}))\hat{W}^{\top}\|$
$\displaystyle\leqslant\|\hat{W}\|^{2}\cdot\|\widehat{\operatorname{cov}}(\bm{y}^{0})-\operatorname{cov}(\bm{y}^{0})\|$
$\displaystyle\leqslant\varepsilon\cdot(1+O(\varepsilon))\cdot\|\operatorname{cov}(\bm{y}^{0})\|\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|$
$\displaystyle\leqslant
O(\varepsilon)\cdot\|\operatorname{cov}(\bm{y}^{0})\|\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|.$

Then all eigenvalues of $\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top}$
lie between $1-\delta$ and $1+\delta$, for
$\delta=O(\varepsilon)\cdot\|\operatorname{cov}(\bm{y}^{0})\|\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|$.
Hence all eigenvalues of the square root of this matrix lie between
$\sqrt{1-\delta}=1-O(\delta)$ and $\sqrt{1+\delta}=1+O(\delta)$. Then

$\|I_{d}-(\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top})^{1/2}\|\leqslant
O(\varepsilon)\cdot\|\operatorname{cov}(\bm{y}^{0})\|\cdot\|\operatorname{cov}(\bm{y}^{0})^{-1}\|.$

∎

###  A.5 Miscellaneous lemmas

######  Lemma A.24.

Let $W\in\mathbb{R}^{d\times d}$ and $\Sigma\in\mathbb{R}^{d\times d}$ with
$\Sigma\succ 0$ symmetric. Suppose that $W\Sigma W^{\top}=I_{d}$. Then
$W=Q\Sigma^{-1/2}$ for some orthogonal matrix $Q\in\mathbb{R}^{d\times d}$.

###### Proof.

We have

$\displaystyle W\Sigma
W^{\top}=I_{d}\Longleftrightarrow(W\Sigma^{1/2})(W\Sigma^{1/2})^{\top}=I_{d}\Longleftrightarrow
W\Sigma^{1/2}=Q\Longleftrightarrow W=Q\Sigma^{-1/2}$

for some orthogonal matrix $Q$. ∎

######  Lemma A.25.

For integers $0\leqslant s\leqslant t$,

$\binom{2t}{2s}(2t-2s-1)!!\leqslant\binom{t}{s}(et)^{t-s},$
$\binom{2t}{2s}(2t-2s-1)!!\geqslant\binom{t}{s}(t/2)^{t-s}.$

###### Proof.

We use the known fact that $(2t-2s-1)!!=\frac{(2t-2s)!}{2^{t-s}(t-s)!}$. Then

$\frac{\binom{2t}{2s}(2t-2s-1)!!}{\binom{t}{s}t^{t-s}}=\frac{\frac{(2t)!}{(2s)!(2t-2s)!}\frac{(2t-2s)!}{2^{t-s}(t-s)!}}{\frac{t!}{s!(t-s)!}t^{t-s}}=\frac{(t+1)(t+2)\cdots(2t)}{(s+1)(s+2)\cdots(2s)(2t)^{t-s}}.$

For the upper bound, we have

$\displaystyle\frac{(t+1)(t+2)\cdots(2t)}{(s+1)(s+2)\cdots(2s)(2t)^{t-s}}$
$\displaystyle=\frac{(t+1)(t+2)\cdots(t+s)}{(s+1)(s+2)\cdots(2s)}\frac{(t+s+1)(t+s+2)\cdots(2t)}{(2t)^{t-s}}$
$\displaystyle\leqslant\frac{(t+1)(t+2)\cdots(t+s)}{(s+1)(s+2)\cdots(2s)}$
$\displaystyle\leqslant\mathopen{}\mathclose{{}\left(\frac{t}{s}}\right)^{s}\leqslant
e^{t-s},$

where in the last inequality we used that
$\mathopen{}\mathclose{{}\left(\frac{t}{s}}\right)^{\frac{s}{t-s}}=\mathopen{}\mathclose{{}\left(1+\frac{t-s}{s}}\right)^{\frac{s}{t-s}}\leqslant
e$.

For the lower bound, we have

$\displaystyle\frac{(t+1)(t+2)\cdots(2t)}{(s+1)(s+2)\cdots(2s)(2t)^{t-s}}$
$\displaystyle=\frac{(t+1)(t+2)\cdots(t+s)}{(s+1)(s+2)\cdots(2s)}\frac{(t+s+1)(t+s+2)\cdots(2t)}{(2t)^{t-s}}$
$\displaystyle\geqslant\frac{(t+s+1)(t+s+2)\cdots(2t)}{(2t)^{t-s}}$
$\displaystyle\geqslant\frac{1}{2^{t-s}}.$

∎

###  A.6 Proofs deferred from Section 4

###### Proof of Lemma 4.9..

For the first proof, with probability $1-\varepsilon/100$,

$\displaystyle\sststile{2}{}v^{\top}\operatorname{cov}(\bm{z})v$
$\displaystyle=v^{\top}\widehat{\operatorname{cov}}(\bm{z})^{1/2}\widehat{\operatorname{cov}}(\bm{z})^{-1/2}\operatorname{cov}(\bm{z})\widehat{\operatorname{cov}}(\bm{z})^{-1/2}\widehat{\operatorname{cov}}(\bm{z})^{1/2}v$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leqslant}}\|\widehat{\operatorname{cov}}(\bm{z})^{-1/2}\operatorname{cov}(\bm{z})\widehat{\operatorname{cov}}(\bm{z})^{-1/2}\|\cdot\|\widehat{\operatorname{cov}}(\bm{z})^{1/2}v\|^{2}$
$\displaystyle\leqslant(1+\eta)C,$

where in (*) we used Lemma A.18.

Similarly, for the second proof, with probability $1-\varepsilon/100$

$\displaystyle\sststile{2}{}v^{\top}\widehat{\operatorname{cov}}(\bm{z})v$
$\displaystyle=v^{\top}\operatorname{cov}(\bm{z})^{1/2}\operatorname{cov}(\bm{z})^{-1/2}\widehat{\operatorname{cov}}(\bm{z})\operatorname{cov}(\bm{z})^{-1/2}\operatorname{cov}(\bm{z})^{1/2}v$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leqslant}}\|\operatorname{cov}(\bm{z})^{-1/2}\widehat{\operatorname{cov}}(\bm{z})\operatorname{cov}(\bm{z})^{-1/2}\|\cdot\|\operatorname{cov}(\bm{z})^{1/2}v\|^{2}$
$\displaystyle\leqslant(1+\eta)C.$

where in (*) we used Lemma A.17. ∎

###### Proof of Lemma 4.10..

We have

$\sststile{2t}{}\hat{\mathbb{E}}\langle\bm{z},v\rangle^{2t}=\mathbb{E}\langle\bm{z},v\rangle^{2t}+\mathopen{}\mathclose{{}\left(\hat{\mathbb{E}}\langle\bm{z},v\rangle^{2t}-\mathbb{E}\langle\bm{z},v\rangle^{2t}}\right).$

For the second term we have that

$\displaystyle\sststile{4t}{}\mathopen{}\mathclose{{}\left(\hat{\mathbb{E}}\langle\bm{z},v\rangle^{2t}-\mathbb{E}\langle\bm{z},v\rangle^{2t}}\right)^{2}$
$\displaystyle\quad=\mathopen{}\mathclose{{}\left(\hat{\mathbb{E}}\langle\operatorname{cov}(\bm{z})^{-1/2}\bm{z},\operatorname{cov}(\bm{z})^{1/2}v\rangle^{2t}-\mathbb{E}\langle\operatorname{cov}(\bm{z})^{-1/2}\bm{z},\operatorname{cov}(\bm{z})^{1/2}v\rangle^{2t}}\right)^{2}$
$\displaystyle\quad=\mathopen{}\mathclose{{}\left(\hat{\mathbb{E}}\langle(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t},(\operatorname{cov}(\bm{z})^{1/2}v)^{\otimes
2t}\rangle-\mathbb{E}\langle(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t},(\operatorname{cov}(\bm{z})^{1/2}v)^{\otimes 2t}\rangle}\right)^{2}$
$\displaystyle\quad=\langle\hat{\mathbb{E}}(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t}-\mathbb{E}(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t},(\operatorname{cov}(\bm{z})^{1/2}v)^{\otimes 2t}\rangle^{2}$
$\displaystyle\quad\leqslant\|\hat{\mathbb{E}}(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t}-\mathbb{E}(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t}\|^{2}\cdot\|(\operatorname{cov}(\bm{z})^{1/2}v)^{\otimes 2t}\|$
$\displaystyle\quad\leqslant\|\hat{\mathbb{E}}(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t}-\mathbb{E}(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t}\|^{2}\cdot C^{t}$

Note that $\mathbb{E}\bm{z}=0$. Then $\operatorname{cov}(\bm{z})^{-1/2}\bm{z}$
is in isotropic position. By Lemma A.20, with probability $1-d^{t}\delta$, we
have that

$\|\hat{\mathbb{E}}(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t}-\mathbb{E}(\operatorname{cov}(\bm{z})^{-1/2}\bm{z})^{\otimes
2t}\|^{2}\leqslant\frac{1}{n\delta}(p_{\mathrm{min}}^{-2}d)^{O(t)}.$

Select $n=(Cp_{\mathrm{min}}^{-1}d)^{O(t)}\eta^{-1}\varepsilon^{-1}$ large
enough the right-hand side is upper boundeed by $\eta^{2}C^{-t}$ with
probability at least $1-\varepsilon$. Then it follows that

$\sststile{4t}{}\mathopen{}\mathclose{{}\left(\hat{\mathbb{E}}\langle\bm{z},v\rangle^{2t}-\mathbb{E}\langle\bm{z},v\rangle^{2t}}\right)^{2}\leqslant\eta^{2}.$

Then, by Lemma A.7, we get that

$\sststile{O(t)}{}\hat{\mathbb{E}}\langle\bm{z},v\rangle^{2t}-\mathbb{E}\langle\bm{z},v\rangle^{2t}\leqslant\eta,$
$\sststile{O(t)}{}-\hat{\mathbb{E}}\langle\bm{z},v\rangle^{2t}+\mathbb{E}\langle\bm{z},v\rangle^{2t}\leqslant\eta.$

Rearranging leads to the desired results.

∎

###  A.7 Proofs deferred from Section 5

###### Proof of Lemma 5.14..

We have

$\sststile{2t}{}\hat{\mathbb{E}}\langle\bm{y},v\rangle^{2t}=\mathbb{E}\langle\bm{y},v\rangle^{2t}+\mathopen{}\mathclose{{}\left(\hat{\mathbb{E}}\langle\bm{y},v\rangle^{2t}-\mathbb{E}\langle\bm{y},v\rangle^{2t}}\right).$

For the second term we have that

$\displaystyle\sststile{4t}{}\mathopen{}\mathclose{{}\left(\hat{\mathbb{E}}\langle\bm{y},v\rangle^{2t}-\mathbb{E}\langle\bm{y},v\rangle^{2t}}\right)^{2}$
$\displaystyle=\mathopen{}\mathclose{{}\left(\hat{\mathbb{E}}\langle\bm{y}^{\otimes
2t},v^{\otimes 2t}\rangle-\mathbb{E}\langle\bm{y}^{\otimes 2t},v^{\otimes
2t}\rangle}\right)^{2}$ $\displaystyle=\langle\hat{\mathbb{E}}\bm{y}^{\otimes
2t}-\mathbb{E}\bm{y}^{\otimes 2t},v^{\otimes 2t}\rangle^{2}$
$\displaystyle\leqslant\|\hat{\mathbb{E}}\bm{y}^{\otimes
2t}-\mathbb{E}\bm{y}^{\otimes 2t}\|^{2}.$

By Lemma A.20, with probability $1-d^{t}\delta$, we have that

$\|\hat{\mathbb{E}}\bm{y}^{\otimes 2t}-\mathbb{E}\bm{y}^{\otimes
2t}\|^{2}\leqslant\frac{1}{n\delta}(p_{\mathrm{min}}^{-1}d)^{O(t)}.$

For $n\geqslant(p_{\mathrm{min}}^{-1}d)^{O(t)}\eta^{-2}\varepsilon^{-1}$ the
right-hand side is $\eta^{2}$ with probability at least $1-\varepsilon$. Then
it follows that

$\sststile{4t}{}\mathopen{}\mathclose{{}\left(\hat{\mathbb{E}}\langle\bm{y},v\rangle^{2t}-\mathbb{E}\langle\bm{y},v\rangle^{2t}}\right)^{2}\leqslant\eta^{2}.$

Then, using that $\\{X^{2}\leqslant 1\\}\sststile{2}{X}\\{X\leqslant 1\\}$, we
get that

$\sststile{O(t)}{}\hat{\mathbb{E}}\langle\bm{y},v\rangle^{2t}-\mathbb{E}\langle\bm{y},v\rangle^{2t}\leqslant\eta,$
$\sststile{O(t)}{}-\hat{\mathbb{E}}\langle\bm{y},v\rangle^{2t}+\mathbb{E}\langle\bm{y},v\rangle^{2t}\leqslant\eta.$

Rearranging leads to the desired results. ∎

###  A.8 Proofs deferred from Section 6

###### Proof of Lemma 6.5..

We have

$\sststile{2t}{}\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t}=\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left(\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle+\langle\hat{W}(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle}\right)^{2t}.$

Let $\delta>0$ to be specified later. For the upper bound:

$\displaystyle\sststile{2t}{}\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left(\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle+\langle\hat{W}(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle}\right)^{2t}$
$\displaystyle\quad\leqslant\mathopen{}\mathclose{{}\left(1+\delta}\right)^{2t-1}\cdot\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}+\mathopen{}\mathclose{{}\left(1+\frac{1}{\delta}}\right)^{2t-1}\cdot\langle\hat{W}(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t},$

where in the inequality we used Lemma A.4.

For the lower bound:

$\displaystyle\sststile{2t}{}\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left(\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle+\langle\hat{W}(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle}\right)^{2t}$
$\displaystyle\quad\stackrel{{\scriptstyle(1)}}{{\geqslant}}\mathopen{}\mathclose{{}\left(\frac{1}{1+\delta}}\right)^{2t-1}\cdot\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}-\mathopen{}\mathclose{{}\left(\frac{1+\frac{1}{\delta}}{1+\delta}}\right)^{2t-1}\cdot\langle\hat{W}(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t}$
$\displaystyle\quad\stackrel{{\scriptstyle(2)}}{{\geqslant}}\mathopen{}\mathclose{{}\left(\frac{1}{1+\delta}}\right)^{2t-1}\cdot\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}-O\mathopen{}\mathclose{{}\left(1+\frac{1}{\delta}}\right)^{2t-1}\cdot\langle\hat{W}(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t},$

where in (1) we used that, by Lemma A.4,
$\sststile{2t}{A,B}A^{2t}\leqslant(1+\delta)^{2t-1}(A+B)^{2t}+(1+\frac{1}{\delta})^{2t-1}B^{2t}$,
so
$\sststile{2t}{A,B}(A+B)^{2t}\geqslant(\frac{1}{1+\delta})^{2t-1}A^{2t}-(\frac{1+\frac{1}{\delta}}{1+\delta})^{2t-1}B^{2t}$.
In (2) we assumed that $\delta=O(1)$, which will be the case for our choice.

Now take $\delta=\frac{\eta}{100t}$. Then $(1+\delta)^{2t-1}\leqslant 1+\eta$
and $\mathopen{}\mathclose{{}\left(\frac{1}{1+\delta}}\right)^{2t-1}\geqslant
1-\eta$ for $\eta$ small.

For the second term in both bounds, we use that

$\displaystyle\sststile{2t}{}\langle\hat{W}(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t}$
$\displaystyle\leqslant\|\hat{W}(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0})\|^{2t}$
$\displaystyle=\|\hat{W}W^{-1}W(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0})\|^{2t}$
$\displaystyle\leqslant\|\hat{W}W^{-1}\|^{2t}\cdot\|W(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0})\|^{2t}$
$\displaystyle=\|(\hat{W}\operatorname{cov}(\bm{y}^{0})^{-1}\hat{W}^{\top})^{1/2}\|^{2t}\cdot\|W(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0})\|^{2t}.$

By Lemma A.17 and Lemma A.23, with probability $1-\varepsilon$,

$\displaystyle\|W(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0})\|$
$\displaystyle\leqslant\mathopen{}\mathclose{{}\left(\frac{\eta}{t}}\right)^{O(1)}$

and

$\|(\hat{W}\operatorname{cov}(\bm{y}^{0})^{-1}\hat{W}^{\top})^{1/2}\|\leqslant
1.$

Then the second term in both bounds becomes

$\displaystyle\sststile{2t}{}O\mathopen{}\mathclose{{}\left(1+\frac{1}{\delta}}\right)^{2t-1}\cdot\langle\hat{W}(\mathbb{E}\bm{y}^{0}-\hat{\mathbb{E}}\bm{y}^{0}),v\rangle^{2t}\leqslant
O\mathopen{}\mathclose{{}\left(\frac{100t}{\eta}}\right)^{2t-1}\cdot\mathopen{}\mathclose{{}\left(\frac{\eta}{t}}\right)^{O(t)}\leqslant\eta.$

∎

###### Proof of Lemma 6.6..

We have

$\sststile{2t}{}\hat{\mathbb{E}}\langle\hat{W}(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v\rangle^{2t}=\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle+\mathopen{}\mathclose{{}\left\langle\mathopen{}\mathclose{{}\left(\hat{W}-W}\right)(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle}\right)^{2t}.$

Let $\delta>0$ to be specified later. For the upper bound:

$\displaystyle\sststile{2t}{}\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle+\mathopen{}\mathclose{{}\left\langle\mathopen{}\mathclose{{}\left(\hat{W}-W}\right)(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle}\right)^{2t}$
$\displaystyle\quad\leqslant\mathopen{}\mathclose{{}\left(1+\delta}\right)^{2t-1}\cdot\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle^{2t}+\mathopen{}\mathclose{{}\left(1+\frac{1}{\delta}}\right)^{2t-1}\cdot\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\langle\mathopen{}\mathclose{{}\left(\hat{W}-W}\right)(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle^{2t},$

where in the inequality we used Lemma A.4.

For the lower bound:

$\displaystyle\sststile{2t}{}\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle+\mathopen{}\mathclose{{}\left\langle\mathopen{}\mathclose{{}\left(\hat{W}-W}\right)(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle}\right)^{2t}$
$\displaystyle\quad\stackrel{{\scriptstyle(1)}}{{\geqslant}}\mathopen{}\mathclose{{}\left(\frac{1}{1+\delta}}\right)^{2t-1}\cdot\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle^{2t}-\mathopen{}\mathclose{{}\left(\frac{1+\frac{1}{\delta}}{1+\delta}}\right)^{2t-1}\cdot\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\langle\mathopen{}\mathclose{{}\left(\hat{W}-W}\right)(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle^{2t}$
$\displaystyle\quad\stackrel{{\scriptstyle(2)}}{{\geqslant}}\mathopen{}\mathclose{{}\left(\frac{1}{1+\delta}}\right)^{2t-1}\cdot\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\langle
W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle^{2t}-O\mathopen{}\mathclose{{}\left(1+\frac{1}{\delta}}\right)^{2t-1}\cdot\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\langle\mathopen{}\mathclose{{}\left(\hat{W}-W}\right)(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle^{2t},$

where in (1) we used that, by Lemma A.4,
$\sststile{2t}{A,B}A^{2t}\leqslant(1+\delta)^{2t-1}(A+B)^{2t}+(1+\frac{1}{\delta})^{2t-1}B^{2t}$,
so
$\sststile{2t}{A,B}(A+B)^{2t}\geqslant(\frac{1}{1+\delta})^{2t-1}A^{2t}-(\frac{1+\frac{1}{\delta}}{1+\delta})^{2t-1}B^{2t}$.
In (2) we assumed that $\delta=O(1)$, which will be the case for our choice.

Now take $\delta=\frac{\eta}{100t}$. Then $(1+\delta)^{2t-1}\leqslant 1+\eta$
and $\mathopen{}\mathclose{{}\left(\frac{1}{1+\delta}}\right)^{2t-1}\geqslant
1-\eta$ for $\eta$ small.

For the second term in both bounds, we use that

$\displaystyle\sststile{2t}{}\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\langle\mathopen{}\mathclose{{}\left(\hat{W}-W}\right)(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle^{2t}$
$\displaystyle=\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\langle\mathopen{}\mathclose{{}\left(\hat{W}W^{-1}-I_{d}}\right)W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle^{2t}$
$\displaystyle\leqslant\mathopen{}\mathclose{{}\left\|I_{d}-\hat{W}W^{-1}}\right\|^{2t}\cdot\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\|W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0})}\right\|^{2t}$
$\displaystyle=\mathopen{}\mathclose{{}\left\|I_{d}-(\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top})^{1/2}}\right\|^{2t}\cdot\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\|W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0})}\right\|^{2t}.$

By Lemma A.17 and Lemma A.23, with probability $1-\varepsilon$,

$\mathopen{}\mathclose{{}\left\|I_{d}-(\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top})^{1/2}}\right\|\leqslant\mathopen{}\mathclose{{}\left(\frac{\eta}{tp_{\mathrm{min}}^{-1}d}}\right)^{O(1)}.$

By Lemma A.21, with probability $1-\varepsilon$,

$\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\|W(\bm{y}^{0}-\mathbb{E}\bm{y}^{0})}\right\|^{2t}\leqslant(p_{\mathrm{min}}^{-1}d)^{O(t)}.$

Then the second term in both bounds becomes

$\displaystyle\sststile{2t}{}O\mathopen{}\mathclose{{}\left(1+\frac{1}{\delta}}\right)^{2t-1}\cdot\hat{\mathbb{E}}\mathopen{}\mathclose{{}\left\langle\mathopen{}\mathclose{{}\left(\hat{W}-W}\right)(\bm{y}^{0}-\mathbb{E}\bm{y}^{0}),v}\right\rangle^{2t}$
$\displaystyle\qquad\leqslant
O\mathopen{}\mathclose{{}\left(\frac{100t}{\eta}}\right)^{2t-1}\cdot\mathopen{}\mathclose{{}\left(\frac{\eta}{tp_{\mathrm{min}}^{-1}d}}\right)^{O(t)}\cdot(p_{\mathrm{min}}^{-1}d)^{O(t)}\leqslant\eta.$

∎

###### Proof of Lemma 6.7.

We have

$\displaystyle|\langle
W(\mu_{i}^{0}-\mu_{j}^{0}),v\rangle-\langle\hat{W}(\mu_{i}^{0}-\mu_{j}^{0}),v\rangle|$
$\displaystyle=|\langle(W-\hat{W})(\mu_{i}^{0}-\mu_{j}^{0}),v\rangle|$
$\displaystyle=|\langle(I_{d}-\hat{W}W^{-1})W(\mu_{i}^{0}-\mu_{j}^{0}),v\rangle|$
$\displaystyle\leqslant\|I_{d}-\hat{W}W^{-1}\|\cdot\|W(\mu_{i}^{0}-\mu_{j}^{0})\|$
$\displaystyle=\|I_{d}-(\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top})^{1/2}\|\cdot\|W(\mu_{i}^{0}-\mu_{j}^{0})\|.$

By Lemma A.17 and Lemma A.23, with probability $1-\varepsilon$,

$\mathopen{}\mathclose{{}\left\|I_{d}-(\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top})^{1/2}}\right\|\leqslant\mathopen{}\mathclose{{}\left(\frac{\eta}{p_{\mathrm{min}}^{-1}}}\right)^{O(1)}.$

Note that
$W(\mu_{i}^{0}-\mu_{j}^{0})=\mu_{i}-\mu_{j}=\langle\mu_{i}-\mu_{j},u\rangle
u$, so $\|W(\mu_{i}^{0}-\mu_{j}^{0})\|=|\langle\mu_{i}-\mu_{j},u\rangle|$.
Using that $\sum_{i=1}^{k}p_{i}\langle\mu_{i},u\rangle^{2}\leqslant 1$, we
have that $\sum_{i=1}^{k}\langle\mu_{i},u\rangle^{2}\leqslant
p_{\mathrm{min}}^{-1}$, so $\langle\mu_{i},u\rangle^{2}\leqslant
p_{\mathrm{min}}^{-1}$, so $|\langle\mu_{i}-\mu_{j},u\rangle|\leqslant
2\sqrt{p_{\mathrm{min}}^{-1}}$. Then $\|W(\mu_{i}^{0}-\mu_{j}^{0})\|\leqslant
2\sqrt{p_{\mathrm{min}}^{-1}}$.

Therefore,

$\displaystyle|\langle
W(\mu_{i}^{0}-\mu_{j}^{0}),v\rangle-\langle\hat{W}(\mu_{i}^{0}-\mu_{j}^{0}),v\rangle|$
$\displaystyle\leqslant\mathopen{}\mathclose{{}\left(\frac{\eta}{p_{\mathrm{min}}^{-1}}}\right)^{O(1)}\cdot
2\sqrt{p_{\mathrm{min}}^{-1}}\leqslant\eta.$

∎

###### Proof of Lemma 6.8..

We have

$\displaystyle\|v^{\top}W(\Sigma^{0})^{1/2}-v^{\top}\hat{W}(\Sigma^{0})^{1/2}\|$
$\displaystyle=\|v^{\top}(W-\hat{W})(\Sigma^{0})^{1/2}\|$
$\displaystyle=\|v^{\top}(I_{d}-\hat{W}W^{-1})W(\Sigma^{0})^{1/2}\|$
$\displaystyle\leqslant\|I_{d}-\hat{W}W^{-1}\|\cdot\|W(\Sigma^{0})^{1/2}\|$
$\displaystyle=\|I_{d}-(\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top})^{1/2}\|\cdot\|W(\Sigma^{0})^{1/2}\|.$

By Lemma A.17 and Lemma A.23, with probability $1-\varepsilon$,

$\mathopen{}\mathclose{{}\left\|I_{d}-(\hat{W}\operatorname{cov}(\bm{y}^{0})\hat{W}^{\top})^{1/2}}\right\|\leqslant\eta.$

Note that, by Lemma A.24,
$W(\Sigma^{0})^{1/2}=Q(\Sigma^{0})^{-1/2}(\Sigma^{0})^{1/2}=Q$ for an
orthogonal matrix $Q$. We have $\|Q\|=1$, so $\|W(\Sigma^{0})^{1/2}\|=1$.

Therefore,

$\displaystyle\|v^{\top}W(\Sigma^{0})^{1/2}-v^{\top}\hat{W}(\Sigma^{0})^{1/2}\|$
$\displaystyle\leqslant\eta.$

∎