- Series
- Joint ACO and ARC Colloquium
- Time
- Wednesday, November 6, 2019 - 12:00pm for 1.5 hours (actually 80 minutes)
- Location
- Skiles 006
- Speaker
- Nima Anari – Stanford University
- Organizer
- Prasad Tetali
(This is Part 2, continuation of Tuesday's lecture.)
A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve computational problems. The main parameter defining the efficiency of this method is how quickly the random walk mixes (converges to the stationary distribution). The goal of these talks is to introduce a new approach for analyzing the mixing time of random walks on high-dimensional discrete objects. This approach works by directly relating the mixing time to analytic properties of a certain multivariate generating polynomial. As our main application we will analyze basis-exchange random walks on the set of bases of a matroid. We will show that the corresponding multivariate polynomial is log-concave over the positive orthant, and use this property to show three progressively improving mixing time bounds: For a matroid of rank r on a ground set of n elements:
- We will first show a mixing time of O(r^2 log n) by analyzing the spectral gap of the random walk (based on related works on high-dimensional expanders).
- Then we will show a mixing time of O(r log r + r log log n) based on the modified log-sobolev inequality (MLSI), due to Cryan, Guo, Mousa.
- We will then completely remove the dependence on n, and show the tight mixing time of O(r log r), by appealing to variants of well-studied notions in discrete convexity.
Time-permitting, I will discuss further recent developments, including relaxed notions of log-concavity of a polynomial, and applications to further sampling/counting problems.
Based on joint works with Kuikui Liu, Shayan OveisGharan, and Cynthia Vinzant.