Poster
Sampling from Structured Log-Concave Distributions via a Soft-Threshold Dikin Walk
Oren Mangoubi · Nisheeth K. Vishnoi
Great Hall & Hall B1+B2 (level 1) #1216
Abstract:
Given a Lipschitz or smooth convex function for a bounded polytope { }, where and , we consider the problem of sampling from the log-concave distribution constrained to . 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 arithmetic operations to sample from within error in the total variation distance from a -warm start. Here is the Lipschitz constant of , is contained in a ball of radius and contains a ball of smaller radius , and 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 to a barrier function for that allows our version of the Dikin walk to propose updates that have a high Metropolis acceptance ratio for , while at the same time remaining inside the polytope .
Chat is not available.