Abstract

We consider the Glauber dynamics (also called Gibbs sampling) for sampling from a high-dimensional discrete distribution; e.g., selecting a random proper coloring or independent set in a given graph, or sampling a “typical” state of a given statistical physics model like the Ising model. In each step, the Glauber dynamics chooses a variable uniformly at random and updates its value conditional on all other variables. We show an optimal mixing time bound for the Glauber dynamics in a variety of settings. As an application of our results, for the hard-core model on weighted independent sets, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree when the parameter of the model lies in the tree uniqueness region. Our results apply more broadly to other models including antiferromagnetic 2-spin systems (e.g., Ising model), random colorings, and weighted matchings.

To establish our results, we present 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 like entropy tensorization/factorization and recent developments of high-dimensional expanders.

Based on joint work with Kuikui Liu and Eric Vigoda.

Time

3月29日  10:00--11:00

Speaker

Zongchen Chen is a fifth-year Ph.D. student in the Algorithms, Combinatorics, and Optimization (ACO) program at Georgia Institute of Technology. He is fortunate to be advised by Prof. Eric Vigoda. Before that, he received the Bachelor's degree in Math & Applied Math from Zhiyuan College at Shanghai Jiao Tong University in 2016. He has broad interests in randomized algorithms, discrete probability, and machine learning. Currently, he mainly works on Markov chain Monte Carlo (MCMC) methods for sampling from Gibbs distributions, and machine learning problems related to graphical models.

Venue

Zoom ID:  66051562293

密码：123456