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

Abstract

Given a Lipschitz or smooth convex function \, f:K R for a bounded polytope K R^d defined by m inequalities, 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 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 L^2 R^2) md^-1) (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 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.

Tasks

Reproductions