Composite Logconcave Sampling with a Restricted Gaussian Oracle

We consider sampling from composite densities on ℝd of the form dπ(x) propto exp(-f(x) - g(x))dx for well-conditioned f and convex (but possibly non-smooth) g, a family generalizing restrictions to a convex set, through the abstraction of a restricted Gaussian oracle. For f with condition number kappa, our algorithm runs in O left(kappa2 d log2tfrackappa dεright) iterations, each querying a gradient of f and a restricted Gaussian oracle, to achieve total variation distance ε. The restricted Gaussian oracle, which draws samples from a distribution whose negative log-likelihood sums a quadratic and g, has been previously studied and is a natural extension of the proximal oracle used in composite optimization. Our algorithm is conceptually simple and obtains stronger provable guarantees and greater generality than existing methods for composite sampling. We conduct experiments showing our algorithm vastly improves upon the hit-and-run algorithm for sampling the restriction of a (non-diagonal) Gaussian to the positive orthant.