*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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
