# Many processors, little time: MCMC for partitions via optimal transport couplings

arXiv: https://arxiv.org/abs/2202.11258 · HTML: https://mlsanity.com/paper/2202.11258/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 65 references that are in the map.
- First posted on arXiv 23 Feb 2022.

## Builds on (most cited first, 10 of 10)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Interactive Supercomputing on 40,000 Cores for Machine Learning and Data Analysis](https://mlsanity.com/paper/1807.07814/) (2018)
- [Scalable Bayes via Barycenter in Wasserstein Space](https://mlsanity.com/paper/1508.05880/) (2015)
- [Validated Variational Inference via Practical Posterior Error Bounds](https://mlsanity.com/paper/1910.04102/) (2019)
- [Mixture models with a prior on the number of components](https://mlsanity.com/paper/1502.06241/) (2015)
- [Recombination: A family of Markov chains for redistricting](https://mlsanity.com/paper/1911.05725/) (2019)
- [Variational consensus Monte Carlo](https://mlsanity.com/paper/1506.03074/) (2015)
- [Couplings for Multinomial Hamiltonian Monte Carlo](https://mlsanity.com/paper/2104.05134/) (2021)
- [Improved Bounds for Randomly Sampling Colorings via Linear Programming](https://mlsanity.com/paper/1810.12980/) (2018)

## Built on by (most cited first, 6 of 6)

- [Scalable Unbalanced Sobolev Transport for Measures on a Graph](https://mlsanity.com/paper/2302.12498/) (2023)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [Optimal Transport for Measures with Noisy Tree Metric](https://mlsanity.com/paper/2310.13653/) (2023)
- [Tree-Sliced Wasserstein Distance: A Geometric Perspective](https://mlsanity.com/paper/2406.13725/) (2024)
- [Distance-Based Tree-Sliced Wasserstein Distance](https://mlsanity.com/paper/2503.11050/) (2025)
- [Tree-Sliced Wasserstein Distance with Nonlinear Projection](https://mlsanity.com/paper/2505.00968/) (2025)

## Abstract (arXiv)

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.