Approximating a probability distribution using a set of particles is a fundamental problem in machine learning and statistics, with applications including clustering and quantization. We formalize this problem by seeking a weighted mixture of Dirac measures that best approximates the target distribution in the sense of maximum mean discrepancy (MMD). We argue that a Wasserstein--Fisher--Rao gradient flow is well-suited to designing such weighted quantizations, and show that this flow can be discretized using a system of interacting particles that satisfy simple closed-form ODEs. To more efficiently reach a stationary solution of these ODEs, we derive a new fixed-point algorithm called mean shift interacting particles (MSIP). We show that MSIP extends the classical mean shift algorithm, widely used for identifying modes in kernel density estimates. Moreover, we show that MSIP can be interpreted as a preconditioned gradient descent with important acceleration properties, and that it acts as a relaxation of Lloyd’s algorithm for clustering. This unification of gradient flows, mean shift, and MMD-optimal quantization yields algorithms that are more robust and efficient than state-of-the-art methods, as demonstrated empirically.
Time permitting, we will also discuss links between MMD quantization and Bayesian quadrature, and present extensions of MSIP to the problem of sampling given access to the unnormalized target density and score.
This is joint work with Ayoub Belhadji and Daniel Sharp.
