Abstract
Markov chain-based methods are ubiquitous and have been highly successful at statistical inference, scientific simulation, and optimization. The common wisdom is that the reason for their success is that a Markov chain of interest “mixes” to its stationary distribution.
But what if the Markov chain does not mix fast? It is empirically observed that often 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.
In this talk, we will see some generic methods to analyze the structure of distributions that non-mixing Markov chains sample from, along with applications to finding large independent sets in graphs, and finding planted cuts in random graphs.
Based on joint work with Kuikui Liu, Prasad Raghavendra, Amit Rajaraman and David X Wu. https://arxiv.org/abs/2405.20849
Bio
Sidhanth Mohanty is an Assistant Professor in the Computer Science department at Northwestern University. Sidhanth is generally interested in theoretical computer science and probability theory. Most recently, he has been interested in mixing times of Markov chains, high-dimensional expansion, random matrix theory, and error-correcting codes. Sidhanth recieved his undergraduate degree from Carnegie Mellon University, his PhD from UC Berkeley, and was postdoc at MIT.
Orchard View Room
Northwestern University, Sidhanth Mohanty