A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics

Understand

\emph{Sampling} constitutes an important tool in a variety of areas: from machine learning and combinatorial optimization to computational physics and biology.

• A central class of sampling algorithms is the \emph{Markov Chain Monte Carlo} method, based on the construction of a Markov chain with the desired sampling distribution as its stationary distribution.
• Many of the traditional Markov chains, such as the \emph{Glauber dynamics}, do not scale well with increasing dimension.
• To address this shortcoming, we propose a simple local update rule based on the Glauber dynamics that leads to efficient parallel and distributed algorithms for sampling from Gibbs distributions.