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

Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-means. Given a point set <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex>, a coreset <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega$</tex> is a small, weighted summary that preserves the cost of all candidate solutions <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex> up to a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1\pm\varepsilon)$</tex> factor. For <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-means in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex>-dimensional Euclidean space the cost for solution <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex> is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma_{p\in P}{\min}_{s\in S}\Vert p-s\Vert ^2$</tex>. 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\widetilde{O}(k/\varepsilon^{2}\min(\sqrt{k},\varepsilon^{-2}))$</tex> for worst-case instances. Uniquely among all known coreset algorithms, for well-clusterable data sets with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(1)$</tex>, cost stability, Sensitivity Sampling gives coresets of size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\widetilde{O}(k/\varepsilon^{2})$</tex>, 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(k/\varepsilon^{2})$</tex>. Our results for Sensitivity Sampling also extend to the k-median problem, and more general metric spaces.