Fast Mean Estimation with SubGaussian Rates
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:786806, 2019.
Abstract
We propose an estimator for the mean of a random vector in $\mathbb{R}^d$ that can be computed in time $O(n^{3.5}+n^2d)$ for $n$ i.i.d. samples and that has error bounds matching the subGaussian case. The only assumptions we make about the data distribution are that it has finite mean and covariance; in particular, we make no assumptions about higherorder moments. Like the polynomial time estimator introduced by Hopkins (2018), which is based on the sumofsquares hierarchy, our estimator achieves optimal statistical efficiency in this challenging setting, but it has a significantly faster runtime and a simpler analysis.
Related Material


