Nguyen Thuy Duong Vuong (Stanford) - Entropic Independence: Optimal Mixing of Local Random Walks
In this talk, we will define a notion called entropic independence that is an entropic analog of spectral notions of high dimensional expansion. Informally, entropic independence of a background distribution µ on k-sized subsets of a ground set of elements says that for any (possibly randomly chosen) set S, the relative entropy of a single element of S drawn uniformly at random carries at most O(1/k) fraction of the relative entropy of S, a constant multiple of its “share of entropy.” Entropic independence is the natural analog of the recently established notion of spectral independence, if one replaces variance by entropy. Similar to how spectral independence is used to establish lower bounds on the Poincare constant of certain local random walks, we show a general way to derive lower bounds on the modified log Sobolev constant of these random walks using entropic independence.
Our main applications include tight mixing time bounds for Glauber dynamics on Ising models whose interaction matrix has eigenspectrum lying within an interval of length smaller than 1, and for a variation of the Glauber dynamics to sample from the hardcore model on general graphs.up to the tree-uniqueness threshold. These results give a quadratic improvement over previously best bounds on the mixing time of these random walks.
Based on joint work with Nima Anari, Vishesh Jain, Frederic Koehler, and Huy Tuan Pham. To appear at STOC 2022.
Host: Madhur Tulsiani
Speakers
Nguyen Thuy Duong Vuong
Thuy-Duong “June” Vuong is a third year PhD student at Stanford University, working with Nima Anari and Moses Charikar. She works on geometry of polynomials, with applications in sampling and optimization algorithms over combinatorial domain.
