标题： 多项式时间采样尽管存在无序混沌 显示英文标题

标题： Polynomial-time sampling despite disorder chaos

摘要： 在抽样问题的实例上的一种分布被称为表现出传输无序混沌，如果对实例施加少量随机噪声会显著改变平稳分布（在Wasserstein距离下）。 为了提供一些抽样任务在平均情况下是困难的证据，最近的一系列工作表明，无序混沌足以排除“稳定”的抽样算法，例如梯度方法和某些扩散过程。 我们证明无序混沌并不排除在规范模型中的规范算法进行多项式时间抽样。 我们显示，在随机图$\boldsymbol{G} \sim G(n,1/2)$上高概率地满足以下条件：(1) 在 fugacity$\lambda = 1$下，$\boldsymbol{G}$上的hardcore模型表现出无序混沌，以及(2) Glauber动力学运行$O(n)$时间可以在 Wasserstein 距离下近似从$\boldsymbol{G}$上的 hardcore 模型中采样。 显示英文摘要

摘要： A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out "stable" sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph $\boldsymbol{G} \sim G(n,1/2)$: (1) the hardcore model (at fugacity $\lambda = 1$) on $\boldsymbol{G}$ exhibits disorder chaos, and (2) Glauber dynamics run for $O(n)$ time can approximately sample from the hardcore model on $\boldsymbol{G}$ (in Wasserstein distance).