Sampling from Log-Concave Distributions with Infinity-Distance Guarantees. (arXiv:2111.04089v3 [cs.DS] UPDATED)

For a $d$-dimensional log-concave distribution $\pi(\theta) \propto
e^{-f(\theta)}$ constrained to a convex body $K$, the problem of outputting
samples from a distribution $\nu$ which is $\varepsilon$-close in
infinity-distance $\sup_{\theta \in K} |\log \frac{\nu(\theta)}{\pi(\theta)}|$
to $\pi$ arises in differentially private optimization. While sampling within
total-variation distance $\varepsilon$ of $\pi$ can be done by algorithms whose
runtime depends polylogarithmically on $\frac{1}{\varepsilon}$, prior
algorithms for sampling in $\varepsilon$ infinity distance have runtime bounds
that depend polynomially on $\frac{1}{\varepsilon}$. We bridge this gap by …

distributions infinity log