Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much
This addresses a theoretical gap for practitioners in statistics and machine learning who rely on systematic scan for efficiency, though it is incremental in refining existing bounds.
The paper tackled the problem of comparing mixing times between random and systematic scan orders in Gibbs sampling, showing by counterexample that they can differ by more than a logarithmic factor and proving a polynomial bound under mild conditions.
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.