# Covariance Estimation: Optimal Dimension-free Guarantees for Adversarial
Corruption and Heavy Tails

Pedro Abdalla Nikita Zhivotovskiy Department of Mathematics, ETH Zürich,
Switzerland<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We provide an estimator of the covariance matrix that achieves the optimal
rate of convergence (up to constant factors) in the operator norm under two
standard notions of data contamination: We allow the adversary to corrupt an
$\eta$-fraction of the sample arbitrarily, while the distribution of the
remaining data points only satisfies that the $L_{p}$-marginal moment with
some $p\geqslant 4$ is equivalent to the corresponding $L_{2}$-marginal
moment. Despite requiring the existence of only a few moments of the
distribution, our estimator achieves the same tail estimates as if the
underlying distribution were Gaussian. As a part of our analysis, we prove a
non-asymptotic, dimension-free Bai-Yin type theorem in the regime $p>4$.

##  1 Introduction

Estimation of the covariance matrix is a classic topic. In high-dimensional
statistics the role of sample covariance matrices is central to Principal
Component Analysis (PCA) and to linear least squares. Most of the existing
work focuses on estimation of covariance matrices under different structural
assumptions allowing minimax estimation in the high-dimensional setup. We
refer to the line of work [6, 7, 41, 24, 12, 10] and the recent surveys [11,
25].

A line of research on non-asymptotic guarantees for sample covariance matrices
was initiated by a question of Kannan, Lovász and Simonovits [35] on the
computation of the volume of a convex body. For the class of log-concave
measures the optimal $\sqrt{\frac{d}{N}}$ ($d$ is the dimension and $N$ is the
sample size) rate of convergence in the operator norm was first obtained in
the renowned work of Adamczak, Litvak, Pajor and Tomczak-Jaegermann [1]. Since
then several authors focused on making less assumptions on the underlying
distribution [62, 52, 53, 29]. The best known result in this direction is due
to K. Tikhomirov [65] who proved the optimal rate of convergence
$\sqrt{\frac{d}{N}}$ for the sample covariance matrix assuming only the
existence of $p>4$ moments.

However, as discussed by Chen, Gao and Ren [16], if there exists only one
outlier in the whole sample, the statistical performance of the sample
covariance matrix can be compromised. Thus, one is interested in estimators of
the covariance matrix robust to adversarial contamination of the data [17,
56]. For a standard perspective on robustness, building on the ideas of
contaminated models, influence functions and breakdown points, we refer to the
monographs [30, 34, 61].

On the other hand, there is a growing interest in getting dimension-free
guarantees for estimating the covariance matrix. Given a covariance matrix
$\Sigma$, the _effective rank_ (see [71]) of $\Sigma$ is defined as

$\mathbf{r}(\Sigma)=\frac{\operatorname{Tr}(\Sigma)}{\|\Sigma\|},$

where, for the rest of the paper, $\|\cdot\|$ denotes the operator norm of the
matrix and the Euclidean norm of the vector. Koltchinskii and Lounici [40]
proved the optimal high probability bound for the sample covariance matrix in
the Gaussian case that depends on the effective rank rather than the
dimension. Since then, their result was recovered and extended multiple times
and via different techniques [68, 72, 73, 39].

Finally, we mention the recent interest in getting the so-called _sub-Gaussian
estimators_ when the data is heavy-tailed. This direction was initiated by O.
Catoni in [13], where the sub-Gaussian estimation of the mean of a random
variable is considered. To explain informally, one aims to construct
statistical estimators performing as good as the sample mean does for the
Gaussian distribution, while making as weak assumptions on the distribution as
possible. For a recent survey with focus on multivariate mean estimation, we
refer to [45]. The central ideas behind the robust mean estimation found their
applications in many related problems such as regression [32, 9, 47, 19, 50,
57], covariance estimation [14, 15, 54, 59, 21, 56], and clustering [37]. For
related results in the context of covariance estimation for heavy-tailed
distributions, we refer to the recent survey [36].

Our goal is to provide an estimator that simultaneously achieves all the
properties described above:

  * •

We allow the adversarial contamination and recover the optimal dependence on
the contamination level based on the number of moments of the underlying
distribution.

  * •

Our bounds do not contain unnecessary logarithmic factors and the convergence
rates coincide with the classical asymptotic result of Bai and Yin [4]
provided that there are at least four moments of the distribution.

  * •

The convergence rates scale with the effective rank $\mathbf{r}(\Sigma)$
rather than the dimension $d$.

  * •

We allow the distributions satisfying certain weak norm equivalence
assumptions instead of more restrictive Gaussian/log-concave assumptions
appearing in the literature. At the same time, we provide the same high
probability bounds as if the data were Gaussian.

We begin with the following definition. We say that the distribution of a zero
mean random vector $X$ satisfies the $L_{p}-L_{2}$ _norm equivalence_
(_hypercontractivity_), if for all $v\in\mathbb{R}^{d}$ and $2\leqslant
q\leqslant p$,

$({\mathbb{E}}|\langle
X,v\rangle|^{q})^{1/q}\leqslant\kappa(q)({\mathbb{E}}|\langle
X,v\rangle|^{2})^{1/2},$ (1)

where $\kappa(\cdot)$ is a function of $q$ and $\langle\cdot,\cdot\rangle$
denotes the inner product. Without loss of generality, we assume that $\kappa$
is a non-decreasing function. We say that the sample
$\widetilde{X}_{1},\ldots,\widetilde{X}_{N}$ is $\eta$-_corrupted_ if it is
obtained from the sample $X_{1},\ldots X_{N}$ of independent copies of $X$ by
replacing at most $\eta N$ points by arbitrary vectors that might depend on
$X_{1},\ldots,X_{N}$. This corruption model is described in detail [48] and
captures the standard setups in robust statistics such as the Huber
contamination model [33]. This model is sometimes called the model of
$\eta$-_corruption_ or the _strong contamination model_ [22]. We discuss this
model in more detail in Section 3.1. We present a simplified version of our
main result.

######  Theorem 1 (Simplified).

Assume that $X$ is a zero mean random vector in $\mathbb{R}^{d}$ with
covariance $\Sigma$ satisfying $L_{p}-L_{2}$ _norm equivalence_ with
$p\geqslant 4$. Fix the corruption level $\eta\in[0,1]$ and the confidence
level $\delta\in(0,1)$. Assume that
$\widetilde{X}_{1},\ldots,\widetilde{X}_{N}$ is an $\eta$-corrupted sample.
There is an estimator
$\widehat{\Sigma}_{\eta,\delta}=\widehat{\Sigma}_{\eta,\delta}(\widetilde{X}_{1},\ldots,\widetilde{X}_{N})$
depending on $\eta,\delta$ such that if $N\geqslant
c(p)(\mathbf{r}(\Sigma)+\log(1/\delta))$, then with probability at least
$1-\delta$, it holds that

$\left\|\widehat{\Sigma}_{\eta,\delta}-\Sigma\right\|\leqslant
C\|\Sigma\|\left(\sqrt{\frac{\mathbf{r}(\Sigma)+\log(1/\delta)}{N}}+\kappa(p)^{2}\eta^{1-2/p}\right),$

where $C>0$ is an absolute constant that depends only on the value $\kappa(4)$
and $c(p)$ depends only on $p$ and $\kappa(p)$. Moreover, under these
assumptions, no estimator can perform better (up to multiplicative constant
factors).

We show that the term $\kappa(p)^{2}\eta^{1-2/p}$ scales as $\sqrt{\eta}$ when
$p=4$ and as $\eta\log(1/\eta)$ for sub-Gaussian distributions. We also show
that both rates cannot be improved. In particular, in the special case of
variance estimation, which corresponds to $d=1$, our bound matches the recent
rates of Comminges, Collier, Ndaoud, and Tsybakov [20, Table 1], whose
analysis covers a less general contamination model called the sparse vector
model and only in-expectation bounds. A detailed version of the Theorem 1 with
the corresponding explicit estimators is stated in Theorem 4 in the regime
$p=4$ and in Theorem 5 in the regime $p>4$ respectively. For a detailed
discussion on the optimality of our result, we refer to Section 5. Since our
estimator is robust to both heavy tails and adversarial corruption, it should
necessarily differ from the sample covariance matrix. However, it still has a
relatively simple form. The estimator depends on a specifically tuned scalar
$\lambda>0$, which in turn depends on some parameters including $\delta$ and
$\eta$ (the details are postponed to Theorem 4 and Theorem 5). We define the
truncation function

$\psi(x)=\begin{cases}x,\quad&\textrm{for}\;x\in[-1,1],\\\
\operatorname{sign}(x),\quad&\textrm{for}\;|x|>1.\end{cases}$ (2)

Then, when $p=4$, our estimator has the following form

$\widehat{\Sigma}_{\eta,\delta}=\mathop{\mathrm{argmin}}\limits_{\widehat{\Sigma}\in\mathbb{S}_{+}^{d}}\sup\limits_{v\in
S^{d-1}}\left|\frac{1}{\lambda
N}\sum\limits_{i=1}^{N}\psi(\lambda\langle\widetilde{X}_{i},v\rangle^{2})-v^{\mathsf{T}}\widehat{\Sigma}v\right|,$
(3)

where $\mathbb{S}_{+}^{d}$ is the set of $d$ by $d$ positive semi-definite
matrices and $S^{d-1}$ denotes the unit sphere in $\mathbb{R}^{d}$. A simple
observation is that, if $\lambda\to 0$, our estimator coincides with the
sample covariance matrix
$\frac{1}{N}\sum\nolimits_{i=1}^{N}\widetilde{X}_{i}\otimes\widetilde{X}_{i}$.
For a fixed value of $\lambda$, our estimator can be seen as the second order
extension of the classical trimmed mean estimator [67, 5, 63, 48]. We are
aiming to remove a fraction of extreme observations and then average over the
remaining sample. The only difference is that, in the matrix case, we need to
take into account all possible directions in the unit sphere. The result of
Theorem 1 has multiple advantages over the best known results in the
literature:

  * •

Adversarial corruption: One of the well known results in the adversarial
corruption setup is due to Chen, Gao and Ren [16]. They analyze a version of
Tukey’s median under the restrictive assumption of elliptical distributions
satisfying certain growth conditions. Moreover, their results are dimension
dependent. See [56] for some recent extensions.

  * •

Heavy-tails: The best-known result in the literature in the heavy-tailed setup
(the only assumption is $L_{4}-L_{2}$ hypercontractivity) is due to S.
Mendelson and the second-named author of this paper [54]. However, their
results can be further improved. First, there is an additional logarithmic
factor $\log\mathbf{r}(\Sigma)$ due to the application of the non-commutative
Bernstein inequality in the analysis111We note that under the $L_{4}-L_{2}$
norm equivalence the logarithmic factor $\log\mathbf{r}(\Sigma)$ can be
removed as implicitly follows from previous arguments. In particular, without
adversarial contamination the technique of Catoni and Giulini [15, Proposition
4.1] can be adapted to recover the desired rate (see also the discussion in
[27] and the bounds in [28] where at least a $\log\log N$ term appears); their
estimator involves some explicit Gaussian integrals in the parameter space and
will depend on additional parameters of the distribution such as
$\operatorname{Tr}(\Sigma)$ and $\|\Sigma\|$. Shortly after the first version
of this paper was made public, the authors were notified that Z. Fernández-
Rico and R. I. Oliveira achieved the same bound (only for $p=4$) without the
logarithmic factor in the setup without any contamination. Their result
appeared later in the PhD thesis of Z. Rico [60] and in a preprint [58]..
Secondly, since their estimator is based on Median-of-Means, it is currently
not known how to significantly improve the dependence on $\eta$ beyond
$\sqrt{\eta}$ in the bound of Theorem 1.

The most involved step is to get the correct dependence on the corruption
level $\eta$ when $p>4$ in (1). One of the technical results used in this
paper is a dimension-free version of the classical Bai-Yin theorem [4]. In a
nutshell, the result of Bai and Yin implies that if $X_{1},\ldots,X_{N}$ are
independent copies of a zero mean random vector $X$ in $\mathbb{R}^{d}$ with
unit covariance and independent identically distributed coordinates having
four bounded moments, that is $p=4$, then

$\left\|\frac{1}{N}\sum\limits_{i=1}^{N}X_{i}\otimes X_{i}-I_{d}\right\|\to
2\sqrt{\frac{d}{N}}+\frac{d}{N}$

almost surely as $d,N\to\infty$ so that $d/N\to\beta\in(0,1]$. Moreover, if
the distribution only has $p<4$ moments, no convergence at such a rate is
possible. Our result is non-asymptotic and is somewhat stronger, since we do
not require that the coordinates of $X_{i}$ are independent. Moreover, our
focus is on the dimension-free bound. At the same time, we require that $p>4$
and the constant in the bound depends on how well $p-4$ is separated from
zero.

######  Theorem 2 (A non-asymptotic, dimension-free Bai-Yin type theorem).

Assume that $Y$ is a zero mean random vector in $\mathbb{R}^{d}$ with
covariance $\Sigma$ satisfying $L_{p}-L_{2}$ _norm equivalence_ with $p>4$.
Let $Y_{1},\ldots,Y_{N}$ be a sample of independent copies of $Y$. Consider
the truncated vectors
$X_{i}=Y_{i}\mathbbm{1}\\{\|Y_{i}\|\leqslant(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/4}\\}$
for $i=1,\ldots,N$. If $N\geqslant c(p)\mathbf{r}(\Sigma)$, then it holds that

${\mathbb{E}}\left\|\frac{1}{N}\sum\limits_{i=1}^{N}\left(X_{i}\otimes
X_{i}-{\mathbb{E}}X_{i}\otimes X_{i}\right)\right\|\leqslant
C(p)\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}},$

where $c(\cdot)$ and $C(\cdot)$ are non-increasing and both satisfy
$C(p),c(p)\to\infty$ as $p\to 4$.

A natural attempt to prove this bound would be to apply the matrix Bernstein
inequality (see the survey [66] for more details on matrix concentration
inequalities) as in [54]. However, in this case, we would get an additional
multiplicative $\log\mathbf{r}(\Sigma)$-term that does not allow us to recover
the optimal Bai-Yin rate of convergence in Theorem 1 for $p>4$. Alternatively
one can try the generic chaining machinery. We refer to the monograph of
Talagrand [64] for a detailed exposition of this method. For example, the
analysis based on the generic chaining is known to recover the optimal
dependence on the effective dimension in the sub-Gaussian case [40]. The
problem with using the generic chaining in our case, is that we only assume
the existence of $p>4$ moments, which does not allow to control the increments
of empirical processes with the required accuracy. The proof of Theorem 2 is
based on the combination of the (dimension dependent) approach developed by K.
Tikhomirov [65] with the variational approach applied by the second-named
author of this paper in [73].

######  Remark 1.

Whether the bound of Theorem 2 holds for $p=4$ is a well-known open problem
(see [70] and the survey [71]) even in the isotropic case where
$\Sigma=I_{d}$. The analysis of Theorem 1 bypasses the bound of Theorem 2 in
the regime where $p=4$. This makes our analysis different from the approach
used in [54].

######  Remark 2.

Theorem 2 can be used to remove the logarithm factor in the Median-of-Means
estimator proposed in [54] for $p>4$.

#### On the breakdown point of our estimator.

To explain informally, the breakdown point of an estimator is defined as the
largest proportion of outliers in the data for which the estimator gives a
non-vacuous result [30]. The form of the bounds we are interested in is a high
probability bound of the form
$\|\widehat{\Sigma}-\Sigma\|\leqslant\varepsilon\|\Sigma\|$, where
$\widehat{\Sigma}$ is our estimator and $\varepsilon>0$ is precision
parameter. Since $\widehat{\Sigma}=0$ satisfies this inequality with
$\varepsilon=1$, in Theorem 1 we are focusing on $\eta\in[0,c]$, where $c$ is
a small enough constant so that for large enough sample size we guarantee
$\varepsilon<1$.

#### Practical considerations.

Our main focus is on the statistical properties of the estimator. In fact, we
are aiming to achieve the best possible statistical performance and we left
computational questions aside. While there is some algorithmic progress in the
case of adversarial contamination (see the survey [22]), in a recent paper
[18], the authors provide an evidence that achieving the same for heavy-tailed
distributions is computationally hard at least when Median-of-Means estimators
are used. For some practical estimators in the context of heavy-tailed
covariance estimation, we refer to [36, 31, 56].

#### Technical overview.

Our analysis connects three separate arguments in the literature. First, we
prove a dimension-free version of the Bai-Yin theorem (Theorem 2) that allows
us to eliminate unnecessary logarithmic factors in our bounds. The proof of
this result consists of two parts: The analysis of the so-called _peaky part_
is based on the arguments of K. Tikhomirov [65], which in itself improves the
line of research [8, 1, 53, 29]. The dimension-free analysis of the _spread
part_ is based on the variational inequality techniques applied by the second-
named author of this paper in [73]. The latter approach traces back to the
works of O. Catoni and co-authors on robust mean estimation [3, 14, 28, 15].
Extending the results in [73], we prove Theorem 1 in the case where $p=4$.
Proposition 6 provides an optimal estimator for the largest eigenvalue of the
covariance matrix and is based on Catoni’s estimator [13, 14]. Finally, the
proof of Theorem 1 in the regime $p>4$ is based on combining Theorem 2 with
the second order version of the multivariate trimmed mean estimator of Lugosi
and Mendelson [48]. Our lower bounds are based on reducing to corresponding
lower bounds in the multivariate mean estimation setup.

#### Structure of the paper.

The rest of the paper is organized as follows. In Section 2, we present a
proof of Theorem 2. In Section 3, we provide a proof Theorem 1 in the regime
$p=4$. In Section 3.3, we provide an auxiliary result on estimating the
largest eigenvalue of the covariance matrix. Then, using Theorem 2 in Section
4, we give a proof Theorem 1 in the regime $p>4$. We conclude with a detailed
discussion of the lower bounds, showing the optimality of our results in
Section 5.

#### Notation.

Throughout the proofs $C(p)$ and $c(p)$ will denote the constants depending
only on $p$ and (possibly) on $\kappa(p)$, where $\kappa(\cdot)$ is given by
(1). The exact values of $C(p)$ and $c(p)$ may change from line to line. For
an integer $N$, we set $[N]=\\{1,\ldots,N\\}$. Let $\mathbbm{1}\\{A\\}$ denote
the indicator of an event $A$. The symbol $\mathbb{R}_{+}$ denotes the set of
positive reals. For any two functions (or random variables) $f,g$ defined in
some common domain, the notation $f\lesssim g$ means that there is an absolute
constant $c$ such that $f\leqslant cg$ and $f\sim g$ means that $f\lesssim g$
and $g\lesssim f$. For $(x_{i})_{i=1}^{m}\in\mathbb{R}^{m}$ the sequence
$(x_{i}^{*})_{i=1}^{m}\in\mathbb{R}^{m}$ is a non-increasing rearrangement of
$(|x_{i}|)_{i=1}^{m}$. For a set $I\subseteq[N]$ let $I^{c}=[N]\setminus I$.
Let $\mathbb{S}_{+}^{d}$ denote the set of $d$ by $d$ positive-definite
matrices. The symbol $\|\cdot\|$ denotes the operator norm of a matrix or the
Euclidean norm of the vector depending on the context. The symbol $\|a\|_{0}$
corresponds to the number of non-zero components of the vector $a$. For a
random variable $X$, let $\|X\|_{\infty}$ denote its essential supremum. Let
$\mathcal{KL}(\rho,\mu)=\int\log\left(\frac{d\rho}{d\mu}\right)d\rho$ denote
the Kullback-Leibler divergence between a pair of measures $\rho$ and $\mu$.

##  2 Proof of Theorem 2

We start by proving the dimension-free version of the Bai-Yin theorem. Fix
$\lambda>0$. In the notation of Theorem 2, let us write the following
decomposition:

$\displaystyle\sup_{v\in
S^{d-1}}\left|\frac{1}{N}\sum\nolimits_{i=1}^{N}\langle
X_{i},v\rangle^{2}-{\mathbb{E}}\langle X,v\rangle^{2}\right|$
$\displaystyle\leqslant\underbrace{\sup_{v\in
S^{d-1}}\frac{1}{N}\sum\nolimits_{i=1}^{N}\langle
X_{i},v\rangle^{2}\mathbbm{1}\\{\lambda\langle
X_{i},v\rangle^{2}>1\\}}_{\textrm{Peaky part}}$
$\displaystyle\qquad+\underbrace{\sup_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum\nolimits_{i=1}^{N}\psi(\lambda\langle
X_{i},v\rangle^{2})-{\mathbb{E}}\langle X,v\rangle^{2}\right|}_{\textrm{Spread
part}}~{},$

where the terminology comes from [64, Chapter 9.4]. Our analysis will consist
of two steps, where we first analyze the _peaky part_ and then analyze the
_spread part_.

###  2.1 Dimension-free upper bound on the peaky part

To analyze this term we follow the strategy of K. Tikhomirov in [65], which in
itself improves a line of research [8, 1, 53, 64, 29]. Although this part of
our proof follows their steps, we need several modifications to avoid any
explicit dependence on the dimension. Following [65] given two sets
$C,I\subset[N]$ and a positive integer $k$, we define the quantities $f(k,C)$,
$g(k,C,I)$ and $W_{v,i}$ as

$f(k,C)=\sup_{\begin{subarray}{c}\|y\|_{2}=1\\\ \|y\|_{0}\leqslant k\\\
\operatorname{supp}{y}\subset
C\end{subarray}}\left\|\sum_{i=1}^{N}y_{i}X_{i}\right\|^{2},$
$g(k,C,I)=\sup_{\begin{subarray}{c}\|y\|_{2}=1\\\ \|y\|_{0}\leqslant
k\end{subarray}}\sup_{\begin{subarray}{c}\|z\|_{2}=1\\\ \|z\|_{0}\leqslant
k\end{subarray}}\left\langle\sum_{i\in I\cap C}y_{i}X_{i},\sum_{j\in I^{c}\cap
C}z_{j}X_{j}\right\rangle,$ $W_{v,i}=\left\langle
X_{i},\sum_{j=1}^{N}v_{j}X_{j}\right\rangle.$ (4)

In particular, as in [64, Equations 9.140 and 9.142], we have

$\sup\limits_{v\in S^{d-1}}\sup_{|I|\leqslant k}\sum\limits_{i\in I}\langle
v,X_{i}\rangle^{2}=\sup_{|I|\leqslant k}\sup_{\sum_{i\in I}a_{i}^{2}\leqslant
1}\left\|\sum_{i\in I}a_{i}X_{i}\right\|^{2}=f(k,[N]).$ (5)

We show below that, to control the peaky part, it is sufficient to upper bound
the quantity $f(k,[N])$. The role of $g(K,C,I)$ goes as follows: Using a
standard decoupling argument (see the derivation in [65, page 11]), we obtain
that

$f(k,C)\leqslant\max_{i\leqslant
N}\|X_{i}\|^{2}+2^{-N+2}\sum_{I\subset[N]}g(k,C,I).$

Since $\max_{i\leqslant
N}\|X_{i}\|^{2}\leqslant(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/2}$ by
assumption, we limit our attention on bounding $g(k,C,I)$. We use the
following auxiliary bound. Its application should be compared with the
application of Lemma 2.6 in [65]. Due to the dimension-free nature of our
bound, we do not capture the best possible dependence on $p$ in the bound
below and only exploit the case of $p=4$. Despite that, this still allows us
to prove the desired result.

######  Lemma 1.

Let $Y\in\mathbb{R}^{d}$ be a zero mean random vector with covariance $\Sigma$
satisfying the $L_{p}-L_{2}$ norm equivalence for $p>4$ with $\kappa(\cdot)$
in (1). Denote $X=Y\mathbbm{1}\\{\|Y\|\leqslant R\\}$ where $R>0$ and let
$\kappa=\kappa(4)$. It holds that

$\mathbb{P}(\|X\|_{2}\geqslant
t)\leqslant\kappa^{4}\frac{\operatorname{Tr}(\Sigma)^{2}}{t^{4}}.$

###### Proof.

We have

${\mathbb{E}}\|X\|_{2}^{4}={\mathbb{E}}\left(\sum\nolimits_{i=1}^{d}\langle
X_{i},e_{i}\rangle^{2}\right)^{2}={\mathbb{E}}\sum\nolimits_{i=1}^{d}\langle
X,e_{i}\rangle^{4}+{\mathbb{E}}\sum\nolimits_{k\neq l}\langle
X,e_{k}\rangle^{2}\langle X,e_{l}\rangle^{2}.$

We use that, for all $i\in[d]$,

$({\mathbb{E}}\langle X,e_{i}\rangle^{4})^{1/4}\leqslant({\mathbb{E}}\langle
Y,e_{i}\rangle^{4})^{1/4}\leqslant\kappa({\mathbb{E}}\langle
Y,e_{i}\rangle^{2})^{1/2}=\kappa\Sigma_{ii}^{1/2}.$

Now, by the above display and Hölder’s inequality we have

$\displaystyle\kappa^{4}\sum\nolimits_{i=1}^{d}({\mathbb{E}}\langle
X,e_{i}\rangle^{2})^{2}+\kappa^{4}\sum\nolimits_{k\neq l}{\mathbb{E}}\langle
X,e_{k}\rangle^{2}{\mathbb{E}}\langle X,e_{l}\rangle^{2}$
$\displaystyle=\kappa^{4}\left(\sum\nolimits_{j=1}^{d}\Sigma_{jj}^{2}+\sum\nolimits_{k\neq
l}\Sigma_{kk}\Sigma_{ll}\right)$
$\displaystyle=\kappa^{4}\operatorname{Tr}(\Sigma)^{2}.$

The Markov’s inequality concludes the proof. ∎

Following [65], the next step is to split the vectors $X_{1},\ldots,X_{N}$ is
several groups so that the vectors in each group are almost orthogonal. Fix
$H>0$. Consider the random graph $\mathcal{G}_{H}=([N],E)$, where the set of
edges is

$E=\left\\{(i,j):1\leqslant i<j\leqslant N,\quad|\langle
X_{i},X_{j}\rangle|>H\max\limits_{k\leqslant N}\|X_{k}\|\right\\}.$

If we color this graph so that no two adjacent vertices share the same color,
we have that the vertices of the same color correspond to a pair of vectors
having a small inner product. Let $\chi(\mathcal{G}_{H})$ denote the chromatic
number of $\mathcal{G}_{H}$. We now induce the sets
$\\{\mathcal{C}_{m}^{H}\\}_{m=1}^{N}$ performing the partition of $[N]$ such
that $\mathcal{C}_{m}^{H}=\emptyset$ for $m>\chi(\mathcal{G}_{H})$ and each
$\mathcal{C}_{m}^{H}$ contains the vertices of the same color. Following the
proof of the dimension-dependent result, we provide a dimension-free bound on
the chromatic number of this random graph.

######  Proposition 1.

Let $Y\in\mathbb{R}^{d}$ be a zero mean random vector with covariance $\Sigma$
satisfying the $L_{p}-L_{2}$ norm equivalence for $p>4$ with $\kappa(\cdot)$
as in (1). Define, for an arbitrary positive $R$,
$X=Y\mathbbm{1}\\{\|Y\|\leqslant R\\}$ and let $\kappa=\kappa(4)$. Then, for
any $H>0$ and any integer $m>1$, with probability at least
$1-(\kappa(p)^{p}\|\Sigma\|^{p/2}NH^{-p})^{m-1}N\kappa(p)^{4}\operatorname{Tr}(\Sigma)^{2}H^{-4}$,

$\chi(\mathcal{G}_{H})\leqslant m.$

###### Proof.

We consider a greedy coloring process. Let $Y(1),Y(2),\ldots$ be an auxiliary
random process such that $Y(1)=1$ and

$Y(i)=\min\\{r\in\mathbb{N}:\forall j<i\ \text{with}\ Y(j)=r\ \text{we have}\
|\langle X_{i},X_{j}\rangle|\leqslant H\|X_{j}\|\\}.$

Note that, by definition, $\chi(\mathcal{G}_{H})\leqslant\max_{i\in[N]}Y(i)$.
Next, for each $i>1$ and $m\geqslant 1$, we have

$\displaystyle\mathbb{P}(Y(i)=m+1)$
$\displaystyle\leqslant\mathbb{P}(\text{There is}\ l\leqslant i-1\ \text{such
that}\ |\langle X_{i},X_{j}\rangle|>H\|X_{j}\|\ \text{and}\ Y(l)=m)$
$\displaystyle\leqslant\sum_{l=1}^{i-1}\mathbb{P}(|\langle
X_{i},X_{j}\rangle|>H\|X_{j}\|\ \text{and}\ Y(l)=m)$
$\displaystyle=\sum_{l=1}^{i-1}\mathbb{P}(|\langle
X_{i},X_{j}\rangle|>H\|X_{j}\|\ |\ Y(l)=m)\mathbb{P}(Y(l)=m)$
$\displaystyle\leqslant\kappa(p)^{p}\frac{\|\Sigma\|^{p/2}}{H^{p}}\sum_{l=1}^{i-1}\mathbb{P}(Y(l)=m)$
$\displaystyle\leqslant\kappa(p)^{p}\frac{\|\Sigma\|^{p/2}}{H^{p}}\mathbb{E}|\\{j\leqslant
N:Y(j)=m\\}|,$

where we used that since $X_{i}$ is independent of $Y(l)$, and by Markov’s
inequality

$\displaystyle\mathbb{P}(|\langle X_{i},X_{j}\rangle|>H\|X_{j}\|\ |\ Y(l)=m)$
$\displaystyle=\mathbb{P}(|\langle X_{i},X_{j}\rangle|>H\|X_{j}\|\
\textrm{and}\ \|X_{j}\|\neq 0\ |\ Y(l)=m)$
$\displaystyle\leqslant\frac{\kappa(p)^{p}\|\Sigma\|^{p/2}}{H^{p}}.$

We obtain the following recursion,

$\mathbb{E}|\\{j\leqslant
N:Y(j)=m+1\\}|\leqslant\kappa(p)^{p}\|\Sigma\|^{p/2}N\frac{1}{H^{p}}\mathbb{E}|\\{j\leqslant
N:Y(j)=m\\}|$

Now we apply Lemma 1 and use the monotonicity of $\kappa(\cdot)$ to obtain,

$\mathbb{E}|\\{j\leqslant N:Y(j)=2\\}|\leqslant N\mathbb{P}(\|X\|>H)\leqslant
N\kappa(p)^{4}\operatorname{Tr}(\Sigma)^{2}H^{-4}.$

Combining the estimates above, we get

$\mathbb{E}|\\{j\leqslant
N:Y(j)=m+1\\}|\leqslant(\kappa(p)^{p}\|\Sigma\|^{p/2}NH^{-p})^{m-1}N\kappa(p)^{4}\operatorname{Tr}(\Sigma)^{2}H^{-4}.$

Finally, we obtain

$\displaystyle\mathbb{P}(\chi(\mathcal{G}_{H})\geqslant m+1)$
$\displaystyle\leqslant\mathbb{P}(\exists j\leqslant N:\ Y(j)=m+1)$
$\displaystyle\leqslant\mathbb{E}|\\{j\leqslant N:Y(j)=m+1\\}|$
$\displaystyle\leqslant(\kappa(p)^{p}\|\Sigma\|^{p/2}NH^{-p})^{m-1}N\kappa(p)^{4}\operatorname{Tr}(\Sigma)^{2}H^{-4}.$

∎

We need the following result. It can be seen as one of the main ingredients of
the proof and follows from the so-called _Sparsifying_ lemma [65, Lemma 4.1].
Our key observation here is that this lemma does not involve explicitly the
dimension $d$. Recall that for $(x_{i})_{i=1}^{m}\in\mathbb{R}^{m}$ the
sequence $(x_{i}^{*})_{i=1}^{m}\in\mathbb{R}^{m}$ is a non-increasing
rearrangement of $(|x_{i}|)_{i=1}^{m}$ and $v$ is an $s$-sparse vector if
$\|v\|_{0}\leqslant s$. We remark that the statement below is deterministic
and holds for any realization of $X_{1},\ldots,X_{N}$.

######  Proposition 2 (Proposition 4.4 in [65]).

There exists an absolute constant $C>0$ such that the following holds. Fix
$I\subseteq[N]$ and let $\gamma\in(0,1/3)$ with $k\geqslant 24/\gamma^{2}$ and
$N\geqslant 128C\gamma^{-2}k$. Set
$t=\lfloor\log_{2}\frac{\gamma^{2}k}{24}\rfloor$ and
$k_{j}=\lfloor\frac{k}{2^{j}}\rfloor$ for $0\leqslant j\leqslant t$. There are
subsets $\mathcal{N}_{j},\mathcal{N}^{\prime}_{j}$ for $0\leqslant j\leqslant
t-1$ supported on $I$ and $I^{c}$ respectively and consisting of unit $\gamma
k_{j}$-sparse vectors such that

$\max\left\\{\mathcal{N}_{j},\mathcal{N}^{\prime}_{j}\right\\}\leqslant\left(\frac{CN}{\gamma
k_{j}}\right)^{2\gamma k_{j}},$

and for any $\mathcal{C}\subseteq[N]$,

$g(k,\mathcal{C},I)\leqslant C\gamma^{-2}\left(\log k\max\limits_{i\neq
j\in\mathcal{C}}|\langle
X_{i},X_{j}\rangle|+\sum\limits_{j=0}^{t-1}\sqrt{k_{j}}\left(\sup\limits_{u\in\mathcal{N}_{j}}\left(A_{u}\right)^{*}_{\left\lfloor\frac{k_{j+1}}{16}\right\rfloor}+\sup\limits_{v\in\mathcal{N}^{\prime}_{j}}\left(B_{v}\right)^{*}_{\left\lfloor\frac{k_{j+1}}{16}\right\rfloor}\right)\right),$

where the random vectors $A_{u}\in\mathbb{R}^{|I^{c}|}$ and
$B_{v}\in\mathbb{R}^{|I|}$ are given by $A_{u}=(|W_{u,i}|)_{i\in I^{c}}$ and
$B_{v}=(|W_{v,i}|)_{i\in I}$ and $W_{u,i},W_{v,i}$ are given by (4).

The next result is a dimension-free analog of Proposition 5.1 in [65] in the
regime $p>4$.

######  Proposition 3.

There exists an absolute constant $C>0$ such that if $I\subset[N]$ with
$|I|\leqslant s$ is fixed and $\log\frac{N}{s}\geqslant C$, then
simultaneously for all $\mathcal{C}\subset[N]$, with probability at least
$1-1/N^{3}$,

$g(s,\mathcal{C},I)\leqslant C\left(\log^{2}\frac{N}{s}\log s\max_{i\neq
j\in\mathcal{C}}|\langle
X_{i},X_{j}\rangle|+p\kappa(p)\|\Sigma\|^{1/2}\log^{2}\frac{N}{s}\sqrt{s}\left(\frac{N}{s}\right)^{1/p}\sqrt{f(s,[N])}\right).$

###### Proof.

We provide the required changes of the original proof. First, we notice that
if $s<C\log^{2}\frac{N}{s}$, then

$g(s,\mathcal{C},I)\leqslant s\max_{i\neq j\in\mathcal{C}}|\langle
X_{i},X_{j}\rangle|<C\log^{2}\frac{N}{s}\max_{i\neq j\in\mathcal{C}}|\langle
X_{i},X_{j}\rangle|,$

and the claim trivially follows.

For the rest of the proof we assume $s\geqslant C\log^{2}\frac{N}{s}$. We
define $\gamma=\frac{1}{\log(N/s)}$,
$t=\lfloor\log_{2}\frac{\gamma^{2}s}{C}\rfloor$ and
$k_{j}=\lfloor\frac{s}{2^{j}}\rfloor$. We choose $C>24$ to be able to apply
Proposition 2 with this choice of $\gamma,t$ and $k_{j}$. For a fixed
$0\leqslant j<t$ consider $u\in\mathcal{N}_{j}$, where $\mathcal{N}_{j}$ is
given by Proposition 2. By its definition $u$ is supported on $I$. Therefore,
for any $l\in I^{c}$ recalling (4), we have $W_{u,l}=\langle X_{l},\sum_{i\in
I}u_{i}X_{i}\rangle$. Observe that conditionally on the realization of
$X_{i},i\in I$, we have that $W_{u,l}$ are independent random variables for
all $l\in I^{c}$. Therefore, by the norm equivalence assumption (1), we have

${\mathbb{E}}[|W_{u,l}|^{p}|X_{i},i\in
I]\leqslant\kappa(p)^{p}\|\Sigma\|^{p/2}\left\|\sum\nolimits_{i\in
I}u_{i}X_{i}\right\|^{p}\leqslant\kappa(p)^{p}\|\Sigma\|^{p/2}f(s,[N])^{p/2}.$

For the same vector $u$ and the same set $I$, consider the random vector

$A_{u}=(|W_{u,l}|)_{l\in I^{c}}.$

We apply the standard bound [65, Lemma 2.5] to control the coordinates of
$A_{u}$ with

$\tau_{j}=(32e)^{1/p}\|\Sigma\|^{1/2}\kappa(p)\sqrt{f(s,[N])}\left(\frac{N}{k_{j+1}}\right)^{p^{-1}\left(1+256\gamma\right)}$

to obtain

$\begin{split}\mathbb{P}((A_{u})^{*}_{\lfloor
k_{j+1}/16\rfloor}\geqslant\tau_{j})&\leqslant\left(\frac{e\kappa^{p}\|\Sigma\|^{p/2}f(s,[N])^{p/2}N}{\tau_{j}^{p}\lfloor
k_{j+1}/16\rfloor}\right)^{\lfloor k_{j+1}/16\rfloor}\\\
&\leqslant\left(\frac{k_{j+1}}{N}\right)^{4\gamma k_{j}}.\end{split}$

We union bound over the net $\mathcal{N}_{j}$, whose size is bounded in
Proposition 2, to get for some absolute constant $C_{1}>0$,

$\mathbb{P}\left(\sup\limits_{u\in\mathcal{N}_{j}}(A_{u})^{*}_{\lfloor
k_{j+1}/16\rfloor}\geqslant\tau_{j}\right)\leqslant\left(\frac{k_{j+1}}{N}\right)^{4\gamma
k_{j}}|\mathcal{N}_{j}|\leqslant\left(\frac{C_{1}k_{j}}{\gamma
N}\right)^{2\gamma k_{j}}\leqslant\left(\frac{k_{j}}{N}\right)^{\gamma
k_{j}}\leqslant\left(\frac{k_{t}}{N}\right)^{\gamma
k_{t}}\leqslant\frac{1}{N^{4}},$

where we assumed $N\geqslant C_{1}^{2}\gamma^{-2}k_{j}$. Repeating the same
arguments for $\mathcal{N}^{\prime}_{j}$ and summing over all $j$ in
Proposition 2 we obtain, with probability at least $1-1/N^{3}$,

$g(s,\mathcal{C},I)\lesssim\gamma^{-2}\left(\log s\max_{i\neq
j\in\mathcal{C}}|\langle
X_{i},X_{j}\rangle|+\sum\nolimits_{j=0}^{t-1}\tau_{j}\sqrt{k_{j}}\right).$

The sum $\sum\nolimits_{j=0}^{t-1}\tau_{j}\sqrt{k_{j}}$ can be upper bounded
exactly the same was as in the the end of the proof of Proposition 5.1 in
[65]. Using $p>4$, we conclude the proof. ∎

The next result applies Proposition 3 to upper bound
$f(s,\mathcal{C}_{m}^{H})$, where $\mathcal{C}_{m}^{H}$ is a class of coloring
of the sample.

######  Lemma 2.

Let $s\leqslant N$ be fixed and assume that $\log\frac{N}{s}\geqslant C_{1}$,
where $C_{1}>0$ is a large enough absolute constant. Let $\mathcal{C}_{m}^{H}$
be the class from the coloring of the sample $X_{1},\ldots,X_{N}$ with
threshold $H>0$. Then there exists an absolute constant $C>0$ such that, with
probability at least $1-\frac{1}{N^{2}}$,

$f(s,\mathcal{C}_{m}^{H})\leqslant\max_{i\leqslant
N}\|X_{i}\|^{2}+C\log^{2}\frac{N}{s}\left(H\log s\max_{i\leqslant
N}\|X_{i}\|+p\kappa\|\Sigma\|^{1/2}\sqrt{s}\left(\frac{N}{s}\right)^{1/p}\sqrt{f(s,[N])}\right).$

###### Proof.

The proof follows exactly the same steps (an application of Proposition 3 in
our case) as the proof of Lemma 5.2 in [65] by replacing $d$ (their notation
for the dimension is $n$) by $s$. ∎

Our final step is to upper bound the desired function $f(s,[N])$ using the
upper bound on $f(s,\mathcal{C}_{m}^{H})$ for different coloring classes. Our
new observation is that since we are only interested in the regime $p>4$, we
can worsen the dependence on some logarithmic factors appearing in the
corresponding result in [65]. This allows us to build our analysis on a
somewhat weaker Lemma 1 (compare it with a dimension-dependent result in [65,
Lemma 2.6]).

######  Lemma 3.

Let $s,N$ satisfy $\log\frac{N}{s}\geqslant C_{1}$, where $C_{1}>0$ is a large
enough absolute constant. Then there exits $\chi=\chi(p)$ that depends only on
$p$ such that

$f(s,[N])\lesssim\chi^{2}\max_{i\leqslant
N}\|X_{i}\|^{2}+\kappa^{2}\|\Sigma\|s\left(\frac{N}{s}\right)^{4/(4+p)}\log^{4}\frac{N}{s}+\chi^{2}p^{2}\kappa(p)^{2}\|\Sigma\|s\log^{4}\frac{N}{s}\left(\frac{N}{s}\right)^{2/p},$

with probability at least
$1-N^{(4-p)(\chi-2)/(p+4)}s^{-(p^{2}(\chi-1)+4p)/(2p+8)}(\log
s)^{p(\chi-1)+4}\mathbf{r}^{2}(\Sigma)-\chi/N^{2}$.

###### Proof.

We define $\chi(\mathcal{G}_{H})$ to be the chromatic number of the random
graph induced by the partition of the sample $X_{1},\ldots,X_{N}$ into the
classes $\mathcal{C}_{m}^{H}$. We fix
$H=\kappa\|\Sigma\|^{1/2}(\frac{N}{s})^{2/(4+p)}\frac{\sqrt{s}}{\log s}$,
where $\kappa=\kappa(p)$ and apply Lemma 2 together with union bound to obtain
that, with probability at least $1-\chi/N^{2}$,

$\displaystyle\frac{1}{\chi}\sum_{m=1}^{\chi}f(s,\mathcal{C}_{m}^{H})$
$\displaystyle\leqslant\max_{i\leqslant N}\|X_{i}\|^{2}$
$\displaystyle\quad+C\log^{2}\frac{N}{s}\left(H\log s\max_{i\leqslant
N}\|X_{i}\|+p\kappa\|\Sigma\|^{1/2}\sqrt{s}\left(\frac{N}{s}\right)^{1/p}\sqrt{f(s,[N])}\right).$

We now apply the dimension-free version of the coloring Proposition 1 to
obtain that the chromatic number $\chi(\mathcal{G}_{H})$ is at most $\chi$,
with probability at least

$1-(\kappa^{p}\|\Sigma\|^{p/2}NH^{-p})^{\chi-1}N\kappa^{4}\operatorname{Tr}(\Sigma)^{2}H^{-4}.$

Now, we estimate the latter probability. We have

$\displaystyle(\kappa^{p}\|\Sigma\|^{p/2}NH^{-p})^{\chi-1}N\kappa^{4}\operatorname{Tr}(\Sigma)^{2}H^{-4}$
$\displaystyle\qquad=(N^{1-2p/(p+4)}s^{2p/(p+4)-p/2})^{\chi-1}N^{1-8/(4+p)}s^{8/(4+p)-2}(\log
s)^{p(\chi-1)+4}\mathbf{r}^{2}(\Sigma)$
$\displaystyle\qquad=N^{(4-p)(\chi-2)/(p+4)}s^{-(p^{2}(\chi-1)+4p)/(2p+8)}(\log
s)^{p(\chi-1)+4}\mathbf{r}^{2}(\Sigma).$

Following exactly the lines of the proof of Proposition 5.3 in [65] we obtain

$\displaystyle\chi^{-1}(\mathcal{G_{H}})f(s,[N])$
$\displaystyle\leqslant\chi^{-1}(\mathcal{G_{H}})\sum_{m=1}^{\chi(\mathcal{G}_{H})}f(s,\mathcal{C}_{m}^{H})$
$\displaystyle\leqslant\max_{i\leqslant
N}\|X_{i}\|^{2}+C\kappa\|\Sigma\|^{1/2}\left(\frac{N}{s}\right)^{2/(4+p)}\sqrt{s}\log^{2}\frac{N}{s}\max_{i\leqslant
N}\|X_{i}\|$
$\displaystyle\qquad+Cp\kappa\|\Sigma\|\log^{2}\frac{N}{s}\sqrt{s}\left(\frac{N}{s}\right)^{1/p}\sqrt{f(s,[N])},$

with probability at least
$1-N^{(4-p)(\chi-2)/(p+4)}s^{-(p^{2}(\chi-1)+4p})/(2p+8)(\log
s)^{p(\chi-1)+4}\mathbf{r}^{2}(\Sigma)$. Now we solve the inequality above by
applying the inequality $2ab\leqslant\gamma a^{2}+\frac{b^{2}}{\gamma}$ for
$a,b,\gamma\geqslant 0$ twice and solving with respect to $f(s,[N])$. ∎

The following bound is the main result of this section.

######  Theorem 3.

Assume that for some large enough absolute constant $c>0$ it holds that
$N\geqslant c\mathbf{r(\Sigma)}$. For large enough sample size $N$,
simultaneously for all integers $s$ satisfying $\mathbf{r}(\Sigma)\leqslant
s\leqslant N/c$, with probability at least $1-\frac{c(p)}{N}$, it holds that

$f(s,[N])\leqslant C(p)\left(\max_{i\leqslant
N}\|X_{i}\|^{2}+\|\Sigma\|s\left(\frac{N}{s}\right)^{4/(4+p)}\log^{4}\frac{N}{s}\right),$
(6)

where $C(p)$ and $c(p)$ depend only on $p$ and $\kappa(p)$.

###### Proof.

The proof is based on the application of Lemma 3. Let
$s\geqslant\mathbf{r}(\Sigma)$ and fix $\chi=\max(10,\frac{4p}{p-4})$.
Consider two cases:

  * •

If $\mathbf{r}(\Sigma)\leqslant 100$, we have

$N^{(4-p)(\chi-2)/(p+4)}s^{(p^{2}(\chi-1)+4p)/(2p+8)}(\log
s)^{p(\chi-1)+4}\mathbf{r}^{2}(\Sigma)\leqslant c(p)N^{-2}.$

  * •

Otherwise, if $\mathbf{r}(\Sigma)>100$, then we have $s\geqslant 100$ and
$\log s\leqslant s^{1/3}$. Therefore,

$N^{(4-p)(\chi-2)/(p+4)}s^{-(p^{2}(\chi-1)+4p)/(2p+8)+(p(\chi-1)+4)/3}\mathbf{r}^{2}(\Sigma)\leqslant
s^{-2}\mathbf{r}^{2}(\Sigma)N^{-2}\leqslant N^{-2}.$

Therefore, for a fixed integer $s$ satisfying $\mathbf{r}(\Sigma)\leqslant
s\leqslant N/c$, we have that $\log\frac{N}{s}$ is sufficiently large so that,
by Lemma 3 and the above calculations, with probability at least
$1-\frac{c(p)}{N^{2}}$,

$f(s,[N])\leqslant C(p)\left(\max_{i\leqslant
N}\|X_{i}\|^{2}+\|\Sigma\|s\left(\frac{N}{s}\right)^{4/(4+p)}\log^{4}\frac{N}{s}\right).$

By taking the union bound with respect to the value of $s$ we conclude the
proof. ∎

###  2.2 Analysis of the spread part

The main tool of this section is the following lemma sometimes called the PAC-
Bayesian inequality (see [15, Proposition 2.1] or [2] for a detailed proof
taking care of measurability questions). In our proofs, we adapt several
computations appearing in [73]. We also refer to [73] for a detailed
exposition of related results.

######  Lemma 4.

Assume that $X_{i}$, $i=1,\ldots,N$ are i.i.d. random variables defined on
some measurable space. Assume also that $\Theta$ (called the parameter space)
is a subset of $\mathbb{R}^{d}$ for some $d\geqslant 1$. Let $\mu$ be a
distribution (called prior) on $\Theta$ and let $\rho$ be any distribution
(called posterior) on $\Theta$ such that $\rho\ll\mu$. Then, simultaneously
for any such $\rho$ we have, with probability at least $1-\exp(-t)$,

$\frac{1}{N}\sum\limits_{i=1}^{N}{\mathbb{E}}_{\rho}f(X_{i},\theta)\leqslant{\mathbb{E}}_{\rho}\log({\mathbb{E}}_{X}\exp(f(X,\theta)))+\frac{\mathcal{KL}(\rho,\mu)+t}{N}.$

Here $\theta$ is distributed according to $\rho$. Moreover,

${\mathbb{E}}\sup\limits_{\rho}\left(\sum\limits_{i=1}^{N}{\mathbb{E}}_{\rho}f(X_{i},\theta)-N{\mathbb{E}}_{\rho}\log({\mathbb{E}}_{X}\exp(f(X,\theta)))-\mathcal{KL}(\rho,\mu)\right)\leqslant
0.$

Our analysis will also exploit the following elementary relation.

######  Lemma 5 (Lemma 4 in [73]).

Let the truncation function $\psi$ be given by (2) and let $Z$ be a square
integrable random variable. We have

$\psi({\mathbb{E}}Z)\leqslant{\mathbb{E}}\log(1+Z+Z^{2})+\min\\{1,{\mathbb{E}}Z^{2}/6\\}.$

Moreover for any $a>0$, it holds that

${\mathbb{E}}\log(1+Z+Z^{2})+a{\mathbb{E}}\min\\{1,Z^{2}/6\\}\leqslant{\mathbb{E}}\log\left(1+Z+\left(1+\frac{(7+\sqrt{6})(\exp(a)-1)}{6}\right)Z^{2}\right).$

The main result of this section is the following.

######  Proposition 4.

Assume that $Y$ is a zero mean random vector with covariance $\Sigma$
satisfying the $L_{p}-L_{2}$ _norm equivalence_ with $p\geqslant 4$. Let
$Y_{1},\ldots,Y_{N}$ be a sample of independent copies of $Y$. Consider the
truncated vectors $X_{i}=Y_{i}\mathbbm{1}\\{\|Y_{i}\|\leqslant R\\}$ for
$i=1,\ldots,N$ and some $R>0$. For a fixed truncation level $\lambda>0$, it
holds that

${\mathbb{E}}\sup_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle
X_{i},v\rangle^{2})-{\mathbb{E}}\langle
X,v\rangle^{2}\right|\lesssim\frac{\mathbf{r}(\Sigma)}{\lambda
N}+\lambda\kappa^{4}\|\Sigma\|^{2},$

where $\kappa=\kappa(4)$. In particular, when
$\lambda=\frac{1}{\kappa^{2}\|\Sigma\|}\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}$,
we have

${\mathbb{E}}\sup_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle
X_{i},v\rangle^{2})-{\mathbb{E}}\langle
X,v\rangle^{2}\right|\lesssim\kappa^{2}\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}.$

###### Proof.

Our aim is to choose the distributions $\mu$ and $\rho$ in Lemma 4. Let
$\Theta=(\mathbb{R}^{d})^{2}.$ We choose $\mu$ to be a product of two zero
mean multivariate Gaussians with mean zero and covariance $\beta^{-1}I_{d}$.
For $v\in S^{d-1}$, let $\rho_{v}$ be a product of two multivariate Gaussian
distribution with mean $v$ and covariance $\beta^{-1}I_{d}$. Because of this,
if $(\theta,\nu)$ is distributed according to $\rho_{v}$, we have
${\mathbb{E}}_{\rho_{v}}(\theta,\nu)=(v,v)$. By the additivity of
$\mathcal{KL}$-divergence for product measures and the standard formula, we
have

$\mathcal{KL}(\rho_{v},\mu)=\beta.$

By the first part of Lemma 5 we have,

$\displaystyle\psi\left(\lambda\langle X,v\rangle^{2}\right)$
$\displaystyle=\psi\left(\lambda{\mathbb{E}}_{\rho_{v}}\langle
X,\theta\rangle\langle X,\nu\rangle\right)$
$\displaystyle\leqslant{\mathbb{E}}_{\rho_{v}}\log\left(1+\lambda\langle
X,\theta\rangle\langle X,\nu\rangle+\lambda^{2}\left(\langle
X,\theta\rangle\langle X,\nu\rangle\right)^{2}\right)$
$\displaystyle\qquad+\min\\{1,\lambda^{2}{\mathbb{E}}_{\rho_{v}}\left(\langle
X,\theta\rangle\langle X,\nu\rangle\right)^{2}/6\\}.$ (7)

Observe that

${\mathbb{E}}_{\rho_{v}}\left(\langle X,\theta\rangle\langle
X,\nu\rangle\right)^{2}=(\langle
X,v\rangle^{2}+\beta^{-1}\|X\|^{2})^{2}\leqslant 2\langle
X,v\rangle^{4}+2\beta^{-2}\|X\|^{4},$ (8)

and we can write

$\min\\{1,\lambda^{2}{\mathbb{E}}_{\rho_{v}}\left(\langle
X,\theta\rangle\langle
X,\nu\rangle\right)^{2}/6\\}\leqslant\min\\{1,2\lambda^{2}\langle
X,v\rangle^{4}/6\\}+\min\\{1,2\lambda^{2}\beta^{-2}\|X\|^{4}/6\\}.$

Conditionally on $X$ the distribution of $\langle X,\theta\rangle$ is Gaussian
with mean $\langle X,v\rangle$. Since it is symmetric, we have that
$\mathbb{P}_{\rho_{v}}\left((\langle X,\theta\rangle)^{2}(\langle
X,\nu\rangle)^{2}\geqslant\langle X,v\rangle^{4}\right)\geqslant\frac{1}{4}$
and this holds trivially when $X=0$. Therefore,

$\min\\{1,2\lambda^{2}\langle X,v\rangle^{4}/6\\}\leqslant
8{\mathbb{E}}_{\rho_{v}}\min\\{1,\lambda^{2}\left(\langle
X,\theta\rangle\langle X,\nu\rangle\right)^{2}/6\\}.$

By the second part of Lemma 5, we have for some absolute constant $c>0$,

$\displaystyle{\mathbb{E}}_{\rho_{v}}\log\left(1+\lambda\langle
X,\theta\rangle\langle X,\nu\rangle+\lambda^{2}\left(\langle
X,\theta\rangle\langle
X,\nu\rangle\right)^{2}\right)+8{\mathbb{E}}_{\rho_{v}}\min\\{1,\lambda^{2}\left(\langle
X,\theta\rangle\langle X,\nu\rangle\right)^{2}/6\\}$
$\displaystyle\qquad\leqslant{\mathbb{E}}_{\rho_{v}}\log\left(1+\lambda\langle
X,\theta\rangle\langle X,\nu\rangle+c\lambda^{2}\left(\langle
X,\theta\rangle\langle X,\nu\rangle\right)^{2}\right).$

Following the proof of Lemma 1 we get

${\mathbb{E}}\|X\|^{4}\leqslant{\mathbb{E}}\|Y\|^{4}\leqslant\kappa^{4}(\operatorname{Tr}(\Sigma))^{2}\quad\text{and}\quad{\mathbb{E}}\langle
X,v\rangle^{2}\leqslant{\mathbb{E}}\langle Y,v\rangle^{2}\leqslant\|\Sigma\|,$
(9)

where $v\in S^{d-1}$. Using $\log(1+y)\leqslant y$ for $y\geqslant-1$ and
Fubini’s theorem, we have

$\displaystyle{\mathbb{E}}_{\rho_{v}}\log{\mathbb{E}}\left(1+\lambda\langle
X,\theta\rangle\langle X,\nu\rangle+c\lambda^{2}\left(\langle
X,\theta\rangle\langle X,\nu\rangle\right)^{2}\right)$
$\displaystyle\leqslant\lambda{\mathbb{E}}_{\rho_{v}}{\mathbb{E}}\langle
X,\theta\rangle\langle
X,\nu\rangle+c\lambda^{2}{\mathbb{E}}{\mathbb{E}}_{\rho_{v}}\langle
X,\theta\rangle^{2}\langle X,\nu\rangle^{2}$
$\displaystyle\leqslant\lambda{\mathbb{E}}\langle
X,v\rangle^{2}+2c\lambda^{2}({\mathbb{E}}\langle
X,v\rangle^{4}+{\mathbb{E}}\beta^{-2}\|X\|^{4})\quad\text{(by
\eqref{eq:forthnorm})}$ $\displaystyle\leqslant\lambda{\mathbb{E}}\langle
X,v\rangle^{2}+2c\lambda^{2}\kappa^{4}(({\mathbb{E}}\langle
X,v\rangle^{2})^{2}+\beta^{-2}(\operatorname{Tr}(\Sigma))^{2})\quad\text{(by
\eqref{eq:normforth})}$ $\displaystyle\leqslant\lambda{\mathbb{E}}\langle
X,v\rangle^{2}+2c\lambda^{2}\kappa^{4}(\|\Sigma\|^{2}+\beta^{-2}(\operatorname{Tr}(\Sigma))^{2}).$

We plug

$f(X,\theta,\nu)=\log\left(1+\lambda\langle X,\theta\rangle\langle
X,\nu\rangle+c\lambda^{2}\left(\langle X,\theta\rangle\langle
X,\nu\rangle\right)^{2}\right)$

in the second part of Lemma 4. Choosing $\beta=\mathbf{r}(\Sigma)$ and
dividing both sides by $N$, we have

${\mathbb{E}}\sup\limits_{v\in
S^{d-1}\cup\\{0\\}}\left(\frac{1}{N}\sum\limits_{i=1}^{N}{\mathbb{E}}_{\rho_{v}}f\left(X_{i},\theta,\nu\right)-\lambda{\mathbb{E}}\langle
X,v\rangle^{2}\right)\leqslant\frac{\mathbf{r}(\Sigma)}{N}+4c\lambda^{2}\kappa^{4}\|\Sigma\|^{2},$
(10)

where we added the $0$ vector by considering $\mu$ as a posterior distribution
and observing that $0=\mathcal{KL}(\mu,\mu)\leqslant\beta$. By adding the $0$
vector we guarantee that the supremum in (10) is always non-negative. Adding
the term

$\frac{1}{N}{\mathbb{E}}\sum\nolimits_{i=1}^{N}\min\\{1,2\lambda^{2}(\mathbf{r}(\Sigma))^{-2}\|X_{i}\|^{4}/6\\}\leqslant\lambda^{2}\frac{\kappa^{4}\|\Sigma\|^{2}}{3},$

to the inequality (10) and using the derivations in the beginning of the
proof, we have

${\mathbb{E}}\sup\limits_{v\in
S^{d-1}\cup\\{0\\}}\left(\frac{1}{N}\sum\limits_{i=1}^{N}\psi(\lambda\langle
X,v\rangle^{2})-\lambda{\mathbb{E}}\langle
X,v\rangle^{2}\right)\leqslant\frac{\mathbf{r}(\Sigma)}{N}+\left(4c+\frac{1}{3}\right)\lambda^{2}\kappa^{4}\|\Sigma\|^{2}.$

The same argument works for $-\lambda$ instead. This leads to

${\mathbb{E}}\sup\limits_{v\in S^{d-1}}\left|\frac{1}{\lambda
N}\sum\limits_{i=1}^{N}\psi(\lambda\langle X,v\rangle^{2})-{\mathbb{E}}\langle
X,v\rangle^{2}\right|\leqslant 2\frac{\mathbf{r}(\Sigma)}{\lambda
N}+2\left(4c+\frac{1}{3}\right)\lambda\kappa^{4}\|\Sigma\|^{2}.$

Our choice of $\lambda$ concludes the proof. ∎

###  2.3 Combining peaky and spread parts

We conclude the proof of Theorem 2. Using our decomposition we have

$\displaystyle{\mathbb{E}}\sup_{v\in
S^{d-1}}\left|\frac{1}{N}\sum_{i=1}^{N}\langle
X_{i},v\rangle^{2}-{\mathbb{E}}\langle X,v\rangle^{2}\right|$
$\displaystyle\leqslant{\mathbb{E}}\sup_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle
X_{i},v\rangle^{2})-{\mathbb{E}}\langle X,v\rangle^{2}\right|$
$\displaystyle\qquad+{\mathbb{E}}\sup_{v\in
S^{d-1}}\frac{1}{N}\sum_{i=1}^{N}\langle
X_{i},v\rangle^{2}\mathbbm{1}\\{\lambda\langle X_{i},v\rangle^{2}>1\\}.$

We choose
$\lambda=\frac{1}{\kappa(4)^{2}\|\Sigma\|}\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}$.
By Proposition 4 we have

${\mathbb{E}}\sup_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle
X_{i},v\rangle^{2})-{\mathbb{E}}\langle
X,v\rangle^{2}\right|\lesssim\kappa(4)^{2}\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}.$

We proceed with the remaining term. Define the random set
$I_{v}=\\{i\in[N]:\langle X_{i},v\rangle^{2}>\lambda^{-1}\\}$. Let
$m=\sup\limits_{v\in S^{d-1}}|I_{v}|$. By (5) we have

$\frac{m}{N\lambda}\leqslant\sup_{v\in
S^{d-1}}\frac{1}{N}\sum\nolimits_{i=1}^{N}\langle
X_{i},v\rangle^{2}\mathbbm{1}\\{\lambda\langle
X_{i},v\rangle^{2}>1\\}\leqslant\frac{1}{N}f(m,[N]).$ (11)

Observe that for any $p>4$, there is $C(p)>0$ such that for all $x\geqslant
1$,

$x^{1-4/(4+p)}\log^{4}x\leqslant C(p)\sqrt{x}.$

We now want to apply Theorem 3 with the (random) value $m$. First, we assume
that $\mathbf{r}(\Sigma)\leqslant m\leqslant N/c$. In this case, by Theorem 3,
with probability at least $1-\frac{c(p)}{N}$, it holds that

$\frac{1}{N}f(m,[N])\leqslant C(p)\left(\frac{1}{N}\max_{i\leqslant
N}\|X_{i}\|^{2}+\|\Sigma\|\left(\frac{m}{N}\right)^{1/2}\right).$

By (11) and since
$\|X_{i}\|\leqslant(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/4}$ we have on
the same event

$m\leqslant C(p)\lambda\left(\max_{i\leqslant
N}\|X_{i}\|^{2}+\sqrt{mN}\|\Sigma\|\right)\leqslant
C(p)\frac{1}{\|\Sigma\|}\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}\left(\sqrt{mN}\|\Sigma\|+\sqrt{\operatorname{Tr}(\Sigma)\|\Sigma\|N}\right).$

Solving the inequality above with respect to $m$ we have on the same event

$m\leqslant C(p)\mathbf{r}(\Sigma).$

We consider the case where $m$ does not satisfy $\mathbf{r}(\Sigma)\leqslant
m\leqslant N/c$. If $m<\mathbf{r}(\Sigma)$, then we recover the same upper
bound as above. If $m>N/c$, then on the event of Theorem 3 for $k=\left\lfloor
N/c-1\right\rfloor$ by (11) and monotonicity we have

$\frac{k}{\lambda}\leqslant f(k,[N])\leqslant
C(p)\left(\sqrt{N\operatorname{Tr}(\Sigma)\|\Sigma\|}+\|\Sigma\|\left(kN\right)^{1/2}\right).$

For our choice of $\lambda$ this bound leads to contradiction if $N\geqslant
c(p)\mathbf{r}(\Sigma)$ for large enough $c(p)$. We are now ready to plug our
bound $m\leqslant C(p)\mathbf{r}(\Sigma)$ in (11) to obtain that, with
probability at least $1-\frac{c(p)}{N}$,

$\frac{1}{N}f(C(p)\mathbf{r}(\Sigma),[N])\leqslant
C(p)\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}.$

Finally, for any $v\in S^{d-1}$, we have $|\langle
X_{i},v\rangle|\leqslant\|X_{i}\|\leqslant(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/4}$.
Therefore,

$\displaystyle{\mathbb{E}}\sup_{v\in S^{d-1}}\frac{1}{N}\sum_{i=1}^{N}\langle
X_{i},v\rangle^{2}\mathbbm{1}\\{\lambda\langle X_{i},v\rangle^{2}>1\\}$
$\displaystyle\leqslant
C(p)\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}+\frac{c(p)}{N}\sqrt{N\operatorname{Tr}(\Sigma)\|\Sigma\|}$
$\displaystyle=(C(p)+c(p))\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}.$

The claim of Theorem 2 follows. ∎

##  3 Proof of Theorem 1 in the regime $p=4$

First, we provide a high probability version of Proposition 4. In the
definition of our estimator we assume that both $\|\Sigma\|$ and
$\operatorname{Tr}(\Sigma)$ are known, so that our estimator depends on such
quantities. In Section 3.1, we provide optimal guarantees for estimating these
parameters. The following result can be seen as a special case of Lemma 5 in
[73]. We provide a detailed sketch of the proof for the sake of completeness.

######  Proposition 5.

Assume that $X$ is a zero mean random vector with covariance $\Sigma$
satisfying the $L_{4}-L_{2}$ _norm equivalence_. Let $X_{1},\ldots,X_{N}$ be a
sample of independent copies of $X$. For a fixed truncation level $\lambda>0$,
with probability at least $1-\delta$, it holds that

$\sup_{v\in S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle
X_{i},v\rangle^{2})-{\mathbb{E}}\langle
X,v\rangle^{2}\right|\lesssim\frac{\mathbf{r}(\Sigma)+\log(1/\delta)}{\lambda
N}+\lambda\kappa^{4}\|\Sigma\|^{2},$

where $\kappa=\kappa(4)$.

###### Proof.

We repeat the lines of the proof of Proposition 4. However, instead we plug

$f(X,\theta,\nu)=\log\left(1+\lambda\langle X,\theta\rangle\langle
X,\nu\rangle+c\lambda^{2}\left(\langle X,\theta\rangle\langle
X,\nu\rangle\right)^{2}\right)$

in the first part of Lemma 4. This implies that, with probability at least
$1-\delta$,

$\sup\limits_{v\in
S^{d-1}}\left(\frac{1}{N}\sum\limits_{i=1}^{N}{\mathbb{E}}_{\rho_{v}}f\left(X_{i},\theta,\nu\right)-\lambda{\mathbb{E}}\langle
X,v\rangle^{2}\right)\leqslant\frac{\mathbf{r}(\Sigma)+\log(1/\delta)}{N}+4c\lambda^{2}\kappa^{4}\|\Sigma\|^{2},$
(12)

where $c>0$ is the same constant as in the proof of Proposition 4.
Furthermore, by the Bernstein inequality we have

$\displaystyle\frac{1}{N}\sum\limits_{i=1}^{N}\min\\{1,\lambda^{2}(\mathbf{r}(\Sigma))^{-2}\|X_{i}\|^{4}/3\\}$
$\displaystyle\leqslant{\mathbb{E}}\min\\{1,2\lambda^{2}(\mathbf{r}(\Sigma))^{-2}\|X\|^{4}/6\\}$
$\displaystyle\
+\sqrt{\frac{2\log(1/\delta)}{N}{\mathbb{E}}\min\\{1,2\lambda^{2}(\mathbf{r}(\Sigma))^{-2}\|X\|^{4}/6\\}}+\frac{2\log(1/\delta)}{3N}.$

where we used that each summand belongs to the interval $[0,1]$ and therefore
the variance of each summand is bounded by its expectation. Following the
proof of Lemma 1, we have
${\mathbb{E}}\|X\|^{4}\leqslant\kappa^{4}(\operatorname{Tr}(\Sigma))^{2}$.
This implies that, with probability at least $1-\delta$,

$\frac{1}{N}\sum\limits_{i=1}^{N}\min\\{1,2\lambda^{2}(\mathbf{r}(\Sigma))^{-2}\|X_{i}\|^{4}/6\\}\leqslant\frac{2\lambda^{2}\kappa^{4}\|\Sigma\|^{2}}{3}+\frac{3\log(1/\delta)}{N}.$
(13)

Using this line and the union bound together with (12) and the derivations in
the proof of Proposition 4, we obtain the one-sided version of our claim.
Repeating the same lines by replacing $\lambda$ by $-\lambda$ and using the
union bound again, we finish the proof. ∎

Our next result concludes the proof of Theorem 1 when $p=4$. Recall that
$\kappa$ denotes $\kappa(4)$.

######  Theorem 4.

There is an absolute constant $C>0$ such that the following holds. Assume that
$X$ is a zero mean random vector with covariance $\Sigma$ satisfying the
$L_{4}-L_{2}$ norm equivalence. Fix the corruption level $\eta\in[0,1]$ and
the confidence level $\delta\in(0,1)$. Assume that
$\widetilde{X}_{1},\ldots,\widetilde{X}_{N}$ is an $\eta$-corrupted sample.
Then there exists an estimator $\widehat{\Sigma}_{\eta,\delta}$ such that,
with probability at least $1-\delta$,

$\left\|\widehat{\Sigma}_{\eta,\delta}-\Sigma\right\|\leqslant
C\kappa^{2}\|\Sigma\|\left(\sqrt{\frac{\mathbf{r}(\Sigma)+\log(1/\delta)}{N}}+\sqrt{\eta}\right).$

We begin with presenting the estimator. As we mentioned, we assume that
$\eta,\|\Sigma\|,\operatorname{Tr}(\Sigma)$ and the constant
$\kappa=\kappa(4)$ are known. In Section 3.1, we discuss how to estimate
$\|\Sigma\|$ and $\operatorname{Tr}(\Sigma)$ up to multiplicative constant
factors. The dependence on $\kappa$ in our estimator can also be ignored,
though in this case we obtain a slightly weaker dependence on this parameter
in the final bound.

The estimator in Theorem 4 1. Given
$\delta,\operatorname{Tr}(\Sigma),\|\Sigma\|,\kappa$, and an $\eta$-corrupted
sample $\widetilde{X}_{1},\ldots,\widetilde{X}_{N}$ we set
$\lambda=\frac{1}{\kappa^{2}\|\Sigma\|}\sqrt{\frac{\mathbf{r}(\Sigma)+\log(1/\delta)+\eta
N}{N}}.$ 2. Define $\Gamma=\bigcap\limits_{v\in
S^{d-1}}\left\\{A\in\mathbb{S}_{+}^{d}:\left|\frac{1}{\lambda
N}\sum\limits_{i=1}^{N}\psi\left(\lambda\langle\widetilde{X}_{i},v\rangle^{2}\right)-v^{\mathsf{T}}Av\right|\leqslant
C\lambda\kappa^{4}\|\Sigma\|^{2}/2\right\\}.$ 3. Let
$\widehat{\Sigma}_{\eta,\delta}$ be any matrix in the set $\Gamma$. If the set
is empty, we output $\widehat{\Sigma}_{\eta,\delta}=0$.

###### Proof.

Since the truncation function $\psi(\cdot)$ is bounded, we have

$\sup_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle\widetilde{X}_{i},v\rangle^{2})-{\mathbb{E}}\langle
X,v\rangle^{2}\right|\leqslant\sup_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle
X_{i},v\rangle^{2})-{\mathbb{E}}\langle
X,v\rangle^{2}\right|+\frac{\eta}{\lambda}.$

Combining this with Proposition 5 we have for some $C>0$, with probability at
least $1-\delta$,

$\sup_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle\widetilde{X}_{i},v\rangle^{2})-v^{\mathsf{T}}\Sigma
v\right|\leqslant\frac{C}{4}\left(\frac{\mathbf{r}(\Sigma)+\log(1/\delta)+\eta
N}{\lambda N}+\lambda\kappa^{4}\|\Sigma\|^{2}\right).$

Using the triangle inequality, the definition of
$\widehat{\Sigma}_{\eta,\delta}$ and the line above, we have on the same event

$\displaystyle\left\|\widehat{\Sigma}_{\eta,\delta}-\Sigma\right\|$
$\displaystyle\leqslant\sup\limits_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle\widetilde{X}_{i},v\rangle^{2})-v^{\mathsf{T}}\widehat{\Sigma}_{\eta,\delta}v\right|+\sup\limits_{v\in
S^{d-1}}\left|\frac{1}{N\lambda}\sum_{i=1}^{N}\psi(\lambda\langle\widetilde{X}_{i},v\rangle^{2})-v^{\mathsf{T}}\Sigma
v\right|$ $\displaystyle\leqslant
C\kappa^{2}\|\Sigma\|\left(\sqrt{\frac{\mathbf{r}(\Sigma)+\log(1/\delta)}{N}}+\sqrt{\eta}\right).$

Our choice of $\lambda$ concludes the proof. ∎

######  Remark 3.

It is straightforward to verify that the matrix
$\widehat{\Sigma}_{\eta,\delta}$ defined by (3) satisfies the assumption of
Theorem 4 and can be used as an estimator of the covariance matrix.

Finally, we show how to estimate the value of the truncation parameter
$\lambda$ using the corrupted observations.

###  3.1 Estimating the truncation level $\lambda$ in the regime $p=4$

We begin this section with a brief discussion of our contamination model. To
simplify the technical aspects of our analysis, we impose a slight restriction
on the strong contamination model described in the introduction. In our
analysis, we require the estimation of multiple parameters, which can be
accomplished by dividing the sample into several equal parts and estimating
these parameters using independent sub-samples. This approach is standard, and
has been analyzed, for example, in [54] in the same context. However, in the
strong contamination model, the adversary has the ability to replace some
observations within each sub-sample in a manner that depends on the entire
sample. This can result in dependent sub-samples and a more complicated
stability type analysis appearing in the literature (see [23, Section 6]). We
therefore restrict the adversary from making the sub-samples dependent on each
other. We note that this assumption is standard and has been made (implicitly)
in some recent works [48, 58]. Furthermore, it is automatically satisfied in
standard contamination models, including the Huber model.

An important aspect of the proof of Theorem 4 is that we only need to know
$\|\Sigma\|$ and $\operatorname{Tr}(\Sigma)$ up to multiplicative constant
factors. That is, we want to find two estimators $\widehat{\varphi}_{1}$ and
$\widehat{\varphi}_{2}$ such that for some $c>1$, with high probability with
respect to the realization of the corrupted sample
$\widetilde{X}_{1},\ldots,\widetilde{X}_{N}$,

$\frac{1}{c}\operatorname{Tr}(\Sigma)\leqslant\widehat{\varphi}_{1}\leqslant
c\operatorname{Tr}(\Sigma)\quad\text{and}\quad\frac{1}{c}\|\Sigma\|\leqslant\widehat{\varphi}_{2}\leqslant
c\|\Sigma\|.$

If these estimators are available, we can assume, without the loss of
generality, that our initial sample is of size $3N$. We use the first $2N$
elements to estimate $\operatorname{Tr}(\Sigma)$ and $\|\Sigma\|$ and then
plug them into the truncation level $\lambda$ in Theorem 4. A similar sample
splitting strategy is used in [54]. Our contribution is that we provide
estimators $\widehat{\varphi}_{1}$ and $\widehat{\varphi}_{2}$ such that they
take the adversarial corruption into account as well as do not contain an
unnecessary logarithmic factor. For the rest of the section, we fix
$\kappa=\kappa(4)$, where $\kappa(\cdot)$ is defined in (1).

###  3.2 Estimating $\operatorname{Tr}(\Sigma)$

One can estimate $\operatorname{Tr}(\Sigma)$ using, for example, the trimmed
mean estimator analyzed in [48]. Let $e_{1},\ldots,e_{d}$ denote the canonical
basis in $\mathbb{R}^{d}$. Observe that

$\operatorname{Tr}(\Sigma)=\sum\nolimits_{i=1}^{d}{\mathbb{E}}\langle
X,e_{i}\rangle^{2}.$

Using the $L_{4}-L_{2}$ norm equivalence and the proof of Lemma 1 we have
$\operatorname{Var}\left(\sum\nolimits_{i=1}^{d}\langle
X,e_{i}\rangle^{2}\right)\leqslant\kappa^{4}(\operatorname{Tr}(\Sigma))^{2}$.
Given an $\eta$-corrupted sample of size $2N$, the trimmed mean estimator
$\widehat{\varphi}_{1}$ applied to the random variable
$\sum\nolimits_{i=1}^{d}\langle X,e_{i}\rangle^{2}$ implies that, for any
$\delta\in(\exp(-N)/4,1)$, with probability at least $1-4\exp(-\varepsilon
N/12)$,

$|\widehat{\varphi}_{1}-\operatorname{Tr}(\Sigma)|\leqslant
10\sqrt{\varepsilon}\kappa^{2}\operatorname{Tr}(\Sigma),$

where $\varepsilon=8\eta+12\frac{\log(4/\delta)}{N}$. This bound is presented
in [48, Theorem 1]. For the sake of brevity, we do not provide the details of
the multivariate trimmed mean estimator. Observe that for this choice of
$\varepsilon$, it holds that $1-4\exp(-\varepsilon N/12)\geqslant 1-\delta$.
Provided that $10\sqrt{\varepsilon}\kappa^{2}\leqslant\frac{1}{2}$ we obtain
that, with probability at least $1-\delta$,

$\frac{1}{2}\operatorname{Tr}(\Sigma)\leqslant\widehat{\varphi}_{1}\leqslant
2\operatorname{Tr}(\Sigma).$ (14)

It is only left to check that it is sufficient to have
$\eta\in\left[0,\frac{1}{40^{2}\kappa^{2}}\right]$ and $N\geqslant 12\cdot
40^{2}\kappa^{4}\log(4/\delta)$.

###  3.3 Estimating $\|\Sigma\|$

A simply way of estimating $\|\Sigma\|$ is to first estimate the full
covariance matrix $\Sigma$ as in Theorem 4 and then compute the operator norm
of the estimator. However, the difficulty of estimating $\|\Sigma\|$ is that
we are not allowed to choose the truncation level $\lambda$ depending on
$\|\Sigma\|$. In particular, all previous results we are aware of lead to an
additional logarithmic factor in the assumption on the sample size (see [54,
15]). Instead we provide an adaptive estimator similar in spirit to the
original robust estimator of O. Catoni [13] for estimating the mean of a
random variable (see also [14] for related computations). To simplify the
proof, we assume that the distribution of $X$ satisfies $\mathbb{P}(X=0)=0$.
This assumption is mild and can always be satisfied if we add a small Gaussian
perturbation to $X$ without changing the covariance matrix of $X$ too much.

######  Proposition 6.

Assume that $X$ is a zero mean random vector with covariance $\Sigma$
satisfying the $L_{4}-L_{2}$ norm equivalence. Assume additionally that
$\mathbb{P}(X=0)=0$. Let $c\geqslant 1$ be a large enough absolute constant.
Fix the corruption level $\eta\in[0,\frac{1}{300c\kappa^{4}}]$ and the
confidence level $\delta\in(0,1/4)$. Assume that
$\widetilde{X}_{1},\ldots,\widetilde{X}_{N}$ is an $\eta$-corrupted sample.
Then there is a unique value $\widehat{\alpha}>0$ satisfying

$\frac{1}{N}\sup\limits_{v\in
S^{d-1}}\sum\nolimits_{i=1}^{N}\psi\left(\widehat{\alpha}^{2}\langle\widetilde{X}_{i},v\rangle^{2}\right)=\frac{1}{20c\kappa^{4}}+\eta.$

If $N\geqslant 100c\kappa^{4}\mathbf{r}(\Sigma)+400c\kappa^{4}\log(1/\delta)$,
then with probability at least $1-4\delta$, it holds that

$\frac{1}{4}\|\Sigma\|\leqslant\frac{1}{24c\kappa^{4}\widehat{\alpha}^{2}}\leqslant
4\|\Sigma\|.$

###### Proof.

We begin with the analysis of an uncorrupted sample $X_{1},\ldots,X_{N}$. Our
first aim is to choose the distributions $\mu$ and $\rho$ in Lemma 4. Let
$\Theta=(\mathbb{R}^{d})^{2}$ and choose $\mu$ to be a product of two zero
mean multivariate Gaussians with mean zero and covariance $\beta^{-1}I_{d}$.
For $v\in S^{d-1}$ and $\alpha>0$ let $\rho_{\alpha,v}$ be a product of two
multivariate Gaussian distribution with mean $\alpha v$ and covariance
$\beta^{-1}I_{d}$. Because of this, if $(\theta,\nu)$ is distributed according
to $\rho_{\alpha,v}$, we have ${\mathbb{E}}_{\rho_{v}}(\theta,\nu)=(\alpha
v,\alpha v)$. By the additivity of $\mathcal{KL}$-divergence for product
measures and the standard formula, we have

$\mathcal{KL}(\rho_{\alpha,v},\mu)=\alpha^{2}\beta.$

For the rest of the proof we sometimes write $\rho$ instead of
$\rho_{\alpha,v}$. By the first part of Lemma 5, we have

$\displaystyle\psi\left(\alpha^{2}\langle X,v\rangle^{2}\right)$
$\displaystyle=\psi\left({\mathbb{E}}_{\rho}\langle X,\theta\rangle\langle
X,\nu\rangle\right)$
$\displaystyle\leqslant{\mathbb{E}}_{\rho}\log\left(1+\langle
X,\theta\rangle\langle X,\nu\rangle+\left(\langle X,\theta\rangle\langle
X,\nu\rangle\right)^{2}\right)+\min\\{1,{\mathbb{E}}_{\rho}\left(\langle
X,\theta\rangle\langle X,\nu\rangle\right)^{2}/6\\}.$

Observe that

${\mathbb{E}}_{\rho}\left(\langle X,\theta\rangle\langle
X,\nu\rangle\right)^{2}=(\alpha^{2}\langle
X,v\rangle^{2}+\beta^{-1}\|X\|^{2})^{2}\leqslant 2\alpha^{4}\langle
X,v\rangle^{4}+2\beta^{-2}\|X\|^{4},$

and we can write

$\min\\{1,{\mathbb{E}}_{\rho}\left(\langle X,\theta\rangle\langle
X,\nu\rangle\right)^{2}/6\\}\leqslant\min\\{1,2\alpha^{4}\langle
X,v\rangle^{4}/6\\}+\min\\{1,2\beta^{-2}\|X\|^{4}/6\\}.$

Repeating the lines of the proof of Proposition 4, we get

${\mathbb{E}}_{\rho}\log{\mathbb{E}}\left(1+\langle X,\theta\rangle\langle
X,\nu\rangle+c\left(\langle X,\theta\rangle\langle
X,\nu\rangle\right)^{2}\right)\leqslant\alpha^{2}v^{\mathsf{T}}\Sigma
v+2c\kappa^{4}(\alpha^{4}\|\Sigma\|^{2}+\beta^{-2}(\operatorname{Tr}(\Sigma))^{2}),$

where $c\geqslant 1$ is an absolute constant. Using the first part of Lemma 4
we obtain that, with probability at least $1-\delta$, simultaneously for all
$v\in S^{d-1}$ and $\alpha>0$,

$\displaystyle\frac{1}{N}\sum\nolimits_{i=1}^{N}\psi\left(\alpha^{2}\langle
X_{i},v\rangle^{2}\right)$
$\displaystyle\leqslant\alpha^{2}v^{\mathsf{T}}\Sigma
v+2c\kappa^{4}(\alpha^{4}\|\Sigma\|^{2}+\beta^{-2}(\operatorname{Tr}(\Sigma))^{2})$
$\displaystyle\qquad+\frac{\alpha^{2}\beta+\log(1/\delta)}{N}+\frac{1}{N}\sum\nolimits_{i=1}^{N}\min\\{1,2\beta^{-2}\|X_{i}\|^{4}/6\\}.$

Using the Bernstein inequality as in (13) we have, with probability at least
$1-\delta$,

$\frac{1}{N}\sum\nolimits_{i=1}^{N}\min\\{1,2\beta^{-2}\|X_{i}\|^{4}/6\\}\leqslant\frac{2\kappa^{4}\beta^{-2}(\operatorname{Tr}(\Sigma))^{2}}{3}+\frac{3\log(1/\delta)}{N}.$

We choose $\beta=10c\kappa^{4}\operatorname{Tr}(\Sigma)$ and using the union
bound, we obtain that, with probability at least $1-2\delta$, simultaneously
for all $v\in S^{d-1}$ and $\alpha>0$,

$\frac{1}{N}\sum\nolimits_{i=1}^{N}\psi\left(\alpha^{2}\langle
X_{i},v\rangle^{2}\right)\leqslant\alpha^{2}v^{\mathsf{T}}\Sigma
v+2c\kappa^{4}\alpha^{4}\|\Sigma\|^{2}+\frac{2}{75c\kappa^{4}}+\frac{10c\kappa^{4}\alpha^{2}\operatorname{Tr}(\Sigma)}{N}+\frac{4\log(1/\delta)}{N}.$

Since $N\geqslant
100c\kappa^{4}\mathbf{r}(\Sigma)+400c\kappa^{4}\log(1/\delta)$, we have on the
same event

$\frac{1}{N}\sum\nolimits_{i=1}^{N}\psi\left(\alpha^{2}\langle
X_{i},v\rangle^{2}\right)\leqslant\alpha^{2}v^{\mathsf{T}}\Sigma
v+\frac{1}{10}\alpha^{2}\|\Sigma\|+2c\kappa^{4}\alpha^{4}\|\Sigma\|^{2}+\frac{11}{300c\kappa^{4}}.$

Returning to the $\eta$-corrupted sample
$\widetilde{X}_{1},\ldots,\widetilde{X}_{N}$ and since $|\psi(\cdot)|\leqslant
1$,

$\frac{1}{N}\sum\nolimits_{i=1}^{N}\psi\left(\alpha^{2}\langle\widetilde{X}_{i},v\rangle^{2}\right)\leqslant\alpha^{2}v^{\mathsf{T}}\Sigma
v+\frac{1}{10}\alpha^{2}\|\Sigma\|+2c\kappa^{4}\alpha^{4}\|\Sigma\|^{2}+\frac{11}{300c\kappa^{4}}+\eta.$
(15)

Observe that the function $\varphi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ given by

$\varphi(\alpha)=\frac{1}{N}\sup\limits_{v\in
S^{d-1}}\sum\nolimits_{i=1}^{N}\psi\left(\alpha^{2}\langle\widetilde{X}_{i},v\rangle^{2}\right)$

is continuous (it is easy to check that $\varphi(\cdot)$ is a supremum over
equi-Lipschitz functions) and non-decreasing. Furthermore, there is $w\in
S^{d-1}$ such that $\langle X_{i},w\rangle\neq 0$ for all $i\in[N]$. Indeed,
to construct such a vector we pick a random vector $U$ distributed as a zero
mean multivariate Gaussian random vector with unit covariance. Since
$X_{i}\neq 0$ almost surely for all $i\in[N]$ we have that $\langle
U,X_{i}\rangle$ is a zero mean Gaussian (conditionally on $X_{i}$) with non-
zero covariance. Thus, taking $w=U/\|U\|$ we have almost surely $\langle
X_{i},w\rangle\neq 0$ for all $i\in[N]$. We have $\varphi(0)=0$ and
$\varphi\left(\frac{1}{\min_{i\in[N]}|\langle X_{i},w\rangle|}\right)\geqslant
1-\eta$ since at most $\eta N$ vectors $\widetilde{X}_{i}$ can be orthogonal
to $w$. Therefore, since $\kappa,c\geqslant 1$ and
$\eta\leqslant\frac{1}{300c\kappa^{4}}$ there is $\widehat{\alpha}>0$ such
that

$\varphi(\widehat{\alpha})=\frac{1}{20c\kappa^{4}}+\eta.$

Using (15), we get on the same event

$2c\kappa^{4}\widehat{\alpha}^{4}\|\Sigma\|^{2}+\frac{11}{10}\widehat{\alpha}^{2}\|\Sigma\|-\frac{1}{75c\kappa^{4}}\geqslant
0.$

Solving this as a quadratic equation (only the positive root plays a role)
with respect to $\widehat{\alpha}^{2}\|\Sigma\|$ we get

$\frac{-11/10+\sqrt{(11/10)^{2}+8/75}}{4c\kappa^{4}\widehat{\alpha}^{2}}\leqslant\|\Sigma\|.$

This provides a lower bound on $\|\Sigma\|$ in terms of
$\widehat{\alpha}^{2}$.

We proceed with an upper bound. For $v\in S^{d-1}$ and $\alpha>0$ let
$\rho_{\alpha,-\alpha,v}$ be a product of two multivariate Gaussian
distributions with means $\alpha v$ and $-\alpha v$ respectively and the same
covariance matrix $\beta^{-1}I_{d}$. Repeating the proof, we obtain the
following analog of inequality (15). With probability at least $1-2\delta$,
for all $v\in S^{d-1}$ and $\alpha>0$,

$-\frac{1}{N}\sum\nolimits_{i=1}^{N}\psi\left(\alpha^{2}\langle\widetilde{X}_{i},v\rangle^{2}\right)\leqslant-\alpha^{2}v^{\mathsf{T}}\Sigma
v+\frac{1}{10}\alpha^{2}\|\Sigma\|+2c\kappa^{4}\alpha^{4}\|\Sigma\|^{2}+\frac{11}{300c\kappa^{4}}+\eta.$
(16)

Let $v_{1}$ be a maximizer of $v^{\mathsf{T}}\Sigma v$ in $S^{d-1}$. We have
$v_{1}^{\mathsf{T}}\Sigma v_{1}=\|\Sigma\|$. Furthermore, we have

$-\sup\limits_{v\in
S^{d-1}}\frac{1}{N}\sum\nolimits_{i=1}^{N}\psi\left(\alpha^{2}\langle\widetilde{X}_{i},v\rangle^{2}\right)\leqslant-\frac{1}{N}\sum\nolimits_{i=1}^{N}\psi\left(\alpha^{2}\langle\widetilde{X}_{i},v_{1}\rangle^{2}\right).$

Since $-\varphi(\cdot)$ is non-increasing, this implies that simultaneously
for all $\alpha\in[0,\widehat{\alpha}]$ on the event where (16) holds, we have

$-\frac{1}{20c\kappa^{4}}-\eta\leqslant-\frac{9}{10}\alpha^{2}\|\Sigma\|+2c\kappa^{4}\alpha^{4}\|\Sigma\|^{2}+\frac{11}{300c\kappa^{4}}+\eta.$

Since $\eta\leqslant\frac{1}{300c\kappa^{4}}$ we reduce this equation to

$2c\kappa^{4}\alpha^{4}\|\Sigma\|^{2}-\frac{9}{10}\alpha^{2}\|\Sigma\|+\frac{7}{75c\kappa^{4}}\geqslant
0.$ (17)

As a function of $\alpha^{2}\|\Sigma\|$ this quadratic equation has two non-
negative roots:

$x_{1}=\frac{9/10-\sqrt{(9/10)^{2}-56/75}}{4c\kappa^{4}}\quad\text{and}\quad
x_{2}=\frac{9/10+\sqrt{(9/10)^{2}-56/75}}{4c\kappa^{4}}.$

We show that since (17) holds for all $\alpha\in[0,\widehat{\alpha}]$, we
should have that $\widehat{\alpha}^{2}\|\Sigma\|\leqslant x_{1}$. Indeed,
assume that instead $\widehat{\alpha}^{2}\|\Sigma\|\geqslant x_{2}$. In this
case $0\leqslant(x_{1}+x_{2})/2\leqslant\widehat{\alpha}^{2}\|\Sigma\|$ and
thus (17) should be satisfied for $\alpha^{2}\|\Sigma\|=(x_{1}+x_{2})/2$. The
obtained contradiction proves that $\widehat{\alpha}^{2}\|\Sigma\|\leqslant
x_{1}$. Finally, by union bound we have, with probability at least
$1-4\delta$,

$\frac{-11/10+\sqrt{(11/10)^{2}+8/75}}{4c\kappa^{4}\widehat{\alpha}^{2}}\leqslant\|\Sigma\|\leqslant\frac{9/10-\sqrt{(9/10)^{2}-56/75}}{4c\kappa^{4}\widehat{\alpha}^{2}}.$

Algebraic computations conclude the proof. ∎

We end up by observing that the estimator proposed in this section admits a
straightforward generalization for (uncontaminated) higher order tensors. In
this setup one is aiming to estimate ${\mathbb{E}}\langle X,v\rangle^{s}$
uniformly over $v\in S^{d-1}$ for some integer $s\geqslant 2$, as in the
recent work of Mendelson [51]. In order to provide this extension we apply
[73, Lemma 5] together with the estimators of the trace and the operator norm
provided above. We note that getting the optimal dependence on the
contamination level $\eta$ seems more subtle when $s>2$.

##  4 Proof of Theorem 1 in the regime $p>4$

In this section, we prove Theorem 1 in the regime $p>4$. We begin with the
following symmetrized version of Theorem 2.

######  Corollary 1.

Assume that $Y$ is a zero mean random vector with covariance $\Sigma$
satisfying the $L_{p}-L_{2}$ _norm equivalence_ with $p>4$. Let
$Y_{1},\ldots,Y_{N}$ be a sample of independent copies of $Y$. Consider the
truncated vectors
$X_{i}=Y_{i}\mathbbm{1}\\{\|Y_{i}\|\leqslant(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/4}\\}$
for $i=1,\ldots,N$. Let $\varepsilon_{1},\ldots,\varepsilon_{N}$ be
independent Rademacher random signs. If $N\geqslant c(p)\mathbf{r}(\Sigma)$,
then it holds that

${\mathbb{E}}\sup\limits_{v\in
S^{d-1}}\left|\frac{1}{N}\sum\limits_{i=1}^{N}\varepsilon_{i}\left\langle
X_{i},v\right\rangle^{2}\right|\leqslant
C(p)\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}},$

where $c(p)$ and $C(p)$ depend only on $p$ and $\kappa(p)$ and the expectation
is taken with respect to both $X_{i}$ and $\varepsilon_{i}$, $i=1,\ldots,N$.

######  Remark 4.

We highlight that the result of Theorem 2 and Corollary 1 admits extensions to
higher order power in the spirit of [69]. For the related derivations in the
light-tailed case, see the proof of Theorem 2 in [73].

###### Proof.

We use the standard desymmetrization argument [38, Section 2.1]. Let
$X^{\prime}_{1},\ldots,X^{\prime}_{N}$ be the independent copies of $X$ and
let ${\mathbb{E}}^{\prime}$ denote the expectation with respect to these
random vectors. Using the triangle inequality, Jensen’s inequality and the
contraction principle [42, Theorem 4.4] we get

$\displaystyle{\mathbb{E}}\sup\limits_{v\in
S^{d-1}}\left|\sum\limits_{i=1}^{N}\varepsilon_{i}\left\langle
X_{i},v\right\rangle^{2}\right|$
$\displaystyle\leqslant{\mathbb{E}}\sup\limits_{v\in
S^{d-1}}\left|\sum\limits_{i=1}^{N}\varepsilon_{i}(\left\langle
X_{i},v\right\rangle^{2}-{\mathbb{E}}^{\prime}\left\langle
X^{\prime}_{i},v\right\rangle^{2})\right|+{\mathbb{E}}\sup\limits_{v\in
S^{d-1}}\left|\sum\limits_{i=1}^{N}\varepsilon_{i}{\mathbb{E}}\left\langle
X_{i},v\right\rangle^{2}\right|$
$\displaystyle\leqslant{\mathbb{E}}{\mathbb{E}}^{\prime}\sup\limits_{v\in
S^{d-1}}\left|\sum\limits_{i=1}^{N}\left\langle
X_{i},v\right\rangle^{2}-\left\langle
X^{\prime}_{i},v\right\rangle^{2}\right|+\|\Sigma\|\sqrt{N}$
$\displaystyle\leqslant 2{\mathbb{E}}\sup\limits_{v\in
S^{d-1}}\left|\sum\limits_{i=1}^{N}\left\langle
X_{i},v\right\rangle^{2}-{\mathbb{E}}\left\langle
X_{i},v\right\rangle^{2}\right|+\|\Sigma\|\sqrt{N}.$

The bound of Theorem 2 concludes the proof. ∎

In the regime $p>4$, we show how to adapt the proposed estimator to obtain the
optimal dependence on the contamination level $\eta$. The main insight is to
interpret our estimator as a second order version of the trimmed mean
estimator of Lugosi and Mendelson [48]. Our proof mainly follows their steps,
however two important modifications are required: First, we need to exploit
Theorem 2 when controlling the expected supremum of quadratic processes, while
in [48] the control of the corresponding process follows from a simple
application of the Cauchy-Schwartz inequality. To do so, we also need to
truncate the norms of our observations as explained after Proposition 7.
Second, since the quadratic forms of interest are non-negative, we consider
only a one-sided truncation. The main theorem of this section is the following
result.

######  Theorem 5.

Assume that $X$ is a zero mean random vector with covariance $\Sigma$
satisfying the $L_{p}-L_{2}$ norm equivalence with $p>4$. Fix the corruption
level $\eta\in[0,1]$ and the confidence level $\delta\in(0,1)$. Then there
exists an estimator $\widehat{\Sigma}_{\eta,\delta}$ such that, with
probability at least $1-\delta$,

$\left\|\widehat{\Sigma}_{\eta,\delta}-\Sigma\right\|\leqslant
C(p)\|\Sigma\|\left(\sqrt{\frac{\mathbf{r}(\Sigma)+\log(1/\delta)}{n}}+\kappa(p)^{2}\eta^{1-2/p}\right).\
$

Here $C(p)$ is a non-increasing function of $p$ that satisfies $C(p)\to\infty$
as $p\to 4$.

Let us first recall the form of our estimator in the case where $p=4$. For
some specifically chosen $\lambda>0$, the estimator in Theorem 4 is defined by
the following set

$\Gamma=\bigcap\limits_{v\in
S^{d-1}}\left\\{A\in\mathbb{S}_{+}^{d}:\left|\frac{1}{\lambda
N}\sum\limits_{i=1}^{N}\psi\left(\lambda\langle\widetilde{X}_{i},v\rangle^{2}\right)-v^{\mathsf{T}}Av\right|\leqslant
C\lambda\kappa^{4}\|\Sigma\|^{2}/2\right\\},$

where $\psi(\cdot)$ is the truncation function given by (2). We defined
$\widehat{\Sigma}_{\eta,\delta}$ to be any matrix in $\Gamma$. In the regime
$p>4$, we introduce a more involved estimator that uses a direction dependent
value of the one-sided threshold. For simplicity, we assume that we observe a
sample of size $2N$. For a set of positive semi-definite matrices $\Gamma$, we
define its diameter as $\Delta(\Gamma)=\sup_{A,B\in\Gamma}\|A-B\|$.

The estimator in Theorem 5 1. Given the confidence level $\delta$, the
corruption level $\eta$ and the $\eta$-corrupted sample
$\widetilde{Y}_{1},\ldots,\widetilde{Y}_{2N}$, we split the sample in two
parts of equal size: Truncate each vector
$\widetilde{Z}_{i}=\widetilde{Y}_{i}\mathbbm{1}\\{\|\widetilde{Y}_{i}\|\leqslant
R\\}$ for $i\in\\{1,\ldots,N\\}$ and
$\widetilde{X}_{i}=\widetilde{Y}_{i}\mathbbm{1}\\{\|\widetilde{Y}_{i}\|\leqslant
R\\}$ for $i\in\\{N+1,\ldots,2N\\}$, where
$R=(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/4}$. 2. Set
$\varepsilon=\max\left(20\eta,560\frac{\log(2/\delta)}{N}\right)$. 3. For the
first half of the sample, define
$q_{v}=(\langle\widetilde{Z}_{i},v\rangle^{2})_{N\varepsilon/2}^{\ast}$. 4.
For the second half of the sample
$\widetilde{X}_{1},\ldots,\widetilde{X}_{N}$, we proceed as follows: For every
$Q>0,v\in S^{d-1}$, define the trimming level $\lambda_{v}(Q)=(q_{v}+Q)^{-1}$
and set $\Gamma(Q)=\bigcap\limits_{v\in
S^{d-1}}\left\\{A\in\mathbb{S}_{+}^{d}:\left|\frac{1}{\lambda_{v}(Q)N}\sum_{i=1}^{N}\psi\left(\lambda_{v}(Q)\langle\widetilde{X}_{i},v\rangle^{2}\right)-v^{\mathsf{T}}Av\right|\leqslant
4\varepsilon Q\right\\}.$ 5. Let $\widehat{\Sigma}_{\eta,\delta}$ be any
matrix in the set $\Gamma(2^{i^{\ast}})$, where $i^{\ast}$ minimizes the
diameter $\Delta(\Gamma(2^{i}))$ over all integers $i$ subject to be non-
empty.

######  Remark 5.

Due to the bounds in Section 3.1, we explicitly assume the knowledge of the
operator norm $\|\Sigma\|$ and the effective rank $\mathbf{r}(\Sigma)$ up to
multiplicative constant factors.

Our first technical observation is that, by truncating the norms of the
vectors at the level $R=(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/4}$, the
covariance matrix does not change too much. At the same time, the truncation
allows us to apply Theorem 2 in our analysis.

######  Proposition 7.

Assume that $Y$ is a zero mean random vector with covariance $\Sigma$
satisfying the $L_{p}-L_{2}$ _norm equivalence_ with $p\geqslant 4$. Consider
the truncated vector
$X=Y\mathbbm{1}\\{\|Y\|\leqslant(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/4}\\}$
and define $\widetilde{\Sigma}={\mathbb{E}}X\otimes X$. It holds that

$\|\Sigma-\widetilde{\Sigma}\|\leqslant\kappa(4)^{4}\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}.$

Moreover, $\|\widetilde{\Sigma}\|\leqslant\|\Sigma\|$ and
$\operatorname{Tr}(\widetilde{\Sigma})\leqslant\operatorname{Tr}(\Sigma)$.

###### Proof.

The proof follows from the proof Lemma 2.1 in [54]. For the second part of the
proof we observe that $\Sigma-\widetilde{\Sigma}$ is positive semi-definite. ∎

The result of Proposition 7 allows us to focus on estimating the matrix of
second moments $\widetilde{\Sigma}$. Indeed, by the triangle inequality, the
estimator $\widehat{\Sigma}_{\eta,\delta}$ satisfies

$\|\widehat{\Sigma}_{\eta,\delta}-\Sigma\|\leqslant\|\widehat{\Sigma}_{\eta,\delta}-\widetilde{\Sigma}\|+\kappa(4)^{4}\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}},$

and the last term only affects the multiplicative constant factors in our
bound. We proceed by defining the following quantity

$Q_{0}=C_{Q_{0}}\max\left\\{\frac{1}{\varepsilon}\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)+\log(2/\delta)}{N}},\varepsilon^{-2/p}\kappa(p)^{2}\|\Sigma\|\right\\}.$

Here $C_{Q_{0}}=C_{Q_{0}}(p)>0$ is to be chosen later, depends only on $p$ and
is non-increasing with respect to $p$. The first term in the definition above
is responsible for the rate in the uncontaminated case and the second term
captures the rate of $\eta$ according to the value of $p$. We start with an
important lemma that is the second order analog of [48, Lemma 1]. For the rest
of this section, $\widetilde{\Sigma}$ is the matrix of second moments of the
truncated vector
$X=Y\mathbbm{1}\\{\|Y\|\leqslant(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/4})\\}$
and $\varepsilon=\max\left(20\eta,560\frac{\log(2/\delta)}{N}\right)$.

######  Lemma 6.

Let $Y\in\mathbb{R}^{d}$ be a mean zero random vector satisfying the
$L_{p}-L_{2}$ norm equivalence assumption with $p>4$. Let $Y_{1},\ldots,Y_{N}$
be i.i.d. copies of $Y$ and set
$Z_{i}=Y_{i}\mathbbm{1}\\{\|Y_{i}\|\leqslant(N\operatorname{Tr}(\Sigma)\|\Sigma\|)^{1/4})\\}$
for every $i\in[N]$, then, with probability at least $1-\delta/2$,

$\sup_{v\in S^{d-1}}\left|\left\\{i\in[N]:\langle
Z_{i},v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v\geqslant
Q_{0}\right\\}\right|\leqslant\frac{\varepsilon}{4}N.$

###### Proof.

For simplicity of notation, we write $\overline{Z}_{i}(v)=\langle
Z_{i},v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v$. The proof is a standard
application of a small ball argument in empirical process theory. Consider a
function $\xi:\mathbb{R}\rightarrow\mathbb{R}$ defined by

$\xi(x)=\begin{cases}0,&x\leqslant Q_{0}/2,\\\
\frac{2x}{Q_{0}}-1,&x\in(Q_{0}/2,Q_{0}],\\\ 1,&x>Q_{0}.\end{cases}$

It is clear that $\mathbbm{1}\\{\overline{Z}_{i}(v)\geqslant
Q_{0}\\}\leqslant\xi(\overline{Z}_{i}(v))\leqslant\mathbbm{1}\\{\overline{Z}_{i}(v)\geqslant
Q_{0}/2\\}$ and $\xi$ is a Lipschitz function with constant $2/Q_{0}$. By
symmetrization [26] and the contraction lemma for Rademacher processes [42,
Theorem 4.4], we have

$\begin{split}\mathbb{E}\sup_{v\in
S^{d-1}}\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}\\{\overline{Z}_{i}(v)\geqslant
Q_{0}\\}&\leqslant\mathbb{E}\sup_{v\in
S^{d-1}}\frac{1}{N}\sum_{i=1}^{N}\xi(\overline{Z}_{i}(v))\\\ &\leqslant
2\mathbb{E}\sup_{v\in
S^{d-1}}\frac{1}{N}\sum_{i=1}^{N}\left|\varepsilon_{i}\xi(\overline{Z}_{i}(v))\right|+\sup_{v\in
S^{d-1}}\mathbb{E}\xi(\overline{Z}_{i}(v))\\\
&\leqslant\frac{4}{Q_{0}}\mathbb{E}\sup_{v\in
S^{d-1}}\frac{1}{N}\left|\sum_{i=1}^{N}\varepsilon_{i}\overline{Z}_{i}(v)\right|+\sup_{v\in
S^{d-1}}\mathbb{E}\xi(\overline{Z}(v)).\end{split}$

Now, we define $C_{BY}=C_{BY}(p)>0$ to be the constant in the conclusion of
Corollary 1. We remark that $C_{BY}$ is at most an absolute constant for any
$p\geqslant c>4$, where $c$ is another absolute constant. We now apply
Corollary 1 and the same arguments as in its proof and obtain

$\begin{split}\mathbb{E}\sup_{v\in
S^{d-1}}\frac{1}{N}\sum_{i=1}^{N}\left|\varepsilon_{i}(\langle
Z_{i},v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v)\right|&\leqslant\mathbb{E}\sup_{v\in
S^{d-1}}\frac{1}{N}\left|\sum_{i=1}^{n}\varepsilon_{i}\langle
Z_{i},v\rangle^{2}\right|+\frac{\|\Sigma\|}{N}\mathbb{E}\left|\sum_{i=1}^{N}\varepsilon_{i}\right|\\\
&\leqslant
2C_{BY}\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}\leqslant\frac{Q_{0}\varepsilon}{128}.\end{split}$

The last steps follow from the fact that $\mathbf{r}(\Sigma)\geqslant 1$ and
$\|\widetilde{\Sigma}\|\leqslant\|\Sigma\|$. By the definition of $Q_{0}$ we
conclude that the first term is at most $\frac{\varepsilon}{32}$ if we choose
a sufficiently large constant $C_{Q_{0}}>0$. We now proceed to bound the
second term. We use Markov’s inequality together with the $L_{p}-L_{2}$ norm
equivalence to obtain

$\begin{split}\mathbb{E}\xi\left(\langle
Z,v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v\right)\leqslant\mathbb{P}\left(\langle
Z,v\rangle^{2}\geqslant
Q/2+v^{\mathsf{T}}\widetilde{\Sigma}v\right)&\leqslant\frac{\kappa(p)^{p}}{\left(Q/2+v^{\mathsf{T}}\widetilde{\Sigma}v\right)^{p/2}}(\mathbb{E}\langle
Z,v\rangle^{2})^{p/2}\\\
&\leqslant\left(\frac{2\kappa(p)^{2}\|\Sigma\|}{Q}\right)^{p/2}.\end{split}$

Again, by the definition of $Q_{0}$, we can choose $C_{Q_{0}}>0$ such that the
right hand side above is at most $\frac{\varepsilon}{32}$. By Talagrand’s
concentration inequality for supremum of empirical process (Massart’s version
[49]), with probability at least $1-\exp(-x)$,

$\sup_{v\in
S^{d-1}}\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}\\{\overline{Z}_{i}(v)\geqslant
Q\\}\leqslant\frac{\varepsilon}{8}+\sqrt{\frac{8x}{N}}\frac{\sqrt{\varepsilon}}{8}+\frac{35x}{N}.$

We choose $x=\varepsilon N/560$ to conclude the proof. ∎

We now describe the first part of the estimation procedure. First, we assume
without loss of generality that $\varepsilon<1$. When the conclusion of the
previous lemma holds, we immediately obtain that, for every $v\in S^{d-1}$ and
$Q\in(2Q_{0},4Q_{0})$,

$\quad q_{v}-v^{\mathsf{T}}\widetilde{\Sigma}v+Q\leqslant
5Q_{0}\quad\text{and}\quad q_{v}-v^{\mathsf{T}}\widetilde{\Sigma}v+Q\geqslant
Q_{0}.$

To see why the latter condition holds, suppose by contradiction that
$q_{v}-v^{\mathsf{T}}\widetilde{\Sigma}v+Q\leqslant Q_{0}$, then
$q_{v}\leqslant v^{\mathsf{T}}\widetilde{\Sigma}v-Q_{0}$. Since
$\varepsilon<1$, by the choice of $Q_{0}$, we have $Q_{0}>\|\Sigma\|$ and then
we get $0\leqslant q_{v}\leqslant v^{\mathsf{T}}\widetilde{\Sigma}v-Q_{0}<0$,
the latter is clearly a contradiction. Moreover, both inequalities above still
hold for an $\eta$-corrupted sample, since $\varepsilon\geqslant 20\eta$ and
by the definition of $\varepsilon$, we have that the fraction of points
greater than $Q_{0}$ is at most
$\frac{\varepsilon}{4}+\eta\leqslant\varepsilon(\frac{1}{20}+\frac{1}{4})<\frac{\varepsilon}{2}$.
Thus, we can use $\widetilde{Z}_{1},\ldots,\widetilde{Z}_{N}$ to estimate
$q_{v}$, and since they are independent from the second half of the sample,
from now on we work conditionally on the event of Lemma 6.

The second part of the analysis consists in proving that $\Gamma(v,Q)$ is non-
empty. The formal statement is the proposition below.

######  Proposition 8.

Under the notation of Theorem 5, fix $Q\in[2Q_{0},4Q_{0}]$ and assume that the
event of Lemma 6 holds. There exists an absolute constant $C>0$ such that if
$C_{Q_{0}}\geqslant C$, then, with probability at least $1-\delta/2$,

$\sup_{v\in
S^{d-1}}\left|\frac{1}{\lambda_{v}(Q)N}\sum_{i=1}^{N}\psi\left(\lambda_{v}(Q)\langle\widetilde{X}_{i},v\rangle^{2}\right)-v^{\mathsf{T}}\widetilde{\Sigma}v\right|\leqslant
4\varepsilon Q.$

It will be convenient to work with two a sided truncation function in the
analysis. We define the following function for arbitrary positive
$\lambda_{1}\geqslant\lambda_{2}$,

$\psi_{\lambda_{1},\lambda_{2}}(x)=\begin{cases}\frac{1}{\lambda_{2}},\quad
x>\frac{1}{\lambda_{2}},\\\ x,\quad
x\in[\frac{1}{\lambda_{1}},\frac{1}{\lambda_{2}}],\\\
\frac{1}{\lambda_{1}},\quad x<\frac{1}{\lambda_{1}}.\end{cases}$

Clearly, if $\lambda_{1}=\lambda_{2}=\lambda$, our definition agrees with (2).
That is, $\frac{1}{\lambda}\psi(\lambda x)=\psi_{\lambda,\lambda}(x)$.

###### Proof.

First, for every $v\in S^{d-1}$, due to the assumption that the event of Lemma
6 holds, the uncorrupted observations satisfy

$\left|\frac{1}{\lambda_{v}(Q)N}\sum_{i=1}^{N}\psi\left(\lambda_{v}(Q)\langle\widetilde{X}_{i},v\rangle^{2}\right)-\frac{1}{\lambda_{v}(Q)N}\sum_{i=1}^{N}\psi\left(\lambda_{v}(Q)\langle
X_{i},v\rangle^{2}\right)\right|\leqslant 2\eta Q\leqslant\frac{\varepsilon
Q}{10}.$

We centralize the empirical process to obtain that

$\frac{1}{\lambda_{v}(Q)N}\sum_{i=1}^{N}\psi\left(\lambda_{v}(Q)\langle
X_{i},v\rangle^{2}\right)-v^{\mathsf{T}}\widetilde{\Sigma}v=\frac{1}{\lambda_{v}^{c}(Q)N}\sum_{i=1}^{N}\psi\left(\lambda_{v}^{c}(Q)(\langle
X_{i},v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v)\right),$

where $\lambda_{v}^{c}(Q)=(q_{v}+Q-v^{\mathsf{T}}\widetilde{\Sigma}v)^{-1}$.
To see why this identity holds, observe that both sides are equal except when
$\langle X_{i},v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v\leqslant-
q_{v}-Q+v^{\mathsf{T}}\widetilde{\Sigma}v$. In this case, $0\leqslant\langle
X_{i},v\rangle^{2}\leqslant-q_{v}-Q+2v^{\mathsf{T}}\widetilde{\Sigma}v$.
However, since $Q\geqslant 2\|\Sigma\|$ if $C_{Q_{0}}\geqslant 2$ and
$\varepsilon<1$, the latter inequality cannot be satisfied. Now, on the event
of Lemma 6, $Q_{0}\leqslant q_{v}-v^{\mathsf{T}}\widetilde{\Sigma}v+Q\leqslant
5Q_{0}$ and therefore

$\frac{1}{\lambda_{v}^{c}(Q)N}\sum_{i=1}^{N}\psi\left(\lambda_{v}^{c}(Q)(\langle
X_{i},v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v)\right)\leqslant\frac{1}{N}\sum_{i=1}^{N}\psi_{-\frac{1}{Q_{0}},\frac{1}{5Q_{0}}}\left(\langle
X_{i},v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v\right).$

We define $\overline{U}_{Q}(v)$ to be the right hand side in the inequality
above. We first study how the empirical process of interest concentrates
around the mean. To simplify the analysis, we consider a simpler quantity,
$\overline{W}_{Q}(v)=\frac{1}{N}\sum_{i=1}^{N}\psi_{\frac{-1}{3Q},\frac{1}{3Q}}\left(\langle
X_{i},v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v\right)$. Our starting
point is

$\displaystyle\sup_{v\in
S^{d-1}}(\overline{U}_{Q}(v)-\mathbb{E}\overline{U}_{Q}(v))$
$\displaystyle\leqslant\sup_{v\in
S^{d-1}}(\overline{U}_{Q}(v)-\overline{W}_{Q}(v))+\sup_{v\in
S^{d-1}}(\overline{W}_{Q}(v)-\mathbb{E}\overline{W}_{Q}(v))$
$\displaystyle\qquad+\sup_{v\in
S^{d-1}}(\mathbb{E}\overline{W}_{Q}(v)-\mathbb{E}\overline{U}_{Q}(v))$
$\displaystyle=(a)+(b)+(c).$

For the first term, observe that it is non-zero if and only if the argument of
the function is above $5Q_{0}$ or below $-Q_{0}$. The latter cannot happen
because of the same contradiction argument as above. The magnitude of the
difference is at most $3Q$. By Lemma 6, there are at most $\varepsilon N/4$
points in the range $(5Q_{0},\infty)$, therefore, we obtain that the first
term (a) is at most $\frac{3\varepsilon Q}{4}$. Similarly, we apply the Markov
inequality together with the $L_{p}-L_{2}$ norm equivalence assumption to
obtain that

$\begin{split}\sup_{v\in
S^{d-1}}\mathbb{E}\left(\overline{W}_{Q}(v)-\overline{U}_{Q}(v)\right)&\leqslant
3Q\mathbb{P}(\langle
X,v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v>5Q_{0})\\\ &\leqslant
3Q\left(\frac{\kappa(p)^{2}\|\Sigma\|}{5Q_{0}}\right)^{p/2}\leqslant\frac{3\varepsilon
Q}{32}.\end{split}$

This concludes the bound for (c). The second term (b) is handled via
Talagrand’s concentration inequality for empirical processes (Massart’s
version [49]). Observe that, for every $v\in S^{d-1}$,

$\left|\psi_{-\frac{1}{3Q},\frac{1}{3Q}}\left(\langle
X,v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v\right)\right|\leqslant
3Q\quad\text{and}\quad\mathbb{E}\left|\psi_{-\frac{1}{3Q},\frac{1}{3Q}}\left(\langle
X,v\rangle^{2}\right)\right|^{2}\leqslant\mathbb{E}\langle
X,v\rangle^{4}\leqslant\kappa(4)^{4}\|\Sigma\|^{2}.$

Moreover, for every $Q>0$, $\psi(\cdot)_{-\frac{1}{Q},\frac{1}{Q}}$ is a
$1$-Lipschitz function that passes through the origin. By the same
symmetrization and contraction arguments as in the proof of Lemma 6, we obtain
that

$\mathbb{E}\sup_{v\in
S^{d-1}}\left|\overline{W}_{Q}(v)-\mathbb{E}\overline{W}_{Q}(v)\right|\leqslant
2\mathbb{E}\sup_{v\in S^{d-1}}\left|\sum_{i=1}^{N}\varepsilon_{i}\langle
X_{i},v\rangle^{2}\right|\leqslant
2C_{BY}\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}.$

Therefore, by Talagrand’s concentration inequality for empirical processes,
with probability at least $1-2e^{-x}$, it holds that

$\sup_{v\in S^{d-1}}|W_{Q}(v)-\mathbb{E}W_{Q}(v)|\leqslant
4C_{BY}\|\Sigma\|\sqrt{\frac{\mathbf{r}(\Sigma)}{N}}+\kappa(4)^{2}\|\Sigma\|\sqrt{\frac{8x}{N}}+105Q\frac{x}{N}.$

We choose $x=2\log(2/\delta)$ to obtain that the right hand side above is less
than $\frac{\varepsilon Q}{2}$. Now, the problem boils down to control
uniformly the typical magnitude of $\overline{U}_{Q}(v)$. For simplicity, we
define $\overline{X}_{i}(v)=\langle
X_{i},v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v$ and write

$\begin{split}\sup_{v\in S^{d-1}}\mathbb{E}\overline{U}_{Q}(v)&=\sup_{v\in
S^{d-1}}\mathbb{E}[\psi_{-\frac{1}{Q_{0}},\frac{1}{5Q_{0}}}(\langle
X,v\rangle^{2}-v^{\mathsf{T}}\widetilde{\Sigma}v))(\mathbbm{1}\\{\overline{X}_{i}(v)\leqslant
5Q_{0}\\}+\mathbbm{1}\\{\overline{X}_{i}(v)>5Q_{0}\\})]\\\
&\leqslant\sup_{v\in
S^{d-1}}5Q_{0}\mathbb{E}\mathbbm{1}\\{\overline{X}(v)\geqslant 5Q_{0}\\}\\\
&\leqslant 5Q\frac{\varepsilon}{64}.\end{split}$

The final bound for the first part becomes $\varepsilon
Q(\frac{1}{10}+\frac{3}{4}+\frac{3}{32}+\frac{5}{64}+\frac{1}{2})\leqslant
2\varepsilon Q$. For the other side bound, observe that

$\begin{split}v^{\mathsf{T}}\widetilde{\Sigma}v-\frac{1}{\lambda_{v}(Q)N}\sum_{i=1}^{N}\psi(\lambda_{v}(Q)\langle
X_{i},v\rangle^{2})&=\frac{1}{\lambda_{v}^{c}(Q)N}\sum_{i=1}^{N}\psi\left(\lambda_{v}^{c}(Q)v^{\mathsf{T}}\widetilde{\Sigma}v-\langle
X_{i},v\rangle^{2}\right)\\\
&\leqslant\frac{1}{N}\sum_{i=1}^{N}\psi_{-\frac{1}{Q_{0}},\frac{1}{5Q_{0}}}\left(v^{\mathsf{T}}\widetilde{\Sigma}v-\langle
X_{i},v\rangle^{2}\right).\end{split}$

The same analysis follows and concludes the proof. ∎

The proof of Theorem 5 follows directly from Lemma 6 and Proposition 8.
Indeed, consider the event $\mathcal{E}$ where the events of both Lemma 6 and
Proposition 8 hold. It occurs with probability at least $1-\delta$ as desired.
Our next argument is standard in the literature [48] and is similar to
Lepskii’s method [43]. Let $i_{0}$ be the smallest integer satisfying
$2^{i_{0}}\in(2Q_{0},4Q_{0})$. By Lemma 6 we know that at most
$\frac{\varepsilon N}{4}$ samples are outside of the range $q_{v}+2^{i_{0}}$.
We conclude that the the difference between $U_{Q}(v)$ and $U_{2Q}(v)$ is at
most $\frac{\varepsilon Q}{2}$. By induction, this implies that
$\Gamma(2^{i_{0}})\subset\Gamma(2^{i_{0}+1})$ for every $i\geqslant i_{0}$.
This implies that corresponding sets are nested. The diameter of the set
$\bigcap_{i\geqslant i^{\ast}}\Gamma(2^{i})$ is at most $8\varepsilon Q$ and
the matrix of second moments $\widetilde{\Sigma}$ belongs to an even smaller
set. Thus, $\|\hat{\Sigma}-\widetilde{\Sigma}\|\leqslant 8\varepsilon Q$. We
conclude by applying Proposition 7. ∎

##  5 Optimality

It is natural to ask about the optimality of our statistical guarantees of
Theorem 1. It is well known that the term
$C\|\Sigma\|\sqrt{\mathbf{r}(\Sigma)/N}$ appears in the minimax lower bound
for covariance estimation [44, Theorem 2] as well as in the lower bound for
the performance of the sample covariance matrix in the Gaussian case [40,
Theorem 4]. Clearly, this term is necessary because the adversary can always
leave the sample uncorrupted and the multivariate Gaussian distribution
satisfies the norm equivalence assumption (1). Further, we show that the term
$C\|\Sigma\|\sqrt{\log(1/\delta)/N}$ cannot be improved in general. As shown
in [54] (following the lower bound in [46]), the term scaling as
$R\sqrt{\log(1/\delta)/N}$ appears in the lower bound for any estimator of the
covariance matrix. Here $R^{2}$ is the so-called _weak variance_ defined by

$R^{2}=\sup\nolimits_{v\in S^{d-1}}{\mathbb{E}}\left(v^{\mathsf{T}}(X\otimes
X-{\mathbb{E}}X\otimes X)v\right)^{2}.$

In the multivariate Gaussian case, using the standard relation between
moments, we get

$R^{2}\geqslant\sup\nolimits_{v\in S^{d-1}}{\mathbb{E}}\langle
v,X\rangle^{4}-\|\Sigma\|^{2}=3\sup\limits_{v\in S^{d-1}}({\mathbb{E}}\langle
v,X\rangle)^{2}-\|\Sigma\|^{2}=2\|\Sigma\|^{2}.$

This shows the necessity of the term $C\|\Sigma\|\sqrt{\log(1/\delta)/N}$ in
Theorem 1.

Finally, we can restrict the discussion to the convergence rate with respect
to the fraction of corrupted samples $\eta$. Some closely related lower bounds
with matching rates of convergence appear in the analysis of the sparse vector
model [20, Theorem 5 and Theorem 6]. Their model can be seen as a special case
of our setup when $d=1$. Instead of exploiting their techniques for the lower
bounds, we provide a separate analysis using explicit examples. Our key
argument to derive the minimax optimality with respect to $\eta$ is to reduce
our problem to a mean estimation problem. For the mean estimation, a simple
computation shows a lower bound with respect to $\eta$. To describe this
result, we first consider a basic definition.

######  Definition 1.

For a random variable $X$, we define the quantile

$Q_{q}(X)=\sup\\{M\in\mathbb{R}:\mathbb{P}(X\geqslant M)\geqslant 1-q\\}.$

Formally, the following simple lower bound holds.

######  Proposition 9 (Inequality 2.3 in [48]).

Let $X$ be a random variable with mean $\mu$, variance $\sigma_{X}$, and with
an absolutely continuous distribution. Suppose that
$\widetilde{X}_{1},\ldots,\widetilde{X}_{N}$ is an $\eta$-corrupted sample
sampled according to the distribution of $X$. Let $\overline{X}=X-\mathbb{E}X$
and define $\varepsilon(\overline{X},\eta)$ as follows

$\varepsilon(\overline{X},\eta)=\max\left\\{\mathbb{E}|\overline{X}-Q_{\eta/2}(\overline{X})|\mathbbm{1}\\{\overline{X}\leqslant
Q_{\eta/2}(\overline{X})\\},\mathbb{E}|\overline{X}-Q_{1-\eta/2}(\overline{X})|\mathbbm{1}\\{\overline{X}\geqslant
Q_{1-\eta/2}(\overline{X})\\}\right\\}.$

Then, no estimator
$\widehat{\mu}=\widehat{\mu}(\widetilde{X}_{1},\ldots,\widetilde{X}_{N})$ of
the mean $\mu$ can perform better than

$|\widehat{\mu}-\mu|\leqslant\varepsilon(\overline{X},\eta).$

To obtain the minimax rates with respect to $\eta$, it is enough to restrict
our attention to the one dimensional case. Assume that the distribution of a
zero mean random variable $X$ satisfies the $L_{4}-L_{2}$ norm equivalence
(1). That is, for some $\kappa\geqslant 1$, it holds that
$\left({\mathbb{E}}X^{4}\right)^{1/4}\leqslant\kappa\left({\mathbb{E}}X^{2}\right)^{1/2}$.
Denote $Y=X^{2}$ and observe that $Y$ is non-negative. In this case, the
estimation of the variance of $X$ can be seen as the estimation of the mean of
$Y$. The norm equivalence assumption can be rewritten as
$\left({\mathbb{E}}Y^{2}\right)^{1/2}\leqslant\kappa^{2}{\mathbb{E}}Y.$

######  Example 1 (Optimality of the $\sqrt{\eta}$-term when $p=4$).

First, a few intermediate random variables are considered before the
definition of $Y$. Define

$Y_{1}=\begin{cases}-\frac{1}{\sqrt{\eta}},&\text{with probability}\
\frac{\eta}{2},\\\ -1,&\text{with probability}\frac{1-\eta}{2},\\\
1,&\text{with probability}\ \frac{1-\eta}{2},\\\
\frac{1}{\sqrt{\eta}},&\text{with probability}\ \frac{\eta}{2}.\end{cases}$

Clearly $\mathbb{E}Y_{1}=0$. Let $\sigma_{Y_{1}}$ denote the standard
deviation of $Y_{1}$. It holds that

$\sigma_{Y_{1}}=(\mathbb{E}Y_{1}^{2})^{1/2}=\sqrt{2-\eta}\leqslant\sqrt{2}.$

Assume that $\eta\leqslant 1/4$. We have $Q_{\eta/2}(Y_{1})=-1$. Indeed,
$\mathbb{P}(Y_{1}\geqslant-1)=1-\frac{\eta}{2}$ and $\mathbb{P}(Y_{1}\geqslant
1)=\frac{1}{2}<1-\frac{\eta}{2}$. We conclude that

$\varepsilon(Y_{1},\eta)\geqslant\mathbb{E}|Y_{1}+1|\mathbbm{1}\\{Y_{1}\leqslant-1\\}=\left(\frac{1}{\sqrt{\eta}}-1\right)\frac{\eta}{2}=\frac{\sqrt{\eta}}{2}-\frac{\eta}{2}\geqslant\frac{1}{4}\sqrt{\eta}.$

We now consider the random variable
$Y_{2}=\frac{\sigma^{2}}{\sqrt{2-\eta}}Y_{1}$, where $\sigma>0$ is a positive
real number. It still holds that $\mathbb{E}Y_{2}=0$, but now,
$(\mathbb{E}Y_{2}^{2})^{1/2}=\sigma^{2}$. By homogeneity, we have

$\varepsilon(Y_{2},\eta)\geqslant\frac{\sigma^{2}\sqrt{\eta}}{4\sqrt{2-\eta}}\geqslant\frac{\sigma^{2}\sqrt{\eta}}{4\sqrt{2}}.$

Finally, observe that $Y=Y_{2}+\|Y_{2}\|_{\infty}$ is a non-negative random
variable and $\varepsilon(Y,\eta)=\varepsilon(Y_{2},\eta)$ since the
difference between $Y$ and $Y_{2}$ is a constant. We conclude by observing
that ${\mathbb{E}}Y=\|Y_{2}\|_{\infty}$ and
${\mathbb{E}}Y^{2}={\mathbb{E}}Y_{2}^{2}+\|Y_{2}\|^{2}_{\infty}\leqslant
2\|Y_{2}\|^{2}_{\infty}$. Thus, the norm equivalence assumption
$\left({\mathbb{E}}Y^{2}\right)^{1/2}\leqslant\kappa^{2}{\mathbb{E}}Y$ holds
with $\kappa^{2}=\sqrt{2}$.

We now present an example that attains the sub-exponential minimax rate in the
mean estimation and therefore confirms the optimality of our covariance
estimation results in the sub-Gaussian case. Indeed, observe that if $X$ is a
sub-Gaussian random variable, then $Y=X^{2}$ is a sub-exponential random
variable (see [72, Lemma 2.7.6]). Therefore, when making a reduction from
covariance estimation to a mean estimation problem as in Example 1, we have to
analyze the mean estimation problem in the sub-exponential regime. We note
that a similar sub-Gaussian construction appears in [48, Remark before Section
2.1]222To make their construction work in the Gaussian case, we changed the
definition of $Q$, so that it becomes an $\eta/4$-quantile instead of an
$\eta/2$-quantile claimed in [48]..

######  Example 2 (Optimality of $\eta\log(1/\eta)$-term in sub-Gaussian
covariance estimation).

Let
$Y=\min\\{1,|g|^{2}\\}\mathbbm{1}\\{|g|^{2}<Q\\}+|g|^{2}\mathbbm{1}\\{|g|^{2}\geqslant
Q\\}$, where $g$ is a standard Gaussian random variable and $Q$ is such that
$\mathbb{P}(|g|^{2}\geqslant Q)=\eta/4$. Consequently, we have
$\mathbb{P}(|g|\geqslant\sqrt{Q})=\eta/4$. It is easy to see that for $\eta$
sufficiently small, it holds that $Q>1$. Let us now prove that
$Q_{1-\eta/2}(Y)=1$. Indeed, since $\mathbb{P}(Y\geqslant
1)=\mathbb{P}(|g|\geqslant 1)>\eta/2$ for small enough $\eta$, then
$Q_{1-\eta/2}(Y)\geqslant 1$. It is clear that if $Q_{1-\eta/2}(Y)>1$, then
$Q_{1-\eta/2}(Y)\geqslant Q$, which contradicts $\mathbb{P}(|g|^{2}\geqslant
Q)=\eta/4<\eta/2$. Thus, we have

$\varepsilon(\overline{Y},\eta)\geqslant\mathbb{E}|\overline{Y}-Q_{1-\eta/2}(\overline{Y})|\mathbbm{1}\\{\overline{Y}\geqslant
Q_{1-\eta/2}(\overline{Y})\\}=\mathbb{E}(Y-1)\mathbbm{1}\\{Y\geqslant 1\\}.$

This leads to

$\displaystyle\mathbb{E}(Y-1)\mathbbm{1}\\{Y\geqslant 1\\}$
$\displaystyle=\mathbb{E}Y\mathbbm{1}\\{1\leqslant
Y<Q\\}+\mathbb{E}Y\mathbbm{1}\\{Y\geqslant Q\\}-\mathbb{P}(Y\geqslant 1)$
$\displaystyle=\mathbb{P}(1\leqslant|g|^{2}<Q)+\mathbb{E}|g|^{2}\mathbbm{1}\\{|g|^{2}\geqslant
Q\\}-\mathbb{P}(|g|^{2}\geqslant 1)$
$\displaystyle=\mathbb{E}|g|^{2}\mathbbm{1}\\{|g|^{2}\geqslant
Q\\}-\mathbb{P}(|g|^{2}\geqslant Q).$

Using the standard computation (see [72, Exercise 2.1.4]), we obtain

$\mathbb{E}|g|^{2}\mathbbm{1}\\{|g|^{2}\geqslant
Q\\}=\frac{2}{\sqrt{2\pi}}\sqrt{Q}\exp(-Q/2)+\mathbb{P}(|g|\geqslant\sqrt{Q}).$

Therefore, since $\eta/4=\mathbb{P}(|g|\geqslant\sqrt{Q})$, and by the
standard Gaussian integration [72, Proposition 2.1.2] we have

$\varepsilon(\overline{Y},\eta)\geqslant\frac{2}{\sqrt{2\pi}}\sqrt{Q}\exp(-Q/2)\geqslant
Q\mathbb{P}(|g|\geqslant\sqrt{Q})=\frac{Q\eta}{4}.$

Using the same Gaussian integration formula, we conclude that, in order to get
$\mathbb{P}(|g|\geqslant\sqrt{Q})=\eta/4$, we need to choose
$Q\sim\log\left(1/\eta\right)$. This implies that

$\varepsilon(\overline{Y},\eta)\geqslant\frac{Q\eta}{4}\gtrsim\eta\log\left(1/\eta\right).$

We claim that the rate $\eta\log\left(1/\eta\right)$ is sharp. To do so, we
compute the upper bound with respect to $\eta$ in Theorem 1. If the original
random variable $X$ is a sub-Gaussian, then $\kappa(p)^{2}\sim p$ for every
$p\geqslant 1$ (see [72, Proposition 2.5.2]) and the upper bound scales as
$\eta p/\eta^{2/p}$. We choose $p\sim\log\left(1/\eta\right)$ to optimize the
fraction and obtain the claimed rate.

Finally, we note that for the Gaussian case, it is possible to achieve a
slightly improved dependence on $\eta$ by eliminating the logarithmic factor
$\log(1/\eta)$ (as shown in the follow-up work of Minasyan and the second-
named author of this paper [55]), owing to the rotational invariance property
of the Gaussian distribution. As discussed in [55], the estimator needs to be
tailored to the Gaussian distribution and therefore it cannot be applied to
the more general setup considered in our Theorem 1.

#### Acknowledgments.

The authors would like to thank Afonso Bandeira for several valuable
discussions, and Alexander Tsybakov for pointing out the connection with [20].
Nikita Zhivotovskiy is funded in part by ETH Foundations of Data Science (ETH-
FDS).

## References

  * [1] R. Adamczak, A. Litvak, A. Pajor, and N. Tomczak-Jaegermann.  Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles.  Journal of the American Mathematical Society, 23(2):535–561, 2010\.
  * [2] G. Appert and O. Catoni.  New bounds for $k$-means and information $k$-means.  arXiv preprint arXiv:2101.05728, 2021.
  * [3] J.-Y. Audibert and O. Catoni.  Robust linear least squares regression.  The Annals of Statistics, 39(5):2766–2794, 2011.
  * [4] Z. D. Bai and Y. Q. Yin.  Limit of the smallest eigenvalue of a large dimensional sample covariance matrix.  The Annals of Probability, 21(3):1275 – 1294, 1993.
  * [5] P. J. Bickel.  On some robust estimates of location.  The Annals of Mathematical Statistics, pages 847–858, 1965.
  * [6] P. J. Bickel and E. Levina.  Covariance regularization by thresholding.  The Annals of Statistics, 36(6):2577–2604, 2008.
  * [7] P. J. Bickel and E. Levina.  Regularized estimation of large covariance matrices.  The Annals of Statistics, 36(1):199–227, 2008.
  * [8] J. Bourgain.  Random points in isotropic convex sets.  Convex Geometric Analysis, 34:53–58, 1996.
  * [9] C. Brownlees, E. Joly, and G. Lugosi.  Empirical risk minimization for heavy-tailed losses.  The Annals of Statistics, 43(6):2507–2536, 2015.
  * [10] T. T. Cai, Z. Ren, and H. H. Zhou.  Optimal rates of convergence for estimating toeplitz covariance matrices.  Probability Theory and Related Fields, 156(1):101–143, 2013.
  * [11] T. T. Cai, Z. Ren, and H. H. Zhou.  Estimating structured high-dimensional covariance and precision matrices: Optimal rates and adaptive estimation.  Electronic Journal of Statistics, 10(1):1–59, 2016.
  * [12] T. T. Cai, C.-H. Zhang, and H. H. Zhou.  Optimal rates of convergence for covariance matrix estimation.  The Annals of Statistics, 38(4):2118–2144, 2010.
  * [13] O. Catoni.  Challenging the empirical mean and empirical variance: a deviation study.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 48(4):1148–1185, 2012.
  * [14] O. Catoni.  PAC-Bayesian bounds for the Gram matrix and least squares regression with a random design.  arXiv preprint arXiv:1603.05229, 2016.
  * [15] O. Catoni and I. Giulini.  Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression.  arXiv preprint arXiv:1712.02747, 2017.
  * [16] M. Chen, C. Gao, and Z. Ren.  Robust covariance and scatter matrix estimation under Huber’s contamination model.  The Annals of Statistics, 46(5):1932–1960, 2018.
  * [17] Y. Cheng, I. Diakonikolas, R. Ge, and D. P. Woodruff.  Faster algorithms for high-dimensional robust covariance estimation.  In Conference on Learning Theory, pages 727–757. PMLR, 2019.
  * [18] Y. Cherapanamjeri, S. B. Hopkins, T. Kathuria, P. Raghavendra, and N. Tripuraneni.  Algorithms for heavy-tailed statistics: Regression, covariance estimation, and beyond.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 601–609, 2020.
  * [19] G. Chinot, G. Lecué, and M. Lerasle.  Robust statistical learning with Lipschitz and convex loss functions.  Probability Theory and Related Fields, pages 1–44, 2019.
  * [20] L. Comminges, O. Collier, M. Ndaoud, and A. B. Tsybakov.  Adaptive robust estimation in sparse vector model.  The Annals of Statistics, 49(3):1347–1377, 2021.
  * [21] J. Depersin.  Robust subgaussian estimation with VC-dimension.  arXiv preprint arXiv:2004.11734, 2020.
  * [22] I. Diakonikolas and D. M. Kane.  Recent advances in algorithmic high-dimensional robust statistics.  arXiv preprint arXiv:1911.05911, 2019.
  * [23] I. Diakonikolas, D. M. Kane, J. C. Lee, and A. Pensia.  Outlier-robust sparse mean estimation for heavy-tailed distributions.  arXiv preprint arXiv:2211.16333, 2022.
  * [24] N. El Karoui.  Operator norm consistent estimation of large-dimensional sparse covariance matrices.  The Annals of Statistics, 36(6):2717–2756, 2008.
  * [25] N. El Karoui.  Random matrices and high-dimensional statistics: Beyond covariance matrices.  In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 2857–2876. World Scientific, 2018.
  * [26] E. Giné and J. Zinn.  Some limit theorems for empirical processes.  The Annals of Probability, pages 929–989, 1984.
  * [27] I. Giulini.  Robust PCA and pairs of projections in a Hilbert space.  Electronic Journal of Statistics, 11(2):3903–3926, 2017.
  * [28] I. Giulini.  Robust dimension-free Gram operator estimates.  Bernoulli, 24(4B):3864–3923, 2018.
  * [29] O. Guédon, A. E. Litvak, A. Pajor, and N. Tomczak-Jaegermann.  On the interval of fluctuation of the singular values of random matrices.  Journal of the European Mathematical Society, 19(5):1469–1505, 2017\.
  * [30] F. R. Hampel.  A general qualitative definition of robustness.  The Annals of Mathematical Statistics, 42(6):1887–1896, 1971.
  * [31] W. Härdle, Y. Klochkov, A. Petukhina, and N. Zhivotovskiy.  Robustifying Markowitz.  Technical report, IRTG 1792 Discussion Paper, 2021.
  * [32] D. Hsu and S. Sabato.  Loss minimization and parameter estimation with heavy tails.  Journal of Machine Learning Research, 17(18):1–40, 2016.
  * [33] P. J. Huber.  Robust Estimation of a Location Parameter.  The Annals of Mathematical Statistics, 35(1):73 – 101, 1964.
  * [34] P. J. Huber.  Robust Statistics.  Wiley Series in Probability and Mathematical Statistics, 1981.
  * [35] R. Kannan, L. Lovász, and M. Simonovits.  Random walks and an ${O}^{*}(n^{5})$ volume algorithm for convex bodies.  Random Structures & Algorithms, 11(1):1–50, 1997.
  * [36] Y. Ke, S. Minsker, Z. Ren, Q. Sun, and W.-X. Zhou.  User-friendly covariance estimation for heavy-tailed distributions.  Statistical Science, 34(3):454–471, 2019.
  * [37] Y. Klochkov, A. Kroshnin, and N. Zhivotovskiy.  Robust k-means clustering for distributions with two moments.  The Annals of Statistics, 49(4):2206–2230, 2021.
  * [38] V. Koltchinskii.  Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: Ecole d’Eté de Probabilités de Saint-Flour XXXVIII-2008, volume 2033.  Springer Science & Business Media, 2011.
  * [39] V. Koltchinskii.  Asymptotically efficient estimation of smooth functionals of covariance operators.  Journal of the European Mathematical Society, 23(3):765–843, 2020\.
  * [40] V. Koltchinskii and K. Lounici.  Concentration inequalities and moment bounds for sample covariance operators.  Bernoulli, 23(1):110–133, 2017.
  * [41] C. Lam and J. Fan.  Sparsistency and rates of convergence in large covariance matrix estimation.  Annals of statistics, 37(6B):4254, 2009.
  * [42] M. Ledoux and M. Talagrand.  Probability in Banach Spaces: Isoperimetry and Processes.  Springer Science & Business Media, 2013.
  * [43] O. Lepskii.  Asymptotically minimax adaptive estimation. I: Upper bounds. Optimally adaptive estimates.  Theory of Probability & Its Applications, 36(4):682–697, 1992\.
  * [44] K. Lounici.  High-dimensional covariance matrix estimation with missing observations.  Bernoulli, 20(3):1029–1058, 2014.
  * [45] G. Lugosi and S. Mendelson.  Mean estimation and regression under heavy-tailed distributions: A survey.  Foundations of Computational Mathematics, 19(5):1145–1190, 2019\.
  * [46] G. Lugosi and S. Mendelson.  Near-optimal mean estimators with respect to general norms.  Probability Theory and Related Fields, 175:957–973, 2019.
  * [47] G. Lugosi and S. Mendelson.  Risk minimization by median-of-means tournaments.  Journal of the European Mathematical Society, 22(3):925–965, 2019\.
  * [48] G. Lugosi and S. Mendelson.  Robust multivariate mean estimation: The optimality of trimmed mean.  The Annals of Statistics, 49(1):393–410, 2021.
  * [49] P. Massart.  About the constants in talagrand’s concentration inequalities for empirical processes.  The Annals of Probability, 28(2):863–884, 2000.
  * [50] S. Mendelson.  An unrestricted learning procedure.  Journal of the ACM, 66(6):1–42, 2019.
  * [51] S. Mendelson.  Approximating ${L}_{p}$ unit balls via random sampling.  Advances in Mathematics, 386:1–20, 2021.
  * [52] S. Mendelson and G. Paouris.  On generic chaining and the smallest singular value of random matrices with heavy tails.  Journal of Functional Analysis, 262(9):3775–3811, 2012.
  * [53] S. Mendelson and G. Paouris.  On the singular values of random matrices.  Journal of the European Mathematical Society, 16(4):823–834, 2014\.
  * [54] S. Mendelson and N. Zhivotovskiy.  Robust covariance estimation under ${L}_{4}-{L}_{2}$ norm equivalence.  The Annals of Statistics, 48(3):1648–1664, 2020.
  * [55] A. Minasyan and N. Zhivotovskiy.  Statistically optimal robust mean and covariance estimation for anisotropic Gaussians.  arXiv preprint arXiv:2301.09024, 2023.
  * [56] S. Minsker and L. Wang.  Robust estimation of covariance matrices: Adversarial contamination and beyond.  arXiv preprint arXiv:2203.02880, 2022.
  * [57] J. Mourtada, T. Vaškevičius, and N. Zhivotovskiy.  Distribution-free robust linear regression.  Mathematical Statistics and Learning, 2022.
  * [58] R. I. Oliveira and Z. F. Rico.  Improved covariance estimation: optimal robustness and sub-gaussian guarantees under heavy tails.  arXiv preprint arXiv:2209.13485, 2022.
  * [59] D. M. Ostrovskii and A. Rudi.  Affine invariant covariance estimation for heavy-tailed distributions.  In Conference on Learning Theory, pages 2531–2550. PMLR, 2019.
  * [60] Z. F. Rico.  Optimal statistical estimation: sub-Gaussian properties, heavy-tailed data, and robust- ness.  PhD thesis, Instituto de Matemática Pura e Aplicada, June 2022.
  * [61] P. J. Rousseeuw and A. M. Leroy.  Robust Regression and Outlier Detection, volume 589.  John Wiley & Sons, 2005.
  * [62] N. Srivastava and R. Vershynin.  Covariance estimation for distributions with $2+\varepsilon$ moments.  The Annals of Probability, 41(5):3081–3111, 2013.
  * [63] S. M. Stigler.  The asymptotic distribution of the trimmed mean.  The Annals of Statistics, pages 472–477, 1973.
  * [64] M. Talagrand.  Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems, volume 60.  Springer Science & Business Media, 2014.
  * [65] K. Tikhomirov.  Sample covariance matrices of heavy-tailed distributions.  International Mathematics Research Notices, 2018(20):6254–6289, 2018.
  * [66] J. A. Tropp.  An Introduction to Matrix Concentration Inequalities.  Foundations and Trends in Machine Learning, 8(1-2):1–230, 2015\.
  * [67] J. W. Tukey and D. H. McLaughlin.  Less vulnerable confidence and significance procedures for location based on a single sample: Trimming/Winsorization 1.  Sankhyā: The Indian Journal of Statistics, Series A, pages 331–352, 1963.
  * [68] R. Van Handel.  Structured random matrices.  In Convexity and Concentration, pages 107–156. Springer, 2017.
  * [69] R. Vershynin.  Approximating the moments of marginals of high-dimensional distributions.  The Annals of Probability, 39(4):1591–1606, 2011.
  * [70] R. Vershynin.  How close is the sample covariance matrix to the actual covariance matrix?  Journal of Theoretical Probability, 25(3):655–686, 2012.
  * [71] R. Vershynin.  Introduction to the non-asymptotic analysis of random matrices, page 210–268.  Cambridge University Press, 2012.
  * [72] R. Vershynin.  High-Dimensional Probability: An Introduction with Applications, volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, 2016.
  * [73] N. Zhivotovskiy.  Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle.  arXiv preprint arXiv:2108.08198, 2021.