ARC and Indo-US Virtual Center Seminar: Zongchen Chen (Georgia Tech)

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.

----------------------------------

Speaker's Webpage

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

Event Details

Date/Time:

  • Monday, November 30, 2020
    11:00 am - 12:00 pm