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:
\mathbb{R}^d \rightarrow \mathbb{R}$, 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 $\epsilon$. 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 \log^3\frac{\kappa d}{\epsilon})$, 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) = \frac{1}{n}\sum_{i \in [n]} f_i(x)$
has condition number $\kappa$, we give a sampler querying $\widetilde{O}(n +
\kappa\max(d, \sqrt{nd}))$ gradient oracles to $\{f_i\}_{i \in [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 \log^2\frac{\kappa d}{\epsilon})$,
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.
