On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs
On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs
复制标题
DOI：
10.4230/lipics.icalp.2022.57
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Charilaos Efthymiou
中科院分区：
文献类型：
--
作者：
Charilaos Efthymiou
我们考虑了稀疏随机(超)图上对称Gibbs分布近似抽样的有效算法。这里我们考虑的例子包括(但不限于)在自旋系统和自旋玻璃上的重要分布，例如$qqq2$的q态反铁磁Potts模型，包括随机着色，随机k-CNF公式的非全等解上的均匀分布。最后，我们提出了一种从自旋玻璃分布中采样的算法，称为k自旋模型。据我们所知，这是第一个经过严格分析的高效自旋玻璃算法，它在参数的非平凡范围内运行。我们的方法依赖于[Efthy miou：Soda 2012]中引入的方法。对于参数在一定范围内的随机(超)图上的对称Gibbs分布$\Mu$，我们的算法具有如下性质：以输入实例上的概率$1-o(1)$生成一个分布在从$\Mu$开始的总变化距离$n^{-\Omega(1)}$内的构形.时间复杂度为$O(n^{2}\logn)$。显然，该算法需要与树唯一性区域一致的分布参数的范围，参数化为W.r.t。更准确地说，对于已知唯一性区域的分布来说，这是正确的。对于我们考虑的许多分布，我们远未确定它们的独特区域。这对我们的目的施加了一定的限制。我们建立了一种新的方法，它利用了吉布斯分布和所谓的教师-学生模型之间的邻接性概念。通过这种方法，我们将抽样和统计推理算法中的工具和概念结合在一起。
We consider efficient algorithms for approximate sampling from symmetric Gibbs distributions on the sparse random (hyper)graph. The examples we consider here include (but are not restricted to) important distributions on spin systems and spin-glasses such as the q state antiferromagnetic Potts model for $q\geq 2$, including the random colourings, the uniform distributions over the Not-All-Equal solutions of random k-CNF formulas. Finally, we present an algorithm for sampling from the spin-glass distribution called the k-spin model. To our knowledge this is the first, rigorously analysed, efficient algorithm for spin-glasses which operates in a non trivial range of the parameters. Our approach relies on the one that was introduced in [Efthymiou: SODA 2012]. For a symmetric Gibbs distribution $\mu$ on a random (hyper)graph whose parameters are within an certain range, our algorithm has the following properties: with probability $1-o(1)$ over the input instances, it generates a configuration which is distributed within total variation distance $n^{-\Omega(1)}$ from $\mu$. The time complexity is $O(n^{2}\log n)$. It is evident that the algorithm requires a range of the parameters of the distributions that coincide with the tree-uniqueness region, parametrised w.r.t. the expected degree d. More precisely, this is true for distributions for which the uniqueness region is known. For many of the distributions we consider, we are far from establishing what is believed to be their uniqueness region. This imposes certain limitations to our purposes. We build a novel approach which utilises the notion of contiguity between Gibbs distributions and the so-called teacher-student model. With this approach we bring together tools and notions from sampling and statistical inference algorithms.