Spectral Independence via Stability and Applications to Holant-Type Problems
Spectral Independence via Stability and Applications to Holant-Type Problems
复制标题
DOI：
10.1109/focs52979.2021.00023
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Zongchen Chen;Kuikui Liu;Eric Vigoda
中科院分区：
文献类型：
--
作者：
Zongchen Chen;Kuikui Liu;Eric Vigoda
本文将多项式的稳定性与马尔可夫链蒙特卡洛（MCMC）算法的收敛速率之间形式化。我们证明，如果在实际点$ \ lambda $周围的区域中（多元）分区功能非零，那么Spectral Independence的保留为$ \ lambda $。结果，对于有限度图上的Holant型问题（例如，自旋系统），我们获得了最佳$ O（n \\ text {log} \ n）$混合时间范围单点更新Markov链已知作为Glauber动态。我们的结果大大改善了通过Patel and Regts（2017）精炼的Barvi-Nok（2017）的多项式插值方法获得的运行时间保证。我们的结果有多种应用。在本文中，我们专注于Holant-Type（即边缘色）问题，包括加权边缘盖和加权的均匀图。对于加权边缘盖问题（和几个天然概括），我们在有限度图上获得了$ o $（$ n $ log n）采样算法。均匀的子图问题对应于铁磁ising模型的高温扩张。我们为铁磁伊辛模型获得了$ o $（$ n $ log n）采样算法，该模型在有限度图上具有非零外部字段，该模型在此类图的经典结果上改善了经典的结果。我们在线图上，加权图同构，张量网络等上获得了反铁磁两旋模型的进一步应用。
This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition function is nonzero in a region around a real point $\lambda$ then spectral independence holds at $\lambda$. As a consequence, for Holant-type problems (e.g., spin systems) on bounded-degree graphs, we obtain optimal $O(n\ \text{log}\ n)$ mixing time bounds for the single-site update Markov chain known as the Glauber dynamics. Our result significantly improves the running time guarantees obtained via the polynomial interpolation method of Barvi-nok (2017), refined by Patel and Regts (2017). There are a variety of applications of our results. In this paper, we focus on Holant-type (i.e., edge-coloring) problems, including weighted edge covers and weighted even subgraphs. For the weighted edge cover problem (and several natural generalizations) we obtain an $O$($n$ log n) sampling algorithm on bounded-degree graphs. The even subgraphs problem corresponds to the high-temperature expansion of the ferromagnetic Ising model. We obtain an $O$($n$ log n) sampling algorithm for the ferromagnetic Ising model with a nonzero external field on bounded-degree graphs, which improves upon the classical result of Jerrum and Sinclair (1993) for this class of graphs. We obtain further applications to antiferromagnetic two-spin models on line graphs, weighted graph homomorphisms, tensor networks, and more.