Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk

We consider the problem of sampling from a d-dimensional log-concave distribution π(θ) propto exp(-f(θ)) for L-Lipschitz f, constrained to a convex body with an efficiently computable self-concordant barrier function, contained in a ball of radius R with a w-warm start. We propose a robust sampling framework that computes spectral approximations to the Hessian of the barrier functions in each iteration. We prove that for polytopes that are described by n hyperplanes, sampling with the Lee-Sidford barrier function mixes within widetilde O((d2+dL2R2)log(w/δ)) steps with a per step cost of widetilde 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 x∈ ℝd: sumi=1d xi Ai succeq C where A1,ldots,Ad, C are n× n real symmetric matrices. We design a walk that mixes in widetilde O((nd+dL2R2)log(w/δ)) steps with a per iteration cost of widetilde O(nω+n2d3ω-5). We improve the mixing time bound of prior best Dikin walk due to Narayanan and Rakhlin that mixes in widetilde O((n2d3+n2dL2R2)log(w/δ)) steps.