Timezone: »

 
Poster
Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much
Bryan He · Christopher M De Sa · Ioannis Mitliagkas · Christopher Ré

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #65 #None
in Tuesday Posters »

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.

Keywords: (Other) Probabilistic Models and Methods · MCMC · (Other) Statistics

Author Information

Bryan He (Stanford University)
Christopher M De Sa (Stanford University)
Ioannis Mitliagkas (Stanford)
Christopher Ré (Stanford University)

More from the Same Authors