Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
复制标题
DOI：
10.1109/focs54457.2022.00038
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
A. Alaoui;A. Montanari;Mark Sellke
中科院分区：
文献类型：
--
作者：
A. Alaoui;A. Montanari;Mark Sellke
考虑高温无外场自旋玻璃的Sherrington-Kirkpatrick模型，研究了多项式时间内Gibbs分布的抽样问题。证明了对于任意逆温度$β1/2$，存在一个复杂性为$O(n^{2})$的算法，它是从一个分布$MU^{\Text{ALS}}$中抽样的，它在归一化Wasserstein距离内接近于$\MU$.也就是说，存在$\MU$和$\MU^{\TEXT{ALG}}$的耦合，如果$(x，x^{\TEXT{ALS}})\in\-1，+1^{n}\Times\-1，+1^{n}$是从该耦合引出的对，则$n^{-1}\mathbb{E}\{\|x-x^{\text{ald}}\|_{2}^{2}\}=o_{n}(1)$.Bauerschmidt和Bodineau[BB19]以及Eldan，Koehler，Zeitouni[EKZ21]以前的最好结果表明，高效的算法可以为$\beta\lt 1/4$近似采样(在更强的度量下)。通过为采样算法引入适当的“稳定性”性质，我们用一个负的结果来补充这个结果，这一性质被许多标准技术所验证。我们证明，即使在归一化的Wasserstein度量下，也没有稳定的算法可以近似采样$\beta$>；1。我们的抽样方法基于随机局部化的算法实现，该算法将测量$\MU$逐渐向单一构型倾斜，并使用近似消息传递算法来近似倾斜测量的平均值。
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 $\mu$ in polynomial time. We prove that, for any inverse temperature $\beta\lt 1/2$, there exists an algorithm with complexity $O(n^{2})$ that samples from a distribution $\mu^{\text{als}}$ which is close in normalized Wasserstein distance to $\mu$. Namely, there exists a coupling of $\mu$ and $\mu^{\text{alg}}$ such that if $(x,x^{\text{als}})\in\{-1,+1\}^{n}\times\{-1,+1\}^{n}$ is a pair drawn from this coupling, then $n^{-1}\mathbb{E}\{\|x-x^{\text{ald}}\|_{2}^{2}\}=o_{n}(1)$. The best previous results, by Bauerschmidt and Bodineau [BB19] and by Eldan, Koehler, Zeitouni [EKZ21], implied efficient algorithms to approximately sample (under a stronger metric) for $\beta\lt 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 $\beta$>1, even under the normalized Wasserstein metric. Our sampling method is based on an algorithmic implementation of stochastic localization, which progressively tilts the measure $\mu$ towards a single configuration, together with an approximate message passing algorithm that is used to approximate the mean of the tilted measure.