Algorithms & Randomness Center (ARC) and
Indo-US Virtual Center Seminar
Zonchen Chen (Georgia Tech)
Monday, November 30, 2020
Virtual via BlueJeans - 11:00am
Title: Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
Abstract: We consider the Glauber dynamics (also called Gibbs sampling) for sampling from a discrete high-dimensional space, where in each step one variable is chosen uniformly at random and gets updated conditional on all other variables. We show an optimal mixing time bound for the Glauber dynamics in a variety of settings. Our work presents an improved version of the spectral independence approach of Anari et al. (2020) and shows O(nlogn) mixing time for graphical models/spin systems on any n-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. Our proof approach combines classic tools of entropy tensorization/factorization and recent developments of high-dimensional expanders.
As an application of our results, for the hard-core model on independent sets weighted by a fugacity lambda, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree D when lambda<lambda_c(D) where lambda_c(D) is the critical point for the uniqueness/non-uniqueness phase transition on the D-regular tree. More generally, for any antiferromagnetic 2-spin system we prove O(nlogn) mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness region. Our results apply more broadly; for example, we also obtain O(nlogn) mixing for sampling random q-colorings of triangle-free graphs of maximum degree D when the number of colors satisfies q > aD where a = 1.763…, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges.
----------------------------------
Videos of recent talks are available at: http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
