Poster
Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
Yuzhou Gu · Nikki Lijing Kuang · Yian Ma · Zhao Song · Lichen Zhang
East Exhibit Hall A-C #4203
Abstract:
We consider the problem of sampling from a -dimensional log-concave distribution for -Lipschitz , constrained to a convex body (described by hyperplanes) equipped with a barrier function, contained in a ball of radius with a -warm start. We propose a \emph{robust} sampling framework that computes spectral approximations to the Hessian of the barrier functions in each iteration. We prove that for the polytope constraints, sampling with the Lee-Sidford barrier function mixes within steps with a per step cost of , where is the fast matrix multiplication exponent. Compared to the prior work of Mangoubi and Vishnoi, our approach gives faster mixing time as we are able to design a generalized soft-threshold Dikin walk beyond log-barrier.We further extend our result to show how to sample from a -dimensional spectrahedron, the constrained set of a semidefinite program, specified by the set where are real symmetric matrices. We design a walk that mixes in steps with a per iteration cost of . We improve the mixing time bound of prior best Dikin walk due to Narayanan and Rakhlin that mixes in steps.
Chat is not available.