Many processors, little time: MCMC for partitions via optimal transport couplings
This work solves the problem of biased parallel MCMC for clustering, which is incremental as it adapts existing coupling ideas to discrete variables.
The paper tackled the problem of slow mixing and bias in parallel Markov chain Monte Carlo (MCMC) methods for clustering by addressing the label-switching issue, resulting in a practical algorithm using optimal transport couplings that improves accuracy and efficiency in time-limited parallel settings.
Markov chain Monte Carlo (MCMC) methods are often used in clustering since they guarantee asymptotically exact expectations in the infinite-time limit. In finite time, though, slow mixing often leads to poor performance. Modern computing environments offer massive parallelism, but naive implementations of parallel MCMC can exhibit substantial bias. In MCMC samplers of continuous random variables, Markov chain couplings can overcome bias. But these approaches depend crucially on paired chains meetings after a small number of transitions. We show that straightforward applications of existing coupling ideas to discrete clustering variables fail to meet quickly. This failure arises from the "label-switching problem": semantically equivalent cluster relabelings impede fast meeting of coupled chains. We instead consider chains as exploring the space of partitions rather than partitions' (arbitrary) labelings. Using a metric on the partition space, we formulate a practical algorithm using optimal transport couplings. Our theory confirms our method is accurate and efficient. In experiments ranging from clustering of genes or seeds to graph colorings, we show the benefits of our coupling in the highly parallel, time-limited regime.