# Sampling from convex sets with a cold start using multiscale decompositions

arXiv: https://arxiv.org/abs/2211.04439 · HTML: https://mlsanity.com/paper/2211.04439/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2022.

## Built on by (most cited first, 1 of 1)

- [Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run](https://mlsanity.com/paper/2608.16878/) (2026)

## Abstract (arXiv)

Running a random walk in a convex body Ksubseteqℝ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 πK on K after a number of steps polynomial in n and the aspect ratio R/r (i.e., when rB2 subseteq K subseteq RB2). Proofs of rapid mixing of such walks often require the probability density η0 of the initial distribution with respect to πK to be at most poly(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", wherein η0 can be as high as exp(poly(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 classical decompositions of subsets of ℝ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 CHR walk also mixes rapidly both from a cold start and from a point not too close to the boundary of K.