Sampling from Structured Log-Concave Distributions via a Soft-Threshold Dikin Walk

Given a Lipschitz or smooth convex function f : K → R d for a bounded polytope K := θ ∈ R d : Aθ ≤ b , where A ∈ R m × d and b ∈ R m , we consider the problem of sampling from the log-concave distribution π ( θ ) ∝ e − f ( θ ) constrained to K . Interest in this problem derives from its applications to Bayesian inference and differential privacy. We present a generalization of the Dikin walk to this setting that requires at most O (( md + dL 2 R 2 ) × md ω − 1 log( wδ )) arithmetic operations to sample from π within error δ > 0 in the total variation distance from a w -warm start. Here L is the Lipschitz constant of f , K is contained in a ball of radius R and contains a ball of smaller radius r , and ω ≈ 2 . 37 is the matrix-multiplication constant. This improves on the running time of prior works for a range of structured settings important for the aforementioned inference and privacy applications. Technically, we depart from previous Dikin walks by adding a soft-threshold regularizer derived from the Lipschitz or smoothness properties of f to a barrier function for K that allows our version of the Dikin walk to propose updates that have a high Metropolis acceptance ratio for f , while at the same time remaining inside the polytope K .