Distributed Metropolis Sampler with Optimal Parallelism
The Metropolis-Hastings algorithm is a fundamental Markov chain Monte Carlo (MCMC) method for sampling and inference. With the advent of Big Data, distributed and parallel variants of MCMC methods are attracting increased attention. In this paper, we give a distributed algorithm that can correctly simulate sequential single-site Metropolis chains without any bias in a fully asynchronous message-passing model. Furthermore, if a natural Lipschitz condition is satisfied by the Metropolis filters, our algorithm can simulate $N$-step Metropolis chains within $O(N/n+\log n)$ rounds of asynchronous communications, where $n$ is the number of variables. For sequential single-site dynamics, whose mixing requires $\Omega(n\log n)$ steps, this achieves an optimal linear speedup. For several well-studied important graphical models, including proper graph coloring, hardcore model, and Ising model, our condition for linear speedup is weaker than the respective uniqueness (mixing) conditions. The novel idea in our algorithm is to resolve updates in advance: the local Metropolis filters can often be executed correctly before the full information about neighboring spins is available. This achieves optimal parallelism without introducing any bias.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
AI Metropolis: Scaling Large Language Model-based Multi-Agent Simulation with Out-of-order Execution
With more advanced natural language understanding and reasoning capabilities, large language model (LLM)-powered agents are increasingly developed in simulated environments to perform complex tasks, interact with other a…
Language ModelingLanguage ModellingLarge Language ModelNatural Language Understanding+1Cyclical Kernel Adaptive Metropolis
We propose cKAM, cyclical Kernel Adaptive Metropolis, which incorporates a cyclical stepsize scheme to allow control for exploration and sampling. We show that on a crafted bimodal distribution, existing Adaptive Metropo…
Oops I Took A Gradient: Scalable Sampling for Discrete Distributions
We propose a general and scalable approximate sampling strategy for probabilistic models with discrete variables. Our approach uses gradients of the likelihood function with respect to its discrete inputs to propose upda…
Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian models
We study general coordinate-wise MCMC schemes (such as Metropolis-within-Gibbs samplers), which are commonly used to fit Bayesian non-conjugate hierarchical models. We relate their convergence properties to the ones of t…
Importance is Important: Generalized Markov Chain Importance Sampling Methods
We show that for any multiple-try Metropolis algorithm, one can always accept the proposal and evaluate the importance weight that is needed to correct for the bias without extra computational cost. This results in a gen…