A Proximal Algorithm for Sampling from Non-Smooth Potentials
A Proximal Algorithm for Sampling from Non-Smooth Potentials
复制标题
DOI：
10.1109/wsc57314.2022.10015293
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Jiaming Liang;Yongxin Chen
中科院分区：
文献类型：
--
作者：
Jiaming Liang;Yongxin Chen
在这项工作中，本文研究了非光滑位势抽样问题，提出了一种新的马尔可夫链蒙特卡罗算法，并对算法进行了非渐近性分析，建立了多项式时间复杂度$\tilde{\mathscr{O}}（M^{2}d_{4}\mathscr{M}^{1/2}_{4}\vareps ^{-1}）$，以达到$\vareps $误差，即到具有4阶矩$\mathscr{M}_{4}$和M-Lipschitz势，优于相同假设下的大多数已有结果。我们的方法是基于近端束方法和交替采样框架。后者的框架需要所谓的限制高斯预言机，它可以被看作是一个采样对应的凸优化中的邻近映射。本文的一个重要贡献是提出了一种快速算法，实现了对具有有界Lipschitz常数的凸非光滑势的约束高斯预言。
In this work, we examine sampling problems with non-smooth potentials and propose a novel Markov chain Monte Carlo algorithm for it. We provide a non-asymptotical analysis of our algorithm and establish a polynomial-time complexity $\tilde{\mathscr{O}}(M^{2}d_{4}\mathscr{M}^{1/2}_{4}\varepsilon^{-1})$ to achieve $\varepsilon$ error in terms of total variation distance to a log-concave target density with 4th moment $\mathscr{M}_{4}$ and M-Lipschitz potential, better than most existing results under the same assumptions. Our method is based on the proximal bundle method and an alternating sampling framework. The latter framework requires the so-called restricted Gaussian oracle, which can be viewed as a sampling counterpart of the proximal mapping in convex optimization. One key contribution of this work is a fast algorithm that realizes the restricted Gaussian oracle for any convex non-smooth potential with bounded Lipschitz constant.