Entropic independence: optimal mixing of down-up random walks
Entropic independence: optimal mixing of down-up random walks
复制标题
DOI：
10.1145/3519935.3520048
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Nima Anari;Vishesh Jain;Frederic Koehler;H. Pham;T. Vuong
中科院分区：
文献类型：
--
作者：
Nima Anari;Vishesh Jain;Frederic Koehler;H. Pham;T. Vuong
我们引入了一个称为熵独立性的通知，该通知是高维膨胀的光谱概念的熵类似物。集合S，S的单个元素的相对熵在随机携带的最多o（1/k）的相对熵S.熵独立性的相对熵的比例均匀绘制是光谱独立性概念的类似物，如果一个人通过通过熵。 Sobolev的不等式，对于频谱通知，我们表明，在任意外部领域下的分布的光谱独立性意味着熵独立性这样做，我们介绍了一个框架，以根据我们所说的限制修改的Log-Sobolev不等式获得Markov链的紧密混合时间边界，该框架保证并非所有分布，而是针对足够大的固定分布中的那些分布的熵收缩。为了获得我们的结果，我们将熵独立性与多项式的性质相关联：µ是熵的，当µ的生成多项式的转换版本上的上限是由其线性切线的上限；通过先前的工作表现为局部等同于光谱独立性。在ISING模型上使用o（nlogn）的o（nlogn）的混合时间，其相互作用矩阵的特征光谱位于长度小于1的间隔内，从而改善了先前对n的二次依赖性，（3）几乎是线性时间oδ（n）样品对于具有δ相关间隙的N节点图上的硬核和ISING模型，在最后一个应用中，我们对运行时间的界限不取决于图形的最大程度δ即使对于高度图，甚至对于高度图的图形大小，最佳的图形也是sublinear。
We introduce a notion called entropic independence that is an entropic analog of spectral notions of high-dimensional expansion. Informally, entropic independence of a background distribution µ on k-sized subsets of a ground set of elements says that for any (possibly randomly chosen) set S, the relative entropy of a single element of S drawn uniformly at random carries at most O(1/k) fraction of the relative entropy of S. Entropic independence is the analog of the notion of spectral independence, if one replaces variance by entropy. We use entropic independence to derive tight mixing time bounds, overcoming the lossy nature of spectral analysis of Markov chains on exponential-sized state spaces. In our main technical result, we show a general way of deriving entropy contraction, a.k.a. modified log-Sobolev inequalities, for down-up random walks from spectral notions. We show that spectral independence of a distribution under arbitrary external fields automatically implies entropic independence. We furthermore extend our theory to the case where spectral independence does not hold under arbitrary external fields. To do this, we introduce a framework for obtaining tight mixing time bounds for Markov chains based on what we call restricted modified log-Sobolev inequalities, which guarantee entropy contraction not for all distributions, but for those in a sufficiently large neighborhood of the stationary distribution. To derive our results, we relate entropic independence to properties of polynomials: µ is entropically independent exactly when a transformed version of the generating polynomial of µ is upper bounded by its linear tangent; this property is implied by concavity of the said transformation, which was shown by prior work to be locally equivalent to spectral independence. We apply our results to obtain (1) tight modified log-Sobolev inequalities and mixing times for multi-step down-up walks on fractionally log-concave distributions, (2) the tight mixing time of O(nlogn) for Glauber dynamics on Ising models whose interaction matrix has eigenspectrum lying within an interval of length smaller than 1, improving upon the prior quadratic dependence on n, and (3) nearly-linear time Oδ(n) samplers for the hardcore and Ising models on n-node graphs that have δ-relative gap to the tree-uniqueness threshold. In the last application, our bound on the running time does not depend on the maximum degree Δ of the graph, and is therefore optimal even for high-degree graphs, and in fact, is sublinear in the size of the graph for high-degree graphs.