Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2505.05185 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908354061795328 |
|---|---|
| author | Chen, Xiaoyu Liu, Hongyang Yin, Yitong Zhang, Xinyuan |
| author_facet | Chen, Xiaoyu Liu, Hongyang Yin, Yitong Zhang, Xinyuan |
| contents | We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficiency, with polylogarithmic depth and polynomial total work, and are applicable to Ising models in the following regimes: (1) Ferromagnetic Ising models with external fields; (2) Ising models with interaction matrix $J$ of operator norm $\|J\|_2<1$.
Our parallel Gibbs sampling approaches are based on localization schemes, which have proven highly effective in establishing rapid mixing of Gibbs sampling. In this work, we employ two such localization schemes to obtain efficient parallel Ising samplers: the \emph{field dynamics} induced by \emph{negative-field localization}, and \emph{restricted Gaussian dynamics} induced by \emph{stochastic localization}. This shows that localization schemes are powerful tools, not only for achieving rapid mixing but also for the efficient parallelization of Gibbs sampling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05185 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Parallel Ising Samplers via Localization Schemes Chen, Xiaoyu Liu, Hongyang Yin, Yitong Zhang, Xinyuan Data Structures and Algorithms We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficiency, with polylogarithmic depth and polynomial total work, and are applicable to Ising models in the following regimes: (1) Ferromagnetic Ising models with external fields; (2) Ising models with interaction matrix $J$ of operator norm $\|J\|_2<1$. Our parallel Gibbs sampling approaches are based on localization schemes, which have proven highly effective in establishing rapid mixing of Gibbs sampling. In this work, we employ two such localization schemes to obtain efficient parallel Ising samplers: the \emph{field dynamics} induced by \emph{negative-field localization}, and \emph{restricted Gaussian dynamics} induced by \emph{stochastic localization}. This shows that localization schemes are powerful tools, not only for achieving rapid mixing but also for the efficient parallelization of Gibbs sampling. |
| title | Efficient Parallel Ising Samplers via Localization Schemes |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.05185 |