The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to 1971 Turchin1971%DIFDELCMD < ]%%% . 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 R^{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.
The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to %DIFDELCMD < ]%%% Turchin, 1971. In each step of the Gibbs Sampler , 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. We show that for a convex body K in R^{n} with diameter D, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on K is polynomial in n and D. We also give a lower bound on the conductance of CHAR , showing that it is strictly worse than hit-and-run or the ball walk in the worst case.
D
1971
D
Turchin1971
R
.
Turchin, 1971.
A
of the Gibbs Sampler
R
Here we
We
R
convex bodies
a convex body K
R
resulting
mixing time of the
R
mixes in poly(n ,D) steps. This is the first polynomial guarantee for this widely-used algorithm.
on K is polynomial in n and D.
R
mixing rate
conductance of CHAR