Fast Mean Estimation with Sub-Gaussian Rates

Yeshwanth Cherapanamjeri, Nicolas Flammarion, Peter L. Bartlett
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:786-806, 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 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-cherapanamjeri19b, title = {Fast Mean Estimation with Sub-Gaussian Rates}, author = {Cherapanamjeri, Yeshwanth and Flammarion, Nicolas and Bartlett, Peter L.}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {786--806}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/cherapanamjeri19b/cherapanamjeri19b.pdf}, url = {https://proceedings.mlr.press/v99/cherapanamjeri19b.html}, 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 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.} }
Endnote
%0 Conference Paper %T Fast Mean Estimation with Sub-Gaussian Rates %A Yeshwanth Cherapanamjeri %A Nicolas Flammarion %A Peter L. Bartlett %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-cherapanamjeri19b %I PMLR %P 786--806 %U https://proceedings.mlr.press/v99/cherapanamjeri19b.html %V 99 %X 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 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.
APA
Cherapanamjeri, Y., Flammarion, N. & Bartlett, P.L.. (2019). Fast Mean Estimation with Sub-Gaussian Rates. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:786-806 Available from https://proceedings.mlr.press/v99/cherapanamjeri19b.html.

Related Material