Near-optimal shattering in the Ising pure p-spin and rarity of solutions returned by stable algorithms
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913645653393408 |
|---|---|
| author | Alaoui, Ahmed El |
| author_facet | Alaoui, Ahmed El |
| contents | We show that in the Ising pure $p$-spin model of spin glasses, shattering takes place at all inverse temperatures $β\in (\sqrt{(2 \log p)/p}, \sqrt{2\log 2})$ when $p$ is sufficiently large as a function of $β$. Of special interest is the lower boundary of this interval which matches the large $p$ asymptotics of the inverse temperature marking the hypothetical dynamical transition predicted in statistical physics. We show this as a consequence of a `soft' version of the overlap gap property which asserts the existence of a distance gap of points of typical energy from a typical sample from the Gibbs measure. We further show that this latter property implies that stable algorithms seeking to return a point of at least typical energy are confined to an exponentially rare subset of that super-level set, provided that their success probability is not vanishingly small. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03511 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-optimal shattering in the Ising pure p-spin and rarity of solutions returned by stable algorithms Alaoui, Ahmed El Probability Disordered Systems and Neural Networks Mathematical Physics We show that in the Ising pure $p$-spin model of spin glasses, shattering takes place at all inverse temperatures $β\in (\sqrt{(2 \log p)/p}, \sqrt{2\log 2})$ when $p$ is sufficiently large as a function of $β$. Of special interest is the lower boundary of this interval which matches the large $p$ asymptotics of the inverse temperature marking the hypothetical dynamical transition predicted in statistical physics. We show this as a consequence of a `soft' version of the overlap gap property which asserts the existence of a distance gap of points of typical energy from a typical sample from the Gibbs measure. We further show that this latter property implies that stable algorithms seeking to return a point of at least typical energy are confined to an exponentially rare subset of that super-level set, provided that their success probability is not vanishingly small. |
| title | Near-optimal shattering in the Ising pure p-spin and rarity of solutions returned by stable algorithms |
| topic | Probability Disordered Systems and Neural Networks Mathematical Physics |
| url | https://arxiv.org/abs/2412.03511 |