Fast Mean Estimation with Sub-Gaussian Rates

arXiv1902.01998MaRDI QIDQ6313661

Author name not available (Why is that?)

Publication date: 5 February 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^4+n^{2}d)$ for $n$ i.i.d.~samples and that has error bounds matching the sub-Gaussian 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 higher-order moments. Like the polynomial time estimator introduced by Hopkins, 2018, which is based on the sum-of-squares hierarchy, our estimator achieves optimal statistical efficiency in this challenging setting, but it has a significantly faster runtime and a simpler analysis.

Has companion code repository: https://github.com/karimtito/Median_SDP

This page was built for publication: Fast Mean Estimation with Sub-Gaussian Rates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6313661)