Entropic Independence and Optimal Sampling from Combinatorial Distributions

Add to your list(s) Download to your calendar using vCal

• Nima Anari (Stanford)
• Tuesday 08 February 2022, 16:30-17:30
• Online (Zoom).

If you have a question about this talk, please contact Perla Sousi.

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.

This talk is part of the Probability series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• Online (Zoom)
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.