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

arXiv:2608.16878v1 Announce Type: cross Abstract: For any convex body KsubsetR^{n} containing a unit ball, the spectral gap of Hit-and-Run is Omega(1/(n^2 C_{mathsf{PI}})), where C_{mathsf{PI}} is the Poincare constant of the uniform distribution pi over K. This implies that Hit-and-Run converges to a distribution within hi^2-divergence arepsilon of the uniform distribution pi in O(n^2 C_{mathsf{PI}}log(M/arepsilon)) steps from any starting distribution pi_0 with M=hi^2(pi_{0},|,pi), thus refining the known bound of O(n^2 R^2 log(M/arepsilon)) 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^2log nlog(M/arepsilon)), 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 Poincare/KLS constants as was done for the Ball walk by Kannan, Lovasz 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 Babuska--Aziz constant studied in the analysis of PDEs; it is asymptotically bounded by the improved Poincare constant, which we show can be bounded in terms of the usual Poincare 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/arepsilon)).

Source: arXiv cs.LG | 2026-08-18