An Efficient Sampling Algorithm for Non-smooth Composite Potentials

Abstract

We consider the problem of sampling from a density of the form $p(x)\propto \exp (-f(x)-g(x))$, where $f:{\mathbb{R}}^d\to \mathbb{R}$ is a smooth and strongly convex function and $g:{\mathbb{R}}^d\to \mathbb{R}$ 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 $\epsilon$ of the target density in at most $O(d\log (d/\epsilon ))$ 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$.

References in corpus (6)

• General state space Markov chains and MCMC algorithms
• Fast simulation of truncated Gaussian distributions
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Convergence of Langevin MCMC in KL-divergence
• Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities

Cited by in corpus (9)

• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo
• Composite Logconcave Sampling with a Restricted Gaussian Oracle
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• A Proximal Algorithm for Sampling from Non-smooth Potentials
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Penalized Langevin dynamics with vanishing penalty for smooth and log-concave targets