Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains

A common algorithmic task is to sample from some probability distribution of choice D.  The most popular algorithm for such tasks is to run a Markov chain with stationary distribution D, and when the Markov chain mixes rapidly, it does indeed produce samples from D.

But what if the Markov chain does not mix fast?  It is empirically observed that sometimes the output produced by the Markov chain is nevertheless still a "good" solution for the downstream applications of sampling, even though it's not faithfully sampling from the correct distribution.

For example, it appears to find planted cuts in random graphs, or planted solutions in random CSPs, despite bottlenecks to rapid mixing.

In this talk, we will see some generic methods to analyze the structure of distributions that non-mixing Markov chains sample from, along with some applications.

Based on joint work with Kuikui Liu, Prasad Raghavendra, Amit Rajaraman and David X Wu. https://arxiv.org/abs/2405.20849