Practical Coreset Constructions for Machine Learning

By Olivier Bachem, Mario Lucic, Andreas Krause. 2017

204 citations recorded by the source corpus.

We investigate coresets - succinct, small summaries of large data sets - so that solutions found on the summary are provably competitive with solution found on the full data set. We provide an overview over the state-of-the-art in coreset construction for machine learning. In Section 2, we present both the intuition behind and a theoretically sound framework to construct coresets for general problems and apply it to $k$-means clustering. In Section 3 we summarize existing coreset construction algorithms for a variety of machine learning problems such as maximum likelihood estimation of mixture models, Bayesian non-parametric models, principal component analysis, regression and general empirical risk minimization.

How researchers see this paper

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

Citations in the corpus

Dataset Distillation (2018, background): “Similarly, core-set construction (Tsang et al., 2005; Har-Peled & Kushal, 2007; Bachem et al., 2017; Sener & Savarese, 2018) and instance selection (Olvera-López et al., 2010) methods aim to select a subset of the entire training data, such that models trained on the subset will perform as well as…”
Distilled One-Shot Federated Learning (2020, methodology): “These methods include dataset pruning [1] and core set construction [2, 31, 27], which keep the examples that are measured to be more useful for training and remove the rest.”
Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds (2018, methodology): “[6] Olivier Bachem, Mario Lucic, and Andreas Krause.”
Soft-Label Dataset Distillation and Text Dataset Distillation (2019, methodology): “Several methods aim to ‘prune’ a dataset, or create a ‘coreset’, by leaving in only examples that are determined to be useful (Angelova et al., 2005; Bachem et al., 2017; Sener and Savarese, 2017; Tsang et al., 2005).”
Training Mixture Models at Scale via Coresets (2017, methodology): “For a survey of the recent results we refer the reader to Bachem et al. (2017b).”
Budgeted Training: Rethinking Deep Neural Network Training Under Resource Constraints (2019, background): “Given a limited budget, one obvious strategy might be data subsampling [1, 55, 66].”
Manipulating SGD with Data Ordering Attacks (2021, background): “We consider four reordering policies, motivated by research in the fields of curriculum learning [5] and core-set selection [2], which discovered that model training can be enhanced by scheduling how and what data is presented to the model.”
Training Gaussian Mixture Models at Scale via Coresets (2017, methodology): “Given the pseudo-dimension dim F and some upper bound on the total sensitivity S we may bound the coreset size by using the following theorem from Bachem et al. (2017b).”
Teacher Improves Learning by Selecting a Training Subset (2018, background): “The second thread is coresets [22, 6], a summary of S such that models learned on the summary are provably competitive with models learned on the full data set S.”
Dataset Distillation by Matching Training Trajectories (2022, methodology): “Similar to dataset distillation, coreset [1, 4, 13, 34, 41] and instance selection [28] aim to select a subset of the entire training dataset, where training on this small subset achieves good performance.”
Flexible Dataset Distillation: Learn Labels Instead of Images (2020, background): “In this sense it is related to other endeavours such as dataset pruning [2, 10, 16], core-set construction [29, 3, 26] and instance selection [22] that focuses on dataset summarization through a small number of examples.”
Sparse Variational Inference: Bayesian Coresets from Scratch (2019, methodology): “of data known as a Bayesian coreset [30], a concept originating from the computational geometry and optimization literature [52–57].”
Provable Filter Pruning for Efficient Neural Networks (2019, background): “This stands in contrast with the sensitivity framework used in state-of-the-art coresets constructions (Braverman et al., 2016; Bachem et al., 2017), where the sensitivity is deﬁned to be with respect to the supremum over all x ∈ supp( D ) in (1) instead of a maximum over x ∈ S .”
Distribution Density, Tails, and Outliers in Machine Learning: Metrics and Applications (2019, background): “Prototypes of a given task share some intuition with the notion of coresets (Agarwal et al., 2005; Huggins et al., 2016; Bachem et al., 2017; Tolochinsky & Feldman, 2018) because both prototypes and coresets describe the dataset in a more compact way—by returning a (potentially weighted) subset of t”