# Introduction to Coresets: Accurate Coresets

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2019.

## Built on by (most cited first, 17 of 17)

- [Efficient Dataset Distillation Using Random Feature Approximation](https://mlsanity.com/paper/2210.12067/) (2022)
- [On the Diversity and Realism of Distilled Dataset: An Efficient Dataset Distillation Paradigm](https://mlsanity.com/paper/2312.03526/) (2023)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [How to Select Datapoints for Efficient Human Evaluation of NLG Models?](https://mlsanity.com/paper/2501.18251/) (2025)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [Coresets for Data Discretization and Sine Wave Fitting](https://mlsanity.com/paper/2203.03009/) (2022)
- [Obstacle Aware Sampling for Path Planning](https://mlsanity.com/paper/2203.04075/) (2022)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [Embarassingly Simple Dataset Distillation](https://mlsanity.com/paper/2311.07025/) (2023)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [On the Size and Approximation Error of Distilled Sets](https://mlsanity.com/paper/2305.14113/) (2023)
- [Distilling Datasets Into Less Than One Image](https://mlsanity.com/paper/2403.12040/) (2024)
- [AutoAdapt: An Automated Domain Adaptation Framework for LLMs](https://mlsanity.com/paper/2603.08181/) (2026)
- [ARIA: Adaptive Region-Based Importance Allocation for Conditional Diffusion Distillation](https://mlsanity.com/paper/2606.23898/) (2026)
- [D-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition](https://mlsanity.com/paper/2610.10636/) (2026)

## Abstract (arXiv)

A coreset (or core-set) of an input set is its small summation, such that solving a problem on the coreset as its input, provably yields the same result as solving the same problem on the original (full) set, for a given family of problems (models, classifiers, loss functions). Over the past decade, coreset construction algorithms have been suggested for many fundamental problems in e.g. machine/deep learning, computer vision, graphics, databases, and theoretical computer science. This introductory paper was written following requests from (usually non-expert, but also colleagues) regarding the many inconsistent coreset definitions, lack of available source code, the required deep theoretical background from different fields, and the dense papers that make it hard for beginners to apply coresets and develop new ones. The paper provides folklore, classic and simple results including step-by-step proofs and figures, for the simplest (accurate) coresets of very basic problems, such as: sum of vectors, minimum enclosing ball, SVD/ PCA and linear regression. Nevertheless, we did not find most of their constructions in the literature. Moreover, we expect that putting them together in a retrospective context would help the reader to grasp modern results that usually extend and generalize these fundamental observations. Experts might appreciate the unified notation and comparison table that links between existing results. Open source code with example scripts are provided for all the presented algorithms, to demonstrate their practical usage, and to support the readers who are more familiar with programming than math.