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

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. These locally stationary measures are analogous to local minima in continuous optimization, while stationary measures correspond to global minima. While locally stationary measures can be statistically far from stationary measures, do they enjoy provable theoretical guarantees that have algorithmic implications? We study this question in this work and demonstrate three algorithmic applications of locally stationary measures: 1)We show that Glauber dynamics on the hardcore model can be used to find large independent sets in triangle-free graphs of bounded degree. 2)We prove that Glauber dynamics on the Ising model defined by a spiked matrix model finds a vector with constant correlation with the planted spike. 3)We show that for sufficiently large constant signal-to-noise ratio, Glauber dynamics on the Ising model finds a vector that has constant correlation with the hidden community vector. In other words, Glauber dynamics subsumes the spectral method for spiked Wigner and community detection, by weakly recovering the planted spike. The full version of this paper can be found on arXiv(arXiv ID: 2405.20849).