Final doctoral examination and defense of dissertation of Zongchen Chen, July 16, 2021
Date: July 16, 2021, 10:00am EST
Bluejeans Link is: https://bluejeans.com/588754075/8107
Title: Optimal Mixing of Markov Chains for Spin Systems via Spectral Independence
Advisor: Dr. Eric Vigoda, School of Computer Science, Georgia Institute of Technology
Committee:
Dr. Dana Randall, School of Computer Science, Georgia Institute of Technology
Dr. Daniel Štefankovič, Department of Computer Science, University of Rochester
Dr. Prasad Tetali, School of Mathematics, Georgia Institute of Technology
Dr. Santosh Vempala, School of Computer Science, Georgia Institute of Technology
Reader: Dr. Daniel Štefankovič, Department of Computer Science, University of Rochester
---------------------------------------------------------------------------------------------------------
The thesis is available here:
https://aco.gatech.edu/sites/default/files/documents/2021/dissertation-z...
Summary of the thesis is below.
Summary:
Spin systems, or undirected graphical models, are important tools for modeling joint distributions of discrete random variables, and are broadly used in statistical physics, machine learning, and theoretical computer science. One of the most important computational tasks for spin systems is to generate random samples approximately from the equilibrium distribution of the model called the Gibbs distribution. We study the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling for sampling from the Gibbs distribution. In each step, the dynamics picks a single variable uniformly at random and updates it conditional on all other variables. Despite its popularity, theoretical guarantees of the convergence rate of the Glauber dynamics are only known in a few special cases.
We prove optimal mixing time of the Glauber dynamics in a variety of settings. As an application of our results, for the hardcore model (weighted independent sets) on any n-vertex graph of constant maximum degree, we establish O(n log n) mixing time of the Glauber dynamics when the fugacity (vertex weight) lies in the tree uniqueness region. For the Ising model, and more generally any antiferromagnetic 2-spin system, we prove O(n log n) 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(n log n) mixing for q-colorings on graphs of maximum degree d when q>(11/6)d, and O(n log n) mixing for the monomer-dimer model (weighted matchings) and weighted partial even subgraphs (corresponding to the ferromagnetic Ising model with nonzero external fields) on any graph with bounded degrees. Our work presents an improved version of the spectral independence approach of Anari, Liu, and Oveis Gharan (2020) and shows optimal mixing time of the Glauber dynamics on bounded-degree graphs when the maximum eigenvalues of associated influence matrices are bounded.
