stat.ML · 2604.14810 Copy arXiv ID · Apr 16, 2026 Save Scalable Model-Based Clustering with Sequential Monte Carlo Authors: Connie Trojan , Pavel Myshkov , Paul Fearnhead , James Hensman , Tom Minka , Christopher Nemeth
Organizations: Lancaster University · Microsoft Research
Abstract In online clustering problems, there is often a large amount of uncertainty over possible cluster assignments that cannot be resolved until more data are observed. This difficulty is compounded when clusters follow complex distributions, as is the case with text data. Sequential Monte Carlo (SMC) methods give a natural way of representing and updating this uncertainty over time, but have prohibitive memory requirements for large-scale problems. We propose a novel SMC algorithm that decomposes clustering problems into approximately independent subproblems, allowing a more compact representation of the algorithm state. Our approach is motivated by the knowledge base construction problem, and we show that our method is able to accurately and efficiently solve clustering problems in this setting and others where traditional SMC struggles.
Explore similar work Jul 6, 2026 · Cristian Boldrin, Fabio Vandin K-Means Kernel Method
Jul 17, 2026 · Ravil Mussabayev, Rustam Mussabayev, Zukhra Yerdaliyeva +1 K-Means Image Clustering
Sep 15, 2026 · Savik Kinger, Luciano Dyballa, Steven W. Zucker Manifold Learning Method Input Uncertainties
Jul 6, 2026 · cs.LG J/K move · Enter open · S save
Cristian Boldrin, Fabio Vandin
University of Padova, Padova, Italy
We study the problem of k-means clustering on large datasets. The state-of-the-art for the problem is given by coresets-based approaches, which build small weighted summaries of the input and derive approximate solutions with rigorous quality guarantees from them. One of the most popular and advanced approaches to derive coresets for k-means is sensitivity sampling. However, sensitivity sampling requires to compute the importance of each input point with respect to the whole dataset over all possible choices of centers. Since the exact computation of such quantities is unfeasible, current approaches work by approximating the sensitivity values. Nevertheless, the runtime of such approaches is still impractical for large datasets. In this work, we propose to reduce the runtime of sensitivity-based approaches for k-means by leveraging predictions to approximate the importance of input points. We first formally prove that current theoretical results on coresets construction via sensitivity sampling hold for coarser approximations of sensitivities compared to the one required by existing approaches. This implies that even fairly noisy predictors can be leveraged for sensitivity-sampling approaches. We then propose a natural predictor, which applies to the common scenario where clustering is performed (over time) on a sequence of datasets from the same problem. We prove that when the datasets in the sequence come from the same (unknown) distribution, centers resulting in a low error on one dataset can be used as predictions for sensitivity sampling in subsequent datasets, with guarantees on their quality. We perform an extensive experimental evaluation showing that our approach significantly improves, in terms of clustering cost vs runtime, over uniform sampling and state-of-the-art sensitivity sampling approaches when applied to sequences of datasets.