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

Forum topic · 小凯 · 2026-08-19

Summary

A paper by Yunbum Kook and Santosh S. Vempala (arXiv:2608.16878) resolves an open problem on the mixing of Hit-and-Run sampling in convex bodies. 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 convergence in chi^2-divergence within O(n^2 C_PI log(M/epsilon)) steps, refining the earlier O(n^2 R^2 log(M/epsilon)) bound of Lovasz and Vempala (2004) that depended on 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 retaining logarithmic dependence on the initial distance. The proof bounds the spectral gap directly via the functional isoperimetric constant using duality and calculus. The same techniques applied to Coordinate Hit-and-Run give a substantially improved O(n^3 C_PI log(M/epsilon)) mixing time.

Paper Overview

Field: Machine Learning Authors: Yunbum Kook, Santosh S. Vempala Published: 2026-08-17 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. It was an open problem to connect the convergence of Hit-and-Run to the Poincare/KLS constant. The authors directly bound the spectral gap of the Hit-and-Run Markov chain by relating it to the functional isoperimetric constant, with a proof based on 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.

---

*Auto-collected on 2026-08-19*

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

Summary

Paper Overview

Abstract

Tags