# Introduction to Core-sets: an Updated Survey

arXiv: https://arxiv.org/abs/2011.09384 · HTML: https://mlsanity.com/paper/2011.09384/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2020.

## Built on by (most cited first, 30 of 45)

- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Dataset Distillation: A Comprehensive Review](https://mlsanity.com/paper/2301.07014/) (2023)
- [Improved Distribution Matching for Dataset Condensation](https://mlsanity.com/paper/2307.09742/) (2023)
- [Learning Dynamics of LLM Finetuning](https://mlsanity.com/paper/2407.10490/) (2024)
- [Anchor Points: Benchmarking Models with Much Fewer Examples](https://mlsanity.com/paper/2309.08638/) (2023)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [MIM4DD: Mutual Information Maximization for Dataset Distillation](https://mlsanity.com/paper/2312.16627/) (2023)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Does Training with Synthetic Data Truly Protect Privacy?](https://mlsanity.com/paper/2502.12976/) (2025)
- [ℓ_∞-Robustness and Beyond: Unleashing Efficient Adversarial Training](https://mlsanity.com/paper/2112.00378/) (2021)
- [Adversarial Coreset Selection for Efficient Robust Training](https://mlsanity.com/paper/2209.05785/) (2022)
- [From Benchmarks to Skills: Low-Rank Factors for LLM Evaluation](https://mlsanity.com/paper/2507.20208/) (2025)
- [Data Summarization via Bilevel Optimization](https://mlsanity.com/paper/2109.12534/) (2021)
- [Coresets for Time Series Clustering](https://mlsanity.com/paper/2110.15263/) (2021)
- [Visual DNA: Representing and Comparing Images using Distributions of Neuron Activations](https://mlsanity.com/paper/2304.10036/) (2023)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [Unknown Domain Inconsistency Minimization for Domain Generalization](https://mlsanity.com/paper/2403.07329/) (2024)
- [Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems](https://mlsanity.com/paper/2107.00068/) (2021)
- [Data-Efficient Training of CNNs and Transformers with Coresets: A Stability Perspective](https://mlsanity.com/paper/2303.02095/) (2023)
- [Machine Learning and the Future of Bayesian Computation](https://mlsanity.com/paper/2304.11251/) (2023)
- [Coreset selection can accelerate quantum machine learning models with provable generalization](https://mlsanity.com/paper/2309.10441/) (2023)
- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [Decomposed Distribution Matching in Dataset Condensation](https://mlsanity.com/paper/2412.04748/) (2024)
- [Data Selection for ERMs](https://mlsanity.com/paper/2504.14572/) (2025)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [General bounds on the quality of Bayesian coresets](https://mlsanity.com/paper/2405.11780/) (2024)
- [One-pass additive-error subset selection for ℓp subspace approximation](https://mlsanity.com/paper/2204.12073/) (2022)
- [Using Low-Discrepancy Points for Data Compression in Machine Learning: An Experimental Comparison](https://mlsanity.com/paper/2407.07450/) (2024)

## Abstract (arXiv)

In optimization or machine learning problems we are given a set of items, usually points in some metric space, and the goal is to minimize or maximize an objective function over some space of candidate solutions. For example, in clustering problems, the input is a set of points in some metric space, and a common goal is to compute a set of centers in some other space (points, lines) that will minimize the sum of distances to these points. In database queries, we may need to compute such a some for a specific query set of k centers. However, traditional algorithms cannot handle modern systems that require parallel real-time computations of infinite distributed streams from sensors such as GPS, audio or video that arrive to a cloud, or networks of weaker devices such as smartphones or robots. Core-set is a "small data" summarization of the input "big data", where every possible query has approximately the same answer on both data sets. Generic techniques enable efficient coreset changedmaintenance of streaming, distributed and dynamic data. Traditional algorithms can then be applied on these coresets to maintain the approximated optimal solutions. The challenge is to design coresets with provable tradeoff between their size and approximation error. This survey summarizes such constructions in a retrospective way, that aims to unified and simplify the state-of-the-art.