Structured Logconcave Sampling with a Restricted Gaussian Oracle

We give algorithms for sampling several structured logconcave families to high accuracy. We further develop a reduction framework, inspired by proximal point methods in convex optimization, which bootstraps samplers for regularized densities to improve dependences on problem conditioning. A key ingredient in our framework is the notion of a "restricted Gaussian oracle" (RGO) for g: ℝd rightarrow ℝ, which is a sampler for distributions whose negative log-likelihood sums a quadratic and g. By combining our reduction framework with our new samplers, we obtain the following bounds for sampling structured distributions to total variation distance ε. For composite densities exp(-f(x) - g(x)), where f has condition number kappa and convex (but possibly non-smooth) g admits an RGO, we obtain a mixing time of O(kappa d log3frackappa dε), matching the state-of-the-art non-composite bound; no composite samplers with better mixing than general-purpose logconcave samplers were previously known. For logconcave finite sums exp(-F(x)), where F(x) = frac1nsumi ∈ [n] fi(x) has condition number kappa, we give a sampler querying widetildeO(n + kappamax(d, √nd)) gradient oracles to fii ∈ [n]; no high-accuracy samplers with nontrivial gradient query complexity were previously known. For densities with condition number kappa, we give an algorithm obtaining mixing time O(kappa d log2frackappa dε), improving the prior state-of-the-art by a logarithmic factor with a significantly simpler analysis; we also show a zeroth-order algorithm attains the same query complexity.