Timezone: »
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.
Author Information
Bryan He (Stanford University)
Christopher M De Sa (Stanford University)
Ioannis Mitliagkas (University of Montreal)
Christopher Ré (Stanford University)
More from the Same Authors
-
2021 : Correct-N-Contrast: A Contrastive Approach for Improving Robustness to Spurious Correlations »
Michael Zhang · Nimit Sohoni · Hongyang Zhang · Chelsea Finn · Christopher Ré -
2021 : Alex Ratner and Chris Re - The Future of Data Centric AI »
Christopher Ré -
2021 Poster: Scatterbrain: Unifying Sparse and Low-rank Attention »
Beidi Chen · Tri Dao · Eric Winsor · Zhao Song · Atri Rudra · Christopher Ré -
2020 : Tree Covers: An Alternative to Metric Embeddings »
Roshni Sahoo · Ines Chami · Christopher Ré -
2020 Poster: No Subclass Left Behind: Fine-Grained Robustness in Coarse-Grained Classification Problems »
Nimit Sohoni · Jared Dunnmon · Geoffrey Angus · Albert Gu · Christopher Ré -
2018 : Lunch »
Hong Yu · Bhanu Pratap Singh Rawat · Arijit Ukil · Waheeda Saib · Jekaterina Novikova · John Hughes · Yuhui Zhang · Rahul V · Mi Jung Kim · Babak Taati · Hariharan Ravishankar · Harry Clifford · Hirofumi Kobayashi · Babak Taati · Keyang Xu · Yen-Chi Cheng · Timothy Cannings · Jayashree Kalpathy-Cramer · Jayashree Kalpathy-Cramer · Parinaz Sobhani · Kimis Perros · Wei-Hung Weng · Yordan Raykov · Lars Lorch · Mengqi Jin · Xue Teng · Michael Ferlaino · Marek Rei · Cédric Beaulac · Aman Verma · Sebastian Keller · Edmond Cunningham · Luc Evers · Victor Rodriguez · Vipul Satone · Dianbo Liu · Angeline Yasodhara · Geoff Tison · Ligin Solamen · Bryan He · Rahul Ladhania · Yipeng Shi · Md Nafiz Hamid · Pouria Mashouri · Woochan Hwang · Sejin Park · Xu Chen · Rachneet Kaur · Davis Blalock · Holly Wiberg · Parminder Bhatia · Kezi Yu · RUMENG LI · Jun Sakuma · Charles Ding · Aaron Babier · Yong Cai · A Pratap · Luke O'Connor · Allen Nie · Martin Kang · Ian Covert · Xun Wang · Zelun Luo · Serena Yeung · William Boag · Kazuki Tachikawa · Mary Saltz · Owen Lahav · Edward Lee · Eric Teasley · Michael Kamp · Nirmesh Patel · Vishwali Mhasawade · Maxim Samarin · Ryo Uchimido · Farzad Khalvati · Francisco Cruz · Laura Symul · Zaid Nabulsi · Mads Mihailescu · Rosalind Picard -
2017 Poster: Gaussian Quadrature for Kernel Features »
Tri Dao · Christopher M De Sa · Christopher Ré -
2017 Spotlight: Gaussian Quadrature for Kernel Features »
Tri Dao · Christopher M De Sa · Christopher Ré -
2017 Poster: Inferring Generative Model Structure with Static Analysis »
Paroma Varma · Bryan He · Payal Bajaj · Nishith Khandwala · Imon Banerjee · Daniel Rubin · Christopher Ré -
2016 Poster: Data Programming: Creating Large Training Sets, Quickly »
Alexander Ratner · Christopher M De Sa · Sen Wu · Daniel Selsam · Christopher Ré -
2015 : Hardware Trends for High Performance Analytics »
Christopher Ré -
2015 : Taking it Easy »
Christopher Ré -
2015 Poster: Smooth Interactive Submodular Set Cover »
Bryan He · Yisong Yue -
2015 Poster: Rapidly Mixing Gibbs Sampling for a Class of Factor Graphs Using Hierarchy Width »
Christopher M De Sa · Ce Zhang · Kunle Olukotun · Christopher Ré -
2015 Spotlight: Rapidly Mixing Gibbs Sampling for a Class of Factor Graphs Using Hierarchy Width »
Christopher M De Sa · Ce Zhang · Kunle Olukotun · Christopher Ré · Christopher Ré -
2015 Poster: Taming the Wild: A Unified Analysis of Hogwild-Style Algorithms »
Christopher M De Sa · Ce Zhang · Kunle Olukotun · Christopher Ré · Christopher Ré