Algorithms & Randomness Center (ARC)
Yuansi Chen (Duke University)
September 12, 2022
Klaus 1116 - 11:00 am
Title: Localization schemes: A framework for proving mixing bounds for Markov chains
Abstract: Our work is motivated by two recent and seemingly-unrelated techniques for proving mixing bounds for Markov chains:
(i) the concept of spectral independence, introduced by Anari, Liu and Oveis Gharan, and its numerous extensions, which have given rise to several breakthroughs in the analysis of mixing times of discrete Markov chains and
(ii) the stochastic localization technique which has proven useful in establishing mixing and expansion bounds for both log-concave measures and for measures on the discrete hypercube.
In this work, we present a framework which connects ideas from both techniques and allows us to unify proofs in the mixing time of MCMC algorithms on high dimensional distributions. In its center is the concept of a localization scheme which, to every probability measure , assigns a martingale of probability measures which localize in space as time evolves. This viewpoint provides tools for deriving mixing bounds for the dynamics through the analysis of the corresponding localization process. Generalizations of concepts of spectral independence naturally arise from our definitions. In particular we show via our framework that it is possible to recover the main theorems in the spectral independence frameworks via simple martingale arguments, while completely bypassing the theory of high-dimensional expanders. As applications, we discuss how to use it to obtain the first O(nlogn) bound for mixing time of the hardcore-model (of arbitrary degree) in the tree-uniqueness regime, under Glauber dynamics and to prove a KL-divergence decay bound for log-concave sampling via the Restricted Gaussian Oracle, which achieves optimal mixing under any exp(n)-warm start.
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
