Sampling from Spherical Spin Glasses in Total Variation via Algorithmic Stochastic Localization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914768342745088 |
|---|---|
| author | Huang, Brice Montanari, Andrea Pham, Huy Tuan |
| author_facet | Huang, Brice Montanari, Andrea Pham, Huy Tuan |
| contents | We consider the problem of algorithmically sampling from the Gibbs measure of a mixed $p$-spin spherical spin glass. We give a polynomial-time algorithm that samples from the Gibbs measure up to vanishing total variation error, for any model whose mixture satisfies $$ξ''(s) < \frac{1}{(1-s)^2}, \qquad \forall s\in [0,1).$$ This includes the pure $p$-spin glasses above a critical temperature that is within an absolute ($p$-independent) constant of the so-called shattering phase transition. Our algorithm follows the algorithmic stochastic localization approach introduced in (Alaoui, Montanari, Sellke, 20022). A key step of this approach is to estimate the mean of a sequence of tilted measures. We produce an improved estimator for this task by identifying a suitable correction to the TAP fixed point selected by approximate message passing (AMP). As a consequence, we improve the algorithm's guarantee over previous work, from normalized Wasserstein to total variation error. In particular, the new algorithm and analysis opens the way to perform inference about one-dimensional projections of the measure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_15651 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sampling from Spherical Spin Glasses in Total Variation via Algorithmic Stochastic Localization Huang, Brice Montanari, Andrea Pham, Huy Tuan Probability Disordered Systems and Neural Networks Mathematical Physics We consider the problem of algorithmically sampling from the Gibbs measure of a mixed $p$-spin spherical spin glass. We give a polynomial-time algorithm that samples from the Gibbs measure up to vanishing total variation error, for any model whose mixture satisfies $$ξ''(s) < \frac{1}{(1-s)^2}, \qquad \forall s\in [0,1).$$ This includes the pure $p$-spin glasses above a critical temperature that is within an absolute ($p$-independent) constant of the so-called shattering phase transition. Our algorithm follows the algorithmic stochastic localization approach introduced in (Alaoui, Montanari, Sellke, 20022). A key step of this approach is to estimate the mean of a sequence of tilted measures. We produce an improved estimator for this task by identifying a suitable correction to the TAP fixed point selected by approximate message passing (AMP). As a consequence, we improve the algorithm's guarantee over previous work, from normalized Wasserstein to total variation error. In particular, the new algorithm and analysis opens the way to perform inference about one-dimensional projections of the measure. |
| title | Sampling from Spherical Spin Glasses in Total Variation via Algorithmic Stochastic Localization |
| topic | Probability Disordered Systems and Neural Networks Mathematical Physics |
| url | https://arxiv.org/abs/2404.15651 |