Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal $O(n \log n)$ sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using $L^p$-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS'13). The non-linearity of $L^p$-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the $L^p$-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph $G(n,d/n)$, where the previously known algorithms run in time $n^{O(\log d)}$ or applied only to large $d$. We refine these algorithmic bounds significantly, and develop fast $n^{1+o(1)}$ algorithms based on Glauber dynamics that apply to all $d$, throughout the uniqueness regime.
翻译:光谱独立是最近为获得古典Glauber动态趋同时间的清晰度而开发的一个框架。 这个新框架在所谓的独特性体系中为一大批问题,包括,例如,采样独立数据集、匹配和Ising 模型配置等问题,在封闭度图形中产生了最佳的美元(n log n)的抽样算法。 我们的主要贡献是放松迄今在建立和应用光谱独立方面一直很重要的受约束度假设。 以往避免度约束的方法依赖于使用$( $)- 诺姆来分析带有约束性连接常数的图表的收缩( 硅、 Srivastava、 Yin; FOCS'13)。 $( p) 的无线性是将这些结果应用于约束光谱独立度配置的问题。 我们的解决方案是通过对用于分析再次收缩的子树进行重现的美元( $) 。 我们的方法概括了先前的分析, 仅用于在以约束性图表中进行约束性精确度的 美元 。