# A New Rejection Sampling Approach to k-mathttmeans++ With Improved Trade-Offs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2025.

## Abstract (arXiv)

The k-mathttmeans++ seeding algorithm (Arthur & Vassilvitskii, 2007) is widely used in practice for the k-means clustering problem where the goal is to cluster a dataset X subset ℝ d into k clusters. The popularity of this algorithm is due to its simplicity and provable guarantee of being O(log k) competitive with the optimal solution in expectation. However, its running time is O(|X|kd), making it expensive for large datasets. In this work, we present a simple and effective rejection sampling based approach for speeding up k-mathttmeans++. Our first method runs in time tildeO(mathttnnz (X) + β k2d) while still being O(log k ) competitive in expectation. Here, β is a parameter which is the ratio of the variance of the dataset to the optimal k-mathttmeans cost in expectation and tildeO hides logarithmic factors in k and |X|. Our second method presents a new trade-off between computational cost and solution quality. It incurs an additional scale-invariant factor of  k-Omega( m/β) operatornameVar (X) in addition to the O(log k) guarantee of k-mathttmeans++ improving upon a result of (Bachem et al, 2016a) who get an additional factor of m-1operatornameVar(X) while still running in time tildeO(mathttnnz(X) + mk2d). We perform extensive empirical evaluations to validate our theoretical results and to show the effectiveness of our approach on real datasets.