Sampling from convex bodies using multiscale decompositions
Speaker 
Speaker: Piyush Srivastava (TIFRSTCS, Mumbai)


When 
Aug 22, 2023
from 04:00 PM to 05:00 PM 
Where  Online via Zoom 
Add event to calendar 
vCal iCal 
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 nontrivial preprocessing 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 wellknown "ball walk". On the other hand, Lovász and Vempala proved that the "hitandrun" random walk mixes rapidly from a cold start. For the related coordinate hitandrun (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 axisaligned 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 hitandrun 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)