Fast Mean Estimation with Sub-Gaussian Rates
Fast Mean Estimation with Sub-Gaussian Rates
复制标题
亚高斯率的快速均值估计
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
P. Bartlett
中科院分区：
文献类型：
--
作者：
Yeshwanth Cherapanamjeri;Nicolas Flammarion;P. Bartlett
我们为$ \ mathbb {r}^d $中的随机向量的平均值提出了一个估计器，该估计值可以在时间$ o $ o（n^4+n^2d）$中计算出$ n $ i.i.d.〜样品，并且有错误与次高斯案件相匹配的界限。我们对数据分布做出的唯一假设是它具有有限的平均值和协方差。特别是，我们对高阶时刻没有任何假设。就像2018年霍普金斯（Hopkins）介绍的多项式时间估计器一样，基于平方的层次结构，我们的估计器在这种挑战性的环境中实现了最佳的统计效率，但是它具有更快的运行时和更简单的分析。
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^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.