论文标题
通过本地化方案进行击中混合
Hit-and-run mixing via localization schemes
论文作者
论文摘要
我们分析了从各向同性凸件$ k $ in $ n $ dimensions中均匀采样的命中算法。我们表明，该算法在时间中混合$ \ tilde {o}（n^2/ψ_n^2）$，其中$ψ_n$是对于任何同型logconcave分布，也称为kannan-lovasz-simonovits（kls）常数。我们的界限改进了$ \ tilde {o}（n^2 r^2/r^2）$的先前界限，这取决于限制和插入的球的比率$ r/r $ $ r/r $的$ k $，在同位素浓度浓度的情况下获得了$ n $的$ n $。因此，我们的结果给出了与击中跑步的混合时间估计，该命中率与球步行的最新边界匹配。我们的主要证明技术是基于对Chen and Eldan（2022）中引入的本地化方案的退火，这使我们能够将问题减少到分析截短高斯分布的混合时间的分析。
We analyze the hit-and-run algorithm for sampling uniformly from an isotropic convex body $K$ in $n$ dimensions. We show that the algorithm mixes in time $\tilde{O}(n^2/ ψ_n^2)$, where $ψ_n$ is the smallest isoperimetric constant for any isotropic logconcave distribution, also known as the Kannan-Lovasz-Simonovits (KLS) constant. Our bound improves upon previous bounds of the form $\tilde{O}(n^2 R^2/r^2)$, which depend on the ratio $R/r$ of the radii of the circumscribed and inscribed balls of $K$, gaining a factor of $n$ in the case of isotropic convex bodies. Consequently, our result gives a mixing time estimate for the hit-and-run which matches the state-of-the-art bounds for the ball walk. Our main proof technique is based on an annealing of localization schemes introduced in Chen and Eldan (2022), which allows us to reduce the problem to the analysis of the mixing time on truncated Gaussian distributions.
