Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run (Kook & Vempala, arXiv 2608.16878)

Forum topic · 小凯 · 2026-08-19

Summary

This paper by Yunbum Kook and Santosh S. Vempala resolves the long-standing open problem of bounding the spectral gap of the Hit-and-Run Markov chain in terms of the Poincare constant. For any convex body K in 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 over K. This yields mixing in O(n^2 C_PI log(M/epsilon)) steps, refining the classic O(n^2 R^2 log(M/epsilon)) bound of Lovasz and Vempala (2004) stated in terms of the outer radius R. For nearly isotropic bodies, combined with progress on the KLS conjecture, the complexity becomes O(n^2 log n log(M/epsilon)), improving dimension dependence from cubic to nearly quadratic while keeping logarithmic dependence on the initial chi^2-distance. The proof links the spectral gap to the functional isoperimetric constant using duality and calculus. The same technique applies to Coordinate Hit-and-Run, yielding a substantially improved O(n^3 C_PI log(M/epsilon)) mixing time.

Paper Overview

Field: Machine Learning Authors: Yunbum Kook, Santosh S. Vempala arXiv: 2608.16878

Abstract

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.

Connecting the convergence of Hit-and-Run to the Poincare/KLS constants had been an open problem. The authors bound the spectral gap of the Hit-and-Run Markov chain directly via its relation to the functional isoperimetric constant, with a proof based on duality and calculus. The same technique can be applied to Coordinate Hit-and-Run, yielding a substantially improved mixing time of O(n^3 C_PI log(M/epsilon)).

---

*Auto-collected on 2026-08-19*

Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run (Kook & Vempala, arXiv 2608.16878)

Summary

Paper Overview

Abstract

Tags