Robust Learning of Mixtures of Gaussians
This resolves a major outstanding problem in robust statistics, providing a foundational advance for handling corrupted data in Gaussian mixture models.
The paper tackles the problem of learning a mixture of two arbitrary Gaussians from samples that have been adversarially corrupted, and it presents a polynomial-time algorithm that achieves error polynomial in the corruption fraction in total variation distance.
We resolve one of the major outstanding problems in robust statistics. In particular, if $X$ is an evenly weighted mixture of two arbitrary $d$-dimensional Gaussians, we devise a polynomial time algorithm that given access to samples from $X$ an $\eps$-fraction of which have been adversarially corrupted, learns $X$ to error $\poly(\eps)$ in total variation distance.