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

Given a Lipschitz or smooth convex function , f:K → ℝ for a bounded polytope K subseteq ℝd defined by m inequalities, we consider the problem of sampling from the log-concave distribution π(θ) propto e-f(θ) constrained to K. Interest in this problem derives from its applications to Bayesian inference and differentially private learning. Our main result is a generalization of the Dikin walk Markov chain to this setting that requires at most O((md + d L2 R2) × mdω-1) log(fracwδ)) 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 ω is the matrix-multiplication constant. Our algorithm improves on the running time of prior works for a range of parameter settings important for the aforementioned learning applications. Technically, we depart from previous Dikin walks by adding a "soft-threshold" regularizer derived from the Lipschitz or smoothness properties of f to the log-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.