2019/10/01 by Wenlong Mou, Mou, Wenlong, Nicolas Flammarion +5 · 3 citations
Engineering · Mathematics · #Computation (stat.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.1910.00551
openalex publication_date 2019/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of sampling from a density of the form p(x) ∝ exp(-f(x)- g(x)), where f: ℝd → ℝ is a smooth and strongly convex function and g: ℝd → ℝ is a convex and Lipschitz function. We propose a new algorithm based on the Metropolis-Hastings framework, and prove that it mixes to within TV distance ε of the target density in at most O(d log (d/ε)) iterations. This guarantee extends previous results on sampling from distributions with smooth log densities (g = 0) to the more general composite non-smooth case, with the same mixing time up to a multiple of the condition number. Our method is based on a novel proximal-based proposal distribution that can be efficiently computed for a large class of non-smooth functions g.