Phase Transitions in Heavy-Tailed Mean Estimation under $\ell_p$ Norms

We study the problem of estimating the mean of a random vector in $\mathbb R^d$ under $\ell_p$ norm, assuming only the existence of a covariance matrix. In the Euclidean norm, the sample mean is already optimal in expectation, and robust estimators are usually needed only to obtain high probability tails. Our results show that this picture changes for $\ell_p$ norms with $p>2$: robustification is necessary already for the expected risk. We prove that the minimax risk exhibits a sharp phase transition, controlled by the interaction between the sample size $n$, the dimension $d$, and the norm parameter $p$. In the large sample regime, the classical Gaussian rate remains achievable. In the complementary regime, heavy tailed distributions create a genuinely non-Gaussian obstruction. The optimal estimator is surprisingly simple: a coordinate-wise median of means whose number of blocks is chosen according to the geometry of the norm, rather than according to a confidence parameter. We also show that natural projection based median of means estimators for general norms, despite achieving the optimal confidence tradeoff relative to the sample mean benchmark of Lugosi and Mendelson (Probab. Theory Relat. Fields, 2019), can be polynomially suboptimal for $\ell_p$ norms even in the constant probability regime.