---
title: "Hit-and-Run 马尔可夫链的谱隙：从三次到近二次的维度复杂度"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2608.16878v1"
permalink: "https://feed.astralor.com/items/itm_fdb3ec7b67bad9cce917d298"
published: "2026-08-17T17:57:11.000Z"
score: 76
channel: "ai"
tags: ["KLS猜想","凸体采样","谱隙","马尔可夫链蒙特卡洛"]
---

# Hit-and-Run 马尔可夫链的谱隙：从三次到近二次的维度复杂度

## AI 点评

> 这篇文章的价值在于把传统上依赖几何参数的 Mixing time 分析，推进到与函数不等式的内在常数绑定，理论上相当优雅。对做 MCMC、凸优化和概率推理的研究者来说，值得一读，尤其那些关注高维采样下界的人。

## 速览

本论文研究了凸体上的 Hit-and-Run 采样马尔可夫链。作者证明，对于包含单位球的任意凸体，其谱隙为 Ω(1/(n² C_PI))，其中 C_PI 为均匀分布的 Poincaré 常数；相应收敛到 χ² 散度 ε 的步数为 O(n² C_PI log(M/ε))，改进了 Lovász-Vempala 依赖外半径的旧界。结合 KLS 猜想的近期进展，近各向同性体上的复杂度可进一步降至 O(n² log n log(M/ε))，将维度依赖从三次压低到近二次。该证明基于对偶与函数等周常数技术，并同样适用于 Coordinate Hit-and-Run。

## 关键点

- 对于包含单位球的凸体，Hit-and-Run 的谱隙为 Ω(1/(n² C_PI))，与 Poincaré 常数直接关联。
- 收敛步数界为 O(n² C_PI log(M/ε))，在近各向同性体上借助 KLS 进展降至 O(n² log n log(M/ε))。
- 该证明基于对偶和微积分，而非传统电导法，并扩展到 Coordinate Hit-and-Run，混合时间 O(n³ C_PI log(M/ε))。

## 全文

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))$.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_fdb3ec7b67bad9cce917d298