# Introduction to Coresets: Approximated Mean

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 53 references that are in the map.
- First posted on arXiv 4 Nov 2021.

## Builds on (most cited first, 19 of 19)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Sets Clustering](https://mlsanity.com/paper/2003.04135/) (2020)
- [Determinantal Point Processes for Coresets](https://mlsanity.com/paper/1803.08700/) (2018)
- [Introduction to Coresets: Accurate Coresets](https://mlsanity.com/paper/1910.08707/) (2019)
- [One-Shot Coresets: The Case of k-Clustering](https://mlsanity.com/paper/1711.09649/) (2017)
- [Strong Coresets for Hard and Soft Bregman Clustering with Applications to Exponential Family Mixtures](https://mlsanity.com/paper/1508.05243/) (2015)
- [Tight Sensitivity Bounds For Smaller Coresets](https://mlsanity.com/paper/1907.01433/) (2019)
- [Coresets for Regressions with Panel Data](https://mlsanity.com/paper/2011.00981/) (2020)
- [Dimensionality Reduction of Massive Sparse Datasets Using Coresets](https://mlsanity.com/paper/1503.01663/) (2015)
- [Faster PAC Learning and Smaller Coresets via Smoothed Analysis](https://mlsanity.com/paper/2006.05441/) (2020)

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

- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [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)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [Compress to Impress: Efficient LLM Adaptation Using a Single Gradient Step on 100 Samples](https://mlsanity.com/paper/2510.20800/) (2025)

## Abstract (arXiv)

A strong coreset for the mean queries of a set P in ℝd is a small weighted subset Csubseteq P, which provably approximates its sum of squared distances to any center (point) x∈ ℝd. A weak coreset is (also) a small weighted subset C of P, whose mean approximates the mean of P. While computing the mean of P can be easily computed in linear time, its coreset can be used to solve harder constrained version, and is in the heart of generalizations such as coresets for k-means clustering. In this paper, we survey most of the mean coreset construction techniques, and suggest a unified analysis methodology for providing and explaining classical and modern results including step-by-step proofs. In particular, we collected folklore and scattered related results, some of which are not formally stated elsewhere. Throughout this survey, we present, explain, and prove a set of techniques, reductions, and algorithms very widespread and crucial in this field. However, when put to use in the (relatively simple) mean problem, such techniques are much simpler to grasp. The survey may help guide new researchers unfamiliar with the field, and introduce them to the very basic foundations of coresets, through a simple, yet fundamental, problem. Experts in this area might appreciate the unified analysis flow, and the comparison table for existing results. Finally, to encourage and help practitioners and software engineers, we provide full open source code for all presented algorithms.