Polynomial-time minimax robust mean estimation under star-shaped constraints

Fix integers $n,N \ge 1$, a contamination level $\epsilon \in [0,1/2)$, a scale parameter $\sigma>0$, and a star-shaped set $K\subseteq\mathbb{R}^n$ (that is, there exists $k^\star\in K$ such that $k^\star+t(x-k^\star)\in K$ for every $x\in K$ and $t\in[0,1]$). Let

For $\delta>0$ and $A\subseteq\mathbb{R}^n$, let $\mathcal{M}(\delta,A)$ be the maximal cardinality of a $\delta$-packing of $A$ in Euclidean norm (pairwise distances $>\delta$). For an absolute constant $c>0$, define the local entropy

and define

This setup follows Prasadan & Neykov (2024).

Data model: there are unobserved clean samples $\widetilde X_i=\mu+\xi_i$, $i=1,\dots,N$, with unknown $\mu\in K$. An adversary, after seeing all clean samples and the estimation procedure, outputs observed samples $X_1,\dots,X_N$ by changing at most $\epsilon N$ coordinates arbitrarily. Denote by $\mathfrak C_\epsilon$ the class of all such contamination mechanisms. The estimator $\widehat\mu$ is any measurable function of $(X_1,\dots,X_N)$.

Noise regimes:

1. Gaussian: $\xi_i\stackrel{iid}{\sim}N(0,\sigma^2 I_n)$.

2. Known-or-sign-symmetric sub-Gaussian: $\xi_i$ are iid mean-zero sub-Gaussian vectors with parameter at most $\sigma$, and either the full noise law is known or $\xi_i\stackrel{d}{=}-\xi_i$.