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

arXiv: https://arxiv.org/abs/2608.16878 · HTML: https://mlsanity.com/paper/2608.16878/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 17 Aug 2026.

## Builds on (most cited first, 8 of 8)

- [In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies](https://mlsanity.com/paper/2405.01425/) (2024)
- [Sampling and Integration of Logconcave Functions by Algorithmic Diffusion](https://mlsanity.com/paper/2411.13462/) (2024)
- [Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast](https://mlsanity.com/paper/2009.11338/) (2020)
- [Zeroth-order Logconcave Sampling](https://mlsanity.com/paper/2507.18021/) (2025)
- [On the mixing time of coordinate Hit-and-Run](https://mlsanity.com/paper/2009.14004/) (2020)
- [A unified complexity bound for logconcave sampling](https://mlsanity.com/paper/2606.12694/) (2026)
- [The Localization Method for High-Dimensional Inequalities](https://mlsanity.com/paper/2512.10848/) (2025)
- [Sampling from convex sets with a cold start using multiscale decompositions](https://mlsanity.com/paper/2211.04439/) (2022)

## Built on by (most cited first, 2 of 2)

- [On two proofs of d2 mixing of weighted Dikin walks](https://mlsanity.com/paper/2608.28566/) (2026)
- [Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start](https://mlsanity.com/paper/2609.15884/) (2026)

## Abstract (arXiv)

For any convex body Ksubsetℝn containing a unit ball, the spectral gap of Hit-and-Run is Omega(1/(n2 C_mathsfPI)), where C_mathsfPI is the Poincar'e constant of the uniform distribution π over K. This implies that Hit-and-Run converges to a distribution within chi2-divergence varepsilon of the uniform distribution π in O(n2 C_mathsfPIlog(M/varepsilon)) steps from any starting distribution π0 with M=chi2(π0,|,π), thus refining the known bound of O(n2 R2 log(M/varepsilon)) by Lov'asz 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(n2log nlog(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'e/KLS constants as was done for the Ball walk by Kannan, Lov'asz 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 Babuvska--Aziz constant studied in the analysis of PDEs; it is asymptotically bounded by the improved Poincar'e constant, which we show can be bounded in terms of the usual Poincar'e 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(n3C_mathsfPIlog(M/varepsilon)).