Scalable Training of Mixture Models via Coresets

Feldman, Dan, Faulkner, Matthew, Krause, Andreas

Neural Information Processing Systems 

How can we train a statistical mixture model on a massive data set? In this paper, we show how to construct coresets for mixtures of Gaussians and natural generalizations. A coreset is a weighted subset of the data, which guarantees that models fitting the coreset will also provide a good fit for the original data set. We show that, perhaps surprisingly, Gaussian mixtures admit coresets of size independent of the size of the data set. More precisely, we prove that a weighted set of $O(dk 3/\eps 2)$ data points suffices for computing a $(1 \eps)$-approximation for the optimal model on the original $n$ data points.