2021/11/07 by Oren Mangoubi, Mangoubi, Oren, Nisheeth K. Vishnoi +1
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2111.04089
openalex publication_date 2021/11/07 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
For a d-dimensional log-concave distribution π(θ) ∝ e-f(θ) constrained to a convex body K, the problem of outputting samples from a distribution ν which is ε-close in infinity-distance supθ∈ K |log (ν(θ))/(π(θ))| to π arises in differentially private optimization. While sampling within total-variation distance ε of π can be done by algorithms whose runtime depends polylogarithmically on (1)/(ε), prior algorithms for sampling in ε infinity distance have runtime bounds that depend polynomially on (1)/(ε). We bridge this gap by presenting an algorithm that outputs a point ε-close to π in infinity distance that requires at most poly(log (1)/(ε), 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 (1)/(ε2)-discretization of K to achieve a sample with ε 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 ε, by plugging in TV-distance running time bounds for the Dikin Walk Markov chain.