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 $\mathbf{X} = \{X_i\}_{i = 1}^n$ from a distribution $\mathcal{D}$
over $\mathbb{R}^d$ with mean $\mu$ which satisfies the following
\emph{weak-moment} assumption for some ${\alpha \in [0, 1]}$: \begin{equation*}
\forall \|v\| = 1: \mathbb{E}_{X \thicksim \mathcal{D}}[\lvert \langle X - \mu,
v\rangle \rvert^{1 + \alpha}] \leq 1, \end{equation*} and given a target
failure probability, $\delta$, our goal is to design an estimator which attains
the smallest possible confidence interval as a function of $n,d,\delta$. For
the specific case of $\alpha = 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 $\alpha$, and establish the
following information-theoretic lower bound on the optimal attainable
confidence interval: \begin{equation*} \Omega \left(\sqrt{\frac{d}{n}} +
\left(\frac{d}{n}\right)^{\frac{\alpha}{(1 + \alpha)}} + \left(\frac{\log 1 /
\delta}{n}\right)^{\frac{\alpha}{(1 + \alpha)}}\right). \end{equation*}
Moreover, we devise a computationally-efficient estimator which achieves this
lower bound.
