  Computational couplings of Markov chains provide a practical route to
unbiased Monte Carlo estimation that can utilize parallel computation. However,
these approaches depend crucially on chains meeting after a small number of
transitions. For models that assign data into groups, e.g. mixture models, the
obvious approaches to couple Gibbs samplers fail to meet quickly. This failure
owes to the so-called "label-switching" problem; semantically equivalent
relabelings of the groups contribute well-separated posterior modes that impede
fast mixing and cause large meeting times. We here demonstrate how to avoid
label switching by considering chains as exploring the space of partitions
rather than labelings. Using a metric on this space, we employ an optimal
transport coupling of the Gibbs conditionals. This coupling outperforms
alternative couplings that rely on labelings and, on a real dataset, provides
estimates more precise than usual ergodic averages in the limited time regime.
Code is available at github.com/tinnguyen96/coupling-Gibbs-partition.
