Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling

本文解决了从可能是非对数凹和多峰的未归一化密度中进行采样的问题。为了增强简单马尔可夫链蒙特卡罗（MCMC）方法的性能，已经广泛使用了退火类型的技术。然而，这些技术的定量理论保证尚未得到充分探索。本研究首次为退火MCMC提供了一个非渐近分析。具体而言，我们建立了一个$\widetilde{O}\left(\frac{d\beta^2{\cal A}^2}{\varepsilon^6}\right)$的预测复杂度，以便简单的退火 Langevin Monte Carlo 算法在 $\mathbb{R}^d$ 上实现对目标分布 $\pi\propto{\rm e}^{-V}$ 的 Kullback-Leibler 散度达到 $\varepsilon^2$ 的精度，其中 $\beta$-平滑势能 $V$。这里，${\cal A}$ 表示概率测度曲线的作用，该曲线插值了目标分布 $\pi$ 和一个易于采样的分布。

研究如何从非对数凹的多峰非标准化密度中采样，提高简单马尔科夫链蒙特卡罗（MCMC）方法的性能，同时探索这些技术的量化理论保证。

使用简单的退火Langevin蒙特卡罗算法，建立了第一次的oracle复杂度，以实现对目标分布的Kullback-Leibler散度的ε^2精度。

提出了一种新的退火Langevin蒙特卡罗算法，建立了其oracle复杂度，证明了其在非对数凹的多峰非标准化密度中采样的有效性。实验结果表明，该算法在不同的数据集上都表现出了良好的性能，具有广泛的应用前景。

在退火MCMC方法的研究中，已经有许多相关研究，如Parallel Tempering, Simulated Annealing, Hybrid Monte Carlo等。