Statistically optimal robust mean and covariance estimation for anisotropic Gaussians

Abstract

Assume that $X_1,\dots ,X_N$ is an $\epsilon$-contaminated sample of $N$ independent Gaussian vectors in ${\mathbb{R}}^d$ with mean $\mu$ and covariance $\Sigma$. In the strong $\epsilon$-contamination model, we assume that the adversary replaced an $\epsilon$ fraction of the vectors in the original Gaussian sample with arbitrary vectors. We show that there is an estimator $\hat{\mu }$ of the mean satisfying, with probability at least $1-\delta$, a bound of the form

where $c>0$ is an absolute constant and $\Vert \Sigma \Vert$ denotes the operator norm of $\Sigma$. In the same contaminated Gaussian setup, we construct an estimator $\hat{\Sigma }$ of the covariance matrix $\Sigma$ that satisfies, with probability at least $1-\delta$,

Both results are optimal up to multiplicative constant factors. Several previously known results were either dimension-dependent and required $\Sigma$ to be close to identity or had a sub-optimal dependence on the contamination level $\epsilon$. As a part of the analysis, we derive sharp concentration inequalities for central order statistics of Gaussian, folded normal, and chi-squared distributions.