---
title: "Spectral Gaps of Hit-and-Run: Reducing Dimension Complexity from Cubic to Nearly Quadratic"
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 conjecture","convex body sampling","spectral gap","Markov chain Monte Carlo"]
---

# Spectral Gaps of Hit-and-Run: Reducing Dimension Complexity from Cubic to Nearly Quadratic

## AI commentary

> This paper elegantly shifts the mixing-time analysis of Hit-and-Run from geometric parameters to intrinsic functional inequality constants. It is valuable for researchers in MCMC, convex optimization, and probabilistic inference, especially those working on high-dimensional sampling lower bounds.

## At a glance

This paper studies the Hit-and-Run Markov chain for sampling from convex bodies. The authors prove that for any convex body containing a unit ball, the spectral gap is Ω(1/(n² C_PI)), where C_PI is the Poincaré constant of the uniform distribution. This yields convergence to within χ² divergence ε in O(n² C_PI log(M/ε)) steps from any starting distribution, refining the earlier O(n² R² log(M/ε)) bound of Lovász and Vempala that depends on the outer radius R. For nearly isotropic bodies, combined with progress on the KLS conjecture, the complexity becomes O(n² log n log(M/ε)), improving the dimension dependence from cubic to nearly quadratic. The proof connects the spectral gap to functional isoperimetric constants via duality and calculus, unlike previous conductance-based arguments. The same technique also applies to Coordinate Hit-and-Run, giving a much improved mixing time O(n³ C_PI log(M/ε)).

## Key points

- For any convex body containing a unit ball, the spectral gap of Hit-and-Run is Ω(1/(n² C_PI)), directly linked to the Poincaré constant.
- The mixing time is O(n² C_PI log(M/ε)), improving to O(n² log n log(M/ε)) for nearly isotropic bodies using recent KLS progress.
- The proof relies on duality and calculus rather than conductance, and extends to Coordinate Hit-and-Run with mixing time O(n³ C_PI log(M/ε)).

## Full text

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

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_fdb3ec7b67bad9cce917d298