OPTIMIZATION OF MEAN-FIELD SPIN GLASSES

Mean-field spin glasses are families of random energy functions (Hamiltonians) on high-dimensional product spaces. In this paper, we consider the case of Ising mixed p-spin models,; namely, Hamiltonians H-N : Sigma(N) -> R on the Hamming hypercube Sigma(N) = [+/- 1](N), which are defined by the property that {H-N(sigma)}(sigma is an element of Sigma N) is a centered Gaussian process with covariance E{H-N(sigma(1)) H-N(sigma(2))} depending only on the scalar product (sigma(1), sigma(2)). The asymptotic value of the optimum max(sigma is an element of Sigma N) H-N (sigma) was characterized in terms of a variational principle known as the Parisi formula, first proved by Talagrand and, in a more general setting, by Panchenko. The structure of superlevel sets is extremely rich and has been studied by a number of authors. Here, we ask whether a near optimal configuration sigma can be computed in polynomial time. We develop a message passing algorithm whose complexity per-iteration is of the same order as the complexity of evaluating the gradient of H-N, and characterize the typical energy value it achieves. When the p-spin model H-N satisfies a certain no-overlap gap assumption, for any epsilon > 0, the algorithm outputs sigma is an element of Sigma(N) such that H-N (sigma) >= (1 - epsilon) max(sigma') H-N (sigma'), with high probability. The number of iterations is bounded in N and depends uniquely on epsilon. More generally, regardless of whether the no-overlap gap assumption holds, the energy achieved is given by an extended variational principle, which generalizes the Parisi formula.