Sum-of-Squares & Gaussian Processes I: Certification
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912061437509632 |
|---|---|
| author | Sandhu, Juspreet Singh Shi, Jonathan |
| author_facet | Sandhu, Juspreet Singh Shi, Jonathan |
| contents | We introduce a class of distributions which may be considered as a smoothed probabilistic version of the ultrametric property that famously characterizes the Gibbs distributions of various spin glass models. This class of \emph{high-entropy step} (HES) distributions is expressive enough to capture a distribution achieving near-optimal average energy on spin glass models in the so-called full Replica-Symmetry Breaking (fRSB) regime.
Simultaneously, with high probability, there are polynomial-size certificates on the average energy achievable by \emph{any} HES distribution which are tight within a constant factor. These certificates can be found in polynomial time by a semidefinite program corresponding to a sum-of-squares (SoS) hierarchy we introduce, termed the HES SoS hierarchy. This improves over classical sum-of-squares certificates which are loose by a factor of $n^{\lfloor p/2 - 1\rfloor/2}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_14383 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sum-of-Squares & Gaussian Processes I: Certification Sandhu, Juspreet Singh Shi, Jonathan Computational Complexity Mathematical Physics Classical Analysis and ODEs Optimization and Control Probability We introduce a class of distributions which may be considered as a smoothed probabilistic version of the ultrametric property that famously characterizes the Gibbs distributions of various spin glass models. This class of \emph{high-entropy step} (HES) distributions is expressive enough to capture a distribution achieving near-optimal average energy on spin glass models in the so-called full Replica-Symmetry Breaking (fRSB) regime. Simultaneously, with high probability, there are polynomial-size certificates on the average energy achievable by \emph{any} HES distribution which are tight within a constant factor. These certificates can be found in polynomial time by a semidefinite program corresponding to a sum-of-squares (SoS) hierarchy we introduce, termed the HES SoS hierarchy. This improves over classical sum-of-squares certificates which are loose by a factor of $n^{\lfloor p/2 - 1\rfloor/2}$. |
| title | Sum-of-Squares & Gaussian Processes I: Certification |
| topic | Computational Complexity Mathematical Physics Classical Analysis and ODEs Optimization and Control Probability |
| url | https://arxiv.org/abs/2401.14383 |