论文标题
使用多尺度分解的凸套装中的采样
Sampling from convex sets with a cold start using multiscale decompositions
论文作者
论文摘要
在凸面上进行随机步行$ k \ subseteq \ mathbb {r}^n $是一种标准方法，可以从身体上大约均匀地采样。要求是，从合适的初始分布中，步行的分布接近$ k $的均匀分布$π_k$，在$ n $的多项式$ k $和长宽比$ r/r $（即，当$ rb_2 \ subseteq k \ subseteq k \ subseteq rb_ rb_ {2} $时）。 相对于$π_k$的初始分布的概率密度$η_0$的快速混合证明，最多是$ \ mathrm {poly}（n）$：这称为“温暖开始”。实现温暖的开始通常需要在开始随机步行之前进行非平凡的预处理。这激发了从“冷启动”中证明快速混合的，其中$η_0$可以高达$ \ exp（\ mathrm {poly}（n））$。与温暖的开始不同，冷启动通常是微不足道的。但是，随机步行不必从冷启动开始迅速混合：一个例子是众所周知的“球步道”。另一方面，Lovász和Vempala证明了“击中”随机步行从冷启动开始迅速混合。对于相关的坐标撞击（CHR）步行（在计算实验中都很有前途），直到最近才证明了从温暖起步的快速混合，但是从冷启动开始快速混合的问题仍然开放。 我们构建了一个由$ \ mathbb {r}^n $子集的经典分解启发的随机步行家族中，这些分解为许多轴对准的二元立方体。我们表明，即使有一个寒冷的开始，这些步行的混合时间也受到$ n $的多项式和宽高比的界定。我们的主要技术成分是用于$ k $的等速度不平等，用于度量，它在$ k $的边界附近的点之间放大了距离。作为推论，我们表明CHR Walk也从冷启动开始，从不太接近$ k $的边界开始迅速混合。
Running a random walk in a convex body $K\subseteq\mathbb{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 $π_K$ on $K$ after a number of steps polynomial in $n$ and the aspect ratio $R/r$ (i.e., when $rB_2 \subseteq K \subseteq RB_{2}$). 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 $\mathrm{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(\mathrm{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á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 classical decompositions of subsets of $\mathbb{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 CHR walk also mixes rapidly both from a cold start and from a point not too close to the boundary of $K$.
