BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Probability
SUMMARY:Entropic Independence and Optimal Sampling from Co
mbinatorial Distributions - Nima Anari (Stanford)
DTSTART;TZID=Europe/London:20220208T163000
DTEND;TZID=Europe/London:20220208T173000
UID:TALK169496AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/169496
DESCRIPTION:I will introduce a notion of expansion for weighte
d hypergraphs called \nentropic independence. This
is motivated by the desire for tight mixing \ntim
e bounds of several natural local discrete Markov
chains. As is \nwidely known in Markov Chain analy
sis\, spectral analysis is often lossy \n(by polyn
omial factors) when the state space is exponential
ly large. \nInstead\, Modified Log-Sobolev Inequal
ities (MLSI)\, which characterize \nthe rate of en
tropy decay\, are powerful enough to often yield a
tight \nmixing time bound. We show how to obtain
entropic independence\, and as a \nconsequence\, t
ight MLSI and mixing time bounds\, for a range of
natural \nchains/distributions. We recover earlier
known results about mixing of \nbasis-exchange wa
lks on matroids\, and obtain new tight mixing time
\nbounds for several others: examples include mon
omer dynamics in \nmonomer-dimer systems\, Glauber
dynamics in high-temperature Ising models \nand h
igh-temperature hardcore models\, and non-symmetri
c determinantal \npoint processes.\n\nOur main tec
hnical contribution is a new connection between th
e geometry \nof the generating polynomial of distr
ibutions and entropy decay. Using \nthis connectio
n\, we show how to lift spectral notions of \nhigh
-dimensional expansion\, with little extra effort\
, into equivalent \nentropic notions. This allows
us to translate Poincare inequalities into \ncorre
sponding MLSI. Time-permitting\, I will briefly me
ntion an \nadditional algorithmic implication of e
ntropic independence: faster \nsampling of distrib
utions via preprocessing and sparsification.\n\nBa
sed on joint works with: Michał Dereziński\, Vishe
sh Jain\, Frederic \nKoehler\, Huy Tuan Pham\, Thu
y-Duong Vuong\, and Elizabeth Yang.\n
LOCATION:Online (Zoom)
CONTACT:Perla Sousi
END:VEVENT
END:VCALENDAR