  We consider the problem of robust mean and location estimation w.r.t. any
pseudo-norm of the form $x\in\mathbb{R}^d\to ||x||_S = \sup_{v\in S}<v,x>$
where $S$ is any symmetric subset of $\mathbb{R}^d$. We show that the
deviation-optimal minimax subgaussian rate for confidence $1-\delta$ is $$
  \max\left(\frac{l^*(\Sigma^{1/2}S)}{\sqrt{N}}, \sup_{v\in
S}||\Sigma^{1/2}v||_2\sqrt{\frac{\log(1/\delta)}{N}}\right) $$where
$l^*(\Sigma^{1/2}S)$ is the Gaussian mean width of $\Sigma^{1/2}S$ and $\Sigma$
the covariance of the data (in the benchmark i.i.d. Gaussian case). This
improves the entropic minimax lower bound from [Lugosi and Mendelson, 2019] and
closes the gap characterized by Sudakov's inequality between the entropy and
the Gaussian mean width for this problem. This shows that the right statistical
complexity measure for the mean estimation problem is the Gaussian mean width.
We also show that this rate can be achieved by a solution to a convex
optimization problem in the adversarial and $L_2$ heavy-tailed setup by
considering minimum of some Fenchel-Legendre transforms constructed using the
Median-of-means principle. We finally show that this rate may also be achieved
in situations where there is not even a first moment but a location parameter
exists.
