Optimal Mean Estimation without a Variance

We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. Concretely, given a sample X = Xii = 1n from a distribution D over ℝd with mean μ which satisfies the following weak-moment assumption for some α ∈ [0, 1]: beginequation* forall |v| = 1: mathbbEX thicksim D[lvert langle X - μ, vrangle rvert1 + α] ≤ 1, endequation* and given a target failure probability, δ, our goal is to design an estimator which attains the smallest possible confidence interval as a function of n,d,δ. For the specific case of α = 1, foundational work of Lugosi and Mendelson exhibits an estimator achieving subgaussian confidence intervals, and subsequent work has led to computationally efficient versions of this estimator. Here, we study the case of general α, and establish the following information-theoretic lower bound on the optimal attainable confidence interval: beginequation* Omega left(√fracdn + left(fracdnright)^fracα(1 + α) + left(fraclog 1 / δnright)^fracα(1 + α)right). endequation* Moreover, we devise a computationally-efficient estimator which achieves this lower bound.