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é

Introduction

Gibbs sampling is a workhorse of Bayesian inference, widely used to sample from complex multivariate distributions by iteratively updating one variable at a time from its conditional distribution. When implementing a Gibbs sampler, practitioners face a fundamental choice: Random Scan (picking a variable at random to update at each step) or Systematic Scan (updating variables in a fixed, repeating order).

From a hardware and systems perspective, systematic scan is the clear winner. It offers vastly superior data locality, cache efficiency, and faster execution times. However, the theoretical landscape tells a different story: most statistical guarantees and convergence proofs only exist for random scan. For decades, a long-standing conjecture suggested that the "mixing time"—the number of iterations required to draw an accurate sample—for these two methods differed by no more than a constant or logarithmic factor. If true, the choice of scan order wouldn't significantly impact statistical efficiency, allowing practitioners to freely enjoy the hardware benefits of systematic scan.

This paper shatters that conventional wisdom. By providing explicit counterexamples, the authors demonstrate that the choice of scan order can change mixing time by a polynomial factor. Furthermore, they provide the first rigorous theoretical bounds that prevent this gap from being infinitely large.

Methods and Synthetic Models

Analyzing systematic scan is notoriously difficult because, unlike random scan, it lacks "reversibility"—a mathematical property that drastically simplifies Markov chain proofs. To overcome this, the authors introduce a novel theoretical technique: state space augmentation. By including the index of the next variable to be sampled as part of the state itself, they transform the systematic scan into a homogeneous Markov chain. This allows them to analyze the chain using conductance, a measure of how easily a Markov chain moves around its state space.

Because this is a theoretical exploration, the authors rely on carefully constructed synthetic models rather than standard real-world datasets. These models are designed to expose the vulnerabilities and strengths of different scan orders:

The three synthetic models used to evaluate scan orders: Sequence of Dependencies, Two Islands, and Discrete Pyramid.
  1. Sequence of Dependencies: A model where variables must be updated in a specific directional order to efficiently propagate information and make progress.
  2. Two Islands: A model featuring two dense clusters of states connected by a narrow "bridge." Certain update orders can easily get "stuck" on one island.
  3. Discrete Pyramid: A baseline model previously introduced in literature, used here for comparative analysis.

Key Insights and Results

The core finding of the paper is that the long-held conjecture is false: the difference in mixing times between random and systematic scan can be polynomial, not just logarithmic. This implies that in large-scale models, the choice of scan order can have a massive impact on overall performance.

Empirical mixing times for the three models, illustrating the polynomial gaps between random and systematic scan orders.

The empirical simulations and theoretical bounds reveal a two-sided story:

  • Systematic Can Be Much Faster: In the Sequence of Dependencies model, a "good" systematic scan follows the natural flow of information. The authors show that the best systematic scan achieves a mixing time of $O(n)$, making it $n$ times faster than a random scan, which takes $O(n^2)$.
  • "Bad Permutations" Can Be Devastating: Conversely, the Two Islands model demonstrates the danger of a poor scan order. A "bad" systematic scan can be $n/2$ times slower than a random scan. This phenomenon mirrors findings in Stochastic Gradient Descent (SGD), where the specific sequence of data points heavily influences convergence.

Despite these wide variations, the authors provide a "polynomial safety net." Their core theoretical contribution (Theorem 1) proves that under mild conditions, the mixing time of a lazy systematic scan is bounded by the square of the random scan's mixing time, multiplied by factors related to the number of variables and the least likely state. The gap is larger than previously thought, but it is strictly bounded.

Limitations and Future Work

While this paper makes significant theoretical strides, a few limitations remain:

  • Lazy Scans: The theoretical bounds are proven for "lazy" versions of the samplers (where the chain has a 50% chance of staying in its current state at any step). While standard for mathematical proofs, practitioners rarely use lazy samplers in production.
  • Dependence on $\pi_{min}$: The theoretical bounds rely on the probability of the least likely state ($\pi_{min}$). In complex models with many variables, this value can be exponentially small, potentially making the bounds quite loose in practice.
  • Finding the Optimal Order: The paper provides a robust framework for analyzing scan orders and proves that optimal permutations exist. However, discovering that "optimal" permutation for an arbitrary, complex real-world graphical model remains an open challenge for future research.

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