2025/02/04 by Poojan Shah, Shah, Poojan, Agrawal, Shashwat +2
Computer Science · Mathematics · #Advanced Statistical Methods and Models #Computer science #Data Structures and Algorithms (cs.DS) #Economics #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Mathematics #Sampling (signal processing) #Statistical Methods and Inference #Telecommunications
paper · pdf · doi:10.48550/arxiv.2502.02085
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ⊂ ℝ 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 O(\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 O 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-Ω( m/β) Var (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-1Var(X) while still running in time O(\mathttnnz(X) + mk2d). We perform extensive empirical evaluations to validate our theoretical results and to show the effectiveness of our approach on real datasets.