Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2105.03506 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917572291592192 |
|---|---|
| author | Sellke, Mark |
| author_facet | Sellke, Mark |
| contents | We consider the Hamiltonians of mean-field spin glasses, which are certain random functions $H_N$ defined on high-dimensional cubes or spheres in $\mathbb R^N$. The asymptotic maximum values of these functions were famously obtained by Talagrand and later by Panchenko and by Chen. The landscape of approximate maxima of $H_N$ is described by various forms of replica symmetry breaking exhibiting a broad range of possible behaviors. We study the problem of efficiently computing an approximate maximizer of $H_N$.
We give a two-phase message pasing algorithm to approximately maximize $H_N$ when a no overlap-gap condition holds. This generalizes several recent works by allowing a non-trivial external field. For even Ising spin glasses with constant external field, our algorithm succeeds exactly when existing methods fail to rule out approximate maximization for a wide class of algorithms. Moreover we give a branching variant of our algorithm which constructs a full ultrametric tree of approximate maxima. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_03506 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Optimizing Mean Field Spin Glasses with External Field Sellke, Mark Disordered Systems and Neural Networks Optimization and Control Probability We consider the Hamiltonians of mean-field spin glasses, which are certain random functions $H_N$ defined on high-dimensional cubes or spheres in $\mathbb R^N$. The asymptotic maximum values of these functions were famously obtained by Talagrand and later by Panchenko and by Chen. The landscape of approximate maxima of $H_N$ is described by various forms of replica symmetry breaking exhibiting a broad range of possible behaviors. We study the problem of efficiently computing an approximate maximizer of $H_N$. We give a two-phase message pasing algorithm to approximately maximize $H_N$ when a no overlap-gap condition holds. This generalizes several recent works by allowing a non-trivial external field. For even Ising spin glasses with constant external field, our algorithm succeeds exactly when existing methods fail to rule out approximate maximization for a wide class of algorithms. Moreover we give a branching variant of our algorithm which constructs a full ultrametric tree of approximate maxima. |
| title | Optimizing Mean Field Spin Glasses with External Field |
| topic | Disordered Systems and Neural Networks Optimization and Control Probability |
| url | https://arxiv.org/abs/2105.03506 |