揭示了随机游走收敛速度与几何常数的深层关联，突破了经典上界限制。
Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run
- 通过功能等周常数建立谱间隙新下界，连接收敛性与几何性质。
- 在近各向同性体上实现接近O(n² log n)的混合时间，优于传统O(n³)。
- 方法基于对偶与微积分，适用于坐标型随机游走，适用范围广。
对于包含单位球的任意凸体 $\mathcal{K}\subset\mathbb{R}^{n}$，Hit-and-Run 的谱间隙为 $Ω(1/(n^2 C_{\mathsf{PI}}))$，其中 $C_{\mathsf{PI}}$ 为 $\mathcal{K}$ 上均匀分布 $π$ 的 Poincaré 常数。这表明从任意初始分布 $π_0$ 出发，需 $O(n^2 C_{\mathsf{PI}}\log(M/\varepsilon))$ 步即可在 $χ^2$-散度上达到与 $π$ 距离 $\varepsilon$ 内，其中 $M=χ^2(π_{0}\|π)$。该结果改进了 Lovász 与 Vempala（2004）基于外半径 $R$ 的 $O(n^2 R^2 \log(M/\varepsilon))$ 上界；在近各向同性情形下，结合 KLS 猜想进展，复杂度为 $O(n^2\log n\log(M/\varepsilon))$，将维数依赖从立方降至近二次。此前，将 Hit-and-Run 收敛性与 Poincaré/KLS 常数关联是开放问题，而球游走虽有类似结论但依赖更强的初始温热性。本文通过连接谱间隙与函数等周常数，并引入双变量证书，重写为偏微分方程中研究的 Babuška--Aziz 常数，其渐近界由改进的 Poincaré 常数控制，且可由常规 Poincaré 常数界定。证明采用对偶与微积分，不同于以往基于连通性的分析。相同方法亦适用于坐标型 Hit-and-Run，获得 $O(n^3 C_{\mathsf{PI}}\log(M/\varepsilon))$ 的更优混合时间。
原文摘要 · Abstract (English)
For any convex body $\mathcal{K}\subset\mathbb{R}^{n}$ containing a unit ball, the spectral gap of Hit-and-Run is $Ω(1/(n^2 C_{\mathsf{PI}}))$, where $C_{\mathsf{PI}}$ is the Poincaré constant of the uniform distribution $π$ over $\mathcal{K}$. This implies that Hit-and-Run converges to a distribution within $χ^2$-divergence $\varepsilon$ of the uniform distribution $π$ in $O(n^2 C_{\mathsf{PI}}\log(M/\varepsilon))$ steps from any starting distribution $π_0$ with $M=χ^2(π_{0}\,\|\,π)$, thus refining the known bound of $O(n^2 R^2 \log(M/\varepsilon))$ by Lovász and Vempala (2004) in terms of the outer radius $R$; for nearly isotropic bodies, together with progress on the KLS conjecture, the complexity is $O(n^2\log n\log(M/\varepsilon))$, improving the dimension dependence from cubic to nearly quadratic while maintaining logarithmic dependence on the initial distance. It was an open problem to connect the convergence of Hit-and-Run to Poincaré/KLS constants as was done for the Ball walk by Kannan, Lovász and Simonovits (1997). Unlike Hit-and-Run, the Ball walk has an unavoidable linear dependence on (a stronger notion) of the initial warmness. We directly bound the spectral gap of the Hit-and-Run Markov chain by connecting it to functional isoperimetric constants, inspired by the recent analysis of In-and-Out. Rewriting the spectral gap in terms of dual certificates leads to the Babuška--Aziz constant studied in the analysis of PDEs; it is asymptotically bounded by the improved Poincaré constant, which we show can be bounded in terms of the usual Poincaré constant. The proof is based on duality and calculus, unlike known proofs of convergence for Hit-and-Run which are based on bounding the conductance. The same technique can be applied to Coordinate Hit-and-Run, resulting in a much improved mixing time of $O(n^3C_{\mathsf{PI}}\log(M/\varepsilon))$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。