PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yunbum Kook, Santosh S. Vempala

arXiv:2608.16878v1cs.DScs.LGmath.PRmath.ST

TL;DR

Hit-and-Run lacked a convergence-rate connection to Poincaré/KLS constants while preserving logarithmic warmness dependence. The paper uses functional isoperimetry and dual certificates to establish spectral-gap bounds, yielding mixing times of O(n^2 C_PI log(M/ε)) for Hit-and-Run and O(n^3 C_PI log(M/ε)) for Coordinate Hit-and-Run.

  • Problem

    Hit-and-Run had no known convergence-rate bound in terms of Poincaré/KLS constants while retaining logarithmic dependence on warmness.

  • Method

    The proof bypasses conductance by using functional isoperimetry and dual certificates linked through the Babuška–Aziz and Improved Poincaré constants.

  • Results

    O(n^2 C_PI log(M/ε)) and O(n^3 C_PI log(M/ε)) mixing-time bounds follow for Hit-and-Run and Coordinate Hit-and-Run, respectively.

  • Takeaways & Limitations

    The paper affirmatively connects both chains’ convergence rates to Poincaré/KLS-type constants while maintaining logarithmic warmness dependence.

  • Takeaways & Limitations

    The Ball walk has an unavoidable polynomial dependence on its warmness parameter, unlike the logarithmic warmness dependence targeted for Hit-and-Run.

Abstract

from arXiv · show

For any convex body $\mathcal{K}\subset\mathbb{R}^{n}$ containing a unit ball, the spectral gap of Hit-and-Run is $Ω(1/(n^2 C_{\mathsf{PI}}))$, where $C_{\mathsf{PI}}$ is the Poincaré constant of the uniform distribution $π$ over $\mathcal{K}$. This implies that Hit-and-Run converges to a distribution within $χ^2$-divergence $\varepsilon$ of the uniform distribution $π$ in $O(n^2 C_{\mathsf{PI}}\log(M/\varepsilon))$ steps from any starting distribution $π_0$ with $M=χ^2(π_{0}\,\|\,π)$, thus refining the known bound of $O(n^2 R^2 \log(M/\varepsilon))$ by Lovász 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/\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é/KLS constants as was done for the Ball walk by Kannan, Lovász 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 Babuška--Aziz constant studied in the analysis of PDEs; it is asymptotically bounded by the improved Poincaré constant, which we show can be bounded in terms of the usual Poincaré 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/\varepsilon))$.

1 Introduction

The paper establishes Poincaré/KLS-based spectral-gap bounds for Hit-and-Run and Coordinate Hit-and-Run while preserving logarithmic dependence on initial warmness. Its proof bypasses conductance by connecting spectral gaps to functional isoperimetry through dual certificates and the Babuška–Aziz constant.

  • Proof strategy: The proof bounds spectral gaps through functional isoperimetric constants, dual certificates, the Babuška–Aziz constant, and the Improved Poincaré constant.For bounded convex domains, C_BA ≤ 1 + 4C_IPI, while C_IPI ≲ n^2 C_PI for bodies containing a unit ball.
  • Main results: λHR ≳ 1/(n^2 C_PI(π)) and λCHAR ≳ 1/(n^3 C_PI(π)) for convex bodies containing a unit ball.These are the main spectral-gap guarantees for Hit-and-Run and Coordinate Hit-and-Run.
  • Main results: O(n^3 C_PI log(M/ε)) steps suffice for Coordinate Hit-and-Run to reach χ^2-divergence ε under the same initialization measure.The Coordinate Hit-and-Run guarantee is worse by a factor of n in the spectral-gap and mixing-time bounds.

2 Spectral gap via Babuška–Aziz constant

The section bounds Hit-and-Run’s spectral gap through the Babuška–Aziz constant using a dual certificate built from gradients. The same approach yields a Coordinate Hit-and-Run bound with an additional linear dependence on dimension.

  • Hit-and-Run: For θ drawn uniformly from the sphere, the dual certificate is gθ(x) = n θ^T∇u(x)θ.The construction uses u ∈ H1_0(K; Rn) satisfying div u = f.
  • Hit-and-Run: Compactly supported approximations and the fundamental theorem of calculus imply Pθgθ = 0, enabling the orthogonality relation ⟨Pθf, gθ⟩π = 0.The argument passes from smooth approximations to u by L2 convergence and conditional-expectation contraction.
  • Coordinate Hit-and-Run: λCHAR ≥ 1/(n CBA(π)), giving Coordinate Hit-and-Run a spectral-gap bound through the same constant.The coordinate certificates are gi = n ∂iui, whose sum equals div u = f, and a similar orthogonality argument applies.

3 Bounding the improved Poincaré constant

This section reduces the analysis to bounding the improved Poincaré constant in terms of the usual Poincaré constant. It establishes the needed bound for convex bodies containing an inscribed ball and derives a corollary based on the maximum inscribed-ball radius.

  • 3 Bounding the improved Poincaré constant: CBA ≤ 1 + 4CIPI for bounded convex domains, so it remains to control IPI by CPI.The section situates this reduction within prior work on distance-to-boundary-weighted improved Poincaré inequalities for John and convex domains.
  • 3 Bounding the improved Poincaré constant: Theorem 3.1 bounds the improved Poincaré constant for convex bodies containing a ball of radius r.The theorem applies to any locally Lipschitz function f : Rn → R.
  • 3 Bounding the improved Poincaré constant: Corollary 3.2 extends the resulting estimate to a convex body whose maximum inscribed ball has radius r.The corollary is stated directly for the maximum inscribed-ball radius.
  • 3 Bounding the improved Poincaré constant: The proof uses medians and positive and negative parts of f to reduce the theorem to a median-zero inequality.It applies the theorem to squared positive and negative parts and combines the resulting bounds.
  • 3 Bounding the improved Poincaré constant: The elementary geometric argument contracts K by roughly 1 − 1/n and uses lower bounds on the boundary distance inside the contracted body.The proof also uses the gauge function and the standard equivalence between L1 and L2-Poincaré constants for logconcave measures.

A Functional-analytic background

The appendix establishes the Hilbert-space, weak-derivative, Sobolev-space, and Markov-kernel framework used in the proof. It also defines stationarity and reversibility through Markov operators and self-adjointness.

  • Hilbert spaces: A real Hilbert space is complete under the norm induced by its inner product, and bounded linear maps have uniquely characterized adjoints.The adjoint T* satisfies ⟨Tf, g⟩G = ⟨f, T*g⟩F.
  • Weak derivatives: Weak derivatives are defined through integration by parts, are unique almost everywhere, and are stable under simultaneous L2 convergence of functions and derivatives.Compact support removes the boundary term in the defining identity.
  • Sobolev spaces: H1(K) consists of L2(K) functions whose coordinate weak derivatives are all in L2(K), and it is a complete Hilbert space.Its norm combines the function and derivative terms as specified in the appendix.
  • Sobolev spaces: H1_0(K) is the H1-closure of compactly supported smooth functions and encodes a zero boundary condition without requiring pointwise boundary values.Each function in the closure is approximated by compactly supported smooth functions in the H1 norm.
  • Actions on functions and measures: A Markov kernel assigns measurable transition probabilities, inducing both a Markov operator on functions and a one-step law transformation on measures.These are the two actions used to describe Markov-chain evolution.
  • Stationarity and reversibility: Reversibility of P with respect to π is equivalent to self-adjointness of P on L2(π), while stationarity means πP = π.Under stationarity, P preserves π-integrals and acts as a bounded linear operator on L2(π).

B From Babuška–Aziz constant to improved Poincaré constant

This section derives the Babuška–Aziz bound from a dual formulation, a Riesz-represented vector field, and a divergence calculus identity. The argument shows that the Babuška–Aziz constant is bounded by 1 + 4 times the improved Poincaré constant.

  • Duality: The Babuška–Aziz constant has equivalent primal and dual formulations involving solutions to div v = f and the adjoint divergence operator.The primal form controls ∥∇v∥2 relative to ∥f∥2, while the dual form controls ∥f∥Q relative to ∥div* f∥V.
  • Map to vector field: For each zero-mean f, the Riesz representation theorem gives a unique vector field u whose V-inner product represents v ↦ ⟨f, div v⟩Q.The map is bounded by |⟨f, div v⟩| ≤ √n ∥f∥2∥∇v∥2, and the supremum is attained at v = u.
  • Divergence identities: For h = f − div u and the antisymmetric matrix G associated with u, the argument establishes ∇h = div G and ⟨h, div u⟩Q = ∥G∥2.These identities connect the residual h to the antisymmetric part of the gradient and are used to control its norm.
  • Improved Poincaré estimate: ∥δ∇h∥2 ≤ 2∥G∥, and finite improved Poincaré constant CIPI implies ∥h∥2^2 ≤ 4CIPI∥G∥2.The proof uses regularization, integration by parts, antisymmetry of G, and the 1-Lipschitz property of the boundary distance δ.
  • Theorem 1.4: 1 + 4CIPI bounds the resulting quadratic form, yielding the theorem’s upper bound on the Babuška–Aziz constant.The decomposition combines the residual, divergence, and antisymmetric terms into (1 + 4CIPI)(∥div u∥2^2 + ∥G∥2).
Loading 2608.16878v1…