2021/10/09 by Jiaming Liang, Yongxin Chen, Liang, Jiaming +1 · 3 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Statistical Methods and Inference #cs.LG #math.OC
paper · pdf · doi:10.48550/arxiv.2110.04597
20 pages
openalex publication_date 2021/10/09 · arxiv created 2022/02/10 · arxiv updated 2022/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we examine sampling problems with non-smooth potentials. We propose a novel Markov chain Monte Carlo algorithm for sampling from non-smooth potentials. We provide a non-asymptotical analysis of our algorithm and establish a polynomial-time complexity \cal O(dε-1) to obtain ε total variation distance to the target density, better than most existing results under the same assumptions. Our method is based on the proximal bundle method and an alternating sampling framework. This 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.