Noisy k-means++ is Not too Noisy
2026-08-03 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a version of the $k$-means++ clustering algorithm where the sampling probabilities are slightly noisy, meaning they can be off by a small factor. Previous work showed this noise made the algorithm's performance guarantee worse than in the perfect case, or led to very large constant factors. The authors prove that the approximation guarantee degrades smoothly with noise, almost matching the original bound with a small extra factor depending on the noise level. They also show this smooth dependence on noise is necessary and that a weaker type of noise control fails to guarantee good clustering. This clarifies how sensitive $k$-means++ is to small errors in sampling.
$k$-means$k$-means++approximation guaranteeD²-samplingnoisy samplingmultiplicative errorclustering algorithmstotal variation distanceadversarial noise
Authors
Poojan Shah
Abstract
The celebrated $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) achieves an $O(\log k)$ expected approximation for the classical $k$-means problem using $D^2$-sampling, a technique now ubiquitous in clustering algorithm design. Bhattacharya et al. (ESA 2020) introduced $\varepsilon$-noisy $k$-means++, where sampling probabilities may incur an adversarial multiplicative error of $(1\pm\varepsilon)$, but obtained only an $O(\log^2 k)$ guarantee. Grunau et al. (ESA 2023) recovered the asymptotic $O(\log k)$ guarantee, but their analysis loses a constant factor of roughly $147{,}638$ even as $\varepsilon\to0$, leaving open whether $k$-means++ is highly sensitive to even a small amount of noise. They asked whether a bound within $1+O(\varepsilon)$ of the classical guarantee is possible. We resolve this affirmatively, proving an expected approximation guarantee of $8(\ln k+2)\left(\frac{1+\varepsilon}{1-\varepsilon}\right)^4 = (1+O(\varepsilon))\,8(\ln k+2)$. We complement the upper bound with two separations. First, a noisy version of the Arthur and Vassilvitskii lower-bound instance incurs a $1+Ω(\varepsilon)$ loss over exact $k$-means++, so linear dependence on the noise is necessary. Second, pointwise multiplicative control is qualitatively essential: replacing it with per-round total variation closeness admits no finite approximation guarantee, even for $k=2$.