Fast Mean Estimation with Sub-Gaussian Rates

Yeshwanth Cherapanamjeri, Nicolas Flammarion, Peter L. Bartlett

We propose an estimator for the mean of a random vector in ${\mathbb{R}}^d$ that can be computed in time $O(n^4+n^{2}d)$ for $n$ i.i.d.~samples and that has error bounds matching the s…