# The Power of Uniform Sampling for Coresets

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2022.

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

- [Refined Coreset Selection: Towards Minimal Coreset Size under Model Performance Constraints](https://mlsanity.com/paper/2311.08675/) (2023)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Simple Weak Coresets for Non-Decomposable Classification Measures](https://mlsanity.com/paper/2312.09885/) (2023)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems](https://mlsanity.com/paper/2411.01115/) (2024)
- [Improving Model Classification by Optimizing the Training Dataset](https://mlsanity.com/paper/2507.16729/) (2025)
- [Structure-Aware Spectral Sparsification via Uniform Edge Sampling](https://mlsanity.com/paper/2510.12669/) (2025)
- [Improved Coresets for Euclidean k-Means](https://mlsanity.com/paper/2211.08184/) (2022)
- [Universal Weak Coreset](https://mlsanity.com/paper/2305.16890/) (2023)
- [Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization](https://mlsanity.com/paper/2410.17945/) (2024)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)
- [Text-attributed Graph Condensation via Text Selection and Attribute Matching](https://mlsanity.com/paper/2606.03839/) (2026)
- [EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset](https://mlsanity.com/paper/2608.16101/) (2026)
- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

Motivated by practical generalizations of the classic k-median and k-means objectives, such as clustering with size constraints, fair clustering, and Wasserstein barycenter, we introduce a meta-theorem for designing coresets for constrained-clustering problems. The meta-theorem reduces the task of coreset construction to one on a bounded number of ring instances with a much-relaxed additive error. This reduction enables us to construct coresets using uniform sampling, in contrast to the widely-used importance sampling, and consequently we can easily handle constrained objectives. Notably and perhaps surprisingly, this simpler sampling scheme can yield coresets whose size is independent of n, the number of input points. Our technique yields smaller coresets, and sometimes the first coresets, for a large number of constrained clustering problems, including capacitated clustering, fair clustering, Euclidean Wasserstein barycenter, clustering in minor-excluded graph, and polygon clustering under Fr'echet and Hausdorff distance. Finally, our technique yields also smaller coresets for 1-median in low-dimensional Euclidean spaces, specifically of size tildeO(varepsilon-1.5) in ℝ2 and tildeO(varepsilon-1.6) in ℝ3.