We present novel results for fast mixing of Glauber dynamics using the newly introduced and powerful Spectral Independence method from [Anari, Liu, Oveis-Gharan: FOCS 2020]. In our results, the parameters of the Gibbs distribution are expressed in terms of the spectral radius of the adjacency matrix of $G$, or that of the Hashimoto non-backtracking matrix. The analysis relies on new techniques that we introduce to bound the maximum eigenvalue of the pairwise influence matrix $\mathcal{I}^{\Lambda,\tau}_{G}$ for the two spin Gibbs distribution $\mu$. There is a common framework that underlies these techniques which we call the topological method. The idea is to systematically exploit the well-known connections between $\mathcal{I}^{\Lambda,\tau}_{G}$ and the topological construction called tree of self-avoiding walks. Our approach is novel and gives new insights to the problem of establishing spectral independence for Gibbs distributions. More importantly, it allows us to derive new -- improved -- rapid mixing bounds for Glauber dynamics on distributions such as the Hard-core model and the Ising model for graphs that the spectral radius is smaller than the maximum degree.
翻译:我们用新推出的和强大的光谱独立法快速混合Glauber动态,从[Anari, Liu, Oveis-Gharan:FOCS 2020] 中得出新的结果。 在我们的结果中,Gibs分布的参数是以G$或桥本非背跟踪矩阵的光谱半径表示的。 分析依赖于我们引入的新技术,以约束双向影响矩阵的最大电子价值$mathcal{I ⁇ Lambda,\tau ⁇ G}, 用于两种旋转Gibs分布 $\mu$。 我们称之为表层法的这些技术有一个共同的框架。 想法是系统地利用$mathcal{I ⁇ Lambda,\tau ⁇ } 和称为自我欣赏行道树的表层构造之间的众所周知的联系。 我们的方法是新颖的,并使人们对为Gibbbbbs的分布建立光谱独立性的问题有了新的洞察。 更重要的是, 它使我们能够开发新的模型 -- -- 改进的快速混合的模型, 用于核心的光谱系分布的深度, 即是较小的光谱度。