Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes

Hassan Ashtiani, Shai Ben-David, Nick Harvey +3

We prove that $\tilde{\Theta }(k{d}^2/{\epsilon }^2)$ samples are necessary and sufficient for learning a mixture of $k$ Gaussians in ${\mathbb{R}}^d$, up to error $\epsilon$ in total va…