Practical Coreset Constructions for Machine Learning

2017/03/19 by Bachem, Olivier, Lucic, Mario, Krause, Andreas · 4 citations
#FOS: Computer and information sciences #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1703.06476

Abstract

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.

Cited by

• Subset Sampling over Joins
• SubZeroCore: A Submodular Approach with Zero Training for Coreset Selection
• Coreset selection based on Intra-class diversity
• Constrained Centroid Clustering: A Novel Approach for Compact and Structured Partitioning

Related

• Robust Coreset Construction for Distributed Machine Learning
• Introduction to Coresets: Accurate Coresets
• A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances
• A Nearly Optimal Size Coreset Algorithm with Nearly Linear Time
• Scalable k-Means Clustering via Lightweight Coresets