June Vuong (Stanford)
Title: Tight Markov chain analysis using discrete log-concavity
Abstract:
Sampling is a fundamental task with many applications in algorithm design and in machine learning. Sampling from high-dimensional discrete distributions, such as Ising models, has long been studied for its applications in statistical physics, image modeling, and neural networks, as well as its connection to complexity theory. While Markov chain Monte Carlo (MCMC) is a widely used method for sampling, many gaps remain in understanding its performance.
In this talk, I will show tight analysis for Markov chains to sample from various discrete distributions using entropic and spectral independence, which are recently developed notions of discrete log-concavity. In particular l will show the optimal mixing time of the Glauber dynamics to sample weighted independent sets of graphs, also known as the hardcore model.
