Skip to yearly menu bar Skip to main content


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
[ ]
[ Paper [ Poster [ OpenReview
Wed 11 Dec 11 a.m. PST — 2 p.m. PST

Abstract: We consider the problem of sampling from a d-dimensional log-concave distribution π(θ)exp(f(θ)) for L-Lipschitz f, constrained to a convex body (described by n hyperplanes) equipped with a barrier function, contained in a ball of radius R with a w-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 O~((d2+dL2R2)log(w/δ)) steps with a per step cost of O~(ndω1), where ω2.37 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 d-dimensional spectrahedron, the constrained set of a semidefinite program, specified by the set {xRd:i=1dxiAiC} where A1,,Ad,C are n×n real symmetric matrices. We design a walk that mixes in O~((nd+dL2R2)log(w/δ)) steps with a per iteration cost of O~(nω+n2d3ω5). We improve the mixing time bound of prior best Dikin walk due to Narayanan and Rakhlin that mixes in O~((n2d3+n2dL2R2)log(w/δ)) steps.

Chat is not available.