论文标题
Sherrington-Kirkpatrick Gibbs通过算法随机定位进行了抽样
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
论文作者
论文摘要
我们考虑了高温和没有外部场的自旋玻璃的Sherrington-Kirkpatrick模型，并研究了来自Gibbs分布在多项式时间的$μ$的采样问题。我们证明，对于任何反向温度$β<1/2 $，存在一种具有复杂性$ o（n^2）$的算法，该算法是从分布的$μ^{alg} $中取样的算法，该算法在正常化的wasserstein距离为$μ$。也就是说，存在$μ$和$μ^{alg} $的耦合，以便如果$（x，x，x，x^{alg}）\ in \ { - 1，+1，+1 \}^n \ times \ times \ { - 1，+1，+1 \}^n $是从这个coupln中绘制的，然后是$ n^} e \ {|| x-x^{alg} || _2^2 \} = o_n（1）$。 Bauerschmidt和Bodineau以及Eldan，Koehler和Zeitouni的最佳先前结果暗示了有效的算法，以$β<1/4 $的价格（按更强的度量）进行样品（按更强的度量）。 我们通过引入合适的“稳定性”属性来对其进行采样算法，以负面的结果进行补充，该算法通过许多标准技术验证。我们证明，即使在标准化的瓦斯坦公制下，也没有稳定的算法可以以$β> 1 $的价格进行样品。 我们的采样方法基于随机定位的算法实现，该算法将尺寸$μ$ $μ$ $μ$ $μ$与单个配置倾斜，以及近似消息传递算法，该算法用于近似倾斜度的均值。
We consider the Sherrington-Kirkpatrick model of spin glasses at high-temperature and no external field, and study the problem of sampling from the Gibbs distribution $μ$ in polynomial time. We prove that, for any inverse temperature $β<1/2$, there exists an algorithm with complexity $O(n^2)$ that samples from a distribution $μ^{alg}$ which is close in normalized Wasserstein distance to $μ$. Namely, there exists a coupling of $μ$ and $μ^{alg}$ such that if $(x,x^{alg})\in\{-1,+1\}^n\times \{-1,+1\}^n$ is a pair drawn from this coupling, then $n^{-1}\mathbb E\{||x-x^{alg}||_2^2\}=o_n(1)$. The best previous results, by Bauerschmidt and Bodineau and by Eldan, Koehler, and Zeitouni, implied efficient algorithms to approximately sample (under a stronger metric) for $β<1/4$. We complement this result with a negative one, by introducing a suitable "stability" property for sampling algorithms, which is verified by many standard techniques. We prove that no stable algorithm can approximately sample for $β>1$, even under the normalized Wasserstein metric. Our sampling method is based on an algorithmic implementation of stochastic localization, which progressively tilts the measure $μ$ towards a single configuration, together with an approximate message passing algorithm that is used to approximate the mean of the tilted measure.
