Abstract

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

To establish our results, wepresent an improved version of the spectral independence approach of Anari etal. (2020) and shows O(nlogn) mixing time for graphical models/spin systems onany n-vertex graph of bounded degree when the maximum eigenvalue of anassociated influence matrix is bounded. Our proof approach combines classictools like entropy tensorization/factorization and recent developments ofhigh-dimensional expanders.

Based on joint work with KuikuiLiu and Eric Vigoda.

Time

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

Speaker

Zongchen Chen is afifth-year Ph.D. student in the Algorithms, Combinatorics, and Optimization(ACO) program at Georgia Institute of Technology. He is fortunate to be advisedby Prof. Eric Vigoda. Before that, he received the Bachelor's degree in Math& Applied Math from Zhiyuan College at Shanghai Jiao Tong University in2016. 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 learningproblems related to graphical models.

Venue

ZoomID:  66051562293

密码：123456