Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
复制标题
DOI：
10.1137/1.9781611975031.171
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
我们研究了在存在噪声的情况下学习高维高斯参数的基本问题 - 在噪声的情况下，我们的样品的$ \ varepsilon $分数是由对手选择的。我们给出了可靠的估计器，以在总变化距离中获得估计误差$ O（\ varepsilon）$，这是最佳的，直至独立于维度的通用常数。在平均值未知的情况下，我们的鲁棒性保证最佳至$ \ sqrt {2} $，并且运行时间在$ d $中是多项式，$ 1/\ epsilon $。当平均值和协方差均未知时，运行时间在$ d $中是多项式，而quasipolynmial in $ 1/\ varepsilon $。此外，我们所有的算法都只需要多项式数量的样本。我们的工作表明，在五十年前在一维环境中建立的相同类型的错误保证也可以通过高维度的有效算法来实现。
We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise -- where an $\varepsilon$-fraction of our samples were chosen by an adversary. We give robust estimators that achieve estimation error $O(\varepsilon)$ in the total variation distance, which is optimal up to a universal constant that is independent of the dimension. In the case where just the mean is unknown, our robustness guarantee is optimal up to a factor of $\sqrt{2}$ and the running time is polynomial in $d$ and $1/\epsilon$. When both the mean and covariance are unknown, the running time is polynomial in $d$ and quasipolynomial in $1/\varepsilon$. Moreover all of our algorithms require only a polynomial number of samples. Our work shows that the same sorts of error guarantees that were established over fifty years ago in the one-dimensional setting can also be achieved by efficient algorithms in high-dimensional settings.