Title of Talk: Multiscale decompositions and random walks on convex bodies
Speaker: Piyush Srivastava, TIFR
Date: January 16, 2023
Time: 16:00:00 Hours
Venue: A-369
Abstract: Running a random walk in a convex body $K \subseteq R^n$ 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 $\pi$ 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 Î$\eta_0$ of the initial distribution with respect to $\pi$ 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 $\eta_0$ with respect to $\pi$ 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\'asz 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^n$ 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).