Sampling from Structured Log Concave Distributions via a Soft Threshold Walk

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.