Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run

技术摘要：Hit-and-Run 与 Coordinate Hit-and-Run 的谱间隙

问题陈述
本文研究了在凸体 $K \subset \mathbb{R}^n$ 中进行采样的 Hit-and-Run (HAR) 和 Coordinate Hit-and-Run (CHAR) 马尔可夫链的收敛速率。虽然 Kannan, Lovász, 和 Simonovits (1997) 已成功将 Ball walk 的收敛性与泛函等周常数（特别是 Poincaré 和 KLS 常数）联系起来，但对于 Hit-and-Run 是否存在类似的联系，此前一直是一个悬而未决的问题。以往针对 HAR 的界限（如 Lovász 和 Vempala (2004) 所给出的界限）依赖于该物体的外半径 $R$，其混合时间为 $O(n^2 R^2 \log(M/\varepsilon))$。对于近各向同性的物体，这种对 $R$ 的依赖是次优的，因为其维度依赖性有望从三次优化到接近二次。此外，不同于 Ball walk 存在对初始“热度”参数的线性依赖，已知 HAR 能保持对该参数的对数依赖。核心问题在于，是否可以在保持对初始距离的对数依赖的同时，通过 Poincaré/KLS 常数来限制 HAR 的收敛速率。

方法论
作者引入了一种证明技术，绕过了传统的通过限制电导率（conductance）来研究的方法，而这曾是以往 HAR 收敛性证明的基础。相反，本文通过将谱间隙直接与泛函等周常数联系起来，直接对马尔可夫链的谱间隙进行估计。

该方法论的核心包括：

1. 对偶证书（Dual Certificates）： 谱间隙被重写为关于对偶证书的形式。这种重新表述导致了对 Babuška–Aziz 常数（在 PDE 分析中被研究）的识别，该常数刻画了 $H^1_0(K; \mathbb{R}^n)$ 中散度方程 $\text{div } u = f$ 的可解性。
2. 算子构造： 定义了一个有界线性算子 $T$，其范数对应于该链的狄利克雷形式（Dirichlet form/能量）。目标是寻找一个对偶证书 $g_f$，使得 $T^* g_f = f$ 且 $\|g_f\| \leq C \|f\|$。
3. 连接常数： 证明建立了一系列不等式链：
   • 谱间隙由 Babuška–Aziz 常数 ($C_{BA}$) 的倒数下界限定。
   • $C_{BA}$ 被证明在渐近意义上受限于 改进的 Poincaré 常数 ($C_{IPI}$)，该常数引入了到边界的距离 $\delta(x)$ 作为权重。
   • $C_{IPI}$ 则由包含单位球的凸体的标准 Poincaré 常数 ($C_{PI}$) 来界定。

这种方法依赖于对偶性和微积分，而非几何电导率论证。作者指出，该证明框架对于 HAR 和 CHAR 基本是相同的，主要的区别在于谱间隙界限中的维度因子。

主要贡献与结果
对于包含单位球的凸体 $K$，设 $\pi$ 为 $K$ 上的均匀分布，本文提供了以下理论结果：

1. 谱间隙界限：

   • 对于 Hit-and-Run：$\lambda_{HR} \gtrsim \frac{1}{n^2 C_{PI}(\pi)}$。
   • 对于 Coordinate Hit-and-Run：$\lambda_{CHAR} \gtrsim \frac{1}{n^3 C_{PI}(\pi)}$。
   • 利用关系式 $C_{PI}(\pi) \lesssim \|\text{cov}_\pi\|_{op} \log n$，这些界限可转化为 $\lambda_{HR} \gtrsim \frac{1}{n^2 \|\text{cov}_\pi\|_{op} \log n}$。

2. 混合时间改进：

   • 实现 $\chi^2$-散度 $\varepsilon$（相对于初始分布的 $\chi^2$-散度为 $M$）的混合时间为：
     • HAR： $O(n^2 C_{PI} \log(M/\varepsilon))$。
     • CHAR： $O(n^3 C_{PI} \log(M/\varepsilon))$。
   • 对于近各向同性的物体（其中 $\|\text{cov}_\pi\|_{op} \approx 1$）并假设 KLS 猜想取得进展（即 $C_{PI} \approx O(1)$），HAR 的复杂度变为 $O(n^2 \log n \log(M/\varepsilon))$。这精炼了之前的 $O(n^2 R^2 \log(M/\varepsilon))$ 界限，将维度依赖性从三次（通过 $R^2 \sim n$）优化到了接近二次。

3. 技术引理：

   • 论文证明了对于有界凸域，$C_{BA} \leq 1 + 4 C_{IPI}$。
   • 它确立了 $C_{IPI} \lesssim n^2 C_{PI} / r^2$（其中 $r$ 是内半径），提供了加权与非加权 Poincaré 常数之间必要的联系。

意义
本文声称解决了一个存在十年的悬而未决的问题，即将 Hit-and-Run 的收敛性直接与 Poincaré 和 KLS 常数联系起来，而这种联系此前仅在 Ball walk 中得到建立。

• 界限精炼： 它精炼了已知的 HAR 界限，用更具本质几何属性的 Poincaré 常数取代了对外部半径 $R$ 的依赖。
• 维度依赖： 对于各向同性物体，该结果将 HAR 的混合时间维度依赖性从三次优化到了接近二次 ($O(n^2 \log n)$)，使 HAR 的理论性能更接近于所推测的最优采样速率。
• 方法论转变： 该工作引入了一种基于对偶性和 Babuška–Aziz 常数的全新证明框架，为其他马尔可夫链提供了一种替代传统的基于电导率分析的方法。
• CHAR 分析： 该技术成功扩展到了 Coordinate Hit-and-Run，得出了显著改进的混合时间界限 $O(n^3 C_{PI} \log(M/\varepsilon))$，这被认为是渐近紧致的。

作者强调，与 Ball walk 具有不可避免的线性热度参数依赖不同，Hit-and-Run 在受益于改进的等周界限的同时，仍保留了对初始距离的对数依赖。