Title: Algorithmic and inferential challenges for ensemble methods
Speaker: Lorenzo Najt
Abstract: This talk will focus on two challenges for the ensemble method of defining extreme gerrymandering, namely, complexity theoretic obstructions to sampling algorithms and the dependence of the distribution of popular sampling algorithms on various features of the graph topology. After reviewing the ensemble methodology and several of the candidate sampling algorithms, we will exhibit families of dual graphs for which the "flip walk" Markov chain provably mixes slowly, and state some general results about the intractability of sampling. We will then explain how results from statistical physics are relevant for understanding the stationary distribution of the flip walk chain. Turning our attention to tree based samplers, we will give a toy example illustrating how the dual graph structure can be metamandered to change the outcome of an outlier analysis. This talk is largely based on https://arxiv.org/abs/1908.08881, but will also discuss some ongoing research and open questions. This talk will be accessible to anyone with a general mathematics or computer science background.