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)