An Efficient Sampling Algorithm for Non-smooth Composite Potentials

We consider the problem of sampling from a density of the form p(x) ? exp(-f (x) - g(x)), where f : Rd-+ R is a smooth function and g : R-d-+ R is a convex and Lipschitz function. We propose a new algorithm based on the Metropolis-Hastings framework. Under certain isoperimetric inequalities on the target density, we prove that the algorithm mixes to within total variation (TV) distance e of the target density in at most O(d log(d/e)) 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. Simulation results on posterior sampling problems that arise from the Bayesian Lasso show empirical advantage over previous proposal distributions.