Rapid mixing of Gibbs sampling on graphs that are sparse on average
Rapid mixing of Gibbs sampling on graphs that are sparse on average
复制标题
在平均稀疏的图上快速混合吉布斯采样
DOI：
10.1002/rsa.v35:2
复制
发表时间：
2009
影响因子：
1
通讯作者：
Allan Sly
中科院分区：
文献类型：
--
作者：
Elchanan Mossel;Allan Sly
Gibbs抽样，也称为Glauber动力学，是一种流行的技术，用于对图上定义的高维分布进行抽样。特别值得关注的是Erdos-Renyi随机图G(n，d-n)上Gibbs抽样的行为，其中每条边以概率d-n独立选择，且d是固定的。当G(n，d-n)中的平均度为d(1-o(1))时，G(n，d-n)中含有许多阶为logn-loglogn的结点。
几乎对数度节点的存在意味着，对于定义在G(n，p)上的许多自然分布，如均匀着色(颜色数目不变)或Ising模型，在任何固定的逆温度β下，Gibbs抽样的混合时间至少为N1+Ω(1-logn)。回想一下，在图G=(V，E)上定义的具有逆温度β的伊辛模型是由$P(\sigma)={1\over Z}\exp(\β\sigma_{(v，u)\varepsilon E}\\sigma(V)\sigma(U))$给出的L±rV上的分布。对于包括Ising模型和着色在内的许多模型，在证明动力学的多项式时间混合方面，高次节点是一个技术挑战。几乎所有已知的关于吉布斯采样器快速混合所需的β或颜色数量的充分条件都是以基础图的最大度来表示的。
在这项工作中，我们证明了对于任意的d0，使得对于所有的β1，其中模型的参数不依赖于n.它们还提供了一个罕见的例子，在实际混合时间比nPolylog(N)慢的情况下，可以证明Gibbs采样器的多项式时间混合.我们的证明以新颖的方式利用了Erdos-Renyi随机图的局部树状结构、比较和区块动力学论点以及Weitz最近的一个结果。
我们的结果推广到更一般的图族，它们在某种平均意义上是稀疏的，以及更一般的相互作用。特别地，它们适用于图的每个顶点v都有半径为O(Logn)的邻域N(V)的任何图，其中导出子图至多为O(Logn)条边的树并，且对于N(V)中的每条简单路，沿该路的顶点度之和为O(Logn)。此外，我们的结果也适用于任意外场的情况，并首次提供了在这种情况下抽样伊辛分布的FPRAS。最后，我们给出了一种非马尔可夫链抽样算法，该算法对更大范围的参数有效。特别地，对于G(n，d-n)，它适用于所有外场和β<；βd，其中d tanh(βd)=1是G(n，d-n)上伊辛模型关联衰减的临界点。©2009威利期刊公司随机结构。高，2009年
Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erdos-Renyi random graph G(n,d-n), where each edge is chosen independently with probability d-n and d is fixed. While the average degree in G(n,d-n) is d(1 - o(1)), it contains many nodes of degree of order log n-log log n.
The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n1+Ω(1-log log n). Recall that the Ising model with inverse temperature β defined on a graph G = (V,E) is the distribution over l±rVgiven by $ P(\sigma) = {1 \over Z} \exp (\beta \Sigma_{(v,u)\varepsilon E}\ \sigma(v)\sigma(u)) $. High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of β or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph.
In this work, we show that for every d 0, such that for all β 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erdos-Renyi random graphs, comparison and block dynamics arguments and a recent result of Weitz.
Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub-graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d-n) it applies for all external fields and β < βd, where d tanh(βd) = 1 is the critical point for decay of correlation for the Ising model on G(n, d-n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009