Information theoretic limits of robust sub-Gaussian mean estimation under star-shaped constraints

Abstract

We obtain the minimax rate for a mean location model with a bounded star-shaped set $K\subseteq {\mathbb{R}}^n$ constraint on the mean, in an adversarially corrupted data setting with Gaussian noise. We assume an unknown fraction $\hat{I}\mu \le 1/2-\hat{I}º$ for some fixed $\hat{I}º\in (0,1/2]$ of $N$ observations are arbitrarily corrupted. We obtain a minimax risk up to proportionality constants under the squared ${\ell }_2$ loss of $\max (\hat{I}{\cdot }^{\ast 2},\ddot{I}{ƒ}^2\hat{I}{\mu }^2)\wedge d^2$ with \begin{align*} η^* = \sup \bigg\{η\ge 0 : \frac{Nη^2}{σ^2} \leq \log \mathcal{M}_K^{\operatorname{loc}}(η,c)\bigg\}, \end{align*} where $\log {\mathcal{M}}_K^{\mathrm{loc}}(\hat{I}\cdot ,c)$ denotes the local entropy of the set $K$, $d$ is the diameter of $K$, $\ddot{I}{ƒ}^2$ is the variance, and $c$ is some sufficiently large absolute constant. A variant of our algorithm achieves the same rate for settings with known or symmetric sub-Gaussian noise, with a smaller breakdown point, still of constant order. We further study the case of unknown sub-Gaussian noise and show that the rate is slightly slower: $\max (\hat{I}{\cdot }^{\ast 2},\ddot{I}{ƒ}^2\hat{I}{\mu }^2\log (1/\hat{I}\mu ))\wedge d^2$. We generalize our results to the case when $K$ is star-shaped but unbounded.