Tight Bounds for Learning a Mixture of Two Gaussians
Tight Bounds for Learning a Mixture of Two Gaussians
复制标题
学习两个高斯混合的严格界限
DOI：
10.1145/2746539.2746579
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Eric Price
中科院分区：
文献类型：
--
作者：
Moritz Hardt;Eric Price
我们考虑从一系列独立的随机样品中识别两个任意D维高斯的未知混合物的参数的问题。解决Pearson（1894）引入的问题。估计每个参数在d = 1时，我们的上限延伸到任意尺寸d> 1，直到使用新颖的 - - 但简单的---尺寸降低技术进一步确定样品复杂性明显小于我们的最佳最差案例结合的一些有趣的特殊情况。 o（σ2），这再次是最佳的。我们的结果也适用于混合物的每个组成部分，在总变化距离上，我们的算法对先前工作的样本复杂性有了很大的改善。
We consider the problem of identifying the parameters of an unknown mixture of two arbitrary d-dimensional gaussians from a sequence of independent random samples. Our main results are upper and lower bounds giving a computationally efficient moment-based estimator with an optimal convergence rate, thus resolving a problem introduced by Pearson (1894). Denoting by σ2 the variance of the unknown mixture, we prove that Θ(σ12) samples are necessary and sufficient to estimate each parameter up to constant additive error when d=1. Our upper bound extends to arbitrary dimension d>1 up to a (provably necessary) logarithmic loss in d using a novel---yet simple---dimensionality reduction technique. We further identify several interesting special cases where the sample complexity is notably smaller than our optimal worst-case bound. For instance, if the means of the two components are separated by Ω(σ) the sample complexity reduces to O(σ2) and this is again optimal. Our results also apply to learning each component of the mixture up to small error in total variation distance, where our algorithm gives strong improvements in sample complexity over previous work.