Optimizing Mean Field Spin Glasses with External Field

We consider the Hamiltonians of mean-field spin glasses, which are certain random functions HN defined on high-dimensional cubes or spheres in mathbb RN. 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 HN 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 HN. We give a two-phase message pasing algorithm to approximately maximize HN 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.