Parallelising Glauber dynamics

For distributions over discrete product spaces ${\prod }_{i=1}^n{\mathrm{\Omega }}_i^{\mathrm{\prime }}$, Glauber dynamics is a Markov chain that at each step, resamples a random coordinate conditioned on the other coordinates. We show that $k$-Glauber dynamics, which resamples a random subset of $k$ coordinates, mixes $k$ times faster in ${\chi }^2$-divergence, and assuming approximate tensorization of entropy, mixes $k$ times faster in KL-divergence. We apply this to obtain parallel algorithms in two settings: (1) For the Ising model ${\mu }_{J,h}(x)\propto \exp (\frac{1}{2}⟨x,Jx⟩+⟨h,x⟩)$ with $\mathrm{\parallel }J\mathrm{\parallel }<1-c$ (the regime where fast mixing is known), we show that we can implement each step of $\tilde{\mathrm{\Theta }}(n\mathrm{/}\mathrm{\parallel }J{\mathrm{\parallel }}_F)$-Glauber dynamics efficiently with a parallel algorithm, resulting in a parallel algorithm with running time $\tilde{O}(\mathrm{\parallel }J{\mathrm{\parallel }}_F)=\tilde{O}(\sqrt{n})$. (2) For the mixed $p$-spin model at high enough temperature, we show that with high probability we can implement each step of $\tilde{\mathrm{\Theta }}(\sqrt{n})$-Glauber dynamics efficiently and obtain running time $\tilde{O}(\sqrt{n})$.