Abstract
For Markov chain Monte Carlo methods, one of the greatest discrepancies between theory and system is the scan order — while most theoretical development on the mixing time analysis deals with random updates, real-world systems are implemented with systematic scans. We bridge this gap for models that exhibit a bipartite structure, including, most notably, the Restricted/Deep Boltzmann Machine. The de facto implementation for these models scans variables in a layer wise fashion. We show that the Gibbs sampler with a layer-wise alternating scan order has its relaxation time (in terms of epochs) no larger than that of a random-update Gibbs sampler (in terms of variable updates). We also construct examples to show that this bound is asymptotically tight. Through standard inequalities, our result also implies a comparison on the mixing times.
Original language | English |
---|---|
Title of host publication | 21st International Conference on Artificial Intelligence and Statistics |
Place of Publication | Playa Blanca, Lanzarote, Canary Islands |
Publisher | PMLR |
Pages | 178-187 |
Number of pages | 10 |
Volume | 84 |
Publication status | Published - 11 Apr 2018 |
Event | The 21st International Conference on Artificial Intelligence and Statistics - Playa Blanca, Lanzarote, Canary Islands, Lanzarote, Spain Duration: 9 Apr 2018 → 11 Apr 2018 Conference number: 21 http://www.aistats.org/ |
Publication series
Name | Proceedings of Machine Learning Research |
---|---|
Publisher | PMLR |
Volume | 84 |
ISSN (Electronic) | 2640-3498 |
Conference
Conference | The 21st International Conference on Artificial Intelligence and Statistics |
---|---|
Abbreviated title | AISTATS 2018 |
Country | Spain |
City | Lanzarote |
Period | 9/04/18 → 11/04/18 |
Internet address |