Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians

Assume that X1, ldots, XN is an varepsilon-contaminated sample of N independent Gaussian vectors in ℝd with mean μ and covariance Sigma. In the strong varepsilon-contamination model we assume that the adversary replaced an varepsilon fraction of vectors in the original Gaussian sample by any other vectors. We show that there is an estimator widehat μ of the mean satisfying, with probability at least 1 - δ, a bound of the form [ |widehatμ - μ|2 ≤ cleft(√fracoperatornameTr(Sigma)N + √frac|Sigma|log(1/δ)N + varepsilon√|Sigma|right), ] where c > 0 is an absolute constant and |Sigma| denotes the operator norm of Sigma. In the same contaminated Gaussian setup, we construct an estimator widehat Sigma of the covariance matrix Sigma that satisfies, with probability at least 1 - δ, [ left|widehatSigma - Sigmaright| ≤ cleft(√frac|Sigma|operatornameTr(Sigma)N + |Sigma|√fraclog(1/δ)N + varepsilon|Sigma|right). ] Both results are optimal up to multiplicative constant factors. Despite the recent significant interest in robust statistics, achieving both dimension-free bounds in the canonical Gaussian case remained open. In fact, 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 varepsilon. As a part of the analysis, we derive sharp concentration inequalities for central order statistics of Gaussian, folded normal, and chi-squared distributions.