Entropic Independence and Optimal Sampling from Combinatorial Distributions

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.

• Speaker: Nima Anari (Stanford)
• Tuesday 08 February 2022, 16:30–17:30
• Venue: Online (Zoom).
• Series: Probability; organiser: Perla Sousi.