BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Entropic Independence and Optimal Sampling from Combinatorial  Dis
 tributions - Nima Anari (Stanford)
DTSTART:20220208T163000Z
DTEND:20220208T173000Z
UID:TALK169496@talks.cam.ac.uk
CONTACT:Perla Sousi
DESCRIPTION:I will introduce a notion of expansion for weighted hypergraph
 s called \nentropic independence. This is motivated by the desire for tigh
 t mixing \ntime bounds of several natural local discrete Markov chains. As
  is \nwidely known in Markov Chain analysis\, spectral analysis is often l
 ossy \n(by polynomial factors) when the state space is exponentially large
 . \nInstead\, Modified Log-Sobolev Inequalities (MLSI)\, which characteriz
 e \nthe rate of entropy decay\, are powerful enough to often yield a tight
  \nmixing time bound. We show how to obtain entropic independence\, and as
  a \nconsequence\, tight MLSI and mixing time bounds\, for a range of natu
 ral \nchains/distributions. We recover earlier known results about mixing 
 of \nbasis-exchange walks on matroids\, and obtain new tight mixing time \
 nbounds for several others: examples include monomer dynamics in \nmonomer
 -dimer systems\, Glauber dynamics in high-temperature Ising models \nand h
 igh-temperature hardcore models\, and non-symmetric determinantal \npoint 
 processes.\n\nOur main technical contribution is a new connection between 
 the geometry \nof the generating polynomial of distributions and entropy d
 ecay. Using \nthis connection\, we show how to lift spectral notions of \n
 high-dimensional expansion\, with little extra effort\, into equivalent \n
 entropic notions. This allows us to translate Poincare inequalities into \
 ncorresponding MLSI. Time-permitting\, I will briefly mention an \nadditio
 nal algorithmic implication of entropic independence: faster \nsampling of
  distributions via preprocessing and sparsification.\n\nBased on joint wor
 ks with: Michał Dereziński\, Vishesh Jain\, Frederic \nKoehler\, Huy Tua
 n Pham\, Thuy-Duong Vuong\, and Elizabeth Yang.\n
LOCATION:Online (Zoom)
END:VEVENT
END:VCALENDAR