Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much

Bryan D. He, Christopher De Sa, Ioannis Mitliagkas, Christopher Ré

Abstract: Gibbs sampling is a Markov Chain Monte Carlo sampling technique that iteratively samples variables from their conditional distributions. There are two common scan orders for the variables: random scan and systematic scan. Due to the benefits of locality in hardware, systematic scan is commonly used, even though most statistical guarantees are only for random scan. While it has been conjectured that the mixing times of random scan and systematic scan do not differ by more than a logarithmic factor, we show by counterexample that this is not the case, and we prove that that the mixing times do not differ by more than a polynomial factor under mild conditions. To prove these relative bounds, we introduce a method of augmenting the state space to study systematic scan using conductance.

Introduction

Gibbs sampling is a cornerstone of multivariate distribution sampling, operating by iteratively updating individual variables based on the current state of the rest of the system. In practice, two primary update strategies exist: Random Scan, where a variable is chosen uniformly at random, and Systematic Scan, which follows a fixed permutation (e.g., $x_1, x_2, \dots, x_n$).

While systematic scan is preferred for its hardware efficiency—leveraging spatial memory locality—theoretical guarantees often lag behind. A long-standing conjecture suggested that the "mixing time" (the time required to reach the target distribution) for these two methods would never differ by more than a factor of $\log(n)$. This research disproves that conjecture, demonstrating that the gap can be polynomial, while simultaneously providing new, rigorous polynomial bounds.

Synthetic Models and Counterexamples

To explore the limits of scan order performance, the authors developed several synthetic mathematical models designed to act as "adversarial" distributions. These models highlight how specific scan orders can either facilitate or bottleneck the sampler's progress.

The three primary synthetic models used to analyze scan order: (a) Sequence of Dependencies, (b) Two Islands, and (c) Discrete Pyramid.
  • Sequence of Dependencies: A model where progress is contingent on updates occurring in a specific linear order. Here, a "good" systematic scan can mix in $O(n)$ time, while random scan requires $O(n^2)$.
  • Two Islands: This model features two clusters of states connected by a narrow "bridge." A poorly chosen systematic scan order can cause the sampler to effectively bounce off the bridge, making it significantly slower than a random scan.
  • Discrete Pyramid: A model where random scan is known to outperform systematic scan, used here to further test the bounds of the logarithmic conjecture.

Methodology: State Space Augmentation

Analyzing systematic scan is traditionally difficult because it lacks the "reversibility" property of many Markov chains. To overcome this, the authors introduced a novel state-space augmentation technique. By including the index of the variable currently being updated as part of the state, the chain becomes easier to analyze using conductance—a standard metric for how easily a Markov chain traverses its state space. This technique allowed the authors to prove Theorem 1, establishing the first general polynomial bounds relating random and systematic scans.

Key Results and Findings

The research successfully disproved the logarithmic gap conjecture, showing that the difference in mixing times can be as large as $n$ vs $n^2$ or $n^3$.

Mixing time ($t_{mix}$) distributions across different scan orders for the Sequence of Dependencies and Two Islands models.

As shown in the experimental results, the choice of permutation in the systematic scan acts as a statistical bottleneck. In the "Two Islands" model, a "bad" permutation can be $n/2$ times slower than random scan.

Formally, the authors proved that for any distribution $\pi$, the mixing times of random scan ($R$) and a "lazy" systematic scan ($S$) are related by:

  • $t_{mix}(R) \leq O(t_{mix}(S)^2 \cdot \log(1/\pi_{min}))$
  • $t_{mix}(S) \leq O(n^2 \cdot t_{mix}(R)^2 \cdot \log(1/\pi_{min}))$

(Where $\pi_{min}$ represents the probability of the least likely state).

Conclusion and Future Work

While the proven bounds provide a safety net, they do depend on $\pi_{min}$, which can be exponentially small in high-dimensional models, potentially leading to loose bounds in practice. Furthermore, the theory relies on "lazy" samplers (which have a 50% chance of remaining in the current state), a variation rarely used by practitioners.

Despite these limitations, the state-space augmentation method opens new doors for finding "optimal" scan orders. Future work may leverage these insights to develop samplers that are both hardware-optimized and statistically superior, bridging the gap between theoretical guarantees and practical performance.

Summary updated

Abstract

Gibbs sampling is a Markov Chain Monte Carlo sampling technique that iteratively samples variables from their conditional distributions. There are two common scan orders for the variables: random scan and systematic scan. Due to the benefits of locality in hardware, systematic scan is commonly used, even though most statistical guarantees are only for random scan. While it has been conjectured that the mixing times of random scan and systematic scan do not differ by more than a logarithmic factor, we show by counterexample that this is not the case, and we prove that that the mixing times do not differ by more than a polynomial factor under mild conditions. To prove these relative bounds, we introduce a method of augmenting the state space to study systematic scan using conductance.
BibTeX
@inproceedings{he2016scan,
  author = {Bryan D. He and Christopher De Sa and Ioannis Mitliagkas and Christopher Ré},
  title = {{Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=SkZgYubO-B},
}
Figure