Localization schemes and the mixing of hit-and-run
We introduce the localization schemes framework for analyzing the mixing time of Markov chains. Our framework unifies and extends the previous proof techniques via spectral independence framework by Anari, Liu and Oveis Gharan and the stochastic localization process used for proving high dimensional properties of log-concave measures. The use of localization schemes allows us to reduce the problem of mixing time analysis on the original target distribution to the mixing time analysis on simpler transformed distributions.
As an example, we apply the framework to analyze the hit-and-run algorithm for sampling uniformly from an isotropic convex body K in n dimensions. We show that the hit-and-run algorithm mixes in time O(n^2) for an isotropic convex body. Our bound improves upon previous bounds of the form O(n^2R^2/r^2), which depend on the ratio R/r of the radii of the circumscribed and inscribed balls of K, gaining a factor of n in the case of isotropic convex bodies. Consequently, our result gives a mixing time estimate for the hit-and-run which matches the state-of-the-art bounds for the ball walk.