Efficiently Learning Mixtures of Two Gaussians

We consider the basic problem of learning the parameters of a mixture of two arbitrary mutlivariate Gaussians. Under provably minimal assumptions (namely that the mixing weights are bounded from 0 and the statistical distance between the two Gaussians is bounded from 0), we give a polynomial-time algorithm for extimating the mixture parameters that converges at an inverse polynomial rate. Previously, efficient algorithms were known for the special case where the Gaussians had little overlap, namely there statistical distance was close to 1.