ARC Colloquium: June Vuong (Klaus 1116, 11am)

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.

Event Details

Date/Time:

  • Monday, October 2, 2023
    11:00 am - 12:00 pm
Location: Klaus 1116