Spectral Independence: A New Tool to Analyze Markov Chains

Abstract:
Sampling from high-dimensional probability distributions is a fundamental and challenging problem encountered throughout science and engineering. One of the most popular approaches to tackle such problems is the Markov chain Monte Carlo (MCMC) paradigm. While MCMC algorithms are often simple to implement and widely used in practice, analyzing the rate of convergence to stationarity, i.e. the “mixing time”, remains a challenging problem in many settings.

I will describe a new technique based on pairwise correlations called “spectral independence”, which has been used to break long-standing barriers and resolve several decades-old open problems in MCMC theory. Through this technique, we’ve further established new connections with other areas such as statistical physics, geometry of polynomials, the emerging study of high-dimensional expanders, and more. Applications include discrete log-concave distributions, graphical models, and concentration inequalities. Based on several joint works with Dorna Abdolazimi, Nima Anari, Zongchen Chen, Shayan Oveis Gharan, Nitya Mani, Ankur Moitra, Eric Vigoda, Cynthia Vinzant, and June Vuong.

Bio:
Kuikui Liu is a Postdoctoral Associate at MIT CSAIL, previously in the Theory Group at the Paul G. Allen School for Computer Science and Engineering at the University of Washington. (UW CSE). His research interests are in high-dimensional geometry and analysis of Markov chains. He develops and uses mathematical tools from fields such as high-dimensional expanders, geometry of polynomials, and statistical physics.