Uniform sampling can efficiently summarize k-means data sets
Coresets for $k$-Means: When Does Uniform Sampling Suffice?
Data Structures and AlgorithmsComputational Geometry
Summary
Clustering large sets of data into groups (called k-means) can be slow if the data is huge. The paper studies how simply picking random samples uniformly from the data can still give a good summary, called a coreset, which speeds up the process. The authors find exact conditions when uniform sampling works well, especially for one cluster and certain structured data. Their approach works without depending on the size or complexity of the data, making it simpler and more efficient than earlier methods.
What this means in practice
- •For machine learning engineers: Use uniform sampling to build small summaries for large clustering tasks on stable data, reducing computation without losing quality.
- •For data infrastructure teams: Implement efficient data reduction pipelines for clustering by applying uniform sample coresets that do not depend on data dimension or size.
A theory result. No direct application yet.
Authors
Amir Carmel, Robert Krauthgamer
Abstract
Data summarization techniques, such as coresets, are essential for scaling clustering algorithms to massive datasets. We study uniform sampling, which is an extremely simple and ultra-efficient method to construct coresets, in the context of weak, stable, and strong coresets for the $k$-means problem in Hilbert space. We begin with the fundamental case $k=1$, and establish matching upper and lower bounds on the sample complexity of stable and weak coresets, finding that the two notions require different sample complexities. As a consequence, we obtain tight bounds for stable $1$-median coresets in $\ell_1$ and $\ell_2$ (and thus also Kendall--tau and Jaccard metrics), removing the dimension dependence of Carmel and Krauthgamer (ICLR 2026). Our analysis is substantially simpler than prior work and reduces to bounding the deviation of the sample mean. For the general $k$-means problem on $ρ$-separated instances, a well-studied structural assumption on the input, we show that uniform sampling yields a stable coreset for all $O(1)$-approximate solutions, and a strong coreset if the instance additionally has bounded kurtosis. In all these results, the sample complexity is independent of the dimension and the instance size.