Abstract

I will introduce a notion of expansion for weighted hypergraphs called entropic independence. This is motivated by the desire for tight mixing time bounds of several natural local discrete Markov chains. As is widely known in Markov Chain analysis, spectral analysis is often lossy (by polynomial factors) when the state space is exponentially large. Instead, Modified Log-Sobolev Inequalities (MLSI), which characterize the rate of entropy decay, are powerful enough to often yield a tight mixing time bound. We show how to obtain entropic independence, and as a consequence, tight MLSI and mixing time bounds, for a range of natural chains/distributions. We recover earlier known results about mixing of basis-exchange walks on matroids, and obtain new tight mixing time bounds for several others: examples include monomer dynamics in monomer-dimer systems, Glauber dynamics in high-temperature Ising models and high-temperature hardcore models, and non-symmetric determinantal point processes.

Our main technical contribution is a new connection between the geometry of the generating polynomial of distributions and entropy decay. Using this connection, we show how to lift spectral notions of high-dimensional expansion, with little extra effort, into equivalent entropic notions. This allows us to translate Poincare inequalities into corresponding MLSI . Time-permitting, I will briefly mention an additional algorithmic implication of entropic independence: faster sampling of distributions via preprocessing and sparsification.

Based on joint works with: Michał Dereziński, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Thuy-Duong Vuong, and Elizabeth Yang.