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

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.