A proximal gradient algorithm for composite log-concave sampling

Abstract

We propose an algorithm to sample from composite log-concave distributions over ${\mathbb{R}}^d$, i.e., densities of the form $\ddot{I}€\propto e^{-f-g}$, assuming access to gradient evaluations of $f$ and a restricted Gaussian oracle (RGO) for $g$. The latter requirement means that we can easily sample from the density ${\text{RGO}}_{g,h,y}(x)\propto \exp (-g(x)-\frac{1}{2h}||y-x|{|}^2)$, which is the sampling analogue of the proximal operator for $g$. If $f+g$ is $\hat{I}\pm$-strongly convex and $f$ is ${\hat{I}}^2$-smooth, our sampler achieves $\epsilon$ error in total variation distance in $\tilde{\mathcal{O}}(\hat{I}º\sqrt{d}{\log }^4(1/\epsilon ))$ iterations where $\hat{I}º:={\hat{I}}^2/\hat{I}\pm$, which matches prior state-of-the-art results for the case $g=0$. We further extend our results to cases where (1) $\ddot{I}€$ is non-log-concave but satisfies a Poincaré or log-Sobolev inequality, and (2) $f$ is non-smooth but Lipschitz.