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 Oleft(N/n+log nright) on tildeO(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 mathsfRNC 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 mathsfRNC samplers for the hardcore and Ising models within their uniqueness regimes, as well as an mathsfRNC SAT sampler for satisfying solutions of CNF formulas in a local lemma regime. Furthermore, by employing non-adaptive simulated annealing, these mathsfRNC samplers can be transformed into mathsfRNC algorithms for approximate counting.