Scaling-up Split-Merge MCMC with Locality Sensitive Sampling (LSS)
  Split-Merge MCMC (Monte Carlo Markov Chain) is one of the essential and
popular variants of MCMC for problems when an MCMC state consists of an unknown
number of components. It is well known that state-of-the-art methods for
split-merge MCMC do not scale well. Strategies for rapid mixing requires smart
and informative proposals to reduce the rejection rate. However, all known
smart proposals involve expensive operations to suggest informative
transitions. As a result, the cost of each iteration is prohibitive for massive
scale datasets. It is further known that uninformative but computationally
efficient proposals, such as random split-merge, leads to extremely slow
convergence. This tradeoff between mixing time and per update cost seems hard
to get around.
  In this paper, we show a sweet spot. We leverage some unique properties of
weighted MinHash, which is a popular LSH, to design a novel class of
split-merge proposals which are significantly more informative than random
sampling but at the same time efficient to compute. Overall, we obtain a
superior tradeoff between convergence and per update cost. As a direct
consequence, our proposals are around 6X faster than the state-of-the-art
sampling methods on two large real datasets KDDCUP and PubMed with several
millions of entities and thousands of clusters.
