Parallelising Glauber dynamics
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913423760031744 |
|---|---|
| author | Lee, Holden |
| author_facet | Lee, Holden |
| contents | For distributions over discrete product spaces $\prod_{i=1}^n Ω_i'$, 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 $χ^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 $μ_{J,h}(x)\propto \exp(\frac1 2\left\langle x,Jx \right\rangle + \langle h,x\rangle)$ with $\|J\|<1-c$ (the regime where fast mixing is known), we show that we can implement each step of $\widetilde Θ(n/\|J\|_F)$-Glauber dynamics efficiently with a parallel algorithm, resulting in a parallel algorithm with running time $\widetilde O(\|J\|_F) = \widetilde 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 $\widetilde Θ(\sqrt n)$-Glauber dynamics efficiently and obtain running time $\widetilde O(\sqrt n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_07131 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Parallelising Glauber dynamics Lee, Holden Data Structures and Algorithms Probability For distributions over discrete product spaces $\prod_{i=1}^n Ω_i'$, 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 $χ^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 $μ_{J,h}(x)\propto \exp(\frac1 2\left\langle x,Jx \right\rangle + \langle h,x\rangle)$ with $\|J\|<1-c$ (the regime where fast mixing is known), we show that we can implement each step of $\widetilde Θ(n/\|J\|_F)$-Glauber dynamics efficiently with a parallel algorithm, resulting in a parallel algorithm with running time $\widetilde O(\|J\|_F) = \widetilde 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 $\widetilde Θ(\sqrt n)$-Glauber dynamics efficiently and obtain running time $\widetilde O(\sqrt n)$. |
| title | Parallelising Glauber dynamics |
| topic | Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2307.07131 |