提出一种新型采样算法，三阶收敛且在高维下更高效。
Underdamped Langevin MCMC with third order convergence
- 基于梯度信息设计新数值方法，提升采样精度
- 三阶光滑条件下，迭代次数仅需 $\mathcal{O}(\sqrt{d}/\varepsilon^{1/3})$
- 适合高维强对数凹分布的高效贝叶斯采样
本文提出一种新的无阻尼朗之万扩散（ULD）数值方法，并在目标分布 $p(x)\propto e^{-f(x)}$ 强对数凹且具有不同光滑性条件下，对其在 2-瓦瑟斯坦距离下的采样误差进行了非渐近分析。当 $f$ 的梯度与海森矩阵满足 Lipschitz 连续时，算法达到 $\mathcal{O}(\sqrt{d}/\varepsilon)$ 和 $\mathcal{O}(\sqrt{d}/\sqrt{\varepsilon})$ 步内误差 $\varepsilon$。若额外假设 $f$ 的三阶导数 Lipschitz 连续，则可实现 $\mathcal{O}(\sqrt{d}/\varepsilon^{1/3})$ 步内的误差控制。这是首个在仅使用梯度信息下实现三阶收敛的 ULD 方法。实验在多个真实数据集上的贝叶斯逻辑回归中验证了其性能，优于现有无阻尼朗之万方法并媲美 NUTS。
原文摘要 · Abstract (English)
In this paper, we propose a new numerical method for the underdamped Langevin diffusion (ULD) and present a non-asymptotic analysis of its sampling error in the 2-Wasserstein distance when the $d$-dimensional target distribution $p(x)\propto e^{-f(x)}$ is strongly log-concave and has varying degrees of smoothness. Precisely, under the assumptions that the gradient and Hessian of $f$ are Lipschitz continuous, our algorithm achieves a 2-Wasserstein error of $\varepsilon$ in $\mathcal{O}(\sqrt{d}/\varepsilon)$ and $\mathcal{O}(\sqrt{d}/\sqrt{\varepsilon})$ steps respectively. Therefore, our algorithm has a similar complexity as other popular Langevin MCMC algorithms under matching assumptions. However, if we additionally assume that the third derivative of $f$ is Lipschitz continuous, then our algorithm achieves a 2-Wasserstein error of $\varepsilon$ in $\mathcal{O}(\sqrt{d}/\varepsilon^{\frac{1}{3}})$ steps. To the best of our knowledge, this is the first gradient-only method for ULD with third order convergence. To support our theory, we perform Bayesian logistic regression across a range of real-world datasets, where our algorithm achieves competitive performance compared to an existing underdamped Langevin MCMC algorithm and the popular No U-Turn Sampler (NUTS).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。