OPTIMIZATION OF MEAN-FIELD SPIN GLASSES
OPTIMIZATION OF MEAN-FIELD SPIN GLASSES
复制标题
DOI：
10.1214/21-aop1519
复制
发表时间：
2021-11-01
影响因子：
2.3
通讯作者：
Sellke, Mark
中科院分区：
文献类型：
--
作者：
El Alaoui, Ahmed;Montanari, Andrea;Sellke, Mark
平均场自旋玻璃是高维乘积空间上的随机能量函数族(哈密顿量)。本文考虑Ising混合p-自旋模型的情形，即哈密顿量H-N：Sigma(N)->；R关于Hamming超立方体Sigma(N)=[+/-1](N)，其定义是：{H-N(Sigma)}(Sigma是Sigma N的元素)是一个中心高斯过程，协方差E{H-N(Sigma(1))H-N(Sigma(2))}仅与标量积(Sigma(1)，Sigma(2))有关。最优max(Sigma是Sigma N的一个元素)H-N(Sigma)的渐近值被用称为Parisi公式的变分原理来刻画，该公式首先由TALAGRAND和在更广泛的背景下，潘琴科著。超水平集的结构极其丰富，已经被许多作者研究过。本文提出了一种消息传递算法，其每次迭代的复杂度与计算H-N的梯度的复杂度相同，并对其所获得的典型能量值进行了刻画。当p-自旋模型H-N满足一定的无重叠能隙假设时，对于任一epsilon>；0，该算法输出的sigma是Sigma(N)的一个元素，使得H-N(Sigma)>；=(1-epsilon)max(sigma‘)H-N(sigma’)，概率很高。迭代次数在N中有界，并且唯一地依赖于epsilon。更广泛地说，无论无重叠能隙假设是否成立，所获得的能量都是由推广了Parisi公式的扩展变分原理给出的。
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.