Uncategorized

Agorithms, Combinatorics & Optimization / Theory Seminar

Friday, December 11, 2020 – 3:30pm to 4:30pm

Location:

Virtual Presentation Remote Access – Zoom

Speaker:

ZONGCHEN CHEN, Ph.D. Student https://sites.google.com/view/zongchenchen/home

Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion

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 aD where a = 1.763…, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges. 

Document Reference

Zoom Participation. See announcement.

Event Website:

http://aco.math.cmu.edu/seminar.html

For More Information, Contact:

Keywords:

Seminar Series

Similar Posts