Statistical Guarantees for Covariance Estimation with Adversarial Corruption under Constraints

Abstract

We obtain a near-minimax rate on covariance estimation of adversarially corrupted Gaussian data in Frobenius norm when the covariance estimation is assumed to lie in a star-shaped set $K\subseteq {\mathbb{R}}^{n\times n}$. Assuming a known upper bound of $\epsilon <1/32$ on the fraction of the $N$ observations of data $X$ are arbitrarily corrupted by an omniscient adversary, we obtain the near-minimax rate (up to constants) of \begin{align*} \left(\varepsilon^2 \vee δ^{\star2} \right)\wedge d^2 \lesssim \inf_{\hatΣ} \sup_{Σ\in K} \sup_{\mathrm{C}} \mathbb{E} \| \hatΣ(\mathrm{C}(X)) - Σ\|_F^2 \lesssim \left(\varepsilon^2\log^2(1/\varepsilon) \vee δ^{\star2} \right)\wedge d^2 \end{align*} where $d$ is the diameter of the set $K$, $N\gtrsim {\sup }_{\delta >0}\log {\mathrm{M}}^{\mathrm{loc}}(\delta ,2c)$, and \begin{align*} δ^*=\sup\left\{ δ\geq 0: \frac{N}{Υ^2} δ^2\leq \log \mathrm{M}_K^{\operatorname{loc}}(δ,c) \right\} \end{align*} for an arbitrary large constant $c$ and the local metric entropy of $K$, ${\mathrm{M}}_K^{\mathrm{loc}}(\delta ,c)$. We believe this is the first such general result on structured robust covariance estimation in the Frobenius norm.

50 pages