Sampling from Log-Concave Distributions with Infinity-Distance Guarantees

For a d-dimensional log-concave distribution π(θ) propto e-f(θ) constrained to a convex body K, the problem of outputting samples from a distribution nu which is varepsilon-close in infinity-distance supθ ∈ K |log fracnu(θ)π(θ)| to π arises in differentially private optimization. While sampling within total-variation distance varepsilon of π can be done by algorithms whose runtime depends polylogarithmically on frac1varepsilon, prior algorithms for sampling in varepsilon infinity distance have runtime bounds that depend polynomially on frac1varepsilon. We bridge this gap by presenting an algorithm that outputs a point varepsilon-close to π in infinity distance that requires at most poly(log frac1varepsilon, d) calls to a membership oracle for K and evaluation oracle for f, when f is Lipschitz. Our approach departs from prior works that construct Markov chains on a frac1varepsilon2-discretization of K to achieve a sample with varepsilon infinity-distance error, and present a method to directly convert continuous samples from K with total-variation bounds to samples with infinity bounds. This approach also allows us to obtain an improvement on the dimension d in the running time for the problem of sampling from a log-concave distribution on polytopes K with infinity distance varepsilon, by plugging in TV-distance running time bounds for the Dikin Walk Markov chain.