Metastable mixing of Markov chains: Efficiently sampling low temperature exponential random graphs
Metastable mixing of Markov chains: Efficiently sampling low temperature exponential random graphs
复制标题
DOI：
10.1214/23-aap1971
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Guy Bresler;Dheeraj M. Nagaraj;Eshaan Nichani
中科院分区：
文献类型：
--
作者：
Guy Bresler;Dheeraj M. Nagaraj;Eshaan Nichani
本文研究了低温指数随机图模型（ERGM）的抽样问题。通常的方法是通过马尔可夫链蒙特卡罗，但Bhamidi等人表明，由于亚稳态的存在，任何局部马尔可夫链的混合时间都是指数级的。我们转而考虑亚稳态混合，这是一种相对于平稳分布的近似混合的概念，对于它来说，只在一组亚稳态中混合就足够了。我们表明，在任何温度下（除了低维临界参数集），当在$G(n,p)$初始化并正确选择$p$时，ERGM的Glauber动力学具有从$O(n^2\log n)$到总变化距离$\exp(-\Omega(n))$的亚稳混合时间。
In this paper we consider the problem of sampling from the low-temperature exponential random graph model (ERGM). The usual approach is via Markov chain Monte Carlo, but Bhamidi et al. showed that any local Markov chain suffers from an exponentially large mixing time due to metastable states. We instead consider metastable mixing, a notion of approximate mixing relative to the stationary distribution, for which it turns out to suffice to mix only within a collection of metastable states. We show that the Glauber dynamics for the ERGM at any temperature -- except at a lower-dimensional critical set of parameters -- when initialized at $G(n,p)$ for the right choice of $p$ has a metastable mixing time of $O(n^2\log n)$ to within total variation distance $\exp(-\Omega(n))$.