Covariance estimation: Optimal dimension-free guarantees for adversarial corruption and heavy tails

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\ge 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$.