Sampling from convex sets with a cold start using multiscale decompositions

Abstract A standard approach for sampling approximately uniformly from a convex body $$K \subseteq \mathbb {R}^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>⊆</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:math> is to run a random walk within K . The requirement is that starting from a suitable initial distribution, the random walk should “mix rapidly”, i.e., after a number of steps that is polynomial in n and the aspect ratio R / r (here, K is assumed to contain a ball of radius r and to be contained within a ball of radius R ), the distribution of the random walk should come close to the uniform distribution $$\pi _K$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>π</mml:mi> <mml:mi>K</mml:mi> </mml:msub> </mml:math> on K . Different random walks differ in aspects such as the ease of implementation of each step, or suitability for a specific class of convex bodies. Therefore, the rapid mixing of a wide variety of random walks on convex bodies has been studied. Many proofs of rapid mixing of such random walks however require that the initial distribution of the random walk is not too different from the target distribution $$\pi _K$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>π</mml:mi> <mml:mi>K</mml:mi> </mml:msub> </mml:math> . In particular, they require that the probability density function of the initial distribution with respect to the uniform distribution $$\pi _K$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>π</mml:mi> <mml:mi>K</mml:mi> </mml:msub> </mml:math> on K must be bounded above by $$\textrm{poly}(n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>poly</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> : this is called a warm start . Achieving such a warm start often requires a non-trivial pre-processing step before the random walk can be started. This motivates the problem of proving rapid mixing from “cold starts”, i.e., when the density of the initial distribution with respect to $$\pi _K$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>π</mml:mi> <mml:mi>K</mml:mi> </mml:msub> </mml:math> can be as high as $$\exp (\textrm{poly}(n))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>exp</mml:mo> <mml:mo>(</mml:mo> <mml:mtext>poly</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . In contrast to warm starts, a cold start is usually trivial to achieve. However, rapid mixing from a cold start may not hold for every random walk, e.g., the well-known “ball walk” does not have rapid mixing from an arbitrary cold start. On the other hand, for the “hit-and-run” random walk, Lovász and Vempala proved rapid mixing from a cold start. For the related coordinate hit-and-run (CHR) random walk, which has been found to be promising in computational experiments, a rapid mixing result starting from a warm start was proven only recently, while the question of whether CHR mixes rapidly from a cold start remained open. In this paper, we construct a family of Markov chains inspired by classical multiscale decompositions of subsets of $$\mathbb {R}^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:math> into countably many axis-aligned cubes. We show that even with a cold start, the mixing times of these chains are bounded by a polynomial in n and the aspect ratio of the body. Our main technical ingredient is an isoperimetric inequality for K for a metric that magnifies distances between points that are close to the boundary of K . As a byproduct of the analysis of this new family of chains, we show that the coordinate hit-and-run (CHR) random walk also mixes rapidly from a cold start, and also from any point that is not too close to the boundary of the body.