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

Overview§

This paper addresses a long-standing open problem in Markov chain Monte Carlo (MCMC) analysis: connecting the convergence rate of Hit-and-Run (H&R) to the Poincaré constant (or KLS constant) of the target distribution. For any convex body $\mathcal{K} \subset \mathbb{R}^n$ containing a unit ball, the authors prove that the spectral gap of H&R is $\Omega(1/(n^2 C_{\mathsf{PI}}))$, where $C_{\mathsf{PI}}$ is the Poincaré constant of the uniform distribution $\pi$ on $\mathcal{K}$. This refines the earlier $O(n^2 R^2 \log(M/\varepsilon))$ bound of Lovász and Vempala (2004) by replacing the outer radius $R$ with the Poincaré constant. For nearly isotropic bodies, the result combines with KLS breakthrough to yield $O(n^2 \log n \log(M/\varepsilon))$ mixing time, improving the dimension dependence from cubic to nearly quadratic.

Main Results§

• Spectral gap lower bound: $\mathrm{gap}(\mathrm{H\&R}) \ge \frac{c}{n^2 C_{\mathsf{PI}}}$ for an absolute constant $c>0$.
• Mixing time bound: From any starting distribution $\pi_0$ with $M = \chi^2(\pi_0 \| \pi)$, the $\chi^2$-divergence to $\pi$ drops below $\varepsilon$ in $O(n^2 C_{\mathsf{PI}} \log(M/\varepsilon))$ steps.
• Coordinate Hit-and-Run (CH&R): Similar technique yields mixing time $O(n^3 C_{\mathsf{PI}} \log(M/\varepsilon))$.

Unlike the Ball walk, H&R's mixing time does not degrade with the initial warmness constant, making it a more robust algorithm.

Proof Technique§

The key innovation is a dual formulation of the spectral gap. Let $\mathcal{P}$ be the H&R transition kernel and $\mathcal{L} = I - \mathcal{P}$ the Laplacian. The spectral gap is $$ \mathrm{gap} = \inf_{f \neq 0} \frac{\langle f, \mathcal{L} f \rangle_{\pi}}{\mathrm{Var}_\pi(f)}. $$ The authors rewrite this as a minimization over functions and then pass to the dual to obtain an equivalent constant related to the Babuška–Aziz constant from PDE analysis. This constant measures the stability of the divergence operator on the domain and is asymptotically bounded by the improved Poincaré constant $C_{\mathsf{PI}}^+$, itself bounded by $C_{\mathsf{PI}}$ up to constants.

The proof avoids the usual conductance-based arguments (e.g., Lovász–Vempala) and instead uses calculus of variations and duality, inspired by the recent analysis of the In-and-Out Markov chain.

Implications§

• Bridges the gap between H&R and Ball walk analyses; now both are governed by KLS/Poincaré constants.
• For near-isotropic convex bodies, the mixing time is $\tilde{O}(n^2)$, which is essentially optimal in the exponent (modulo constant factors).
• The technique may extend to other hit-and-run variants and to sampling from non-uniform log-concave distributions.

Code Snippet (Illustrative Hit-and-Run in Python)§

import numpy as np

def hit_and_run(log_density, n_samples, x0, step=1.0):
    samples = []
    x = x0.copy()
    for _ in range(n_samples):
        # Random direction uniformly on the sphere
        direction = np.random.randn(x.shape[0])
        direction /= np.linalg.norm(direction)
        # Find interval along line for which density is above a threshold (here: uniform on convex body)
        # For generic log-concave, use slice sampling or projection
        t_vals = np.linspace(-10, 10, 1000)
        import scipy.stats as stats
        # Example: uniform on a ball: accept if inside unit ball
        def in_body(x): return np.linalg.norm(x) <= 1.0
        line = x + t_vals[:, None] * direction[None, :]
        valid = [t for t, y in zip(t_vals, line) if in_body(y)]
        if len(valid) == 0:
            continue
        # Sample uniformly along the chord
        t = np.random.uniform(valid[0], valid[-1])
        x = x + t * direction
        samples.append(x.copy())
    return np.array(samples)

This snippet illustrates the core H&R step; the paper's analysis applies to this exact update for uniform distributions over convex bodies.

Conclusion§

By delivering a direct spectral gap lower bound tied to Poincaré constants, this paper resolves the open question and provides a powerful new analytic framework for MCMC convergence, with implications beyond H&R to coordinate samplers and functional inequalities.