Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast
share
The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to 1971 [Turchin1971]. In each step, we pick a random coordinate and re-sample that coordinate from the distribution induced by fixing all other coordinates. While it has become widely used over the past half-century, guarantees of efficient convergence have been elusive. Here we show that for convex bodies in ℝ^n with diameter D, the resulting Coordinate Hit-and-Run (CHAR) algorithm mixes in poly(n,D) steps. This is the first polynomial guarantee for this widely-used algorithm. We also give a lower bound on the mixing rate, showing that it is strictly worse than hit-and-run or the ball walk in the worst case.
READ FULL TEXT