Sampling from Log-Concave Distributions with Infinity-Distance Guarantees
This addresses a bottleneck in differentially private optimization by providing more efficient sampling methods for log-concave distributions.
The paper tackles the problem of sampling from log-concave distributions with infinity-distance guarantees, which is important for differentially private optimization, and presents an algorithm that achieves a runtime with polylogarithmic dependence on 1/ε, improving upon prior polynomial dependencies.
For a $d$-dimensional log-concave distribution $π(θ) \propto e^{-f(θ)}$ constrained to a convex body $K$, the problem of outputting samples from a distribution $ν$ which is $\varepsilon$-close in infinity-distance $\sup_{θ\in K} |\log \frac{ν(θ)}{π(θ)}|$ to $π$ arises in differentially private optimization. While sampling within total-variation distance $\varepsilon$ of $π$ 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 presenting an algorithm that outputs a point $\varepsilon$-close to $π$ in infinity distance that requires at most $\mathrm{poly}(\log \frac{1}{\varepsilon}, 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 $\frac{1}{\varepsilon^2}$-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.