论文标题
Gibbs采样的收敛：坐标快速混合速度混合
Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast
论文作者
论文摘要
Gibbs采样器是采样高维分布的一般方法，可追溯到Turchin，1971。在Gibbs Sampler的每个步骤中，我们选择一个随机坐标和重新样本，该坐标和样本通过固定所有其他坐标引起的分布进行协调。尽管它在过去半个世纪中已被广泛使用，但有效收敛的保证仍然难以捉摸。我们表明，对于$ \ mathbb {r}^{n} $，带直径$ d $的凸件$ k $，$ k $上的坐标命中率（char）算法的混合时间是$ n $和$ d $的多项式。我们还对char的电导率进行了下限，这表明它严格比命中率差或最坏情况下的球行走更糟。
The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to 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 $\mathbb{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.
