2017/05/15 by Heng Guo, Guo, Heng, Kaan Kara +3
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Generative Adversarial Networks and Image Synthesis #Machine Learning (cs.LG) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1705.05154
openalex publication_date 2017/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 layerwise fashion. We show that the Gibbs sampler with a layerwise 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.