Parallelize Single-Site Dynamics up to Dobrushin Criterion

Single-site dynamics are canonical Markov chain based algorithms for sampling from high-dimensional distributions, such as the Gibbs distributions of graphical models. We introduce a simple and generic parallel algorithm that faithfully simulates single-site dynamics. Under a much relaxed, asymptotic variant of the ℓ p -Dobrushin’s condition—where the Dobrushin’s influence matrix has a bounded ℓ p -induced operator norm for an arbitrary p ∈ [1, ∞]—our algorithm simulates N steps of single-site updates within a parallel depth of O ( N / n +log n ) on Õ( m ) processors, where n is the number of sites and m is the size of the graphical model. For Boolean-valued random variables, if the ℓ p -Dobrushin’s condition holds—specifically, if the ℓ p -induced operator norm of the Dobrushin’s influence matrix is less than 1—the parallel depth can be further reduced to O (log N + log n ), achieving an exponential speedup. These results suggest that single-site dynamics with near-linear mixing times can be parallelized into RNC sampling algorithms, independent of the maximum degree of the underlying graphical model, as long as the Dobrushin influence matrix maintains a bounded operator norm. We show the effectiveness of this approach with RNC samplers for the hardcore and Ising models within their uniqueness regimes, as well as an RNC SAT sampler for satisfying solutions of conjunctive normal form formulas in a local lemma regime. Furthermore, by employing non-adaptive simulated annealing, these RNC samplers can be transformed into RNC algorithms for approximate counting.