Training Gaussian Mixture Models at Scale via Coresets

By Mario Lucic, Matthew Faulkner, Andreas Krause, Dan Feldman. 2017

114 citations recorded by the source corpus.

How can we train a statistical mixture model on a massive data set? In this work we show how to construct coresets for mixtures of Gaussians. A coreset is a weighted subset of the data, which guarantees that models fitting the coreset also provide a good fit for the original data set. We show that, perhaps surprisingly, Gaussian mixtures admit coresets of size polynomial in dimension and the number of mixture components, while being independent of the data set size. Hence, one can harness computationally intensive algorithms to compute a good approximation on a significantly smaller data set. More importantly, such coresets can be efficiently constructed both in distributed and streaming settings and do not impose restrictions on the data generating process. Our results rely on a novel reduction of statistical estimation to problems in computational geometry and new combinatorial complexity results for mixtures of Gaussians. Empirical evaluation on several real-world data sets suggests that our coreset-based approach enables significant reduction in training-time with negligible approximation error.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Coresets via Bilevel Optimization for Continual Learning and Streaming (2020, methodology): “, coresets for k-means [19], Gaussian mixture model [41] and logistic regression [29].”
DataComp: In search of the next generation of multimodal datasets (2023, background): “[87] Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman.”
Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes (2018, methodology): “See [17] for using core-sets in maximum likelihood estimation.”
Practical Coreset Constructions for Machine Learning (2017, background): “Based on the framework presented in Chapter 2, the sensitivity can be bounded by O(kλ−4) and the pseudo-dimension of the associated function family is O(k4d4) yielding a coreset of size Θ ( d4k6ε−2λ−8 ) [Feldman et al., 2011, Lucic et al., 2017].”
Coresets for Data-efficient Training of Machine Learning Models (2019, background): “…traditionally perform importance sampling with respect to sensitivity score, to provide high-probability solutions (Har-Peled & Mazumdar, 2004; Lucic et al., 2017; Cohen et al., 2017) for a particular problem, such as k -means and k -median clustering (Har-Peled & Mazumdar, 2004), naïve Bayes…”