Near-optimal mean estimators with respect to general norms

We study the problem of estimating the mean of a random vector in ${\mathbb{R}}^d$ based on an i.i.d.\ sample, when the accuracy of the estimator is measured by a general norm on ${\mathbb{R}}^d$. We construct an estimator (that depends on the norm) that achieves an essentially optimal accuracy/confidence tradeoff under the only assumption that the random vector has a well-defined covariance matrix. The estimator is based on the construction of a uniform median-of-means estimator in a class of real valued functions that may be of independent interest.