Parallelization of Markov Chain Monte Carlo Methods

We analyze a massive search space for finding optimal scalable parallelization strategies, including parallel temperature schedule, mixing strategy, and mixing frequency, for rapid convergence of the parallel Markov Chain Monte Carlo methods. We expect to find out the optimal time and ways for multiple Markov chains to communicate. Also, we adjust the sequential parameter, temperature, to fit for the parallel method. It is impossible to design a general theory applicable to arbitrary objective functions at this stage of our research. We examine the performance of our strategies by testing the optimization of the mobile route recommendation problem. We find that with the careful selection of the parallel strategies, nearly 100% speedup can be achieved. We believe there exists a scheme for these strategies leading to the optimal parallelization.