Learning GMMs with Nearly Optimal Robustness Guarantees

Gaussian mixture models have a long and storied history. They were first introduced in a groundbreaking work of Karl Pearson[33] in 1894 and have found wide-ranging applications ever since, as a natural model for data believed to be coming from two or more heterogeneous sources. Early works focused on the statistical complexity [35], namely bounding the number of samples needed to estimate the Gaussian mixture model to within some desired accuracy. More recently, these problems have been revisited with the emphasis being on giving computationally efficient algorithms that work in high dimensions and with minimal assumptions [8,11,21,25,32]. There are different types of learning goals we could ask for, and the distinctions between them will play an important role in understanding the context of our work: (1) In parameter learning, we want to estimate the mixture on a component-by-component basis. We ask that there is a matching between the components in our hypothesis and those of the true mixture so that across the matching we are close in total variation distance. Alternatively we could ask to be close in an appropriate parameter distance instead.