Sum-of-Squares & Gaussian Processes I: Certification

Abstract

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}$.

143 pages, 0 figures. (Nearly) final version. Rounding delegated to companion paper