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

Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run Yunbum Kook University of Michigan ybkook@umich.edu

Santosh S. Vempala Georgia Tech vempala@gatech.edu

August 18, 2026

arXiv:2608.16878v1 [cs.DS] 17 Aug 2026

Abstract For any convex body K ⊂ Rn containing a unit ball, the spectral gap of Hit-and-Run is Ω(1/(n2 CPI )), where CPI is the Poincaré constant of the uniform distribution π over K. This implies that Hit-and-Run converges to a distribution within χ2 -divergence ε of the uniform distribution π in O(n2 CPI log(M/ε)) steps from any starting distribution π0 with M = χ2 (π0 ∥ π), thus refining the known bound of O(n2 R2 log(M/ε)) 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(n2 log n log(M/ε)), 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 first 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 of the target distribution, 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(n3 CPI log(M/ε)).

AI disclosure: A preliminary version of the main technique/proof/figure was suggested by GPT 5.6 Pro through guided prompting by the first author. The authors then verified, streamlined and wrote the full proof. 1

1

Introduction

Sampling a convex body is a fundamental algorithmic problem. Hit-and-Run, proposed independently by Boneh and Golan [BG79] and Smith [Smi84], is the following Markov chain (see Figure 1.1) when applied to a convex body K ⊂ Rn : at a current point x ∈ K, 1. Sample a uniformly distributed random line ℓ through x. 2. Go to a uniform random point on the chord ℓ ∩ K. Hit-and-Run is an attractive, easy-to-implement process that has been widely used in practice. Coordinate Hit-and-Run (CHAR), also known as Gibbs sampling and introduced in 1971 [Tur71], is the variant that only uses axis-parallel chords and is also popular due to its low memory overhead. Building on the seminal work of [Lov99], Lovász and Vempala [LV06a] showed that Hit-and-Run mixes from a cold start: in any convex body K ⊂ Rn with B n ⊆ K ⊆ RB n , it outputs a point within χ2 -divergence ε of the uniform distribution over K in O(n2 R2 log(M/ε)) steps from any starting distribution within χ2 -divergence M of the target. This convergence rate is asymptotically optimal in terms of these parameters, as shown by a cylinder whose cross section is a unit ball and axis has length 2R. It also means that Hit-and-Run mixes rapidly from any interior starting point (by applying the convergence bound to the distribution obtained after taking one step), the first random walk known to have this property for arbitrary convex bodies. More recently, CHAR was shown to have (higher) polynomial convergence rates [LV23, NS22, NRS25], with the last paper showing logarithmic dependence on the warm start parameter. The study of efficiently sampling convex bodies has made much progress over the past few decades, starting from an initial polynomial-time algorithm with complexity n23 by Dyer, Frieze, and Kannan [DFK91]. The Ball walk introduced by Lovász [Lov90] has been particularly fruitful, leading to the current best complexity for sampling, general techniques for the analysis of Markov chains [LS90, LS93, KLS97, LV07], and novel classes of isoperimetric inequalities. One highlight is the Kannan–Lovász–Simonovits (KLS) conjecture [KLS95] which posits that halfspaces are asymptotically optimal isoperimetric cuts for convex bodies (and logconcave densities). The conjecture directly leads to a better bound on the convergence rate of the Ball walk, and has several other interesting mathematical consequences and connections. Another highlight is the localization method, first developed by Kannan, Lovász, and Simonovits [LS93, KLS95] to prove inequalities in high dimension and later generalized to a stochastic method by Eldan [Eld13]. For a more comprehensive account of these developments, we refer the reader to [Vem05, KV25a]. The Ball walk has a polynomial dependence on the warmness parameter1 , and this is unavoidable. To get around this, researchers have developed algorithmic solutions, notably annealing [LV06b, KV06, CV18], to arrange an O(1)-warm start. From such a warm start, the Ball walk’s convergence rate is roughly n2 ∥cov∥op ψn2 , where ∥cov∥op is the operator norm√of the covariance of the target distribution, and ψn is the KLS constant, which is known to be O( log n) and is conjectured to be O(1). This is always a better bound than n2 R2 and is asymptotically better by a factor of n when the target is isotropic (i.e., ∥cov∥op = 1). Note that for convex bodies and logconcave densities, we have CPI ≃ ∥cov∥op ψn2 , where the RHS is the squared reciprocal of the Cheeger constant. On the other hand, despite its logarithmic dependence on the warmness parameter, there was no known connection between the convergence of Hit-and-Run and the KLS constant. Thus, a decade of progress on the latter, leading to improved complexities for sampling (near-)isotropic convex bodies, did not refine the bound for Hit-and-Run. Unlike the Ball walk, whose analysis directly uses Euclidean isoperimetry, the analysis of Hit-and-Run was based on an average isoperimetric inequality for the 1

In fact, the Ball walk uses a more stringent notion of warmness, namely dπ0 /dπ ≤ M .

2

Hit-and-Run

Coordinate Hit-and-Run ℓ

y ℓi x

x

y

y ∼ Unif(ℓi ∩ K)

y ∼ Unif(ℓ ∩ K)

Figure 1.1: Left: A HAR kernel at x ∈ K chooses a random line ℓ through x and samples y uniformly from the chord ℓ ∩ K. Right: A CHAR kernel chooses an axis-parallel line ℓi through x and samples y uniformly from the chord ℓi ∩ K. cross-ratio distance, and the latter was already the best possible. Thus, it remained a tantalizing open problem to bridge the analysis of Hit-and-Run with improved isoperimetric constants. Chen and Eldan [CE26] made a conceptually important breakthrough, showing that for isotropic convex bodies, the convergence rate is indeed nearly quadratic in the dimension, albeit with a polynomial dependence on initial warmness and the distance to the target. Interestingly, their proof technique, called a localization scheme [CE25], used a stochastic localization process to reduce the analysis from general convex bodies to that of a highly concentrated Gaussian restricted to a convex body; this general stochastic technique has also been the driving force for much of the progress in bounding the KLS constant. So, although they lost the logarithmic dependence on the warmness parameter, they showed that the conjectured dimension dependence is indeed plausible and valid in the isotropic setting. Recent work [KVZ26, KV25b, KV25c] took a different approach inspired by continuous diffusion, and showed that the In-and-Out random walk has a convergence rate that matches the best-known bounds for the Ball walk, with stronger output guarantees and, importantly, a novel proof framework that directly connects convergence (in fact, per-step contraction towards the target) with functional isoperimetric constants of the target distribution. Nevertheless, In-and-Out also has an unavoidable linear dependence on the warmness parameter, highlighting the open problem about Hit-and-Run: Can the convergence rate of Hit-and-Run be bounded by the Poincaré/KLS constants while maintaining its logarithmic dependence on the warmness parameter? In this paper, we answer this question affirmatively for both Hit-and-Run and CHAR. The proof technique bypasses the traditional method of bounding the conductance and directly connects the convergence rate to functional isoperimetric constants. The main high-level idea of the proof is to produce a dual certificate bounding the spectral gap. Rewriting the spectral gap first in terms of dual certificates leads to the Babuška–Aziz constant [BA72, HP83] studied in the analysis of PDEs; for bounded domains, this is known to be asymptotically bounded by the Improved Poincaré constant of the target density. The latter is a refined version of the classical Poincaré constant, incorporating distance to the boundary as a weight function for points in the domain [HS94, Cos17, Zsu20]. We show that this constant can be bounded in terms of the usual Poincaré constant for convex bodies resulting in a mixing time bound of O(n2 CPI log(M/ε)). Applying this to CHAR, with the only change being in the first step of connecting the spectral gap to the Babuška–Aziz constant, results in a mixing time bound of O(n3 CPI log(M/ε)), which is conjectured to be asymptotically tight. We note that under this new analytical framework, the proofs for Hit-and-Run and CHAR are essentially the same. We discuss the proof techniques in more detail after stating the main results. 3

1.1

Results

Below, CPI (π) denotes the Poincaré constant of a probability measure π, formally defined in §1.2. Theorem 1.1 (Spectral gaps). Let n ≥ 2 and K ⊂ Rn be a bounded, open, and convex set with unit ball inside, and let π be the uniform distribution over K. Then, the spectral gaps of Hit-and-Run and Coordinate Hit-and-Run satisfy λHR ≳

1 n2 C

PI (π)

≳

1 n2 ∥cov π∥op log n

,

λCHAR ≳

1 n3 C

PI (π)

≳

1 n3 ∥cov π∥op log n

.

HR and π CHAR be Corollary 1.2 (Mixing time). Under the assumptions of Theorem 1.1, let πN N the distribution of the N -th iterate of Hit-and-Run and Coordinate Hit-and-Run initialized at π0 , respectively. Then, for some universal constant c > 0 HR χ2 (πN ∥ π) ≤ exp − CHAR χ2 (πN ∥ π) ≤ exp −

cN n2 ∥cov π∥op log n cN n3 ∥cov π∥op log n

2 χ (π0 ∥ π) ,
2 χ (π0 ∥ π) .

In particular, for given ε > 0, the number of iterations for Hit-and-Run and Coordinate Hit-and-Run to achieve ε-distance to π in χ2 -divergence is bounded as NHR ≲ n2 ∥cov π∥op log n log

1.2 1.2.1

χ2 (π0 ∥ π) , ε

NCHAR ≲ n3 ∥cov π∥op log n log

χ2 (π0 ∥ π) . ε

Technical overview Preliminaries

We recall the functional-analytic facts used later, with more details in §A. Basics. Throughout the paper, we use the same symbol to denote a probability measure and dx its Lebesgue density when it is clear from context, and dπ(x) = vol K denotes the uniform measure R n 2 2 ], and L2 (π) := {f ∈ L2 (π) : f g on K ⊂ R . We write ⟨f, g⟩ := dπ, ∥f ∥ := ⟨f, f ⟩ = E [f π π π 2 0 K R 2 2 K f dπ = 0}, Rthe set of centered L functions. The mean and variance of f ∈ L (π) are denoted as πf := Eπ f = K f dπ and Varπ f = ∥f − πf ∥22 . R R A function f ∈ L2 (K) has weak derivative ∂j f ∈ L2 (K) if K f ∂j φ dx = − K (∂j f ) φ dx for every φ ∈ Cc∞ (K). The Sobolev space H 1 (K) consists of the L2 functions whose weak derivatives belong to L2 . Recall that it is a Hilbert space with ⟨f, g⟩H 1 = ⟨f, g⟩L2 + ⟨∇f, ∇g⟩L2 . We denote the closure H 1 (K)

of compactly-supported smooth functions with respect to the H 1 -norm by H01 (K) := Cc∞ (K) . Pn 1 n 1 n 2 2 For a vector field u = (u1 , . . . , un ), we use H (K; R ) := H (K) and ∥∇u∥2 = i,j=1R∥∂j ui ∥2 . P For u ∈ H 1 (K; Rn ), its weak divergence is div u := ni=1 ∂i ui ∈ L2 (K). Equivalently, K (div u) φ dx = R − K u · ∇φ dx for any φ ∈ C ∞ (K). If u ∈ H01 (K; Rn ), approximation by compactly supported R c smooth vector fields gives K div u dπ = 0. Functional inequalities. For δ(x) := dist(x, ∂K) = miny∈∂K |x − y| and a probability measure π over K, its Poincaré constant and improved Poincaré constant are defined as the smallest constants satisfying that for any test function f ∈ H 1 (K), Varπ f ≤ CPI (π)

Z

Varπ f ≤ CIPI (π) 4

ZK K

|∇f |2 dπ ,

(PI)

δ 2 |∇f |2 dπ .

(IPI)

Dirichlet form and spectral gap. Let G be a sub-σ-algebra of the Borel σ-algebra on K. Recall that the conditional expectation PG f := Eπ [f | G] is the orthogonal projection of L2 (π) onto the closed subspace of G-measurable functions: PG∗ = PG ,

PG2 = PG ,

⟨f, (Id − PG )f ⟩π = ∥f − PG f ∥22 .

(1.1)

For a π-reversible Markov operator P , its Dirichlet form is EP (f, f ) := ⟨f, (Id − P )f ⟩π , and the spectral gap of P is defined as EP (f, f ) λP := inf 2 . 2 0̸=f ∈L0 (π) ∥f ∥2 0 A positive spectral gap of positive semidefinite P implies contraction in χ2 -divergence: if q0 = dµ dπ 2 N belongs to L (π) and µN = µ0 P ,

χ2 (µN ∥ π) = ∥P N (q0 − 1)∥22 ≤ (1 − λP )2N χ2 (µ0 ∥ π) ≤ exp(−2 λP N ) χ2 (µ0 ∥ π) . 1.2.2

(1.2)

Proof ideas

We will define a bounded linear operator T : F → G for two Hilbert spaces F and G so that ∥f ∥2F and ∥T f ∥2G correspond to ∥f ∥22 and EP (f, f ) in our setting, respectively. Then, our goal is to establish ∥T f ∥2G ≥ λ∥f ∥2F for some λ > 0. A natural dual approach is to find, for each f ∈ F , a dual-certificate gf ∈ G such that T ∗ gf = f for the adjoint T ∗ : G → F . If the certificate also satisfies ∥gf ∥2G ≤ C ∥f ∥2F , then √ ∥f ∥2F = ⟨f, f ⟩F = ⟨f, T ∗ gf ⟩F = ⟨T f, gf ⟩G ≤ ∥T f ∥G ∥gf ∥G ≤ C ∥T f ∥G ∥f ∥F , which implies ∥f ∥2F ≤ C ∥T f ∥2G , and it leads to λ ≥ C −1 . In summary, we should tackle two concrete problems: (i) find the dual certificate gf such that T ∗ gf = f , and (ii) show ∥gf ∥2G ≤ C ∥f ∥2F for some C > 0. We now illustrate the main idea through Coordinate Hit-and-Run, whose finite product structure makes the adjoint transparent. Fix an orthonormal basis e1 , . . . , en , and let Pi be conditional expectation given all coordinates except the i-th one; equivalently, Pi f is the uniform average of f on each ei -parallel chord. By (1.1), PCHAR =

n 1X Pi , n i=1

ECHAR (f, f ) := ⟨f, (Id − PCHAR )f ⟩π =

n 1X ∥f − Pi f ∥22 . n i=1

In this case, we can take F := L20 (π) and G := {g = (g1 , . . . , gn ) : gi ∈ L2 (π)} with norm P ∥f ∥2F = ∥f ∥22 and ∥g∥2G = n1 ni=1 ∥gi ∥22 . Also, we define T : F → G by (T f )i = (Id − Pi )f for i ∈ [n], so ∥T f ∥2G = ECHAR (f, f ) as desired. Let us now compute the adjoint T ∗ . For g = (g1 , . . . , gn ) ∈ G, using Pi = Pi∗ , 1X 1X ⟨T f, g⟩G = ⟨(Id − Pi )f, gi ⟩π = ⟨f, (Id − Pi )gi ⟩π . n i n i Hence, T ∗ g = n1 i (Id − Pi )gi . With the dual-certificate approach in mind, we address the first problem of finding g such that ∗ T g = f . To this end, we could consider two sufficient conditions given as P

Pi gi = 0

for i ∈ [n]

&

5

n 1X gi = f . n i=1

A convenient way to enforce the first condition is to set gi = n ∂i ui for each i ∈ [n] for some u ∈ H01 (K; Rn ) extended by zero outside of K. Indeed, for a.e. z ∈ e⊥ i , if Iz := {s ∈ R : z + sei ∈ K}, then for t ∈ Iz , the fundamental theorem of calculus leads to (Pi gi )(z + tei ) =

n |Iz |

Z

∂i ui (z + sei ) ds = 0 . Iz

Then, the second condition corresponds to div u = f . In summary, the first problem comes down to finding u ∈ H01 (K; Rn ) such that div u = f . We now address the second problem of showing ∥g∥2G ≤ C ∥f ∥2F for some C. Since ∥g∥2G =

n n X 1X ∥gi ∥22 = n ∥∂i ui ∥22 ≤ n ∥∇u∥22 , n i=1 i=1

the second problem can be reduced to the following optimization problem: among functions u with div u = f , find a function u that minimizes ∥∇u∥22 . Namely, one should minimize the Frobenius norm ∥∇u∥2 with trace constraint div u = tr(∇u) = f . This is where the Babuška–Aziz constant comes in: ∥∇u∥22 CBA (π) := sup inf 2 . 1 n 0̸=f ∈L2 (π) u∈H0 (K;R ) ∥f ∥2 0

div u=f

The minimizer satisfies div u = f and ∥∇u∥22 ≤ CBA (π) ∥f ∥22 . Consequently, ∥g∥2G ≤ nCBA (π) ∥f ∥2F , 1 and the dual argument gives λCHAR ≥ nCBA (π) . We formalize this functional analytic result as follows. Lemma 1.3. Suppose CBA (π) < ∞. Then, for every f ∈ L20 (π), there exists u ∈ H01 (K; Rn ) such that div u = f , and ∥∇u∥22 ≤ CBA (π) ∥f ∥22 . (1.3) Proof. Finiteness of CBA (π) makes the feasible set in the inner infimum nonempty. Equip H01 (K; Rn ) with the norm ∥∇u∥2 . By the Poincaré inequality for H01 (K; Rn ), this is an equivalent Hilbert norm √ on H01 (K; Rn ). Since ∥div u∥2 ≤ n ∥∇u∥2 , it follows that div : H01 (K; Rn ) → L20 (π) is a bounded linear operator (so continuous). Hence, div−1 ({f }) = {u ∈ H01 (K; Rn ) : div u = f } is a nonempty closed convex subset of H01 (K; Rn ). By the Hilbert projection theorem, the infimum in the definition of CBA (π) is attained, and its minimizer satisfies (1.3). In §2, we formally bound the spectral gaps of HAR and CHAR in terms of the Babuška–Aziz constant of the target distribution. Notably, the spectral-gap bound for CHAR is smaller by a factor of the dimension. The rest of the analysis is independent of the Markov chain and will apply to both HAR and CHAR. The next step is the following result from [Zsu20] which relates the Babuška–Aziz constant to the Improved Poincaré constant. We give a self-contained proof of this in §B. Theorem 1.4. For a bounded convex domain in Rn , we have CBA ≤ 1 + 4CIPI . Then, in §3, we show that CIPI (π) ≲ n2 CPI (π) for a convex body containing a unit ball (Theorem 3.1 and Corollary 3.2). These ingredients suffice to prove the main results.

6

1.3

Proof of main result

Proof of Theorem 1.1. Note that CPI (π) ≥ ∥cov π∥op ≳ 1/n when B(0, 1) ⊂ K (see [KV26, Lemma 2.1]). By applying Propositions 2.1 and 2.2 with Theorem 1.4 (CBA ≤ 1 + 4CIPI ) and Corollary 3.2 (CIPI ≲ n2 CPI /r2 with r = 1), 1

λHR ≳

n2 C

PI (π)

,

λCHAR ≳

1 n3 C

PI (π)

.

Using CPI (π) ≲ ∥cov π∥op log n [Kla23], we complete the proof. Proof of Corollary 1.2. This follows from the spectral-gap results in Theorem 1.1 and (1.2).

2

Spectral gap via Babuška–Aziz constant

2.1

Hit-and-Run

Let σ be uniform probability measure on Sn−1 . For θ ∈ Sn−1 , let Pθ be conditional expectation with respect to the orthogonal projection onto θ⊥ , so Pθ f is the uniform average of f on each θ-parallel chord. Then, Z

PHR =

Sn−1

Pθ dσ(θ) ,

EHR (f, f ) = ⟨f, (Id − PHR )f ⟩π =

Z Sn−1

∥f − Pθ f ∥22 dσ(θ) .

For θ drawn from Sn−1 , the natural dual certificate is gθ (x) := n θT ∇u(x)θ. Proposition 2.1. If CBA (π) < ∞, then n+2 1 ≳ . n (2 + CBA (π)) 1 + CBA (π)

λHR ≥

Proof. Fix f ∈ L20 (π), and pick u ∈ H01 (K; Rn ) given by Lemma 1.3 that satisfies div u = f and ∥∇u∥22 ≤ CBA (π) ∥f ∥22 . For θ ∈ Sn−1 , define gθ (x) := n θT ∇u(x) θ

for a.e. x ∈ K .

Let u ∈ H01 (K; Rn ) and choose uk ∈ Cc∞ (K; Rn ) converging to u in H 1 . Define gθ,k := n θT ∇uk θ. The fundamental theorem of calculus on every θ-parallel line gives Pθ gθ,k = 0, because uk is compactly supported. Since gθ,k → gθ in L2 (π) and conditional expectation is an L2 contraction, Pθ gθ = limk→∞ Pθ gθ,k = 0 in L2 . Hence, 0 = ⟨f, Pθ gθ ⟩π = ⟨Pθ f, gθ ⟩π . Recall that for a square matrix M , rotational invariance of dσ(θ) gives 1 Id , n (tr M )2 + 2 ∥sym M ∥2F Eθ [(θT M θ)2 ] = , n (n + 2) Eθ [θθT ] =

where the second identity follows from E[θi θj θk θℓ ] = Z Sn−1

(2.2)

δij δkℓ +δik δjℓ +δiℓ δjk . By (2.1) and div u = f , n (n+2)

gθ dσ(θ) = tr ∇u = f . 7

(2.1)

Therefore, using ⟨Pθ f, gθ ⟩π = 0 and Cauchy–Schwarz, ∥f ∥22 =

Z Sn−1

⟨f, gθ ⟩π dσ(θ) =

∥f ∥42 ≤ EHR (f, f )

Z Sn−1

Z Sn−1

⟨f − Pθ f, gθ ⟩π dσ(θ) ,

∥gθ ∥22 dσ(θ) .

(2.3)

For a square matrix M , we denote its symmetrization by sym M := (M + M T )/2. By integration by parts, for u ∈ H01 (K; Rn ), 2 ∥sym ∇u∥22 = ∥∇u∥22 + ∥div u∥22 ,

(2.4)

since the cross term satisfies i,j K (∂j ui )(∂i uj ) dπ = K (div u)2 dπ. Applying (2.2) to M = ∇u, and then using (2.4), div u = f , and ∥∇u∥22 ≤ CBA (π) ∥f ∥22 , we obtain R

P

Z Sn−1

R

n n Eπ [(div u)2 + 2 ∥sym ∇u∥2F ] = (∥f ∥22 + 2 ∥sym ∇u∥22 ) n+2 n+2
n 2 + CBA (π) ≤ ∥f ∥22 . n+2

∥gθ ∥22 dσ(θ) =

Substitution into (2.3) gives EHR (f, f ) ≥

n+2
∥f ∥22 . n 2 + CBA (π)

Taking the infimum over nonzero f ∈ L20 (π) completes the proof.

2.2

Coordinate Hit-and-Run

Proposition 2.2. If CBA (π) < ∞, then λCHAR ≥

1 . nCBA (π)

Proof. Fix f ∈ L20 (π) and let u be given by Lemma 1.3. For i = 1, . . . , n, set gi := n ∂i ui and note P that n1 ni=1 gi = div u = f . A similar argument in the proof of Proposition 2.1 gives Pi gi = 0, and thus 0 = ⟨f, Pi gi ⟩π = ⟨Pi f, gi ⟩π . Then, ∥f ∥22 =

n n 1X 1X ⟨f, gi ⟩π = ⟨f − Pi f, gi ⟩π , n i=1 n i=1 n X

n X

n i=1

i=1

1 ∥f ∥42 ≤ ECHAR (f, f ) By Lemma 1.3,

n X

∥gi ∥22 = n ECHAR (f, f )

∥∂i ui ∥22 .

(2.5)

∥∂i ui ∥22 ≤ ∥∇u∥22 ≤ CBA (π) ∥f ∥22 .

i=1 1 2 Substitution into (2.5) gives ECHAR (f, f ) ≥ nCBA (π) ∥f ∥2 , and taking the infimum over nonzero f ∈ L20 (π) finishes the proof.

8

3

Bounding the improved Poincaré constant

Since CBA ≤ 1 + 4CIPI for a bounded convex domain (Theorem 1.4), we are only left with bounding the improved Poincaré constant (IPI) in terms of the usual Poincaré constant. Before we proceed, we briefly survey prior work on (IPI). Improved Poincaré inequalities with the distance to the boundary as a weight have been studied for John domains (which include convex domains), starting with [HS94] and further developed in [DD08, CW10]. In particular, for convex domains, [CW10] gives a quantitative bound in terms of the eccentricity of the domain. In our notation, this implies CIPI (π) ≤ C(n) R2 /r2 , where R and r denote the outer-radius and in-radius of the domain, respectively, and the dimension dependence is absorbed into C(n). For our application, we need a bound in terms of the ordinary Poincaré constant with explicit dimension dependence, so in Corollary 3.2 we show CIPI (π) ≲ n2 CPI (π)/r2 . Theorem 3.1. For any locally Lipschitz function f : Rn → R and a convex body K ⊂ Rn containing a ball of radius r, we have p

n CPI (π) inf |f (x) − z| dx ≲ z r K Z

Z

δ(x) |∇f | dx .

K

This gives the following immediate corollary: Corollary 3.2. For a convex body K in Rn whose maximum inscribed ball has radius r, we have CIPI (π) ≲

n2 CPI (π) . r2

Proof. Since C ∞ (Rn )|K is dense in H 1 (K), it suffices to prove the claim for f ∈ C ∞ (Rn )|K . Then, Theorem 3.1 holds with z set to the median of f , i.e., for any g : Rn → R with median 0, we have p

n CPI (π) |g(x)| dx ≲ r K

Z

Z

δ(x) |∇g| dx .

K

Now set u(x) := (f (x) − zf )+ where zf is the median of f and apply the above to g = u2 . Then, 0 is the median of g. Denoting C := nCPI (π)1/2 /r, we have Z K

u2 dx ≲ C

Z

δ(x) u |∇u| dx ≤ C

Z

K

u2 dx

1/2 Z

K

1/2

δ(x)2 |∇u|2 dx

.

K

Hence, K u2 dx ≲ C 2 K δ(x)2 |∇u|2 dx. We get the same conclusion with v = (zf − f (x))+ in place of u. Adding these, R

R

n2 CPI (π) Varπ f ≤ (f − zf ) dπ ≲ r2 K Z

2

Z

δ(x)2 |∇f |2 dπ ,

K

which completes the proof. We now give an elementary proof of the theorem. Proof of Theorem 3.1. We may assume that B(0, r) ⊂ K by translation. The idea is just that since K contains a ball of radius r, we will consider a slight contraction of K by roughly (1 − 1/n). Set 1 α = 1 − 2n , and note that Z

inf z

K

|f (x) − z| dx ≤

Z

|f (x) − f (αx)| dx + inf z

K

9

Z K

|f (αx) − z| dx .

p

For the first term, since the diameter of isotropic convex bodies is at most n(n + 2) ≤ n + 1 1/2 [KLS95, Theorem 4.1], we have supK |x| ≲ n ∥cov π∥op ≤ nCPI (π)1/2 . Hence, for the gauge function ∥x∥K := inf{t > 0 : x ∈ tK}, Z

|f (x) − f (αx)| dx ≤

K

Z Z 1 K α

p

|x| |∇f (tx)| dtdx ≲ n CPI

p

= n CPI

Z Z

p

Z

Z 1

−n

Z

t α

|∇f (y)| dydt

tK

t−n dtdy

max{α,∥y∥K } Z 1 −n

K

p

≤ n CPI

|∇f (y)|

Z 1

|∇f (y)| α

dtdy

max{α,∥y∥K }

K

≤ n CPI |∇f (y)| · 2 (1 − ∥y∥K ) dy K √ Z n CPI δ(y) |∇f (y)| dy , ≲ r K where in the last line, we used δ(y) ≥ r (1 − ∥y∥K ), since ∥y∥K K + (1 − ∥y∥K ) B(0, r) ⊂ K. For the second term, using the standard equivalence between the L1 and L2 -Poincaré constants for logconcave measures, and noting that the constant is α2 CPI for αK, √ Z Z Z Z p n CPI −n −n inf |f (αx)−z| dx = α inf |f (x)−z| dx ≤ α α CPI |∇f | dx ≲ δ(x) |∇f | dx , z z r K αK αK αK r where we used δ(x) ≥ 2n for x ∈ αK. The theorem follows by adding these two bounds.

Acknowledgement. This work was supported in part by NSF Awards CCF-2504995, CCF-2236669, CCF-2504994, and a Simons Investigator award. The second author is grateful to Laci Lovász for many inspiring discussions on the problem.

References [BA72]

Ivo Babuška and Abdul K. Aziz. Survey lectures on the mathematical foundations of the finite element method. In The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations (Proc. Sympos., Univ. Maryland, Baltimore, Md., 1972), pages 1–359. Academic Press, New York, 1972. With the collaboration of G. Fix and R. B. Kellogg.

[BG79]

Arnon Boneh and A. Golan. Constraints’ redundancy and feasible region boundedness by random feasible point generator (RFPG). In Third European congress on operations research (EURO III), Amsterdam, 1979.

[CE25]

Yuansi Chen and Ronen Eldan. Localization schemes: a framework for proving mixing bounds for Markov chains. Duke Mathematical Journal, 174(8):1431–1510, 2025.

[CE26]

Yuansi Chen and Ronen Eldan. Hit-and-Run mixing via localization schemes. Discrete & Computational Geometry, 75(3):747–794, 2026.

[Cos17]

Martin Costabel. Inequalities of Babuška–Aziz and Friedrichs–Velte for differential forms. In Vladimir Maz’ya, David Natroshvili, Eugene Shargorodsky, and Wolfgang L. Wendland, editors, Recent Trends in Operator Theory and Partial Differential Equations, volume 258 of Operator Theory: Advances and Applications, pages 79–88. Birkhäuser, Cham, 2017.

[CV18]

Ben Cousins and Santosh S. Vempala. Gaussian cooling and O∗ (n3 ) algorithms for volume and Gaussian volume. SIAM Journal on Computing, 47(3):1237–1273, 2018.

[CW10]

Seng-Kee Chua and Richard L. Wheeden. Weighted Poincaré inequalities on convex domains. Mathematical Research Letters, 17(5):993–1011, 2010.

10

[DD08]

Irene Drelichman and Ricardo G. Durán. Improved Poincaré inequalities with weights. Journal of Mathematical Analysis and Applications, 347(1):286–293, 2008.

[DFK91] Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM, 38(1):1–17, 1991. [Eld13]

Ronen Eldan. Thin shell implies spectral gap up to polylog via a stochastic localization scheme. Geometric and Functional Analysis, 23(2):532–569, 2013.

[Eva10]

Lawrence C. Evans. Partial differential equations, volume 19 of Graduate Studies in Mathematics. American Mathematical Society, second edition, 2010.

[HP83]

Cornelius O. Horgan and Lawrence E. Payne. On inequalities of Korn, Friedrichs and Babuška-Aziz. Archive for Rational Mechanics and Analysis, 82(2):165–179, 1983.

[HS94]

Ritva Hurri-Syrjänen. An improved Poincaré inequality. Proceedings of the American Mathematical Society, 120(1):213–222, 1994.

[Kla23]

Bo’az Klartag. Logarithmic bounds for isoperimetry and slices of convex sets. Ars Inveniendi Analytica, (4):1–17, 2023.

[KLS95]

Ravi Kannan, László Lovász, and Miklós Simonovits. Isoperimetric problems for convex bodies and a localization lemma. Discrete & Computational Geometry, 13(3):541–559, 1995.

[KLS97]

Ravi Kannan, László Lovász, and Miklós Simonovits. Random walks and an O∗ (n5 ) volume algorithm for convex bodies. Random Structures & Algorithms, 11(1):1–50, 1997.

[KV06]

Adam T. Kalai and Santosh S. Vempala. Simulated annealing for convex optimization. Mathematics of Operations Research, 31(2):253–266, 2006.

[KV25a]

Yunbum Kook and Santosh S. Vempala. The localization method for high-dimensional inequalities. arXiv preprint arXiv:2512.10848, 2025.

[KV25b]

Yunbum Kook and Santosh S. Vempala. Sampling and integration of logconcave functions by algorithmic diffusion. In Symposium on Theory of Computing, pages 924–932. ACM, 2025.

[KV25c]

Yunbum Kook and Santosh S. Vempala. Zeroth-order logconcave sampling. arXiv preprint arXiv:2507.18021, 2025.

[KV26]

Yunbum Kook and Santosh S. Vempala. A unified complexity bound for logconcave sampling. arXiv preprint arXiv:2606.12694, 2026.

[KVZ26] Yunbum Kook, Santosh S. Vempala, and Matthew S. Zhang. In-and-Out: algorithmic diffusion for sampling convex bodies. Random Structures & Algorithms, 68(3):e70061, 2026. [Lov90]

László Lovász. How to compute the volume? Jber. d. Dt. Math.-Verein, Jubiläumstagung, pages 138–151, 1990.

[Lov99]

László Lovász. Hit-and-run mixes fast. Mathematical Programming, 86(3):443–461, 1999.

[LS90]

László Lovász and Miklós Simonovits. The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. In Symposium on Foundations of Computer Science, pages 346–354. IEEE, 1990.

[LS93]

László Lovász and Miklós Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures & Algorithms, 4(4):359–412, 1993.

[LV06a]

László Lovász and Santosh S. Vempala. Hit-and-run from a corner. SIAM Journal on Computing, 35(4):985–1005, 2006.

[LV06b]

László Lovász and Santosh S. Vempala. Simulated annealing in convex bodies and an O∗ (n4 ) volume algorithm. Journal of Computer and System Sciences, 72(2):392–417, 2006.

[LV07]

László Lovász and Santosh S. Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms, 30(3):307–358, 2007.

[LV23]

Aditi Laddha and Santosh S. Vempala. Convergence of Gibbs sampling: coordinate hit-and-run mixes fast. Discrete & Computational Geometry, 70(2):406–425, 2023.

11

[NRS25]

Hariharan Narayanan, Amit Rajaraman, and Piyush Srivastava. Sampling from convex sets with a cold start using multiscale decompositions. Probability Theory and Related Fields, 191(3-4):1169– 1232, 2025.

[NS22]

Hariharan Narayanan and Piyush Srivastava. On the mixing time of coordinate hit-and-run. Combinatorics, Probability and Computing, 31(2):320–332, 2022.

[Smi84]

Robert L. Smith. Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Operations Research, 32(6):1296–1308, 1984.

[Tur71]

Valentin F. Turchin. On the computation of multidimensional integrals by the Monte-Carlo method. Theory of Probability & Its Applications, 16(4):720–724, 1971.

[Vem05]

Santosh S. Vempala. Geometric random walks: a survey. In Combinatorial and Computational Geometry, volume 52 of Math. Sci. Res. Inst. Publ., pages 577–616. Cambridge Univ. Press, 2005.

[Zsu20]

Sándor Zsuppán. Connections between optimal constants in some norm inequalities for differential forms. Zeitschrift für Analysis und ihre Anwendungen, 39(2):171–184, 2020.

A

Functional-analytic background

This appendix expands the functional-analytic facts used in the proof. All Sobolev spaces are taken over the open set K. A standard reference is Evans [Eva10, Chapter 5]. Hilbert spaces. A real Hilbert space is a vector space F with an inner product ⟨f, g⟩F that is complete in the induced norm ∥f ∥2F := ⟨f, f ⟩F , where completeness means that every Cauchy sequence converges to an element of the same space. If T : F → G is a bounded linear map between Hilbert spaces, its adjoint is the unique bounded map T ∗ : G → F satisfying ⟨T f, g⟩G = ⟨f, T ∗ g⟩F

for every f ∈ F, g ∈ G .

The Hilbert projection theorem states that every nonempty closed convex set contains a unique element of minimum norm. Weak derivatives.

For smooth f and φ ∈ Cc∞ (K), integration by parts gives Z K

f ∂j φ dx = −

Z K

(∂j f ) φ dx .

There is no boundary term because φ is compactly supported in K. We take this identity as the definition for f ∈ L2 (K) that need not possess a classical derivative: a function vj ∈ L2 (K) is the weak derivative ∂j f if Z K

f ∂j φ dx = −

Z K

vj φ dx

for every φ ∈ Cc∞ (K) .

Thus, the definition preserves precisely the integration-by-parts rule needed later. The weak derivative is unique (in a.e. sense). It is also stable under L2 limits: if fk → f and ∂j fk → vj in L2 (K), passing to the limit in the preceding identity shows that ∂j f = vj . Sobolev spaces. 1

2

The Sobolev space is 2

H (K) := {f ∈ L (K) : ∂j f ∈ L (K) for every j ∈ [n]}

with norm ∥f ∥2H 1 (K) :=

Z

(|f |2 +|∇f |2 ) dx .

K

The stability of weak derivatives under limits shows that H 1 (K) is complete, hence Hilbert. Let us consider the H 1 -closure of smooth functions with compact support in K, H01 (K) := H 1 (K)

Cc∞ (K) . Namely, for any f ∈ H01 (K), there exists a sequence of compactly-supported smooth functions φk such that φk → f in the H 1 norm. This closure encodes a zero boundary condition without requiring pointwise boundary values. 12

Actions on functions and measures. Let B(K) be the Borel σ-algebra of K. A Markov kernel is a map P : K × B(K) → [0, 1] such that P (x, ·) is a probability measure for every x ∈ K and x 7→ P (x, A) is measurable for every A ∈ B(K). For a bounded measurable function f and a probability measure µ, define Z

(P f )(x) :=

Z

f (y) P (x, dy),

P (x, A) dµ(x) .

(µP )(A) :=

K

K

The first action is the associated Markov operator on functions, while the second one is the law after one transition from an initial law µ. Stationarity and reversibility. A probability measure π is stationary if πP = π. In this case π(P f ) = πf , so P preserves L20 (π). Jensen’s inequality and stationarity give ∥P f ∥22 ≤

Z

P (f 2 ) dπ =

K

Z K

f 2 dπ = ∥f ∥22 ,

so P is a bounded linear map. Then, its adjoint P ∗ is characterized by ⟨P f, g⟩π = ⟨f, P ∗ g⟩π for every f, g ∈ L2 (π). The operator is self-adjoint if P = P ∗ . A Markov kernel P is reversible with respect to π if dπ(x) P (x, dy) = dπ(y) P (y, dx). This is equivalent to self-adjointness of P on L2 (π).

B

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

Throughout this section, we use Ω ⊂ Rn for the domain, Q = L20 (Ω) for the space of square-integrable functions over Ω with zero mean and norm ∥f ∥Q := ∥f ∥2 , and V = H01 (Ω; Rn ) for the space of vector fields on Ω with square-integrable derivatives that vanish on the boundary and norm ∥v∥V = ∥∇v∥2 (note that this is the L2 -norm of the Frobenius norm of ∇v ∈ Rn×n ). As implied in §1.2.2, we will R R focus on the divergence operator div : V → Q. Since Ω div v = ∂Ω v · ν = 0 for v ∈ V (here, ν is the outward normal vector), this divergence operator is well-defined. In this section, we will recap the proof of Theorem 1.4 for the reader’s convenience, focusing on Euclidean domains. Note that this result follows from combining [Cos17, Theorem 2.1] and [Zsu20, Lemma 3.4]. The proof of the theorem will follow from the following lemmas. The first one is just a dual definition of CBA . Lemma B.1 (Duality). The following are equivalent for any C > 0: 1. For any f ∈ Q, there exists v ∈ V such that div v = f and ∥∇v∥22 ≤ C ∥f ∥22 . 2. For any f ∈ Q, it holds that ∥f ∥22 ≤ C (supv∈V,v̸=0

⟨f,div v⟩Q 2 ∥∇v∥2 ) .

When solving div v = f , the Babuška–Aziz constant essentially asks how large ∥v∥V is compared with ∥f ∥Q , and this is the first statement (i.e., ∥v∥V ≤ C 1/2 ∥div v∥Q for some v ∈ V ). Consider the adjoint div∗ : Q → V such that ⟨f, div v⟩Q = ⟨div∗ f, v⟩V . Then, the RHS in the second statement is equivalent to ∥f ∥Q ≤ C 1/2 ∥div∗ f ∥V . The next lemma derives an explicit solution of the supremum on the RHS in the previous lemma using the Riesz representation theorem. Lemma B.2 (Map to vector field). For any f ∈ Q, there is a unique u ∈ V such that ⟨f, div v⟩Q = ⟨u, v⟩V for any v ∈ V , and ⟨f, div v⟩Q ∥∇u∥2 = sup . ∥∇v∥2 v∈V,v̸=0 13

Proof. The map v 7→ ⟨f, div v⟩ is a bounded linear map, since |⟨f, div v⟩| ≤ ∥f ∥2 ∥div v∥2 ≤ √ n ∥f ∥2 ∥∇v∥2 . By the Riesz representation theorem, there is a unique u ∈ V such that ⟨f, div v⟩Q = ⟨u, v⟩V = ⟨∇u, ∇v⟩ ≤ ∥∇u∥2 ∥∇v∥2 . Hence, the supremum on the RHS in the lemma statement is at most ∥∇u∥2 . Setting v = u shows equality. Due to this lemma, it now suffices to show ∥f ∥Q ≤ C 1/2 ∥u∥V for some C. The next lemma is a calculus identity about divergence of vector fields. Lemma B.3. For u ∈ V , define the n × n matrix function G as Gij := ∂j ui − ∂i uj with ∥G∥2 := R P 2 2 2 2 i<j Gij dx. Then, ∥∇u∥2 = ∥div u∥2 + ∥G∥ . Ω Proof. Using integration by parts twice and the fact that partial derivatives commute, ∥div u∥22 =

XZ ij

∂i ui ∂j uj = −

Ω

XZ ij

ui ∂i ∂j uj =

Ω

X

−

ij

Z

ui ∂j ∂i uj = Ω

XZ ij

∂j ui ∂i uj .

Ω

Let us now compute ∥G∥2 : ∥G∥2 =

XZ i<j

(∂j ui − ∂i uj )2 =

Ω

X X 1X (∂j ui − ∂i uj )2 = (∂i uj )2 − ∂j ui ∂i uj 2 ij Ω ij Ω ij Ω Z

Z

Z

= ∥∇u∥22 − ∥div u∥22 , which completes the proof. Next, using this definition of G, we get useful identities. Lemma B.4. For f ∈ Q, let u ∈ V be the vector field given by Lemma B.2 and G be the matrix function for u defined in Lemma B.3. Then for h := f − div u, we have 1.

R

Ω h = 0;

2. ∇h = div G (i.e., ∂i h =

Pn

j=1 ∂j Gij for i ∈ [n]);

3. ⟨h, div u⟩Q = ∥G∥2 . R

R

R

R

Proof. Since u = 0 on ∂Ω, we have Ω div u = ∂Ω ⟨u, ν⟩ = 0. Hence, Ω h = Ω (f − div u) = 0. Next, using weak derivatives and integration by parts, we can deduce ∆u = ∇f from ⟨f, div v⟩Q = ⟨u, v⟩V . Using this, for each i, X j

∂j Gij =

X

∂j (∂j ui − ∂i uj ) = ∆ui − ∂i div u = ∂i f − ∂i div u = ∂i h .

j

Taking v = u in the definition of u, we obtain ⟨f, div u⟩Q = ∥∇u∥22 = ∥div u∥22 + ∥G∥2 , and this implies that ⟨h, div u⟩Q = ⟨f − div u, div u⟩Q = ∥G∥2 . The following lemma captures the heart of the argument. Recall that δ(x) is the distance of x to the boundary of Ω. Lemma B.5. For any h ∈ Q and G an anti-symmetric matrix function satisfying ∇h = div G, we have ∥δ∇h∥2 ≤ 2∥G∥. Hence, if Ω has finite improved Poincaré constant CIPI , then ∥h∥22 ≤ 4CIPI ∥G∥2 . 14

Proof. By a standard regularization argument, it suffices to prove the claim for smooth h and G; the general case follows by approximation. We start with the relation between h and G. Using ∇h = div G in (i) below, Z

∥δ∇h∥22 =

δ 2 |∇h|2 =

Ω

= −2

XZ i

XZ

(i)

Ω

δ (∂j δ)(∂i h) Gij −

Ω

ij

XZ

δ 2 ∂i h∂i h =

ij

XZ ij

δ 2 ∂i h∂j Gij = − (ii)

Ω

δ 2 (∂ij h) Gij = −2 (iii)

Ω

XZ ij

XZ ij

∂j (δ 2 ∂i h) Gij

Ω

δ (∂j δ)(∂i h) Gij ,

Ω

where in (ii), we used integration by parts and the fact that δ = 0 on ∂Ω, and in (iii), we used ⟨∇2 h, G⟩ = 0 since the Hessian of h is symmetric, and G is anti-symmetric. Then, ∥δ∇h∥22 = −2 ≤2

Z

δ Ω

Z

δ Ω

X

{(∂j δ)(∂i h) − (∂i δ)(∂j h)} Gij ≤ 2

Z

X

G2ij

1/2

Ω

i<j

X

δ

{(∂j δ)(∂i h) − (∂i δ)(∂j h)}2

1/2 X

i<j

{(∂j δ)(∂i h) − (∂i δ)(∂j h)} Gij

i<j

.

i<j

Next, the summation in the first term is equal to |∇δ|2 |∇h|2 − ⟨∇δ, ∇h⟩2 and thus at most |∇δ|2 |∇h|2 ≤ |∇h|2 , since δ is 1-Lipschitz. Therefore, ∥δ∇h∥22 ≤ 2

Z Ω

δ |∇h|

X

G2ij

1/2

≤2

Z

2

2

δ |∇h|

Ω

i<j

1/2 Z X Ω i<j

G2ij

1/2

,

which completes the proof. With these lemmas in hand, we can prove the main theorem of this section. Proof of Theorem 1.4. Let f ∈ Q. Pick u ∈ V from Lemma B.2 and G from Lemma B.3 for this u. Then for h = f − div u, we have ∥h∥22 ≤ 4CIPI ∥G∥2 by Lemma B.5. Moreover, using Lemma B.4 and Cauchy–Schwarz, ∥G∥2 = ⟨h, div u⟩Q ≤ ∥h∥2 ∥div u∥2 ≤ 2 CIPI ∥G∥ ∥div u∥2 , p

which implies ∥G∥2 ≤ 4CIPI ∥div u∥22 . Finally, ∥f ∥22 = ∥h∥22 + ∥div u∥22 + 2⟨h, div u⟩Q ≤ 4CIPI ∥G∥2 + ∥div u∥22 + 2∥G∥2 ≤ 4CIPI ∥G∥2 + ∥div u∥22 + ∥G∥2 + 4CIPI ∥div u∥22 = (1 + 4CIPI ) (∥div u∥22 + ∥G∥2 ) ⟨f, div v⟩Q
2 = (1 + 4CIPI )∥∇u∥22 = (1 + 4CIPI ) sup ∥∇v∥2 v∈V,v̸=0 which proves the theorem.

15

Related documents

• Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run#625423
• Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run#623150
• Observable- and state-selective prethermalization and bounds on prethermal lifetimes#821626
• Spectral theory for dynamical large deviations in non-Markov self-interacting processes#1154589
• Cosmology Without Origins#87027