Simple parallel algorithms for single-site dynamics

DOI10.1145/3519935.3519999MaRDI QIDQ6083598zbMATH OpenOpenAlexFDO

Authors Hongyang Liu, Yitong Yin

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.04044

zbMATH Keywords

Markov chain Monte Carlosamplingsingle-site dynamics

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The single-site dynamics are a canonical class of Markov chains for sampling from high-dimensional probability distributions, e.g. the ones represented by graphical models. We give a simple and generic parallel algorithm that can faithfully simulate single-site dynamics. When the chain asymptotically satisfies the $el{l}_p$-Dobrushin's condition, specifically, when the Dobrushin's influence matrix has constantly bounded $el{l}_p$-induced operator norm for an arbitrary $pin[1,infty]$, the parallel simulation of $N$ steps of single-site updates succeeds within $Oleft(N/n+lognight)$ depth of parallel computing using $ildeO(m)$ processors, where $n$ is the number of sites and $m$ is the size of graphical model. Since the Dobrushin's condition is almost always satisfied asymptotically by mixing chains, this parallel simulation algorithm essentially transforms single-site dynamics with optimal $O(nlogn)$ mixing time to RNC algorithms for sampling. In particular we obtain RNC samplers, for the Ising models on general graphs in the uniqueness regime, and for satisfying solutions of CNF formulas in a local lemma regime. With non-adaptive simulated annealing, these RNC samplers can be transformed routinely to RNC algorithms for approximate counting. A key step in our parallel simulation algorithm, is a so-called "universal coupling" procedure, which tries to simultaneously couple all distributions over the same sample space. We construct such a universal coupling, that for every pair of distributions the coupled probability is at least their Jaccard similarity. We also prove this is optimal in the worst case. The universal coupling and its applications are of independent interests.

Recommendations

• Fast parallel algorithms for short-range molecular dynamics
• A parallel implementation of the Wang-Landau algorithm
• Efficient parallel simulations of dynamic Ising spin systems
• Efficient parallel algorithms for molecular dynamics simulations
• scientific article; zbMATH DE number 1262862
• Parallel molecular dynamics simulations for short-ranged many-body potentials
• Numerical analysis of parallel replica dynamics
• scientific article; zbMATH DE number 2156331
• scientific article; zbMATH DE number 5199790

Cited in

(2)

• Parallelising Glauber dynamics
• Efficient parallel Ising samplers via localization schemes

This page was built for publication: Simple parallel algorithms for single-site dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083598)