Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913492746895360 |
|---|---|
| author | Huang, Neng Perkins, Will Potechin, Aaron |
| author_facet | Huang, Neng Perkins, Will Potechin, Aaron |
| contents | We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree $d$ for large constant $d$, proving that when the normalized inverse temperature satisfies $β>1$ (asymptotically corresponding to the condensation threshold), then w.h.p. over the random graph there is no stable sampling algorithm that can output a sample close in $W_2$ distance to the Gibbs measure. The results also apply to a fixed-magnetization version of the model, showing that there are no stable sampling algorithms for low but positive temperature max and min bisection distributions. These results show a gap in the tractability of search and sampling problems: while there are efficient algorithms to find near optimizers, stable sampling algorithms cannot access the Gibbs distribution concentrated on such solutions.
Our techniques involve extensions of the interpolation technique relating behavior of the mean field Sherrington-Kirkpatrick model to behavior of Ising models on random graphs of average degree $d$ for large $d$. While previous interpolation arguments compared the free energies of the two models, our argument compares the average energies and average overlaps in the two models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03974 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hardness of sampling for the anti-ferromagnetic Ising model on random graphs Huang, Neng Perkins, Will Potechin, Aaron Probability Computational Complexity Data Structures and Algorithms We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree $d$ for large constant $d$, proving that when the normalized inverse temperature satisfies $β>1$ (asymptotically corresponding to the condensation threshold), then w.h.p. over the random graph there is no stable sampling algorithm that can output a sample close in $W_2$ distance to the Gibbs measure. The results also apply to a fixed-magnetization version of the model, showing that there are no stable sampling algorithms for low but positive temperature max and min bisection distributions. These results show a gap in the tractability of search and sampling problems: while there are efficient algorithms to find near optimizers, stable sampling algorithms cannot access the Gibbs distribution concentrated on such solutions. Our techniques involve extensions of the interpolation technique relating behavior of the mean field Sherrington-Kirkpatrick model to behavior of Ising models on random graphs of average degree $d$ for large $d$. While previous interpolation arguments compared the free energies of the two models, our argument compares the average energies and average overlaps in the two models. |
| title | Hardness of sampling for the anti-ferromagnetic Ising model on random graphs |
| topic | Probability Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.03974 |