Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
复制标题
DOI：
10.1145/3406325.3451035
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Zongchen Chen;Kuikui Liu;Eric Vigoda
中科院分区：
文献类型：
--
作者：
Zongchen Chen;Kuikui Liu;Eric Vigoda
我们证明了一个最佳的混合时间界的单站点更新马尔可夫链称为格劳伯动态或吉布斯采样在各种设置。我们的工作提出了Anari et al.（2020）的谱独立方法的改进版本，并且当相关影响矩阵的最大特征值有界时，在任何有界度的n-顶点图上显示O（nlogn）混合时间。作为结果的应用，对于逸度为λ的独立集上的硬核模型，当λ α Δ（其中α ≤ 1.763）时，我们建立了任意最大度为Δ的n点图上Glauber动力学的O（nlogn）混合时间，以及任意有界度m边图的随机匹配的O（mlogn）混合时间.我们的方法基于两个步骤。首先，我们证明了熵的近似张量化（即，将熵分解为单顶点），这是许多文献中建立修正的log-Sobolev不等式的关键步骤。其次，我们采用Alev和Lau（2020）的局部到全局方案，在满足局部谱展开的纯加权单纯复形的更一般设置中建立熵的块分解;这也基本上推广了Cryan等人的结果。
We prove an optimal mixing time bound for the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved version of the spectral independence approach of Anari et al. (2020) and shows O(nlogn) mixing time on any n-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. As an application of our results, for the hard-core model on independent sets weighted by a fugacity λ, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree Δ when λ α Δ where α ≈ 1.763, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges. Our approach is based on two steps. First, we show that the approximate tensorization of entropy (i.e., factorizing entropy into single vertices), which is a key step for establishing the modified log-Sobolev inequality in many previous works, can be deduced from entropy factorization into blocks of fixed linear size. Second, we adapt the local-to-global scheme of Alev and Lau (2020) to establish such block factorization of entropy in a more general setting of pure weighted simplicial complexes satisfying local spectral expansion; this also substantially generalizes the result of Cryan et al. (2019).