Sampling from convex bodies using multiscale decompositions

Abstract: Running a random walk in a convex body K ⊆ Rⁿ is a standard approach to sample approximately uniformly from the body. The requirement is that from a suitable initial distribution, the distribution of the walk comes close to the uniform distribution π on K after a number of steps polynomial in the dimension n and the aspect ratio R/r (i.e., when the body is contained in a ball of radius R and contains a ball of radius r). Proofs of rapid mixing of such walks often require that the initial distribution from which the random walk starts should be somewhat diffuse: formally, the probability density η₀ of the initial distribution with respect to π should be at most polynomial in the dimension n: this is called a "warm start". Achieving a warm start often requires non-trivial pre-processing before starting the random walk. This motivates proving rapid mixing from a "cold start", where the initial density η₀ with respect to π can be exponential in the dimension n. Unlike warm starts, a cold start is usually trivial to achieve. However, a random walk need not mix rapidly from a cold start: an example being the well-known "ball walk". On the other hand, Lovász and Vempala proved that the "hit-and-run" random walk mixes rapidly from a cold start. For the related coordinate hit-and-run (CHR) walk, which has been found to be promising in computational experiments, rapid mixing from a warm start was proved only recently but the question of rapid mixing from a cold start remained open. We construct a family of random walks inspired by the classical Whitney decomposition of subsets of Rⁿ into countably many axis-aligned dyadic cubes. We show that even with a cold start, the mixing times of these walks are bounded by a polynomial in n and the aspect ratio. Our main technical ingredient is an isoperimetric inequality for K for a metric that magnifies distances between points close to the boundary of K. As a corollary, we show that the coordinate hit-and-run walk also mixes rapidly both from a cold start and even from any initial point not too close to the boundary of K.

Joint work with Hariharan Narayanan (TIFR) and Amit Rajaraman (IIT Bombay).

Click here to watch the recording