# Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 May 2024.

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

- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Coresets for Clustering Under Stochastic Noise](https://mlsanity.com/paper/2510.23438/) (2025)
- [Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling](https://mlsanity.com/paper/2609.06394/) (2026)

## Abstract (arXiv)

Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as k-means. Given a point set P, a coreset Omega is a small, weighted summary that preserves the cost of all candidate solutions S up to a (1± varepsilon) factor. For k-means in d-dimensional Euclidean space the cost for solution S is sump∈ Pmins∈ S|p-s|2. A very popular method for coreset construction, both in theory and practice, is Sensitivity Sampling, where points are sampled in proportion to their importance. We show that Sensitivity Sampling yields optimal coresets of size tildeO(k/varepsilon2min(√k,varepsilon-2)) for worst-case instances. Uniquely among all known coreset algorithms, for well-clusterable data sets with Omega(1) cost stability, Sensitivity Sampling gives coresets of size tildeO(k/varepsilon2), improving over the worst-case lower bound. Notably, Sensitivity Sampling does not have to know the cost stability in order to exploit it: It is appropriately sensitive to the clusterability of the data set while being oblivious to it. We also show that any coreset for stable instances consisting of only input points must have size Omega(k/varepsilon2). Our results for Sensitivity Sampling also extend to the k-median problem, and more general metric spaces.