We consider the problem of identifying the parameters of an unknown mixture of two arbitrary $d$-dimensional gaussians from a sequence of random samples. Our main result is a computationally efficient moment-based estimator with an optimal convergence rate thus resolving a problem introduced by Pearson (1894). Denoting by $\sigma^2$ the variance of the unknown mixture, we prove that $\Theta(\sigma^{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 (necessary) logarithmic loss in $d$ using a novel---yet simple---dimensionality reduction technique. Strikingly, our estimator turns out to be very similar to the one Pearson proposed in 1894 which reduces the one-dimensional problem to solving and analyzing a tractable system of polynomial equations. Our result greatly improves on the exponent in the sample size of the best previous estimator due to Kalai, Moitra and Valiant (2010).

本文介绍了一种基于矩估计的计算方法，并应用新颖且简单的降维技术将上界推广到任意维数$d>1$，同时发现了一些样本复杂度较小的特殊情况，同时我们的结果也适用于在总变异距离上学习混合物的每个组件，其中我们的算法显著提高了样本复杂度。

学习两个高斯混合的紧密界限