[论文] Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run

论文概要

研究领域: ML
作者: Yunbum Kook, Santosh S. Vempala
发布时间: 2026-08-17
arXiv: 2608.16878

中文摘要

对于任何包含单位球的凸体K包含于R^n，Hit-and-Run的谱间隙为Omega(1/(n^2 C_PI))，其中C_PI是K上均匀分布pi的Poincare常数。这意味着Hit-and-Run在O(n^2 C_PI log(M/epsilon))步内收敛到与均匀分布pi的chi^2-散度不超过epsilon的分布，改进了Lovasz和Vempala (2004)关于外半径R的已知界O(n^2 R^2 log(M/epsilon))；对于近乎各向同性体，结合KLS猜想的进展，复杂度为O(n^2 log n log(M/epsilon))，将维度依赖从三次改进到近乎二次，同时保持对初始距离的对数依赖。将Hit-and-Run的收敛与Poincare/KLS常数联系起来一直是开放问题。我们直接通过将其与函数等周常数联系来限定Hit-and-Run马尔可夫链的谱间隙，证明基于对偶和微积分。相同技术可应用于Coordinate Hit-and-Run，得到大幅改进的O(n^3 C_PI log(M/epsilon))混合时间。

原文摘要

For any convex body K subset R^n containing a unit ball, the spectral gap of Hit-and-Run is Omega(1/(n^2 C_PI)), where C_PI is the Poincare constant of the uniform distribution pi over K. This implies that Hit-and-Run converges to a distribution within chi^2-divergence epsilon of the uniform distribution pi in O(n^2 C_PI log(M/epsilon)) steps from any starting distribution pi_0 with M=chi^2(pi_0 || pi), thus refining the known bound of O(n^2 R^2 log(M/epsilon)) by Lovasz 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/epsilon)), improving the dimension dependence from cubic to nearly quadratic while maintaining logarithmic dependence on the initial distance. It was an open prob...

自动采集于 2026-08-19

#论文 #arXiv #ML #小凯