Probabilitas Seminar: Kuikui Liu
Date and Time
Location
The probabilitas seminar focuses on topics at the intersection of topics like probability, signal processing, information theory, and statistical physics. This week's seminar speaker is Kuikui Liu from MIT EECS (Electrical Engineering and Computer Science).
Title: Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
Abstract: Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to sample from their stationary measure. Nevertheless, Markov chains can be shown to always converge quickly to measures that are locally stationary, i.e., measures that don't change over a small number of steps. While locally stationary measures can be statistically far from stationary measures, do they enjoy provable theoretical guarantees which are useful for optimization and statistical inference tasks? We study this question and demonstrate several algorithmic applications: We show that Glauber dynamics
- efficiently finds large independent sets in arbitrary d-regular triangle-free graphs, and
- efficiently samples vectors achieving constant correlation with the hidden communities in the stochastic block model.
Based on joint work with Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, David X. Wu.