Scaling-up Split-Merge MCMC with Locality Sensitive Sampling .

Split-Merge MCMC (Monte Carlo Markov Chain) is one of the essential andpopular variants of MCMC for problems when an MCMC state consists of an unknownnumber of components or clusters. It is well known that state-of-the-artmethods for split-merge MCMC do not scale well. Strategies for rapid mixingrequires smart and informative proposals to reduce the rejection rate. However,all known smart proposals involve cost at least linear in the size of the data$ \ge O(N)$, to suggest informative transitions. Thus, the cost of eachiteration is prohibitive for massive scale datasets. It is further known thatuninformative but computationally efficient proposals, such as randomsplit-merge, leads to extremely slow convergence. This tradeoff between mixingtime and per update cost seems hard to get around. In this paper, we get aroundthis tradeoff by utilizing simple similarity information, such as cosinesimilarity, between the entity vectors to design a proposal distribution. Suchinformation is readily available in almost all applications. We show that therecent use of locality sensitive hashing for efficient adaptive sampling can beleveraged to obtain a computationally efficient pseudo-marginal MCMC. The newsplit-merge MCMC has constant time update, just like random split-merge, and atthe same time the proposal is informative and needs significantly feweriterations than random split-merge. Overall, we obtain a sweet tradeoff betweenconvergence and per update cost. As a direct consequence, our proposal, namedLSHSM, is around 10x faster than the state-of-the-art sampling methods on bothsynthetic datasets and two large real datasets KDDCUP and PubMed with severalmillions of entities and thousands of cluster centers.