Kuikui Liu: Markov Chain Analysis via Spectral Independence

ABSTRACT: Markov chain Monte Carlo is a widely used class of algorithms for sampling from high-dimensional probability distributions, both in theory and in practice. While simple to implement, analyzing the rate of convergence to stationarity, i.e. the "mixing time", remains a challenging problem in many settings. I will describe a recent line of work using correlation inequalities to prove rapid mixing which has been used to break long-standing barriers. This surprisingly powerful technique is based on the emerging study of high-dimensional expanders, and has allowed us to build numerous new connections with other areas such as statistical physics, geometry of polynomials, and more. Applications include discrete log-concave distributions, probabilistic graphical models in machine learning, and concentration inequalities. Based on several joint works with Dorna Abdolazimi, Nima Anari, Zongchen Chen, Shayan Oveis Gharan, Eric Vigoda, and Cynthia Vinzant.