Statistical Guarantees for Covariance Estimation with Adversarial Corruption under Constraints

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\mathrm{/}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.