Theory Seminar

  • Gates Hillman 8102 and Zoom
  • In Person and Virtual ET
  • KUIKUI LIU
  • Ph.D. Student in Computer Science, Theory Group
  • Paul G. Allen School of Computer Science & Engineering
  • University of Washington
Seminars

Spectral Independence: A New Tool to Analyze Markov Chains

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. We introduce a new technique to bound mixing times called "spectral independence", which says that certain pairwise correlation matrices all have bounded spectral norm. This surprisingly powerful technique originates in the emerging study of high-dimensional expanders, and has allowed us to "unify" nearly all existing approaches to approximate counting and sampling by building new connections with other areas, including statistical physics, geometry of polynomials, functional analysis, and more. Through these connections, several long-standing open problems have recently been answered, including counting bases of matroids and optimal mixing of the Glauber dynamics/Gibbs sampler up to the algorithmic phase transition threshold.

Based on several joint works with Dorna Abdolazimi, Nima Anari, Zongchen Chen, Shayan Oveis Gharan, Eric Vigoda, and Cynthia Vinzant.

In Person and Zoom. See announcement.

For More Information, Please Contact: 
Keywords: